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/huffer.h"
6
7 #include <algorithm>
8 #include <memory>
9 #include <string>
10 #include <utility>
11
12 #include "puffin/src/bit_writer.h"
13 #include "puffin/src/huffman_table.h"
14 #include "puffin/src/include/puffin/common.h"
15 #include "puffin/src/include/puffin/stream.h"
16 #include "puffin/src/logging.h"
17 #include "puffin/src/puff_data.h"
18 #include "puffin/src/puff_reader.h"
19
20 using std::string;
21
22 namespace puffin {
23
Huffer()24 Huffer::Huffer() : dyn_ht_(new HuffmanTable()), fix_ht_(new HuffmanTable()) {}
25
~Huffer()26 Huffer::~Huffer() {}
27
HuffDeflate(PuffReaderInterface * pr,BitWriterInterface * bw) const28 bool Huffer::HuffDeflate(PuffReaderInterface* pr,
29 BitWriterInterface* bw) const {
30 PuffData pd;
31 HuffmanTable* cur_ht = nullptr;
32 // If no bytes left for PuffReader to read, bail out.
33 while (pr->BytesLeft() != 0) {
34 TEST_AND_RETURN_FALSE(pr->GetNext(&pd));
35
36 // The first data should be a metadata.
37 TEST_AND_RETURN_FALSE(pd.type == PuffData::Type::kBlockMetadata);
38 auto header = pd.block_metadata[0];
39 auto final_bit = (header & 0x80) >> 7;
40 auto type = (header & 0x60) >> 5;
41 auto skipped_bits = header & 0x1F;
42 DVLOG(2) << "Write block type: "
43 << BlockTypeToString(static_cast<BlockType>(type));
44
45 TEST_AND_RETURN_FALSE(bw->WriteBits(1, final_bit));
46 TEST_AND_RETURN_FALSE(bw->WriteBits(2, type));
47 switch (static_cast<BlockType>(type)) {
48 case BlockType::kUncompressed:
49 bw->WriteBoundaryBits(skipped_bits);
50 TEST_AND_RETURN_FALSE(pr->GetNext(&pd));
51 TEST_AND_RETURN_FALSE(pd.type != PuffData::Type::kLiteral);
52
53 if (pd.type == PuffData::Type::kLiterals) {
54 TEST_AND_RETURN_FALSE(bw->WriteBits(16, pd.length));
55 TEST_AND_RETURN_FALSE(bw->WriteBits(16, ~pd.length));
56 TEST_AND_RETURN_FALSE(bw->WriteBytes(pd.length, pd.read_fn));
57 // Reading end of block, but don't write anything.
58 TEST_AND_RETURN_FALSE(pr->GetNext(&pd));
59 TEST_AND_RETURN_FALSE(pd.type == PuffData::Type::kEndOfBlock);
60 } else if (pd.type == PuffData::Type::kEndOfBlock) {
61 TEST_AND_RETURN_FALSE(bw->WriteBits(16, 0));
62 TEST_AND_RETURN_FALSE(bw->WriteBits(16, ~0));
63 } else {
64 LOG(ERROR) << "Uncompressed block did not end properly!";
65 return false;
66 }
67 // We have to read a new block.
68 continue;
69
70 case BlockType::kFixed:
71 fix_ht_->BuildFixedHuffmanTable();
72 cur_ht = fix_ht_.get();
73 break;
74
75 case BlockType::kDynamic:
76 cur_ht = dyn_ht_.get();
77 TEST_AND_RETURN_FALSE(dyn_ht_->BuildDynamicHuffmanTable(
78 &pd.block_metadata[1], pd.length - 1, bw));
79 break;
80
81 default:
82 LOG(ERROR) << "Invalid block compression type: "
83 << static_cast<int>(type);
84 return false;
85 }
86
87 // We read literal or distrance/lengths until and end of block or end of
88 // stream is reached.
89 bool block_ended = false;
90 while (!block_ended) {
91 TEST_AND_RETURN_FALSE(pr->GetNext(&pd));
92 switch (pd.type) {
93 case PuffData::Type::kLiteral:
94 case PuffData::Type::kLiterals: {
95 auto write_literal = [&cur_ht, &bw](uint8_t literal) {
96 uint16_t literal_huffman;
97 size_t nbits;
98 TEST_AND_RETURN_FALSE(
99 cur_ht->LitLenHuffman(literal, &literal_huffman, &nbits));
100 TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, literal_huffman));
101 return true;
102 };
103
104 if (pd.type == PuffData::Type::kLiteral) {
105 TEST_AND_RETURN_FALSE(write_literal(pd.byte));
106 } else {
107 auto len = pd.length;
108 while (len-- > 0) {
109 uint8_t literal;
110 pd.read_fn(&literal, 1);
111 TEST_AND_RETURN_FALSE(write_literal(literal));
112 }
113 }
114 break;
115 }
116 case PuffData::Type::kLenDist: {
117 auto len = pd.length;
118 auto dist = pd.distance;
119 TEST_AND_RETURN_FALSE(len >= 3 && len <= 258);
120
121 // Using a binary search here instead of the linear search may be (but
122 // not necessarily) faster. Needs experiment to validate.
123 size_t index = 0;
124 while (len > kLengthBases[index]) {
125 index++;
126 }
127 if (len < kLengthBases[index]) {
128 index--;
129 }
130 auto extra_bits_len = kLengthExtraBits[index];
131 uint16_t length_huffman;
132 size_t nbits;
133 TEST_AND_RETURN_FALSE(
134 cur_ht->LitLenHuffman(index + 257, &length_huffman, &nbits));
135
136 TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, length_huffman));
137
138 if (extra_bits_len > 0) {
139 TEST_AND_RETURN_FALSE(
140 bw->WriteBits(extra_bits_len, len - kLengthBases[index]));
141 }
142
143 // Same as above (binary search).
144 index = 0;
145 while (dist > kDistanceBases[index]) {
146 index++;
147 }
148 if (dist < kDistanceBases[index]) {
149 index--;
150 }
151 extra_bits_len = kDistanceExtraBits[index];
152 uint16_t distance_huffman;
153 TEST_AND_RETURN_FALSE(
154 cur_ht->DistanceHuffman(index, &distance_huffman, &nbits));
155
156 TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, distance_huffman));
157 if (extra_bits_len > 0) {
158 TEST_AND_RETURN_FALSE(
159 bw->WriteBits(extra_bits_len, dist - kDistanceBases[index]));
160 }
161 break;
162 }
163
164 case PuffData::Type::kEndOfBlock: {
165 uint16_t eos_huffman;
166 size_t nbits;
167 TEST_AND_RETURN_FALSE(
168 cur_ht->LitLenHuffman(256, &eos_huffman, &nbits));
169 TEST_AND_RETURN_FALSE(bw->WriteBits(nbits, eos_huffman));
170 block_ended = true;
171 break;
172 }
173 case PuffData::Type::kBlockMetadata:
174 LOG(ERROR) << "Not expecing a metadata!";
175 return false;
176
177 default:
178 LOG(ERROR) << "Invalid block data type!";
179 return false;
180 }
181 }
182 }
183
184 TEST_AND_RETURN_FALSE(bw->Flush());
185 return true;
186 }
187
188 } // namespace puffin
189