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 }