@@ 240,7 240,7 @@ struct ANode plain
     key : u64
     pnodei : PNodeIndex
 
-inline lowerbound (self value keyf)
+#inline lowerbound (self value keyf)
     """"Return the leftmost occurrence of `value` in sorted array `self`, or the
         number of values smaller than `value`.
     keyf := static-if (none? keyf) defaultkey

          
@@ 256,7 256,7 @@ inline lowerbound (self value keyf)
         else
             repeat L m
 
-inline upperbound (self value keyf)
+#inline upperbound (self value keyf)
     """"Return the index of the first value greater than `value` (or the size
         of the array itself).
     keyf := static-if (none? keyf) defaultkey

          
@@ 303,6 303,44 @@ struct UHeap
     stackaddr : intptr
     globaladdrs : Array (tuple intptr usize)
 
+    fn startoffset (self offset count start)
+        # return offset x0
+        x0 := fold (x0 = 0:usize) for i in (range count)
+            x := self.indices @ (offset + i)
+            n := self.nodes @ x
+            x1 := x0 + n.size
+            #print "x0" x0 "x1" x1 (x1 > start)
+            if (x1 > start)
+                return i x0
+            repeat x1
+        return count x0
+
+    fn startoffset_fast (self offset count start)
+        #slow_offset slow_x0 := startoffset_slow self offset count start
+        L := offset
+        R := offset + count
+        #print L ".." R "|" start
+        x0 := (offset == 0) 0:usize (self.indexsize @ (offset - 1))
+        #for i in (range count)
+            x1 := ((offset + i) == 0) 0:usize (self.indexsize @ (offset + i - 1))
+            print i "->" (x1 - x0)
+        #print "total" ((self.indexsize @ (R - 1)) - x0)
+        loop (L R)
+            if (L >= R)
+                x1 := (L == 0) 0:usize (self.indexsize @ (L - 1))
+                #print "done" (L - offset) (x1 - x0)
+                #print "should be" slow_offset slow_x0
+                #assert ((L - offset) == slow_offset)
+                #assert ((x1 - x0) == slow_x0)
+                break (L - offset) (x1 - x0)
+            m := (L + R) // 2
+            x1 := self.indexsize @ m
+            #print m (x1 - x0)
+            if ((x1 - x0) <= start)
+                repeat (m + 1) R
+            else
+                repeat L m
+
     inline init-hnode (self)
         idx := (countof self.hnodes) as i32
         'append self.hnodes (HNode)

          
@@ 715,7 753,8 @@ inline gen_uheap_data_iterate_slices (te
         case join (offset count)
             if (enterf node start end)
                 db := (uheap_instance)
-                fold (x0 = 0:usize) for i in (range count)
+                starti x0 := 'startoffset db (copy offset) (copy count) start
+                fold (x0) for i in (range starti count)
                     if (x0 >= end)
                         break x0
                     x := db.indices @ (offset + i)

          
@@ 1059,7 1098,8 @@ fn uheap_flatten_prim (dest n start end)
             local last : PNodeDataIndex
             local t0 = 0:usize
             local t1 = 0:usize
-            fold (x0 = 0:usize) for i in (range count)
+            starti x0 := 'startoffset db (copy offset) (copy count) start
+            fold (x0) for i in (range starti count)
                 x := db.indices @ (offset + i)
                 m := db.nodes @ x
                 x1 := x0 + m.size

          

@@ 9999,7 9999,7 @@ inline dot (u v)
 inline length (v)
     sqrt (dot v v)
 
-inline build_matching_real_vector (value c)
+inline build_matching_vector (value c)
     let T = (typeof value)
     let ST = (storageof T)
     static-if (ST < vector)

          
@@ 10013,7 10013,7 @@ inline build_matching_real_vector (value
 
 inline normalize (v)
     fdiv v
-        build_matching_real_vector v (length v)
+        build_matching_vector v (length v)
 
 inline distance (a b)
     length (a - b)

          
@@ 10033,7 10033,7 @@ inline fmix (a b c)
     A B C := typeof a, typeof b, typeof c
     static-assert ((A == B) and (B == C))
     a b c := storagecast a, storagecast b, storagecast c
-    let one = (build_matching_real_vector a 1)
+    let one = (build_matching_vector a 1)
     let invx = (fsub one c)
     bitcast (fadd (fmul a invx) (fmul b c)) A
 

          
@@ 10041,13 10041,18 @@ inline step (a b)
     A B := typeof a, typeof b
     static-assert (A == B)
     a b := storagecast a, storagecast b
-    let one = (build_matching_real_vector a 1)
-    let zero = (build_matching_real_vector b 0)
+    let one = (build_matching_vector a 1)
+    let zero = (build_matching_vector b 0)
     bitcast (? (fcmp>o a b) zero one) A
 
+inline ssign (x)
+    let zero = (build_matching_vector x 0)
+    let T = (typeof x)
+    sub (zext (< zero x) T) (zext (< x zero) T)
+
 inline fsign (x)
     # (0 < x) - (x < 0)
-    let zero = (build_matching_real_vector x 0)
+    let zero = (build_matching_vector x 0)
     let T = (typeof x)
     fsub (uitofp (fcmp<o zero x) T) (uitofp (fcmp<o x zero) T)
 

          
@@ 10059,7 10064,7 @@ inline radians (x)
     let ST = (storageof T)
     static-if (ST < vector)
         fmul x
-            build_matching_real_vector x deg2rad
+            build_matching_vector x deg2rad
     else
         let x = (x as real)
         x * (deg2rad as (typeof x))

          
@@ 10070,7 10075,7 @@ inline degrees (x)
     let ST = (storageof T)
     static-if (ST < vector)
         fmul x
-            build_matching_real_vector x rad2deg
+            build_matching_vector x rad2deg
     else
         let x = (x as real)
         x * (rad2deg as (typeof x))

          
@@ 11120,7 11125,7 @@ spice autocopy (value...)
 unlet _memo dot-char dot-sym ellipsis-symbol _Value constructor destructor
     \ gen-tupleof nested-struct-field-accessor nested-union-field-accessor
     \ tuple-comparison gen-arrayof MethodsAccessor-typeattr floorf modules
-    \ string-array-ref-type? build_matching_real_vector
+    \ string-array-ref-type? build_matching_vector
 
 # about to be removed
 #unlet include sc_import_c

          

@@ 334,6 334,12 @@ fn sc_hash2x64 (a b)
 
 # function to invert large odd number
 inline... mod_inverse_2
+case (a : u32)
+    x := (a * a) + a - 1:u32 # 4
+    x := x * (2:u32 - a * x) # 8
+    x := x * (2:u32 - a * x) # 16
+    x := x * (2:u32 - a * x) # 32
+    x
 case (a : u64)
     x := (a * a) + a - 1:u64 # 4
     x := x * (2:u64 - a * x) # 8

          
@@ 350,6 356,9 @@ case (a : u128)
     x := x * (2:u64 - a * x) # 128
     x
 
+#print
+    mod_inverse_2 2654435789:u32
+
 inline unpack-u128 (x)
     (x >> 64) as u64, x as u64
 inline pack-u128 (h1 h2)

          

@@ 442,6 442,10 @@ do
         t @ i = k
         ;
 
+# mip binary search:
+#while (k <= n)
+    k = 2 * k + (b[k] < x)
+
 fn tree2mipl (x)
     b := x & -x
     level := findlsb b

          
@@ 459,11 463,11 @@ fn mip2tree (x maxlevel)
     q := 1 << (findmsb x)
     ((1 << maxlevel) // q) * ((x - q) * 2 + 1)
 
-MAXLEVEL := 3
-for x in (range 1 16)
-    print x "=>" (mip2tree x MAXLEVEL)
+MAXLEVEL := 6
+for x in (range 100)
+    print x "=>" ((mip2tree x MAXLEVEL) - 1)
 
-for x in (range 1 16)
+#for x in (range 100)
     level offset := tree2mipl x
     x1 := mipl2tree level offset
     x2 := tree2mip x MAXLEVEL