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 }