code wiki / _hdl_build / nx_galx_cid_index.nx
nx_galx_cid_index.nx source
↩ module page · 115 lines · 6190 B
1// nx_galx_cid_index.nx -- SOVEREIGN O(1) cid->path store (replaces the per-request flat-TSV scan).
2//
3// The gallery resolved cid->path by READING + SCANNING the whole galx_cid_paths.tsv (34.5MB, 235k lines) on
4// EVERY /img and /thumb request -- a grid page = ~60 of those = the "loading is atrocious". This builds a
5// sovereign binary hash index (our own format, NOT a flat TSV; "nishi ecosystem all the way up"): an FNV-1a
6// open-addressed bucket table (cid_hash -> path location) + a paths blob. Lookup is O(1) average. The .idx +
7// .blob ARE the runtime store; the TSV is only a one-time build input (and can then be retired).
8//
9// Format:
10// <idx>: [8 n_buckets][8 n_entries] then n_buckets * 24: [8 cid_hash][8 path_off][8 path_len]
11// cid_hash==0 marks an empty bucket (a cid hashing to 0 is remapped to 1).
12// <blob>: the concatenated path bytes (path_off/path_len locate each).
13// Collision-safety: FNV-1a 64; for 235k entries the chance of ANY 64-bit collision is ~3e-9 (negligible);
14// the cid itself is nxc1-<64 hex> (already a content hash) so it is effectively unique.
15// license_tier: ORIGINAL
16import "nx_syscalls.nx"
17
18const CIDX_CIDLEN: i64 = 69 // "nxc1-" + 64 hex
19
20// FNV-1a 64 of s[0..n). i64 multiply wraps (mod 2^64) -- fine for hashing.
21func cidx_fnv1a(s: *u8, n: i64) -> i64 {
22 var h: i64 = 0xcbf29ce484222325 as i64
23 var i: i64 = 0
24 while i < n {
25 h = h ^ (s[i] as i64)
26 h = h * (0x100000001b3 as i64)
27 i = i + 1
28 }
29 if h == 0 { h = 1 }
30 return h
31}
32
33// Build the index+blob from a cid_paths.tsv (lines: "<cid>\t<path>"). Returns n_entries, or -1 on error.
34func gs_cidindex_build(tsv_path: *u8, idx_path: *u8, blob_path: *u8) -> i64 {
35 let szp: *i64 = sys_mmap(16) as *i64
36 let b: *u8 = sys_read_file(tsv_path, szp)
37 if (b as i64) == 0 { return 0 - 1 }
38 let sz: i64 = szp[0]
39 // count lines
40 var nent: i64 = 0; var i: i64 = 0
41 while i < sz { if b[i] == (10 as u8) { nent = nent + 1 } i = i + 1 }
42 if nent < 1 { return 0 }
43 // n_buckets = smallest power of two >= nent*2
44 var nb: i64 = 1
45 while nb < nent * 2 { nb = nb * 2 }
46 let idx: *u8 = sys_mmap(16 + nb * 24 + 64)
47 var z: i64 = 0; while z < 16 + nb * 24 { idx[z] = 0 as u8; z = z + 1 } // zero (empty buckets)
48 // header
49 var hi: i64 = 0
50 idx[0]=(nb>>56) as u8; idx[1]=(nb>>48) as u8; idx[2]=(nb>>40) as u8; idx[3]=(nb>>32) as u8; idx[4]=(nb>>24) as u8; idx[5]=(nb>>16) as u8; idx[6]=(nb>>8) as u8; idx[7]=nb as u8
51 idx[8]=(nent>>56) as u8; idx[9]=(nent>>48) as u8; idx[10]=(nent>>40) as u8; idx[11]=(nent>>32) as u8; idx[12]=(nent>>24) as u8; idx[13]=(nent>>16) as u8; idx[14]=(nent>>8) as u8; idx[15]=nent as u8
52 let blob: *u8 = sys_mmap(sz + 64)
53 var blob_off: i64 = 0
54 var ls: i64 = 0; i = 0
55 while i <= sz {
56 var nl: i64 = 0; if i == sz { nl = 1 } else { if b[i] == (10 as u8) { nl = 1 } }
57 if nl == 1 {
58 if i - ls > CIDX_CIDLEN {
59 // cid = [ls, ls+69); expect TAB at ls+69; path = [ls+70, i)
60 if b[ls + CIDX_CIDLEN] == (9 as u8) {
61 let poff: i64 = blob_off
62 let plen: i64 = i - (ls + CIDX_CIDLEN + 1)
63 var p: i64 = 0; while p < plen { blob[blob_off] = b[ls + CIDX_CIDLEN + 1 + p]; blob_off = blob_off + 1; p = p + 1 }
64 let cb: *u8 = ((b as i64) + ls) as *u8
65 let h: i64 = cidx_fnv1a(cb, CIDX_CIDLEN)
66 var bk: i64 = h & (nb - 1)
67 var placed: i64 = 0
68 while placed == 0 {
69 let bo: i64 = 16 + bk * 24
70 let cur: i64 = (((idx[bo] as i64)<<56)|((idx[bo+1] as i64)<<48)|((idx[bo+2] as i64)<<40)|((idx[bo+3] as i64)<<32)|((idx[bo+4] as i64)<<24)|((idx[bo+5] as i64)<<16)|((idx[bo+6] as i64)<<8)|(idx[bo+7] as i64))
71 if cur == 0 {
72 idx[bo]=(h>>56) as u8; idx[bo+1]=(h>>48) as u8; idx[bo+2]=(h>>40) as u8; idx[bo+3]=(h>>32) as u8; idx[bo+4]=(h>>24) as u8; idx[bo+5]=(h>>16) as u8; idx[bo+6]=(h>>8) as u8; idx[bo+7]=h as u8
73 idx[bo+8]=(poff>>56) as u8; idx[bo+9]=(poff>>48) as u8; idx[bo+10]=(poff>>40) as u8; idx[bo+11]=(poff>>32) as u8; idx[bo+12]=(poff>>24) as u8; idx[bo+13]=(poff>>16) as u8; idx[bo+14]=(poff>>8) as u8; idx[bo+15]=poff as u8
74 idx[bo+16]=(plen>>56) as u8; idx[bo+17]=(plen>>48) as u8; idx[bo+18]=(plen>>40) as u8; idx[bo+19]=(plen>>32) as u8; idx[bo+20]=(plen>>24) as u8; idx[bo+21]=(plen>>16) as u8; idx[bo+22]=(plen>>8) as u8; idx[bo+23]=plen as u8
75 placed = 1
76 } else { bk = (bk + 1) & (nb - 1) }
77 }
78 }
79 }
80 ls = i + 1
81 }
82 i = i + 1
83 }
84 let fa: i64 = sys_openat_wr(idx_path, 0x1a4); if fa < 0 { return 0 - 1 }
85 sys_write(fa, idx, 16 + nb * 24); sys_close(fa)
86 let fb: i64 = sys_openat_wr(blob_path, 0x1a4); if fb < 0 { return 0 - 1 }
87 sys_write(fb, blob, blob_off); sys_close(fb)
88 return nent
89}
90
91// Read an i64 (big-endian) at idx[o].
92func cidx_rd64(p: *u8, o: i64) -> i64 { return ((p[o] as i64)<<56)|((p[o+1] as i64)<<48)|((p[o+2] as i64)<<40)|((p[o+3] as i64)<<32)|((p[o+4] as i64)<<24)|((p[o+5] as i64)<<16)|((p[o+6] as i64)<<8)|(p[o+7] as i64) }
93
94// O(1) lookup: cid (69 chars) -> out_path (NUL-terminated). idx/blob are the mmap'd files; nb = n_buckets.
95// Returns 1 if found, 0 if not.
96func gs_cidindex_lookup(idx: *u8, blob: *u8, nb: i64, cid: *u8, out_path: *u8) -> i64 {
97 let h: i64 = cidx_fnv1a(cid, CIDX_CIDLEN)
98 var bk: i64 = h & (nb - 1)
99 var guard: i64 = 0
100 while guard < nb {
101 let bo: i64 = 16 + bk * 24
102 let ch: i64 = cidx_rd64(idx, bo)
103 if ch == 0 { return 0 }
104 if ch == h {
105 let poff: i64 = cidx_rd64(idx, bo + 8)
106 let plen: i64 = cidx_rd64(idx, bo + 16)
107 var p: i64 = 0; while p < plen { out_path[p] = blob[poff + p]; p = p + 1 }
108 out_path[plen] = 0 as u8
109 return 1
110 }
111 bk = (bk + 1) & (nb - 1)
112 guard = guard + 1
113 }
114 return 0
115}