puffer.cc 7.9 KB

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