1 // Copyright 2017 The Chromium OS Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <algorithm>
6 #include <string>
7 #include <vector>
8
9 #include "gtest/gtest.h"
10
11 #include "puffin/src/bit_reader.h"
12 #include "puffin/src/bit_writer.h"
13 #include "puffin/src/include/puffin/common.h"
14 #include "puffin/src/include/puffin/huffer.h"
15 #include "puffin/src/include/puffin/puffer.h"
16 #include "puffin/src/include/puffin/utils.h"
17 #include "puffin/src/logging.h"
18 #include "puffin/src/memory_stream.h"
19 #include "puffin/src/puff_reader.h"
20 #include "puffin/src/puff_writer.h"
21 #include "puffin/src/puffin_stream.h"
22 #include "puffin/src/unittest_common.h"
23
24 using std::string;
25 using std::vector;
26
27 namespace puffin {
28
29 namespace {
30
31 // Uncompressed deflate block.
32 const Buffer kRawEmpty = {};
33 const Buffer kRaw1 = {0x01};
34 const Buffer kRaw2 = {0x01, 0x01};
35 const Buffer kRaw5 = {0x01, 0x02, 0x03, 0x04, 0x05};
36
37 } // namespace
38
39 class PuffinTest : public ::testing::Test {
40 public:
41 // Utility for decompressing a puff stream.
DecompressPuff(const uint8_t * puff_buf,size_t * puff_size,uint8_t * out_buf,size_t * out_size)42 bool DecompressPuff(const uint8_t* puff_buf,
43 size_t* puff_size,
44 uint8_t* out_buf,
45 size_t* out_size) {
46 BufferPuffReader puff_reader(static_cast<const uint8_t*>(puff_buf),
47 *puff_size);
48 auto start = static_cast<uint8_t*>(out_buf);
49
50 PuffData pd;
51 while (puff_reader.BytesLeft() != 0) {
52 TEST_AND_RETURN_FALSE(puff_reader.GetNext(&pd));
53 switch (pd.type) {
54 case PuffData::Type::kLiteral:
55 *start = pd.byte;
56 start++;
57 FALLTHROUGH_INTENDED;
58
59 case PuffData::Type::kLiterals:
60 pd.read_fn(start, pd.length);
61 start += pd.length;
62 break;
63
64 case PuffData::Type::kLenDist: {
65 while (pd.length-- > 0) {
66 *start = *(start - pd.distance);
67 start++;
68 }
69 break;
70 }
71
72 case PuffData::Type::kBlockMetadata:
73 break;
74
75 case PuffData::Type::kEndOfBlock:
76 break;
77
78 default:
79 LOG(ERROR) << "Invalid block data type";
80 break;
81 }
82 }
83 *out_size = start - static_cast<uint8_t*>(out_buf);
84 *puff_size = *puff_size - puff_reader.BytesLeft();
85 return true;
86 }
87
PuffDeflate(const uint8_t * comp_buf,size_t comp_size,uint8_t * puff_buf,size_t puff_size) const88 bool PuffDeflate(const uint8_t* comp_buf,
89 size_t comp_size,
90 uint8_t* puff_buf,
91 size_t puff_size) const {
92 BufferBitReader bit_reader(comp_buf, comp_size);
93 BufferPuffWriter puff_writer(puff_buf, puff_size);
94
95 TEST_AND_RETURN_FALSE(
96 puffer_.PuffDeflate(&bit_reader, &puff_writer, nullptr));
97 TEST_AND_RETURN_FALSE(comp_size == bit_reader.Offset());
98 TEST_AND_RETURN_FALSE(puff_size == puff_writer.Size());
99 return true;
100 }
101
HuffDeflate(const uint8_t * puff_buf,size_t puff_size,uint8_t * comp_buf,size_t comp_size) const102 bool HuffDeflate(const uint8_t* puff_buf,
103 size_t puff_size,
104 uint8_t* comp_buf,
105 size_t comp_size) const {
106 BufferPuffReader puff_reader(puff_buf, puff_size);
107 BufferBitWriter bit_writer(comp_buf, comp_size);
108
109 TEST_AND_RETURN_FALSE(huffer_.HuffDeflate(&puff_reader, &bit_writer));
110 TEST_AND_RETURN_FALSE(comp_size == bit_writer.Size());
111 TEST_AND_RETURN_FALSE(puff_reader.BytesLeft() == 0);
112 return true;
113 }
114
115 // Puffs |compressed| into |out_puff| and checks its equality with
116 // |expected_puff|.
TestPuffDeflate(const Buffer & compressed,const Buffer & expected_puff,Buffer * out_puff)117 void TestPuffDeflate(const Buffer& compressed,
118 const Buffer& expected_puff,
119 Buffer* out_puff) {
120 out_puff->resize(expected_puff.size());
121 auto comp_size = compressed.size();
122 auto puff_size = out_puff->size();
123 ASSERT_TRUE(
124 PuffDeflate(compressed.data(), comp_size, out_puff->data(), puff_size));
125 ASSERT_EQ(puff_size, expected_puff.size());
126 out_puff->resize(puff_size);
127 ASSERT_EQ(expected_puff, *out_puff);
128 }
129
130 // Should fail when trying to puff |compressed|.
FailPuffDeflate(const Buffer & compressed,Buffer * out_puff)131 void FailPuffDeflate(const Buffer& compressed, Buffer* out_puff) {
132 out_puff->resize(compressed.size() * 2 + 10);
133 auto comp_size = compressed.size();
134 auto puff_size = out_puff->size();
135 ASSERT_FALSE(
136 PuffDeflate(compressed.data(), comp_size, out_puff->data(), puff_size));
137 }
138
139 // Huffs |puffed| into |out_huff| and checks its equality with
140 // |expected_huff|.|
TestHuffDeflate(const Buffer & puffed,const Buffer & expected_huff,Buffer * out_huff)141 void TestHuffDeflate(const Buffer& puffed,
142 const Buffer& expected_huff,
143 Buffer* out_huff) {
144 out_huff->resize(expected_huff.size());
145 auto huff_size = out_huff->size();
146 auto puffed_size = puffed.size();
147 ASSERT_TRUE(
148 HuffDeflate(puffed.data(), puffed_size, out_huff->data(), huff_size));
149 ASSERT_EQ(expected_huff, *out_huff);
150 }
151
152 // Should fail while huffing |puffed|
FailHuffDeflate(const Buffer & puffed,Buffer * out_compress)153 void FailHuffDeflate(const Buffer& puffed, Buffer* out_compress) {
154 out_compress->resize(puffed.size());
155 auto comp_size = out_compress->size();
156 auto puff_size = puffed.size();
157 ASSERT_TRUE(
158 HuffDeflate(puffed.data(), puff_size, out_compress->data(), comp_size));
159 }
160
161 // Decompresses from |puffed| into |uncompress| and checks its equality with
162 // |original|.
Decompress(const Buffer & puffed,const Buffer & original,Buffer * uncompress)163 void Decompress(const Buffer& puffed,
164 const Buffer& original,
165 Buffer* uncompress) {
166 uncompress->resize(original.size());
167 auto uncomp_size = uncompress->size();
168 auto puffed_size = puffed.size();
169 ASSERT_TRUE(DecompressPuff(puffed.data(), &puffed_size, uncompress->data(),
170 &uncomp_size));
171 ASSERT_EQ(puffed_size, puffed.size());
172 ASSERT_EQ(uncomp_size, original.size());
173 uncompress->resize(uncomp_size);
174 ASSERT_EQ(original, *uncompress);
175 }
176
CheckSample(const Buffer original,const Buffer compressed,const Buffer puffed)177 void CheckSample(const Buffer original,
178 const Buffer compressed,
179 const Buffer puffed) {
180 Buffer puff, uncompress, huff;
181 TestPuffDeflate(compressed, puffed, &puff);
182 TestHuffDeflate(puffed, compressed, &huff);
183 Decompress(puffed, original, &uncompress);
184 }
185
CheckBitExtentsPuffAndHuff(const Buffer & deflate_buffer,const vector<BitExtent> & deflate_extents,const Buffer & puff_buffer,const vector<ByteExtent> & puff_extents)186 void CheckBitExtentsPuffAndHuff(const Buffer& deflate_buffer,
187 const vector<BitExtent>& deflate_extents,
188 const Buffer& puff_buffer,
189 const vector<ByteExtent>& puff_extents) {
190 auto puffer = std::make_shared<Puffer>();
191 auto deflate_stream = MemoryStream::CreateForRead(deflate_buffer);
192 ASSERT_TRUE(deflate_stream->Seek(0));
193 vector<ByteExtent> out_puff_extents;
194 uint64_t puff_size;
195 ASSERT_TRUE(FindPuffLocations(deflate_stream, deflate_extents,
196 &out_puff_extents, &puff_size));
197 EXPECT_EQ(puff_size, puff_buffer.size());
198 EXPECT_EQ(out_puff_extents, puff_extents);
199
200 auto src_puffin_stream =
201 PuffinStream::CreateForPuff(std::move(deflate_stream), puffer,
202 puff_size, deflate_extents, puff_extents);
203
204 Buffer out_puff_buffer(puff_buffer.size());
205 ASSERT_TRUE(src_puffin_stream->Read(out_puff_buffer.data(),
206 out_puff_buffer.size()));
207 EXPECT_EQ(out_puff_buffer, puff_buffer);
208
209 auto huffer = std::make_shared<Huffer>();
210 Buffer out_deflate_buffer;
211 deflate_stream = MemoryStream::CreateForWrite(&out_deflate_buffer);
212
213 src_puffin_stream =
214 PuffinStream::CreateForHuff(std::move(deflate_stream), huffer,
215 puff_size, deflate_extents, puff_extents);
216
217 ASSERT_TRUE(
218 src_puffin_stream->Write(puff_buffer.data(), puff_buffer.size()));
219 EXPECT_EQ(out_deflate_buffer, deflate_buffer);
220 }
221
222 protected:
223 Puffer puffer_;
224 Huffer huffer_;
225 };
226
227 // Tests a simple buffer with uncompressed deflate block.
TEST_F(PuffinTest,UncompressedTest)228 TEST_F(PuffinTest, UncompressedTest) {
229 const Buffer kDeflate = {0x01, 0x05, 0x00, 0xFA, 0xFF,
230 0x01, 0x02, 0x03, 0x04, 0x05};
231 const Buffer kPuff = {0x00, 0x00, 0x80, 0x04, 0x01, 0x02,
232 0x03, 0x04, 0x05, 0xFF, 0x81};
233 CheckSample(kRaw5, kDeflate, kPuff);
234 }
235
236 // Tests a simple buffer with uncompressed deflate block with length zero.
TEST_F(PuffinTest,ZeroLengthUncompressedTest)237 TEST_F(PuffinTest, ZeroLengthUncompressedTest) {
238 const Buffer kDeflate = {0x01, 0x00, 0x00, 0xFF, 0xFF};
239 const Buffer kPuff = {0x00, 0x00, 0x80, 0xFF, 0x81};
240 CheckSample(kRawEmpty, kDeflate, kPuff);
241 }
242
243 // Tests a Fixed Huffman table compressed buffer with only one literal.
TEST_F(PuffinTest,OneLiteralFixedHuffmanTableTest)244 TEST_F(PuffinTest, OneLiteralFixedHuffmanTableTest) {
245 const Buffer kDeflate = {0x63, 0x04, 0x00};
246 const Buffer kPuff = {0x00, 0x00, 0xA0, 0x00, 0x01, 0xFF, 0x81};
247 CheckSample(kRaw1, kDeflate, kPuff);
248 }
249
250 // Tests deflate of an empty buffer.
TEST_F(PuffinTest,EmptyTest)251 TEST_F(PuffinTest, EmptyTest) {
252 const Buffer kDeflate = {0x03, 0x00};
253 const Buffer kPuff = {0x00, 0x00, 0xA0, 0xFF, 0x81};
254 CheckSample(kRawEmpty, kDeflate, kPuff);
255 }
256
257 // Tests a simple buffer with compress deflate block using fixed Huffman table.
TEST_F(PuffinTest,FixedHuffmanTableCompressedTest)258 TEST_F(PuffinTest, FixedHuffmanTableCompressedTest) {
259 const Buffer kDeflate = {0x63, 0x64, 0x62, 0x66, 0x61, 0x05, 0x00};
260 const Buffer kPuff = {0x00, 0x00, 0xA0, 0x04, 0x01, 0x02,
261 0x03, 0x04, 0x05, 0xFF, 0x81};
262 CheckSample(kRaw5, kDeflate, kPuff);
263 }
264
265 // Tests that uncompressed deflate blocks are not ignored when the output
266 // deflate location pointer is null.
TEST_F(PuffinTest,NoIgnoreUncompressedBlocksTest)267 TEST_F(PuffinTest, NoIgnoreUncompressedBlocksTest) {
268 const Buffer kDeflate = {0x01, 0x05, 0x00, 0xFA, 0xFF,
269 0x01, 0x02, 0x03, 0x04, 0x05};
270 BufferBitReader bit_reader(kDeflate.data(), kDeflate.size());
271 Buffer puff_buffer(11); // Same size as |uncomp_puff| below.
272 BufferPuffWriter puff_writer(puff_buffer.data(), puff_buffer.size());
273 vector<BitExtent> deflates;
274 EXPECT_TRUE(puffer_.PuffDeflate(&bit_reader, &puff_writer, nullptr));
275 const Buffer kPuff = {0x00, 0x00, 0x80, 0x04, 0x01, 0x02,
276 0x03, 0x04, 0x05, 0xFF, 0x81};
277 EXPECT_EQ(puff_writer.Size(), kPuff.size());
278 EXPECT_EQ(puff_buffer, kPuff);
279 }
280
281 // Tests that uncompressed deflate blocks are ignored when the output
282 // deflate location pointer is valid.
TEST_F(PuffinTest,IgnoreUncompressedBlocksTest)283 TEST_F(PuffinTest, IgnoreUncompressedBlocksTest) {
284 const Buffer kDeflate = {0x01, 0x05, 0x00, 0xFA, 0xFF,
285 0x01, 0x02, 0x03, 0x04, 0x05};
286 BufferBitReader bit_reader(kDeflate.data(), kDeflate.size());
287 BufferPuffWriter puff_writer(nullptr, 0);
288 vector<BitExtent> deflates;
289 EXPECT_TRUE(puffer_.PuffDeflate(&bit_reader, &puff_writer, &deflates));
290 EXPECT_TRUE(deflates.empty());
291 }
292
293 namespace {
294 // It is actuall the content of the copyright header.
295 const Buffer kDynamicHTRaw = {
296 0x0A, 0x2F, 0x2F, 0x0A, 0x2F, 0x2F, 0x20, 0x43, 0x6F, 0x70, 0x79, 0x72,
297 0x69, 0x67, 0x68, 0x74, 0x20, 0x28, 0x43, 0x29, 0x20, 0x32, 0x30, 0x31,
298 0x37, 0x20, 0x54, 0x68, 0x65, 0x20, 0x41, 0x6E, 0x64, 0x72, 0x6F, 0x69,
299 0x64, 0x20, 0x4F, 0x70, 0x65, 0x6E, 0x20, 0x53, 0x6F, 0x75, 0x72, 0x63,
300 0x65, 0x20, 0x50, 0x72, 0x6F, 0x6A, 0x65, 0x63, 0x74, 0x0A, 0x2F, 0x2F,
301 0x0A, 0x2F, 0x2F, 0x20, 0x4C, 0x69, 0x63, 0x65, 0x6E, 0x73, 0x65, 0x64,
302 0x20, 0x75, 0x6E, 0x64, 0x65, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x41,
303 0x70, 0x61, 0x63, 0x68, 0x65, 0x20, 0x4C, 0x69, 0x63, 0x65, 0x6E, 0x73,
304 0x65, 0x2C, 0x20, 0x56, 0x65, 0x72, 0x73, 0x69, 0x6F, 0x6E, 0x20, 0x32,
305 0x2E, 0x30, 0x20, 0x28, 0x74, 0x68, 0x65, 0x20, 0x22, 0x4C, 0x69, 0x63,
306 0x65, 0x6E, 0x73, 0x65, 0x22, 0x29, 0x3B, 0x0A, 0x2F, 0x2F, 0x20, 0x79,
307 0x6F, 0x75, 0x20, 0x6D, 0x61, 0x79, 0x20, 0x6E, 0x6F, 0x74, 0x20, 0x75,
308 0x73, 0x65, 0x20, 0x74, 0x68, 0x69, 0x73, 0x20, 0x66, 0x69, 0x6C, 0x65,
309 0x20, 0x65, 0x78, 0x63, 0x65, 0x70, 0x74, 0x20, 0x69, 0x6E, 0x20, 0x63,
310 0x6F, 0x6D, 0x70, 0x6C, 0x69, 0x61, 0x6E, 0x63, 0x65, 0x20, 0x77, 0x69,
311 0x74, 0x68, 0x20, 0x74, 0x68, 0x65, 0x20, 0x4C, 0x69, 0x63, 0x65, 0x6E,
312 0x73, 0x65, 0x2E, 0x0A, 0x2F, 0x2F, 0x20, 0x59, 0x6F, 0x75, 0x20, 0x6D,
313 0x61, 0x79, 0x20, 0x6F, 0x62, 0x74, 0x61, 0x69, 0x6E, 0x20, 0x61, 0x20,
314 0x63, 0x6F, 0x70, 0x79, 0x20, 0x6F, 0x66, 0x20, 0x74, 0x68, 0x65, 0x20,
315 0x4C, 0x69, 0x63, 0x65, 0x6E, 0x73, 0x65, 0x20, 0x61, 0x74, 0x0A, 0x2F,
316 0x2F, 0x0A, 0x2F, 0x2F, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x68, 0x74,
317 0x74, 0x70, 0x3A, 0x2F, 0x2F, 0x77, 0x77, 0x77, 0x2E, 0x61, 0x70, 0x61,
318 0x63, 0x68, 0x65, 0x2E, 0x6F, 0x72, 0x67, 0x2F, 0x6C, 0x69, 0x63, 0x65,
319 0x6E, 0x73, 0x65, 0x73, 0x2F, 0x4C, 0x49, 0x43, 0x45, 0x4E, 0x53, 0x45,
320 0x2D, 0x32, 0x2E, 0x30, 0x0A, 0x2F, 0x2F, 0x0A, 0x2F, 0x2F, 0x20, 0x55,
321 0x6E, 0x6C, 0x65, 0x73, 0x73, 0x20, 0x72, 0x65, 0x71, 0x75, 0x69, 0x72,
322 0x65, 0x64, 0x20, 0x62, 0x79, 0x20, 0x61, 0x70, 0x70, 0x6C, 0x69, 0x63,
323 0x61, 0x62, 0x6C, 0x65, 0x20, 0x6C, 0x61, 0x77, 0x20, 0x6F, 0x72, 0x20,
324 0x61, 0x67, 0x72, 0x65, 0x65, 0x64, 0x20, 0x74, 0x6F, 0x20, 0x69, 0x6E,
325 0x20, 0x77, 0x72, 0x69, 0x74, 0x69, 0x6E, 0x67, 0x2C, 0x20, 0x73, 0x6F,
326 0x66, 0x74, 0x77, 0x61, 0x72, 0x65, 0x0A, 0x2F, 0x2F, 0x20, 0x64, 0x69,
327 0x73, 0x74, 0x72, 0x69, 0x62, 0x75, 0x74, 0x65, 0x64, 0x20, 0x75, 0x6E,
328 0x64, 0x65, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x4C, 0x69, 0x63, 0x65,
329 0x6E, 0x73, 0x65, 0x20, 0x69, 0x73, 0x20, 0x64, 0x69, 0x73, 0x74, 0x72,
330 0x69, 0x62, 0x75, 0x74, 0x65, 0x64, 0x20, 0x6F, 0x6E, 0x20, 0x61, 0x6E,
331 0x20, 0x22, 0x41, 0x53, 0x20, 0x49, 0x53, 0x22, 0x20, 0x42, 0x41, 0x53,
332 0x49, 0x53, 0x2C, 0x0A, 0x2F, 0x2F, 0x20, 0x57, 0x49, 0x54, 0x48, 0x4F,
333 0x55, 0x54, 0x20, 0x57, 0x41, 0x52, 0x52, 0x41, 0x4E, 0x54, 0x49, 0x45,
334 0x53, 0x20, 0x4F, 0x52, 0x20, 0x43, 0x4F, 0x4E, 0x44, 0x49, 0x54, 0x49,
335 0x4F, 0x4E, 0x53, 0x20, 0x4F, 0x46, 0x20, 0x41, 0x4E, 0x59, 0x20, 0x4B,
336 0x49, 0x4E, 0x44, 0x2C, 0x20, 0x65, 0x69, 0x74, 0x68, 0x65, 0x72, 0x20,
337 0x65, 0x78, 0x70, 0x72, 0x65, 0x73, 0x73, 0x20, 0x6F, 0x72, 0x20, 0x69,
338 0x6D, 0x70, 0x6C, 0x69, 0x65, 0x64, 0x2E, 0x0A, 0x2F, 0x2F, 0x20, 0x53,
339 0x65, 0x65, 0x20, 0x74, 0x68, 0x65, 0x20, 0x4C, 0x69, 0x63, 0x65, 0x6E,
340 0x73, 0x65, 0x20, 0x66, 0x6F, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x73,
341 0x70, 0x65, 0x63, 0x69, 0x66, 0x69, 0x63, 0x20, 0x6C, 0x61, 0x6E, 0x67,
342 0x75, 0x61, 0x67, 0x65, 0x20, 0x67, 0x6F, 0x76, 0x65, 0x72, 0x6E, 0x69,
343 0x6E, 0x67, 0x20, 0x70, 0x65, 0x72, 0x6D, 0x69, 0x73, 0x73, 0x69, 0x6F,
344 0x6E, 0x73, 0x20, 0x61, 0x6E, 0x64, 0x0A, 0x2F, 0x2F, 0x20, 0x6C, 0x69,
345 0x6D, 0x69, 0x74, 0x61, 0x74, 0x69, 0x6F, 0x6E, 0x73, 0x20, 0x75, 0x6E,
346 0x64, 0x65, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x4C, 0x69, 0x63, 0x65,
347 0x6E, 0x73, 0x65, 0x2E, 0x0A};
348
349 // Dynamic huffman compressed deflate.
350 const Buffer kDynamicHTDeflate = {
351 0x65, 0x91, 0x41, 0x6F, 0x9C, 0x30, 0x10, 0x85, 0xEF, 0xFB, 0x2B, 0x9E,
352 0xF6, 0x94, 0x48, 0x5B, 0x48, 0x73, 0xA9, 0xD4, 0x9E, 0xE8, 0x66, 0xAB,
353 0xA0, 0x46, 0x50, 0x2D, 0xA4, 0x51, 0x8E, 0x5E, 0x18, 0xD8, 0x89, 0x58,
354 0xDB, 0xB5, 0x4D, 0xC9, 0xFE, 0xFB, 0x8E, 0x59, 0x22, 0x25, 0xAA, 0x2F,
355 0xC8, 0xCC, 0xCC, 0x9B, 0xEF, 0x3D, 0xAF, 0xD2, 0x74, 0x95, 0xA6, 0xD8,
356 0x1A, 0x7B, 0x76, 0xDC, 0x1F, 0x03, 0xAE, 0xB6, 0xD7, 0xB8, 0xBD, 0xF9,
357 0xFC, 0x05, 0xF5, 0x91, 0x90, 0xE9, 0xD6, 0x19, 0x6E, 0x51, 0x5A, 0xD2,
358 0xA8, 0xCC, 0xE8, 0x1A, 0xC2, 0x2F, 0x67, 0x5E, 0xA8, 0x09, 0xAB, 0xCB,
359 0xE0, 0x03, 0x37, 0xA4, 0x3D, 0xB5, 0x18, 0x75, 0x4B, 0x0E, 0x21, 0x0E,
360 0x59, 0xD5, 0xC8, 0x67, 0xA9, 0x6C, 0xF0, 0x9B, 0x9C, 0x67, 0xA3, 0x71,
361 0x9B, 0xDC, 0xE0, 0x2A, 0x36, 0xAC, 0x97, 0xD2, 0xFA, 0xFA, 0x5B, 0x94,
362 0x38, 0x9B, 0x11, 0x27, 0x75, 0x86, 0x36, 0x01, 0xA3, 0x27, 0xD1, 0x60,
363 0x8F, 0x8E, 0x07, 0x02, 0xBD, 0x36, 0x64, 0x03, 0x58, 0xA3, 0x31, 0x27,
364 0x3B, 0xB0, 0xD2, 0xB2, 0x7F, 0xE2, 0x70, 0x9C, 0xF7, 0x2C, 0x2A, 0x49,
365 0xD4, 0x78, 0x5E, 0x34, 0xCC, 0x21, 0x28, 0x69, 0x57, 0x32, 0x60, 0xE5,
366 0xD6, 0xBD, 0x6F, 0x84, 0x7A, 0x83, 0x9E, 0xCF, 0x31, 0x04, 0xFB, 0x35,
367 0x4D, 0xA7, 0x69, 0x4A, 0xD4, 0x4C, 0x9C, 0x18, 0xD7, 0xA7, 0xC3, 0xA5,
368 0xD7, 0xA7, 0x0F, 0xF9, 0x76, 0x57, 0x54, 0xBB, 0x4F, 0x42, 0xBD, 0x4C,
369 0x3D, 0xEA, 0x81, 0xBC, 0x87, 0xA3, 0x3F, 0x23, 0x3B, 0x71, 0x7C, 0x38,
370 0x43, 0x59, 0xA1, 0x6A, 0xD4, 0x41, 0x58, 0x07, 0x35, 0xC1, 0x38, 0xA8,
371 0xDE, 0x91, 0xD4, 0x82, 0x89, 0xD4, 0x93, 0xE3, 0xC0, 0xBA, 0xDF, 0xC0,
372 0x9B, 0x2E, 0x4C, 0xCA, 0x51, 0x94, 0x69, 0xD9, 0x07, 0xC7, 0x87, 0x31,
373 0x7C, 0x08, 0xED, 0x8D, 0x51, 0xAC, 0xBF, 0x6F, 0x90, 0xD8, 0x94, 0xC6,
374 0x3A, 0xAB, 0x90, 0x57, 0x6B, 0x7C, 0xCF, 0xAA, 0xBC, 0xDA, 0x44, 0x91,
375 0xA7, 0xBC, 0xBE, 0x2F, 0x1F, 0x6B, 0x3C, 0x65, 0xFB, 0x7D, 0x56, 0xD4,
376 0xF9, 0xAE, 0x42, 0xB9, 0xC7, 0xB6, 0x2C, 0xEE, 0xF2, 0x3A, 0x2F, 0x0B,
377 0xB9, 0xFD, 0x40, 0x56, 0x3C, 0xE3, 0x67, 0x5E, 0xDC, 0x6D, 0x40, 0x12,
378 0x99, 0xEC, 0xA1, 0x57, 0xEB, 0xA2, 0x03, 0xC1, 0xE4, 0x18, 0x27, 0xB5,
379 0x73, 0x76, 0x15, 0xD1, 0x07, 0x84, 0xCE, 0x5C, 0x90, 0xBC, 0xA5, 0x86,
380 0x3B, 0x6E, 0xC4, 0x9A, 0xEE, 0x47, 0xD5, 0x13, 0x7A, 0xF3, 0x97, 0x9C,
381 0x16, 0x47, 0xB0, 0xE4, 0x4E, 0xEC, 0xE3, 0xB3, 0x7A, 0x01, 0x6C, 0xA3,
382 0xCC, 0xC0, 0x27, 0x0E, 0x2A, 0xCC, 0xBF, 0xFE, 0xF3, 0x95, 0xAC, 0xFE,
383 0x01};
384
385 const Buffer kDynamicHTPuff = {
386 0x00, 0x74, 0xC0, 0x0C, 0x11, 0x0C, 0x04, 0x63, 0x34, 0x32, 0x03, 0x04,
387 0x05, 0x06, 0x1B, 0x07, 0x26, 0x03, 0x00, 0x07, 0x16, 0x08, 0x08, 0x00,
388 0x00, 0x07, 0x09, 0x06, 0x06, 0x08, 0x09, 0x08, 0x15, 0x09, 0x00, 0x00,
389 0x09, 0x09, 0x16, 0x06, 0x09, 0x07, 0x08, 0x07, 0x09, 0x00, 0x08, 0x06,
390 0x00, 0x09, 0x08, 0x00, 0x06, 0x06, 0x09, 0x00, 0x07, 0x06, 0x06, 0x08,
391 0x09, 0x08, 0x00, 0x08, 0x18, 0x05, 0x07, 0x06, 0x06, 0x04, 0x06, 0x06,
392 0x07, 0x04, 0x08, 0x00, 0x06, 0x07, 0x05, 0x05, 0x05, 0x09, 0x05, 0x05,
393 0x05, 0x06, 0x09, 0x06, 0x08, 0x07, 0x97, 0x09, 0x04, 0x05, 0x06, 0x07,
394 0x06, 0x08, 0x00, 0x00, 0x08, 0x08, 0x00, 0x09, 0x05, 0x15, 0x06, 0x00,
395 0x05, 0x06, 0x04, 0x04, 0x04, 0x03, 0x04, 0x02, 0x03, 0x03, 0x05, 0x39,
396 0x0A, 0x2F, 0x2F, 0x0A, 0x2F, 0x2F, 0x20, 0x43, 0x6F, 0x70, 0x79, 0x72,
397 0x69, 0x67, 0x68, 0x74, 0x20, 0x28, 0x43, 0x29, 0x20, 0x32, 0x30, 0x31,
398 0x37, 0x20, 0x54, 0x68, 0x65, 0x20, 0x41, 0x6E, 0x64, 0x72, 0x6F, 0x69,
399 0x64, 0x20, 0x4F, 0x70, 0x65, 0x6E, 0x20, 0x53, 0x6F, 0x75, 0x72, 0x63,
400 0x65, 0x20, 0x50, 0x72, 0x6F, 0x6A, 0x65, 0x63, 0x74, 0x0A, 0x83, 0x00,
401 0x38, 0x0F, 0x4C, 0x69, 0x63, 0x65, 0x6E, 0x73, 0x65, 0x64, 0x20, 0x75,
402 0x6E, 0x64, 0x65, 0x72, 0x20, 0x74, 0x81, 0x00, 0x34, 0x02, 0x70, 0x61,
403 0x63, 0x80, 0x00, 0x06, 0x84, 0x00, 0x19, 0x0E, 0x2C, 0x20, 0x56, 0x65,
404 0x72, 0x73, 0x69, 0x6F, 0x6E, 0x20, 0x32, 0x2E, 0x30, 0x20, 0x28, 0x81,
405 0x00, 0x20, 0x00, 0x22, 0x84, 0x00, 0x1A, 0x02, 0x22, 0x29, 0x3B, 0x81,
406 0x00, 0x42, 0x0E, 0x79, 0x6F, 0x75, 0x20, 0x6D, 0x61, 0x79, 0x20, 0x6E,
407 0x6F, 0x74, 0x20, 0x75, 0x73, 0x65, 0x80, 0x00, 0x43, 0x19, 0x69, 0x73,
408 0x20, 0x66, 0x69, 0x6C, 0x65, 0x20, 0x65, 0x78, 0x63, 0x65, 0x70, 0x74,
409 0x20, 0x69, 0x6E, 0x20, 0x63, 0x6F, 0x6D, 0x70, 0x6C, 0x69, 0x61, 0x6E,
410 0x80, 0x00, 0x7F, 0x03, 0x77, 0x69, 0x74, 0x68, 0x82, 0x00, 0x67, 0x84,
411 0x00, 0x45, 0x00, 0x2E, 0x81, 0x00, 0x43, 0x00, 0x59, 0x84, 0x00, 0x43,
412 0x03, 0x6F, 0x62, 0x74, 0x61, 0x80, 0x00, 0x2E, 0x00, 0x61, 0x80, 0x00,
413 0x30, 0x00, 0x70, 0x80, 0x00, 0x0D, 0x00, 0x66, 0x89, 0x00, 0x28, 0x01,
414 0x20, 0x61, 0x85, 0x00, 0xB4, 0x82, 0x00, 0x00, 0x0B, 0x68, 0x74, 0x74,
415 0x70, 0x3A, 0x2F, 0x2F, 0x77, 0x77, 0x77, 0x2E, 0x61, 0x82, 0x00, 0xB1,
416 0x05, 0x2E, 0x6F, 0x72, 0x67, 0x2F, 0x6C, 0x83, 0x00, 0x2B, 0x09, 0x73,
417 0x2F, 0x4C, 0x49, 0x43, 0x45, 0x4E, 0x53, 0x45, 0x2D, 0x80, 0x00, 0xB5,
418 0x84, 0x00, 0x35, 0x0C, 0x55, 0x6E, 0x6C, 0x65, 0x73, 0x73, 0x20, 0x72,
419 0x65, 0x71, 0x75, 0x69, 0x72, 0x80, 0x00, 0xF1, 0x04, 0x62, 0x79, 0x20,
420 0x61, 0x70, 0x80, 0x00, 0x95, 0x02, 0x63, 0x61, 0x62, 0x80, 0x00, 0xAB,
421 0x0A, 0x6C, 0x61, 0x77, 0x20, 0x6F, 0x72, 0x20, 0x61, 0x67, 0x72, 0x65,
422 0x80, 0x00, 0x1B, 0x01, 0x74, 0x6F, 0x81, 0x00, 0xB5, 0x10, 0x77, 0x72,
423 0x69, 0x74, 0x69, 0x6E, 0x67, 0x2C, 0x20, 0x73, 0x6F, 0x66, 0x74, 0x77,
424 0x61, 0x72, 0x65, 0x81, 0x00, 0x46, 0x08, 0x64, 0x69, 0x73, 0x74, 0x72,
425 0x69, 0x62, 0x75, 0x74, 0x8A, 0x01, 0x34, 0x85, 0x00, 0xA3, 0x80, 0x00,
426 0xFA, 0x89, 0x00, 0x20, 0x80, 0x01, 0x36, 0x10, 0x61, 0x6E, 0x20, 0x22,
427 0x41, 0x53, 0x20, 0x49, 0x53, 0x22, 0x20, 0x42, 0x41, 0x53, 0x49, 0x53,
428 0x2C, 0x81, 0x00, 0x44, 0x1E, 0x57, 0x49, 0x54, 0x48, 0x4F, 0x55, 0x54,
429 0x20, 0x57, 0x41, 0x52, 0x52, 0x41, 0x4E, 0x54, 0x49, 0x45, 0x53, 0x20,
430 0x4F, 0x52, 0x20, 0x43, 0x4F, 0x4E, 0x44, 0x49, 0x54, 0x49, 0x4F, 0x4E,
431 0x80, 0x00, 0x0D, 0x0C, 0x46, 0x20, 0x41, 0x4E, 0x59, 0x20, 0x4B, 0x49,
432 0x4E, 0x44, 0x2C, 0x20, 0x65, 0x80, 0x01, 0x32, 0x80, 0x00, 0x67, 0x03,
433 0x65, 0x78, 0x70, 0x72, 0x81, 0x00, 0xC1, 0x80, 0x00, 0xA6, 0x00, 0x69,
434 0x81, 0x01, 0x4E, 0x01, 0x65, 0x64, 0x82, 0x01, 0x3B, 0x02, 0x53, 0x65,
435 0x65, 0x8A, 0x00, 0x82, 0x01, 0x66, 0x6F, 0x83, 0x00, 0x92, 0x07, 0x73,
436 0x70, 0x65, 0x63, 0x69, 0x66, 0x69, 0x63, 0x80, 0x00, 0xDA, 0x0C, 0x6E,
437 0x67, 0x75, 0x61, 0x67, 0x65, 0x20, 0x67, 0x6F, 0x76, 0x65, 0x72, 0x6E,
438 0x80, 0x00, 0xD1, 0x06, 0x20, 0x70, 0x65, 0x72, 0x6D, 0x69, 0x73, 0x81,
439 0x01, 0xD6, 0x00, 0x73, 0x80, 0x00, 0xA0, 0x00, 0x64, 0x81, 0x00, 0x46,
440 0x06, 0x6C, 0x69, 0x6D, 0x69, 0x74, 0x61, 0x74, 0x82, 0x00, 0x12, 0x8E,
441 0x00, 0xD7, 0x01, 0x2E, 0x0A, 0xFF, 0x81};
442 } // namespace
443
444 // Tests a compressed deflate block using dynamic Huffman table.
TEST_F(PuffinTest,DynamicHuffmanTableTest)445 TEST_F(PuffinTest, DynamicHuffmanTableTest) {
446 CheckSample(kDynamicHTRaw, kDynamicHTDeflate, kDynamicHTPuff);
447 }
448
449 // Tests an uncompressed deflate block with invalid LEN/NLEN.
TEST_F(PuffinTest,PuffInvalidUncompressedLengthDeflateTest)450 TEST_F(PuffinTest, PuffInvalidUncompressedLengthDeflateTest) {
451 const Buffer kDeflate = {0x01, 0x05, 0x00, 0xFF, 0xFF,
452 0x01, 0x02, 0x03, 0x04, 0x05};
453 Buffer puffed;
454 FailPuffDeflate(kDeflate, &puffed);
455 }
456
457 // Tests puffing a block with invalid block header.
TEST_F(PuffinTest,PuffInvalidBlockHeaderDeflateTest)458 TEST_F(PuffinTest, PuffInvalidBlockHeaderDeflateTest) {
459 const Buffer kDeflate = {0x07};
460 Buffer puffed;
461 FailPuffDeflate(kDeflate, &puffed);
462 }
463
464 // Tests puffing a block with final block bit unset so it returns false.
TEST_F(PuffinTest,PuffDeflateNoFinalBlockBitTest)465 TEST_F(PuffinTest, PuffDeflateNoFinalBlockBitTest) {
466 const Buffer kDeflate = {0x62, 0x04, 0x00};
467 const Buffer kPuff = {0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81};
468 CheckSample(kRaw1, kDeflate, kPuff);
469 }
470
471 // Tests two deflate buffers concatenated, neither have their final bit set. It
472 // is a valid deflate and puff buffer.
TEST_F(PuffinTest,MultipleDeflateBufferNoFinabBitsTest)473 TEST_F(PuffinTest, MultipleDeflateBufferNoFinabBitsTest) {
474 const Buffer kDeflate = {0x62, 0x04, 0x88, 0x11, 0x00};
475 const Buffer kPuff = {0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81,
476 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81};
477 CheckSample(kRaw2, kDeflate, kPuff);
478 }
479
480 // Tests two deflate buffers concatenated, the first one has final bit set,
481 // second one not. It is a valid deflate and puff buffer.
TEST_F(PuffinTest,MultipleDeflateBufferOneFinalBitTest)482 TEST_F(PuffinTest, MultipleDeflateBufferOneFinalBitTest) {
483 const Buffer kDeflate = {0x63, 0x04, 0x88, 0x11, 0x00};
484 const Buffer kPuff = {0x00, 0x00, 0xA0, 0x00, 0x01, 0xFF, 0x81,
485 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81};
486 CheckSample(kRaw2, kDeflate, kPuff);
487 }
488
489 // Tests two deflate buffers concatenated, both have final bits set. It is a
490 // valid deflate and puff buffer.
TEST_F(PuffinTest,MultipleDeflateBufferBothFinalBitTest)491 TEST_F(PuffinTest, MultipleDeflateBufferBothFinalBitTest) {
492 const Buffer kDeflate = {0x63, 0x04, 0x8C, 0x11, 0x00};
493 const Buffer kPuff = {0x00, 0x00, 0xA0, 0x00, 0x01, 0xFF, 0x81,
494 0x00, 0x00, 0xA0, 0x00, 0x01, 0xFF, 0x81};
495 CheckSample(kRaw2, kDeflate, kPuff);
496 }
497
498 // When locating deflates, the puffer has to end when it hit a final block. Test
499 // that with two deflate buffers concatenated and both have final bits set.
TEST_F(PuffinTest,EndOnFinalBitTest)500 TEST_F(PuffinTest, EndOnFinalBitTest) {
501 const Buffer kDeflate = {0x63, 0x04, 0x8C, 0x11, 0x00};
502 BufferBitReader bit_reader(kDeflate.data(), kDeflate.size());
503 BufferPuffWriter puff_writer(nullptr, 0);
504 vector<BitExtent> deflates;
505 EXPECT_TRUE(puffer_.PuffDeflate(&bit_reader, &puff_writer, &deflates));
506 const vector<BitExtent> kExpectedDeflates = {{0, 18}};
507 EXPECT_EQ(deflates, kExpectedDeflates);
508 EXPECT_EQ(bit_reader.Offset(), 3);
509 }
510
511 // TODO(ahassani): Add unittests for Failhuff too.
512
513 namespace {
514 // The following is a sequence of bits starting from the top right and ends in
515 // bottom left. It represents the bits in |kGapDeflates|. Bits inside the
516 // brackets (including bits exactly under brackets) represent a deflate stream.
517 //
518 // } { } { }{ }
519 // 11000101 10000000 10001100 01010000 00010001 10001000 00000100 01100010
520 // 0xC5 0x80 0x8C 0x50 0x11 0x88 0x04 0x62
521 //
522 // } { } { } {
523 // 10001011 11111100 00000100 01100010 00000001 00011000 10111000 00001000
524 // 0x8B 0xFC 0x04 0x62 0x01 0x18 0xB8 0x08
525 //
526 // } { } { }{
527 // 10001011 00000001 00011000 10111111 11000000 01000110 00100000 00010001
528 // 0x8B 0x01 0x18 0xBF 0xC0 0x46 0x20 0x11
529 //
530 // { } { } {
531 // 11111100 00000100 01100010 11111111 00000001 00011000 10110000 00010001
532 // 0xFC 0x04 0x62 0xFF 0x01 0x18 0xB0 0x11
533 //
534 const Buffer kGapDeflates = {0x62, 0x04, 0x88, 0x11, 0x50, 0x8C, 0x80, 0xC5,
535 0x08, 0xB8, 0x18, 0x01, 0x62, 0x04, 0xFC, 0x8B,
536 0x11, 0x20, 0x46, 0xC0, 0xBF, 0x18, 0x01, 0x8B,
537 0x11, 0xB0, 0x18, 0x01, 0xFF, 0x62, 0x04, 0xFC};
538
539 const Buffer kGapPuffs = {0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 0
540 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 7
541 0x01, // raw 14
542 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 15
543 0x01, 0x01, // raw 22
544 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 24
545 0x07, // raw 31
546 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 32
547 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 39
548 0x3F, 0x03, // raw 46
549 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 48
550 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 55
551 0x03, 0x3F, // raw 62
552 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 64
553 0x03, // raw 71
554 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 72
555 0x03, // raw 79
556 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 80
557 0xFF, // raw 87
558 0x00, 0x00, 0x20, 0x00, 0x01, 0xFF, 0x81, // puff 88
559 0x3F}; // raw 95
560
561 // The fifth deflate (and its puff in kGapPuffExtents) is for zero length
562 // deflate corner case.
563 const vector<BitExtent> kGapSubblockDeflateExtents = {
564 {0, 18}, {18, 18}, {37, 18}, {57, 18}, {75, 0}, {78, 18}, {96, 18},
565 {122, 18}, {140, 18}, {166, 18}, {186, 18}, {206, 18}, {232, 18}};
566
567 const vector<ByteExtent> kGapPuffExtents = {
568 {0, 7}, {7, 7}, {15, 7}, {24, 7}, {31, 0}, {32, 7}, {39, 7},
569 {48, 7}, {55, 7}, {64, 7}, {72, 7}, {80, 7}, {88, 7}};
570 } // namespace
571
TEST_F(PuffinTest,BitExtentPuffAndHuffTest)572 TEST_F(PuffinTest, BitExtentPuffAndHuffTest) {
573 CheckBitExtentsPuffAndHuff(kGapDeflates, kGapSubblockDeflateExtents,
574 kGapPuffs, kGapPuffExtents);
575 }
576
TEST_F(PuffinTest,ExcludeBadDistanceCaches)577 TEST_F(PuffinTest, ExcludeBadDistanceCaches) {
578 BufferBitReader br(kProblematicCache.data(), kProblematicCache.size());
579 BufferPuffWriter pw(nullptr, 0);
580
581 // The first two bits of this data should be ignored.
582 br.CacheBits(2);
583 br.DropBits(2);
584
585 vector<BitExtent> deflates, empty;
586 Puffer puffer(true);
587 EXPECT_TRUE(puffer.PuffDeflate(&br, &pw, &deflates));
588 EXPECT_EQ(deflates, empty);
589 }
590
TEST_F(PuffinTest,NoExcludeBadDistanceCaches)591 TEST_F(PuffinTest, NoExcludeBadDistanceCaches) {
592 BufferBitReader br(kProblematicCache.data(), kProblematicCache.size());
593 BufferPuffWriter pw(nullptr, 0);
594
595 // The first two bits of this data should be ignored.
596 br.CacheBits(2);
597 br.DropBits(2);
598
599 vector<BitExtent> deflates;
600 Puffer puffer; // The default value for excluding bad distance cache should
601 // be false.
602 EXPECT_TRUE(puffer.PuffDeflate(&br, &pw, &deflates));
603 EXPECT_EQ(deflates, kProblematicCacheDeflateExtents);
604 }
605
606 } // namespace puffin
607