lib/deflate/src/decode.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const bits = @import("bits.zig");
3 const huffman = @import("huffman.zig");
4 const model = @import("model.zig");
5
6 const LiteralDecoder = huffman.Decoder(10, 288);
7 const DistanceDecoder = huffman.Decoder(8, 32);
8 const PrecodeDecoder = huffman.Decoder(7, 19);
9
10 const length_base = [29]u16{
11 3, 4, 5, 6, 7, 8, 9, 10,
12 11, 13, 15, 17, 19, 23, 27, 31,
13 35, 43, 51, 59, 67, 83, 99, 115,
14 131, 163, 195, 227, 258,
15 };
16
17 const length_extra = [29]u4{
18 0, 0, 0, 0, 0, 0, 0, 0,
19 1, 1, 1, 1, 2, 2, 2, 2,
20 3, 3, 3, 3, 4, 4, 4, 4,
21 5, 5, 5, 5, 0,
22 };
23
24 const distance_base = [30]u16{
25 1, 2, 3, 4, 5, 7, 9, 13,
26 17, 25, 33, 49, 65, 97, 129, 193,
27 257, 385, 513, 769, 1025, 1537, 2049, 3073,
28 4097, 6145, 8193, 12289, 16385, 24577,
29 };
30
31 const distance_extra = [30]u4{
32 0, 0, 0, 0, 1, 1, 2, 2,
33 3, 3, 4, 4, 5, 5, 6, 6,
34 7, 7, 8, 8, 9, 9, 10, 10,
35 11, 11, 12, 12, 13, 13,
36 };
37
38 const precode_order = [19]u8{
39 16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
40 11, 4, 12, 3, 13, 2, 14, 1, 15,
41 };
42
43 const Decoder = struct {
44 reader: bits.Reader,
45 output: []u8,
46 written: usize = 0,
47 literals: LiteralDecoder = .{},
48 distances: DistanceDecoder = .{},
49 precode: PrecodeDecoder = .{},
50
51 fn run(self: *Decoder) model.Error!model.Result {
52 var final = false;
53 while (!final) {
54 final = try self.reader.read(1) != 0;
55 const block_type = try self.reader.read(2);
56 switch (block_type) {
57 0 => try self.stored(),
58 1 => try self.fixed(),
59 2 => try self.dynamic(),
60 else => return error.InvalidBlockType,
61 }
62 }
63 return .{
64 .consumed = self.reader.consumed(),
65 .written = self.written,
66 };
67 }
68
69 fn stored(self: *Decoder) model.Error!void {
70 std.debug.assert(self.written <= self.output.len);
71 self.reader.alignForward();
72 const length: u16 = @intCast(try self.reader.read(16));
73 const complement: u16 = @intCast(try self.reader.read(16));
74 if (length != ~complement) return error.WrongStoredLength;
75 if (length > self.output.len - self.written) return error.OutputTooSmall;
76 const end = self.written + length;
77 try self.reader.copyAligned(self.output[self.written..end]);
78 self.written = end;
79 }
80
81 fn fixed(self: *Decoder) model.Error!void {
82 var literal_lengths: [288]u8 = undefined;
83 @memset(literal_lengths[0..144], 8);
84 @memset(literal_lengths[144..256], 9);
85 @memset(literal_lengths[256..280], 7);
86 @memset(literal_lengths[280..288], 8);
87 var distance_lengths: [32]u8 = @splat(5);
88 try self.literals.build(&literal_lengths);
89 try self.distances.build(&distance_lengths);
90 try self.compressed();
91 }
92
93 fn dynamic(self: *Decoder) model.Error!void {
94 const literal_count = @as(usize, try self.reader.read(5)) + 257;
95 const distance_count = @as(usize, try self.reader.read(5)) + 1;
96 const precode_count = @as(usize, try self.reader.read(4)) + 4;
97 if (literal_count > 286 or distance_count > 32) {
98 return error.InvalidDynamicHeader;
99 }
100 std.debug.assert(literal_count + distance_count <= 318);
101
102 var precode_lengths: [19]u8 = @splat(0);
103 for (precode_order[0..precode_count]) |index| {
104 precode_lengths[index] = @intCast(try self.reader.read(3));
105 }
106 self.precode.build(&precode_lengths) catch return error.InvalidDynamicHeader;
107
108 var lengths: [318]u8 = @splat(0);
109 const count = literal_count + distance_count;
110 var index: usize = 0;
111 while (index < count) {
112 const symbol = self.precode.decode(&self.reader) catch {
113 return error.InvalidDynamicHeader;
114 };
115 switch (symbol) {
116 0...15 => {
117 lengths[index] = @intCast(symbol);
118 index += 1;
119 },
120 16 => {
121 if (index == 0) return error.InvalidDynamicHeader;
122 const repeat = @as(usize, try self.reader.read(2)) + 3;
123 if (repeat > count - index) return error.InvalidDynamicHeader;
124 @memset(lengths[index..][0..repeat], lengths[index - 1]);
125 index += repeat;
126 },
127 17 => {
128 const repeat = @as(usize, try self.reader.read(3)) + 3;
129 if (repeat > count - index) return error.InvalidDynamicHeader;
130 index += repeat;
131 },
132 18 => {
133 const repeat = @as(usize, try self.reader.read(7)) + 11;
134 if (repeat > count - index) return error.InvalidDynamicHeader;
135 index += repeat;
136 },
137 else => return error.InvalidDynamicHeader,
138 }
139 }
140 if (lengths[256] == 0) return error.MissingEndOfBlock;
141 self.literals.build(lengths[0..literal_count]) catch {
142 return error.InvalidDynamicHeader;
143 };
144 self.distances.buildAllowEmpty(lengths[literal_count..count]) catch {
145 return error.InvalidDynamicHeader;
146 };
147 try self.compressed();
148 }
149
150 fn compressed(self: *Decoder) model.Error!void {
151 std.debug.assert(self.written <= self.output.len);
152 while (true) {
153 const symbol = try self.literals.decode(&self.reader);
154 if (symbol < 256) {
155 if (self.written == self.output.len) return error.OutputTooSmall;
156 self.output[self.written] = @intCast(symbol);
157 self.written += 1;
158 continue;
159 }
160 if (symbol == 256) return;
161 if (symbol > 285) return error.InvalidCode;
162
163 const length_index = symbol - 257;
164 const length = @as(usize, length_base[length_index]) +
165 try self.reader.read(length_extra[length_index]);
166 const distance_symbol = try self.distances.decode(&self.reader);
167 if (distance_symbol > 29) return error.InvalidCode;
168 const distance = @as(usize, distance_base[distance_symbol]) +
169 try self.reader.read(distance_extra[distance_symbol]);
170 if (distance > self.written) return error.InvalidDistance;
171 if (length > self.output.len - self.written) return error.OutputTooSmall;
172 self.copyMatch(distance, length);
173 }
174 }
175
176 fn copyMatch(self: *Decoder, distance: usize, length: usize) void {
177 std.debug.assert(distance > 0);
178 std.debug.assert(distance <= self.written);
179 std.debug.assert(length <= self.output.len - self.written);
180 const start = self.written;
181 if (distance == 1) {
182 @memset(self.output[start..][0..length], self.output[start - 1]);
183 self.written += length;
184 return;
185 }
186 const initial = @min(distance, length);
187 @memcpy(
188 self.output[start..][0..initial],
189 self.output[start - distance ..][0..initial],
190 );
191 var copied = initial;
192 while (copied < length) {
193 const chunk = @min(copied, length - copied);
194 @memcpy(
195 self.output[start + copied ..][0..chunk],
196 self.output[start..][0..chunk],
197 );
198 copied += chunk;
199 }
200 self.written += length;
201 }
202 };
203
204 pub fn raw(input: []const u8, output: []u8) model.Error!model.Result {
205 var decoder = Decoder{
206 .reader = bits.Reader.init(input),
207 .output = output,
208 };
209 return decoder.run();
210 }
211
212 test "raw decoder handles stored block" {
213 var output: [5]u8 = undefined;
214 const result = try raw(&.{ 0x01, 0x05, 0x00, 0xfa, 0xff, 'h', 'e', 'l', 'l', 'o' }, &output);
215 try std.testing.expectEqualStrings("hello", &output);
216 try std.testing.expectEqual(@as(usize, 10), result.consumed);
217 }