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 26 Puffer::Puffer() : dyn_ht_(new HuffmanTable()), fix_ht_(new HuffmanTable()) {} 27 28 Puffer::~Puffer() {} 29 30 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
