1const std = @import("std");
2const builtin = @import("builtin");
3
4pub const min_length = 3;
5pub const max_length = 258;
6
7pub const min_distance = 1;
8pub const max_distance = std.compress.flate.history_len;
9
10pub const codegen_order: [19]u8 = .{
11 16, 17, 18,
12 0, 8, //
13 7, 9,
14 6, 10,
15 5, 11,
16 4, 12,
17 3, 13,
18 2, 14,
19 1, 15,
20};
21
22pub const fixed_lit_codes = fixed_lit[0];
23pub const fixed_lit_bits = fixed_lit[1];
24const fixed_lit = blk: {
25 var codes: [286]u16 = undefined;
26 var bits: [286]u4 = undefined;
27
28 for (0..143 + 1, 0b00110000..0b10111111 + 1) |i, v| {
29 codes[i] = @bitReverse(@as(u8, v));
30 bits[i] = 8;
31 }
32 for (144..255 + 1, 0b110010000..0b111111111 + 1) |i, v| {
33 codes[i] = @bitReverse(@as(u9, v));
34 bits[i] = 9;
35 }
36 for (256..279 + 1, 0b0000000..0b0010111 + 1) |i, v| {
37 codes[i] = @bitReverse(@as(u7, v));
38 bits[i] = 7;
39 }
40 for (280..287 - 2 + 1, 0b11000000..0b11000111 - 2 + 1) |i, v| {
41 codes[i] = @bitReverse(@as(u8, v));
42 bits[i] = 8;
43 }
44 break :blk .{ codes, bits };
45};
46
47pub const fixed_dist_codes = fixed_dist[0];
48pub const fixed_dist_bits = fixed_dist[1];
49const fixed_dist = blk: {
50 var codes: [30]u16 = undefined;
51 const bits: [30]u4 = @splat(5);
52
53 for (0..30) |i| {
54 codes[i] = @bitReverse(@as(u5, i));
55 }
56 break :blk .{ codes, bits };
57};
58
59// All paramters of codes can be derived matchematically, however some are faster to
60// do via lookup table. For -Osmall, we do all mathematically to save space.
61pub const LenCode = if (builtin.mode != .small) LookupLenCode else ShortLenCode;
62pub const DistCode = if (builtin.mode != .small) LookupDistCode else ShortDistCode;
63const ShortLenCode = ShortCode(u8, u2, u3, true);
64const ShortDistCode = ShortCode(u15, u1, u4, false);
65/// For length and distance codes, they having this format.
66///
67/// For example, length code 0b1101 (13 or literal 270) has high_bits=0b01 and high_log2=3
68/// and is 1_01_xx (2 extra bits). It is then offsetted by the min length of 3.
69/// ^ bit 4 = 2 + high_log2 - 1
70///
71/// An exception is Length codes, where value 255 is assigned the special zero-bit code 28 or
72/// literal 285.
73fn ShortCode(Value: type, HighBits: type, HighLog2: type, len_special: bool) type {
74 return packed struct(u5) {
75 /// Bits preceding high bit or start if none
76 high_bits: HighBits,
77 /// High bit, 0 means none, otherwise it is at bit `x + high_log2 - 1`
78 high_log2: HighLog2,
79
80 pub fn fromVal(v: Value) @This() {
81 if (len_special and v == 255) return .fromInt(28);
82 const high_bits = @bitSizeOf(HighBits) + 1;
83 const bits = @bitSizeOf(Value) - @clz(v);
84 if (bits <= high_bits) return @bitCast(@as(u5, @intCast(v)));
85 const high = v >> @intCast(bits - high_bits);
86 return .{ .high_bits = @truncate(high), .high_log2 = @intCast(bits - high_bits + 1) };
87 }
88
89 /// `@ctz(return) >= extraBits()`
90 pub fn base(c: @This()) Value {
91 if (len_special and c.toInt() == 28) return 255;
92 if (c.high_log2 <= 1) return @as(u5, @bitCast(c));
93 const high_value = (@as(Value, @intFromBool(c.high_log2 != 0)) << @bitSizeOf(HighBits)) | c.high_bits;
94 const high_start = @as(std.math.Log2Int(Value), c.high_log2 - 1);
95 return @shlExact(high_value, high_start);
96 }
97
98 const max_extra = @bitSizeOf(Value) - (1 + @bitSizeOf(HighLog2));
99 pub fn extraBits(c: @This()) std.math.IntFittingRange(0, max_extra) {
100 if (len_special and c.toInt() == 28) return 0;
101 return @intCast(c.high_log2 -| 1);
102 }
103
104 pub fn toInt(c: @This()) u5 {
105 return @bitCast(c);
106 }
107
108 pub fn fromInt(x: u5) @This() {
109 return @bitCast(x);
110 }
111 };
112}
113
114const LookupLenCode = packed struct(u5) {
115 code: ShortLenCode,
116
117 const code_table = table: {
118 var codes: [256]ShortLenCode = undefined;
119 for (0.., &codes) |v, *c| {
120 c.* = .fromVal(v);
121 }
122 break :table codes;
123 };
124
125 const base_table = table: {
126 var bases: [29]u8 = undefined;
127 for (0.., &bases) |c, *b| {
128 b.* = ShortLenCode.fromInt(c).base();
129 }
130 break :table bases;
131 };
132
133 pub fn fromVal(v: u8) LookupLenCode {
134 return .{ .code = code_table[v] };
135 }
136
137 /// `@ctz(return) >= extraBits()`
138 pub fn base(c: LookupLenCode) u8 {
139 return base_table[c.toInt()];
140 }
141
142 pub fn extraBits(c: LookupLenCode) u3 {
143 return c.code.extraBits();
144 }
145
146 pub fn toInt(c: LookupLenCode) u5 {
147 return @bitCast(c);
148 }
149
150 pub fn fromInt(x: u5) LookupLenCode {
151 return @bitCast(x);
152 }
153};
154
155const LookupDistCode = packed struct(u5) {
156 code: ShortDistCode,
157
158 const base_table = table: {
159 var bases: [30]u15 = undefined;
160 for (0.., &bases) |c, *b| {
161 b.* = ShortDistCode.fromInt(c).base();
162 }
163 break :table bases;
164 };
165
166 pub fn fromVal(v: u15) LookupDistCode {
167 return .{ .code = .fromVal(v) };
168 }
169
170 /// `@ctz(return) >= extraBits()`
171 pub fn base(c: LookupDistCode) u15 {
172 return base_table[c.toInt()];
173 }
174
175 pub fn extraBits(c: LookupDistCode) u4 {
176 return c.code.extraBits();
177 }
178
179 pub fn toInt(c: LookupDistCode) u5 {
180 return @bitCast(c);
181 }
182
183 pub fn fromInt(x: u5) LookupDistCode {
184 return @bitCast(x);
185 }
186};
187
188test LenCode {
189 inline for ([_]type{ ShortLenCode, LookupLenCode }) |Code| {
190 // Check against the RFC 1951 table
191 for (0.., [_]struct {
192 base: u8,
193 extra_bits: u4,
194 }{
195 // zig fmt: off
196 .{ .base = 3 - min_length, .extra_bits = 0 },
197 .{ .base = 4 - min_length, .extra_bits = 0 },
198 .{ .base = 5 - min_length, .extra_bits = 0 },
199 .{ .base = 6 - min_length, .extra_bits = 0 },
200 .{ .base = 7 - min_length, .extra_bits = 0 },
201 .{ .base = 8 - min_length, .extra_bits = 0 },
202 .{ .base = 9 - min_length, .extra_bits = 0 },
203 .{ .base = 10 - min_length, .extra_bits = 0 },
204 .{ .base = 11 - min_length, .extra_bits = 1 },
205 .{ .base = 13 - min_length, .extra_bits = 1 },
206 .{ .base = 15 - min_length, .extra_bits = 1 },
207 .{ .base = 17 - min_length, .extra_bits = 1 },
208 .{ .base = 19 - min_length, .extra_bits = 2 },
209 .{ .base = 23 - min_length, .extra_bits = 2 },
210 .{ .base = 27 - min_length, .extra_bits = 2 },
211 .{ .base = 31 - min_length, .extra_bits = 2 },
212 .{ .base = 35 - min_length, .extra_bits = 3 },
213 .{ .base = 43 - min_length, .extra_bits = 3 },
214 .{ .base = 51 - min_length, .extra_bits = 3 },
215 .{ .base = 59 - min_length, .extra_bits = 3 },
216 .{ .base = 67 - min_length, .extra_bits = 4 },
217 .{ .base = 83 - min_length, .extra_bits = 4 },
218 .{ .base = 99 - min_length, .extra_bits = 4 },
219 .{ .base = 115 - min_length, .extra_bits = 4 },
220 .{ .base = 131 - min_length, .extra_bits = 5 },
221 .{ .base = 163 - min_length, .extra_bits = 5 },
222 .{ .base = 195 - min_length, .extra_bits = 5 },
223 .{ .base = 227 - min_length, .extra_bits = 5 },
224 .{ .base = 258 - min_length, .extra_bits = 0 },
225 }) |code, params| {
226 // zig fmt: on
227 const c: u5 = @intCast(code);
228 try std.testing.expectEqual(params.extra_bits, Code.extraBits(.fromInt(@intCast(c))));
229 try std.testing.expectEqual(params.base, Code.base(.fromInt(@intCast(c))));
230 for (params.base..params.base + @shlExact(@as(u16, 1), params.extra_bits) -
231 @intFromBool(c == 27)) |v|
232 {
233 try std.testing.expectEqual(c, Code.fromVal(@intCast(v)).toInt());
234 }
235 }
236 }
237}
238
239test DistCode {
240 inline for ([_]type{ ShortDistCode, LookupDistCode }) |Code| {
241 for (0.., [_]struct {
242 base: u15,
243 extra_bits: u4,
244 }{
245 // zig fmt: off
246 .{ .base = 1 - min_distance, .extra_bits = 0 },
247 .{ .base = 2 - min_distance, .extra_bits = 0 },
248 .{ .base = 3 - min_distance, .extra_bits = 0 },
249 .{ .base = 4 - min_distance, .extra_bits = 0 },
250 .{ .base = 5 - min_distance, .extra_bits = 1 },
251 .{ .base = 7 - min_distance, .extra_bits = 1 },
252 .{ .base = 9 - min_distance, .extra_bits = 2 },
253 .{ .base = 13 - min_distance, .extra_bits = 2 },
254 .{ .base = 17 - min_distance, .extra_bits = 3 },
255 .{ .base = 25 - min_distance, .extra_bits = 3 },
256 .{ .base = 33 - min_distance, .extra_bits = 4 },
257 .{ .base = 49 - min_distance, .extra_bits = 4 },
258 .{ .base = 65 - min_distance, .extra_bits = 5 },
259 .{ .base = 97 - min_distance, .extra_bits = 5 },
260 .{ .base = 129 - min_distance, .extra_bits = 6 },
261 .{ .base = 193 - min_distance, .extra_bits = 6 },
262 .{ .base = 257 - min_distance, .extra_bits = 7 },
263 .{ .base = 385 - min_distance, .extra_bits = 7 },
264 .{ .base = 513 - min_distance, .extra_bits = 8 },
265 .{ .base = 769 - min_distance, .extra_bits = 8 },
266 .{ .base = 1025 - min_distance, .extra_bits = 9 },
267 .{ .base = 1537 - min_distance, .extra_bits = 9 },
268 .{ .base = 2049 - min_distance, .extra_bits = 10 },
269 .{ .base = 3073 - min_distance, .extra_bits = 10 },
270 .{ .base = 4097 - min_distance, .extra_bits = 11 },
271 .{ .base = 6145 - min_distance, .extra_bits = 11 },
272 .{ .base = 8193 - min_distance, .extra_bits = 12 },
273 .{ .base = 12289 - min_distance, .extra_bits = 12 },
274 .{ .base = 16385 - min_distance, .extra_bits = 13 },
275 .{ .base = 24577 - min_distance, .extra_bits = 13 },
276 }) |code, params| {
277 // zig fmt: on
278 const c: u5 = @intCast(code);
279 try std.testing.expectEqual(params.extra_bits, Code.extraBits(.fromInt(@intCast(c))));
280 try std.testing.expectEqual(params.base, Code.base(.fromInt(@intCast(c))));
281 for (params.base..params.base + @shlExact(@as(u16, 1), params.extra_bits)) |v| {
282 try std.testing.expectEqual(c, Code.fromVal(@intCast(v)).toInt());
283 }
284 }
285 }
286}