| OLD | NEW |
|---|
| (Empty) |
| 1 /* Copyright 2013 Google Inc. All Rights Reserved. | |
| 2 | |
| 3 Licensed under the Apache License, Version 2.0 (the "License"); | |
| 4 you may not use this file except in compliance with the License. | |
| 5 You may obtain a copy of the License at | |
| 6 | |
| 7 http://www.apache.org/licenses/LICENSE-2.0 | |
| 8 | |
| 9 Unless required by applicable law or agreed to in writing, software | |
| 10 distributed under the License is distributed on an "AS IS" BASIS, | |
| 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| 12 See the License for the specific language governing permissions and | |
| 13 limitations under the License. | |
| 14 */ | |
| 15 | |
| 16 #include <stdlib.h> | |
| 17 #include <stdio.h> | |
| 18 #include <string.h> | |
| 19 #include "./bit_reader.h" | |
| 20 #include "./context.h" | |
| 21 #include "./decode.h" | |
| 22 #include "./dictionary.h" | |
| 23 #include "./transform.h" | |
| 24 #include "./huffman.h" | |
| 25 #include "./prefix.h" | |
| 26 #include "./safe_malloc.h" | |
| 27 | |
| 28 #if defined(__cplusplus) || defined(c_plusplus) | |
| 29 extern "C" { | |
| 30 #endif | |
| 31 | |
| 32 #ifdef BROTLI_DECODE_DEBUG | |
| 33 #define BROTLI_LOG_UINT(name) \ | |
| 34 printf("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)) | |
| 35 #define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \ | |
| 36 printf("[%s] %s[%lu] = %lu\n", __func__, #array_name, \ | |
| 37 (unsigned long)(idx), (unsigned long)array_name[idx]) | |
| 38 #else | |
| 39 #define BROTLI_LOG_UINT(name) | |
| 40 #define BROTLI_LOG_ARRAY_INDEX(array_name, idx) | |
| 41 #endif | |
| 42 | |
| 43 static const uint8_t kDefaultCodeLength = 8; | |
| 44 static const uint8_t kCodeLengthRepeatCode = 16; | |
| 45 static const int kNumLiteralCodes = 256; | |
| 46 static const int kNumInsertAndCopyCodes = 704; | |
| 47 static const int kNumBlockLengthCodes = 26; | |
| 48 static const int kLiteralContextBits = 6; | |
| 49 static const int kDistanceContextBits = 2; | |
| 50 | |
| 51 #define HUFFMAN_TABLE_BITS 8 | |
| 52 #define HUFFMAN_TABLE_MASK 0xff | |
| 53 /* Maximum possible Huffman table size for an alphabet size of 704, max code | |
| 54 * length 15 and root table bits 8. */ | |
| 55 #define HUFFMAN_MAX_TABLE_SIZE 1080 | |
| 56 | |
| 57 #define CODE_LENGTH_CODES 18 | |
| 58 static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = { | |
| 59 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, | |
| 60 }; | |
| 61 | |
| 62 #define NUM_DISTANCE_SHORT_CODES 16 | |
| 63 static const int kDistanceShortCodeIndexOffset[NUM_DISTANCE_SHORT_CODES] = { | |
| 64 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 | |
| 65 }; | |
| 66 | |
| 67 static const int kDistanceShortCodeValueOffset[NUM_DISTANCE_SHORT_CODES] = { | |
| 68 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 | |
| 69 }; | |
| 70 | |
| 71 static BROTLI_INLINE int DecodeWindowBits(BrotliBitReader* br) { | |
| 72 if (BrotliReadBits(br, 1)) { | |
| 73 return 17 + (int)BrotliReadBits(br, 3); | |
| 74 } else { | |
| 75 return 16; | |
| 76 } | |
| 77 } | |
| 78 | |
| 79 /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */ | |
| 80 static BROTLI_INLINE int DecodeVarLenUint8(BrotliBitReader* br) { | |
| 81 if (BrotliReadBits(br, 1)) { | |
| 82 int nbits = (int)BrotliReadBits(br, 3); | |
| 83 if (nbits == 0) { | |
| 84 return 1; | |
| 85 } else { | |
| 86 return (int)BrotliReadBits(br, nbits) + (1 << nbits); | |
| 87 } | |
| 88 } | |
| 89 return 0; | |
| 90 } | |
| 91 | |
| 92 static void DecodeMetaBlockLength(BrotliBitReader* br, | |
| 93 int* meta_block_length, | |
| 94 int* input_end, | |
| 95 int* is_uncompressed) { | |
| 96 int size_nibbles; | |
| 97 int i; | |
| 98 *input_end = (int)BrotliReadBits(br, 1); | |
| 99 *meta_block_length = 0; | |
| 100 *is_uncompressed = 0; | |
| 101 if (*input_end && BrotliReadBits(br, 1)) { | |
| 102 return; | |
| 103 } | |
| 104 size_nibbles = (int)BrotliReadBits(br, 2) + 4; | |
| 105 for (i = 0; i < size_nibbles; ++i) { | |
| 106 *meta_block_length |= (int)BrotliReadBits(br, 4) << (i * 4); | |
| 107 } | |
| 108 ++(*meta_block_length); | |
| 109 if (!*input_end) { | |
| 110 *is_uncompressed = (int)BrotliReadBits(br, 1); | |
| 111 } | |
| 112 } | |
| 113 | |
| 114 /* Decodes the next Huffman code from bit-stream. */ | |
| 115 static BROTLI_INLINE int ReadSymbol(const HuffmanCode* table, | |
| 116 BrotliBitReader* br) { | |
| 117 int nbits; | |
| 118 BrotliFillBitWindow(br); | |
| 119 table += (int)(br->val_ >> br->bit_pos_) & HUFFMAN_TABLE_MASK; | |
| 120 nbits = table->bits - HUFFMAN_TABLE_BITS; | |
| 121 if (nbits > 0) { | |
| 122 br->bit_pos_ += HUFFMAN_TABLE_BITS; | |
| 123 table += table->value; | |
| 124 table += (int)(br->val_ >> br->bit_pos_) & ((1 << nbits) - 1); | |
| 125 } | |
| 126 br->bit_pos_ += table->bits; | |
| 127 return table->value; | |
| 128 } | |
| 129 | |
| 130 static void PrintUcharVector(const uint8_t* v, int len) { | |
| 131 while (len-- > 0) printf(" %d", *v++); | |
| 132 printf("\n"); | |
| 133 } | |
| 134 | |
| 135 static int ReadHuffmanCodeLengths( | |
| 136 const uint8_t* code_length_code_lengths, | |
| 137 int num_symbols, uint8_t* code_lengths, | |
| 138 BrotliBitReader* br) { | |
| 139 int symbol = 0; | |
| 140 uint8_t prev_code_len = kDefaultCodeLength; | |
| 141 int repeat = 0; | |
| 142 uint8_t repeat_code_len = 0; | |
| 143 int space = 32768; | |
| 144 HuffmanCode table[32]; | |
| 145 | |
| 146 if (!BrotliBuildHuffmanTable(table, 5, | |
| 147 code_length_code_lengths, | |
| 148 CODE_LENGTH_CODES)) { | |
| 149 printf("[ReadHuffmanCodeLengths] Building code length tree failed: "); | |
| 150 PrintUcharVector(code_length_code_lengths, CODE_LENGTH_CODES); | |
| 151 return 0; | |
| 152 } | |
| 153 | |
| 154 while (symbol < num_symbols && space > 0) { | |
| 155 const HuffmanCode* p = table; | |
| 156 uint8_t code_len; | |
| 157 if (!BrotliReadMoreInput(br)) { | |
| 158 printf("[ReadHuffmanCodeLengths] Unexpected end of input.\n"); | |
| 159 return 0; | |
| 160 } | |
| 161 BrotliFillBitWindow(br); | |
| 162 p += (br->val_ >> br->bit_pos_) & 31; | |
| 163 br->bit_pos_ += p->bits; | |
| 164 code_len = (uint8_t)p->value; | |
| 165 if (code_len < kCodeLengthRepeatCode) { | |
| 166 repeat = 0; | |
| 167 code_lengths[symbol++] = code_len; | |
| 168 if (code_len != 0) { | |
| 169 prev_code_len = code_len; | |
| 170 space -= 32768 >> code_len; | |
| 171 } | |
| 172 } else { | |
| 173 const int extra_bits = code_len - 14; | |
| 174 int old_repeat; | |
| 175 int repeat_delta; | |
| 176 uint8_t new_len = 0; | |
| 177 if (code_len == kCodeLengthRepeatCode) { | |
| 178 new_len = prev_code_len; | |
| 179 } | |
| 180 if (repeat_code_len != new_len) { | |
| 181 repeat = 0; | |
| 182 repeat_code_len = new_len; | |
| 183 } | |
| 184 old_repeat = repeat; | |
| 185 if (repeat > 0) { | |
| 186 repeat -= 2; | |
| 187 repeat <<= extra_bits; | |
| 188 } | |
| 189 repeat += (int)BrotliReadBits(br, extra_bits) + 3; | |
| 190 repeat_delta = repeat - old_repeat; | |
| 191 if (symbol + repeat_delta > num_symbols) { | |
| 192 return 0; | |
| 193 } | |
| 194 memset(&code_lengths[symbol], repeat_code_len, (size_t)repeat_delta); | |
| 195 symbol += repeat_delta; | |
| 196 if (repeat_code_len != 0) { | |
| 197 space -= repeat_delta << (15 - repeat_code_len); | |
| 198 } | |
| 199 } | |
| 200 } | |
| 201 if (space != 0) { | |
| 202 printf("[ReadHuffmanCodeLengths] space = %d\n", space); | |
| 203 return 0; | |
| 204 } | |
| 205 memset(&code_lengths[symbol], 0, (size_t)(num_symbols - symbol)); | |
| 206 return 1; | |
| 207 } | |
| 208 | |
| 209 static int ReadHuffmanCode(int alphabet_size, | |
| 210 HuffmanCode* table, | |
| 211 BrotliBitReader* br) { | |
| 212 int ok = 1; | |
| 213 int table_size = 0; | |
| 214 int simple_code_or_skip; | |
| 215 uint8_t* code_lengths = NULL; | |
| 216 | |
| 217 code_lengths = | |
| 218 (uint8_t*)BrotliSafeMalloc((uint64_t)alphabet_size, | |
| 219 sizeof(*code_lengths)); | |
| 220 if (code_lengths == NULL) { | |
| 221 return 0; | |
| 222 } | |
| 223 if (!BrotliReadMoreInput(br)) { | |
| 224 printf("[ReadHuffmanCode] Unexpected end of input.\n"); | |
| 225 return 0; | |
| 226 } | |
| 227 /* simple_code_or_skip is used as follows: | |
| 228 1 for simple code; | |
| 229 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ | |
| 230 simple_code_or_skip = (int)BrotliReadBits(br, 2); | |
| 231 BROTLI_LOG_UINT(simple_code_or_skip); | |
| 232 if (simple_code_or_skip == 1) { | |
| 233 /* Read symbols, codes & code lengths directly. */ | |
| 234 int i; | |
| 235 int max_bits_counter = alphabet_size - 1; | |
| 236 int max_bits = 0; | |
| 237 int symbols[4] = { 0 }; | |
| 238 const int num_symbols = (int)BrotliReadBits(br, 2) + 1; | |
| 239 while (max_bits_counter) { | |
| 240 max_bits_counter >>= 1; | |
| 241 ++max_bits; | |
| 242 } | |
| 243 memset(code_lengths, 0, (size_t)alphabet_size); | |
| 244 for (i = 0; i < num_symbols; ++i) { | |
| 245 symbols[i] = (int)BrotliReadBits(br, max_bits) % alphabet_size; | |
| 246 code_lengths[symbols[i]] = 2; | |
| 247 } | |
| 248 code_lengths[symbols[0]] = 1; | |
| 249 switch (num_symbols) { | |
| 250 case 1: | |
| 251 break; | |
| 252 case 3: | |
| 253 ok = ((symbols[0] != symbols[1]) && | |
| 254 (symbols[0] != symbols[2]) && | |
| 255 (symbols[1] != symbols[2])); | |
| 256 break; | |
| 257 case 2: | |
| 258 ok = (symbols[0] != symbols[1]); | |
| 259 code_lengths[symbols[1]] = 1; | |
| 260 break; | |
| 261 case 4: | |
| 262 ok = ((symbols[0] != symbols[1]) && | |
| 263 (symbols[0] != symbols[2]) && | |
| 264 (symbols[0] != symbols[3]) && | |
| 265 (symbols[1] != symbols[2]) && | |
| 266 (symbols[1] != symbols[3]) && | |
| 267 (symbols[2] != symbols[3])); | |
| 268 if (BrotliReadBits(br, 1)) { | |
| 269 code_lengths[symbols[2]] = 3; | |
| 270 code_lengths[symbols[3]] = 3; | |
| 271 } else { | |
| 272 code_lengths[symbols[0]] = 2; | |
| 273 } | |
| 274 break; | |
| 275 } | |
| 276 BROTLI_LOG_UINT(num_symbols); | |
| 277 } else { /* Decode Huffman-coded code lengths. */ | |
| 278 int i; | |
| 279 uint8_t code_length_code_lengths[CODE_LENGTH_CODES] = { 0 }; | |
| 280 int space = 32; | |
| 281 int num_codes = 0; | |
| 282 /* Static Huffman code for the code length code lengths */ | |
| 283 static const HuffmanCode huff[16] = { | |
| 284 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 1}, | |
| 285 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 5}, | |
| 286 }; | |
| 287 for (i = simple_code_or_skip; i < CODE_LENGTH_CODES && space > 0; ++i) { | |
| 288 const int code_len_idx = kCodeLengthCodeOrder[i]; | |
| 289 const HuffmanCode* p = huff; | |
| 290 uint8_t v; | |
| 291 BrotliFillBitWindow(br); | |
| 292 p += (br->val_ >> br->bit_pos_) & 15; | |
| 293 br->bit_pos_ += p->bits; | |
| 294 v = (uint8_t)p->value; | |
| 295 code_length_code_lengths[code_len_idx] = v; | |
| 296 BROTLI_LOG_ARRAY_INDEX(code_length_code_lengths, code_len_idx); | |
| 297 if (v != 0) { | |
| 298 space -= (32 >> v); | |
| 299 ++num_codes; | |
| 300 } | |
| 301 } | |
| 302 ok = (num_codes == 1 || space == 0) && | |
| 303 ReadHuffmanCodeLengths(code_length_code_lengths, | |
| 304 alphabet_size, code_lengths, br); | |
| 305 } | |
| 306 if (ok) { | |
| 307 table_size = BrotliBuildHuffmanTable(table, HUFFMAN_TABLE_BITS, | |
| 308 code_lengths, alphabet_size); | |
| 309 if (table_size == 0) { | |
| 310 printf("[ReadHuffmanCode] BuildHuffmanTable failed: "); | |
| 311 PrintUcharVector(code_lengths, alphabet_size); | |
| 312 } | |
| 313 } | |
| 314 free(code_lengths); | |
| 315 return table_size; | |
| 316 } | |
| 317 | |
| 318 static BROTLI_INLINE int ReadBlockLength(const HuffmanCode* table, | |
| 319 BrotliBitReader* br) { | |
| 320 int code; | |
| 321 int nbits; | |
| 322 code = ReadSymbol(table, br); | |
| 323 nbits = kBlockLengthPrefixCode[code].nbits; | |
| 324 return kBlockLengthPrefixCode[code].offset + (int)BrotliReadBits(br, nbits); | |
| 325 } | |
| 326 | |
| 327 static int TranslateShortCodes(int code, int* ringbuffer, int index) { | |
| 328 int val; | |
| 329 if (code < NUM_DISTANCE_SHORT_CODES) { | |
| 330 index += kDistanceShortCodeIndexOffset[code]; | |
| 331 index &= 3; | |
| 332 val = ringbuffer[index] + kDistanceShortCodeValueOffset[code]; | |
| 333 } else { | |
| 334 val = code - NUM_DISTANCE_SHORT_CODES + 1; | |
| 335 } | |
| 336 return val; | |
| 337 } | |
| 338 | |
| 339 static void MoveToFront(uint8_t* v, uint8_t index) { | |
| 340 uint8_t value = v[index]; | |
| 341 uint8_t i = index; | |
| 342 for (; i; --i) v[i] = v[i - 1]; | |
| 343 v[0] = value; | |
| 344 } | |
| 345 | |
| 346 static void InverseMoveToFrontTransform(uint8_t* v, int v_len) { | |
| 347 uint8_t mtf[256]; | |
| 348 int i; | |
| 349 for (i = 0; i < 256; ++i) { | |
| 350 mtf[i] = (uint8_t)i; | |
| 351 } | |
| 352 for (i = 0; i < v_len; ++i) { | |
| 353 uint8_t index = v[i]; | |
| 354 v[i] = mtf[index]; | |
| 355 if (index) MoveToFront(mtf, index); | |
| 356 } | |
| 357 } | |
| 358 | |
| 359 /* Contains a collection of huffman trees with the same alphabet size. */ | |
| 360 typedef struct { | |
| 361 int alphabet_size; | |
| 362 int num_htrees; | |
| 363 HuffmanCode* codes; | |
| 364 HuffmanCode** htrees; | |
| 365 } HuffmanTreeGroup; | |
| 366 | |
| 367 static void HuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size, | |
| 368 int ntrees) { | |
| 369 group->alphabet_size = alphabet_size; | |
| 370 group->num_htrees = ntrees; | |
| 371 group->codes = (HuffmanCode*)malloc( | |
| 372 sizeof(HuffmanCode) * (size_t)(ntrees * HUFFMAN_MAX_TABLE_SIZE)); | |
| 373 group->htrees = (HuffmanCode**)malloc(sizeof(HuffmanCode*) * (size_t)ntrees); | |
| 374 } | |
| 375 | |
| 376 static void HuffmanTreeGroupRelease(HuffmanTreeGroup* group) { | |
| 377 if (group->codes) { | |
| 378 free(group->codes); | |
| 379 } | |
| 380 if (group->htrees) { | |
| 381 free(group->htrees); | |
| 382 } | |
| 383 } | |
| 384 | |
| 385 static int HuffmanTreeGroupDecode(HuffmanTreeGroup* group, | |
| 386 BrotliBitReader* br) { | |
| 387 int i; | |
| 388 int table_size; | |
| 389 HuffmanCode* next = group->codes; | |
| 390 for (i = 0; i < group->num_htrees; ++i) { | |
| 391 group->htrees[i] = next; | |
| 392 table_size = ReadHuffmanCode(group->alphabet_size, next, br); | |
| 393 next += table_size; | |
| 394 if (table_size == 0) { | |
| 395 return 0; | |
| 396 } | |
| 397 } | |
| 398 return 1; | |
| 399 } | |
| 400 | |
| 401 static int DecodeContextMap(int context_map_size, | |
| 402 int* num_htrees, | |
| 403 uint8_t** context_map, | |
| 404 BrotliBitReader* br) { | |
| 405 int ok = 1; | |
| 406 int use_rle_for_zeros; | |
| 407 int max_run_length_prefix = 0; | |
| 408 HuffmanCode* table; | |
| 409 int i; | |
| 410 if (!BrotliReadMoreInput(br)) { | |
| 411 printf("[DecodeContextMap] Unexpected end of input.\n"); | |
| 412 return 0; | |
| 413 } | |
| 414 *num_htrees = DecodeVarLenUint8(br) + 1; | |
| 415 | |
| 416 BROTLI_LOG_UINT(context_map_size); | |
| 417 BROTLI_LOG_UINT(*num_htrees); | |
| 418 | |
| 419 *context_map = (uint8_t*)malloc((size_t)context_map_size); | |
| 420 if (*context_map == 0) { | |
| 421 return 0; | |
| 422 } | |
| 423 if (*num_htrees <= 1) { | |
| 424 memset(*context_map, 0, (size_t)context_map_size); | |
| 425 return 1; | |
| 426 } | |
| 427 | |
| 428 use_rle_for_zeros = (int)BrotliReadBits(br, 1); | |
| 429 if (use_rle_for_zeros) { | |
| 430 max_run_length_prefix = (int)BrotliReadBits(br, 4) + 1; | |
| 431 } | |
| 432 table = (HuffmanCode*)malloc(HUFFMAN_MAX_TABLE_SIZE * sizeof(*table)); | |
| 433 if (table == NULL) { | |
| 434 return 0; | |
| 435 } | |
| 436 if (!ReadHuffmanCode(*num_htrees + max_run_length_prefix, table, br)) { | |
| 437 ok = 0; | |
| 438 goto End; | |
| 439 } | |
| 440 for (i = 0; i < context_map_size;) { | |
| 441 int code; | |
| 442 if (!BrotliReadMoreInput(br)) { | |
| 443 printf("[DecodeContextMap] Unexpected end of input.\n"); | |
| 444 ok = 0; | |
| 445 goto End; | |
| 446 } | |
| 447 code = ReadSymbol(table, br); | |
| 448 if (code == 0) { | |
| 449 (*context_map)[i] = 0; | |
| 450 ++i; | |
| 451 } else if (code <= max_run_length_prefix) { | |
| 452 int reps = 1 + (1 << code) + (int)BrotliReadBits(br, code); | |
| 453 while (--reps) { | |
| 454 if (i >= context_map_size) { | |
| 455 ok = 0; | |
| 456 goto End; | |
| 457 } | |
| 458 (*context_map)[i] = 0; | |
| 459 ++i; | |
| 460 } | |
| 461 } else { | |
| 462 (*context_map)[i] = (uint8_t)(code - max_run_length_prefix); | |
| 463 ++i; | |
| 464 } | |
| 465 } | |
| 466 if (BrotliReadBits(br, 1)) { | |
| 467 InverseMoveToFrontTransform(*context_map, context_map_size); | |
| 468 } | |
| 469 End: | |
| 470 free(table); | |
| 471 return ok; | |
| 472 } | |
| 473 | |
| 474 static BROTLI_INLINE void DecodeBlockType(const int max_block_type, | |
| 475 const HuffmanCode* trees, | |
| 476 int tree_type, | |
| 477 int* block_types, | |
| 478 int* ringbuffers, | |
| 479 int* indexes, | |
| 480 BrotliBitReader* br) { | |
| 481 int* ringbuffer = ringbuffers + tree_type * 2; | |
| 482 int* index = indexes + tree_type; | |
| 483 int type_code = ReadSymbol(&trees[tree_type * HUFFMAN_MAX_TABLE_SIZE], br); | |
| 484 int block_type; | |
| 485 if (type_code == 0) { | |
| 486 block_type = ringbuffer[*index & 1]; | |
| 487 } else if (type_code == 1) { | |
| 488 block_type = ringbuffer[(*index - 1) & 1] + 1; | |
| 489 } else { | |
| 490 block_type = type_code - 2; | |
| 491 } | |
| 492 if (block_type >= max_block_type) { | |
| 493 block_type -= max_block_type; | |
| 494 } | |
| 495 block_types[tree_type] = block_type; | |
| 496 ringbuffer[(*index) & 1] = block_type; | |
| 497 ++(*index); | |
| 498 } | |
| 499 | |
| 500 /* Copy len bytes from src to dst. It can write up to ten extra bytes | |
| 501 after the end of the copy. | |
| 502 | |
| 503 The main part of this loop is a simple copy of eight bytes at a time until | |
| 504 we've copied (at least) the requested amount of bytes. However, if dst and | |
| 505 src are less than eight bytes apart (indicating a repeating pattern of | |
| 506 length < 8), we first need to expand the pattern in order to get the correct | |
| 507 results. For instance, if the buffer looks like this, with the eight-byte | |
| 508 <src> and <dst> patterns marked as intervals: | |
| 509 | |
| 510 abxxxxxxxxxxxx | |
| 511 [------] src | |
| 512 [------] dst | |
| 513 | |
| 514 a single eight-byte copy from <src> to <dst> will repeat the pattern once, | |
| 515 after which we can move <dst> two bytes without moving <src>: | |
| 516 | |
| 517 ababxxxxxxxxxx | |
| 518 [------] src | |
| 519 [------] dst | |
| 520 | |
| 521 and repeat the exercise until the two no longer overlap. | |
| 522 | |
| 523 This allows us to do very well in the special case of one single byte | |
| 524 repeated many times, without taking a big hit for more general cases. | |
| 525 | |
| 526 The worst case of extra writing past the end of the match occurs when | |
| 527 dst - src == 1 and len == 1; the last copy will read from byte positions | |
| 528 [0..7] and write to [4..11], whereas it was only supposed to write to | |
| 529 position 1. Thus, ten excess bytes. | |
| 530 */ | |
| 531 static BROTLI_INLINE void IncrementalCopyFastPath( | |
| 532 uint8_t* dst, const uint8_t* src, int len) { | |
| 533 if (src < dst) { | |
| 534 while (dst - src < 8) { | |
| 535 UNALIGNED_MOVE64(dst, src); | |
| 536 len -= (int)(dst - src); | |
| 537 dst += dst - src; | |
| 538 } | |
| 539 } | |
| 540 while (len > 0) { | |
| 541 UNALIGNED_COPY64(dst, src); | |
| 542 src += 8; | |
| 543 dst += 8; | |
| 544 len -= 8; | |
| 545 } | |
| 546 } | |
| 547 | |
| 548 int CopyUncompressedBlockToOutput(BrotliOutput output, int len, int pos, | |
| 549 uint8_t* ringbuffer, int ringbuffer_mask, | |
| 550 BrotliBitReader* br) { | |
| 551 const int rb_size = ringbuffer_mask + 1; | |
| 552 uint8_t* ringbuffer_end = ringbuffer + rb_size; | |
| 553 int rb_pos = pos & ringbuffer_mask; | |
| 554 int br_pos = br->pos_ & BROTLI_IBUF_MASK; | |
| 555 int nbytes; | |
| 556 | |
| 557 /* For short lengths copy byte-by-byte */ | |
| 558 if (len < 8 || br->bit_pos_ + (uint32_t)(len << 3) < br->bit_end_pos_) { | |
| 559 while (len-- > 0) { | |
| 560 if (!BrotliReadMoreInput(br)) { | |
| 561 return 0; | |
| 562 } | |
| 563 ringbuffer[rb_pos++]= (uint8_t)BrotliReadBits(br, 8); | |
| 564 if (rb_pos == rb_size) { | |
| 565 if (BrotliWrite(output, ringbuffer, (size_t)rb_size) < rb_size) { | |
| 566 return 0; | |
| 567 } | |
| 568 rb_pos = 0; | |
| 569 } | |
| 570 } | |
| 571 return 1; | |
| 572 } | |
| 573 | |
| 574 if (br->bit_end_pos_ < 64) { | |
| 575 return 0; | |
| 576 } | |
| 577 | |
| 578 /* Copy remaining 0-8 bytes from br->val_ to ringbuffer. */ | |
| 579 while (br->bit_pos_ < 64) { | |
| 580 ringbuffer[rb_pos] = (uint8_t)(br->val_ >> br->bit_pos_); | |
| 581 br->bit_pos_ += 8; | |
| 582 ++rb_pos; | |
| 583 --len; | |
| 584 } | |
| 585 | |
| 586 /* Copy remaining bytes from br->buf_ to ringbuffer. */ | |
| 587 nbytes = (int)(br->bit_end_pos_ - br->bit_pos_) >> 3; | |
| 588 if (br_pos + nbytes > BROTLI_IBUF_MASK) { | |
| 589 int tail = BROTLI_IBUF_MASK + 1 - br_pos; | |
| 590 memcpy(&ringbuffer[rb_pos], &br->buf_[br_pos], (size_t)tail); | |
| 591 nbytes -= tail; | |
| 592 rb_pos += tail; | |
| 593 len -= tail; | |
| 594 br_pos = 0; | |
| 595 } | |
| 596 memcpy(&ringbuffer[rb_pos], &br->buf_[br_pos], (size_t)nbytes); | |
| 597 rb_pos += nbytes; | |
| 598 len -= nbytes; | |
| 599 | |
| 600 /* If we wrote past the logical end of the ringbuffer, copy the tail of the | |
| 601 ringbuffer to its beginning and flush the ringbuffer to the output. */ | |
| 602 if (rb_pos >= rb_size) { | |
| 603 if (BrotliWrite(output, ringbuffer, (size_t)rb_size) < rb_size) { | |
| 604 return 0; | |
| 605 } | |
| 606 rb_pos -= rb_size; | |
| 607 memcpy(ringbuffer, ringbuffer_end, (size_t)rb_pos); | |
| 608 } | |
| 609 | |
| 610 /* If we have more to copy than the remaining size of the ringbuffer, then we | |
| 611 first fill the ringbuffer from the input and then flush the ringbuffer to | |
| 612 the output */ | |
| 613 while (rb_pos + len >= rb_size) { | |
| 614 nbytes = rb_size - rb_pos; | |
| 615 if (BrotliRead(br->input_, &ringbuffer[rb_pos], (size_t)nbytes) < nbytes || | |
| 616 BrotliWrite(output, ringbuffer, (size_t)rb_size) < nbytes) { | |
| 617 return 0; | |
| 618 } | |
| 619 len -= nbytes; | |
| 620 rb_pos = 0; | |
| 621 } | |
| 622 | |
| 623 /* Copy straight from the input onto the ringbuffer. The ringbuffer will be | |
| 624 flushed to the output at a later time. */ | |
| 625 if (BrotliRead(br->input_, &ringbuffer[rb_pos], (size_t)len) < len) { | |
| 626 return 0; | |
| 627 } | |
| 628 | |
| 629 /* Restore the state of the bit reader. */ | |
| 630 BrotliInitBitReader(br, br->input_); | |
| 631 return 1; | |
| 632 } | |
| 633 | |
| 634 int BrotliDecompressedSize(size_t encoded_size, | |
| 635 const uint8_t* encoded_buffer, | |
| 636 size_t* decoded_size) { | |
| 637 int i; | |
| 638 uint64_t val = 0; | |
| 639 int bit_pos = 0; | |
| 640 int is_last; | |
| 641 int is_uncompressed = 0; | |
| 642 int size_nibbles; | |
| 643 int meta_block_len = 0; | |
| 644 if (encoded_size == 0) { | |
| 645 return 0; | |
| 646 } | |
| 647 /* Look at the first 8 bytes, it is enough to decode the length of the first | |
| 648 meta-block. */ | |
| 649 for (i = 0; (size_t)i < encoded_size && i < 8; ++i) { | |
| 650 val |= (uint64_t)encoded_buffer[i] << (8 * i); | |
| 651 } | |
| 652 /* Skip the window bits. */ | |
| 653 bit_pos += (val & 1) ? 4 : 1; | |
| 654 /* Decode the ISLAST bit. */ | |
| 655 is_last = (val >> bit_pos) & 1; | |
| 656 ++bit_pos; | |
| 657 if (is_last) { | |
| 658 /* Decode the ISEMPTY bit, if it is set to 1, we are done. */ | |
| 659 if ((val >> bit_pos) & 1) { | |
| 660 *decoded_size = 0; | |
| 661 return 1; | |
| 662 } | |
| 663 ++bit_pos; | |
| 664 } | |
| 665 /* Decode the length of the first meta-block. */ | |
| 666 size_nibbles = (int)((val >> bit_pos) & 3) + 4; | |
| 667 bit_pos += 2; | |
| 668 for (i = 0; i < size_nibbles; ++i) { | |
| 669 meta_block_len |= (int)((val >> bit_pos) & 0xf) << (4 * i); | |
| 670 bit_pos += 4; | |
| 671 } | |
| 672 ++meta_block_len; | |
| 673 if (is_last) { | |
| 674 /* If this meta-block is the only one, we are done. */ | |
| 675 *decoded_size = (size_t)meta_block_len; | |
| 676 return 1; | |
| 677 } | |
| 678 is_uncompressed = (val >> bit_pos) & 1; | |
| 679 ++bit_pos; | |
| 680 if (is_uncompressed) { | |
| 681 /* If the first meta-block is uncompressed, we skip it and look at the | |
| 682 first two bits (ISLAST and ISEMPTY) of the next meta-block, and if | |
| 683 both are set to 1, we have a stream with an uncompressed meta-block | |
| 684 followed by an empty one, so the decompressed size is the size of the | |
| 685 first meta-block. */ | |
| 686 size_t offset = ((bit_pos + 7) >> 3) + meta_block_len; | |
| 687 if (offset < encoded_size && ((encoded_buffer[offset] & 3) == 3)) { | |
| 688 *decoded_size = (size_t)meta_block_len; | |
| 689 return 1; | |
| 690 } | |
| 691 } | |
| 692 return 0; | |
| 693 } | |
| 694 | |
| 695 int BrotliDecompressBuffer(size_t encoded_size, | |
| 696 const uint8_t* encoded_buffer, | |
| 697 size_t* decoded_size, | |
| 698 uint8_t* decoded_buffer) { | |
| 699 BrotliMemInput memin; | |
| 700 BrotliInput in = BrotliInitMemInput(encoded_buffer, encoded_size, &memin); | |
| 701 BrotliMemOutput mout; | |
| 702 BrotliOutput out = BrotliInitMemOutput(decoded_buffer, *decoded_size, &mout); | |
| 703 int success = BrotliDecompress(in, out); | |
| 704 *decoded_size = mout.pos; | |
| 705 return success; | |
| 706 } | |
| 707 | |
| 708 int BrotliDecompress(BrotliInput input, BrotliOutput output) { | |
| 709 int ok = 1; | |
| 710 int i; | |
| 711 int pos = 0; | |
| 712 int input_end = 0; | |
| 713 int window_bits = 0; | |
| 714 int max_backward_distance; | |
| 715 int max_distance = 0; | |
| 716 int ringbuffer_size; | |
| 717 int ringbuffer_mask; | |
| 718 uint8_t* ringbuffer; | |
| 719 uint8_t* ringbuffer_end; | |
| 720 /* This ring buffer holds a few past copy distances that will be used by */ | |
| 721 /* some special distance codes. */ | |
| 722 int dist_rb[4] = { 16, 15, 11, 4 }; | |
| 723 int dist_rb_idx = 0; | |
| 724 /* The previous 2 bytes used for context. */ | |
| 725 uint8_t prev_byte1 = 0; | |
| 726 uint8_t prev_byte2 = 0; | |
| 727 HuffmanTreeGroup hgroup[3]; | |
| 728 HuffmanCode* block_type_trees = NULL; | |
| 729 HuffmanCode* block_len_trees = NULL; | |
| 730 BrotliBitReader br; | |
| 731 | |
| 732 /* We need the slack region for the following reasons: | |
| 733 - always doing two 8-byte copies for fast backward copying | |
| 734 - transforms | |
| 735 - flushing the input ringbuffer when decoding uncompressed blocks */ | |
| 736 static const int kRingBufferWriteAheadSlack = 128 + BROTLI_READ_SIZE; | |
| 737 | |
| 738 if (!BrotliInitBitReader(&br, input)) { | |
| 739 return 0; | |
| 740 } | |
| 741 | |
| 742 /* Decode window size. */ | |
| 743 window_bits = DecodeWindowBits(&br); | |
| 744 max_backward_distance = (1 << window_bits) - 16; | |
| 745 | |
| 746 ringbuffer_size = 1 << window_bits; | |
| 747 ringbuffer_mask = ringbuffer_size - 1; | |
| 748 ringbuffer = (uint8_t*)malloc((size_t)(ringbuffer_size + | |
| 749 kRingBufferWriteAheadSlack + | |
| 750 kMaxDictionaryWordLength)); | |
| 751 if (!ringbuffer) { | |
| 752 ok = 0; | |
| 753 } | |
| 754 ringbuffer_end = ringbuffer + ringbuffer_size; | |
| 755 | |
| 756 if (ok) { | |
| 757 block_type_trees = (HuffmanCode*)malloc( | |
| 758 3 * HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode)); | |
| 759 block_len_trees = (HuffmanCode*)malloc( | |
| 760 3 * HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode)); | |
| 761 if (block_type_trees == NULL || block_len_trees == NULL) { | |
| 762 ok = 0; | |
| 763 } | |
| 764 } | |
| 765 | |
| 766 while (!input_end && ok) { | |
| 767 int meta_block_remaining_len = 0; | |
| 768 int is_uncompressed; | |
| 769 int block_length[3] = { 1 << 28, 1 << 28, 1 << 28 }; | |
| 770 int block_type[3] = { 0 }; | |
| 771 int num_block_types[3] = { 1, 1, 1 }; | |
| 772 int block_type_rb[6] = { 0, 1, 0, 1, 0, 1 }; | |
| 773 int block_type_rb_index[3] = { 0 }; | |
| 774 int distance_postfix_bits; | |
| 775 int num_direct_distance_codes; | |
| 776 int distance_postfix_mask; | |
| 777 int num_distance_codes; | |
| 778 uint8_t* context_map = NULL; | |
| 779 uint8_t* context_modes = NULL; | |
| 780 int num_literal_htrees; | |
| 781 uint8_t* dist_context_map = NULL; | |
| 782 int num_dist_htrees; | |
| 783 int context_offset = 0; | |
| 784 uint8_t* context_map_slice = NULL; | |
| 785 uint8_t literal_htree_index = 0; | |
| 786 int dist_context_offset = 0; | |
| 787 uint8_t* dist_context_map_slice = NULL; | |
| 788 uint8_t dist_htree_index = 0; | |
| 789 int context_lookup_offset1 = 0; | |
| 790 int context_lookup_offset2 = 0; | |
| 791 uint8_t context_mode; | |
| 792 HuffmanCode* htree_command; | |
| 793 | |
| 794 for (i = 0; i < 3; ++i) { | |
| 795 hgroup[i].codes = NULL; | |
| 796 hgroup[i].htrees = NULL; | |
| 797 } | |
| 798 | |
| 799 if (!BrotliReadMoreInput(&br)) { | |
| 800 printf("[BrotliDecompress] Unexpected end of input.\n"); | |
| 801 ok = 0; | |
| 802 goto End; | |
| 803 } | |
| 804 BROTLI_LOG_UINT(pos); | |
| 805 DecodeMetaBlockLength(&br, &meta_block_remaining_len, | |
| 806 &input_end, &is_uncompressed); | |
| 807 BROTLI_LOG_UINT(meta_block_remaining_len); | |
| 808 if (meta_block_remaining_len == 0) { | |
| 809 goto End; | |
| 810 } | |
| 811 if (is_uncompressed) { | |
| 812 BrotliSetBitPos(&br, (br.bit_pos_ + 7) & (uint32_t)(~7UL)); | |
| 813 ok = CopyUncompressedBlockToOutput(output, meta_block_remaining_len, pos, | |
| 814 ringbuffer, ringbuffer_mask, &br); | |
| 815 pos += meta_block_remaining_len; | |
| 816 goto End; | |
| 817 } | |
| 818 for (i = 0; i < 3; ++i) { | |
| 819 num_block_types[i] = DecodeVarLenUint8(&br) + 1; | |
| 820 if (num_block_types[i] >= 2) { | |
| 821 if (!ReadHuffmanCode(num_block_types[i] + 2, | |
| 822 &block_type_trees[i * HUFFMAN_MAX_TABLE_SIZE], | |
| 823 &br) || | |
| 824 !ReadHuffmanCode(kNumBlockLengthCodes, | |
| 825 &block_len_trees[i * HUFFMAN_MAX_TABLE_SIZE], | |
| 826 &br)) { | |
| 827 ok = 0; | |
| 828 goto End; | |
| 829 } | |
| 830 block_length[i] = ReadBlockLength( | |
| 831 &block_len_trees[i * HUFFMAN_MAX_TABLE_SIZE], &br); | |
| 832 block_type_rb_index[i] = 1; | |
| 833 } | |
| 834 } | |
| 835 | |
| 836 BROTLI_LOG_UINT(num_block_types[0]); | |
| 837 BROTLI_LOG_UINT(num_block_types[1]); | |
| 838 BROTLI_LOG_UINT(num_block_types[2]); | |
| 839 BROTLI_LOG_UINT(block_length[0]); | |
| 840 BROTLI_LOG_UINT(block_length[1]); | |
| 841 BROTLI_LOG_UINT(block_length[2]); | |
| 842 | |
| 843 if (!BrotliReadMoreInput(&br)) { | |
| 844 printf("[BrotliDecompress] Unexpected end of input.\n"); | |
| 845 ok = 0; | |
| 846 goto End; | |
| 847 } | |
| 848 distance_postfix_bits = (int)BrotliReadBits(&br, 2); | |
| 849 num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES + | |
| 850 ((int)BrotliReadBits(&br, 4) << distance_postfix_bits); | |
| 851 distance_postfix_mask = (1 << distance_postfix_bits) - 1; | |
| 852 num_distance_codes = (num_direct_distance_codes + | |
| 853 (48 << distance_postfix_bits)); | |
| 854 context_modes = (uint8_t*)malloc((size_t)num_block_types[0]); | |
| 855 if (context_modes == 0) { | |
| 856 ok = 0; | |
| 857 goto End; | |
| 858 } | |
| 859 for (i = 0; i < num_block_types[0]; ++i) { | |
| 860 context_modes[i] = (uint8_t)(BrotliReadBits(&br, 2) << 1); | |
| 861 BROTLI_LOG_ARRAY_INDEX(context_modes, i); | |
| 862 } | |
| 863 BROTLI_LOG_UINT(num_direct_distance_codes); | |
| 864 BROTLI_LOG_UINT(distance_postfix_bits); | |
| 865 | |
| 866 if (!DecodeContextMap(num_block_types[0] << kLiteralContextBits, | |
| 867 &num_literal_htrees, &context_map, &br) || | |
| 868 !DecodeContextMap(num_block_types[2] << kDistanceContextBits, | |
| 869 &num_dist_htrees, &dist_context_map, &br)) { | |
| 870 ok = 0; | |
| 871 goto End; | |
| 872 } | |
| 873 | |
| 874 HuffmanTreeGroupInit(&hgroup[0], kNumLiteralCodes, num_literal_htrees); | |
| 875 HuffmanTreeGroupInit(&hgroup[1], kNumInsertAndCopyCodes, | |
| 876 num_block_types[1]); | |
| 877 HuffmanTreeGroupInit(&hgroup[2], num_distance_codes, num_dist_htrees); | |
| 878 | |
| 879 for (i = 0; i < 3; ++i) { | |
| 880 if (!HuffmanTreeGroupDecode(&hgroup[i], &br)) { | |
| 881 ok = 0; | |
| 882 goto End; | |
| 883 } | |
| 884 } | |
| 885 | |
| 886 context_map_slice = context_map; | |
| 887 dist_context_map_slice = dist_context_map; | |
| 888 context_mode = context_modes[block_type[0]]; | |
| 889 context_lookup_offset1 = kContextLookupOffsets[context_mode]; | |
| 890 context_lookup_offset2 = kContextLookupOffsets[context_mode + 1]; | |
| 891 htree_command = hgroup[1].htrees[0]; | |
| 892 | |
| 893 while (meta_block_remaining_len > 0) { | |
| 894 int cmd_code; | |
| 895 int range_idx; | |
| 896 int insert_code; | |
| 897 int copy_code; | |
| 898 int insert_length; | |
| 899 int copy_length; | |
| 900 int distance_code; | |
| 901 int distance; | |
| 902 uint8_t context; | |
| 903 int j; | |
| 904 const uint8_t* copy_src; | |
| 905 uint8_t* copy_dst; | |
| 906 if (!BrotliReadMoreInput(&br)) { | |
| 907 printf("[BrotliDecompress] Unexpected end of input.\n"); | |
| 908 ok = 0; | |
| 909 goto End; | |
| 910 } | |
| 911 if (block_length[1] == 0) { | |
| 912 DecodeBlockType(num_block_types[1], | |
| 913 block_type_trees, 1, block_type, block_type_rb, | |
| 914 block_type_rb_index, &br); | |
| 915 block_length[1] = ReadBlockLength( | |
| 916 &block_len_trees[HUFFMAN_MAX_TABLE_SIZE], &br); | |
| 917 htree_command = hgroup[1].htrees[block_type[1]]; | |
| 918 } | |
| 919 --block_length[1]; | |
| 920 cmd_code = ReadSymbol(htree_command, &br); | |
| 921 range_idx = cmd_code >> 6; | |
| 922 if (range_idx >= 2) { | |
| 923 range_idx -= 2; | |
| 924 distance_code = -1; | |
| 925 } else { | |
| 926 distance_code = 0; | |
| 927 } | |
| 928 insert_code = kInsertRangeLut[range_idx] + ((cmd_code >> 3) & 7); | |
| 929 copy_code = kCopyRangeLut[range_idx] + (cmd_code & 7); | |
| 930 insert_length = kInsertLengthPrefixCode[insert_code].offset + | |
| 931 (int)BrotliReadBits(&br, kInsertLengthPrefixCode[insert_code].nbits); | |
| 932 copy_length = kCopyLengthPrefixCode[copy_code].offset + | |
| 933 (int)BrotliReadBits(&br, kCopyLengthPrefixCode[copy_code].nbits); | |
| 934 BROTLI_LOG_UINT(insert_length); | |
| 935 BROTLI_LOG_UINT(copy_length); | |
| 936 BROTLI_LOG_UINT(distance_code); | |
| 937 for (j = 0; j < insert_length; ++j) { | |
| 938 if (!BrotliReadMoreInput(&br)) { | |
| 939 printf("[BrotliDecompress] Unexpected end of input.\n"); | |
| 940 ok = 0; | |
| 941 goto End; | |
| 942 } | |
| 943 if (block_length[0] == 0) { | |
| 944 DecodeBlockType(num_block_types[0], | |
| 945 block_type_trees, 0, block_type, block_type_rb, | |
| 946 block_type_rb_index, &br); | |
| 947 block_length[0] = ReadBlockLength(block_len_trees, &br); | |
| 948 context_offset = block_type[0] << kLiteralContextBits; | |
| 949 context_map_slice = context_map + context_offset; | |
| 950 context_mode = context_modes[block_type[0]]; | |
| 951 context_lookup_offset1 = kContextLookupOffsets[context_mode]; | |
| 952 context_lookup_offset2 = kContextLookupOffsets[context_mode + 1]; | |
| 953 } | |
| 954 context = (kContextLookup[context_lookup_offset1 + prev_byte1] | | |
| 955 kContextLookup[context_lookup_offset2 + prev_byte2]); | |
| 956 BROTLI_LOG_UINT(context); | |
| 957 literal_htree_index = context_map_slice[context]; | |
| 958 --block_length[0]; | |
| 959 prev_byte2 = prev_byte1; | |
| 960 prev_byte1 = (uint8_t)ReadSymbol(hgroup[0].htrees[literal_htree_index], | |
| 961 &br); | |
| 962 ringbuffer[pos & ringbuffer_mask] = prev_byte1; | |
| 963 BROTLI_LOG_UINT(literal_htree_index); | |
| 964 BROTLI_LOG_ARRAY_INDEX(ringbuffer, pos & ringbuffer_mask); | |
| 965 if ((pos & ringbuffer_mask) == ringbuffer_mask) { | |
| 966 if (BrotliWrite(output, ringbuffer, (size_t)ringbuffer_size) < 0) { | |
| 967 ok = 0; | |
| 968 goto End; | |
| 969 } | |
| 970 } | |
| 971 ++pos; | |
| 972 } | |
| 973 meta_block_remaining_len -= insert_length; | |
| 974 if (meta_block_remaining_len <= 0) break; | |
| 975 | |
| 976 if (distance_code < 0) { | |
| 977 uint8_t context; | |
| 978 if (!BrotliReadMoreInput(&br)) { | |
| 979 printf("[BrotliDecompress] Unexpected end of input.\n"); | |
| 980 ok = 0; | |
| 981 goto End; | |
| 982 } | |
| 983 if (block_length[2] == 0) { | |
| 984 DecodeBlockType(num_block_types[2], | |
| 985 block_type_trees, 2, block_type, block_type_rb, | |
| 986 block_type_rb_index, &br); | |
| 987 block_length[2] = ReadBlockLength( | |
| 988 &block_len_trees[2 * HUFFMAN_MAX_TABLE_SIZE], &br); | |
| 989 dist_context_offset = block_type[2] << kDistanceContextBits; | |
| 990 dist_context_map_slice = dist_context_map + dist_context_offset; | |
| 991 } | |
| 992 --block_length[2]; | |
| 993 context = (uint8_t)(copy_length > 4 ? 3 : copy_length - 2); | |
| 994 dist_htree_index = dist_context_map_slice[context]; | |
| 995 distance_code = ReadSymbol(hgroup[2].htrees[dist_htree_index], &br); | |
| 996 if (distance_code >= num_direct_distance_codes) { | |
| 997 int nbits; | |
| 998 int postfix; | |
| 999 int offset; | |
| 1000 distance_code -= num_direct_distance_codes; | |
| 1001 postfix = distance_code & distance_postfix_mask; | |
| 1002 distance_code >>= distance_postfix_bits; | |
| 1003 nbits = (distance_code >> 1) + 1; | |
| 1004 offset = ((2 + (distance_code & 1)) << nbits) - 4; | |
| 1005 distance_code = num_direct_distance_codes + | |
| 1006 ((offset + (int)BrotliReadBits(&br, nbits)) << | |
| 1007 distance_postfix_bits) + postfix; | |
| 1008 } | |
| 1009 } | |
| 1010 | |
| 1011 /* Convert the distance code to the actual distance by possibly looking */ | |
| 1012 /* up past distnaces from the ringbuffer. */ | |
| 1013 distance = TranslateShortCodes(distance_code, dist_rb, dist_rb_idx); | |
| 1014 if (distance < 0) { | |
| 1015 ok = 0; | |
| 1016 goto End; | |
| 1017 } | |
| 1018 BROTLI_LOG_UINT(distance); | |
| 1019 | |
| 1020 if (pos < max_backward_distance && | |
| 1021 max_distance != max_backward_distance) { | |
| 1022 max_distance = pos; | |
| 1023 } else { | |
| 1024 max_distance = max_backward_distance; | |
| 1025 } | |
| 1026 | |
| 1027 copy_dst = &ringbuffer[pos & ringbuffer_mask]; | |
| 1028 | |
| 1029 if (distance > max_distance) { | |
| 1030 if (copy_length >= kMinDictionaryWordLength && | |
| 1031 copy_length <= kMaxDictionaryWordLength) { | |
| 1032 int offset = kBrotliDictionaryOffsetsByLength[copy_length]; | |
| 1033 int word_id = distance - max_distance - 1; | |
| 1034 int shift = kBrotliDictionarySizeBitsByLength[copy_length]; | |
| 1035 int mask = (1 << shift) - 1; | |
| 1036 int word_idx = word_id & mask; | |
| 1037 int transform_idx = word_id >> shift; | |
| 1038 offset += word_idx * copy_length; | |
| 1039 if (transform_idx < kNumTransforms) { | |
| 1040 const uint8_t* word = &kBrotliDictionary[offset]; | |
| 1041 int len = TransformDictionaryWord( | |
| 1042 copy_dst, word, copy_length, transform_idx); | |
| 1043 copy_dst += len; | |
| 1044 pos += len; | |
| 1045 meta_block_remaining_len -= len; | |
| 1046 if (copy_dst >= ringbuffer_end) { | |
| 1047 if (BrotliWrite(output, ringbuffer, | |
| 1048 (size_t)ringbuffer_size) < 0) { | |
| 1049 ok = 0; | |
| 1050 goto End; | |
| 1051 } | |
| 1052 memcpy(ringbuffer, ringbuffer_end, | |
| 1053 (size_t)(copy_dst - ringbuffer_end)); | |
| 1054 } | |
| 1055 } else { | |
| 1056 printf("Invalid backward reference. pos: %d distance: %d " | |
| 1057 "len: %d bytes left: %d\n", pos, distance, copy_length, | |
| 1058 meta_block_remaining_len); | |
| 1059 ok = 0; | |
| 1060 goto End; | |
| 1061 } | |
| 1062 } else { | |
| 1063 printf("Invalid backward reference. pos: %d distance: %d " | |
| 1064 "len: %d bytes left: %d\n", pos, distance, copy_length, | |
| 1065 meta_block_remaining_len); | |
| 1066 ok = 0; | |
| 1067 goto End; | |
| 1068 } | |
| 1069 } else { | |
| 1070 if (distance_code > 0) { | |
| 1071 dist_rb[dist_rb_idx & 3] = distance; | |
| 1072 ++dist_rb_idx; | |
| 1073 } | |
| 1074 | |
| 1075 if (copy_length > meta_block_remaining_len) { | |
| 1076 printf("Invalid backward reference. pos: %d distance: %d " | |
| 1077 "len: %d bytes left: %d\n", pos, distance, copy_length, | |
| 1078 meta_block_remaining_len); | |
| 1079 ok = 0; | |
| 1080 goto End; | |
| 1081 } | |
| 1082 | |
| 1083 copy_src = &ringbuffer[(pos - distance) & ringbuffer_mask]; | |
| 1084 | |
| 1085 #if (defined(__x86_64__) || defined(_M_X64)) | |
| 1086 if (copy_src + copy_length <= ringbuffer_end && | |
| 1087 copy_dst + copy_length < ringbuffer_end) { | |
| 1088 if (copy_length <= 16 && distance >= 8) { | |
| 1089 UNALIGNED_COPY64(copy_dst, copy_src); | |
| 1090 UNALIGNED_COPY64(copy_dst + 8, copy_src + 8); | |
| 1091 } else { | |
| 1092 IncrementalCopyFastPath(copy_dst, copy_src, copy_length); | |
| 1093 } | |
| 1094 pos += copy_length; | |
| 1095 meta_block_remaining_len -= copy_length; | |
| 1096 copy_length = 0; | |
| 1097 } | |
| 1098 #endif | |
| 1099 | |
| 1100 for (j = 0; j < copy_length; ++j) { | |
| 1101 ringbuffer[pos & ringbuffer_mask] = | |
| 1102 ringbuffer[(pos - distance) & ringbuffer_mask]; | |
| 1103 if ((pos & ringbuffer_mask) == ringbuffer_mask) { | |
| 1104 if (BrotliWrite(output, ringbuffer, (size_t)ringbuffer_size) < 0) { | |
| 1105 ok = 0; | |
| 1106 goto End; | |
| 1107 } | |
| 1108 } | |
| 1109 ++pos; | |
| 1110 --meta_block_remaining_len; | |
| 1111 } | |
| 1112 } | |
| 1113 | |
| 1114 /* When we get here, we must have inserted at least one literal and */ | |
| 1115 /* made a copy of at least length two, therefore accessing the last 2 */ | |
| 1116 /* bytes is valid. */ | |
| 1117 prev_byte1 = ringbuffer[(pos - 1) & ringbuffer_mask]; | |
| 1118 prev_byte2 = ringbuffer[(pos - 2) & ringbuffer_mask]; | |
| 1119 } | |
| 1120 | |
| 1121 /* Protect pos from overflow, wrap it around at every GB of input data */ | |
| 1122 pos &= 0x3fffffff; | |
| 1123 | |
| 1124 End: | |
| 1125 if (context_modes != 0) { | |
| 1126 free(context_modes); | |
| 1127 } | |
| 1128 if (context_map != 0) { | |
| 1129 free(context_map); | |
| 1130 } | |
| 1131 if (dist_context_map != 0) { | |
| 1132 free(dist_context_map); | |
| 1133 } | |
| 1134 for (i = 0; i < 3; ++i) { | |
| 1135 HuffmanTreeGroupRelease(&hgroup[i]); | |
| 1136 } | |
| 1137 } | |
| 1138 | |
| 1139 if (ringbuffer != 0) { | |
| 1140 if (BrotliWrite(output, ringbuffer, (size_t)(pos & ringbuffer_mask)) < 0) { | |
| 1141 ok = 0; | |
| 1142 } | |
| 1143 free(ringbuffer); | |
| 1144 } | |
| 1145 if (block_type_trees != 0) { | |
| 1146 free(block_type_trees); | |
| 1147 } | |
| 1148 if (block_len_trees != 0) { | |
| 1149 free(block_len_trees); | |
| 1150 } | |
| 1151 return ok; | |
| 1152 } | |
| 1153 | |
| 1154 #if defined(__cplusplus) || defined(c_plusplus) | |
| 1155 } /* extern "C" */ | |
| 1156 #endif | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1433383003:
Remove //third_party/brotli and //third_party/ots. (Closed)
Base URL: https://github.com/domokit/mojo.git@master