lib/deflate/src/test.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const namespace_owner = @import("root.zig");
3
4 const decompress = namespace_owner.decompress;
5
6 const conformance = struct {
7 const frame = @import("frame.zig");
8
9 const Writer = struct {
10 bytes: [128]u8 = @splat(0),
11 bit_count: usize = 0,
12
13 fn put(self: *Writer, value: u32, count: u6) void {
14 for (0..count) |bit| {
15 const byte_index = self.bit_count / 8;
16 const bit_index: u3 = @intCast(self.bit_count & 7);
17 if (((value >> @intCast(bit)) & 1) != 0) {
18 self.bytes[byte_index] |= @as(u8, 1) << bit_index;
19 }
20 self.bit_count += 1;
21 }
22 }
23
24 fn written(self: *const Writer) []const u8 {
25 return self.bytes[0 .. (self.bit_count + 7) / 8];
26 }
27 };
28
29 fn putMany(writer: *Writer, value: u32, count: u6, repetitions: usize) void {
30 for (0..repetitions) |_| writer.put(value, count);
31 }
32
33 fn expectRaw(writer: *const Writer, expected: []const u8) !void {
34 var output: [128]u8 = undefined;
35 const result = try frame.decompress(
36 writer.written(),
37 &output,
38 .raw,
39 .{ .exact_input = true },
40 );
41 try std.testing.expectEqual(expected.len, result.written);
42 try std.testing.expectEqualSlices(u8, expected, output[0..result.written]);
43 }
44
45 fn emptyOffsetCode() Writer {
46 var writer: Writer = .{};
47 writer.put(1, 1);
48 writer.put(2, 2);
49 writer.put(0, 5);
50 writer.put(0, 5);
51 writer.put(14, 4);
52 putMany(&writer, 0, 3, 2);
53 writer.put(1, 3);
54 writer.put(3, 3);
55 putMany(&writer, 0, 3, 11);
56 writer.put(2, 3);
57 writer.put(0, 3);
58 writer.put(3, 3);
59 writer.put(0, 1);
60 writer.put(54, 7);
61 writer.put(7, 3);
62 writer.put(1, 2);
63 writer.put(0, 1);
64 writer.put(89, 7);
65 writer.put(0, 1);
66 writer.put(78, 7);
67 writer.put(1, 2);
68 writer.put(3, 3);
69 writer.put(0, 1);
70 writer.put(1, 2);
71 writer.put(0, 1);
72 writer.put(0, 1);
73 writer.put(3, 2);
74 return writer;
75 }
76
77 fn singletonLiteralCode() Writer {
78 var writer: Writer = .{};
79 writer.put(1, 1);
80 writer.put(2, 2);
81 writer.put(0, 5);
82 writer.put(0, 5);
83 writer.put(14, 4);
84 putMany(&writer, 0, 3, 2);
85 writer.put(1, 3);
86 writer.put(2, 3);
87 putMany(&writer, 0, 3, 13);
88 writer.put(2, 3);
89 writer.put(0, 1);
90 writer.put(117, 7);
91 writer.put(0, 1);
92 writer.put(117, 7);
93 writer.put(3, 2);
94 writer.put(1, 2);
95 writer.put(0, 1);
96 return writer;
97 }
98
99 fn singletonOffsetCode() Writer {
100 var writer: Writer = .{};
101 writer.put(1, 1);
102 writer.put(2, 2);
103 writer.put(1, 5);
104 writer.put(0, 5);
105 writer.put(14, 4);
106 putMany(&writer, 0, 3, 2);
107 writer.put(1, 3);
108 putMany(&writer, 0, 3, 12);
109 writer.put(2, 3);
110 writer.put(0, 3);
111 writer.put(2, 3);
112 writer.put(0, 1);
113 writer.put(117, 7);
114 writer.put(0, 1);
115 writer.put(116, 7);
116 writer.put(1, 2);
117 writer.put(3, 2);
118 writer.put(3, 2);
119 writer.put(1, 2);
120 writer.put(0, 1);
121 writer.put(3, 2);
122 writer.put(0, 1);
123 writer.put(1, 2);
124 return writer;
125 }
126
127 fn singletonNonzeroOffsetCode() Writer {
128 var writer: Writer = .{};
129 writer.put(1, 1);
130 writer.put(2, 2);
131 writer.put(1, 5);
132 writer.put(1, 5);
133 writer.put(14, 4);
134 putMany(&writer, 0, 3, 2);
135 writer.put(2, 3);
136 writer.put(2, 3);
137 putMany(&writer, 0, 3, 11);
138 writer.put(2, 3);
139 writer.put(0, 3);
140 writer.put(2, 3);
141 writer.put(3, 2);
142 writer.put(117, 7);
143 writer.put(3, 2);
144 writer.put(115, 7);
145 putMany(&writer, 1, 2, 4);
146 writer.put(0, 2);
147 writer.put(2, 2);
148 writer.put(0, 2);
149 writer.put(2, 2);
150 writer.put(3, 2);
151 writer.put(0, 1);
152 writer.put(1, 2);
153 return writer;
154 }
155
156 fn excessiveCodeLengths() Writer {
157 var writer: Writer = .{};
158 writer.put(1, 1);
159 writer.put(2, 2);
160 writer.put(0, 5);
161 writer.put(0, 5);
162 writer.put(14, 4);
163 putMany(&writer, 0, 3, 2);
164 writer.put(1, 3);
165 writer.put(0, 3);
166 putMany(&writer, 0, 3, 13);
167 writer.put(1, 3);
168 writer.put(1, 1);
169 writer.put(117, 7);
170 writer.put(1, 1);
171 writer.put(116, 7);
172 writer.put(0, 1);
173 writer.put(0, 1);
174 writer.put(1, 1);
175 writer.put(117, 7);
176 writer.put(1, 1);
177 return writer;
178 }
179
180 test "libdeflate b122c8b accepts permitted incomplete Huffman codes" {
181 const empty_offset = emptyOffsetCode();
182 try expectRaw(&empty_offset, "ABAA");
183 const singleton_literal = singletonLiteralCode();
184 try expectRaw(&singleton_literal, "");
185 const singleton_offset = singletonOffsetCode();
186 try expectRaw(&singleton_offset, &.{ 255, 255, 255, 255 });
187 const nonzero_offset = singletonNonzeroOffsetCode();
188 try expectRaw(&nonzero_offset, &.{ 254, 255, 254, 255, 254 });
189 }
190
191 test "libdeflate b122c8b rejects excessive code lengths" {
192 const stream = excessiveCodeLengths();
193 var output: [128]u8 = undefined;
194 try std.testing.expectError(
195 error.InvalidDynamicHeader,
196 frame.decompress(stream.written(), &output, .raw, .{}),
197 );
198 }
199 };
200
201 test "zlib and gzip conformance fixtures" {
202 const plain = "hello hello hello\n";
203 const zlib = [_]u8{
204 0x78, 0x9c, 0xcb, 0x48, 0xcd, 0xc9, 0xc9, 0x57,
205 0xc8, 0x40, 0x90, 0x5c, 0x00, 0x40, 0xb5, 0x06,
206 0x87,
207 };
208 const gzip = [_]u8{
209 0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
210 0x02, 0x03, 0xcb, 0x48, 0xcd, 0xc9, 0xc9, 0x57,
211 0xc8, 0x40, 0x90, 0x5c, 0x00, 0x3b, 0x7c, 0x8a,
212 0xdf, 0x12, 0x00, 0x00, 0x00,
213 };
214 var output: [plain.len]u8 = undefined;
215 _ = try decompress(&zlib, &output, .zlib, .{ .exact_output = true });
216 try std.testing.expectEqualStrings(plain, &output);
217 _ = try decompress(&gzip, &output, .gzip, .{ .exact_output = true });
218 try std.testing.expectEqualStrings(plain, &output);
219 }
220
221 test "framing rejects checksum mismatch, trailing input, and short output" {
222 var output: [5]u8 = undefined;
223 const valid = [_]u8{
224 0x78, 0x01, 0x01, 0x05, 0x00, 0xfa, 0xff, 'h',
225 'e', 'l', 'l', 'o', 0x06, 0x2c, 0x02, 0x15,
226 };
227 var bad_checksum = valid;
228 bad_checksum[bad_checksum.len - 1] ^= 1;
229 try std.testing.expectError(
230 error.BadChecksum,
231 decompress(&bad_checksum, &output, .zlib, .{}),
232 );
233 const trailing = valid ++ [_]u8{0};
234 try std.testing.expectError(
235 error.TrailingInput,
236 decompress(&trailing, &output, .zlib, .{}),
237 );
238 var short: [4]u8 = undefined;
239 try std.testing.expectError(
240 error.OutputTooSmall,
241 decompress(&valid, &short, .zlib, .{}),
242 );
243 }
244
245 test "decoder rejects malformed headers and blocks" {
246 const bad_gzip = [_]u8{ 0x1f, 0x8b, 0x08, 0xe0 } ++ @as([14]u8, @splat(0));
247 var output: [16]u8 = undefined;
248 try std.testing.expectError(
249 error.InvalidBlockType,
250 decompress(&.{0x07}, &output, .raw, .{}),
251 );
252 try std.testing.expectError(
253 error.WrongStoredLength,
254 decompress(&.{ 0x01, 0x01, 0x00, 0x01, 0x00, 0x00 }, &output, .raw, .{}),
255 );
256 try std.testing.expectError(
257 error.PresetDictionaryUnsupported,
258 decompress(&.{ 0x78, 0x20, 0, 0, 0, 0 }, &output, .zlib, .{}),
259 );
260 try std.testing.expectError(
261 error.BadHeader,
262 decompress(&bad_gzip, &output, .gzip, .{}),
263 );
264 }
265
266 test "decoder rejects every truncation of a framed stream" {
267 const valid = [_]u8{
268 0x78, 0x01, 0x01, 0x05, 0x00, 0xfa, 0xff, 'h',
269 'e', 'l', 'l', 'o', 0x06, 0x2c, 0x02, 0x15,
270 };
271 var output: [5]u8 = undefined;
272 for (0..valid.len) |length| {
273 if (decompress(valid[0..length], &output, .zlib, .{})) |_| {
274 return error.TestUnexpectedResult;
275 } else |_| {}
276 }
277 }
278
279 test "gzip optional fields and header checksum are bounded" {
280 const compressed = [_]u8{
281 0xcb, 0x48, 0xcd, 0xc9, 0xc9, 0x57,
282 0xc8, 0x40, 0x90, 0x5c, 0x00,
283 };
284 const footer = [_]u8{ 0x3b, 0x7c, 0x8a, 0xdf, 0x12, 0x00, 0x00, 0x00 };
285 var stream: [39]u8 = @splat(0);
286 stream[0..18].* = .{
287 0x1f, 0x8b, 0x08, 0x1e, 0, 0, 0, 0, 0, 0xff,
288 2, 0, 0xaa, 0xbb, 'n', 0, 'c', 0,
289 };
290 const header_crc: u16 = @truncate(std.hash.Crc32.hash(stream[0..18]));
291 stream[18] = @truncate(header_crc);
292 stream[19] = @truncate(header_crc >> 8);
293 @memcpy(stream[20..31], &compressed);
294 @memcpy(stream[31..], &footer);
295 var output: ["hello hello hello\n".len]u8 = undefined;
296 _ = try decompress(&stream, &output, .gzip, .{ .exact_output = true });
297 try std.testing.expectEqualStrings("hello hello hello\n", &output);
298 stream[18] ^= 1;
299 try std.testing.expectError(
300 error.BadChecksum,
301 decompress(&stream, &output, .gzip, .{}),
302 );
303 }
304
305 test {
306 _ = @import("bits.zig");
307 _ = conformance;
308 _ = @import("decode.zig");
309 _ = @import("huffman.zig");
310 }