https://github.com/akkartik/mu/blob/main/412render-float-decimal.mu
  1 # print out floats in decimal
  2 # https://research.swtch.com/ftoa
  3 #
  4 # Basic idea:
  5 #   Ignoring sign, floating point numbers are represented as 1.mantissa * 2^exponent
  6 #   Therefore, to print a float in decimal, we need to:
  7 #     - compute its value without decimal point
  8 #     - convert to an array of decimal digits
  9 #     - print out the array while inserting the decimal point appropriately
 10 #
 11 # Basic complication: the computation generates numbers larger than an int can
 12 # hold. We need a way to represent big ints.
 13 #
 14 # Key insight: use a representation for big ints that's close to what we need
 15 # anyway, an array of decimal digits.
 16 #
 17 # Style note: we aren't creating a big int library here. The only operations
 18 # we need are halving and doubling. Following the link above, it seems more
 19 # comprehensible to keep these operations inlined so that we can track the
 20 # position of the decimal point with dispatch.
 21 #
 22 # This approach turns out to be fast enough for most purposes.
 23 # Optimizations, however, get wildly more complex.
 24 
 25 fn test-write-float-decimal-approximate-normal {
 26   var s-storage: (stream byte 0x10)
 27   var s/ecx: (addr stream byte) <- address s-storage
 28   # 0.5
 29   var half/xmm0: float <- rational 1, 2
 30   write-float-decimal-approximate s, half, 3
 31   check-stream-equal s, "0.5", "F - test-write-float-decimal-approximate-normal 0.5"
 32   # 0.25
 33   clear-stream s
 34   var quarter/xmm0: float <- rational 1, 4
 35   write-float-decimal-approximate s, quarter, 3
 36   check-stream-equal s, "0.25", "F - test-write-float-decimal-approximate-normal 0.25"
 37   # 0.75
 38   clear-stream s
 39   var three-quarters/xmm0: float <- rational 3, 4
 40   write-float-decimal-approximate s, three-quarters, 3
 41   check-stream-equal s, "0.75", "F - test-write-float-decimal-approximate-normal 0.75"
 42   # 0.125
 43   clear-stream s
 44   var eighth/xmm0: float <- rational 1, 8
 45   write-float-decimal-approximate s, eighth, 3
 46   check-stream-equal s, "0.125", "F - test-write-float-decimal-approximate-normal 0.125"
 47   # 0.0625; start using scientific notation
 48   clear-stream s
 49   var sixteenth/xmm0: float <- rational 1, 0x10
 50   write-float-decimal-approximate s, sixteenth, 3
 51   check-stream-equal s, "6.25e-2", "F - test-write-float-decimal-approximate-normal 0.0625"
 52   # sqrt(2); truncate floats with lots of digits after the decimal but not too many before
 53   clear-stream s
 54   var two-f/xmm0: float <- rational 2, 1
 55   var sqrt-2/xmm0: float <- square-root two-f
 56   write-float-decimal-approximate s, sqrt-2, 3
 57   check-stream-equal s, "1.414", "F - test-write-float-decimal-approximate-normal √2"
 58 }
 59 
 60 # print whole integers without decimals
 61 fn test-write-float-decimal-approximate-integer {
 62   var s-storage: (stream byte 0x10)
 63   var s/ecx: (addr stream byte) <- address s-storage
 64   # 1
 65   var one-f/xmm0: float <- rational 1, 1
 66   write-float-decimal-approximate s, one-f, 3
 67   check-stream-equal s, "1", "F - test-write-float-decimal-approximate-integer 1"
 68   # 2
 69   clear-stream s
 70   var two-f/xmm0: float <- rational 2, 1
 71   write-float-decimal-approximate s, two-f, 3
 72   check-stream-equal s, "2", "F - test-write-float-decimal-approximate-integer 2"
 73   # 10
 74   clear-stream s
 75   var ten-f/xmm0: float <- rational 0xa, 1
 76   write-float-decimal-approximate s, ten-f, 3
 77   check-stream-equal s, "10", "F - test-write-float-decimal-approximate-integer 10"
 78   # -10
 79   clear-stream s
 80   var minus-ten-f/xmm0: float <- rational -0xa, 1
 81   write-float-decimal-approximate s, minus-ten-f, 3
 82   check-stream-equal s, "-10", "F - test-write-float-decimal-approximate-integer -10"
 83   # 999
 84   clear-stream s
 85   var minus-ten-f/xmm0: float <- rational 0x3e7, 1
 86   write-float-decimal-approximate s, minus-ten-f, 3
 87   check-stream-equal s, "999", "F - test-write-float-decimal-approximate-integer 1000"
 88   # 1000 - start using scientific notation
 89   clear-stream s
 90   var minus-ten-f/xmm0: float <- rational 0x3e8, 1
 91   write-float-decimal-approximate s, minus-ten-f, 3
 92   check-stream-equal s, "1.00e3", "F - test-write-float-decimal-approximate-integer 1000"
 93   # 100,000
 94   clear-stream s
 95   var hundred-thousand/eax: int <- copy 0x186a0
 96   var hundred-thousand-f/xmm0: float <- convert hundred-thousand
 97   write-float-decimal-approximate s, hundred-thousand-f, 3
 98   check-stream-equal s, "1.00e5", "F - test-write-float-decimal-approximate-integer 100,000"
 99 }
100 
101 fn test-write-float-decimal-approximate-zero {
102   var s-storage: (stream byte 0x10)
103   var s/ecx: (addr stream byte) <- address s-storage
104   var zero: float
105   write-float-decimal-approximate s, zero, 3
106   check-stream-equal s, "0", "F - test-write-float-decimal-approximate-zero"
107 }
108 
109 fn test-write-float-decimal-approximate-negative-zero {
110   var s-storage: (stream byte 0x10)
111   var s/ecx: (addr stream byte) <- address s-storage
112   var n: int
113   copy-to n, 0x80000000
114   var negative-zero/xmm0: float <- reinterpret n
115   write-float-decimal-approximate s, negative-zero, 3
116   check-stream-equal s, "-0", "F - test-write-float-decimal-approximate-negative-zero"
117 }
118 
119 fn test-write-float-decimal-approximate-infinity {
120   var s-storage: (stream byte 0x10)
121   var s/ecx: (addr stream byte) <- address s-storage
122   var n: int
123   #          0|11111111|00000000000000000000000
124   #          0111|1111|1000|0000|0000|0000|0000|0000
125   copy-to n, 0x7f800000
126   var infinity/xmm0: float <- reinterpret n
127   write-float-decimal-approximate s, infinity, 3
128   check-stream-equal s, "Inf", "F - test-write-float-decimal-approximate-infinity"
129 }
130 
131 fn test-write-float-decimal-approximate-negative-infinity {
132   var s-storage: (stream byte 0x10)
133   var s/ecx: (addr stream byte) <- address s-storage
134   var n: int
135   copy-to n, 0xff800000
136   var negative-infinity/xmm0: float <- reinterpret n
137   write-float-decimal-approximate s, negative-infinity, 3
138   check-stream-equal s, "-Inf", "F - test-write-float-decimal-approximate-negative-infinity"
139 }
140 
141 fn test-write-float-decimal-approximate-not-a-number {
142   var s-storage: (stream byte 0x10)
143   var s/ecx: (addr stream byte) <- address s-storage
144   var n: int
145   copy-to n, 0xffffffff  # exponent must be all 1's, and mantissa must be non-zero
146   var nan/xmm0: float <- reinterpret n
147   write-float-decimal-approximate s, nan, 3
148   check-stream-equal s, "NaN", "F - test-write-float-decimal-approximate-not-a-number"
149 }
150 
151 fn render-float-decimal screen: (addr screen), in: float, precision: int, x: int, y: int, color: int, background-color: int -> _/eax: int {
152   var s-storage: (stream byte 0x10)
153   var s/esi: (addr stream byte) <- address s-storage
154   write-float-decimal-approximate s, in, precision
155   var width/eax: int <- copy 0
156   var height/ecx: int <- copy 0
157   width, height <- screen-size screen
158   var result/eax: int <- draw-stream-rightward screen, s, x, width, y, color, background-color
159   return result
160 }
161 
162 # 'precision' controls the maximum width past which we resort to scientific notation
163 fn write-float-decimal-approximate out: (addr stream byte), in: float, precision: int {
164   # - special names
165   var bits/eax: int <- reinterpret in
166   compare bits, 0
167   {
168     break-if-!=
169     write out, "0"
170     return
171   }
172   compare bits, 0x80000000
173   {
174     break-if-!=
175     write out, "-0"
176     return
177   }
178   compare bits, 0x7f800000
179   {
180     break-if-!=
181     write out, "Inf"
182     return
183   }
184   compare bits, 0xff800000
185   {
186     break-if-!=
187     write out, "-Inf"
188     return
189   }
190   var exponent/ecx: int <- copy bits
191   exponent <- shift-right 0x17  # 23 bits of mantissa
192   exponent <- and 0xff
193   exponent <- subtract 0x7f
194   compare exponent, 0x80
195   {
196     break-if-!=
197     write out, "NaN"
198     return
199   }
200   # - regular numbers
201   var sign/edx: int <- copy bits
202   sign <- shift-right 0x1f
203   {
204     compare sign, 1
205     break-if-!=
206     append-byte out, 0x2d/minus
207   }
208 
209   # v = 1.mantissa (in base 2) << 0x17
210   var v/ebx: int <- copy bits
211   v <- and 0x7fffff
212   v <- or 0x00800000  # insert implicit 1
213   # e = exponent - 0x17
214   var e/ecx: int <- copy exponent
215   e <- subtract 0x17  # move decimal place from before mantissa to after
216 
217   # initialize buffer with decimal representation of v
218   # unlike https://research.swtch.com/ftoa, no ascii here
219   var buf-storage: (array byte 0x7f)
220   var buf/edi: (addr array byte) <- address buf-storage
221   var n/eax: int <- decimal-digits v, buf
222   # I suspect we can do without reversing, but we'll follow https://research.swtch.com/ftoa
223   # closely for now.
224   reverse-digits buf, n
225 
226   # loop if e > 0
227   {
228     compare e, 0
229     break-if-<=
230     n <- double-array-of-decimal-digits buf, n
231     e <- decrement
232     loop
233   }
234 
235   var dp/edx: int <- copy n
236 
237   # loop if e < 0
238   {
239     compare e, 0
240     break-if->=
241     n, dp <- halve-array-of-decimal-digits buf, n, dp
242     e <- increment
243     loop
244   }
245 
246   _write-float-array-of-decimal-digits out, buf, n, dp, precision
247 }
248 
249 # store the decimal digits of 'n' into 'buf', units first
250 # n must be positive
251 fn decimal-digits n: int, _buf: (addr array byte) -> _/eax: int {
252   var buf/edi: (addr array byte) <- copy _buf
253   var i/ecx: int <- copy 0
254   var curr/eax: int <- copy n
255   var curr-byte/edx: int <- copy 0
256   {
257     compare curr, 0
258     break-if-=
259     curr, curr-byte <- integer-divide curr, 0xa
260     var dest/ebx: (addr byte) <- index buf, i
261     copy-byte-to *dest, curr-byte
262     i <- increment
263     loop
264   }
265   return i
266 }
267 
268 fn reverse-digits _buf: (addr array byte), n: int {
269   var buf/esi: (addr array byte) <- copy _buf
270   var left/ecx: int <- copy 0
271   var right/edx: int <- copy n
272   right <- decrement
273   {
274     compare left, right
275     break-if->=
276     {
277       var l-a/ecx: (addr byte) <- index buf, left
278       var r-a/edx: (addr byte) <- index buf, right
279       var l/ebx: byte <- copy-byte *l-a
280       var r/eax: byte <- copy-byte *r-a
281       copy-byte-to *l-a, r
282       copy-byte-to *r-a, l
283     }
284     left <- increment
285     right <- decrement
286     loop
287   }
288 }
289 
290 fn double-array-of-decimal-digits _buf: (addr array byte), _n: int -> _/eax: int {
291   var buf/edi: (addr array byte) <- copy _buf
292   # initialize delta
293   var delta/edx: int <- copy 0
294   {
295     var curr/ebx: (addr byte) <- index buf, 0
296     var tmp/eax: byte <- copy-byte *curr
297     compare tmp, 5
298     break-if-<
299     delta <- copy 1
300   }
301   # loop
302   var x/eax: int <- copy 0
303   var i/ecx: int <- copy _n
304   i <- decrement
305   {
306     compare i, 0
307     break-if-<=
308     # x += 2*buf[i]
309     {
310       var tmp/ecx: (addr byte) <- index buf, i
311       var tmp2/ecx: byte <- copy-byte *tmp
312       x <- add tmp2
313       x <- add tmp2
314     }
315     # x, buf[i+delta] = x/10, x%10
316     {
317       var dest-index/ecx: int <- copy i
318       dest-index <- add delta
319       var dest/edi: (addr byte) <- index buf, dest-index
320       var next-digit/edx: int <- copy 0
321       x, next-digit <- integer-divide x, 0xa
322       copy-byte-to *dest, next-digit
323     }
324     #
325     i <- decrement
326     loop
327   }
328   # final patch-up
329   var n/eax: int <- copy _n
330   compare delta, 1
331   {
332     break-if-!=
333     var curr/ebx: (addr byte) <- index buf, 0
334     var one/edx: int <- copy 1
335     copy-byte-to *curr, one
336     n <- increment
337   }
338   return n
339 }
340 
341 fn halve-array-of-decimal-digits _buf: (addr array byte), _n: int, _dp: int -> _/eax: int, _/edx: int {
342   var buf/edi: (addr array byte) <- copy _buf
343   var n/eax: int <- copy _n
344   var dp/edx: int <- copy _dp
345   # initialize one side
346   {
347     # if buf[n-1]%2 == 0, break
348     var right-index/ecx: int <- copy n
349     right-index <- decrement
350     var right-a/ecx: (addr byte) <- index buf, right-index
351     var right/ecx: byte <- copy-byte *right-a
352     var right-int/ecx: int <- copy right
353     var remainder/edx: int <- copy 0
354     {
355       var dummy/eax: int <- copy 0
356       dummy, remainder <- integer-divide right-int, 2
357     }
358     compare remainder, 0
359     break-if-=
360     # buf[n] = 0
361     var next-a/ecx: (addr byte) <- index buf, n
362     var zero/edx: byte <- copy 0
363     copy-byte-to *next-a, zero
364     # n++
365     n <- increment
366   }
367   # initialize the other
368   var delta/ebx: int <- copy 0
369   var x/esi: int <- copy 0
370   {
371     # if buf[0] >= 2, break
372     var left/ecx: (addr byte) <- index buf, 0
373     var src/ecx: byte <- copy-byte *left
374     compare src, 2
375     break-if->=
376     # delta, x = 1, buf[0]
377     delta <- copy 1
378     x <- copy src
379     # n--
380     n <- decrement
381     # dp--
382     dp <- decrement
383   }
384   # loop
385   var i/ecx: int <- copy 0
386   {
387     compare i, n
388     break-if->=
389     # x = x*10 + buf[i+delta]
390     {
391       var ten/edx: int <- copy 0xa
392       x <- multiply ten
393       var src-index/edx: int <- copy i
394       src-index <- add delta
395       var src-a/edx: (addr byte) <- index buf, src-index
396       var src/edx: byte <- copy-byte *src-a
397       x <- add src
398     }
399     # buf[i], x = x/2, x%2
400     {
401       var quotient/eax: int <- copy 0
402       var remainder/edx: int <- copy 0
403       quotient, remainder <- integer-divide x, 2
404       x <- copy remainder
405       var dest/edx: (addr byte) <- index buf, i
406       copy-byte-to *dest, quotient
407     }
408     #
409     i <- increment
410     loop
411   }
412   return n, dp
413 }
414 
415 fn _write-float-array-of-decimal-digits out: (addr stream byte), _buf: (addr array byte), n: int, dp: int, precision: int {
416   var buf/edi: (addr array byte) <- copy _buf
417   {
418     compare dp, 0
419     break-if->=
420     _write-float-array-of-decimal-digits-in-scientific-notation out, buf, n, dp, precision
421     return
422   }
423   {
424     var dp2/eax: int <- copy dp
425     compare dp2, precision
426     break-if-<=
427     _write-float-array-of-decimal-digits-in-scientific-notation out, buf, n, dp, precision
428     return
429   }
430   {
431     compare dp, 0
432     break-if-!=
433     append-byte out, 0x30/0
434   }
435   var i/eax: int <- copy 0
436   # bounds = min(n, dp+3)
437   var limit/edx: int <- copy dp
438   limit <- add 3
439   {
440     compare limit, n
441     break-if-<=
442     limit <- copy n
443   }
444   {
445     compare i, limit
446     break-if->=
447     # print '.' if necessary
448     compare i, dp
449     {
450       break-if-!=
451       append-byte out, 0x2e/decimal-point
452     }
453     var curr-a/ecx: (addr byte) <- index buf, i
454     var curr/ecx: byte <- copy-byte *curr-a
455     var curr-int/ecx: int <- copy curr
456     curr-int <- add 0x30/0
457     append-byte out, curr-int
458     #
459     i <- increment
460     loop
461   }
462 }
463 
464 fn _write-float-array-of-decimal-digits-in-scientific-notation out: (addr stream byte), _buf: (addr array byte), n: int, dp: int, precision: int {
465   var buf/edi: (addr array byte) <- copy _buf
466   var i/eax: int <- copy 0
467   {
468     compare i, n
469     break-if->=
470     compare i, precision
471     break-if->=
472     compare i, 1
473     {
474       break-if-!=
475       append-byte out, 0x2e/decimal-point
476     }
477     var curr-a/ecx: (addr byte) <- index buf, i
478     var curr/ecx: byte <- copy-byte *curr-a
479     var curr-int/ecx: int <- copy curr
480     curr-int <- add 0x30/0
481     append-byte out, curr-int
482     #
483     i <- increment
484     loop
485   }
486   append-byte out, 0x65/e
487   decrement dp
488   write-int32-decimal out, dp
489 }
490 
491 # follows the structure of write-float-decimal-approximate
492 # 'precision' controls the maximum width past which we resort to scientific notation
493 fn float-size in: float, precision: int -> _/eax: int {
494   # - special names
495   var bits/eax: int <- reinterpret in
496   compare bits, 0
497   {
498     break-if-!=
499     return 1  # for "0"
500   }
501   compare bits, 0x80000000
502   {
503     break-if-!=
504     return 2  # for "-0"
505   }
506   compare bits, 0x7f800000
507   {
508     break-if-!=
509     return 3  # for "Inf"
510   }
511   compare bits, 0xff800000
512   {
513     break-if-!=
514     return 4  # for "-Inf"
515   }
516   var exponent/ecx: int <- copy bits
517   exponent <- shift-right 0x17  # 23 bits of mantissa
518   exponent <- and 0xff
519   exponent <- subtract 0x7f
520   compare exponent, 0x80
521   {
522     break-if-!=
523     return 3  # for "NaN"
524   }
525   # - regular numbers
526   # v = 1.mantissa (in base 2) << 0x17
527   var v/ebx: int <- copy bits
528   v <- and 0x7fffff
529   v <- or 0x00800000  # insert implicit 1
530   # e = exponent - 0x17
531   var e/ecx: int <- copy exponent
532   e <- subtract 0x17  # move decimal place from before mantissa to after
533 
534   # initialize buffer with decimal representation of v
535   var buf-storage: (array byte 0x7f)
536   var buf/edi: (addr array byte) <- address buf-storage
537   var n/eax: int <- decimal-digits v, buf
538   reverse-digits buf, n
539 
540   # loop if e > 0
541   {
542     compare e, 0
543     break-if-<=
544     n <- double-array-of-decimal-digits buf, n
545     e <- decrement
546     loop
547   }
548 
549   var dp/edx: int <- copy n
550 
551   # loop if e < 0
552   {
553     compare e, 0
554     break-if->=
555     n, dp <- halve-array-of-decimal-digits buf, n, dp
556     e <- increment
557     loop
558   }
559 
560   compare dp, 0
561   {
562     break-if->=
563     return 8  # hacky for scientific notation
564   }
565   {
566     var dp2/eax: int <- copy dp
567     compare dp2, precision
568     break-if-<=
569     return 8  # hacky for scientific notation
570   }
571 
572   # result = min(n, dp+3)
573   var result/ecx: int <- copy dp
574   result <- add 3
575   {
576     compare result, n
577     break-if-<=
578     result <- copy n
579   }
580 
581   # account for decimal point
582   compare dp, n
583   {
584     break-if->=
585     result <- increment
586   }
587 
588   # account for sign
589   var sign/edx: int <- reinterpret in
590   sign <- shift-right 0x1f
591   {
592     compare sign, 1
593     break-if-!=
594     result <- increment
595   }
596   return result
597 }