1 // Copyright 2012 Google Inc. All Rights Reserved. 2 // 3 // Use of this source code is governed by a BSD-style license 4 // that can be found in the COPYING file in the root of the source 5 // tree. An additional intellectual property rights grant can be found 6 // in the file PATENTS. All contributing project authors may 7 // be found in the AUTHORS file in the root of the source tree. 8 // ----------------------------------------------------------------------------- 9 // 10 // main entry for the decoder 11 // 12 // Authors: Vikas Arora (vikaas.arora (at) gmail.com) 13 // Jyrki Alakuijala (jyrki (at) google.com) 14 15 #include <stdlib.h> 16 17 #include "src/dec/alphai_dec.h" 18 #include "src/dec/vp8li_dec.h" 19 #include "src/dsp/dsp.h" 20 #include "src/dsp/lossless.h" 21 #include "src/dsp/lossless_common.h" 22 #include "src/dsp/yuv.h" 23 #include "src/utils/endian_inl_utils.h" 24 #include "src/utils/huffman_utils.h" 25 #include "src/utils/utils.h" 26 27 #define NUM_ARGB_CACHE_ROWS 16 28 29 static const int kCodeLengthLiterals = 16; 30 static const int kCodeLengthRepeatCode = 16; 31 static const uint8_t kCodeLengthExtraBits[3] = { 2, 3, 7 }; 32 static const uint8_t kCodeLengthRepeatOffsets[3] = { 3, 3, 11 }; 33 34 // ----------------------------------------------------------------------------- 35 // Five Huffman codes are used at each meta code: 36 // 1. green + length prefix codes + color cache codes, 37 // 2. alpha, 38 // 3. red, 39 // 4. blue, and, 40 // 5. distance prefix codes. 41 typedef enum { 42 GREEN = 0, 43 RED = 1, 44 BLUE = 2, 45 ALPHA = 3, 46 DIST = 4 47 } HuffIndex; 48 49 static const uint16_t kAlphabetSize[HUFFMAN_CODES_PER_META_CODE] = { 50 NUM_LITERAL_CODES + NUM_LENGTH_CODES, 51 NUM_LITERAL_CODES, NUM_LITERAL_CODES, NUM_LITERAL_CODES, 52 NUM_DISTANCE_CODES 53 }; 54 55 static const uint8_t kLiteralMap[HUFFMAN_CODES_PER_META_CODE] = { 56 0, 1, 1, 1, 0 57 }; 58 59 #define NUM_CODE_LENGTH_CODES 19 60 static const uint8_t kCodeLengthCodeOrder[NUM_CODE_LENGTH_CODES] = { 61 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 62 }; 63 64 #define CODE_TO_PLANE_CODES 120 65 static const uint8_t kCodeToPlane[CODE_TO_PLANE_CODES] = { 66 0x18, 0x07, 0x17, 0x19, 0x28, 0x06, 0x27, 0x29, 0x16, 0x1a, 67 0x26, 0x2a, 0x38, 0x05, 0x37, 0x39, 0x15, 0x1b, 0x36, 0x3a, 68 0x25, 0x2b, 0x48, 0x04, 0x47, 0x49, 0x14, 0x1c, 0x35, 0x3b, 69 0x46, 0x4a, 0x24, 0x2c, 0x58, 0x45, 0x4b, 0x34, 0x3c, 0x03, 70 0x57, 0x59, 0x13, 0x1d, 0x56, 0x5a, 0x23, 0x2d, 0x44, 0x4c, 71 0x55, 0x5b, 0x33, 0x3d, 0x68, 0x02, 0x67, 0x69, 0x12, 0x1e, 72 0x66, 0x6a, 0x22, 0x2e, 0x54, 0x5c, 0x43, 0x4d, 0x65, 0x6b, 73 0x32, 0x3e, 0x78, 0x01, 0x77, 0x79, 0x53, 0x5d, 0x11, 0x1f, 74 0x64, 0x6c, 0x42, 0x4e, 0x76, 0x7a, 0x21, 0x2f, 0x75, 0x7b, 75 0x31, 0x3f, 0x63, 0x6d, 0x52, 0x5e, 0x00, 0x74, 0x7c, 0x41, 76 0x4f, 0x10, 0x20, 0x62, 0x6e, 0x30, 0x73, 0x7d, 0x51, 0x5f, 77 0x40, 0x72, 0x7e, 0x61, 0x6f, 0x50, 0x71, 0x7f, 0x60, 0x70 78 }; 79 80 // Memory needed for lookup tables of one Huffman tree group. Red, blue, alpha 81 // and distance alphabets are constant (256 for red, blue and alpha, 40 for 82 // distance) and lookup table sizes for them in worst case are 630 and 410 83 // respectively. Size of green alphabet depends on color cache size and is equal 84 // to 256 (green component values) + 24 (length prefix values) 85 // + color_cache_size (between 0 and 2048). 86 // All values computed for 8-bit first level lookup with Mark Adler's tool: 87 // http://www.hdfgroup.org/ftp/lib-external/zlib/zlib-1.2.5/examples/enough.c 88 #define FIXED_TABLE_SIZE (630 * 3 + 410) 89 static const uint16_t kTableSize[12] = { 90 FIXED_TABLE_SIZE + 654, 91 FIXED_TABLE_SIZE + 656, 92 FIXED_TABLE_SIZE + 658, 93 FIXED_TABLE_SIZE + 662, 94 FIXED_TABLE_SIZE + 670, 95 FIXED_TABLE_SIZE + 686, 96 FIXED_TABLE_SIZE + 718, 97 FIXED_TABLE_SIZE + 782, 98 FIXED_TABLE_SIZE + 912, 99 FIXED_TABLE_SIZE + 1168, 100 FIXED_TABLE_SIZE + 1680, 101 FIXED_TABLE_SIZE + 2704 102 }; 103 104 static int DecodeImageStream(int xsize, int ysize, 105 int is_level0, 106 VP8LDecoder* const dec, 107 uint32_t** const decoded_data); 108 109 //------------------------------------------------------------------------------ 110 111 int VP8LCheckSignature(const uint8_t* const data, size_t size) { 112 return (size >= VP8L_FRAME_HEADER_SIZE && 113 data[0] == VP8L_MAGIC_BYTE && 114 (data[4] >> 5) == 0); // version 115 } 116 117 static int ReadImageInfo(VP8LBitReader* const br, 118 int* const width, int* const height, 119 int* const has_alpha) { 120 if (VP8LReadBits(br, 8) != VP8L_MAGIC_BYTE) return 0; 121 *width = VP8LReadBits(br, VP8L_IMAGE_SIZE_BITS) + 1; 122 *height = VP8LReadBits(br, VP8L_IMAGE_SIZE_BITS) + 1; 123 *has_alpha = VP8LReadBits(br, 1); 124 if (VP8LReadBits(br, VP8L_VERSION_BITS) != 0) return 0; 125 return !br->eos_; 126 } 127 128 int VP8LGetInfo(const uint8_t* data, size_t data_size, 129 int* const width, int* const height, int* const has_alpha) { 130 if (data == NULL || data_size < VP8L_FRAME_HEADER_SIZE) { 131 return 0; // not enough data 132 } else if (!VP8LCheckSignature(data, data_size)) { 133 return 0; // bad signature 134 } else { 135 int w, h, a; 136 VP8LBitReader br; 137 VP8LInitBitReader(&br, data, data_size); 138 if (!ReadImageInfo(&br, &w, &h, &a)) { 139 return 0; 140 } 141 if (width != NULL) *width = w; 142 if (height != NULL) *height = h; 143 if (has_alpha != NULL) *has_alpha = a; 144 return 1; 145 } 146 } 147 148 //------------------------------------------------------------------------------ 149 150 static WEBP_INLINE int GetCopyDistance(int distance_symbol, 151 VP8LBitReader* const br) { 152 int extra_bits, offset; 153 if (distance_symbol < 4) { 154 return distance_symbol + 1; 155 } 156 extra_bits = (distance_symbol - 2) >> 1; 157 offset = (2 + (distance_symbol & 1)) << extra_bits; 158 return offset + VP8LReadBits(br, extra_bits) + 1; 159 } 160 161 static WEBP_INLINE int GetCopyLength(int length_symbol, 162 VP8LBitReader* const br) { 163 // Length and distance prefixes are encoded the same way. 164 return GetCopyDistance(length_symbol, br); 165 } 166 167 static WEBP_INLINE int PlaneCodeToDistance(int xsize, int plane_code) { 168 if (plane_code > CODE_TO_PLANE_CODES) { 169 return plane_code - CODE_TO_PLANE_CODES; 170 } else { 171 const int dist_code = kCodeToPlane[plane_code - 1]; 172 const int yoffset = dist_code >> 4; 173 const int xoffset = 8 - (dist_code & 0xf); 174 const int dist = yoffset * xsize + xoffset; 175 return (dist >= 1) ? dist : 1; // dist<1 can happen if xsize is very small 176 } 177 } 178 179 //------------------------------------------------------------------------------ 180 // Decodes the next Huffman code from bit-stream. 181 // FillBitWindow(br) needs to be called at minimum every second call 182 // to ReadSymbol, in order to pre-fetch enough bits. 183 static WEBP_INLINE int ReadSymbol(const HuffmanCode* table, 184 VP8LBitReader* const br) { 185 int nbits; 186 uint32_t val = VP8LPrefetchBits(br); 187 table += val & HUFFMAN_TABLE_MASK; 188 nbits = table->bits - HUFFMAN_TABLE_BITS; 189 if (nbits > 0) { 190 VP8LSetBitPos(br, br->bit_pos_ + HUFFMAN_TABLE_BITS); 191 val = VP8LPrefetchBits(br); 192 table += table->value; 193 table += val & ((1 << nbits) - 1); 194 } 195 VP8LSetBitPos(br, br->bit_pos_ + table->bits); 196 return table->value; 197 } 198 199 // Reads packed symbol depending on GREEN channel 200 #define BITS_SPECIAL_MARKER 0x100 // something large enough (and a bit-mask) 201 #define PACKED_NON_LITERAL_CODE 0 // must be < NUM_LITERAL_CODES 202 static WEBP_INLINE int ReadPackedSymbols(const HTreeGroup* group, 203 VP8LBitReader* const br, 204 uint32_t* const dst) { 205 const uint32_t val = VP8LPrefetchBits(br) & (HUFFMAN_PACKED_TABLE_SIZE - 1); 206 const HuffmanCode32 code = group->packed_table[val]; 207 assert(group->use_packed_table); 208 if (code.bits < BITS_SPECIAL_MARKER) { 209 VP8LSetBitPos(br, br->bit_pos_ + code.bits); 210 *dst = code.value; 211 return PACKED_NON_LITERAL_CODE; 212 } else { 213 VP8LSetBitPos(br, br->bit_pos_ + code.bits - BITS_SPECIAL_MARKER); 214 assert(code.value >= NUM_LITERAL_CODES); 215 return code.value; 216 } 217 } 218 219 static int AccumulateHCode(HuffmanCode hcode, int shift, 220 HuffmanCode32* const huff) { 221 huff->bits += hcode.bits; 222 huff->value |= (uint32_t)hcode.value << shift; 223 assert(huff->bits <= HUFFMAN_TABLE_BITS); 224 return hcode.bits; 225 } 226 227 static void BuildPackedTable(HTreeGroup* const htree_group) { 228 uint32_t code; 229 for (code = 0; code < HUFFMAN_PACKED_TABLE_SIZE; ++code) { 230 uint32_t bits = code; 231 HuffmanCode32* const huff = &htree_group->packed_table[bits]; 232 HuffmanCode hcode = htree_group->htrees[GREEN][bits]; 233 if (hcode.value >= NUM_LITERAL_CODES) { 234 huff->bits = hcode.bits + BITS_SPECIAL_MARKER; 235 huff->value = hcode.value; 236 } else { 237 huff->bits = 0; 238 huff->value = 0; 239 bits >>= AccumulateHCode(hcode, 8, huff); 240 bits >>= AccumulateHCode(htree_group->htrees[RED][bits], 16, huff); 241 bits >>= AccumulateHCode(htree_group->htrees[BLUE][bits], 0, huff); 242 bits >>= AccumulateHCode(htree_group->htrees[ALPHA][bits], 24, huff); 243 (void)bits; 244 } 245 } 246 } 247 248 static int ReadHuffmanCodeLengths( 249 VP8LDecoder* const dec, const int* const code_length_code_lengths, 250 int num_symbols, int* const code_lengths) { 251 int ok = 0; 252 VP8LBitReader* const br = &dec->br_; 253 int symbol; 254 int max_symbol; 255 int prev_code_len = DEFAULT_CODE_LENGTH; 256 HuffmanCode table[1 << LENGTHS_TABLE_BITS]; 257 258 if (!VP8LBuildHuffmanTable(table, LENGTHS_TABLE_BITS, 259 code_length_code_lengths, 260 NUM_CODE_LENGTH_CODES)) { 261 goto End; 262 } 263 264 if (VP8LReadBits(br, 1)) { // use length 265 const int length_nbits = 2 + 2 * VP8LReadBits(br, 3); 266 max_symbol = 2 + VP8LReadBits(br, length_nbits); 267 if (max_symbol > num_symbols) { 268 goto End; 269 } 270 } else { 271 max_symbol = num_symbols; 272 } 273 274 symbol = 0; 275 while (symbol < num_symbols) { 276 const HuffmanCode* p; 277 int code_len; 278 if (max_symbol-- == 0) break; 279 VP8LFillBitWindow(br); 280 p = &table[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK]; 281 VP8LSetBitPos(br, br->bit_pos_ + p->bits); 282 code_len = p->value; 283 if (code_len < kCodeLengthLiterals) { 284 code_lengths[symbol++] = code_len; 285 if (code_len != 0) prev_code_len = code_len; 286 } else { 287 const int use_prev = (code_len == kCodeLengthRepeatCode); 288 const int slot = code_len - kCodeLengthLiterals; 289 const int extra_bits = kCodeLengthExtraBits[slot]; 290 const int repeat_offset = kCodeLengthRepeatOffsets[slot]; 291 int repeat = VP8LReadBits(br, extra_bits) + repeat_offset; 292 if (symbol + repeat > num_symbols) { 293 goto End; 294 } else { 295 const int length = use_prev ? prev_code_len : 0; 296 while (repeat-- > 0) code_lengths[symbol++] = length; 297 } 298 } 299 } 300 ok = 1; 301 302 End: 303 if (!ok) dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 304 return ok; 305 } 306 307 // 'code_lengths' is pre-allocated temporary buffer, used for creating Huffman 308 // tree. 309 static int ReadHuffmanCode(int alphabet_size, VP8LDecoder* const dec, 310 int* const code_lengths, HuffmanCode* const table) { 311 int ok = 0; 312 int size = 0; 313 VP8LBitReader* const br = &dec->br_; 314 const int simple_code = VP8LReadBits(br, 1); 315 316 memset(code_lengths, 0, alphabet_size * sizeof(*code_lengths)); 317 318 if (simple_code) { // Read symbols, codes & code lengths directly. 319 const int num_symbols = VP8LReadBits(br, 1) + 1; 320 const int first_symbol_len_code = VP8LReadBits(br, 1); 321 // The first code is either 1 bit or 8 bit code. 322 int symbol = VP8LReadBits(br, (first_symbol_len_code == 0) ? 1 : 8); 323 code_lengths[symbol] = 1; 324 // The second code (if present), is always 8 bit long. 325 if (num_symbols == 2) { 326 symbol = VP8LReadBits(br, 8); 327 code_lengths[symbol] = 1; 328 } 329 ok = 1; 330 } else { // Decode Huffman-coded code lengths. 331 int i; 332 int code_length_code_lengths[NUM_CODE_LENGTH_CODES] = { 0 }; 333 const int num_codes = VP8LReadBits(br, 4) + 4; 334 if (num_codes > NUM_CODE_LENGTH_CODES) { 335 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 336 return 0; 337 } 338 339 for (i = 0; i < num_codes; ++i) { 340 code_length_code_lengths[kCodeLengthCodeOrder[i]] = VP8LReadBits(br, 3); 341 } 342 ok = ReadHuffmanCodeLengths(dec, code_length_code_lengths, alphabet_size, 343 code_lengths); 344 } 345 346 ok = ok && !br->eos_; 347 if (ok) { 348 size = VP8LBuildHuffmanTable(table, HUFFMAN_TABLE_BITS, 349 code_lengths, alphabet_size); 350 } 351 if (!ok || size == 0) { 352 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 353 return 0; 354 } 355 return size; 356 } 357 358 static int ReadHuffmanCodes(VP8LDecoder* const dec, int xsize, int ysize, 359 int color_cache_bits, int allow_recursion) { 360 int i, j; 361 VP8LBitReader* const br = &dec->br_; 362 VP8LMetadata* const hdr = &dec->hdr_; 363 uint32_t* huffman_image = NULL; 364 HTreeGroup* htree_groups = NULL; 365 HuffmanCode* huffman_tables = NULL; 366 HuffmanCode* next = NULL; 367 int num_htree_groups = 1; 368 int max_alphabet_size = 0; 369 int* code_lengths = NULL; 370 const int table_size = kTableSize[color_cache_bits]; 371 372 if (allow_recursion && VP8LReadBits(br, 1)) { 373 // use meta Huffman codes. 374 const int huffman_precision = VP8LReadBits(br, 3) + 2; 375 const int huffman_xsize = VP8LSubSampleSize(xsize, huffman_precision); 376 const int huffman_ysize = VP8LSubSampleSize(ysize, huffman_precision); 377 const int huffman_pixs = huffman_xsize * huffman_ysize; 378 if (!DecodeImageStream(huffman_xsize, huffman_ysize, 0, dec, 379 &huffman_image)) { 380 goto Error; 381 } 382 hdr->huffman_subsample_bits_ = huffman_precision; 383 for (i = 0; i < huffman_pixs; ++i) { 384 // The huffman data is stored in red and green bytes. 385 const int group = (huffman_image[i] >> 8) & 0xffff; 386 huffman_image[i] = group; 387 if (group >= num_htree_groups) { 388 num_htree_groups = group + 1; 389 } 390 } 391 } 392 393 if (br->eos_) goto Error; 394 395 // Find maximum alphabet size for the htree group. 396 for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) { 397 int alphabet_size = kAlphabetSize[j]; 398 if (j == 0 && color_cache_bits > 0) { 399 alphabet_size += 1 << color_cache_bits; 400 } 401 if (max_alphabet_size < alphabet_size) { 402 max_alphabet_size = alphabet_size; 403 } 404 } 405 406 huffman_tables = (HuffmanCode*)WebPSafeMalloc(num_htree_groups * table_size, 407 sizeof(*huffman_tables)); 408 htree_groups = VP8LHtreeGroupsNew(num_htree_groups); 409 code_lengths = (int*)WebPSafeCalloc((uint64_t)max_alphabet_size, 410 sizeof(*code_lengths)); 411 412 if (htree_groups == NULL || code_lengths == NULL || huffman_tables == NULL) { 413 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 414 goto Error; 415 } 416 417 next = huffman_tables; 418 for (i = 0; i < num_htree_groups; ++i) { 419 HTreeGroup* const htree_group = &htree_groups[i]; 420 HuffmanCode** const htrees = htree_group->htrees; 421 int size; 422 int total_size = 0; 423 int is_trivial_literal = 1; 424 int max_bits = 0; 425 for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) { 426 int alphabet_size = kAlphabetSize[j]; 427 htrees[j] = next; 428 if (j == 0 && color_cache_bits > 0) { 429 alphabet_size += 1 << color_cache_bits; 430 } 431 size = ReadHuffmanCode(alphabet_size, dec, code_lengths, next); 432 if (size == 0) { 433 goto Error; 434 } 435 if (is_trivial_literal && kLiteralMap[j] == 1) { 436 is_trivial_literal = (next->bits == 0); 437 } 438 total_size += next->bits; 439 next += size; 440 if (j <= ALPHA) { 441 int local_max_bits = code_lengths[0]; 442 int k; 443 for (k = 1; k < alphabet_size; ++k) { 444 if (code_lengths[k] > local_max_bits) { 445 local_max_bits = code_lengths[k]; 446 } 447 } 448 max_bits += local_max_bits; 449 } 450 } 451 htree_group->is_trivial_literal = is_trivial_literal; 452 htree_group->is_trivial_code = 0; 453 if (is_trivial_literal) { 454 const int red = htrees[RED][0].value; 455 const int blue = htrees[BLUE][0].value; 456 const int alpha = htrees[ALPHA][0].value; 457 htree_group->literal_arb = 458 ((uint32_t)alpha << 24) | (red << 16) | blue; 459 if (total_size == 0 && htrees[GREEN][0].value < NUM_LITERAL_CODES) { 460 htree_group->is_trivial_code = 1; 461 htree_group->literal_arb |= htrees[GREEN][0].value << 8; 462 } 463 } 464 htree_group->use_packed_table = !htree_group->is_trivial_code && 465 (max_bits < HUFFMAN_PACKED_BITS); 466 if (htree_group->use_packed_table) BuildPackedTable(htree_group); 467 } 468 WebPSafeFree(code_lengths); 469 470 // All OK. Finalize pointers and return. 471 hdr->huffman_image_ = huffman_image; 472 hdr->num_htree_groups_ = num_htree_groups; 473 hdr->htree_groups_ = htree_groups; 474 hdr->huffman_tables_ = huffman_tables; 475 return 1; 476 477 Error: 478 WebPSafeFree(code_lengths); 479 WebPSafeFree(huffman_image); 480 WebPSafeFree(huffman_tables); 481 VP8LHtreeGroupsFree(htree_groups); 482 return 0; 483 } 484 485 //------------------------------------------------------------------------------ 486 // Scaling. 487 488 #if !defined(WEBP_REDUCE_SIZE) 489 static int AllocateAndInitRescaler(VP8LDecoder* const dec, VP8Io* const io) { 490 const int num_channels = 4; 491 const int in_width = io->mb_w; 492 const int out_width = io->scaled_width; 493 const int in_height = io->mb_h; 494 const int out_height = io->scaled_height; 495 const uint64_t work_size = 2 * num_channels * (uint64_t)out_width; 496 rescaler_t* work; // Rescaler work area. 497 const uint64_t scaled_data_size = (uint64_t)out_width; 498 uint32_t* scaled_data; // Temporary storage for scaled BGRA data. 499 const uint64_t memory_size = sizeof(*dec->rescaler) + 500 work_size * sizeof(*work) + 501 scaled_data_size * sizeof(*scaled_data); 502 uint8_t* memory = (uint8_t*)WebPSafeMalloc(memory_size, sizeof(*memory)); 503 if (memory == NULL) { 504 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 505 return 0; 506 } 507 assert(dec->rescaler_memory == NULL); 508 dec->rescaler_memory = memory; 509 510 dec->rescaler = (WebPRescaler*)memory; 511 memory += sizeof(*dec->rescaler); 512 work = (rescaler_t*)memory; 513 memory += work_size * sizeof(*work); 514 scaled_data = (uint32_t*)memory; 515 516 WebPRescalerInit(dec->rescaler, in_width, in_height, (uint8_t*)scaled_data, 517 out_width, out_height, 0, num_channels, work); 518 return 1; 519 } 520 #endif // WEBP_REDUCE_SIZE 521 522 //------------------------------------------------------------------------------ 523 // Export to ARGB 524 525 #if !defined(WEBP_REDUCE_SIZE) 526 527 // We have special "export" function since we need to convert from BGRA 528 static int Export(WebPRescaler* const rescaler, WEBP_CSP_MODE colorspace, 529 int rgba_stride, uint8_t* const rgba) { 530 uint32_t* const src = (uint32_t*)rescaler->dst; 531 const int dst_width = rescaler->dst_width; 532 int num_lines_out = 0; 533 while (WebPRescalerHasPendingOutput(rescaler)) { 534 uint8_t* const dst = rgba + num_lines_out * rgba_stride; 535 WebPRescalerExportRow(rescaler); 536 WebPMultARGBRow(src, dst_width, 1); 537 VP8LConvertFromBGRA(src, dst_width, colorspace, dst); 538 ++num_lines_out; 539 } 540 return num_lines_out; 541 } 542 543 // Emit scaled rows. 544 static int EmitRescaledRowsRGBA(const VP8LDecoder* const dec, 545 uint8_t* in, int in_stride, int mb_h, 546 uint8_t* const out, int out_stride) { 547 const WEBP_CSP_MODE colorspace = dec->output_->colorspace; 548 int num_lines_in = 0; 549 int num_lines_out = 0; 550 while (num_lines_in < mb_h) { 551 uint8_t* const row_in = in + num_lines_in * in_stride; 552 uint8_t* const row_out = out + num_lines_out * out_stride; 553 const int lines_left = mb_h - num_lines_in; 554 const int needed_lines = WebPRescaleNeededLines(dec->rescaler, lines_left); 555 int lines_imported; 556 assert(needed_lines > 0 && needed_lines <= lines_left); 557 WebPMultARGBRows(row_in, in_stride, 558 dec->rescaler->src_width, needed_lines, 0); 559 lines_imported = 560 WebPRescalerImport(dec->rescaler, lines_left, row_in, in_stride); 561 assert(lines_imported == needed_lines); 562 num_lines_in += lines_imported; 563 num_lines_out += Export(dec->rescaler, colorspace, out_stride, row_out); 564 } 565 return num_lines_out; 566 } 567 568 #endif // WEBP_REDUCE_SIZE 569 570 // Emit rows without any scaling. 571 static int EmitRows(WEBP_CSP_MODE colorspace, 572 const uint8_t* row_in, int in_stride, 573 int mb_w, int mb_h, 574 uint8_t* const out, int out_stride) { 575 int lines = mb_h; 576 uint8_t* row_out = out; 577 while (lines-- > 0) { 578 VP8LConvertFromBGRA((const uint32_t*)row_in, mb_w, colorspace, row_out); 579 row_in += in_stride; 580 row_out += out_stride; 581 } 582 return mb_h; // Num rows out == num rows in. 583 } 584 585 //------------------------------------------------------------------------------ 586 // Export to YUVA 587 588 static void ConvertToYUVA(const uint32_t* const src, int width, int y_pos, 589 const WebPDecBuffer* const output) { 590 const WebPYUVABuffer* const buf = &output->u.YUVA; 591 592 // first, the luma plane 593 WebPConvertARGBToY(src, buf->y + y_pos * buf->y_stride, width); 594 595 // then U/V planes 596 { 597 uint8_t* const u = buf->u + (y_pos >> 1) * buf->u_stride; 598 uint8_t* const v = buf->v + (y_pos >> 1) * buf->v_stride; 599 // even lines: store values 600 // odd lines: average with previous values 601 WebPConvertARGBToUV(src, u, v, width, !(y_pos & 1)); 602 } 603 // Lastly, store alpha if needed. 604 if (buf->a != NULL) { 605 uint8_t* const a = buf->a + y_pos * buf->a_stride; 606 #if defined(WORDS_BIGENDIAN) 607 WebPExtractAlpha((uint8_t*)src + 0, 0, width, 1, a, 0); 608 #else 609 WebPExtractAlpha((uint8_t*)src + 3, 0, width, 1, a, 0); 610 #endif 611 } 612 } 613 614 static int ExportYUVA(const VP8LDecoder* const dec, int y_pos) { 615 WebPRescaler* const rescaler = dec->rescaler; 616 uint32_t* const src = (uint32_t*)rescaler->dst; 617 const int dst_width = rescaler->dst_width; 618 int num_lines_out = 0; 619 while (WebPRescalerHasPendingOutput(rescaler)) { 620 WebPRescalerExportRow(rescaler); 621 WebPMultARGBRow(src, dst_width, 1); 622 ConvertToYUVA(src, dst_width, y_pos, dec->output_); 623 ++y_pos; 624 ++num_lines_out; 625 } 626 return num_lines_out; 627 } 628 629 static int EmitRescaledRowsYUVA(const VP8LDecoder* const dec, 630 uint8_t* in, int in_stride, int mb_h) { 631 int num_lines_in = 0; 632 int y_pos = dec->last_out_row_; 633 while (num_lines_in < mb_h) { 634 const int lines_left = mb_h - num_lines_in; 635 const int needed_lines = WebPRescaleNeededLines(dec->rescaler, lines_left); 636 int lines_imported; 637 WebPMultARGBRows(in, in_stride, dec->rescaler->src_width, needed_lines, 0); 638 lines_imported = 639 WebPRescalerImport(dec->rescaler, lines_left, in, in_stride); 640 assert(lines_imported == needed_lines); 641 num_lines_in += lines_imported; 642 in += needed_lines * in_stride; 643 y_pos += ExportYUVA(dec, y_pos); 644 } 645 return y_pos; 646 } 647 648 static int EmitRowsYUVA(const VP8LDecoder* const dec, 649 const uint8_t* in, int in_stride, 650 int mb_w, int num_rows) { 651 int y_pos = dec->last_out_row_; 652 while (num_rows-- > 0) { 653 ConvertToYUVA((const uint32_t*)in, mb_w, y_pos, dec->output_); 654 in += in_stride; 655 ++y_pos; 656 } 657 return y_pos; 658 } 659 660 //------------------------------------------------------------------------------ 661 // Cropping. 662 663 // Sets io->mb_y, io->mb_h & io->mb_w according to start row, end row and 664 // crop options. Also updates the input data pointer, so that it points to the 665 // start of the cropped window. Note that pixels are in ARGB format even if 666 // 'in_data' is uint8_t*. 667 // Returns true if the crop window is not empty. 668 static int SetCropWindow(VP8Io* const io, int y_start, int y_end, 669 uint8_t** const in_data, int pixel_stride) { 670 assert(y_start < y_end); 671 assert(io->crop_left < io->crop_right); 672 if (y_end > io->crop_bottom) { 673 y_end = io->crop_bottom; // make sure we don't overflow on last row. 674 } 675 if (y_start < io->crop_top) { 676 const int delta = io->crop_top - y_start; 677 y_start = io->crop_top; 678 *in_data += delta * pixel_stride; 679 } 680 if (y_start >= y_end) return 0; // Crop window is empty. 681 682 *in_data += io->crop_left * sizeof(uint32_t); 683 684 io->mb_y = y_start - io->crop_top; 685 io->mb_w = io->crop_right - io->crop_left; 686 io->mb_h = y_end - y_start; 687 return 1; // Non-empty crop window. 688 } 689 690 //------------------------------------------------------------------------------ 691 692 static WEBP_INLINE int GetMetaIndex( 693 const uint32_t* const image, int xsize, int bits, int x, int y) { 694 if (bits == 0) return 0; 695 return image[xsize * (y >> bits) + (x >> bits)]; 696 } 697 698 static WEBP_INLINE HTreeGroup* GetHtreeGroupForPos(VP8LMetadata* const hdr, 699 int x, int y) { 700 const int meta_index = GetMetaIndex(hdr->huffman_image_, hdr->huffman_xsize_, 701 hdr->huffman_subsample_bits_, x, y); 702 assert(meta_index < hdr->num_htree_groups_); 703 return hdr->htree_groups_ + meta_index; 704 } 705 706 //------------------------------------------------------------------------------ 707 // Main loop, with custom row-processing function 708 709 typedef void (*ProcessRowsFunc)(VP8LDecoder* const dec, int row); 710 711 static void ApplyInverseTransforms(VP8LDecoder* const dec, int num_rows, 712 const uint32_t* const rows) { 713 int n = dec->next_transform_; 714 const int cache_pixs = dec->width_ * num_rows; 715 const int start_row = dec->last_row_; 716 const int end_row = start_row + num_rows; 717 const uint32_t* rows_in = rows; 718 uint32_t* const rows_out = dec->argb_cache_; 719 720 // Inverse transforms. 721 while (n-- > 0) { 722 VP8LTransform* const transform = &dec->transforms_[n]; 723 VP8LInverseTransform(transform, start_row, end_row, rows_in, rows_out); 724 rows_in = rows_out; 725 } 726 if (rows_in != rows_out) { 727 // No transform called, hence just copy. 728 memcpy(rows_out, rows_in, cache_pixs * sizeof(*rows_out)); 729 } 730 } 731 732 // Processes (transforms, scales & color-converts) the rows decoded after the 733 // last call. 734 static void ProcessRows(VP8LDecoder* const dec, int row) { 735 const uint32_t* const rows = dec->pixels_ + dec->width_ * dec->last_row_; 736 const int num_rows = row - dec->last_row_; 737 738 assert(row <= dec->io_->crop_bottom); 739 // We can't process more than NUM_ARGB_CACHE_ROWS at a time (that's the size 740 // of argb_cache_), but we currently don't need more than that. 741 assert(num_rows <= NUM_ARGB_CACHE_ROWS); 742 if (num_rows > 0) { // Emit output. 743 VP8Io* const io = dec->io_; 744 uint8_t* rows_data = (uint8_t*)dec->argb_cache_; 745 const int in_stride = io->width * sizeof(uint32_t); // in unit of RGBA 746 747 ApplyInverseTransforms(dec, num_rows, rows); 748 if (!SetCropWindow(io, dec->last_row_, row, &rows_data, in_stride)) { 749 // Nothing to output (this time). 750 } else { 751 const WebPDecBuffer* const output = dec->output_; 752 if (WebPIsRGBMode(output->colorspace)) { // convert to RGBA 753 const WebPRGBABuffer* const buf = &output->u.RGBA; 754 uint8_t* const rgba = buf->rgba + dec->last_out_row_ * buf->stride; 755 const int num_rows_out = 756 #if !defined(WEBP_REDUCE_SIZE) 757 io->use_scaling ? 758 EmitRescaledRowsRGBA(dec, rows_data, in_stride, io->mb_h, 759 rgba, buf->stride) : 760 #endif // WEBP_REDUCE_SIZE 761 EmitRows(output->colorspace, rows_data, in_stride, 762 io->mb_w, io->mb_h, rgba, buf->stride); 763 // Update 'last_out_row_'. 764 dec->last_out_row_ += num_rows_out; 765 } else { // convert to YUVA 766 dec->last_out_row_ = io->use_scaling ? 767 EmitRescaledRowsYUVA(dec, rows_data, in_stride, io->mb_h) : 768 EmitRowsYUVA(dec, rows_data, in_stride, io->mb_w, io->mb_h); 769 } 770 assert(dec->last_out_row_ <= output->height); 771 } 772 } 773 774 // Update 'last_row_'. 775 dec->last_row_ = row; 776 assert(dec->last_row_ <= dec->height_); 777 } 778 779 // Row-processing for the special case when alpha data contains only one 780 // transform (color indexing), and trivial non-green literals. 781 static int Is8bOptimizable(const VP8LMetadata* const hdr) { 782 int i; 783 if (hdr->color_cache_size_ > 0) return 0; 784 // When the Huffman tree contains only one symbol, we can skip the 785 // call to ReadSymbol() for red/blue/alpha channels. 786 for (i = 0; i < hdr->num_htree_groups_; ++i) { 787 HuffmanCode** const htrees = hdr->htree_groups_[i].htrees; 788 if (htrees[RED][0].bits > 0) return 0; 789 if (htrees[BLUE][0].bits > 0) return 0; 790 if (htrees[ALPHA][0].bits > 0) return 0; 791 } 792 return 1; 793 } 794 795 static void AlphaApplyFilter(ALPHDecoder* const alph_dec, 796 int first_row, int last_row, 797 uint8_t* out, int stride) { 798 if (alph_dec->filter_ != WEBP_FILTER_NONE) { 799 int y; 800 const uint8_t* prev_line = alph_dec->prev_line_; 801 assert(WebPUnfilters[alph_dec->filter_] != NULL); 802 for (y = first_row; y < last_row; ++y) { 803 WebPUnfilters[alph_dec->filter_](prev_line, out, out, stride); 804 prev_line = out; 805 out += stride; 806 } 807 alph_dec->prev_line_ = prev_line; 808 } 809 } 810 811 static void ExtractPalettedAlphaRows(VP8LDecoder* const dec, int last_row) { 812 // For vertical and gradient filtering, we need to decode the part above the 813 // crop_top row, in order to have the correct spatial predictors. 814 ALPHDecoder* const alph_dec = (ALPHDecoder*)dec->io_->opaque; 815 const int top_row = 816 (alph_dec->filter_ == WEBP_FILTER_NONE || 817 alph_dec->filter_ == WEBP_FILTER_HORIZONTAL) ? dec->io_->crop_top 818 : dec->last_row_; 819 const int first_row = (dec->last_row_ < top_row) ? top_row : dec->last_row_; 820 assert(last_row <= dec->io_->crop_bottom); 821 if (last_row > first_row) { 822 // Special method for paletted alpha data. We only process the cropped area. 823 const int width = dec->io_->width; 824 uint8_t* out = alph_dec->output_ + width * first_row; 825 const uint8_t* const in = 826 (uint8_t*)dec->pixels_ + dec->width_ * first_row; 827 VP8LTransform* const transform = &dec->transforms_[0]; 828 assert(dec->next_transform_ == 1); 829 assert(transform->type_ == COLOR_INDEXING_TRANSFORM); 830 VP8LColorIndexInverseTransformAlpha(transform, first_row, last_row, 831 in, out); 832 AlphaApplyFilter(alph_dec, first_row, last_row, out, width); 833 } 834 dec->last_row_ = dec->last_out_row_ = last_row; 835 } 836 837 //------------------------------------------------------------------------------ 838 // Helper functions for fast pattern copy (8b and 32b) 839 840 // cyclic rotation of pattern word 841 static WEBP_INLINE uint32_t Rotate8b(uint32_t V) { 842 #if defined(WORDS_BIGENDIAN) 843 return ((V & 0xff000000u) >> 24) | (V << 8); 844 #else 845 return ((V & 0xffu) << 24) | (V >> 8); 846 #endif 847 } 848 849 // copy 1, 2 or 4-bytes pattern 850 static WEBP_INLINE void CopySmallPattern8b(const uint8_t* src, uint8_t* dst, 851 int length, uint32_t pattern) { 852 int i; 853 // align 'dst' to 4-bytes boundary. Adjust the pattern along the way. 854 while ((uintptr_t)dst & 3) { 855 *dst++ = *src++; 856 pattern = Rotate8b(pattern); 857 --length; 858 } 859 // Copy the pattern 4 bytes at a time. 860 for (i = 0; i < (length >> 2); ++i) { 861 ((uint32_t*)dst)[i] = pattern; 862 } 863 // Finish with left-overs. 'pattern' is still correctly positioned, 864 // so no Rotate8b() call is needed. 865 for (i <<= 2; i < length; ++i) { 866 dst[i] = src[i]; 867 } 868 } 869 870 static WEBP_INLINE void CopyBlock8b(uint8_t* const dst, int dist, int length) { 871 const uint8_t* src = dst - dist; 872 if (length >= 8) { 873 uint32_t pattern = 0; 874 switch (dist) { 875 case 1: 876 pattern = src[0]; 877 #if defined(__arm__) || defined(_M_ARM) // arm doesn't like multiply that much 878 pattern |= pattern << 8; 879 pattern |= pattern << 16; 880 #elif defined(WEBP_USE_MIPS_DSP_R2) 881 __asm__ volatile ("replv.qb %0, %0" : "+r"(pattern)); 882 #else 883 pattern = 0x01010101u * pattern; 884 #endif 885 break; 886 case 2: 887 memcpy(&pattern, src, sizeof(uint16_t)); 888 #if defined(__arm__) || defined(_M_ARM) 889 pattern |= pattern << 16; 890 #elif defined(WEBP_USE_MIPS_DSP_R2) 891 __asm__ volatile ("replv.ph %0, %0" : "+r"(pattern)); 892 #else 893 pattern = 0x00010001u * pattern; 894 #endif 895 break; 896 case 4: 897 memcpy(&pattern, src, sizeof(uint32_t)); 898 break; 899 default: 900 goto Copy; 901 break; 902 } 903 CopySmallPattern8b(src, dst, length, pattern); 904 return; 905 } 906 Copy: 907 if (dist >= length) { // no overlap -> use memcpy() 908 memcpy(dst, src, length * sizeof(*dst)); 909 } else { 910 int i; 911 for (i = 0; i < length; ++i) dst[i] = src[i]; 912 } 913 } 914 915 // copy pattern of 1 or 2 uint32_t's 916 static WEBP_INLINE void CopySmallPattern32b(const uint32_t* src, 917 uint32_t* dst, 918 int length, uint64_t pattern) { 919 int i; 920 if ((uintptr_t)dst & 4) { // Align 'dst' to 8-bytes boundary. 921 *dst++ = *src++; 922 pattern = (pattern >> 32) | (pattern << 32); 923 --length; 924 } 925 assert(0 == ((uintptr_t)dst & 7)); 926 for (i = 0; i < (length >> 1); ++i) { 927 ((uint64_t*)dst)[i] = pattern; // Copy the pattern 8 bytes at a time. 928 } 929 if (length & 1) { // Finish with left-over. 930 dst[i << 1] = src[i << 1]; 931 } 932 } 933 934 static WEBP_INLINE void CopyBlock32b(uint32_t* const dst, 935 int dist, int length) { 936 const uint32_t* const src = dst - dist; 937 if (dist <= 2 && length >= 4 && ((uintptr_t)dst & 3) == 0) { 938 uint64_t pattern; 939 if (dist == 1) { 940 pattern = (uint64_t)src[0]; 941 pattern |= pattern << 32; 942 } else { 943 memcpy(&pattern, src, sizeof(pattern)); 944 } 945 CopySmallPattern32b(src, dst, length, pattern); 946 } else if (dist >= length) { // no overlap 947 memcpy(dst, src, length * sizeof(*dst)); 948 } else { 949 int i; 950 for (i = 0; i < length; ++i) dst[i] = src[i]; 951 } 952 } 953 954 //------------------------------------------------------------------------------ 955 956 static int DecodeAlphaData(VP8LDecoder* const dec, uint8_t* const data, 957 int width, int height, int last_row) { 958 int ok = 1; 959 int row = dec->last_pixel_ / width; 960 int col = dec->last_pixel_ % width; 961 VP8LBitReader* const br = &dec->br_; 962 VP8LMetadata* const hdr = &dec->hdr_; 963 int pos = dec->last_pixel_; // current position 964 const int end = width * height; // End of data 965 const int last = width * last_row; // Last pixel to decode 966 const int len_code_limit = NUM_LITERAL_CODES + NUM_LENGTH_CODES; 967 const int mask = hdr->huffman_mask_; 968 const HTreeGroup* htree_group = 969 (pos < last) ? GetHtreeGroupForPos(hdr, col, row) : NULL; 970 assert(pos <= end); 971 assert(last_row <= height); 972 assert(Is8bOptimizable(hdr)); 973 974 while (!br->eos_ && pos < last) { 975 int code; 976 // Only update when changing tile. 977 if ((col & mask) == 0) { 978 htree_group = GetHtreeGroupForPos(hdr, col, row); 979 } 980 assert(htree_group != NULL); 981 VP8LFillBitWindow(br); 982 code = ReadSymbol(htree_group->htrees[GREEN], br); 983 if (code < NUM_LITERAL_CODES) { // Literal 984 data[pos] = code; 985 ++pos; 986 ++col; 987 if (col >= width) { 988 col = 0; 989 ++row; 990 if (row <= last_row && (row % NUM_ARGB_CACHE_ROWS == 0)) { 991 ExtractPalettedAlphaRows(dec, row); 992 } 993 } 994 } else if (code < len_code_limit) { // Backward reference 995 int dist_code, dist; 996 const int length_sym = code - NUM_LITERAL_CODES; 997 const int length = GetCopyLength(length_sym, br); 998 const int dist_symbol = ReadSymbol(htree_group->htrees[DIST], br); 999 VP8LFillBitWindow(br); 1000 dist_code = GetCopyDistance(dist_symbol, br); 1001 dist = PlaneCodeToDistance(width, dist_code); 1002 if (pos >= dist && end - pos >= length) { 1003 CopyBlock8b(data + pos, dist, length); 1004 } else { 1005 ok = 0; 1006 goto End; 1007 } 1008 pos += length; 1009 col += length; 1010 while (col >= width) { 1011 col -= width; 1012 ++row; 1013 if (row <= last_row && (row % NUM_ARGB_CACHE_ROWS == 0)) { 1014 ExtractPalettedAlphaRows(dec, row); 1015 } 1016 } 1017 if (pos < last && (col & mask)) { 1018 htree_group = GetHtreeGroupForPos(hdr, col, row); 1019 } 1020 } else { // Not reached 1021 ok = 0; 1022 goto End; 1023 } 1024 br->eos_ = VP8LIsEndOfStream(br); 1025 } 1026 // Process the remaining rows corresponding to last row-block. 1027 ExtractPalettedAlphaRows(dec, row > last_row ? last_row : row); 1028 1029 End: 1030 br->eos_ = VP8LIsEndOfStream(br); 1031 if (!ok || (br->eos_ && pos < end)) { 1032 ok = 0; 1033 dec->status_ = br->eos_ ? VP8_STATUS_SUSPENDED 1034 : VP8_STATUS_BITSTREAM_ERROR; 1035 } else { 1036 dec->last_pixel_ = pos; 1037 } 1038 return ok; 1039 } 1040 1041 static void SaveState(VP8LDecoder* const dec, int last_pixel) { 1042 assert(dec->incremental_); 1043 dec->saved_br_ = dec->br_; 1044 dec->saved_last_pixel_ = last_pixel; 1045 if (dec->hdr_.color_cache_size_ > 0) { 1046 VP8LColorCacheCopy(&dec->hdr_.color_cache_, &dec->hdr_.saved_color_cache_); 1047 } 1048 } 1049 1050 static void RestoreState(VP8LDecoder* const dec) { 1051 assert(dec->br_.eos_); 1052 dec->status_ = VP8_STATUS_SUSPENDED; 1053 dec->br_ = dec->saved_br_; 1054 dec->last_pixel_ = dec->saved_last_pixel_; 1055 if (dec->hdr_.color_cache_size_ > 0) { 1056 VP8LColorCacheCopy(&dec->hdr_.saved_color_cache_, &dec->hdr_.color_cache_); 1057 } 1058 } 1059 1060 #define SYNC_EVERY_N_ROWS 8 // minimum number of rows between check-points 1061 static int DecodeImageData(VP8LDecoder* const dec, uint32_t* const data, 1062 int width, int height, int last_row, 1063 ProcessRowsFunc process_func) { 1064 int row = dec->last_pixel_ / width; 1065 int col = dec->last_pixel_ % width; 1066 VP8LBitReader* const br = &dec->br_; 1067 VP8LMetadata* const hdr = &dec->hdr_; 1068 uint32_t* src = data + dec->last_pixel_; 1069 uint32_t* last_cached = src; 1070 uint32_t* const src_end = data + width * height; // End of data 1071 uint32_t* const src_last = data + width * last_row; // Last pixel to decode 1072 const int len_code_limit = NUM_LITERAL_CODES + NUM_LENGTH_CODES; 1073 const int color_cache_limit = len_code_limit + hdr->color_cache_size_; 1074 int next_sync_row = dec->incremental_ ? row : 1 << 24; 1075 VP8LColorCache* const color_cache = 1076 (hdr->color_cache_size_ > 0) ? &hdr->color_cache_ : NULL; 1077 const int mask = hdr->huffman_mask_; 1078 const HTreeGroup* htree_group = 1079 (src < src_last) ? GetHtreeGroupForPos(hdr, col, row) : NULL; 1080 assert(dec->last_row_ < last_row); 1081 assert(src_last <= src_end); 1082 1083 while (src < src_last) { 1084 int code; 1085 if (row >= next_sync_row) { 1086 SaveState(dec, (int)(src - data)); 1087 next_sync_row = row + SYNC_EVERY_N_ROWS; 1088 } 1089 // Only update when changing tile. Note we could use this test: 1090 // if "((((prev_col ^ col) | prev_row ^ row)) > mask)" -> tile changed 1091 // but that's actually slower and needs storing the previous col/row. 1092 if ((col & mask) == 0) { 1093 htree_group = GetHtreeGroupForPos(hdr, col, row); 1094 } 1095 assert(htree_group != NULL); 1096 if (htree_group->is_trivial_code) { 1097 *src = htree_group->literal_arb; 1098 goto AdvanceByOne; 1099 } 1100 VP8LFillBitWindow(br); 1101 if (htree_group->use_packed_table) { 1102 code = ReadPackedSymbols(htree_group, br, src); 1103 if (VP8LIsEndOfStream(br)) break; 1104 if (code == PACKED_NON_LITERAL_CODE) goto AdvanceByOne; 1105 } else { 1106 code = ReadSymbol(htree_group->htrees[GREEN], br); 1107 } 1108 if (VP8LIsEndOfStream(br)) break; 1109 if (code < NUM_LITERAL_CODES) { // Literal 1110 if (htree_group->is_trivial_literal) { 1111 *src = htree_group->literal_arb | (code << 8); 1112 } else { 1113 int red, blue, alpha; 1114 red = ReadSymbol(htree_group->htrees[RED], br); 1115 VP8LFillBitWindow(br); 1116 blue = ReadSymbol(htree_group->htrees[BLUE], br); 1117 alpha = ReadSymbol(htree_group->htrees[ALPHA], br); 1118 if (VP8LIsEndOfStream(br)) break; 1119 *src = ((uint32_t)alpha << 24) | (red << 16) | (code << 8) | blue; 1120 } 1121 AdvanceByOne: 1122 ++src; 1123 ++col; 1124 if (col >= width) { 1125 col = 0; 1126 ++row; 1127 if (process_func != NULL) { 1128 if (row <= last_row && (row % NUM_ARGB_CACHE_ROWS == 0)) { 1129 process_func(dec, row); 1130 } 1131 } 1132 if (color_cache != NULL) { 1133 while (last_cached < src) { 1134 VP8LColorCacheInsert(color_cache, *last_cached++); 1135 } 1136 } 1137 } 1138 } else if (code < len_code_limit) { // Backward reference 1139 int dist_code, dist; 1140 const int length_sym = code - NUM_LITERAL_CODES; 1141 const int length = GetCopyLength(length_sym, br); 1142 const int dist_symbol = ReadSymbol(htree_group->htrees[DIST], br); 1143 VP8LFillBitWindow(br); 1144 dist_code = GetCopyDistance(dist_symbol, br); 1145 dist = PlaneCodeToDistance(width, dist_code); 1146 if (VP8LIsEndOfStream(br)) break; 1147 if (src - data < (ptrdiff_t)dist || src_end - src < (ptrdiff_t)length) { 1148 goto Error; 1149 } else { 1150 CopyBlock32b(src, dist, length); 1151 } 1152 src += length; 1153 col += length; 1154 while (col >= width) { 1155 col -= width; 1156 ++row; 1157 if (process_func != NULL) { 1158 if (row <= last_row && (row % NUM_ARGB_CACHE_ROWS == 0)) { 1159 process_func(dec, row); 1160 } 1161 } 1162 } 1163 // Because of the check done above (before 'src' was incremented by 1164 // 'length'), the following holds true. 1165 assert(src <= src_end); 1166 if (col & mask) htree_group = GetHtreeGroupForPos(hdr, col, row); 1167 if (color_cache != NULL) { 1168 while (last_cached < src) { 1169 VP8LColorCacheInsert(color_cache, *last_cached++); 1170 } 1171 } 1172 } else if (code < color_cache_limit) { // Color cache 1173 const int key = code - len_code_limit; 1174 assert(color_cache != NULL); 1175 while (last_cached < src) { 1176 VP8LColorCacheInsert(color_cache, *last_cached++); 1177 } 1178 *src = VP8LColorCacheLookup(color_cache, key); 1179 goto AdvanceByOne; 1180 } else { // Not reached 1181 goto Error; 1182 } 1183 } 1184 1185 br->eos_ = VP8LIsEndOfStream(br); 1186 if (dec->incremental_ && br->eos_ && src < src_end) { 1187 RestoreState(dec); 1188 } else if (!br->eos_) { 1189 // Process the remaining rows corresponding to last row-block. 1190 if (process_func != NULL) { 1191 process_func(dec, row > last_row ? last_row : row); 1192 } 1193 dec->status_ = VP8_STATUS_OK; 1194 dec->last_pixel_ = (int)(src - data); // end-of-scan marker 1195 } else { 1196 // if not incremental, and we are past the end of buffer (eos_=1), then this 1197 // is a real bitstream error. 1198 goto Error; 1199 } 1200 return 1; 1201 1202 Error: 1203 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 1204 return 0; 1205 } 1206 1207 // ----------------------------------------------------------------------------- 1208 // VP8LTransform 1209 1210 static void ClearTransform(VP8LTransform* const transform) { 1211 WebPSafeFree(transform->data_); 1212 transform->data_ = NULL; 1213 } 1214 1215 // For security reason, we need to remap the color map to span 1216 // the total possible bundled values, and not just the num_colors. 1217 static int ExpandColorMap(int num_colors, VP8LTransform* const transform) { 1218 int i; 1219 const int final_num_colors = 1 << (8 >> transform->bits_); 1220 uint32_t* const new_color_map = 1221 (uint32_t*)WebPSafeMalloc((uint64_t)final_num_colors, 1222 sizeof(*new_color_map)); 1223 if (new_color_map == NULL) { 1224 return 0; 1225 } else { 1226 uint8_t* const data = (uint8_t*)transform->data_; 1227 uint8_t* const new_data = (uint8_t*)new_color_map; 1228 new_color_map[0] = transform->data_[0]; 1229 for (i = 4; i < 4 * num_colors; ++i) { 1230 // Equivalent to AddPixelEq(), on a byte-basis. 1231 new_data[i] = (data[i] + new_data[i - 4]) & 0xff; 1232 } 1233 for (; i < 4 * final_num_colors; ++i) { 1234 new_data[i] = 0; // black tail. 1235 } 1236 WebPSafeFree(transform->data_); 1237 transform->data_ = new_color_map; 1238 } 1239 return 1; 1240 } 1241 1242 static int ReadTransform(int* const xsize, int const* ysize, 1243 VP8LDecoder* const dec) { 1244 int ok = 1; 1245 VP8LBitReader* const br = &dec->br_; 1246 VP8LTransform* transform = &dec->transforms_[dec->next_transform_]; 1247 const VP8LImageTransformType type = 1248 (VP8LImageTransformType)VP8LReadBits(br, 2); 1249 1250 // Each transform type can only be present once in the stream. 1251 if (dec->transforms_seen_ & (1U << type)) { 1252 return 0; // Already there, let's not accept the second same transform. 1253 } 1254 dec->transforms_seen_ |= (1U << type); 1255 1256 transform->type_ = type; 1257 transform->xsize_ = *xsize; 1258 transform->ysize_ = *ysize; 1259 transform->data_ = NULL; 1260 ++dec->next_transform_; 1261 assert(dec->next_transform_ <= NUM_TRANSFORMS); 1262 1263 switch (type) { 1264 case PREDICTOR_TRANSFORM: 1265 case CROSS_COLOR_TRANSFORM: 1266 transform->bits_ = VP8LReadBits(br, 3) + 2; 1267 ok = DecodeImageStream(VP8LSubSampleSize(transform->xsize_, 1268 transform->bits_), 1269 VP8LSubSampleSize(transform->ysize_, 1270 transform->bits_), 1271 0, dec, &transform->data_); 1272 break; 1273 case COLOR_INDEXING_TRANSFORM: { 1274 const int num_colors = VP8LReadBits(br, 8) + 1; 1275 const int bits = (num_colors > 16) ? 0 1276 : (num_colors > 4) ? 1 1277 : (num_colors > 2) ? 2 1278 : 3; 1279 *xsize = VP8LSubSampleSize(transform->xsize_, bits); 1280 transform->bits_ = bits; 1281 ok = DecodeImageStream(num_colors, 1, 0, dec, &transform->data_); 1282 ok = ok && ExpandColorMap(num_colors, transform); 1283 break; 1284 } 1285 case SUBTRACT_GREEN: 1286 break; 1287 default: 1288 assert(0); // can't happen 1289 break; 1290 } 1291 1292 return ok; 1293 } 1294 1295 // ----------------------------------------------------------------------------- 1296 // VP8LMetadata 1297 1298 static void InitMetadata(VP8LMetadata* const hdr) { 1299 assert(hdr != NULL); 1300 memset(hdr, 0, sizeof(*hdr)); 1301 } 1302 1303 static void ClearMetadata(VP8LMetadata* const hdr) { 1304 assert(hdr != NULL); 1305 1306 WebPSafeFree(hdr->huffman_image_); 1307 WebPSafeFree(hdr->huffman_tables_); 1308 VP8LHtreeGroupsFree(hdr->htree_groups_); 1309 VP8LColorCacheClear(&hdr->color_cache_); 1310 VP8LColorCacheClear(&hdr->saved_color_cache_); 1311 InitMetadata(hdr); 1312 } 1313 1314 // ----------------------------------------------------------------------------- 1315 // VP8LDecoder 1316 1317 VP8LDecoder* VP8LNew(void) { 1318 VP8LDecoder* const dec = (VP8LDecoder*)WebPSafeCalloc(1ULL, sizeof(*dec)); 1319 if (dec == NULL) return NULL; 1320 dec->status_ = VP8_STATUS_OK; 1321 dec->state_ = READ_DIM; 1322 1323 VP8LDspInit(); // Init critical function pointers. 1324 1325 return dec; 1326 } 1327 1328 void VP8LClear(VP8LDecoder* const dec) { 1329 int i; 1330 if (dec == NULL) return; 1331 ClearMetadata(&dec->hdr_); 1332 1333 WebPSafeFree(dec->pixels_); 1334 dec->pixels_ = NULL; 1335 for (i = 0; i < dec->next_transform_; ++i) { 1336 ClearTransform(&dec->transforms_[i]); 1337 } 1338 dec->next_transform_ = 0; 1339 dec->transforms_seen_ = 0; 1340 1341 WebPSafeFree(dec->rescaler_memory); 1342 dec->rescaler_memory = NULL; 1343 1344 dec->output_ = NULL; // leave no trace behind 1345 } 1346 1347 void VP8LDelete(VP8LDecoder* const dec) { 1348 if (dec != NULL) { 1349 VP8LClear(dec); 1350 WebPSafeFree(dec); 1351 } 1352 } 1353 1354 static void UpdateDecoder(VP8LDecoder* const dec, int width, int height) { 1355 VP8LMetadata* const hdr = &dec->hdr_; 1356 const int num_bits = hdr->huffman_subsample_bits_; 1357 dec->width_ = width; 1358 dec->height_ = height; 1359 1360 hdr->huffman_xsize_ = VP8LSubSampleSize(width, num_bits); 1361 hdr->huffman_mask_ = (num_bits == 0) ? ~0 : (1 << num_bits) - 1; 1362 } 1363 1364 static int DecodeImageStream(int xsize, int ysize, 1365 int is_level0, 1366 VP8LDecoder* const dec, 1367 uint32_t** const decoded_data) { 1368 int ok = 1; 1369 int transform_xsize = xsize; 1370 int transform_ysize = ysize; 1371 VP8LBitReader* const br = &dec->br_; 1372 VP8LMetadata* const hdr = &dec->hdr_; 1373 uint32_t* data = NULL; 1374 int color_cache_bits = 0; 1375 1376 // Read the transforms (may recurse). 1377 if (is_level0) { 1378 while (ok && VP8LReadBits(br, 1)) { 1379 ok = ReadTransform(&transform_xsize, &transform_ysize, dec); 1380 } 1381 } 1382 1383 // Color cache 1384 if (ok && VP8LReadBits(br, 1)) { 1385 color_cache_bits = VP8LReadBits(br, 4); 1386 ok = (color_cache_bits >= 1 && color_cache_bits <= MAX_CACHE_BITS); 1387 if (!ok) { 1388 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 1389 goto End; 1390 } 1391 } 1392 1393 // Read the Huffman codes (may recurse). 1394 ok = ok && ReadHuffmanCodes(dec, transform_xsize, transform_ysize, 1395 color_cache_bits, is_level0); 1396 if (!ok) { 1397 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 1398 goto End; 1399 } 1400 1401 // Finish setting up the color-cache 1402 if (color_cache_bits > 0) { 1403 hdr->color_cache_size_ = 1 << color_cache_bits; 1404 if (!VP8LColorCacheInit(&hdr->color_cache_, color_cache_bits)) { 1405 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 1406 ok = 0; 1407 goto End; 1408 } 1409 } else { 1410 hdr->color_cache_size_ = 0; 1411 } 1412 UpdateDecoder(dec, transform_xsize, transform_ysize); 1413 1414 if (is_level0) { // level 0 complete 1415 dec->state_ = READ_HDR; 1416 goto End; 1417 } 1418 1419 { 1420 const uint64_t total_size = (uint64_t)transform_xsize * transform_ysize; 1421 data = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*data)); 1422 if (data == NULL) { 1423 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 1424 ok = 0; 1425 goto End; 1426 } 1427 } 1428 1429 // Use the Huffman trees to decode the LZ77 encoded data. 1430 ok = DecodeImageData(dec, data, transform_xsize, transform_ysize, 1431 transform_ysize, NULL); 1432 ok = ok && !br->eos_; 1433 1434 End: 1435 if (!ok) { 1436 WebPSafeFree(data); 1437 ClearMetadata(hdr); 1438 } else { 1439 if (decoded_data != NULL) { 1440 *decoded_data = data; 1441 } else { 1442 // We allocate image data in this function only for transforms. At level 0 1443 // (that is: not the transforms), we shouldn't have allocated anything. 1444 assert(data == NULL); 1445 assert(is_level0); 1446 } 1447 dec->last_pixel_ = 0; // Reset for future DECODE_DATA_FUNC() calls. 1448 if (!is_level0) ClearMetadata(hdr); // Clean up temporary data behind. 1449 } 1450 return ok; 1451 } 1452 1453 //------------------------------------------------------------------------------ 1454 // Allocate internal buffers dec->pixels_ and dec->argb_cache_. 1455 static int AllocateInternalBuffers32b(VP8LDecoder* const dec, int final_width) { 1456 const uint64_t num_pixels = (uint64_t)dec->width_ * dec->height_; 1457 // Scratch buffer corresponding to top-prediction row for transforming the 1458 // first row in the row-blocks. Not needed for paletted alpha. 1459 const uint64_t cache_top_pixels = (uint16_t)final_width; 1460 // Scratch buffer for temporary BGRA storage. Not needed for paletted alpha. 1461 const uint64_t cache_pixels = (uint64_t)final_width * NUM_ARGB_CACHE_ROWS; 1462 const uint64_t total_num_pixels = 1463 num_pixels + cache_top_pixels + cache_pixels; 1464 1465 assert(dec->width_ <= final_width); 1466 dec->pixels_ = (uint32_t*)WebPSafeMalloc(total_num_pixels, sizeof(uint32_t)); 1467 if (dec->pixels_ == NULL) { 1468 dec->argb_cache_ = NULL; // for sanity check 1469 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 1470 return 0; 1471 } 1472 dec->argb_cache_ = dec->pixels_ + num_pixels + cache_top_pixels; 1473 return 1; 1474 } 1475 1476 static int AllocateInternalBuffers8b(VP8LDecoder* const dec) { 1477 const uint64_t total_num_pixels = (uint64_t)dec->width_ * dec->height_; 1478 dec->argb_cache_ = NULL; // for sanity check 1479 dec->pixels_ = (uint32_t*)WebPSafeMalloc(total_num_pixels, sizeof(uint8_t)); 1480 if (dec->pixels_ == NULL) { 1481 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 1482 return 0; 1483 } 1484 return 1; 1485 } 1486 1487 //------------------------------------------------------------------------------ 1488 1489 // Special row-processing that only stores the alpha data. 1490 static void ExtractAlphaRows(VP8LDecoder* const dec, int last_row) { 1491 int cur_row = dec->last_row_; 1492 int num_rows = last_row - cur_row; 1493 const uint32_t* in = dec->pixels_ + dec->width_ * cur_row; 1494 1495 assert(last_row <= dec->io_->crop_bottom); 1496 while (num_rows > 0) { 1497 const int num_rows_to_process = 1498 (num_rows > NUM_ARGB_CACHE_ROWS) ? NUM_ARGB_CACHE_ROWS : num_rows; 1499 // Extract alpha (which is stored in the green plane). 1500 ALPHDecoder* const alph_dec = (ALPHDecoder*)dec->io_->opaque; 1501 uint8_t* const output = alph_dec->output_; 1502 const int width = dec->io_->width; // the final width (!= dec->width_) 1503 const int cache_pixs = width * num_rows_to_process; 1504 uint8_t* const dst = output + width * cur_row; 1505 const uint32_t* const src = dec->argb_cache_; 1506 ApplyInverseTransforms(dec, num_rows_to_process, in); 1507 WebPExtractGreen(src, dst, cache_pixs); 1508 AlphaApplyFilter(alph_dec, 1509 cur_row, cur_row + num_rows_to_process, dst, width); 1510 num_rows -= num_rows_to_process; 1511 in += num_rows_to_process * dec->width_; 1512 cur_row += num_rows_to_process; 1513 } 1514 assert(cur_row == last_row); 1515 dec->last_row_ = dec->last_out_row_ = last_row; 1516 } 1517 1518 int VP8LDecodeAlphaHeader(ALPHDecoder* const alph_dec, 1519 const uint8_t* const data, size_t data_size) { 1520 int ok = 0; 1521 VP8LDecoder* dec = VP8LNew(); 1522 1523 if (dec == NULL) return 0; 1524 1525 assert(alph_dec != NULL); 1526 alph_dec->vp8l_dec_ = dec; 1527 1528 dec->width_ = alph_dec->width_; 1529 dec->height_ = alph_dec->height_; 1530 dec->io_ = &alph_dec->io_; 1531 dec->io_->opaque = alph_dec; 1532 dec->io_->width = alph_dec->width_; 1533 dec->io_->height = alph_dec->height_; 1534 1535 dec->status_ = VP8_STATUS_OK; 1536 VP8LInitBitReader(&dec->br_, data, data_size); 1537 1538 if (!DecodeImageStream(alph_dec->width_, alph_dec->height_, 1, dec, NULL)) { 1539 goto Err; 1540 } 1541 1542 // Special case: if alpha data uses only the color indexing transform and 1543 // doesn't use color cache (a frequent case), we will use DecodeAlphaData() 1544 // method that only needs allocation of 1 byte per pixel (alpha channel). 1545 if (dec->next_transform_ == 1 && 1546 dec->transforms_[0].type_ == COLOR_INDEXING_TRANSFORM && 1547 Is8bOptimizable(&dec->hdr_)) { 1548 alph_dec->use_8b_decode_ = 1; 1549 ok = AllocateInternalBuffers8b(dec); 1550 } else { 1551 // Allocate internal buffers (note that dec->width_ may have changed here). 1552 alph_dec->use_8b_decode_ = 0; 1553 ok = AllocateInternalBuffers32b(dec, alph_dec->width_); 1554 } 1555 1556 if (!ok) goto Err; 1557 1558 return 1; 1559 1560 Err: 1561 VP8LDelete(alph_dec->vp8l_dec_); 1562 alph_dec->vp8l_dec_ = NULL; 1563 return 0; 1564 } 1565 1566 int VP8LDecodeAlphaImageStream(ALPHDecoder* const alph_dec, int last_row) { 1567 VP8LDecoder* const dec = alph_dec->vp8l_dec_; 1568 assert(dec != NULL); 1569 assert(last_row <= dec->height_); 1570 1571 if (dec->last_row_ >= last_row) { 1572 return 1; // done 1573 } 1574 1575 if (!alph_dec->use_8b_decode_) WebPInitAlphaProcessing(); 1576 1577 // Decode (with special row processing). 1578 return alph_dec->use_8b_decode_ ? 1579 DecodeAlphaData(dec, (uint8_t*)dec->pixels_, dec->width_, dec->height_, 1580 last_row) : 1581 DecodeImageData(dec, dec->pixels_, dec->width_, dec->height_, 1582 last_row, ExtractAlphaRows); 1583 } 1584 1585 //------------------------------------------------------------------------------ 1586 1587 int VP8LDecodeHeader(VP8LDecoder* const dec, VP8Io* const io) { 1588 int width, height, has_alpha; 1589 1590 if (dec == NULL) return 0; 1591 if (io == NULL) { 1592 dec->status_ = VP8_STATUS_INVALID_PARAM; 1593 return 0; 1594 } 1595 1596 dec->io_ = io; 1597 dec->status_ = VP8_STATUS_OK; 1598 VP8LInitBitReader(&dec->br_, io->data, io->data_size); 1599 if (!ReadImageInfo(&dec->br_, &width, &height, &has_alpha)) { 1600 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 1601 goto Error; 1602 } 1603 dec->state_ = READ_DIM; 1604 io->width = width; 1605 io->height = height; 1606 1607 if (!DecodeImageStream(width, height, 1, dec, NULL)) goto Error; 1608 return 1; 1609 1610 Error: 1611 VP8LClear(dec); 1612 assert(dec->status_ != VP8_STATUS_OK); 1613 return 0; 1614 } 1615 1616 int VP8LDecodeImage(VP8LDecoder* const dec) { 1617 VP8Io* io = NULL; 1618 WebPDecParams* params = NULL; 1619 1620 // Sanity checks. 1621 if (dec == NULL) return 0; 1622 1623 assert(dec->hdr_.huffman_tables_ != NULL); 1624 assert(dec->hdr_.htree_groups_ != NULL); 1625 assert(dec->hdr_.num_htree_groups_ > 0); 1626 1627 io = dec->io_; 1628 assert(io != NULL); 1629 params = (WebPDecParams*)io->opaque; 1630 assert(params != NULL); 1631 1632 // Initialization. 1633 if (dec->state_ != READ_DATA) { 1634 dec->output_ = params->output; 1635 assert(dec->output_ != NULL); 1636 1637 if (!WebPIoInitFromOptions(params->options, io, MODE_BGRA)) { 1638 dec->status_ = VP8_STATUS_INVALID_PARAM; 1639 goto Err; 1640 } 1641 1642 if (!AllocateInternalBuffers32b(dec, io->width)) goto Err; 1643 1644 #if !defined(WEBP_REDUCE_SIZE) 1645 if (io->use_scaling && !AllocateAndInitRescaler(dec, io)) goto Err; 1646 1647 if (io->use_scaling || WebPIsPremultipliedMode(dec->output_->colorspace)) { 1648 // need the alpha-multiply functions for premultiplied output or rescaling 1649 WebPInitAlphaProcessing(); 1650 } 1651 #else 1652 if (io->use_scaling) { 1653 dec->status_ = VP8_STATUS_INVALID_PARAM; 1654 goto Err; 1655 } 1656 #endif 1657 if (!WebPIsRGBMode(dec->output_->colorspace)) { 1658 WebPInitConvertARGBToYUV(); 1659 if (dec->output_->u.YUVA.a != NULL) WebPInitAlphaProcessing(); 1660 } 1661 if (dec->incremental_) { 1662 if (dec->hdr_.color_cache_size_ > 0 && 1663 dec->hdr_.saved_color_cache_.colors_ == NULL) { 1664 if (!VP8LColorCacheInit(&dec->hdr_.saved_color_cache_, 1665 dec->hdr_.color_cache_.hash_bits_)) { 1666 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 1667 goto Err; 1668 } 1669 } 1670 } 1671 dec->state_ = READ_DATA; 1672 } 1673 1674 // Decode. 1675 if (!DecodeImageData(dec, dec->pixels_, dec->width_, dec->height_, 1676 io->crop_bottom, ProcessRows)) { 1677 goto Err; 1678 } 1679 1680 params->last_y = dec->last_out_row_; 1681 return 1; 1682 1683 Err: 1684 VP8LClear(dec); 1685 assert(dec->status_ != VP8_STATUS_OK); 1686 return 0; 1687 } 1688 1689 //------------------------------------------------------------------------------ 1690
