nx_uleb.nx source
↩ module page · 191 lines · 6570 B
1// nx_uleb.nx -- LEB128 (unsigned + signed) encoders + decoders.
2//
3// LEB128 (Little Endian Base 128) is a variable-length integer
4// encoding used by DWARF, WebAssembly, Android dex, the MQTT
5// protocol, and many others. Each byte carries 7 bits of payload
6// plus a continuation bit (high bit) indicating "more bytes follow".
7//
8// Encoding rules:
9// uleb128:
10// - Take the low 7 bits, OR with 0x80 if more bits remain.
11// - Shift right by 7, repeat until value is 0.
12// sleb128:
13// - Same, but stop when the remaining value is 0 AND the sign
14// bit of the last 7-bit chunk is 0 (or value is -1 and the
15// sign bit is 1).
16//
17// Today nx_dwarf_line.nx, nx_dwarf_loc.nx, and nx_dwarf_aranges.nx
18// each have their own copies of these. This module is the single
19// source of truth. As the off-C runtime grows new LEB128 consumers
20// (WebAssembly support, dex parsing, BPF), they import here.
21
22// nx_safety_envelope:
23// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
24// sil_target: SIL1
25// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
26// verdict: NOT_YET_EVALUATED
27
28import "syscalls.nx"
29import "nx_loop.nx"
30
31// Encode `v` as uleb128 into `dst[off..]`. Returns new offset.
32// Caller must ensure `cap - off >= 10` (max uleb128 length for i64).
33func nx_uleb_enc_u(dst: *u8, off: i64, cap: i64, v: i64) -> i64 {
34 var n: i64 = v
35 var k: i64 = off
36 // Bound: ULEB128 i64 ≤ 10 bytes.
37 let lp: *NxLoopFrame = nx_loop_begin(11)
38 while nx_loop_step(lp) == 1 {
39 if k >= cap { return -1 }
40 let lo: i64 = n & 0x7F
41 n = (n >> 7) & 0x01FFFFFFFFFFFFFF // logical shift
42 if n == 0 {
43 dst[k] = lo
44 k = k + 1
45 nx_loop_break(lp)
46 } else {
47 dst[k] = lo | 0x80
48 k = k + 1
49 }
50 }
51 return k
52}
53
54// Encode `v` as sleb128 into `dst[off..]`. Returns new offset.
55func nx_uleb_enc_s(dst: *u8, off: i64, cap: i64, v: i64) -> i64 {
56 var n: i64 = v
57 var k: i64 = off
58 // Bound: SLEB128 i64 ≤ 10 bytes.
59 let lp: *NxLoopFrame = nx_loop_begin(11)
60 while nx_loop_step(lp) == 1 {
61 if k >= cap { return -1 }
62 let lo: i64 = n & 0x7F
63 let sign: i64 = lo & 0x40
64 let n2: i64 = n >> 7
65 var stop: i64 = 0
66 if n2 == 0 {
67 if sign == 0 { stop = 1 }
68 }
69 if n2 == (0 - 1) {
70 if sign != 0 { stop = 1 }
71 }
72 if stop == 1 {
73 dst[k] = lo
74 k = k + 1
75 nx_loop_break(lp)
76 } else {
77 dst[k] = lo | 0x80
78 k = k + 1
79 n = n2
80 }
81 }
82 return k
83}
84
85// Decode a uleb128 from `src[off..]`. Returns the value (caller-
86// readable via *out_val) and the offset of the byte AFTER the last
87// byte consumed. Returns -1 on end-of-stream before terminator.
88func nx_uleb_dec_u(src: *u8, off: i64, cap: i64, out_val: *i64) -> i64 {
89 var k: i64 = off
90 var shift: i64 = 0
91 var v: i64 = 0
92 // Bound: ULEB128 i64 ≤ 10 bytes.
93 let lp: *NxLoopFrame = nx_loop_begin(11)
94 while nx_loop_step(lp) == 1 {
95 if k >= cap { return -1 }
96 let b: i64 = src[k]
97 v = v | ((b & 0x7F) << shift)
98 k = k + 1
99 if (b & 0x80) == 0 {
100 nx_loop_break(lp)
101 } else {
102 shift = shift + 7
103 }
104 }
105 *out_val = v
106 return k
107}
108
109// Decode an sleb128 from `src[off..]`. Same return contract as
110// nx_uleb_dec_u; sign-extends the final value.
111func nx_uleb_dec_s(src: *u8, off: i64, cap: i64, out_val: *i64) -> i64 {
112 var k: i64 = off
113 var shift: i64 = 0
114 var v: i64 = 0
115 var last_byte: i64 = 0
116 // Bound: SLEB128 i64 ≤ 10 bytes.
117 let lp: *NxLoopFrame = nx_loop_begin(11)
118 while nx_loop_step(lp) == 1 {
119 if k >= cap { return -1 }
120 let b: i64 = src[k]
121 last_byte = b
122 v = v | ((b & 0x7F) << shift)
123 k = k + 1
124 shift = shift + 7
125 if (b & 0x80) == 0 { nx_loop_break(lp) }
126 }
127 // Sign-extend: if last byte's bit 6 is set, fill high bits.
128 if (last_byte & 0x40) != 0 {
129 if shift < 64 {
130 let m: i64 = 0 - (1 << shift)
131 v = v | m
132 }
133 }
134 *out_val = v
135 return k
136}
137
138// ---- self-test ---------------------------------------------------
139
140func main() -> i64 {
141 let buf: *u8 = sys_mmap(32)
142 let val_raw: *u8 = sys_mmap(8)
143 let val: *i64 = val_raw as *i64
144
145 // uleb128(0) = [0x00]
146 let n1: i64 = nx_uleb_enc_u(buf, 0, 32, 0)
147 if n1 != 1 { return __syscall(93, 1, 0, 0, 0, 0, 0) }
148 if buf[0] != 0 { return __syscall(93, 2, 0, 0, 0, 0, 0) }
149
150 // uleb128(127) = [0x7F] (no continuation)
151 let n2: i64 = nx_uleb_enc_u(buf, 0, 32, 127)
152 if n2 != 1 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
153 if buf[0] != 0x7F { return __syscall(93, 4, 0, 0, 0, 0, 0) }
154
155 // uleb128(128) = [0x80, 0x01]
156 let n3: i64 = nx_uleb_enc_u(buf, 0, 32, 128)
157 if n3 != 2 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
158 if buf[0] != 0x80 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
159 if buf[1] != 0x01 { return __syscall(93, 7, 0, 0, 0, 0, 0) }
160
161 // uleb128(624485) = [0xE5, 0x8E, 0x26] (Wikipedia canonical example)
162 let n4: i64 = nx_uleb_enc_u(buf, 0, 32, 624485)
163 if n4 != 3 { return __syscall(93, 8, 0, 0, 0, 0, 0) }
164 if buf[0] != 0xE5 { return __syscall(93, 9, 0, 0, 0, 0, 0) }
165 if buf[1] != 0x8E { return __syscall(93, 10, 0, 0, 0, 0, 0) }
166 if buf[2] != 0x26 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
167
168 // Decode it back.
169 let next: i64 = nx_uleb_dec_u(buf, 0, 32, val)
170 if next != 3 { return __syscall(93, 12, 0, 0, 0, 0, 0) }
171 if *val != 624485 { return __syscall(93, 13, 0, 0, 0, 0, 0) }
172
173 // sleb128(-1) = [0x7F] (single byte, sign bit set)
174 let n5: i64 = nx_uleb_enc_s(buf, 0, 32, 0 - 1)
175 if n5 != 1 { return __syscall(93, 14, 0, 0, 0, 0, 0) }
176 if buf[0] != 0x7F { return __syscall(93, 15, 0, 0, 0, 0, 0) }
177
178 // sleb128(-128) = [0x80, 0x7F]
179 let n6: i64 = nx_uleb_enc_s(buf, 0, 32, 0 - 128)
180 if n6 != 2 { return __syscall(93, 16, 0, 0, 0, 0, 0) }
181 if buf[0] != 0x80 { return __syscall(93, 17, 0, 0, 0, 0, 0) }
182 if buf[1] != 0x7F { return __syscall(93, 18, 0, 0, 0, 0, 0) }
183
184 // Round-trip sleb128(-12345)
185 let n7: i64 = nx_uleb_enc_s(buf, 0, 32, 0 - 12345)
186 let next2: i64 = nx_uleb_dec_s(buf, 0, n7, val)
187 if next2 != n7 { return __syscall(93, 19, 0, 0, 0, 0, 0) }
188 if *val != (0 - 12345) { return __syscall(93, 20, 0, 0, 0, 0, 0) }
189
190 return 0
191}