nx_zigzag_varint.nx source
↩ module page · 116 lines · 5345 B
1// nx_zigzag_varint.nx -- Protobuf zigzag encoding for signed integers.
2//
3// Distinct from nx_zigzag.nx (JPEG/MPEG/H.264 8x8 DCT scan-order
4// primitive). Same word, completely different math. This one is the
5// Protobuf signed-integer compression scheme.
6//
7// Problem: a naive varint encoding of a signed i64 wastes bytes on
8// small negative numbers. -1 encoded as two's complement i64 is
9// 0xFFFFFFFFFFFFFFFF, which a 7-bit-continuation varint emits as 10
10// full bytes. Zigzag remaps signed integers so small absolute values
11// (positive OR negative) encode to small unsigned values:
12//
13// 0 -> 0 -1 -> 1 1 -> 2 -2 -> 3 2 -> 4 ...
14//
15// The mapping is bit-twiddled: encode(n) = (n << 1) ^ (n >> 63).
16// (Note: this relies on >> being arithmetic-shift, which is correct
17// behaviour for the encoding step per the cardinal on shift-arith
18// in the parser-quirks meta-class memory.)
19//
20// After zigzag, a varint of (encode(n)) emits 1 byte for |n| < 64,
21// 2 bytes for |n| < 8192, etc. For game deltas that cluster near
22// zero (velocity changes, health deltas, small move offsets) this
23// saves ~50% of bytes on typical streams.
24//
25// Composes with nx_state_delta_codec's varint codec to build a
26// world-class binary protocol for poor-internet multiplayer.
27//
28// Source: developers.google.com/protocol-buffers/docs/encoding#signed-ints
29// Introduced by Google Protocol Buffers (Sanjay Ghemawat + Jeff Dean
30// 2001), now a de-facto standard for binary protocols.
31//
32// genealogy_id: protobuf_2001_zigzag_varint_encoding
33// lineage_id: signed_integer_compact_encoding
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"
43const K_MAGIC_1000000: i64 = 1000000
44const K_MAGIC_2000000: i64 = 2000000
45const K_MAGIC_1999999: i64 = 1999999
46
47// Encode a signed i64 into an unsigned i64 such that small |n| -> small u.
48// Relies on >> being arithmetic-shift so n>>63 is 0 for n>=0 and -1
49// (all-bits-set) for n<0. This is CORRECT use of arithmetic shift;
50// it's how Protobuf's reference implementation works.
51func nx_zigzag_varint_encode(n: i64) -> i64 {
52 return (n << 1) ^ (n >> 63)
53}
54
55// Decode an unsigned zigzag-encoded integer back to signed.
56// Identity: decode(encode(n)) == n for all i64.
57// We mask the low bit and negate via subtraction -- explicit pattern
58// that works regardless of right-shift sign-extension behaviour.
59func nx_zigzag_varint_decode(u: i64) -> i64 {
60 let lsb: i64 = u & 1
61 let half: i64 = (u >> 1) & 0x7FFFFFFFFFFFFFFF // logical-shift workaround
62 if lsb == 1 {
63 return 0 - half - 1
64 }
65 return half
66}
67
68// ===== Self-test ====================================================
69
70func main() -> i64 {
71 // T1: documented small-value mapping from Protobuf spec.
72 if nx_zigzag_varint_encode(0) != 0 { return __syscall(93, 1, 0, 0, 0, 0, 0) }
73 if nx_zigzag_varint_encode(-1) != 1 { return __syscall(93, 2, 0, 0, 0, 0, 0) }
74 if nx_zigzag_varint_encode(1) != 2 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
75 if nx_zigzag_varint_encode(-2) != 3 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
76 if nx_zigzag_varint_encode(2) != 4 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
77
78 // T2: decode inverses encode for small values.
79 if nx_zigzag_varint_decode(0) != 0 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
80 if nx_zigzag_varint_decode(1) != -1 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
81 if nx_zigzag_varint_decode(2) != 1 { return __syscall(93, 12, 0, 0, 0, 0, 0) }
82 if nx_zigzag_varint_decode(3) != -2 { return __syscall(93, 13, 0, 0, 0, 0, 0) }
83 if nx_zigzag_varint_decode(4) != 2 { return __syscall(93, 14, 0, 0, 0, 0, 0) }
84
85 // T3: round-trip for a range of values.
86 var n: i64 = -200
87 while n <= 200 {
88 let enc: i64 = nx_zigzag_varint_encode(n)
89 let dec: i64 = nx_zigzag_varint_decode(enc)
90 if dec != n { return __syscall(93, 20, 0, 0, 0, 0, 0) }
91 n = n + 1
92 }
93
94 // T4: |n| < 64 always encodes to u < 128 (1 varint byte territory).
95 var k: i64 = -63
96 while k <= 63 {
97 let enc: i64 = nx_zigzag_varint_encode(k)
98 if enc < 0 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
99 if enc >= 128 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
100 k = k + 1
101 }
102
103 // T5: boundary cases.
104 if nx_zigzag_varint_encode(63) != 126 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
105 if nx_zigzag_varint_encode(-64) != 127 { return __syscall(93, 41, 0, 0, 0, 0, 0) }
106 if nx_zigzag_varint_encode(64) != 128 { return __syscall(93, 42, 0, 0, 0, 0, 0) }
107 if nx_zigzag_varint_encode(-65) != 129 { return __syscall(93, 43, 0, 0, 0, 0, 0) }
108
109 // T6: large positive + negative.
110 if nx_zigzag_varint_encode(K_MAGIC_1000000) != K_MAGIC_2000000 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
111 if nx_zigzag_varint_encode(-K_MAGIC_1000000) != K_MAGIC_1999999 { return __syscall(93, 51, 0, 0, 0, 0, 0) }
112 if nx_zigzag_varint_decode(K_MAGIC_2000000) != K_MAGIC_1000000 { return __syscall(93, 52, 0, 0, 0, 0, 0) }
113 if nx_zigzag_varint_decode(K_MAGIC_1999999) != -K_MAGIC_1000000 { return __syscall(93, 53, 0, 0, 0, 0, 0) }
114
115 return 0
116}