`nx_zstd_huf.nx` source

↩ module page · 161 lines · 5607 B
1// nx_zstd_huf.nx -- Zstandard's Huffman decode table (the X1 flat form).
2//
3// The literals section's engine. zstd does not walk a Huffman tree bit by bit;
4// it builds a FLAT table of 2^tableLog entries where each symbol occupies a
5// contiguous run, peeks tableLog bits to index it in one step, then consumes
6// only the code's true length. That is why the reader needs peek and skip as
7// separate operations.
8//
9// SLOT COUNT IS DRIVEN BY WEIGHT, NOT LENGTH. A symbol of weight w occupies
10// 2^(w-1) slots, which is the same as 2^(tableLog - length) since
11// length = tableLog + 1 - w. Both forms appear in the literature and they are
12// equal only when the table log is right -- so a table built with the wrong
13// log fills a plausible number of slots and still fails to tile the table.
14// The build REFUSES unless the slots sum to exactly 2^tableLog.
15//
16// RANKS ARE LAID OUT BY DESCENDING WEIGHT. Heaviest symbols (shortest codes)
17// take the lowest table indices. Laying them out in symbol order instead
18// produces a table that decodes self-consistently and disagrees with every
19// other zstd implementation -- the failure mode is a file that only this
20// decoder can read.
21//
22// genealogy_id: zstandard_rfc8878_huffman
23// lineage_id:   nx_zstd_huf_v1
24// license_tier: ORIGINAL
25
26import "nx_syscalls.nx"
27import "nx_zstd_bits.nx"
28
29const NX_HUF_MAX_LOG:     i64 = 12
30const NX_HUF_MAX_SYMBOLS: i64 = 256
31const NX_HUF_TBL_BYTES:   i64 = 40
32
33struct NxZstdHuf {
34    table_log:  i64,
35    table_size: i64,
36    symbol:     i64,
37    nbits:      i64,
38}
39
40// ===== build the flat table =======================================
41//
42// weights[0..count-1] are the COMPLETED weight set (including the inferred
43// last one). Returns the table, or 0 if the slots do not tile 2^tableLog
44// exactly -- a partial tile means some peek value indexes an entry that was
45// never written, and that entry would decode as symbol 0 forever.
46
47func nx_zstd_huf_build(weights: *i64, count: i64, table_log: i64) -> *NxZstdHuf {
48    if count <= 0 { return 0 as *NxZstdHuf }
49    if count > NX_HUF_MAX_SYMBOLS { return 0 as *NxZstdHuf }
50    if table_log <= 0 { return 0 as *NxZstdHuf }
51    if table_log > NX_HUF_MAX_LOG { return 0 as *NxZstdHuf }
52
53    let size: i64 = 1 << table_log
54
55    // rank_count[w] = how many symbols carry weight w
56    let rank_count: *i64 = sys_mmap((NX_HUF_MAX_LOG + 4) * 8) as *i64
57    var i: i64 = 0
58    while i <= NX_HUF_MAX_LOG + 1 { rank_count[i] = 0; i = i + 1 }
59
60    var total: i64 = 0
61    i = 0
62    while i < count {
63        let w: i64 = weights[i]
64        if w < 0 { return 0 as *NxZstdHuf }
65        if w > table_log { return 0 as *NxZstdHuf }
66        if w > 0 {
67            rank_count[w] = rank_count[w] + 1
68            total = total + (1 << (w - 1))
69        }
70        i = i + 1
71    }
72    // the slots must tile the table EXACTLY -- no gaps, no overlap
73    if total != size { return 0 as *NxZstdHuf }
74
75    // rank_start[w] = first table index for weight w, laid out heaviest first
76    let rank_start: *i64 = sys_mmap((NX_HUF_MAX_LOG + 4) * 8) as *i64
77    var next: i64 = 0
78    var w2: i64 = table_log
79    while w2 >= 1 {
80        rank_start[w2] = next
81        next = next + (rank_count[w2] << (w2 - 1))
82        w2 = w2 - 1
83    }
84
85    let sym: *i64 = sys_mmap(size * 8 + 64) as *i64
86    let nb: *i64 = sys_mmap(size * 8 + 64) as *i64
87    i = 0
88    while i < size { sym[i] = 0 - 1; nb[i] = 0; i = i + 1 }
89
90    // fill each symbol's contiguous run, heaviest weight first so that the
91    // shortest codes occupy the lowest indices
92    w2 = table_log
93    while w2 >= 1 {
94        var s: i64 = 0
95        while s < count {
96            if weights[s] == w2 {
97                let slots: i64 = 1 << (w2 - 1)
98                let len: i64 = table_log + 1 - w2
99                var k: i64 = 0
100                while k < slots {
101                    let idx: i64 = rank_start[w2] + k
102                    if idx >= size { return 0 as *NxZstdHuf }
103                    sym[idx] = s
104                    nb[idx] = len
105                    k = k + 1
106                }
107                rank_start[w2] = rank_start[w2] + slots
108            }
109            s = s + 1
110        }
111        w2 = w2 - 1
112    }
113
114    // every entry must have been written
115    i = 0
116    while i < size {
117        if sym[i] < 0 { return 0 as *NxZstdHuf }
118        i = i + 1
119    }
120
121    let t: *NxZstdHuf = sys_mmap(NX_HUF_TBL_BYTES) as *NxZstdHuf
122    t.table_log = table_log
123    t.table_size = size
124    t.symbol = sym as i64
125    t.nbits = nb as i64
126    return t
127}
128
129// ===== accessors ==================================================
130
131func nx_zstd_huf_symbol_at(t: *NxZstdHuf, idx: i64) -> i64 {
132    if t == (0 as *NxZstdHuf) { return 0 - 1 }
133    if idx < 0 { return 0 - 1 }
134    if idx >= t.table_size { return 0 - 1 }
135    let a: *i64 = t.symbol as *i64
136    return a[idx]
137}
138
139func nx_zstd_huf_nbits_at(t: *NxZstdHuf, idx: i64) -> i64 {
140    if t == (0 as *NxZstdHuf) { return 0 - 1 }
141    if idx < 0 { return 0 - 1 }
142    if idx >= t.table_size { return 0 - 1 }
143    let a: *i64 = t.nbits as *i64
144    return a[idx]
145}
146
147// ===== decode one symbol ==========================================
148//
149// Peek tableLog bits, index, consume only the code's true length.
150
151func nx_zstd_huf_decode(t: *NxZstdHuf, b: *NxZstdBits) -> i64 {
152    if t == (0 as *NxZstdHuf) { return 0 - 1 }
153    if b == (0 as *NxZstdBits) { return 0 - 1 }
154    let idx: i64 = nx_zstd_bits_peek(b, t.table_log)
155    let s: i64 = nx_zstd_huf_symbol_at(t, idx)
156    if s < 0 { return 0 - 1 }
157    let n: i64 = nx_zstd_huf_nbits_at(t, idx)
158    if n <= 0 { return 0 - 1 }
159    nx_zstd_bits_skip(b, n)
160    return s
161}
nx_zstd_huf.nx source

`nx_zstd_huf.nx` source
