leb128.nx source
↩ module page · 153 lines · 4801 B
1// leb128.nx -- LEB128 (Little-Endian Base 128) integer encoding.
2//
3// Used by WASM (every length, every offset, every section header
4// is LEB128), DWARF debug info, Android dex files.
5//
6// Distinct from varint.nx (protobuf):
7// - Same 7-bit-per-byte continuation pattern
8// - LEB128 has a SIGNED variant (sleb128) that uses 2's complement
9// sign-extension across the final byte's high bit -- different
10// from protobuf's ZigZag mapping
11// - sleb128's 1-byte encoding covers -64..63; ZigZag's covers
12// -1..1. Choose by ecosystem interop need.
13//
14// Invariants:
15// LB1 Encoders write at most 10 bytes (covers full i64 range).
16// LB2 Decoders bound-check; sequences > 10 bytes return overflow.
17// LB3 ULEB128 round-trips any unsigned i64 exactly.
18// LB4 SLEB128 round-trips any signed i64 exactly via sign
19// extension on the final byte.
20
21import "syscalls.nx"
22
23const LEB128_ERR_TRUNCATED: i64 = -1
24const LEB128_ERR_OVERFLOW: i64 = -2
25
26// ---- ULEB128 (unsigned) -------------------------------------------
27
28func uleb128_encode(v: i64, out: *u8, pos: i64) -> i64 {
29 var p: i64 = pos
30 var val: i64 = v
31 while 1 == 1 {
32 let low: i64 = val & 0x7F
33 let remaining: i64 = (val >> 7) & 0x1FFFFFFFFFFFFFFF
34 if remaining == 0 {
35 out[p] = low & 0xFF
36 return p - pos + 1
37 }
38 out[p] = (low | 0x80) & 0xFF
39 p = p + 1
40 val = remaining
41 }
42 return 0
43}
44
45func uleb128_decode(in_bytes: *u8, n: i64, pos: i64,
46 val_out: *i64) -> i64 {
47 var p: i64 = pos
48 var result: i64 = 0
49 var shift: i64 = 0
50 var bytes_read: i64 = 0
51 while p < n {
52 let b: i64 = in_bytes[p]
53 p = p + 1
54 bytes_read = bytes_read + 1
55 if bytes_read > 10 { return LEB128_ERR_OVERFLOW }
56 result = result | ((b & 0x7F) << shift)
57 if (b & 0x80) == 0 {
58 *val_out = result
59 return bytes_read
60 }
61 shift = shift + 7
62 }
63 return LEB128_ERR_TRUNCATED
64}
65
66// ---- SLEB128 (signed) ---------------------------------------------
67
68func sleb128_encode(v: i64, out: *u8, pos: i64) -> i64 {
69 var p: i64 = pos
70 var val: i64 = v
71 while 1 == 1 {
72 let byte_val: i64 = val & 0x7F
73 // Arithmetic shift right by 7 (sign-extends).
74 let next: i64 = val >> 7
75 // Last byte iff next is all-zeros (positive done) OR
76 // all-ones (negative done) AND the byte's sign bit
77 // matches the sign of `val`.
78 let sign_bit: i64 = (byte_val >> 6) & 1
79 var done: i64 = 0
80 if next == 0 {
81 if sign_bit == 0 { done = 1 }
82 }
83 if next == -1 {
84 if sign_bit == 1 { done = 1 }
85 }
86 if done == 1 {
87 out[p] = byte_val & 0xFF
88 return p - pos + 1
89 }
90 out[p] = (byte_val | 0x80) & 0xFF
91 p = p + 1
92 val = next
93 }
94 return 0
95}
96
97func sleb128_decode(in_bytes: *u8, n: i64, pos: i64,
98 val_out: *i64) -> i64 {
99 var p: i64 = pos
100 var result: i64 = 0
101 var shift: i64 = 0
102 var bytes_read: i64 = 0
103 var sign_bit: i64 = 0
104 while p < n {
105 let b: i64 = in_bytes[p]
106 p = p + 1
107 bytes_read = bytes_read + 1
108 if bytes_read > 10 { return LEB128_ERR_OVERFLOW }
109 result = result | ((b & 0x7F) << shift)
110 shift = shift + 7
111 if (b & 0x80) == 0 {
112 // Sign-extend if MSB of last 7-bit group is set AND
113 // we haven't filled the full 64 bits.
114 sign_bit = b & 0x40
115 if sign_bit != 0 {
116 if shift < 64 {
117 let ones: i64 = -1
118 let mask: i64 = ones << shift
119 result = result | mask
120 }
121 }
122 *val_out = result
123 return bytes_read
124 }
125 }
126 return LEB128_ERR_TRUNCATED
127}
128
129// Compile-only smoke.
130func main() -> i64 {
131 let buf: *u8 = sys_mmap(64)
132 let v: *i64 = sys_mmap(16) as *i64
133
134 // ULEB128: 624485 = 0xE5 0x8E 0x26 (3 bytes, WASM-classic).
135 let n1: i64 = uleb128_encode(624485, buf, 0)
136 if n1 != 3 { return 1 }
137 if buf[0] != 0xE5 { return 2 }
138 if buf[1] != 0x8E { return 3 }
139 if buf[2] != 0x26 { return 4 }
140
141 let n2: i64 = uleb128_decode(buf, 3, 0, v)
142 if n2 != 3 { return 5 }
143 if *v != 624485 { return 6 }
144
145 // SLEB128: -123456 = 0xC0 0xBB 0x78 (3 bytes).
146 let n3: i64 = sleb128_encode(0 - 123456, buf, 10)
147 if n3 != 3 { return 7 }
148
149 let n4: i64 = sleb128_decode(buf, 13, 10, v)
150 if n4 != 3 { return 8 }
151 if *v != (0 - 123456) { return 9 }
152 return 0
153}