| OLD | NEW |
|---|
| (Empty) |
| 1 /* Copyright 2013 Google Inc. All Rights Reserved. | |
| 2 | |
| 3 Distributed under MIT license. | |
| 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT | |
| 5 */ | |
| 6 | |
| 7 // Implementation of Brotli compressor. | |
| 8 | |
| 9 #include "./encode.h" | |
| 10 | |
| 11 #include <algorithm> | |
| 12 #include <cstdlib> /* free, malloc */ | |
| 13 #include <cstring> /* memset */ | |
| 14 #include <limits> | |
| 15 | |
| 16 #include "./backward_references.h" | |
| 17 #include "./bit_cost.h" | |
| 18 #include "./block_splitter.h" | |
| 19 #include "./brotli_bit_stream.h" | |
| 20 #include "./cluster.h" | |
| 21 #include "./context.h" | |
| 22 #include "./metablock.h" | |
| 23 #include "./transform.h" | |
| 24 #include "./compress_fragment.h" | |
| 25 #include "./compress_fragment_two_pass.h" | |
| 26 #include "./entropy_encode.h" | |
| 27 #include "./fast_log.h" | |
| 28 #include "./hash.h" | |
| 29 #include "./histogram.h" | |
| 30 #include "./prefix.h" | |
| 31 #include "./utf8_util.h" | |
| 32 #include "./write_bits.h" | |
| 33 | |
| 34 namespace brotli { | |
| 35 | |
| 36 static const int kMinQualityForBlockSplit = 4; | |
| 37 static const int kMinQualityForContextModeling = 5; | |
| 38 static const int kMinQualityForOptimizeHistograms = 4; | |
| 39 // For quality 2 there is no block splitting, so we buffer at most this much | |
| 40 // literals and commands. | |
| 41 static const size_t kMaxNumDelayedSymbols = 0x2fff; | |
| 42 | |
| 43 #define COPY_ARRAY(dst, src) memcpy(dst, src, sizeof(src)); | |
| 44 | |
| 45 static void RecomputeDistancePrefixes(Command* cmds, | |
| 46 size_t num_commands, | |
| 47 uint32_t num_direct_distance_codes, | |
| 48 uint32_t distance_postfix_bits) { | |
| 49 if (num_direct_distance_codes == 0 && distance_postfix_bits == 0) { | |
| 50 return; | |
| 51 } | |
| 52 for (size_t i = 0; i < num_commands; ++i) { | |
| 53 Command* cmd = &cmds[i]; | |
| 54 if (cmd->copy_len() && cmd->cmd_prefix_ >= 128) { | |
| 55 PrefixEncodeCopyDistance(cmd->DistanceCode(), | |
| 56 num_direct_distance_codes, | |
| 57 distance_postfix_bits, | |
| 58 &cmd->dist_prefix_, | |
| 59 &cmd->dist_extra_); | |
| 60 } | |
| 61 } | |
| 62 } | |
| 63 | |
| 64 /* Wraps 64-bit input position to 32-bit ringbuffer position preserving | |
| 65 "not-a-first-lap" feature. */ | |
| 66 static uint32_t WrapPosition(uint64_t position) { | |
| 67 uint32_t result = static_cast<uint32_t>(position); | |
| 68 if (position > (1u << 30)) { | |
| 69 result = (result & ((1u << 30) - 1)) | (1u << 30); | |
| 70 } | |
| 71 return result; | |
| 72 } | |
| 73 | |
| 74 uint8_t* BrotliCompressor::GetBrotliStorage(size_t size) { | |
| 75 if (storage_size_ < size) { | |
| 76 delete[] storage_; | |
| 77 storage_ = new uint8_t[size]; | |
| 78 storage_size_ = size; | |
| 79 } | |
| 80 return storage_; | |
| 81 } | |
| 82 | |
| 83 static size_t MaxHashTableSize(int quality) { | |
| 84 return quality == 0 ? 1 << 15 : 1 << 17; | |
| 85 } | |
| 86 | |
| 87 static size_t HashTableSize(size_t max_table_size, size_t input_size) { | |
| 88 size_t htsize = 256; | |
| 89 while (htsize < max_table_size && htsize < input_size) { | |
| 90 htsize <<= 1; | |
| 91 } | |
| 92 return htsize; | |
| 93 } | |
| 94 | |
| 95 int* BrotliCompressor::GetHashTable(int quality, | |
| 96 size_t input_size, | |
| 97 size_t* table_size) { | |
| 98 // Use smaller hash table when input.size() is smaller, since we | |
| 99 // fill the table, incurring O(hash table size) overhead for | |
| 100 // compression, and if the input is short, we won't need that | |
| 101 // many hash table entries anyway. | |
| 102 const size_t max_table_size = MaxHashTableSize(quality); | |
| 103 assert(max_table_size >= 256); | |
| 104 size_t htsize = HashTableSize(max_table_size, input_size); | |
| 105 | |
| 106 int* table; | |
| 107 if (htsize <= sizeof(small_table_) / sizeof(small_table_[0])) { | |
| 108 table = small_table_; | |
| 109 } else { | |
| 110 if (large_table_ == NULL) { | |
| 111 large_table_ = new int[max_table_size]; | |
| 112 } | |
| 113 table = large_table_; | |
| 114 } | |
| 115 | |
| 116 *table_size = htsize; | |
| 117 memset(table, 0, htsize * sizeof(*table)); | |
| 118 return table; | |
| 119 } | |
| 120 | |
| 121 static void EncodeWindowBits(int lgwin, uint8_t* last_byte, | |
| 122 uint8_t* last_byte_bits) { | |
| 123 if (lgwin == 16) { | |
| 124 *last_byte = 0; | |
| 125 *last_byte_bits = 1; | |
| 126 } else if (lgwin == 17) { | |
| 127 *last_byte = 1; | |
| 128 *last_byte_bits = 7; | |
| 129 } else if (lgwin > 17) { | |
| 130 *last_byte = static_cast<uint8_t>(((lgwin - 17) << 1) | 1); | |
| 131 *last_byte_bits = 4; | |
| 132 } else { | |
| 133 *last_byte = static_cast<uint8_t>(((lgwin - 8) << 4) | 1); | |
| 134 *last_byte_bits = 7; | |
| 135 } | |
| 136 } | |
| 137 | |
| 138 // Initializes the command and distance prefix codes for the first block. | |
| 139 static void InitCommandPrefixCodes(uint8_t cmd_depths[128], | |
| 140 uint16_t cmd_bits[128], | |
| 141 uint8_t cmd_code[512], | |
| 142 size_t* cmd_code_numbits) { | |
| 143 static const uint8_t kDefaultCommandDepths[128] = { | |
| 144 0, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, | |
| 145 0, 0, 0, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, | |
| 146 7, 7, 10, 10, 10, 10, 10, 10, 0, 4, 4, 5, 5, 5, 6, 6, | |
| 147 7, 8, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, | |
| 148 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 149 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, | |
| 150 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 8, 10, | |
| 151 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, | |
| 152 }; | |
| 153 static const uint16_t kDefaultCommandBits[128] = { | |
| 154 0, 0, 8, 9, 3, 35, 7, 71, | |
| 155 39, 103, 23, 47, 175, 111, 239, 31, | |
| 156 0, 0, 0, 4, 12, 2, 10, 6, | |
| 157 13, 29, 11, 43, 27, 59, 87, 55, | |
| 158 15, 79, 319, 831, 191, 703, 447, 959, | |
| 159 0, 14, 1, 25, 5, 21, 19, 51, | |
| 160 119, 159, 95, 223, 479, 991, 63, 575, | |
| 161 127, 639, 383, 895, 255, 767, 511, 1023, | |
| 162 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 163 27, 59, 7, 39, 23, 55, 30, 1, 17, 9, 25, 5, 0, 8, 4, 12, | |
| 164 2, 10, 6, 21, 13, 29, 3, 19, 11, 15, 47, 31, 95, 63, 127, 255, | |
| 165 767, 2815, 1791, 3839, 511, 2559, 1535, 3583, 1023, 3071, 2047, 4095, | |
| 166 }; | |
| 167 COPY_ARRAY(cmd_depths, kDefaultCommandDepths); | |
| 168 COPY_ARRAY(cmd_bits, kDefaultCommandBits); | |
| 169 | |
| 170 // Initialize the pre-compressed form of the command and distance prefix | |
| 171 // codes. | |
| 172 static const uint8_t kDefaultCommandCode[] = { | |
| 173 0xff, 0x77, 0xd5, 0xbf, 0xe7, 0xde, 0xea, 0x9e, 0x51, 0x5d, 0xde, 0xc6, | |
| 174 0x70, 0x57, 0xbc, 0x58, 0x58, 0x58, 0xd8, 0xd8, 0x58, 0xd5, 0xcb, 0x8c, | |
| 175 0xea, 0xe0, 0xc3, 0x87, 0x1f, 0x83, 0xc1, 0x60, 0x1c, 0x67, 0xb2, 0xaa, | |
| 176 0x06, 0x83, 0xc1, 0x60, 0x30, 0x18, 0xcc, 0xa1, 0xce, 0x88, 0x54, 0x94, | |
| 177 0x46, 0xe1, 0xb0, 0xd0, 0x4e, 0xb2, 0xf7, 0x04, 0x00, | |
| 178 }; | |
| 179 static const int kDefaultCommandCodeNumBits = 448; | |
| 180 COPY_ARRAY(cmd_code, kDefaultCommandCode); | |
| 181 *cmd_code_numbits = kDefaultCommandCodeNumBits; | |
| 182 } | |
| 183 | |
| 184 // Decide about the context map based on the ability of the prediction | |
| 185 // ability of the previous byte UTF8-prefix on the next byte. The | |
| 186 // prediction ability is calculated as shannon entropy. Here we need | |
| 187 // shannon entropy instead of 'BitsEntropy' since the prefix will be | |
| 188 // encoded with the remaining 6 bits of the following byte, and | |
| 189 // BitsEntropy will assume that symbol to be stored alone using Huffman | |
| 190 // coding. | |
| 191 static void ChooseContextMap(int quality, | |
| 192 uint32_t* bigram_histo, | |
| 193 size_t* num_literal_contexts, | |
| 194 const uint32_t** literal_context_map) { | |
| 195 uint32_t monogram_histo[3] = { 0 }; | |
| 196 uint32_t two_prefix_histo[6] = { 0 }; | |
| 197 size_t total = 0; | |
| 198 for (size_t i = 0; i < 9; ++i) { | |
| 199 total += bigram_histo[i]; | |
| 200 monogram_histo[i % 3] += bigram_histo[i]; | |
| 201 size_t j = i; | |
| 202 if (j >= 6) { | |
| 203 j -= 6; | |
| 204 } | |
| 205 two_prefix_histo[j] += bigram_histo[i]; | |
| 206 } | |
| 207 size_t dummy; | |
| 208 double entropy1 = ShannonEntropy(monogram_histo, 3, &dummy); | |
| 209 double entropy2 = (ShannonEntropy(two_prefix_histo, 3, &dummy) + | |
| 210 ShannonEntropy(two_prefix_histo + 3, 3, &dummy)); | |
| 211 double entropy3 = 0; | |
| 212 for (size_t k = 0; k < 3; ++k) { | |
| 213 entropy3 += ShannonEntropy(bigram_histo + 3 * k, 3, &dummy); | |
| 214 } | |
| 215 | |
| 216 assert(total != 0); | |
| 217 double scale = 1.0 / static_cast<double>(total); | |
| 218 entropy1 *= scale; | |
| 219 entropy2 *= scale; | |
| 220 entropy3 *= scale; | |
| 221 | |
| 222 static const uint32_t kStaticContextMapContinuation[64] = { | |
| 223 1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 224 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 225 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 226 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 227 }; | |
| 228 static const uint32_t kStaticContextMapSimpleUTF8[64] = { | |
| 229 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 230 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 231 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 232 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
| 233 }; | |
| 234 if (quality < 7) { | |
| 235 // 3 context models is a bit slower, don't use it at lower qualities. | |
| 236 entropy3 = entropy1 * 10; | |
| 237 } | |
| 238 // If expected savings by symbol are less than 0.2 bits, skip the | |
| 239 // context modeling -- in exchange for faster decoding speed. | |
| 240 if (entropy1 - entropy2 < 0.2 && | |
| 241 entropy1 - entropy3 < 0.2) { | |
| 242 *num_literal_contexts = 1; | |
| 243 } else if (entropy2 - entropy3 < 0.02) { | |
| 244 *num_literal_contexts = 2; | |
| 245 *literal_context_map = kStaticContextMapSimpleUTF8; | |
| 246 } else { | |
| 247 *num_literal_contexts = 3; | |
| 248 *literal_context_map = kStaticContextMapContinuation; | |
| 249 } | |
| 250 } | |
| 251 | |
| 252 static void DecideOverLiteralContextModeling( | |
| 253 const uint8_t* input, | |
| 254 size_t start_pos, | |
| 255 size_t length, | |
| 256 size_t mask, | |
| 257 int quality, | |
| 258 ContextType* literal_context_mode, | |
| 259 size_t* num_literal_contexts, | |
| 260 const uint32_t** literal_context_map) { | |
| 261 if (quality < kMinQualityForContextModeling || length < 64) { | |
| 262 return; | |
| 263 } | |
| 264 // Gather bigram data of the UTF8 byte prefixes. To make the analysis of | |
| 265 // UTF8 data faster we only examine 64 byte long strides at every 4kB | |
| 266 // intervals. | |
| 267 const size_t end_pos = start_pos + length; | |
| 268 uint32_t bigram_prefix_histo[9] = { 0 }; | |
| 269 for (; start_pos + 64 <= end_pos; start_pos += 4096) { | |
| 270 static const int lut[4] = { 0, 0, 1, 2 }; | |
| 271 const size_t stride_end_pos = start_pos + 64; | |
| 272 int prev = lut[input[start_pos & mask] >> 6] * 3; | |
| 273 for (size_t pos = start_pos + 1; pos < stride_end_pos; ++pos) { | |
| 274 const uint8_t literal = input[pos & mask]; | |
| 275 ++bigram_prefix_histo[prev + lut[literal >> 6]]; | |
| 276 prev = lut[literal >> 6] * 3; | |
| 277 } | |
| 278 } | |
| 279 *literal_context_mode = CONTEXT_UTF8; | |
| 280 ChooseContextMap(quality, &bigram_prefix_histo[0], num_literal_contexts, | |
| 281 literal_context_map); | |
| 282 } | |
| 283 | |
| 284 static bool ShouldCompress(const uint8_t* data, | |
| 285 const size_t mask, | |
| 286 const uint64_t last_flush_pos, | |
| 287 const size_t bytes, | |
| 288 const size_t num_literals, | |
| 289 const size_t num_commands) { | |
| 290 if (num_commands < (bytes >> 8) + 2) { | |
| 291 if (num_literals > 0.99 * static_cast<double>(bytes)) { | |
| 292 uint32_t literal_histo[256] = { 0 }; | |
| 293 static const uint32_t kSampleRate = 13; | |
| 294 static const double kMinEntropy = 7.92; | |
| 295 const double bit_cost_threshold = | |
| 296 static_cast<double>(bytes) * kMinEntropy / kSampleRate; | |
| 297 size_t t = (bytes + kSampleRate - 1) / kSampleRate; | |
| 298 uint32_t pos = static_cast<uint32_t>(last_flush_pos); | |
| 299 for (size_t i = 0; i < t; i++) { | |
| 300 ++literal_histo[data[pos & mask]]; | |
| 301 pos += kSampleRate; | |
| 302 } | |
| 303 if (BitsEntropy(literal_histo, 256) > bit_cost_threshold) { | |
| 304 return false; | |
| 305 } | |
| 306 } | |
| 307 } | |
| 308 return true; | |
| 309 } | |
| 310 | |
| 311 static void WriteMetaBlockInternal(const uint8_t* data, | |
| 312 const size_t mask, | |
| 313 const uint64_t last_flush_pos, | |
| 314 const size_t bytes, | |
| 315 const bool is_last, | |
| 316 const int quality, | |
| 317 const bool font_mode, | |
| 318 const uint8_t prev_byte, | |
| 319 const uint8_t prev_byte2, | |
| 320 const size_t num_literals, | |
| 321 const size_t num_commands, | |
| 322 Command* commands, | |
| 323 const int* saved_dist_cache, | |
| 324 int* dist_cache, | |
| 325 size_t* storage_ix, | |
| 326 uint8_t* storage) { | |
| 327 if (bytes == 0) { | |
| 328 // Write the ISLAST and ISEMPTY bits. | |
| 329 WriteBits(2, 3, storage_ix, storage); | |
| 330 *storage_ix = (*storage_ix + 7u) & ~7u; | |
| 331 return; | |
| 332 } | |
| 333 | |
| 334 if (!ShouldCompress(data, mask, last_flush_pos, bytes, | |
| 335 num_literals, num_commands)) { | |
| 336 // Restore the distance cache, as its last update by | |
| 337 // CreateBackwardReferences is now unused. | |
| 338 memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | |
| 339 StoreUncompressedMetaBlock(is_last, data, | |
| 340 WrapPosition(last_flush_pos), mask, bytes, | |
| 341 storage_ix, storage); | |
| 342 return; | |
| 343 } | |
| 344 | |
| 345 const uint8_t last_byte = storage[0]; | |
| 346 const uint8_t last_byte_bits = static_cast<uint8_t>(*storage_ix & 0xff); | |
| 347 uint32_t num_direct_distance_codes = 0; | |
| 348 uint32_t distance_postfix_bits = 0; | |
| 349 if (quality > 9 && font_mode) { | |
| 350 num_direct_distance_codes = 12; | |
| 351 distance_postfix_bits = 1; | |
| 352 RecomputeDistancePrefixes(commands, | |
| 353 num_commands, | |
| 354 num_direct_distance_codes, | |
| 355 distance_postfix_bits); | |
| 356 } | |
| 357 if (quality == 2) { | |
| 358 StoreMetaBlockFast(data, WrapPosition(last_flush_pos), | |
| 359 bytes, mask, is_last, | |
| 360 commands, num_commands, | |
| 361 storage_ix, storage); | |
| 362 } else if (quality < kMinQualityForBlockSplit) { | |
| 363 StoreMetaBlockTrivial(data, WrapPosition(last_flush_pos), | |
| 364 bytes, mask, is_last, | |
| 365 commands, num_commands, | |
| 366 storage_ix, storage); | |
| 367 } else { | |
| 368 MetaBlockSplit mb; | |
| 369 ContextType literal_context_mode = CONTEXT_UTF8; | |
| 370 if (quality <= 9) { | |
| 371 size_t num_literal_contexts = 1; | |
| 372 const uint32_t* literal_context_map = NULL; | |
| 373 DecideOverLiteralContextModeling(data, WrapPosition(last_flush_pos), | |
| 374 bytes, mask, | |
| 375 quality, | |
| 376 &literal_context_mode, | |
| 377 &num_literal_contexts, | |
| 378 &literal_context_map); | |
| 379 if (literal_context_map == NULL) { | |
| 380 BuildMetaBlockGreedy(data, WrapPosition(last_flush_pos), mask, | |
| 381 commands, num_commands, &mb); | |
| 382 } else { | |
| 383 BuildMetaBlockGreedyWithContexts(data, WrapPosition(last_flush_pos), | |
| 384 mask, | |
| 385 prev_byte, prev_byte2, | |
| 386 literal_context_mode, | |
| 387 num_literal_contexts, | |
| 388 literal_context_map, | |
| 389 commands, num_commands, | |
| 390 &mb); | |
| 391 } | |
| 392 } else { | |
| 393 if (!IsMostlyUTF8(data, WrapPosition(last_flush_pos), mask, bytes, | |
| 394 kMinUTF8Ratio)) { | |
| 395 literal_context_mode = CONTEXT_SIGNED; | |
| 396 } | |
| 397 BuildMetaBlock(data, WrapPosition(last_flush_pos), mask, | |
| 398 prev_byte, prev_byte2, | |
| 399 commands, num_commands, | |
| 400 literal_context_mode, | |
| 401 &mb); | |
| 402 } | |
| 403 if (quality >= kMinQualityForOptimizeHistograms) { | |
| 404 OptimizeHistograms(num_direct_distance_codes, | |
| 405 distance_postfix_bits, | |
| 406 &mb); | |
| 407 } | |
| 408 StoreMetaBlock(data, WrapPosition(last_flush_pos), bytes, mask, | |
| 409 prev_byte, prev_byte2, | |
| 410 is_last, | |
| 411 num_direct_distance_codes, | |
| 412 distance_postfix_bits, | |
| 413 literal_context_mode, | |
| 414 commands, num_commands, | |
| 415 mb, | |
| 416 storage_ix, storage); | |
| 417 } | |
| 418 if (bytes + 4 < (*storage_ix >> 3)) { | |
| 419 // Restore the distance cache and last byte. | |
| 420 memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | |
| 421 storage[0] = last_byte; | |
| 422 *storage_ix = last_byte_bits; | |
| 423 StoreUncompressedMetaBlock(is_last, data, | |
| 424 WrapPosition(last_flush_pos), mask, | |
| 425 bytes, storage_ix, storage); | |
| 426 } | |
| 427 } | |
| 428 | |
| 429 BrotliCompressor::BrotliCompressor(BrotliParams params) | |
| 430 : params_(params), | |
| 431 hashers_(new Hashers()), | |
| 432 input_pos_(0), | |
| 433 num_commands_(0), | |
| 434 num_literals_(0), | |
| 435 last_insert_len_(0), | |
| 436 last_flush_pos_(0), | |
| 437 last_processed_pos_(0), | |
| 438 prev_byte_(0), | |
| 439 prev_byte2_(0), | |
| 440 storage_size_(0), | |
| 441 storage_(0), | |
| 442 large_table_(NULL), | |
| 443 cmd_code_numbits_(0), | |
| 444 command_buf_(NULL), | |
| 445 literal_buf_(NULL), | |
| 446 is_last_block_emitted_(0) { | |
| 447 // Sanitize params. | |
| 448 params_.quality = std::max(0, params_.quality); | |
| 449 if (params_.lgwin < kMinWindowBits) { | |
| 450 params_.lgwin = kMinWindowBits; | |
| 451 } else if (params_.lgwin > kMaxWindowBits) { | |
| 452 params_.lgwin = kMaxWindowBits; | |
| 453 } | |
| 454 if (params_.quality <= 1) { | |
| 455 params_.lgblock = params_.lgwin; | |
| 456 } else if (params_.quality < kMinQualityForBlockSplit) { | |
| 457 params_.lgblock = 14; | |
| 458 } else if (params_.lgblock == 0) { | |
| 459 params_.lgblock = 16; | |
| 460 if (params_.quality >= 9 && params_.lgwin > params_.lgblock) { | |
| 461 params_.lgblock = std::min(18, params_.lgwin); | |
| 462 } | |
| 463 } else { | |
| 464 params_.lgblock = std::min(kMaxInputBlockBits, | |
| 465 std::max(kMinInputBlockBits, params_.lgblock)); | |
| 466 } | |
| 467 | |
| 468 // Initialize input and literal cost ring buffers. | |
| 469 // We allocate at least lgwin + 1 bits for the ring buffer so that the newly | |
| 470 // added block fits there completely and we still get lgwin bits and at least | |
| 471 // read_block_size_bits + 1 bits because the copy tail length needs to be | |
| 472 // smaller than ringbuffer size. | |
| 473 int ringbuffer_bits = std::max(params_.lgwin + 1, params_.lgblock + 1); | |
| 474 ringbuffer_ = new RingBuffer(ringbuffer_bits, params_.lgblock); | |
| 475 | |
| 476 commands_ = 0; | |
| 477 cmd_alloc_size_ = 0; | |
| 478 | |
| 479 // Initialize last byte with stream header. | |
| 480 EncodeWindowBits(params_.lgwin, &last_byte_, &last_byte_bits_); | |
| 481 | |
| 482 // Initialize distance cache. | |
| 483 dist_cache_[0] = 4; | |
| 484 dist_cache_[1] = 11; | |
| 485 dist_cache_[2] = 15; | |
| 486 dist_cache_[3] = 16; | |
| 487 // Save the state of the distance cache in case we need to restore it for | |
| 488 // emitting an uncompressed block. | |
| 489 memcpy(saved_dist_cache_, dist_cache_, sizeof(dist_cache_)); | |
| 490 | |
| 491 if (params_.quality == 0) { | |
| 492 InitCommandPrefixCodes(cmd_depths_, cmd_bits_, | |
| 493 cmd_code_, &cmd_code_numbits_); | |
| 494 } else if (params_.quality == 1) { | |
| 495 command_buf_ = new uint32_t[kCompressFragmentTwoPassBlockSize]; | |
| 496 literal_buf_ = new uint8_t[kCompressFragmentTwoPassBlockSize]; | |
| 497 } | |
| 498 | |
| 499 // Initialize hashers. | |
| 500 hash_type_ = std::min(10, params_.quality); | |
| 501 hashers_->Init(hash_type_); | |
| 502 } | |
| 503 | |
| 504 BrotliCompressor::~BrotliCompressor(void) { | |
| 505 delete[] storage_; | |
| 506 free(commands_); | |
| 507 delete ringbuffer_; | |
| 508 delete hashers_; | |
| 509 delete[] large_table_; | |
| 510 delete[] command_buf_; | |
| 511 delete[] literal_buf_; | |
| 512 } | |
| 513 | |
| 514 void BrotliCompressor::CopyInputToRingBuffer(const size_t input_size, | |
| 515 const uint8_t* input_buffer) { | |
| 516 ringbuffer_->Write(input_buffer, input_size); | |
| 517 input_pos_ += input_size; | |
| 518 | |
| 519 // TL;DR: If needed, initialize 7 more bytes in the ring buffer to make the | |
| 520 // hashing not depend on uninitialized data. This makes compression | |
| 521 // deterministic and it prevents uninitialized memory warnings in Valgrind. | |
| 522 // Even without erasing, the output would be valid (but nondeterministic). | |
| 523 // | |
| 524 // Background information: The compressor stores short (at most 8 bytes) | |
| 525 // substrings of the input already read in a hash table, and detects | |
| 526 // repetitions by looking up such substrings in the hash table. If it | |
| 527 // can find a substring, it checks whether the substring is really there | |
| 528 // in the ring buffer (or it's just a hash collision). Should the hash | |
| 529 // table become corrupt, this check makes sure that the output is | |
| 530 // still valid, albeit the compression ratio would be bad. | |
| 531 // | |
| 532 // The compressor populates the hash table from the ring buffer as it's | |
| 533 // reading new bytes from the input. However, at the last few indexes of | |
| 534 // the ring buffer, there are not enough bytes to build full-length | |
| 535 // substrings from. Since the hash table always contains full-length | |
| 536 // substrings, we erase with dummy 0s here to make sure that those | |
| 537 // substrings will contain 0s at the end instead of uninitialized | |
| 538 // data. | |
| 539 // | |
| 540 // Please note that erasing is not necessary (because the | |
| 541 // memory region is already initialized since he ring buffer | |
| 542 // has a `tail' that holds a copy of the beginning,) so we | |
| 543 // skip erasing if we have already gone around at least once in | |
| 544 // the ring buffer. | |
| 545 size_t pos = ringbuffer_->position(); | |
| 546 // Only clear during the first round of ringbuffer writes. On | |
| 547 // subsequent rounds data in the ringbuffer would be affected. | |
| 548 if (pos <= ringbuffer_->mask()) { | |
| 549 // This is the first time when the ring buffer is being written. | |
| 550 // We clear 7 bytes just after the bytes that have been copied from | |
| 551 // the input buffer. | |
| 552 // | |
| 553 // The ringbuffer has a "tail" that holds a copy of the beginning, | |
| 554 // but only once the ring buffer has been fully written once, i.e., | |
| 555 // pos <= mask. For the first time, we need to write values | |
| 556 // in this tail (where index may be larger than mask), so that | |
| 557 // we have exactly defined behavior and don't read un-initialized | |
| 558 // memory. Due to performance reasons, hashing reads data using a | |
| 559 // LOAD64, which can go 7 bytes beyond the bytes written in the | |
| 560 // ringbuffer. | |
| 561 memset(ringbuffer_->start() + pos, 0, 7); | |
| 562 } | |
| 563 } | |
| 564 | |
| 565 void BrotliCompressor::BrotliSetCustomDictionary( | |
| 566 const size_t size, const uint8_t* dict) { | |
| 567 CopyInputToRingBuffer(size, dict); | |
| 568 last_flush_pos_ = size; | |
| 569 last_processed_pos_ = size; | |
| 570 if (size > 0) { | |
| 571 prev_byte_ = dict[size - 1]; | |
| 572 } | |
| 573 if (size > 1) { | |
| 574 prev_byte2_ = dict[size - 2]; | |
| 575 } | |
| 576 hashers_->PrependCustomDictionary(hash_type_, params_.lgwin, size, dict); | |
| 577 } | |
| 578 | |
| 579 bool BrotliCompressor::WriteBrotliData(const bool is_last, | |
| 580 const bool force_flush, | |
| 581 size_t* out_size, | |
| 582 uint8_t** output) { | |
| 583 const uint64_t delta = input_pos_ - last_processed_pos_; | |
| 584 const uint8_t* data = ringbuffer_->start(); | |
| 585 const uint32_t mask = ringbuffer_->mask(); | |
| 586 | |
| 587 /* Adding more blocks after "last" block is forbidden. */ | |
| 588 if (is_last_block_emitted_) return false; | |
| 589 if (is_last) is_last_block_emitted_ = 1; | |
| 590 | |
| 591 if (delta > input_block_size()) { | |
| 592 return false; | |
| 593 } | |
| 594 const uint32_t bytes = static_cast<uint32_t>(delta); | |
| 595 | |
| 596 if (params_.quality <= 1) { | |
| 597 if (delta == 0 && !is_last) { | |
| 598 // We have no new input data and we don't have to finish the stream, so | |
| 599 // nothing to do. | |
| 600 *out_size = 0; | |
| 601 return true; | |
| 602 } | |
| 603 const size_t max_out_size = 2 * bytes + 500; | |
| 604 uint8_t* storage = GetBrotliStorage(max_out_size); | |
| 605 storage[0] = last_byte_; | |
| 606 size_t storage_ix = last_byte_bits_; | |
| 607 size_t table_size; | |
| 608 int* table = GetHashTable(params_.quality, bytes, &table_size); | |
| 609 if (params_.quality == 0) { | |
| 610 BrotliCompressFragmentFast( | |
| 611 &data[WrapPosition(last_processed_pos_) & mask], | |
| 612 bytes, is_last, | |
| 613 table, table_size, | |
| 614 cmd_depths_, cmd_bits_, | |
| 615 &cmd_code_numbits_, cmd_code_, | |
| 616 &storage_ix, storage); | |
| 617 } else { | |
| 618 BrotliCompressFragmentTwoPass( | |
| 619 &data[WrapPosition(last_processed_pos_) & mask], | |
| 620 bytes, is_last, | |
| 621 command_buf_, literal_buf_, | |
| 622 table, table_size, | |
| 623 &storage_ix, storage); | |
| 624 } | |
| 625 last_byte_ = storage[storage_ix >> 3]; | |
| 626 last_byte_bits_ = storage_ix & 7u; | |
| 627 last_processed_pos_ = input_pos_; | |
| 628 *output = &storage[0]; | |
| 629 *out_size = storage_ix >> 3; | |
| 630 return true; | |
| 631 } | |
| 632 | |
| 633 // Theoretical max number of commands is 1 per 2 bytes. | |
| 634 size_t newsize = num_commands_ + bytes / 2 + 1; | |
| 635 if (newsize > cmd_alloc_size_) { | |
| 636 // Reserve a bit more memory to allow merging with a next block | |
| 637 // without realloc: that would impact speed. | |
| 638 newsize += (bytes / 4) + 16; | |
| 639 cmd_alloc_size_ = newsize; | |
| 640 commands_ = | |
| 641 static_cast<Command*>(realloc(commands_, sizeof(Command) * newsize)); | |
| 642 } | |
| 643 | |
| 644 CreateBackwardReferences(bytes, WrapPosition(last_processed_pos_), | |
| 645 is_last, data, mask, | |
| 646 params_.quality, | |
| 647 params_.lgwin, | |
| 648 hashers_, | |
| 649 hash_type_, | |
| 650 dist_cache_, | |
| 651 &last_insert_len_, | |
| 652 &commands_[num_commands_], | |
| 653 &num_commands_, | |
| 654 &num_literals_); | |
| 655 | |
| 656 size_t max_length = std::min<size_t>(mask + 1, 1u << kMaxInputBlockBits); | |
| 657 const size_t max_literals = max_length / 8; | |
| 658 const size_t max_commands = max_length / 8; | |
| 659 if (!is_last && !force_flush && | |
| 660 (params_.quality >= kMinQualityForBlockSplit || | |
| 661 (num_literals_ + num_commands_ < kMaxNumDelayedSymbols)) && | |
| 662 num_literals_ < max_literals && | |
| 663 num_commands_ < max_commands && | |
| 664 input_pos_ + input_block_size() <= last_flush_pos_ + max_length) { | |
| 665 // Merge with next input block. Everything will happen later. | |
| 666 last_processed_pos_ = input_pos_; | |
| 667 *out_size = 0; | |
| 668 return true; | |
| 669 } | |
| 670 | |
| 671 // Create the last insert-only command. | |
| 672 if (last_insert_len_ > 0) { | |
| 673 brotli::Command cmd(last_insert_len_); | |
| 674 commands_[num_commands_++] = cmd; | |
| 675 num_literals_ += last_insert_len_; | |
| 676 last_insert_len_ = 0; | |
| 677 } | |
| 678 | |
| 679 if (!is_last && input_pos_ == last_flush_pos_) { | |
| 680 // We have no new input data and we don't have to finish the stream, so | |
| 681 // nothing to do. | |
| 682 *out_size = 0; | |
| 683 return true; | |
| 684 } | |
| 685 assert(input_pos_ >= last_flush_pos_); | |
| 686 assert(input_pos_ > last_flush_pos_ || is_last); | |
| 687 assert(input_pos_ - last_flush_pos_ <= 1u << 24); | |
| 688 const uint32_t metablock_size = | |
| 689 static_cast<uint32_t>(input_pos_ - last_flush_pos_); | |
| 690 const size_t max_out_size = 2 * metablock_size + 500; | |
| 691 uint8_t* storage = GetBrotliStorage(max_out_size); | |
| 692 storage[0] = last_byte_; | |
| 693 size_t storage_ix = last_byte_bits_; | |
| 694 bool font_mode = params_.mode == BrotliParams::MODE_FONT; | |
| 695 WriteMetaBlockInternal( | |
| 696 data, mask, last_flush_pos_, metablock_size, is_last, params_.quality, | |
| 697 font_mode, prev_byte_, prev_byte2_, num_literals_, num_commands_, | |
| 698 commands_, saved_dist_cache_, dist_cache_, &storage_ix, storage); | |
| 699 last_byte_ = storage[storage_ix >> 3]; | |
| 700 last_byte_bits_ = storage_ix & 7u; | |
| 701 last_flush_pos_ = input_pos_; | |
| 702 last_processed_pos_ = input_pos_; | |
| 703 if (last_flush_pos_ > 0) { | |
| 704 prev_byte_ = data[(static_cast<uint32_t>(last_flush_pos_) - 1) & mask]; | |
| 705 } | |
| 706 if (last_flush_pos_ > 1) { | |
| 707 prev_byte2_ = data[(static_cast<uint32_t>(last_flush_pos_) - 2) & mask]; | |
| 708 } | |
| 709 num_commands_ = 0; | |
| 710 num_literals_ = 0; | |
| 711 // Save the state of the distance cache in case we need to restore it for | |
| 712 // emitting an uncompressed block. | |
| 713 memcpy(saved_dist_cache_, dist_cache_, sizeof(dist_cache_)); | |
| 714 *output = &storage[0]; | |
| 715 *out_size = storage_ix >> 3; | |
| 716 return true; | |
| 717 } | |
| 718 | |
| 719 bool BrotliCompressor::WriteMetaBlock(const size_t input_size, | |
| 720 const uint8_t* input_buffer, | |
| 721 const bool is_last, | |
| 722 size_t* encoded_size, | |
| 723 uint8_t* encoded_buffer) { | |
| 724 CopyInputToRingBuffer(input_size, input_buffer); | |
| 725 size_t out_size = 0; | |
| 726 uint8_t* output; | |
| 727 if (!WriteBrotliData(is_last, /* force_flush = */ true, &out_size, &output) || | |
| 728 out_size > *encoded_size) { | |
| 729 return false; | |
| 730 } | |
| 731 if (out_size > 0) { | |
| 732 memcpy(encoded_buffer, output, out_size); | |
| 733 } | |
| 734 *encoded_size = out_size; | |
| 735 return true; | |
| 736 } | |
| 737 | |
| 738 bool BrotliCompressor::WriteMetadata(const size_t input_size, | |
| 739 const uint8_t* input_buffer, | |
| 740 const bool is_last, | |
| 741 size_t* encoded_size, | |
| 742 uint8_t* encoded_buffer) { | |
| 743 if (input_size > (1 << 24) || input_size + 6 > *encoded_size) { | |
| 744 return false; | |
| 745 } | |
| 746 uint64_t hdr_buffer_data[2]; | |
| 747 uint8_t* hdr_buffer = reinterpret_cast<uint8_t*>(&hdr_buffer_data[0]); | |
| 748 size_t storage_ix = last_byte_bits_; | |
| 749 hdr_buffer[0] = last_byte_; | |
| 750 WriteBits(1, 0, &storage_ix, hdr_buffer); | |
| 751 WriteBits(2, 3, &storage_ix, hdr_buffer); | |
| 752 WriteBits(1, 0, &storage_ix, hdr_buffer); | |
| 753 if (input_size == 0) { | |
| 754 WriteBits(2, 0, &storage_ix, hdr_buffer); | |
| 755 *encoded_size = (storage_ix + 7u) >> 3; | |
| 756 memcpy(encoded_buffer, hdr_buffer, *encoded_size); | |
| 757 } else { | |
| 758 uint32_t nbits = (input_size == 1) ? 0 : (Log2FloorNonZero( | |
| 759 static_cast<uint32_t>(input_size) - 1) + 1); | |
| 760 uint32_t nbytes = (nbits + 7) / 8; | |
| 761 WriteBits(2, nbytes, &storage_ix, hdr_buffer); | |
| 762 WriteBits(8 * nbytes, input_size - 1, &storage_ix, hdr_buffer); | |
| 763 size_t hdr_size = (storage_ix + 7u) >> 3; | |
| 764 memcpy(encoded_buffer, hdr_buffer, hdr_size); | |
| 765 memcpy(&encoded_buffer[hdr_size], input_buffer, input_size); | |
| 766 *encoded_size = hdr_size + input_size; | |
| 767 } | |
| 768 if (is_last) { | |
| 769 encoded_buffer[(*encoded_size)++] = 3; | |
| 770 } | |
| 771 last_byte_ = 0; | |
| 772 last_byte_bits_ = 0; | |
| 773 return true; | |
| 774 } | |
| 775 | |
| 776 bool BrotliCompressor::FinishStream( | |
| 777 size_t* encoded_size, uint8_t* encoded_buffer) { | |
| 778 return WriteMetaBlock(0, NULL, true, encoded_size, encoded_buffer); | |
| 779 } | |
| 780 | |
| 781 static int BrotliCompressBufferQuality10(int lgwin, | |
| 782 size_t input_size, | |
| 783 const uint8_t* input_buffer, | |
| 784 size_t* encoded_size, | |
| 785 uint8_t* encoded_buffer) { | |
| 786 const size_t mask = std::numeric_limits<size_t>::max() >> 1; | |
| 787 assert(input_size <= mask + 1); | |
| 788 const size_t max_backward_limit = (1 << lgwin) - 16; | |
| 789 int dist_cache[4] = { 4, 11, 15, 16 }; | |
| 790 int saved_dist_cache[4] = { 4, 11, 15, 16 }; | |
| 791 int ok = 1; | |
| 792 const size_t max_out_size = *encoded_size; | |
| 793 size_t total_out_size = 0; | |
| 794 uint8_t last_byte; | |
| 795 uint8_t last_byte_bits; | |
| 796 EncodeWindowBits(lgwin, &last_byte, &last_byte_bits); | |
| 797 | |
| 798 Hashers::H10* hasher = new Hashers::H10; | |
| 799 const size_t hasher_eff_size = std::min(input_size, max_backward_limit + 16); | |
| 800 hasher->Init(lgwin, 0, hasher_eff_size, true); | |
| 801 | |
| 802 const int lgblock = std::min(18, lgwin); | |
| 803 const int lgmetablock = std::min(24, lgwin + 1); | |
| 804 const size_t max_block_size = static_cast<size_t>(1) << lgblock; | |
| 805 const size_t max_metablock_size = static_cast<size_t>(1) << lgmetablock; | |
| 806 const size_t max_literals_per_metablock = max_metablock_size / 8; | |
| 807 const size_t max_commands_per_metablock = max_metablock_size / 8; | |
| 808 size_t metablock_start = 0; | |
| 809 uint8_t prev_byte = 0; | |
| 810 uint8_t prev_byte2 = 0; | |
| 811 while (ok && metablock_start < input_size) { | |
| 812 const size_t metablock_end = | |
| 813 std::min(input_size, metablock_start + max_metablock_size); | |
| 814 const size_t expected_num_commands = | |
| 815 (metablock_end - metablock_start) / 12 + 16; | |
| 816 Command* commands = 0; | |
| 817 size_t num_commands = 0; | |
| 818 size_t last_insert_len = 0; | |
| 819 size_t num_literals = 0; | |
| 820 size_t metablock_size = 0; | |
| 821 size_t cmd_alloc_size = 0; | |
| 822 | |
| 823 for (size_t block_start = metablock_start; block_start < metablock_end; ) { | |
| 824 size_t block_size = std::min(metablock_end - block_start, max_block_size); | |
| 825 ZopfliNode* nodes = new ZopfliNode[block_size + 1]; | |
| 826 std::vector<uint32_t> path; | |
| 827 hasher->StitchToPreviousBlock(block_size, block_start, | |
| 828 input_buffer, mask); | |
| 829 ZopfliComputeShortestPath(block_size, block_start, input_buffer, mask, | |
| 830 max_backward_limit, dist_cache, | |
| 831 hasher, nodes, &path); | |
| 832 // We allocate a command buffer in the first iteration of this loop that | |
| 833 // will be likely big enough for the whole metablock, so that for most | |
| 834 // inputs we will not have to reallocate in later iterations. We do the | |
| 835 // allocation here and not before the loop, because if the input is small, | |
| 836 // this will be allocated after the zopfli cost model is freed, so this | |
| 837 // will not increase peak memory usage. | |
| 838 // TODO: If the first allocation is too small, increase command | |
| 839 // buffer size exponentially. | |
| 840 size_t new_cmd_alloc_size = std::max(expected_num_commands, | |
| 841 num_commands + path.size() + 1); | |
| 842 if (cmd_alloc_size != new_cmd_alloc_size) { | |
| 843 cmd_alloc_size = new_cmd_alloc_size; | |
| 844 commands = static_cast<Command*>( | |
| 845 realloc(commands, cmd_alloc_size * sizeof(Command))); | |
| 846 } | |
| 847 ZopfliCreateCommands(block_size, block_start, max_backward_limit, path, | |
| 848 &nodes[0], dist_cache, &last_insert_len, | |
| 849 &commands[num_commands], &num_literals); | |
| 850 num_commands += path.size(); | |
| 851 block_start += block_size; | |
| 852 metablock_size += block_size; | |
| 853 delete[] nodes; | |
| 854 if (num_literals > max_literals_per_metablock || | |
| 855 num_commands > max_commands_per_metablock) { | |
| 856 break; | |
| 857 } | |
| 858 } | |
| 859 | |
| 860 if (last_insert_len > 0) { | |
| 861 Command cmd(last_insert_len); | |
| 862 commands[num_commands++] = cmd; | |
| 863 num_literals += last_insert_len; | |
| 864 } | |
| 865 | |
| 866 const bool is_last = (metablock_start + metablock_size == input_size); | |
| 867 uint8_t* storage = NULL; | |
| 868 size_t storage_ix = last_byte_bits; | |
| 869 | |
| 870 if (metablock_size == 0) { | |
| 871 // Write the ISLAST and ISEMPTY bits. | |
| 872 storage = new uint8_t[16]; | |
| 873 storage[0] = last_byte; | |
| 874 WriteBits(2, 3, &storage_ix, storage); | |
| 875 storage_ix = (storage_ix + 7u) & ~7u; | |
| 876 } else if (!ShouldCompress(input_buffer, mask, metablock_start, | |
| 877 metablock_size, num_literals, num_commands)) { | |
| 878 // Restore the distance cache, as its last update by | |
| 879 // CreateBackwardReferences is now unused. | |
| 880 memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | |
| 881 storage = new uint8_t[metablock_size + 16]; | |
| 882 storage[0] = last_byte; | |
| 883 StoreUncompressedMetaBlock(is_last, input_buffer, | |
| 884 metablock_start, mask, metablock_size, | |
| 885 &storage_ix, storage); | |
| 886 } else { | |
| 887 uint32_t num_direct_distance_codes = 0; | |
| 888 uint32_t distance_postfix_bits = 0; | |
| 889 MetaBlockSplit mb; | |
| 890 ContextType literal_context_mode = CONTEXT_UTF8; | |
| 891 if (!IsMostlyUTF8( | |
| 892 input_buffer, metablock_start, mask, metablock_size, | |
| 893 kMinUTF8Ratio)) { | |
| 894 literal_context_mode = CONTEXT_SIGNED; | |
| 895 } | |
| 896 BuildMetaBlock(input_buffer, metablock_start, mask, | |
| 897 prev_byte, prev_byte2, | |
| 898 commands, num_commands, | |
| 899 literal_context_mode, | |
| 900 &mb); | |
| 901 OptimizeHistograms(num_direct_distance_codes, | |
| 902 distance_postfix_bits, | |
| 903 &mb); | |
| 904 const size_t max_out_metablock_size = 2 * metablock_size + 500; | |
| 905 storage = new uint8_t[max_out_metablock_size]; | |
| 906 storage[0] = last_byte; | |
| 907 StoreMetaBlock(input_buffer, metablock_start, metablock_size, mask, | |
| 908 prev_byte, prev_byte2, | |
| 909 is_last, | |
| 910 num_direct_distance_codes, | |
| 911 distance_postfix_bits, | |
| 912 literal_context_mode, | |
| 913 commands, num_commands, | |
| 914 mb, | |
| 915 &storage_ix, storage); | |
| 916 if (metablock_size + 4 < (storage_ix >> 3)) { | |
| 917 // Restore the distance cache and last byte. | |
| 918 memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | |
| 919 storage[0] = last_byte; | |
| 920 storage_ix = last_byte_bits; | |
| 921 StoreUncompressedMetaBlock(is_last, input_buffer, | |
| 922 metablock_start, mask, | |
| 923 metablock_size, &storage_ix, storage); | |
| 924 } | |
| 925 } | |
| 926 last_byte = storage[storage_ix >> 3]; | |
| 927 last_byte_bits = storage_ix & 7u; | |
| 928 metablock_start += metablock_size; | |
| 929 prev_byte = input_buffer[metablock_start - 1]; | |
| 930 prev_byte2 = input_buffer[metablock_start - 2]; | |
| 931 // Save the state of the distance cache in case we need to restore it for | |
| 932 // emitting an uncompressed block. | |
| 933 memcpy(saved_dist_cache, dist_cache, 4 * sizeof(dist_cache[0])); | |
| 934 | |
| 935 const size_t out_size = storage_ix >> 3; | |
| 936 total_out_size += out_size; | |
| 937 if (total_out_size <= max_out_size) { | |
| 938 memcpy(encoded_buffer, storage, out_size); | |
| 939 encoded_buffer += out_size; | |
| 940 } else { | |
| 941 ok = 0; | |
| 942 } | |
| 943 delete[] storage; | |
| 944 free(commands); | |
| 945 } | |
| 946 | |
| 947 *encoded_size = total_out_size; | |
| 948 delete hasher; | |
| 949 return ok; | |
| 950 } | |
| 951 | |
| 952 int BrotliCompressBuffer(BrotliParams params, | |
| 953 size_t input_size, | |
| 954 const uint8_t* input_buffer, | |
| 955 size_t* encoded_size, | |
| 956 uint8_t* encoded_buffer) { | |
| 957 if (*encoded_size == 0) { | |
| 958 // Output buffer needs at least one byte. | |
| 959 return 0; | |
| 960 } | |
| 961 if (input_size == 0) { | |
| 962 // Handle the special case of empty input. | |
| 963 *encoded_size = 1; | |
| 964 *encoded_buffer = 6; | |
| 965 return 1; | |
| 966 } | |
| 967 if (params.quality == 10) { | |
| 968 // TODO: Implement this direct path for all quality levels. | |
| 969 const int lgwin = std::min(24, std::max(16, params.lgwin)); | |
| 970 return BrotliCompressBufferQuality10(lgwin, input_size, input_buffer, | |
| 971 encoded_size, encoded_buffer); | |
| 972 } | |
| 973 BrotliMemIn in(input_buffer, input_size); | |
| 974 BrotliMemOut out(encoded_buffer, *encoded_size); | |
| 975 if (!BrotliCompress(params, &in, &out)) { | |
| 976 return 0; | |
| 977 } | |
| 978 *encoded_size = out.position(); | |
| 979 return 1; | |
| 980 } | |
| 981 | |
| 982 static bool BrotliInIsFinished(BrotliIn* r) { | |
| 983 size_t read_bytes; | |
| 984 return r->Read(0, &read_bytes) == NULL; | |
| 985 } | |
| 986 | |
| 987 static const uint8_t* BrotliInReadAndCheckEnd(const size_t block_size, | |
| 988 BrotliIn* r, | |
| 989 size_t* bytes_read, | |
| 990 bool* is_last) { | |
| 991 *bytes_read = 0; | |
| 992 const uint8_t* data = reinterpret_cast<const uint8_t*>( | |
| 993 r->Read(block_size, bytes_read)); | |
| 994 assert((data == NULL) == (*bytes_read == 0)); | |
| 995 *is_last = BrotliInIsFinished(r); | |
| 996 return data; | |
| 997 } | |
| 998 | |
| 999 static bool CopyOneBlockToRingBuffer(BrotliIn* r, | |
| 1000 BrotliCompressor* compressor, | |
| 1001 size_t* bytes_read, | |
| 1002 bool* is_last) { | |
| 1003 const size_t block_size = compressor->input_block_size(); | |
| 1004 const uint8_t* data = BrotliInReadAndCheckEnd(block_size, r, | |
| 1005 bytes_read, is_last); | |
| 1006 if (data == NULL) { | |
| 1007 return *is_last; | |
| 1008 } | |
| 1009 compressor->CopyInputToRingBuffer(*bytes_read, data); | |
| 1010 | |
| 1011 // Read more bytes until block_size is filled or an EOF (data == NULL) is | |
| 1012 // received. This is useful to get deterministic compressed output for the | |
| 1013 // same input no matter how r->Read splits the input to chunks. | |
| 1014 for (size_t remaining = block_size - *bytes_read; remaining > 0; ) { | |
| 1015 size_t more_bytes_read = 0; | |
| 1016 data = BrotliInReadAndCheckEnd(remaining, r, &more_bytes_read, is_last); | |
| 1017 if (data == NULL) { | |
| 1018 return *is_last; | |
| 1019 } | |
| 1020 compressor->CopyInputToRingBuffer(more_bytes_read, data); | |
| 1021 *bytes_read += more_bytes_read; | |
| 1022 remaining -= more_bytes_read; | |
| 1023 } | |
| 1024 return true; | |
| 1025 } | |
| 1026 | |
| 1027 | |
| 1028 int BrotliCompress(BrotliParams params, BrotliIn* in, BrotliOut* out) { | |
| 1029 return BrotliCompressWithCustomDictionary(0, 0, params, in, out); | |
| 1030 } | |
| 1031 | |
| 1032 // Reads the provided input in 'block_size' blocks. Only the last read can be | |
| 1033 // smaller than 'block_size'. | |
| 1034 class BrotliBlockReader { | |
| 1035 public: | |
| 1036 explicit BrotliBlockReader(size_t block_size) | |
| 1037 : block_size_(block_size), buf_(NULL) {} | |
| 1038 ~BrotliBlockReader(void) { delete[] buf_; } | |
| 1039 | |
| 1040 const uint8_t* Read(BrotliIn* in, size_t* bytes_read, bool* is_last) { | |
| 1041 *bytes_read = 0; | |
| 1042 const uint8_t* data = BrotliInReadAndCheckEnd(block_size_, in, | |
| 1043 bytes_read, is_last); | |
| 1044 if (data == NULL || *bytes_read == block_size_ || *is_last) { | |
| 1045 // If we could get the whole block in one read, or it is the last block, | |
| 1046 // we just return the pointer to the data without copying. | |
| 1047 return data; | |
| 1048 } | |
| 1049 // If the data comes in smaller chunks, we need to copy it into an internal | |
| 1050 // buffer until we get a whole block or reach the last chunk. | |
| 1051 if (buf_ == NULL) { | |
| 1052 buf_ = new uint8_t[block_size_]; | |
| 1053 } | |
| 1054 memcpy(buf_, data, *bytes_read); | |
| 1055 do { | |
| 1056 size_t cur_bytes_read = 0; | |
| 1057 data = BrotliInReadAndCheckEnd(block_size_ - *bytes_read, in, | |
| 1058 &cur_bytes_read, is_last); | |
| 1059 if (data == NULL) { | |
| 1060 return *is_last ? buf_ : NULL; | |
| 1061 } | |
| 1062 memcpy(&buf_[*bytes_read], data, cur_bytes_read); | |
| 1063 *bytes_read += cur_bytes_read; | |
| 1064 } while (*bytes_read < block_size_ && !*is_last); | |
| 1065 return buf_; | |
| 1066 } | |
| 1067 | |
| 1068 private: | |
| 1069 const size_t block_size_; | |
| 1070 uint8_t* buf_; | |
| 1071 }; | |
| 1072 | |
| 1073 int BrotliCompressWithCustomDictionary(size_t dictsize, const uint8_t* dict, | |
| 1074 BrotliParams params, | |
| 1075 BrotliIn* in, BrotliOut* out) { | |
| 1076 if (params.quality <= 1) { | |
| 1077 const int quality = std::max(0, params.quality); | |
| 1078 const int lgwin = std::min(kMaxWindowBits, | |
| 1079 std::max(kMinWindowBits, params.lgwin)); | |
| 1080 uint8_t* storage = NULL; | |
| 1081 int* table = NULL; | |
| 1082 uint32_t* command_buf = NULL; | |
| 1083 uint8_t* literal_buf = NULL; | |
| 1084 uint8_t cmd_depths[128]; | |
| 1085 uint16_t cmd_bits[128]; | |
| 1086 uint8_t cmd_code[512]; | |
| 1087 size_t cmd_code_numbits; | |
| 1088 if (quality == 0) { | |
| 1089 InitCommandPrefixCodes(cmd_depths, cmd_bits, cmd_code, &cmd_code_numbits); | |
| 1090 } | |
| 1091 uint8_t last_byte; | |
| 1092 uint8_t last_byte_bits; | |
| 1093 EncodeWindowBits(lgwin, &last_byte, &last_byte_bits); | |
| 1094 BrotliBlockReader r(1u << lgwin); | |
| 1095 int ok = 1; | |
| 1096 bool is_last = false; | |
| 1097 while (ok && !is_last) { | |
| 1098 // Read next block of input. | |
| 1099 size_t bytes; | |
| 1100 const uint8_t* data = r.Read(in, &bytes, &is_last); | |
| 1101 if (data == NULL) { | |
| 1102 if (!is_last) { | |
| 1103 ok = 0; | |
| 1104 break; | |
| 1105 } | |
| 1106 assert(bytes == 0); | |
| 1107 } | |
| 1108 // Set up output storage. | |
| 1109 const size_t max_out_size = 2 * bytes + 500; | |
| 1110 if (storage == NULL) { | |
| 1111 storage = new uint8_t[max_out_size]; | |
| 1112 } | |
| 1113 storage[0] = last_byte; | |
| 1114 size_t storage_ix = last_byte_bits; | |
| 1115 // Set up hash table. | |
| 1116 size_t htsize = HashTableSize(MaxHashTableSize(quality), bytes); | |
| 1117 if (table == NULL) { | |
| 1118 table = new int[htsize]; | |
| 1119 } | |
| 1120 memset(table, 0, htsize * sizeof(table[0])); | |
| 1121 // Set up command and literal buffers for two pass mode. | |
| 1122 if (quality == 1 && command_buf == NULL) { | |
| 1123 size_t buf_size = std::min(bytes, kCompressFragmentTwoPassBlockSize); | |
| 1124 command_buf = new uint32_t[buf_size]; | |
| 1125 literal_buf = new uint8_t[buf_size]; | |
| 1126 } | |
| 1127 // Do the actual compression. | |
| 1128 if (quality == 0) { | |
| 1129 BrotliCompressFragmentFast(data, bytes, is_last, table, htsize, | |
| 1130 cmd_depths, cmd_bits, | |
| 1131 &cmd_code_numbits, cmd_code, | |
| 1132 &storage_ix, storage); | |
| 1133 } else { | |
| 1134 BrotliCompressFragmentTwoPass(data, bytes, is_last, | |
| 1135 command_buf, literal_buf, | |
| 1136 table, htsize, | |
| 1137 &storage_ix, storage); | |
| 1138 } | |
| 1139 // Save last bytes to stitch it together with the next output block. | |
| 1140 last_byte = storage[storage_ix >> 3]; | |
| 1141 last_byte_bits = storage_ix & 7u; | |
| 1142 // Write output block. | |
| 1143 size_t out_bytes = storage_ix >> 3; | |
| 1144 if (out_bytes > 0 && !out->Write(storage, out_bytes)) { | |
| 1145 ok = 0; | |
| 1146 break; | |
| 1147 } | |
| 1148 } | |
| 1149 delete[] storage; | |
| 1150 delete[] table; | |
| 1151 delete[] command_buf; | |
| 1152 delete[] literal_buf; | |
| 1153 return ok; | |
| 1154 } | |
| 1155 | |
| 1156 size_t in_bytes = 0; | |
| 1157 size_t out_bytes = 0; | |
| 1158 uint8_t* output = NULL; | |
| 1159 bool final_block = false; | |
| 1160 BrotliCompressor compressor(params); | |
| 1161 if (dictsize != 0) compressor.BrotliSetCustomDictionary(dictsize, dict); | |
| 1162 while (!final_block) { | |
| 1163 if (!CopyOneBlockToRingBuffer(in, &compressor, &in_bytes, &final_block)) { | |
| 1164 return false; | |
| 1165 } | |
| 1166 out_bytes = 0; | |
| 1167 if (!compressor.WriteBrotliData(final_block, | |
| 1168 /* force_flush = */ false, | |
| 1169 &out_bytes, &output)) { | |
| 1170 return false; | |
| 1171 } | |
| 1172 if (out_bytes > 0 && !out->Write(output, out_bytes)) { | |
| 1173 return false; | |
| 1174 } | |
| 1175 } | |
| 1176 return true; | |
| 1177 } | |
| 1178 | |
| 1179 | |
| 1180 } // namespace brotli | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2537133002:
Update brotli to v1.0.0-snapshot. (Closed)
