1const std = @import("../std.zig");
2const assert = std.debug.assert;
3
4pub const Decompress = @import("zstd/Decompress.zig");
5
6/// Recommended amount by the standard. Lower than this may result in inability
7/// to decompress common streams.
8pub const default_window_len = 8 * 1024 * 1024;
9pub const block_size_max = 1 << 17;
10
11pub const literals_length_default_distribution = [36]i16{
12 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
13 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
14 -1, -1, -1, -1,
15};
16
17pub const match_lengths_default_distribution = [53]i16{
18 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
19 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
20 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1,
21 -1, -1, -1, -1, -1,
22};
23
24pub const offset_codes_default_distribution = [29]i16{
25 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
26 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1,
27};
28
29pub const start_repeated_offset_1 = 1;
30pub const start_repeated_offset_2 = 4;
31pub const start_repeated_offset_3 = 8;
32
33pub const literals_length_code_table = [36]struct { u32, u5 }{
34 .{ 0, 0 }, .{ 1, 0 }, .{ 2, 0 }, .{ 3, 0 },
35 .{ 4, 0 }, .{ 5, 0 }, .{ 6, 0 }, .{ 7, 0 },
36 .{ 8, 0 }, .{ 9, 0 }, .{ 10, 0 }, .{ 11, 0 },
37 .{ 12, 0 }, .{ 13, 0 }, .{ 14, 0 }, .{ 15, 0 },
38 .{ 16, 1 }, .{ 18, 1 }, .{ 20, 1 }, .{ 22, 1 },
39 .{ 24, 2 }, .{ 28, 2 }, .{ 32, 3 }, .{ 40, 3 },
40 .{ 48, 4 }, .{ 64, 6 }, .{ 128, 7 }, .{ 256, 8 },
41 .{ 512, 9 }, .{ 1024, 10 }, .{ 2048, 11 }, .{ 4096, 12 },
42 .{ 8192, 13 }, .{ 16384, 14 }, .{ 32768, 15 }, .{ 65536, 16 },
43};
44
45pub const match_length_code_table = [53]struct { u32, u5 }{
46 .{ 3, 0 }, .{ 4, 0 }, .{ 5, 0 }, .{ 6, 0 }, .{ 7, 0 }, .{ 8, 0 },
47 .{ 9, 0 }, .{ 10, 0 }, .{ 11, 0 }, .{ 12, 0 }, .{ 13, 0 }, .{ 14, 0 },
48 .{ 15, 0 }, .{ 16, 0 }, .{ 17, 0 }, .{ 18, 0 }, .{ 19, 0 }, .{ 20, 0 },
49 .{ 21, 0 }, .{ 22, 0 }, .{ 23, 0 }, .{ 24, 0 }, .{ 25, 0 }, .{ 26, 0 },
50 .{ 27, 0 }, .{ 28, 0 }, .{ 29, 0 }, .{ 30, 0 }, .{ 31, 0 }, .{ 32, 0 },
51 .{ 33, 0 }, .{ 34, 0 }, .{ 35, 1 }, .{ 37, 1 }, .{ 39, 1 }, .{ 41, 1 },
52 .{ 43, 2 }, .{ 47, 2 }, .{ 51, 3 }, .{ 59, 3 }, .{ 67, 4 }, .{ 83, 4 },
53 .{ 99, 5 }, .{ 131, 7 }, .{ 259, 8 }, .{ 515, 9 }, .{ 1027, 10 }, .{ 2051, 11 },
54 .{ 4099, 12 }, .{ 8195, 13 }, .{ 16387, 14 }, .{ 32771, 15 }, .{ 65539, 16 },
55};
56
57pub const table_accuracy_log_max = struct {
58 pub const literal = 9;
59 pub const match = 9;
60 pub const offset = 8;
61};
62
63pub const table_symbol_count_max = struct {
64 pub const literal = 36;
65 pub const match = 53;
66 pub const offset = 32;
67};
68
69pub const default_accuracy_log = struct {
70 pub const literal = 6;
71 pub const match = 6;
72 pub const offset = 5;
73};
74pub const table_size_max = struct {
75 pub const literal = 1 << table_accuracy_log_max.literal;
76 pub const match = 1 << table_accuracy_log_max.match;
77 pub const offset = 1 << table_accuracy_log_max.offset;
78};
79
80fn testDecompress(gpa: std.mem.Allocator, compressed: []const u8) ![]u8 {
81 var out: std.Io.Writer.Allocating = .init(gpa);
82 defer out.deinit();
83
84 var in: std.Io.Reader = .fixed(compressed);
85 var zstd_stream: Decompress = .init(&in, &.{}, .{});
86 _ = try zstd_stream.reader.streamRemaining(&out.writer);
87
88 return out.toOwnedSlice();
89}
90
91/// Create a `Decompress` from `compressed` and immediately discard all output. Returns the number
92/// of discarded bytes.
93fn testDiscard(gpa: std.mem.Allocator, compressed: []const u8) !usize {
94 const buf: []u8 = try gpa.alloc(u8, default_window_len + block_size_max);
95 defer gpa.free(buf);
96
97 var in: std.Io.Reader = .fixed(compressed);
98 var zstd_stream: Decompress = .init(&in, buf, .{});
99 return try zstd_stream.reader.discardRemaining();
100}
101
102fn testExpectDecompress(uncompressed: []const u8, compressed: []const u8) !void {
103 const gpa = std.testing.allocator;
104 const result = try testDecompress(gpa, compressed);
105 defer gpa.free(result);
106 try std.testing.expectEqualSlices(u8, uncompressed, result);
107}
108
109fn testExpectDecompressError(err: anyerror, compressed: []const u8) !void {
110 const gpa = std.testing.allocator;
111
112 var out: std.Io.Writer.Allocating = .init(gpa);
113 defer out.deinit();
114
115 var in: std.Io.Reader = .fixed(compressed);
116 var zstd_stream: Decompress = .init(&in, &.{}, .{});
117 try std.testing.expectError(
118 error.ReadFailed,
119 zstd_stream.reader.streamRemaining(&out.writer),
120 );
121 try std.testing.expectError(err, zstd_stream.err orelse {});
122}
123
124test "partial magic number" {
125 const input_raw =
126 "\x28\xb5\x2f"; // 3 bytes of the 4-byte zstandard frame magic number
127 try testExpectDecompressError(error.BadMagic, input_raw);
128}
129
130test "zero sized raw block" {
131 const input_raw =
132 "\x28\xb5\x2f\xfd" ++ // zstandard frame magic number
133 "\x20\x00" ++ // frame header: only single_segment_flag set, frame_content_size zero
134 "\x01\x00\x00"; // block header with: last_block set, block_type raw, block_size zero
135 try testExpectDecompress("", input_raw);
136}
137
138test "zero sized rle block" {
139 const input_rle =
140 "\x28\xb5\x2f\xfd" ++ // zstandard frame magic number
141 "\x20\x00" ++ // frame header: only single_segment_flag set, frame_content_size zero
142 "\x03\x00\x00" ++ // block header with: last_block set, block_type rle, block_size zero
143 "\xaa"; // block_content
144 try testExpectDecompress("", input_rle);
145}
146
147test "declared raw literals size too large" {
148 const input_raw =
149 "\x28\xb5\x2f\xfd" ++ // zstandard frame magic number
150 "\x00\x00" ++ // frame header: everything unset, window descriptor zero
151 "\x95\x00\x00" ++ // block header with: last_block set, block_type compressed, block_size 18
152 "\xbc\xf3\xae" ++ // literals section header with: type raw, size_format 3, regenerated_size 716603
153 "\xa5\x9f\xe3"; // some bytes of literal content - the content is shorter than regenerated_size
154
155 // Note that the regenerated_size in the above input is larger than block maximum size, so the
156 // block can't be valid as it is a raw literals block.
157 try testExpectDecompressError(error.MalformedLiteralsSection, input_raw);
158}
159
160test "skippable frame" {
161 const input_raw =
162 "\x50\x2a\x4d\x18" ++ // min magic number for a skippable frame
163 "\x02\x00\x00\x00" ++ // number of bytes to skip
164 "\xFF\xFF"; // the bytes that are skipped
165
166 try testExpectDecompress("", input_raw);
167}