Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 597 lines 16 KiB Raw Permalink Blame History

 `# print out floats in decimal` `# https://research.swtch.com/ftoa` `#` `# Basic idea:` `# Ignoring sign, floating point numbers are represented as 1.mantissa * 2^exponent` `# Therefore, to print a float in decimal, we need to:` `# - compute its value without decimal point` `# - convert to an array of decimal digits` `# - print out the array while inserting the decimal point appropriately` `#` `# Basic complication: the computation generates numbers larger than an int can` `# hold. We need a way to represent big ints.` `#` `# Key insight: use a representation for big ints that's close to what we need` `# anyway, an array of decimal digits.` `#` `# Style note: we aren't creating a big int library here. The only operations` `# we need are halving and doubling. Following the link above, it seems more` `# comprehensible to keep these operations inlined so that we can track the` `# position of the decimal point with dispatch.` `#` `# This approach turns out to be fast enough for most purposes.` `# Optimizations, however, get wildly more complex.` `fn test-write-float-decimal-approximate-normal {` ` var s-storage: (stream byte 0x10)` ` var s/ecx: (addr stream byte) <- address s-storage` ` # 0.5` ` var half/xmm0: float <- rational 1, 2` ` write-float-decimal-approximate s, half, 3` ` check-stream-equal s, "0.5", "F - test-write-float-decimal-approximate-normal 0.5"` ` # 0.25` ` clear-stream s` ` var quarter/xmm0: float <- rational 1, 4` ` write-float-decimal-approximate s, quarter, 3` ` check-stream-equal s, "0.25", "F - test-write-float-decimal-approximate-normal 0.25"` ` # 0.75` ` clear-stream s` ` var three-quarters/xmm0: float <- rational 3, 4` ` write-float-decimal-approximate s, three-quarters, 3` ` check-stream-equal s, "0.75", "F - test-write-float-decimal-approximate-normal 0.75"` ` # 0.125` ` clear-stream s` ` var eighth/xmm0: float <- rational 1, 8` ` write-float-decimal-approximate s, eighth, 3` ` check-stream-equal s, "0.125", "F - test-write-float-decimal-approximate-normal 0.125"` ` # 0.0625; start using scientific notation` ` clear-stream s` ` var sixteenth/xmm0: float <- rational 1, 0x10` ` write-float-decimal-approximate s, sixteenth, 3` ` check-stream-equal s, "6.25e-2", "F - test-write-float-decimal-approximate-normal 0.0625"` ` # sqrt(2); truncate floats with lots of digits after the decimal but not too many before` ` clear-stream s` ` var two-f/xmm0: float <- rational 2, 1` ` var sqrt-2/xmm0: float <- square-root two-f` ` write-float-decimal-approximate s, sqrt-2, 3` ` check-stream-equal s, "1.414", "F - test-write-float-decimal-approximate-normal √2"` `}` `# print whole integers without decimals` `fn test-write-float-decimal-approximate-integer {` ` var s-storage: (stream byte 0x10)` ` var s/ecx: (addr stream byte) <- address s-storage` ` # 1` ` var one-f/xmm0: float <- rational 1, 1` ` write-float-decimal-approximate s, one-f, 3` ` check-stream-equal s, "1", "F - test-write-float-decimal-approximate-integer 1"` ` # 2` ` clear-stream s` ` var two-f/xmm0: float <- rational 2, 1` ` write-float-decimal-approximate s, two-f, 3` ` check-stream-equal s, "2", "F - test-write-float-decimal-approximate-integer 2"` ` # 10` ` clear-stream s` ` var ten-f/xmm0: float <- rational 0xa, 1` ` write-float-decimal-approximate s, ten-f, 3` ` check-stream-equal s, "10", "F - test-write-float-decimal-approximate-integer 10"` ` # -10` ` clear-stream s` ` var minus-ten-f/xmm0: float <- rational -0xa, 1` ` write-float-decimal-approximate s, minus-ten-f, 3` ` check-stream-equal s, "-10", "F - test-write-float-decimal-approximate-integer -10"` ` # 999` ` clear-stream s` ` var minus-ten-f/xmm0: float <- rational 0x3e7, 1` ` write-float-decimal-approximate s, minus-ten-f, 3` ` check-stream-equal s, "999", "F - test-write-float-decimal-approximate-integer 1000"` ` # 1000 - start using scientific notation` ` clear-stream s` ` var minus-ten-f/xmm0: float <- rational 0x3e8, 1` ` write-float-decimal-approximate s, minus-ten-f, 3` ` check-stream-equal s, "1.00e3", "F - test-write-float-decimal-approximate-integer 1000"` ` # 100,000` ` clear-stream s` ` var hundred-thousand/eax: int <- copy 0x186a0` ` var hundred-thousand-f/xmm0: float <- convert hundred-thousand` ` write-float-decimal-approximate s, hundred-thousand-f, 3` ` check-stream-equal s, "1.00e5", "F - test-write-float-decimal-approximate-integer 100,000"` `}` `fn test-write-float-decimal-approximate-zero {` ` var s-storage: (stream byte 0x10)` ` var s/ecx: (addr stream byte) <- address s-storage` ` var zero: float` ` write-float-decimal-approximate s, zero, 3` ` check-stream-equal s, "0", "F - test-write-float-decimal-approximate-zero"` `}` `fn test-write-float-decimal-approximate-negative-zero {` ` var s-storage: (stream byte 0x10)` ` var s/ecx: (addr stream byte) <- address s-storage` ` var n: int` ` copy-to n, 0x80000000` ` var negative-zero/xmm0: float <- reinterpret n` ` write-float-decimal-approximate s, negative-zero, 3` ` check-stream-equal s, "-0", "F - test-write-float-decimal-approximate-negative-zero"` `}` `fn test-write-float-decimal-approximate-infinity {` ` var s-storage: (stream byte 0x10)` ` var s/ecx: (addr stream byte) <- address s-storage` ` var n: int` ` # 0|11111111|00000000000000000000000` ` # 0111|1111|1000|0000|0000|0000|0000|0000` ` copy-to n, 0x7f800000` ` var infinity/xmm0: float <- reinterpret n` ` write-float-decimal-approximate s, infinity, 3` ` check-stream-equal s, "Inf", "F - test-write-float-decimal-approximate-infinity"` `}` `fn test-write-float-decimal-approximate-negative-infinity {` ` var s-storage: (stream byte 0x10)` ` var s/ecx: (addr stream byte) <- address s-storage` ` var n: int` ` copy-to n, 0xff800000` ` var negative-infinity/xmm0: float <- reinterpret n` ` write-float-decimal-approximate s, negative-infinity, 3` ` check-stream-equal s, "-Inf", "F - test-write-float-decimal-approximate-negative-infinity"` `}` `fn test-write-float-decimal-approximate-not-a-number {` ` var s-storage: (stream byte 0x10)` ` var s/ecx: (addr stream byte) <- address s-storage` ` var n: int` ` copy-to n, 0xffffffff # exponent must be all 1's, and mantissa must be non-zero` ` var nan/xmm0: float <- reinterpret n` ` write-float-decimal-approximate s, nan, 3` ` check-stream-equal s, "NaN", "F - test-write-float-decimal-approximate-not-a-number"` `}` `fn render-float-decimal screen: (addr screen), in: float, precision: int, x: int, y: int, color: int, background-color: int -> _/eax: int {` ` var s-storage: (stream byte 0x10)` ` var s/esi: (addr stream byte) <- address s-storage` ` write-float-decimal-approximate s, in, precision` ` var width/eax: int <- copy 0` ` var height/ecx: int <- copy 0` ` width, height <- screen-size screen` ` var result/eax: int <- draw-stream-rightward screen, s, x, width, y, color, background-color` ` return result` `}` `# 'precision' controls the maximum width past which we resort to scientific notation` `fn write-float-decimal-approximate out: (addr stream byte), in: float, precision: int {` ` # - special names` ` var bits/eax: int <- reinterpret in` ` compare bits, 0` ` {` ` break-if-!=` ` write out, "0"` ` return` ` }` ` compare bits, 0x80000000` ` {` ` break-if-!=` ` write out, "-0"` ` return` ` }` ` compare bits, 0x7f800000` ` {` ` break-if-!=` ` write out, "Inf"` ` return` ` }` ` compare bits, 0xff800000` ` {` ` break-if-!=` ` write out, "-Inf"` ` return` ` }` ` var exponent/ecx: int <- copy bits` ` exponent <- shift-right 0x17 # 23 bits of mantissa` ` exponent <- and 0xff` ` exponent <- subtract 0x7f` ` compare exponent, 0x80` ` {` ` break-if-!=` ` write out, "NaN"` ` return` ` }` ` # - regular numbers` ` var sign/edx: int <- copy bits` ` sign <- shift-right 0x1f` ` {` ` compare sign, 1` ` break-if-!=` ` append-byte out, 0x2d/minus` ` }` ` # v = 1.mantissa (in base 2) << 0x17` ` var v/ebx: int <- copy bits` ` v <- and 0x7fffff` ` v <- or 0x00800000 # insert implicit 1` ` # e = exponent - 0x17` ` var e/ecx: int <- copy exponent` ` e <- subtract 0x17 # move decimal place from before mantissa to after` ` # initialize buffer with decimal representation of v` ` # unlike https://research.swtch.com/ftoa, no ascii here` ` var buf-storage: (array byte 0x7f)` ` var buf/edi: (addr array byte) <- address buf-storage` ` var n/eax: int <- decimal-digits v, buf` ` # I suspect we can do without reversing, but we'll follow https://research.swtch.com/ftoa` ` # closely for now.` ` reverse-digits buf, n` ` # loop if e > 0` ` {` ` compare e, 0` ` break-if-<=` ` n <- double-array-of-decimal-digits buf, n` ` e <- decrement` ` loop` ` }` ` var dp/edx: int <- copy n` ` # loop if e < 0` ` {` ` compare e, 0` ` break-if->=` ` n, dp <- halve-array-of-decimal-digits buf, n, dp` ` e <- increment` ` loop` ` }` ` _write-float-array-of-decimal-digits out, buf, n, dp, precision` `}` `# store the decimal digits of 'n' into 'buf', units first` `# n must be positive` `fn decimal-digits n: int, _buf: (addr array byte) -> _/eax: int {` ` var buf/edi: (addr array byte) <- copy _buf` ` var i/ecx: int <- copy 0` ` var curr/eax: int <- copy n` ` var curr-byte/edx: int <- copy 0` ` {` ` compare curr, 0` ` break-if-=` ` curr, curr-byte <- integer-divide curr, 0xa` ` var dest/ebx: (addr byte) <- index buf, i` ` copy-byte-to *dest, curr-byte` ` i <- increment` ` loop` ` }` ` return i` `}` `fn reverse-digits _buf: (addr array byte), n: int {` ` var buf/esi: (addr array byte) <- copy _buf` ` var left/ecx: int <- copy 0` ` var right/edx: int <- copy n` ` right <- decrement` ` {` ` compare left, right` ` break-if->=` ` {` ` var l-a/ecx: (addr byte) <- index buf, left` ` var r-a/edx: (addr byte) <- index buf, right` ` var l/ebx: byte <- copy-byte *l-a` ` var r/eax: byte <- copy-byte *r-a` ` copy-byte-to *l-a, r` ` copy-byte-to *r-a, l` ` }` ` left <- increment` ` right <- decrement` ` loop` ` }` `}` `fn double-array-of-decimal-digits _buf: (addr array byte), _n: int -> _/eax: int {` ` var buf/edi: (addr array byte) <- copy _buf` ` # initialize delta` ` var delta/edx: int <- copy 0` ` {` ` var curr/ebx: (addr byte) <- index buf, 0` ` var tmp/eax: byte <- copy-byte *curr` ` compare tmp, 5` ` break-if-<` ` delta <- copy 1` ` }` ` # loop` ` var x/eax: int <- copy 0` ` var i/ecx: int <- copy _n` ` i <- decrement` ` {` ` compare i, 0` ` break-if-<=` ` # x += 2*buf[i]` ` {` ` var tmp/ecx: (addr byte) <- index buf, i` ` var tmp2/ecx: byte <- copy-byte *tmp` ` x <- add tmp2` ` x <- add tmp2` ` }` ` # x, buf[i+delta] = x/10, x%10` ` {` ` var dest-index/ecx: int <- copy i` ` dest-index <- add delta` ` var dest/edi: (addr byte) <- index buf, dest-index` ` var next-digit/edx: int <- copy 0` ` x, next-digit <- integer-divide x, 0xa` ` copy-byte-to *dest, next-digit` ` }` ` #` ` i <- decrement` ` loop` ` }` ` # final patch-up` ` var n/eax: int <- copy _n` ` compare delta, 1` ` {` ` break-if-!=` ` var curr/ebx: (addr byte) <- index buf, 0` ` var one/edx: int <- copy 1` ` copy-byte-to *curr, one` ` n <- increment` ` }` ` return n` `}` `fn halve-array-of-decimal-digits _buf: (addr array byte), _n: int, _dp: int -> _/eax: int, _/edx: int {` ` var buf/edi: (addr array byte) <- copy _buf` ` var n/eax: int <- copy _n` ` var dp/edx: int <- copy _dp` ` # initialize one side` ` {` ` # if buf[n-1]%2 == 0, break` ` var right-index/ecx: int <- copy n` ` right-index <- decrement` ` var right-a/ecx: (addr byte) <- index buf, right-index` ` var right/ecx: byte <- copy-byte *right-a` ` var right-int/ecx: int <- copy right` ` var remainder/edx: int <- copy 0` ` {` ` var dummy/eax: int <- copy 0` ` dummy, remainder <- integer-divide right-int, 2` ` }` ` compare remainder, 0` ` break-if-=` ` # buf[n] = 0` ` var next-a/ecx: (addr byte) <- index buf, n` ` var zero/edx: byte <- copy 0` ` copy-byte-to *next-a, zero` ` # n++` ` n <- increment` ` }` ` # initialize the other` ` var delta/ebx: int <- copy 0` ` var x/esi: int <- copy 0` ` {` ` # if buf[0] >= 2, break` ` var left/ecx: (addr byte) <- index buf, 0` ` var src/ecx: byte <- copy-byte *left` ` compare src, 2` ` break-if->=` ` # delta, x = 1, buf[0]` ` delta <- copy 1` ` x <- copy src` ` # n--` ` n <- decrement` ` # dp--` ` dp <- decrement` ` }` ` # loop` ` var i/ecx: int <- copy 0` ` {` ` compare i, n` ` break-if->=` ` # x = x*10 + buf[i+delta]` ` {` ` var ten/edx: int <- copy 0xa` ` x <- multiply ten` ` var src-index/edx: int <- copy i` ` src-index <- add delta` ` var src-a/edx: (addr byte) <- index buf, src-index` ` var src/edx: byte <- copy-byte *src-a` ` x <- add src` ` }` ` # buf[i], x = x/2, x%2` ` {` ` var quotient/eax: int <- copy 0` ` var remainder/edx: int <- copy 0` ` quotient, remainder <- integer-divide x, 2` ` x <- copy remainder` ` var dest/edx: (addr byte) <- index buf, i` ` copy-byte-to *dest, quotient` ` }` ` #` ` i <- increment` ` loop` ` }` ` return n, dp` `}` `fn _write-float-array-of-decimal-digits out: (addr stream byte), _buf: (addr array byte), n: int, dp: int, precision: int {` ` var buf/edi: (addr array byte) <- copy _buf` ` {` ` compare dp, 0` ` break-if->=` ` _write-float-array-of-decimal-digits-in-scientific-notation out, buf, n, dp, precision` ` return` ` }` ` {` ` var dp2/eax: int <- copy dp` ` compare dp2, precision` ` break-if-<=` ` _write-float-array-of-decimal-digits-in-scientific-notation out, buf, n, dp, precision` ` return` ` }` ` {` ` compare dp, 0` ` break-if-!=` ` append-byte out, 0x30/0` ` }` ` var i/eax: int <- copy 0` ` # bounds = min(n, dp+3)` ` var limit/edx: int <- copy dp` ` limit <- add 3` ` {` ` compare limit, n` ` break-if-<=` ` limit <- copy n` ` }` ` {` ` compare i, limit` ` break-if->=` ` # print '.' if necessary` ` compare i, dp` ` {` ` break-if-!=` ` append-byte out, 0x2e/decimal-point` ` }` ` var curr-a/ecx: (addr byte) <- index buf, i` ` var curr/ecx: byte <- copy-byte *curr-a` ` var curr-int/ecx: int <- copy curr` ` curr-int <- add 0x30/0` ` append-byte out, curr-int` ` #` ` i <- increment` ` loop` ` }` `}` `fn _write-float-array-of-decimal-digits-in-scientific-notation out: (addr stream byte), _buf: (addr array byte), n: int, dp: int, precision: int {` ` var buf/edi: (addr array byte) <- copy _buf` ` var i/eax: int <- copy 0` ` {` ` compare i, n` ` break-if->=` ` compare i, precision` ` break-if->=` ` compare i, 1` ` {` ` break-if-!=` ` append-byte out, 0x2e/decimal-point` ` }` ` var curr-a/ecx: (addr byte) <- index buf, i` ` var curr/ecx: byte <- copy-byte *curr-a` ` var curr-int/ecx: int <- copy curr` ` curr-int <- add 0x30/0` ` append-byte out, curr-int` ` #` ` i <- increment` ` loop` ` }` ` append-byte out, 0x65/e` ` decrement dp` ` write-int32-decimal out, dp` `}` `# follows the structure of write-float-decimal-approximate` `# 'precision' controls the maximum width past which we resort to scientific notation` `fn float-size in: float, precision: int -> _/eax: int {` ` # - special names` ` var bits/eax: int <- reinterpret in` ` compare bits, 0` ` {` ` break-if-!=` ` return 1 # for "0"` ` }` ` compare bits, 0x80000000` ` {` ` break-if-!=` ` return 2 # for "-0"` ` }` ` compare bits, 0x7f800000` ` {` ` break-if-!=` ` return 3 # for "Inf"` ` }` ` compare bits, 0xff800000` ` {` ` break-if-!=` ` return 4 # for "-Inf"` ` }` ` var exponent/ecx: int <- copy bits` ` exponent <- shift-right 0x17 # 23 bits of mantissa` ` exponent <- and 0xff` ` exponent <- subtract 0x7f` ` compare exponent, 0x80` ` {` ` break-if-!=` ` return 3 # for "NaN"` ` }` ` # - regular numbers` ` # v = 1.mantissa (in base 2) << 0x17` ` var v/ebx: int <- copy bits` ` v <- and 0x7fffff` ` v <- or 0x00800000 # insert implicit 1` ` # e = exponent - 0x17` ` var e/ecx: int <- copy exponent` ` e <- subtract 0x17 # move decimal place from before mantissa to after` ` # initialize buffer with decimal representation of v` ` var buf-storage: (array byte 0x7f)` ` var buf/edi: (addr array byte) <- address buf-storage` ` var n/eax: int <- decimal-digits v, buf` ` reverse-digits buf, n` ` # loop if e > 0` ` {` ` compare e, 0` ` break-if-<=` ` n <- double-array-of-decimal-digits buf, n` ` e <- decrement` ` loop` ` }` ` var dp/edx: int <- copy n` ` # loop if e < 0` ` {` ` compare e, 0` ` break-if->=` ` n, dp <- halve-array-of-decimal-digits buf, n, dp` ` e <- increment` ` loop` ` }` ` compare dp, 0` ` {` ` break-if->=` ` return 8 # hacky for scientific notation` ` }` ` {` ` var dp2/eax: int <- copy dp` ` compare dp2, precision` ` break-if-<=` ` return 8 # hacky for scientific notation` ` }` ` # result = min(n, dp+3)` ` var result/ecx: int <- copy dp` ` result <- add 3` ` {` ` compare result, n` ` break-if-<=` ` result <- copy n` ` }` ` # account for decimal point` ` compare dp, n` ` {` ` break-if->=` ` result <- increment` ` }` ` # account for sign` ` var sign/edx: int <- reinterpret in` ` sign <- shift-right 0x1f` ` {` ` compare sign, 1` ` break-if-!=` ` result <- increment` ` }` ` return result` ```} ``` ``` ```