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