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 "puffin/src/include/puffin/puffer.h"
6
7 #include <algorithm>
8 #include <memory>
9 #include <string>
10 #include <utility>
11 #include <vector>
12
13 #include "puffin/src/bit_reader.h"
14 #include "puffin/src/huffman_table.h"
15 #include "puffin/src/include/puffin/common.h"
16 #include "puffin/src/include/puffin/stream.h"
17 #include "puffin/src/puff_data.h"
18 #include "puffin/src/puff_writer.h"
19 #include "puffin/src/set_errors.h"
20
21 namespace puffin {
22
23 using std::vector;
24 using std::string;
25
Puffer()26 Puffer::Puffer() : dyn_ht_(new HuffmanTable()), fix_ht_(new HuffmanTable()) {}
27
~Puffer()28 Puffer::~Puffer() {}
29
PuffDeflate(BitReaderInterface * br,PuffWriterInterface * pw,vector<BitExtent> * deflates,Error * error) const30 bool Puffer::PuffDeflate(BitReaderInterface* br,
31 PuffWriterInterface* pw,
32 vector<BitExtent>* deflates,
33 Error* error) const {
34 *error = Error::kSuccess;
35 PuffData pd;
36 HuffmanTable* cur_ht;
37 // No bits left to read, return. We try to cache at least eight bits because
38 // the minimum length of a deflate bit stream is 8: (fixed huffman table) 3
39 // bits header + 5 bits just one len/dist symbol.
40 while (br->CacheBits(8)) {
41 auto start_bit_offset = br->OffsetInBits();
42
43 TEST_AND_RETURN_FALSE_SET_ERROR(br->CacheBits(3),
44 Error::kInsufficientInput);
45 uint8_t final_bit = br->ReadBits(1); // BFINAL
46 br->DropBits(1);
47 uint8_t type = br->ReadBits(2); // BTYPE
48 br->DropBits(2);
49 DVLOG(2) << "Read block type: "
50 << BlockTypeToString(static_cast<BlockType>(type));
51
52 // Header structure
53 // +-+-+-+-+-+-+-+-+
54 // |F| TP| SKIP |
55 // +-+-+-+-+-+-+-+-+
56 // F -> final_bit
57 // TP -> type
58 // SKIP -> skipped_bits (only in kUncompressed type)
59 auto block_header = (final_bit << 7) | (type << 5);
60 switch (static_cast<BlockType>(type)) {
61 case BlockType::kUncompressed: {
62 auto skipped_bits = br->ReadBoundaryBits();
63 br->SkipBoundaryBits();
64 TEST_AND_RETURN_FALSE_SET_ERROR(br->CacheBits(32),
65 Error::kInsufficientInput);
66 auto len = br->ReadBits(16); // LEN
67 br->DropBits(16);
68 auto nlen = br->ReadBits(16); // NLEN
69 br->DropBits(16);
70
71 if ((len ^ nlen) != 0xFFFF) {
72 LOG(ERROR) << "Length of uncompressed data is invalid;"
73 << " LEN(" << len << ") NLEN(" << nlen << ")";
74 *error = Error::kInvalidInput;
75 return false;
76 }
77
78 // Put skipped bits into header.
79 block_header |= skipped_bits;
80
81 // Insert block header.
82 pd.type = PuffData::Type::kBlockMetadata;
83 pd.block_metadata[0] = block_header;
84 pd.length = 1;
85 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
86
87 // Insert all the raw literals.
88 pd.type = PuffData::Type::kLiterals;
89 pd.length = len;
90 TEST_AND_RETURN_FALSE_SET_ERROR(
91 br->GetByteReaderFn(pd.length, &pd.read_fn),
92 Error::kInsufficientInput);
93 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
94
95 pd.type = PuffData::Type::kEndOfBlock;
96 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
97
98 if (deflates != nullptr) {
99 deflates->emplace_back(start_bit_offset,
100 br->OffsetInBits() - start_bit_offset);
101 }
102
103 // continue the loop. Do not read any literal/length/distance.
104 continue;
105 }
106
107 case BlockType::kFixed:
108 fix_ht_->BuildFixedHuffmanTable();
109 cur_ht = fix_ht_.get();
110 pd.type = PuffData::Type::kBlockMetadata;
111 pd.block_metadata[0] = block_header;
112 pd.length = 1;
113 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
114 break;
115
116 case BlockType::kDynamic:
117 pd.type = PuffData::Type::kBlockMetadata;
118 pd.block_metadata[0] = block_header;
119 pd.length = sizeof(pd.block_metadata) - 1;
120 TEST_AND_RETURN_FALSE(dyn_ht_->BuildDynamicHuffmanTable(
121 br, &pd.block_metadata[1], &pd.length, error));
122 pd.length += 1; // For the header.
123 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
124 cur_ht = dyn_ht_.get();
125 break;
126
127 default:
128 LOG(ERROR) << "Invalid block compression type: "
129 << static_cast<int>(type);
130 *error = Error::kInvalidInput;
131 return false;
132 }
133
134 while (true) { // Breaks when the end of block is reached.
135 auto max_bits = cur_ht->LitLenMaxBits();
136 if (!br->CacheBits(max_bits)) {
137 // It could be the end of buffer and the bit length of the end_of_block
138 // symbol has less than maximum bit length of current Huffman table. So
139 // only asking for the size of end of block symbol (256).
140 TEST_AND_RETURN_FALSE_SET_ERROR(cur_ht->EndOfBlockBitLength(&max_bits),
141 Error::kInvalidInput);
142 }
143 TEST_AND_RETURN_FALSE_SET_ERROR(br->CacheBits(max_bits),
144 Error::kInsufficientInput);
145 auto bits = br->ReadBits(max_bits);
146 uint16_t lit_len_alphabet;
147 size_t nbits;
148 TEST_AND_RETURN_FALSE_SET_ERROR(
149 cur_ht->LitLenAlphabet(bits, &lit_len_alphabet, &nbits),
150 Error::kInvalidInput);
151 br->DropBits(nbits);
152 if (lit_len_alphabet < 256) {
153 pd.type = PuffData::Type::kLiteral;
154 pd.byte = lit_len_alphabet;
155 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
156
157 } else if (256 == lit_len_alphabet) {
158 pd.type = PuffData::Type::kEndOfBlock;
159 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
160 if (deflates != nullptr) {
161 deflates->emplace_back(start_bit_offset,
162 br->OffsetInBits() - start_bit_offset);
163 }
164 break; // Breaks the loop.
165 } else {
166 TEST_AND_RETURN_FALSE_SET_ERROR(lit_len_alphabet <= 285,
167 Error::kInvalidInput);
168 // Reading length.
169 auto len_code_start = lit_len_alphabet - 257;
170 auto extra_bits_len = kLengthExtraBits[len_code_start];
171 uint16_t extra_bits_value = 0;
172 if (extra_bits_len) {
173 TEST_AND_RETURN_FALSE_SET_ERROR(br->CacheBits(extra_bits_len),
174 Error::kInsufficientInput);
175 extra_bits_value = br->ReadBits(extra_bits_len);
176 br->DropBits(extra_bits_len);
177 }
178 auto length = kLengthBases[len_code_start] + extra_bits_value;
179
180 TEST_AND_RETURN_FALSE_SET_ERROR(
181 br->CacheBits(cur_ht->DistanceMaxBits()),
182 Error::kInsufficientInput);
183 auto bits = br->ReadBits(cur_ht->DistanceMaxBits());
184 uint16_t distance_alphabet;
185 size_t nbits;
186 TEST_AND_RETURN_FALSE_SET_ERROR(
187 cur_ht->DistanceAlphabet(bits, &distance_alphabet, &nbits),
188 Error::kInvalidInput);
189 br->DropBits(nbits);
190
191 // Reading distance.
192 extra_bits_len = kDistanceExtraBits[distance_alphabet];
193 extra_bits_value = 0;
194 if (extra_bits_len) {
195 TEST_AND_RETURN_FALSE_SET_ERROR(br->CacheBits(extra_bits_len),
196 Error::kInsufficientInput);
197 extra_bits_value = br->ReadBits(extra_bits_len);
198 br->DropBits(extra_bits_len);
199 }
200
201 pd.type = PuffData::Type::kLenDist;
202 pd.length = length;
203 pd.distance = kDistanceBases[distance_alphabet] + extra_bits_value;
204 TEST_AND_RETURN_FALSE(pw->Insert(pd, error));
205 }
206 }
207 }
208 TEST_AND_RETURN_FALSE(pw->Flush(error));
209 return true;
210 }
211
212 } // namespace puffin
213