43b2bda0d00a — Leonard Ritter 18 days ago
* more logregion arithmetic
1 files changed, 76 insertions(+), 32 deletions(-)

M lib/tukan/logregion.sc
M lib/tukan/logregion.sc +76 -32
@@ 16,34 16,8 @@ 
     problem, because ranges are always subregions of allocations, and so by
     definition will never cross block alignments greater than the parent region.
 
-    also good to know:
-
-    fn next (addr)
-        sz := (addr & -addr)
-        addr + (size << 1)
-
-    fn prev (addr)
-        addr - (size << 1)
-
-    fn left (addr)
-        sz := (addr & -addr)
-        (addr ^ sz) | ((sz + 1) >> 1)
-
-    fn right (addr)
-        sz := (addr & -addr)
-        addr | ((sz + 1) >> 1)
-
-    fn sibling (addr)
-        sz := (addr & -addr)
-        addr ^ (sz << 1)
-
-    fn parent (addr)
-        sz := (addr & -addr)
-        (addr + (addr ^ (sz << 1))) >> 1
-
-
 """"round x to the next highest power of 2
-inline... alignsize (x : u32)
+inline... alignsizeu (x : u32)
     x := x - 1
     x := x | x >> 1
     x := x | x >> 2

          
@@ 62,7 36,7 @@ case (x : u64)
     x + 1
 
 """"extract the highest bit from x (round x to the next lowest power of 2)
-inline... msbbit (x : u32)
+inline... alignsized (x : u32)
     x := x | x >> 1
     x := x | x >> 2
     x := x | x >> 4

          
@@ 98,7 72,7 @@ fn encaddrun (offset size)
         requested range.
         If the resulting range doesn't fit into the maximum partition, the result
         is undefined.
-    size := (alignsize size)
+    size := (alignsizeu size)
     encaddr (alignoffsetu offset size) size
 
 fn encaddrrangeun (lhs rhs)

          
@@ 109,7 83,7 @@ fn encaddrrangeun (lhs rhs)
         result is undefined.
     assert (rhs > lhs)
     # highest changing bit in inclusive range
-    blocksize := (msbbit (1 | (lhs ^ (rhs - 1))))
+    blocksize := (alignsized (1 | (lhs ^ (rhs - 1))))
     _lhs := (alignoffsetd lhs blocksize)
     _rhs := (alignoffsetu rhs blocksize)
     size := (_rhs - _lhs)

          
@@ 121,7 95,50 @@ inline decaddr (addr)
     size := addr & -addr
     _ ((addr ^ size) >> 1) size
 
-if main-module?
+""""compute the upper and lower inclusive bounds of `addr`, which are always
+    of unit size. For the bounds `x0..x1`, for any subregion `s` of `addr`,
+    `x0 <= s <= x1`.
+inline addrbounds (addr)
+    lim := (addr & -addr) - 1
+    _ (addr - lim) (addr + lim)
+
+""""compute the upper and lower exclusive bounds of `addr`. For the bounds
+    `x0..x1`, for any subregion `s` of `addr`, `x0 < s < x1`.
+inline addrxbounds (addr)
+    lim := addr & -addr
+    _ (addr - lim) (addr + lim)
+
+""""returns `true` if region `addr` is a subregion of `parentaddr`
+inline addrin? (addr parentaddr)
+    let mn mx = (addrxbounds parentaddr)
+    (addr > mn) & (addr < mx)
+
+""""compute the first child region of `addr`
+inline leftaddr (addr)
+    sz := addr & -addr
+    addr - (sz >> 1)
+
+""""compute the second child region of `addr`
+inline rightaddr (addr)
+    sz := addr & -addr
+    addr + (sz >> 1)
+
+""""compute the sibling region sharing the same parent as `addr`
+inline siblingaddr (addr)
+    sz := addr & -addr
+    addr ^ (sz << 1)
+
+""""compute the parent region containing `addr`
+inline parentaddr (addr)
+    sz := addr & -addr
+    addr ^ sz | (sz << 1)
+
+""""compute the neighbor at signed `offset` relative to `addr`
+inline neighboraddr (addr offset)
+    sz := addr & -addr
+    addr + (sz << 1) * offset
+
+static-if main-module?
     # 0:u32
     print
         decaddr 0:u32

          
@@ 163,9 180,36 @@ if main-module?
         decaddr
             encaddrun 54321:u32 (1920:u32 * 1080 * 4)
 
+    fn regionstr (addr)
+        using import String
+        local s : String
+        let offset size = (decaddr addr)
+        for i in (range offset)
+            'append s "_"
+        for i in (range size)
+            'append s "#"
+        s
+    for i in (range 1:u32 17:u32)
+        print " "
+            regionstr i
+        let d u = (addrbounds i)
+        print "d"
+            regionstr d
+        print "u"
+            regionstr u
+        print "L"
+            regionstr (leftaddr i)
+        print "R"
+            regionstr (rightaddr i)
+        print "S"
+            regionstr (siblingaddr i)
+        print "P"
+            regionstr (parentaddr i)
+
 do
     let encaddr encaddrun encaddrrangeun decaddr alignoffsetu alignoffsetd
-        \ alignsize msbbit
+        \ alignsizeu alignsized leftaddr rightaddr siblingaddr parentaddr
+        \ neighboraddr addrbounds addrxbounds addrin?
     locals;