nx_zstd_seqtab.nx source
↩ module page · 112 lines · 4150 B
1// nx_zstd_seqtab.nx -- Zstandard's three PREDEFINED sequence distributions.
2//
3// These are spec DATA, transcribed from RFC 8878 rather than reconstructed --
4// a distribution that is merely plausible produces a decoder that looks right
5// and disagrees with every other zstd implementation on real files.
6//
7// A NEGATIVE ONE IS A REAL ENTRY, NOT A TERMINATOR. In an FSE normalized
8// count, -1 means "less than one in this table": the symbol is present, it
9// occupies a single low-probability slot, and it counts as ONE toward the
10// total. Dropping the -1 entries -- the obvious reading, since they look like
11// end markers -- leaves the counts short of the table size and the build
12// refuses, which is the good outcome. Treating them as zero is the bad one:
13// the rarest symbols become undecodable and only some files break.
14//
15// THE SUM IS THE TRANSCRIPTION CHECK. Each distribution must total exactly its
16// table size -- 64, 64 and 32 -- and nx_fse_build_dtable enforces that. A
17// single mistyped digit almost always breaks the sum, so a successful build is
18// meaningful evidence the numbers are right, not just that they parse.
19//
20// genealogy_id: rfc8878_default_distributions
21// lineage_id: nx_zstd_seqtab_v1
22// license_tier: ORIGINAL
23
24import "nx_syscalls.nx"
25import "nx_zstd_fse.nx"
26
27const NX_SEQTAB_LL_MAX: i64 = 35
28const NX_SEQTAB_LL_LOG: i64 = 6
29const NX_SEQTAB_ML_MAX: i64 = 52
30const NX_SEQTAB_ML_LOG: i64 = 6
31const NX_SEQTAB_OF_MAX: i64 = 28
32const NX_SEQTAB_OF_LOG: i64 = 5
33
34// ===== literal lengths: 36 entries, total 64 ======================
35
36func nx_zstd_seqtab_ll(o: *i64) -> i64 {
37 o[0]=4; o[1]=3; o[2]=2; o[3]=2; o[4]=2; o[5]=2; o[6]=2; o[7]=2
38 o[8]=2; o[9]=2; o[10]=2; o[11]=2; o[12]=2; o[13]=1; o[14]=1; o[15]=1
39 o[16]=2; o[17]=2; o[18]=2; o[19]=2; o[20]=2; o[21]=2; o[22]=2; o[23]=2
40 o[24]=2; o[25]=3; o[26]=2; o[27]=1; o[28]=1; o[29]=1; o[30]=1; o[31]=1
41 o[32]=0-1; o[33]=0-1; o[34]=0-1; o[35]=0-1
42 return NX_SEQTAB_LL_MAX + 1
43}
44
45// ===== match lengths: 53 entries, total 64 ========================
46
47func nx_zstd_seqtab_ml(o: *i64) -> i64 {
48 o[0]=1; o[1]=4; o[2]=3; o[3]=2; o[4]=2; o[5]=2; o[6]=2; o[7]=2
49 o[8]=2; o[9]=1; o[10]=1; o[11]=1; o[12]=1; o[13]=1; o[14]=1; o[15]=1
50 var i: i64 = 16
51 while i < 46 { o[i] = 1; i = i + 1 }
52 i = 46
53 while i <= NX_SEQTAB_ML_MAX { o[i] = 0 - 1; i = i + 1 }
54 return NX_SEQTAB_ML_MAX + 1
55}
56
57// ===== offsets: 29 entries, total 32 ==============================
58
59func nx_zstd_seqtab_of(o: *i64) -> i64 {
60 var i: i64 = 0
61 while i < 6 { o[i] = 1; i = i + 1 }
62 o[6]=2; o[7]=2; o[8]=2
63 i = 9
64 while i < 24 { o[i] = 1; i = i + 1 }
65 i = 24
66 while i <= NX_SEQTAB_OF_MAX { o[i] = 0 - 1; i = i + 1 }
67 return NX_SEQTAB_OF_MAX + 1
68}
69
70// ===== the total, counting -1 as one ==============================
71//
72// Exposed so a caller can check a transcription without building a table.
73
74func nx_zstd_seqtab_total(o: *i64, count: i64) -> i64 {
75 var t: i64 = 0
76 var i: i64 = 0
77 while i < count {
78 let v: i64 = o[i]
79 if v == (0 - 1) { t = t + 1 } else {
80 if v < 0 { return 0 - 1 }
81 t = t + v
82 }
83 i = i + 1
84 }
85 return t
86}
87
88// ===== the three predefined tables ================================
89
90func nx_zstd_seqtab_ll_table() -> *NxFseTable {
91 let n: *i64 = sys_mmap(NX_FSE_MAX_SYMBOL * 8 + 64) as *i64
92 var i: i64 = 0
93 while i < NX_FSE_MAX_SYMBOL { n[i] = 0; i = i + 1 }
94 nx_zstd_seqtab_ll(n)
95 return nx_fse_build_dtable(n, NX_SEQTAB_LL_MAX, NX_SEQTAB_LL_LOG)
96}
97
98func nx_zstd_seqtab_ml_table() -> *NxFseTable {
99 let n: *i64 = sys_mmap(NX_FSE_MAX_SYMBOL * 8 + 64) as *i64
100 var i: i64 = 0
101 while i < NX_FSE_MAX_SYMBOL { n[i] = 0; i = i + 1 }
102 nx_zstd_seqtab_ml(n)
103 return nx_fse_build_dtable(n, NX_SEQTAB_ML_MAX, NX_SEQTAB_ML_LOG)
104}
105
106func nx_zstd_seqtab_of_table() -> *NxFseTable {
107 let n: *i64 = sys_mmap(NX_FSE_MAX_SYMBOL * 8 + 64) as *i64
108 var i: i64 = 0
109 while i < NX_FSE_MAX_SYMBOL { n[i] = 0; i = i + 1 }
110 nx_zstd_seqtab_of(n)
111 return nx_fse_build_dtable(n, NX_SEQTAB_OF_MAX, NX_SEQTAB_OF_LOG)
112}