nx_posting_compress.nx source
↩ module page · 91 lines · 4000 B
1// nx_posting_compress.nx -- LIB: posting-list compression (Lucene Frame-of-Reference model) = the biggest perf+size
2// lever for a billion-posting sovereign index. Sorted ascending doc-ids -> per 256-doc BLOCK: store first-id absolute
3// + delta-encode the rest + BIT-PACK the deltas at the block's max bit-width. A dense list (small gaps) collapses to
4// ~2 bits/posting vs 32. Roundtrip-exact (lossless). Built + gated NOW on fixtures; runs at NAS scale over the real
5// index later. SIMD-decode is a later optimization; correctness first. No float. license_tier: ORIGINAL
6import "nx_syscalls.nx"
7
8const PC_BLOCK: i64 = 256
9
10// smallest w with (1<<w) > maxv; >=1.
11func pc_bitwidth(maxv: i64) -> i64 { var w: i64=0; while (1 << w) <= maxv { w = w + 1 } if w==0 { w=1 } return w }
12
13// write w bits of v at bit position bitpos (LSB-first) into buf (buf must be pre-zeroed for the region).
14func pc_putbits(buf: *u8, bitpos: i64, v: i64, w: i64) -> i64 {
15 var i: i64 = 0
16 while i < w {
17 let bit: i64 = (v >> i) & 1
18 if bit == 1 {
19 let byte_i: i64 = (bitpos + i) / 8
20 let bit_i: i64 = (bitpos + i) - (byte_i * 8)
21 buf[byte_i] = ((buf[byte_i] as i64) | (1 << bit_i)) as u8
22 }
23 i = i + 1
24 }
25 return bitpos + w
26}
27// read w bits at bit position bitpos (LSB-first) from buf.
28func pc_getbits(buf: *u8, bitpos: i64, w: i64) -> i64 {
29 var v: i64 = 0; var i: i64 = 0
30 while i < w {
31 let byte_i: i64 = (bitpos + i) / 8
32 let bit_i: i64 = (bitpos + i) - (byte_i * 8)
33 let bit: i64 = ((buf[byte_i] as i64) >> bit_i) & 1
34 v = v | (bit << i)
35 i = i + 1
36 }
37 return v
38}
39
40// compress n ascending doc-ids into out; returns total bytes written.
41// block layout: [count u16][first_id u32][bitwidth u8][packed deltas ceil((count-1)*w/8) bytes]
42func pc_compress(ids: *i64, n: i64, out: *u8) -> i64 {
43 var ob: i64 = 0
44 var base: i64 = 0
45 while base < n {
46 var cnt: i64 = n - base
47 if cnt > PC_BLOCK { cnt = PC_BLOCK }
48 out[ob] = (cnt & 0xff) as u8; out[ob+1] = ((cnt >> 8) & 0xff) as u8; ob = ob + 2
49 let f: i64 = ids[base]
50 out[ob]=(f & 0xff) as u8; out[ob+1]=((f>>8)&0xff) as u8; out[ob+2]=((f>>16)&0xff) as u8; out[ob+3]=((f>>24)&0xff) as u8; ob = ob + 4
51 var maxd: i64 = 0; var i: i64 = 1
52 while i < cnt { let d: i64 = ids[base+i] - ids[base+i-1]; if d > maxd { maxd = d } i = i + 1 }
53 var w: i64 = 0
54 if cnt > 1 { w = pc_bitwidth(maxd) }
55 out[ob] = w as u8; ob = ob + 1
56 if cnt > 1 {
57 let nd: i64 = cnt - 1
58 let bytes: i64 = (nd * w + 7) / 8
59 var z: i64 = 0; while z < bytes { out[ob+z] = 0 as u8; z = z + 1 }
60 let region: *u8 = ((out as i64) + ob) as *u8
61 var bp: i64 = 0
62 i = 1
63 while i < cnt { let d: i64 = ids[base+i] - ids[base+i-1]; pc_putbits(region, bp, d, w); bp = bp + w; i = i + 1 }
64 ob = ob + bytes
65 }
66 base = base + cnt
67 }
68 return ob
69}
70
71// decompress nbytes back into out_ids; returns the count of ids recovered.
72func pc_decompress(inp: *u8, nbytes: i64, out_ids: *i64) -> i64 {
73 var ib: i64 = 0
74 var total: i64 = 0
75 while ib < nbytes {
76 let cnt: i64 = (inp[ib] as i64) | ((inp[ib+1] as i64) << 8); ib = ib + 2
77 let f: i64 = (inp[ib] as i64) | ((inp[ib+1] as i64)<<8) | ((inp[ib+2] as i64)<<16) | ((inp[ib+3] as i64)<<24); ib = ib + 4
78 let w: i64 = inp[ib] as i64; ib = ib + 1
79 out_ids[total] = f; total = total + 1
80 var prev: i64 = f
81 if cnt > 1 {
82 let nd: i64 = cnt - 1
83 let region: *u8 = ((inp as i64) + ib) as *u8
84 var bp: i64 = 0; var i: i64 = 0
85 while i < nd { let d: i64 = pc_getbits(region, bp, w); prev = prev + d; out_ids[total] = prev; total = total + 1; bp = bp + w; i = i + 1 }
86 let bytes: i64 = (nd * w + 7) / 8
87 ib = ib + bytes
88 }
89 }
90 return total
91}