From 71e4f3812982dba2efb471283d310224e8db363e Mon Sep 17 00:00:00 2001
From: "Kartik K. Agaram" <vc@akkartik.com>
Date: Wed, 3 Mar 2021 22:09:50 -0800
Subject: 7842 - new directory organization

Baremetal is now the default build target and therefore has its sources
at the top-level. Baremetal programs build using the phase-2 Mu toolchain
that requires a Linux kernel. This phase-2 codebase which used to be at
the top-level is now under the linux/ directory. Finally, the phase-2 toolchain,
while self-hosting, has a way to bootstrap from a C implementation, which
is now stored in linux/bootstrap. The bootstrap C implementation uses some
literate programming tools that are now in linux/bootstrap/tools.

So the whole thing has gotten inverted. Each directory should build one
artifact and include the main sources (along with standard library). Tools
used for building it are relegated to sub-directories, even though those
tools are often useful in their own right, and have had lots of interesting
programs written using them.

A couple of things have gotten dropped in this process:
  - I had old ways to run on just a Linux kernel, or with a Soso kernel.
    No more.
  - I had some old tooling for running a single test at the cursor. I haven't
    used that lately. Maybe I'll bring it back one day.

The reorg isn't done yet. Still to do:
  - redo documentation everywhere. All the README files, all other markdown,
    particularly vocabulary.md.
  - clean up how-to-run comments at the start of programs everywhere
  - rethink what to do with the html/ directory. Do we even want to keep
    supporting it?

In spite of these shortcomings, all the scripts at the top-level, linux/
and linux/bootstrap are working. The names of the scripts also feel reasonable.
This is a good milestone to take stock at.
---
 412render-float-decimal.mu | 597 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 597 insertions(+)
 create mode 100644 412render-float-decimal.mu

(limited to '412render-float-decimal.mu')

diff --git a/412render-float-decimal.mu b/412render-float-decimal.mu
new file mode 100644
index 00000000..7aaf8b3a
--- /dev/null
+++ b/412render-float-decimal.mu
@@ -0,0 +1,597 @@
+# 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
+}
-- 
cgit 1.4.1-2-gfad0