adc6f4c7a9ce — Leonard Ritter a month ago
* renamed logregion to logtile
2 files changed, 277 insertions(+), 16 deletions(-)

A => lib/tukan/logtile.sc
M testing/test_node4.sc
A => lib/tukan/logtile.sc +261 -0
@@ 0,0 1,261 @@ 
+
+#   logtile.sc
+    by Leonard Ritter, Duangle GbR <leonard.ritter@duangle.com>
+    first checked in 2021/03/27
+
+    This file is in the public domain.
+
+    An encoding of 2**n sized tiles that allows addressing 2**31/2**63 units
+    with a single 32-bit/64-bit value, provided the address is size-aligned.
+    In this format, we encode size and offset (which must be a multiple of size)
+    as ((offset << 1) | size). Then size(tile) = tile & -tile and offset(tile)
+    = (tile ^ size(tile)) >> 1. Zero can still be used as a null value.
+
+    The final partitioning resembles a binary subdivision; when tiles are
+    ordered by decreasing size, the packing will be gapless.
+
+    Trying to quantize ranges across major block alignments is associated with
+    a strong penalty though; e.g. 2045..2048 is quantized to 2044..2048, but
+    2045..2049 requires the entire 0..4096 tile. In practice this is hardly a
+    problem, because ranges are always subtiles of allocations, and so by
+    definition will never cross block alignments greater than the parent tile.
+
+    logtiles are also valid addresses for a pointerless binary tree, where
+    the ordering matches that of a sorted array:
+
+    --------0-------    [              ]    --------h-------
+    ----1-------1---    [      ][      ]    ----d-------l---
+    --2---2---2---2-    [  ][  ][  ][  ]    --b---f---j---n-
+    -3-3-3-3-3-3-3-3    [][][][][][][][]    -a-c-e-g-i-k-m-o
+    -323132303231323    -323132303231323    -abcdefghijklmno
+
+    increasing the depth of an array addressed by logtiles:
+
+    a.) at bottom
+
+        shift right & space apart by 1 element
+            -323132303231323 -> -4342434143424340434243414342434
+                                  - - - - - - - - - - - - - - -
+
+    b.) at top (e.g. as in a merkle tree expansion)
+
+        append new right hand side
+            -434243414342434 -> -4342434143424340434243414342434
+                                 ---------------
+
+
+""""round x to the next highest power of 2
+inline... alignsizeu (x : u32)
+    x := x - 1
+    x := x | x >> 1
+    x := x | x >> 2
+    x := x | x >> 4
+    x := x | x >> 8
+    x := x | x >> 16
+    x + 1
+case (x : u64)
+    x := x - 1
+    x := x | x >> 1
+    x := x | x >> 2
+    x := x | x >> 4
+    x := x | x >> 8
+    x := x | x >> 16
+    x := x | x >> 32
+    x + 1
+
+""""extract the highest bit from x (round x to the next lowest power of 2)
+inline... alignsized (x : u32)
+    x := x | x >> 1
+    x := x | x >> 2
+    x := x | x >> 4
+    x := x | x >> 8
+    x := x | x >> 16
+    x & ((x >> 1) + 1)
+case (x : u64)
+    x := x | x >> 1
+    x := x | x >> 2
+    x := x | x >> 4
+    x := x | x >> 8
+    x := x | x >> 16
+    x := x | x >> 32
+    x & ((x >> 1) + 1)
+
+inline alignoffsetu (offset align)
+    """"align `offset` up to `align`, which must be a power of 2
+    (offset + align - 1) & -align
+
+inline alignoffsetd (offset align)
+    """"align `offset` down to `align`, which must be a power of 2
+    offset & -align
+
+inline enctile (offset size)
+    """"encode a tile from `offset` and `size`, where `size` is a power
+        of 2, and offset is aligned by size. If the range doesn't fit into
+        the maximum partition, the result is undefined.
+    (offset << 1) | size
+
+fn enctileun (offset size)
+    """"encode a tile from an arbitrary `offset` and `size`, which are
+        aligned and rounded to the next highest partition that fits the
+        requested range.
+        If the resulting range doesn't fit into the maximum partition, the result
+        is undefined.
+    size := (alignsizeu size)
+    enctile (alignoffsetu offset size) size
+
+fn enctilerangeun (lhs rhs)
+    """"encode a tile from an arbitrary range `lhs` (inclusive) and `rhs`
+        (exclusive), which are aligned and rounded to a partition that wraps the
+        requested range.
+        If the resulting range doesn't fit into the maximum partition, the
+        result is undefined.
+    assert (rhs > lhs)
+    # highest changing bit in inclusive range
+    blocksize := (alignsized (1 | (lhs ^ (rhs - 1))))
+    _lhs := (alignoffsetd lhs blocksize)
+    _rhs := (alignoffsetu rhs blocksize)
+    size := (_rhs - _lhs)
+    enctile _lhs size
+
+inline dectile (tile)
+    """"decode offset and size from a provided `tile` that was previously
+        encoded with `enctile`.
+    size := tile & -tile
+    _ ((tile ^ size) >> 1) size
+
+""""compute the upper and lower inclusive bounds of `tile`, which are always
+    of unit size. For the bounds `x0..x1`, for any subtile `s` of `tile`,
+    `x0 <= s <= x1`.
+inline tilebounds (tile)
+    lim := (tile & -tile) - 1
+    _ (tile - lim) (tile + lim)
+
+""""compute the upper and lower exclusive bounds of `tile`. For the bounds
+    `x0..x1`, for any subtile `s` of `tile`, `x0 < s < x1`.
+inline tilexbounds (tile)
+    lim := tile & -tile
+    _ (tile - lim) (tile + lim)
+
+""""returns `true` if tile `tile` is a subtile of `parenttile`
+inline tilein? (tile parenttile)
+    let mn mx = (tilexbounds parenttile)
+    (tile > mn) & (tile < mx)
+
+""""compute the two child tiles of `tile`
+inline childtile (tile)
+    sz := ((tile & -tile) >> 1)
+    _ (tile - sz) (tile + sz)
+
+""""compute the sibling tile sharing the same parent as `tile`
+inline siblingtile (tile)
+    sz := tile & -tile
+    tile ^ (sz << 1)
+
+""""compute the parent tile containing `tile`
+inline parenttile (tile)
+    sz := tile & -tile
+    tile ^ sz | (sz << 1)
+
+""""compute the neighbor at signed `offset` relative to `tile`
+inline neighbortile (tile offset)
+    sz := tile & -tile
+    tile + (sz << 1) * offset
+
+""""compute the largest tile following `tile`
+    if the tile covers the entire range, the result is zero
+inline iternexttile (tile)
+    sz := tile & -tile
+    ofs := ((tile + (sz << 1)) ^ sz)
+    sz2 := ofs & -ofs
+    ofs | (sz2 >> 1)
+
+""""compute the largest tile preceding `tile`
+    if the tile covers the entire range, the result is zero
+inline iterprevtile (tile)
+    ofs := (tile ^ (tile & -tile))
+    sz2 := ofs & -ofs
+    (ofs - sz2) | (sz2 >> 1)
+
+static-if main-module?
+    # 0:u32
+    print
+        dectile 0:u32
+
+    # 113280:u32 128:u32
+    print
+        dectile
+            enctileun 113241:u32 100:u32
+
+    print
+        dectile
+            enctileun 7:u32 1:u32
+
+    for o in (range 12345:u32)
+        for s in (range 1:u32 12345:u32)
+            let lhs rhs = o (o + s)
+            let ro rs =
+                dectile
+                    enctilerangeun lhs rhs
+            let lhs2 rhs2 = ro (ro + rs)
+            assert ((lhs2 <= lhs) & (rhs2 >= rhs))
+
+    # 2044:u32 4:u32
+    print
+        dectile
+            enctilerangeun 2045:u32 2048:u32
+    # 0:u32 4096:u32
+    print
+        dectile
+            enctilerangeun 2045:u32 2049:u32
+
+    # 113152:u32 256:u32
+    print
+        dectile
+            enctilerangeun 113241:u32 (113241:u32 + 100:u32)
+
+    # 8388608:u64 8388608:u64
+    print
+        dectile
+            enctileun 54321:u32 (1920:u32 * 1080 * 4)
+
+    fn tilestr (tile)
+        using import String
+        local s : String
+        let offset size = (dectile tile)
+        'append s "\x1b[30;1m"
+        for i in (range offset)
+            'append s (hex (i % 16))
+        'append s "\x1b[36;1m"
+        for i in (range size)
+            'append s (hex ((offset + i) % 16))
+        'append s "\x1b[0m"
+        s
+    for i in (range 1:u32 17:u32)
+        print " "
+            tilestr i
+        let d u = (tilebounds i)
+        print "<"
+            tilestr (iterprevtile i)
+        print ">"
+            tilestr (iternexttile i)
+        print "d"
+            tilestr d
+        print "u"
+            tilestr u
+        let l r = (childtile i)
+        print "L"
+            tilestr l
+        print "R"
+            tilestr r
+        print "S"
+            tilestr (siblingtile i)
+        print "P"
+            tilestr (parenttile i)
+
+do
+    let enctile enctileun enctilerangeun dectile alignoffsetu alignoffsetd
+        \ alignsizeu alignsized childtile siblingtile parenttile
+        \ neighbortile tilebounds tilexbounds tilein? iternexttile iterprevtile
+    locals;
+
+

          
M testing/test_node4.sc +16 -16
@@ 6,7 6,7 @@ using import Set
 using import property
 
 import ..lib.tukan.use
-using import tukan.logregion
+using import tukan.logtile
 using import tukan.SHA256
 
 # print debug output while deduplicating

          
@@ 75,7 75,7 @@ type Id : u32
         elseif (T == (storageof this-type)) storagecast
         elseif (T == Region)
             inline (self)
-                bitcast (encaddr (storagecast self) 1) Region
+                bitcast (enctile (storagecast self) 1) Region
 
     inline makeop (op)
         @@ memo

          
@@ 105,7 105,7 @@ type+ Region
         elseif (T == (storageof this-type)) storagecast
 
     fn __unpack (self)
-        decaddr (storagecast self)
+        dectile (storagecast self)
 
     fn __hash (self)
         hash (storagecast self)

          
@@ 131,32 131,32 @@ type+ Region
         dupe (deref self)
 
     fn parent (self)
-        bitcast (parentaddr (storagecast self)) this-type
+        bitcast (parenttile (storagecast self)) this-type
 
     fn children (self)
-        let l r = (childaddr (storagecast self))
+        let l r = (childtile (storagecast self))
         _ (bitcast l this-type) (bitcast r this-type)
 
     inline left (self)
-        addr := (storagecast self)
-        bitcast (addr - ((addr & -addr) >> 1)) Region
+        tile := (storagecast self)
+        bitcast (tile - ((tile & -tile) >> 1)) Region
 
     inline right (self)
-        addr := (storagecast self)
-        bitcast (addr + ((addr & -addr) >> 1)) Region
+        tile := (storagecast self)
+        bitcast (tile + ((tile & -tile) >> 1)) Region
 
     fn endpoints (self)
         let offset size = (unpack self)
         _ (bitcast offset Id) (bitcast (offset + size - 1) Id)
 
     fn neighbor (self offset)
-        bitcast (neighboraddr (storagecast self) offset) Region
+        bitcast (neighbortile (storagecast self) offset) Region
 
     fn next (self)
-        bitcast (iternextaddr (storagecast self)) Region
+        bitcast (iternexttile (storagecast self)) Region
 
     fn prev (self)
-        bitcast (iterprevaddr (storagecast self)) Region
+        bitcast (iterprevtile (storagecast self)) Region
 
     @@ memo
     inline __rin (cls T)

          
@@ 181,10 181,10 @@ type+ Region
 
     inline... from-aligned-offset (offset : u32, size : u32 = 1:u32)
         assert ((offset & (size - 1)) == 0)
-        bitcast (encaddr offset size) Region
+        bitcast (enctile offset size) Region
 
     inline... from-range (lhs : u32, rhs : u32)
-        bitcast (encaddrrangeun lhs rhs) Region
+        bitcast (enctilerangeun lhs rhs) Region
 
 ################################################################################
 

          
@@ 227,8 227,8 @@ struct Module
         'resize self.p newcount (nullof WordType)
         bitcount := (newcount + BitWordWidth - 1) // BitWordWidth
         'resize self.ref bitcount (nullof BitWordType)
-        id := (encaddr offset size)
-        let o s = (decaddr id)
+        id := (enctile offset size)
+        let o s = (dectile id)
         assert ((o == offset) & (s == size))
         bitcast id Region