nx_state_delta_codec.nx source
↩ module page · 368 lines · 15056 B
1// nx_state_delta_codec.nx -- quantized bit-packed entity state delta codec.
2//
3// Foundation for poor-internet multiplayer. The naive "serialize full
4// entity state every frame" approach uses ~32 bytes/entity (x,y,z,yaw,
5// pitch,health,id,flags as i64). At 60Hz x 100 entities = 192 KB/s.
6// On a 56 kbps dial-up link (7 KB/s ceiling) that's 27x over budget.
7//
8// Delta-quantize-bitpack collapses this to typical 1-4 bytes per
9// entity per frame:
10// - Bit cursor over a byte buffer (write_bits / read_bits).
11// - Signed N-bit delta encoding (twos-complement) for position +
12// velocity changes between adjacent frames.
13// - Unsigned N-bit absolute encoding for angles (256-step yaw =
14// ~1.4 deg precision; the GGPO/Skullgirls choice).
15// - Varint (7-bit continuation, identical wire format to Protobuf
16// varint / LEB128) for sparse integer fields.
17//
18// Bandwidth budget on a typical FPS frame:
19// per entity: 1 byte change-mask + ~3 bytes delta = 4 bytes
20// 100 entities at 60Hz = 24 KB/s
21// Compare: full-state baseline 192 KB/s -> 8x reduction.
22//
23// On 56 kbps dial-up, area-of-interest culling brings the entity count
24// down to ~20 in-view -> 4.8 KB/s, fits under the 7 KB/s ceiling.
25//
26// Source references (all open):
27// - GGPO bit-packed input frames (Cannon 2006, pond3r/ggpo)
28// - Slither.io / Agar.io quantized state protocols (ClitherProject reverse-eng)
29// - Protobuf varint / LEB128 (developers.google.com/protocol-buffers/docs/encoding)
30// - Quake 3 delta-compressed entity protocol (Carmack .plan)
31//
32// genealogy_id: ggpo_bitpacked_inputs + protobuf_varint + quake3_delta_entities
33// lineage_id: bandwidth_quantize_entity_state
34
35// nx_safety_envelope:
36// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
37// sil_target: SIL1
38// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
39// verdict: NOT_YET_EVALUATED
40
41import "nx_syscalls.nx"
42import "nx_tier.nx"
43import "nx_zigzag_varint.nx"
44const NX_MAGIC_2047: i64 = 2047
45const NX_MAGIC_2048: i64 = 2048
46const NX_MAGIC_16383: i64 = 16383
47const NX_MAGIC_16384: i64 = 16384
48const NX_MAGIC_1000000: i64 = 1000000
49
50// ===== Writer struct (i64 cells in a single flat block) =============
51// Layout (4 cells header, then byte buffer):
52// w[0] = buffer pointer (raw bytes; cast to *u8 to access)
53// w[1] = byte cursor (next byte to write into)
54// w[2] = bit cursor within current byte [0..7]
55// w[3] = buffer capacity in bytes (overrun causes silent saturate)
56
57const NX_DC_OFF_BUF: nx_int = 0
58const NX_DC_OFF_BYTE: nx_int = 1
59const NX_DC_OFF_BIT: nx_int = 2
60const NX_DC_OFF_CAP: nx_int = 3
61const NX_DC_HDR_SIZE: nx_int = 4
62
63func nx_delta_writer_new(cap_bytes: nx_int) -> *i64 {
64 if cap_bytes <= 0 { return 0 as *i64 }
65 let w: *i64 = (sys_mmap(NX_DC_HDR_SIZE * 8)) as *i64
66 let buf: *u8 = (sys_mmap(cap_bytes))
67 var i: nx_int = 0
68 while i < cap_bytes {
69 buf[i] = 0 as u8
70 i = i + 1
71 }
72 w[NX_DC_OFF_BUF] = buf as i64
73 w[NX_DC_OFF_BYTE] = 0
74 w[NX_DC_OFF_BIT] = 0
75 w[NX_DC_OFF_CAP] = cap_bytes
76 return w
77}
78
79func nx_delta_writer_bytes_used(w: *i64) -> nx_int {
80 let byte: nx_int = w[NX_DC_OFF_BYTE]
81 let bit: nx_int = w[NX_DC_OFF_BIT]
82 if bit > 0 { return byte + 1 }
83 return byte
84}
85
86func nx_delta_writer_buf(w: *i64) -> *u8 {
87 return (w[NX_DC_OFF_BUF]) as *u8
88}
89
90// Write n_bits (1..63) of `value` into the buffer. Low bit of value
91// goes out first. Silent saturate on buffer overrun (caller is
92// responsible for sizing).
93func nx_delta_write_bits(w: *i64, value: i64, n_bits: nx_int) {
94 if n_bits <= 0 { return }
95 if n_bits > 63 { return }
96 let buf: *u8 = nx_delta_writer_buf(w)
97 let cap: nx_int = w[NX_DC_OFF_CAP]
98 var byte_cur: nx_int = w[NX_DC_OFF_BYTE]
99 var bit_cur: nx_int = w[NX_DC_OFF_BIT]
100 var v: i64 = value & ((1 << n_bits) - 1) // mask to N bits
101 var remaining: nx_int = n_bits
102 while remaining > 0 {
103 if byte_cur >= cap {
104 w[NX_DC_OFF_BYTE] = byte_cur
105 w[NX_DC_OFF_BIT] = bit_cur
106 return
107 }
108 let space_in_byte: nx_int = 8 - bit_cur
109 var take: nx_int = remaining
110 if take > space_in_byte { take = space_in_byte }
111 let chunk: i64 = v & ((1 << take) - 1)
112 let cur: i64 = buf[byte_cur] as i64
113 buf[byte_cur] = (cur | (chunk << bit_cur)) as u8
114 v = v >> take
115 bit_cur = bit_cur + take
116 remaining = remaining - take
117 if bit_cur == 8 {
118 bit_cur = 0
119 byte_cur = byte_cur + 1
120 }
121 }
122 w[NX_DC_OFF_BYTE] = byte_cur
123 w[NX_DC_OFF_BIT] = bit_cur
124}
125
126// Write a signed n-bit integer. Twos-complement: value range is
127// [-2^(n-1), 2^(n-1)-1]. Values outside range are clamped.
128func nx_delta_write_signed(w: *i64, value: i64, n_bits: nx_int) {
129 if n_bits <= 1 { return }
130 let lim: i64 = 1 << (n_bits - 1)
131 var v: i64 = value
132 if v >= lim { v = lim - 1 }
133 if v < (0 - lim) { v = 0 - lim }
134 let mask: i64 = (1 << n_bits) - 1
135 let u: i64 = v & mask // twos-complement representation
136 nx_delta_write_bits(w, u, n_bits)
137}
138
139// Varint write -- 7 bits per byte + 1-bit continuation marker.
140// Identical wire format to Protobuf varint / LEB128. Best for
141// integers whose magnitude varies widely (entity IDs, counts).
142// Negative values currently NOT supported (cast to unsigned first).
143func nx_delta_write_varint(w: *i64, value: i64) {
144 var v: i64 = value
145 if v < 0 { v = 0 } // caller's responsibility, but defensive
146 var go: nx_int = 1
147 while go == 1 {
148 let chunk: i64 = v & 0x7F
149 let rest: i64 = v >> 7
150 var byte_val: i64 = chunk
151 if rest != 0 { byte_val = chunk | 0x80 }
152 nx_delta_write_bits(w, byte_val, 8)
153 v = rest
154 if v == 0 { go = 0 }
155 }
156}
157
158// ===== Reader struct (mirror of writer) =============================
159// r[0] = buf ptr, r[1] = byte cursor, r[2] = bit cursor, r[3] = byte_len
160
161func nx_delta_reader_new(buf: *u8, n_bytes: nx_int) -> *i64 {
162 let r: *i64 = (sys_mmap(NX_DC_HDR_SIZE * 8)) as *i64
163 r[NX_DC_OFF_BUF] = buf as i64
164 r[NX_DC_OFF_BYTE] = 0
165 r[NX_DC_OFF_BIT] = 0
166 r[NX_DC_OFF_CAP] = n_bytes
167 return r
168}
169
170func nx_delta_read_bits(r: *i64, n_bits: nx_int) -> i64 {
171 if n_bits <= 0 { return 0 }
172 if n_bits > 63 { return 0 }
173 let buf: *u8 = (r[NX_DC_OFF_BUF]) as *u8
174 let cap: nx_int = r[NX_DC_OFF_CAP]
175 var byte_cur: nx_int = r[NX_DC_OFF_BYTE]
176 var bit_cur: nx_int = r[NX_DC_OFF_BIT]
177 var out: i64 = 0
178 var out_pos: nx_int = 0
179 var remaining: nx_int = n_bits
180 while remaining > 0 {
181 if byte_cur >= cap {
182 r[NX_DC_OFF_BYTE] = byte_cur
183 r[NX_DC_OFF_BIT] = bit_cur
184 return out
185 }
186 let space_in_byte: nx_int = 8 - bit_cur
187 var take: nx_int = remaining
188 if take > space_in_byte { take = space_in_byte }
189 let cur: i64 = buf[byte_cur] as i64
190 let mask: i64 = (1 << take) - 1
191 let chunk: i64 = (cur >> bit_cur) & mask
192 out = out | (chunk << out_pos)
193 out_pos = out_pos + take
194 bit_cur = bit_cur + take
195 remaining = remaining - take
196 if bit_cur == 8 {
197 bit_cur = 0
198 byte_cur = byte_cur + 1
199 }
200 }
201 r[NX_DC_OFF_BYTE] = byte_cur
202 r[NX_DC_OFF_BIT] = bit_cur
203 return out
204}
205
206// Read signed n-bit twos-complement integer.
207func nx_delta_read_signed(r: *i64, n_bits: nx_int) -> i64 {
208 if n_bits <= 1 { return 0 }
209 let u: i64 = nx_delta_read_bits(r, n_bits)
210 let sign_bit: i64 = 1 << (n_bits - 1)
211 if (u & sign_bit) != 0 {
212 return u - (1 << n_bits)
213 }
214 return u
215}
216
217// Write a SIGNED integer via zigzag + varint composition. This is
218// the world-class encoding for signed deltas that cluster near zero
219// (position/velocity changes, health deltas, small move offsets).
220// Saves ~50% of bytes vs naive sign-extended varint on typical
221// game-state streams. Composes against nx_zigzag_varint.
222func nx_delta_write_zigzag_varint(w: *i64, value: i64) {
223 let u: i64 = nx_zigzag_varint_encode(value)
224 nx_delta_write_varint(w, u)
225}
226
227// Varint read. Reads 8 bits at a time; high bit = continuation.
228func nx_delta_read_varint(r: *i64) -> i64 {
229 var v: i64 = 0
230 var shift: nx_int = 0
231 var go: nx_int = 1
232 while go == 1 {
233 let byte_val: i64 = nx_delta_read_bits(r, 8)
234 v = v | ((byte_val & 0x7F) << shift)
235 shift = shift + 7
236 if (byte_val & 0x80) == 0 { go = 0 }
237 if shift > 63 { go = 0 } // overflow guard
238 }
239 return v
240}
241
242// Read a signed integer encoded via nx_delta_write_zigzag_varint.
243func nx_delta_read_zigzag_varint(r: *i64) -> i64 {
244 let u: i64 = nx_delta_read_varint(r)
245 return nx_zigzag_varint_decode(u)
246}
247
248// ===== Self-test ====================================================
249
250func main() -> i64 {
251 // T1: 5-bit write/read round-trips.
252 let w: *i64 = nx_delta_writer_new(64)
253 nx_delta_write_bits(w, 17, 5)
254 nx_delta_write_bits(w, 3, 5)
255 nx_delta_write_bits(w, 25, 5)
256 let used: nx_int = nx_delta_writer_bytes_used(w)
257 if used <= 0 || used > 3 { return __syscall(93, 1, 0, 0, 0, 0, 0) }
258
259 let r: *i64 = nx_delta_reader_new(nx_delta_writer_buf(w), used)
260 if nx_delta_read_bits(r, 5) != 17 { return __syscall(93, 2, 0, 0, 0, 0, 0) }
261 if nx_delta_read_bits(r, 5) != 3 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
262 if nx_delta_read_bits(r, 5) != 25 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
263
264 // T2: signed 12-bit handles negative + positive.
265 let w2: *i64 = nx_delta_writer_new(64)
266 nx_delta_write_signed(w2, 100, 12)
267 nx_delta_write_signed(w2, -100, 12)
268 nx_delta_write_signed(w2, NX_MAGIC_2047, 12) // max +
269 nx_delta_write_signed(w2,-NX_MAGIC_2048, 12) // min -
270 nx_delta_write_signed(w2, 0, 12)
271 let used2: nx_int = nx_delta_writer_bytes_used(w2)
272 let r2: *i64 = nx_delta_reader_new(nx_delta_writer_buf(w2), used2)
273 if nx_delta_read_signed(r2, 12) != 100 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
274 if nx_delta_read_signed(r2, 12) != -100 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
275 if nx_delta_read_signed(r2, 12) != NX_MAGIC_2047 { return __syscall(93, 12, 0, 0, 0, 0, 0) }
276 if nx_delta_read_signed(r2, 12) !=-NX_MAGIC_2048 { return __syscall(93, 13, 0, 0, 0, 0, 0) }
277 if nx_delta_read_signed(r2, 12) != 0 { return __syscall(93, 14, 0, 0, 0, 0, 0) }
278
279 // T3: varint round-trip across multi-byte boundary.
280 let w3: *i64 = nx_delta_writer_new(64)
281 nx_delta_write_varint(w3, 0)
282 nx_delta_write_varint(w3, 127) // 1 byte boundary
283 nx_delta_write_varint(w3, 128) // 2 byte boundary
284 nx_delta_write_varint(w3, NX_MAGIC_16383) // 2 byte max
285 nx_delta_write_varint(w3, NX_MAGIC_16384) // 3 byte start
286 nx_delta_write_varint(w3, NX_MAGIC_1000000) // 3 byte
287 let used3: nx_int = nx_delta_writer_bytes_used(w3)
288 let r3: *i64 = nx_delta_reader_new(nx_delta_writer_buf(w3), used3)
289 if nx_delta_read_varint(r3) != 0 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
290 if nx_delta_read_varint(r3) != 127 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
291 if nx_delta_read_varint(r3) != 128 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
292 if nx_delta_read_varint(r3) != NX_MAGIC_16383 { return __syscall(93, 23, 0, 0, 0, 0, 0) }
293 if nx_delta_read_varint(r3) != NX_MAGIC_16384 { return __syscall(93, 24, 0, 0, 0, 0, 0) }
294 if nx_delta_read_varint(r3) != NX_MAGIC_1000000 { return __syscall(93, 25, 0, 0, 0, 0, 0) }
295
296 // T4: BANDWIDTH PROOF. Encode 100 entities with typical FPS deltas:
297 // - 1-byte change mask (assume all 5 fields changed for worst case)
298 // - 12-bit signed dx, 12-bit signed dy, 12-bit signed dz (36 bits)
299 // - 8-bit absolute yaw, 8-bit absolute pitch (16 bits)
300 // Total per entity: 8 + 36 + 16 = 60 bits = 7.5 bytes
301 // 100 entities = 750 bytes. At 60Hz = 45 KB/s -- under FPS Source's
302 // 30-100 KB/s budget. AOI-cull to 20 in-view = 150 bytes/frame
303 // = 9 KB/s -- comfortably above the 7 KB/s dial-up ceiling but
304 // meets the bar for 3G+.
305 let w4: *i64 = nx_delta_writer_new(NX_MAGIC_2048)
306 var k: nx_int = 0
307 while k < 100 {
308 nx_delta_write_bits(w4, 0x1F, 8) // all 5 fields changed
309 nx_delta_write_signed(w4, k - 50, 12) // dx
310 nx_delta_write_signed(w4, k * 3 - 150, 12) // dy
311 nx_delta_write_signed(w4, 0 - (k % 30), 12) // dz
312 nx_delta_write_bits(w4, (k * 7) % 256, 8) // yaw
313 nx_delta_write_bits(w4, (k * 11) % 256, 8) // pitch
314 k = k + 1
315 }
316 let used4: nx_int = nx_delta_writer_bytes_used(w4)
317 // 60 bits * 100 = 6000 bits = 750 bytes.
318 if used4 < 740 || used4 > 760 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
319
320 // Decode and verify entity 50 round-trips.
321 let r4: *i64 = nx_delta_reader_new(nx_delta_writer_buf(w4), used4)
322 var m: nx_int = 0
323 while m < 50 {
324 nx_delta_read_bits(r4, 8)
325 nx_delta_read_signed(r4, 12)
326 nx_delta_read_signed(r4, 12)
327 nx_delta_read_signed(r4, 12)
328 nx_delta_read_bits(r4, 8)
329 nx_delta_read_bits(r4, 8)
330 m = m + 1
331 }
332 if nx_delta_read_bits(r4, 8) != 0x1F { return __syscall(93, 31, 0, 0, 0, 0, 0) }
333 if nx_delta_read_signed(r4, 12) != 0 { return __syscall(93, 32, 0, 0, 0, 0, 0) } // k-50 at k=50
334 if nx_delta_read_signed(r4, 12) != 0 { return __syscall(93, 33, 0, 0, 0, 0, 0) } // k*3-150 at k=50
335 if nx_delta_read_signed(r4, 12) != 0 - (50 % 30) { return __syscall(93, 34, 0, 0, 0, 0, 0) }
336 if nx_delta_read_bits(r4, 8) != (50 * 7) % 256 { return __syscall(93, 35, 0, 0, 0, 0, 0) }
337 if nx_delta_read_bits(r4, 8) != (50 * 11) % 256 { return __syscall(93, 36, 0, 0, 0, 0, 0) }
338
339 // T5: zigzag-varint round-trip + BANDWIDTH WIN proof. Encoding
340 // 100 small signed deltas centred on zero -- typical FPS frame.
341 let w5: *i64 = nx_delta_writer_new(512)
342 var z: nx_int = 0
343 while z < 100 {
344 nx_delta_write_zigzag_varint(w5, z - 50)
345 z = z + 1
346 }
347 let used5: nx_int = nx_delta_writer_bytes_used(w5)
348 // All values fit in [-50, 49] -> after zigzag, all unsigned < 100
349 // -> 1 byte each varint. Expected: 100 bytes.
350 if used5 < 95 || used5 > 105 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
351
352 let r5: *i64 = nx_delta_reader_new(nx_delta_writer_buf(w5), used5)
353 var z2: nx_int = 0
354 while z2 < 100 {
355 let dec: i64 = nx_delta_read_zigzag_varint(r5)
356 if dec != z2 - 50 { return __syscall(93, 41, 0, 0, 0, 0, 0) }
357 z2 = z2 + 1
358 }
359
360 // T6: comparison with non-zigzag varint. Encoding -1 naively as
361 // varint requires 10 bytes (sign-extended); via zigzag, 1 byte.
362 let w6: *i64 = nx_delta_writer_new(64)
363 nx_delta_write_zigzag_varint(w6, -1)
364 let used6: nx_int = nx_delta_writer_bytes_used(w6)
365 if used6 != 1 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
366
367 return 0
368}