1 // Copyright 2012 Google Inc. All Rights Reserved. 2 // 3 // This code is licensed under the same terms as WebM: 4 // Software License Agreement: http://www.webmproject.org/license/software/ 5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/ 6 // ----------------------------------------------------------------------------- 7 // 8 // main entry for the decoder 9 // 10 // Authors: Vikas Arora (vikaas.arora (at) gmail.com) 11 // Jyrki Alakuijala (jyrki (at) google.com) 12 13 #include <stdio.h> 14 #include <stdlib.h> 15 #include "./vp8li.h" 16 #include "../dsp/lossless.h" 17 #include "../dsp/yuv.h" 18 #include "../utils/huffman.h" 19 #include "../utils/utils.h" 20 21 #if defined(__cplusplus) || defined(c_plusplus) 22 extern "C" { 23 #endif 24 25 #define NUM_ARGB_CACHE_ROWS 16 26 27 static const int kCodeLengthLiterals = 16; 28 static const int kCodeLengthRepeatCode = 16; 29 static const int kCodeLengthExtraBits[3] = { 2, 3, 7 }; 30 static const int kCodeLengthRepeatOffsets[3] = { 3, 3, 11 }; 31 32 // ----------------------------------------------------------------------------- 33 // Five Huffman codes are used at each meta code: 34 // 1. green + length prefix codes + color cache codes, 35 // 2. alpha, 36 // 3. red, 37 // 4. blue, and, 38 // 5. distance prefix codes. 39 typedef enum { 40 GREEN = 0, 41 RED = 1, 42 BLUE = 2, 43 ALPHA = 3, 44 DIST = 4 45 } HuffIndex; 46 47 static const uint16_t kAlphabetSize[HUFFMAN_CODES_PER_META_CODE] = { 48 NUM_LITERAL_CODES + NUM_LENGTH_CODES, 49 NUM_LITERAL_CODES, NUM_LITERAL_CODES, NUM_LITERAL_CODES, 50 NUM_DISTANCE_CODES 51 }; 52 53 54 #define NUM_CODE_LENGTH_CODES 19 55 static const uint8_t kCodeLengthCodeOrder[NUM_CODE_LENGTH_CODES] = { 56 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 57 }; 58 59 #define CODE_TO_PLANE_CODES 120 60 static const uint8_t code_to_plane_lut[CODE_TO_PLANE_CODES] = { 61 0x18, 0x07, 0x17, 0x19, 0x28, 0x06, 0x27, 0x29, 0x16, 0x1a, 62 0x26, 0x2a, 0x38, 0x05, 0x37, 0x39, 0x15, 0x1b, 0x36, 0x3a, 63 0x25, 0x2b, 0x48, 0x04, 0x47, 0x49, 0x14, 0x1c, 0x35, 0x3b, 64 0x46, 0x4a, 0x24, 0x2c, 0x58, 0x45, 0x4b, 0x34, 0x3c, 0x03, 65 0x57, 0x59, 0x13, 0x1d, 0x56, 0x5a, 0x23, 0x2d, 0x44, 0x4c, 66 0x55, 0x5b, 0x33, 0x3d, 0x68, 0x02, 0x67, 0x69, 0x12, 0x1e, 67 0x66, 0x6a, 0x22, 0x2e, 0x54, 0x5c, 0x43, 0x4d, 0x65, 0x6b, 68 0x32, 0x3e, 0x78, 0x01, 0x77, 0x79, 0x53, 0x5d, 0x11, 0x1f, 69 0x64, 0x6c, 0x42, 0x4e, 0x76, 0x7a, 0x21, 0x2f, 0x75, 0x7b, 70 0x31, 0x3f, 0x63, 0x6d, 0x52, 0x5e, 0x00, 0x74, 0x7c, 0x41, 71 0x4f, 0x10, 0x20, 0x62, 0x6e, 0x30, 0x73, 0x7d, 0x51, 0x5f, 72 0x40, 0x72, 0x7e, 0x61, 0x6f, 0x50, 0x71, 0x7f, 0x60, 0x70 73 }; 74 75 static int DecodeImageStream(int xsize, int ysize, 76 int is_level0, 77 VP8LDecoder* const dec, 78 uint32_t** const decoded_data); 79 80 //------------------------------------------------------------------------------ 81 82 int VP8LCheckSignature(const uint8_t* const data, size_t size) { 83 return (size >= 1) && (data[0] == VP8L_MAGIC_BYTE); 84 } 85 86 static int ReadImageInfo(VP8LBitReader* const br, 87 int* const width, int* const height, 88 int* const has_alpha) { 89 const uint8_t signature = VP8LReadBits(br, 8); 90 if (!VP8LCheckSignature(&signature, 1)) { 91 return 0; 92 } 93 *width = VP8LReadBits(br, VP8L_IMAGE_SIZE_BITS) + 1; 94 *height = VP8LReadBits(br, VP8L_IMAGE_SIZE_BITS) + 1; 95 *has_alpha = VP8LReadBits(br, 1); 96 VP8LReadBits(br, VP8L_VERSION_BITS); // Read/ignore the version number. 97 return 1; 98 } 99 100 int VP8LGetInfo(const uint8_t* data, size_t data_size, 101 int* const width, int* const height, int* const has_alpha) { 102 if (data == NULL || data_size < VP8L_FRAME_HEADER_SIZE) { 103 return 0; // not enough data 104 } else { 105 int w, h, a; 106 VP8LBitReader br; 107 VP8LInitBitReader(&br, data, data_size); 108 if (!ReadImageInfo(&br, &w, &h, &a)) { 109 return 0; 110 } 111 if (width != NULL) *width = w; 112 if (height != NULL) *height = h; 113 if (has_alpha != NULL) *has_alpha = a; 114 return 1; 115 } 116 } 117 118 //------------------------------------------------------------------------------ 119 120 static WEBP_INLINE int GetCopyDistance(int distance_symbol, 121 VP8LBitReader* const br) { 122 int extra_bits, offset; 123 if (distance_symbol < 4) { 124 return distance_symbol + 1; 125 } 126 extra_bits = (distance_symbol - 2) >> 1; 127 offset = (2 + (distance_symbol & 1)) << extra_bits; 128 return offset + VP8LReadBits(br, extra_bits) + 1; 129 } 130 131 static WEBP_INLINE int GetCopyLength(int length_symbol, 132 VP8LBitReader* const br) { 133 // Length and distance prefixes are encoded the same way. 134 return GetCopyDistance(length_symbol, br); 135 } 136 137 static WEBP_INLINE int PlaneCodeToDistance(int xsize, int plane_code) { 138 if (plane_code > CODE_TO_PLANE_CODES) { 139 return plane_code - CODE_TO_PLANE_CODES; 140 } else { 141 const int dist_code = code_to_plane_lut[plane_code - 1]; 142 const int yoffset = dist_code >> 4; 143 const int xoffset = 8 - (dist_code & 0xf); 144 const int dist = yoffset * xsize + xoffset; 145 return (dist >= 1) ? dist : 1; 146 } 147 } 148 149 //------------------------------------------------------------------------------ 150 // Decodes the next Huffman code from bit-stream. 151 // FillBitWindow(br) needs to be called at minimum every second call 152 // to ReadSymbol, in order to pre-fetch enough bits. 153 static WEBP_INLINE int ReadSymbol(const HuffmanTree* tree, 154 VP8LBitReader* const br) { 155 const HuffmanTreeNode* node = tree->root_; 156 int num_bits = 0; 157 uint32_t bits = VP8LPrefetchBits(br); 158 assert(node != NULL); 159 while (!HuffmanTreeNodeIsLeaf(node)) { 160 node = HuffmanTreeNextNode(node, bits & 1); 161 bits >>= 1; 162 ++num_bits; 163 } 164 VP8LDiscardBits(br, num_bits); 165 return node->symbol_; 166 } 167 168 static int ReadHuffmanCodeLengths( 169 VP8LDecoder* const dec, const int* const code_length_code_lengths, 170 int num_symbols, int* const code_lengths) { 171 int ok = 0; 172 VP8LBitReader* const br = &dec->br_; 173 int symbol; 174 int max_symbol; 175 int prev_code_len = DEFAULT_CODE_LENGTH; 176 HuffmanTree tree; 177 178 if (!HuffmanTreeBuildImplicit(&tree, code_length_code_lengths, 179 NUM_CODE_LENGTH_CODES)) { 180 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 181 return 0; 182 } 183 184 if (VP8LReadBits(br, 1)) { // use length 185 const int length_nbits = 2 + 2 * VP8LReadBits(br, 3); 186 max_symbol = 2 + VP8LReadBits(br, length_nbits); 187 if (max_symbol > num_symbols) { 188 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 189 goto End; 190 } 191 } else { 192 max_symbol = num_symbols; 193 } 194 195 symbol = 0; 196 while (symbol < num_symbols) { 197 int code_len; 198 if (max_symbol-- == 0) break; 199 VP8LFillBitWindow(br); 200 code_len = ReadSymbol(&tree, br); 201 if (code_len < kCodeLengthLiterals) { 202 code_lengths[symbol++] = code_len; 203 if (code_len != 0) prev_code_len = code_len; 204 } else { 205 const int use_prev = (code_len == kCodeLengthRepeatCode); 206 const int slot = code_len - kCodeLengthLiterals; 207 const int extra_bits = kCodeLengthExtraBits[slot]; 208 const int repeat_offset = kCodeLengthRepeatOffsets[slot]; 209 int repeat = VP8LReadBits(br, extra_bits) + repeat_offset; 210 if (symbol + repeat > num_symbols) { 211 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 212 goto End; 213 } else { 214 const int length = use_prev ? prev_code_len : 0; 215 while (repeat-- > 0) code_lengths[symbol++] = length; 216 } 217 } 218 } 219 ok = 1; 220 221 End: 222 HuffmanTreeRelease(&tree); 223 return ok; 224 } 225 226 static int ReadHuffmanCode(int alphabet_size, VP8LDecoder* const dec, 227 HuffmanTree* const tree) { 228 int ok = 0; 229 VP8LBitReader* const br = &dec->br_; 230 const int simple_code = VP8LReadBits(br, 1); 231 232 if (simple_code) { // Read symbols, codes & code lengths directly. 233 int symbols[2]; 234 int codes[2]; 235 int code_lengths[2]; 236 const int num_symbols = VP8LReadBits(br, 1) + 1; 237 const int first_symbol_len_code = VP8LReadBits(br, 1); 238 // The first code is either 1 bit or 8 bit code. 239 symbols[0] = VP8LReadBits(br, (first_symbol_len_code == 0) ? 1 : 8); 240 codes[0] = 0; 241 code_lengths[0] = num_symbols - 1; 242 // The second code (if present), is always 8 bit long. 243 if (num_symbols == 2) { 244 symbols[1] = VP8LReadBits(br, 8); 245 codes[1] = 1; 246 code_lengths[1] = num_symbols - 1; 247 } 248 ok = HuffmanTreeBuildExplicit(tree, code_lengths, codes, symbols, 249 alphabet_size, num_symbols); 250 } else { // Decode Huffman-coded code lengths. 251 int* code_lengths = NULL; 252 int i; 253 int code_length_code_lengths[NUM_CODE_LENGTH_CODES] = { 0 }; 254 const int num_codes = VP8LReadBits(br, 4) + 4; 255 if (num_codes > NUM_CODE_LENGTH_CODES) { 256 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 257 return 0; 258 } 259 260 code_lengths = 261 (int*)WebPSafeCalloc((uint64_t)alphabet_size, sizeof(*code_lengths)); 262 if (code_lengths == NULL) { 263 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 264 return 0; 265 } 266 267 for (i = 0; i < num_codes; ++i) { 268 code_length_code_lengths[kCodeLengthCodeOrder[i]] = VP8LReadBits(br, 3); 269 } 270 ok = ReadHuffmanCodeLengths(dec, code_length_code_lengths, alphabet_size, 271 code_lengths); 272 if (ok) { 273 ok = HuffmanTreeBuildImplicit(tree, code_lengths, alphabet_size); 274 } 275 free(code_lengths); 276 } 277 ok = ok && !br->error_; 278 if (!ok) { 279 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 280 return 0; 281 } 282 return 1; 283 } 284 285 static void DeleteHtreeGroups(HTreeGroup* htree_groups, int num_htree_groups) { 286 if (htree_groups != NULL) { 287 int i, j; 288 for (i = 0; i < num_htree_groups; ++i) { 289 HuffmanTree* const htrees = htree_groups[i].htrees_; 290 for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) { 291 HuffmanTreeRelease(&htrees[j]); 292 } 293 } 294 free(htree_groups); 295 } 296 } 297 298 static int ReadHuffmanCodes(VP8LDecoder* const dec, int xsize, int ysize, 299 int color_cache_bits, int allow_recursion) { 300 int i, j; 301 VP8LBitReader* const br = &dec->br_; 302 VP8LMetadata* const hdr = &dec->hdr_; 303 uint32_t* huffman_image = NULL; 304 HTreeGroup* htree_groups = NULL; 305 int num_htree_groups = 1; 306 307 if (allow_recursion && VP8LReadBits(br, 1)) { 308 // use meta Huffman codes. 309 const int huffman_precision = VP8LReadBits(br, 3) + 2; 310 const int huffman_xsize = VP8LSubSampleSize(xsize, huffman_precision); 311 const int huffman_ysize = VP8LSubSampleSize(ysize, huffman_precision); 312 const int huffman_pixs = huffman_xsize * huffman_ysize; 313 if (!DecodeImageStream(huffman_xsize, huffman_ysize, 0, dec, 314 &huffman_image)) { 315 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 316 goto Error; 317 } 318 hdr->huffman_subsample_bits_ = huffman_precision; 319 for (i = 0; i < huffman_pixs; ++i) { 320 // The huffman data is stored in red and green bytes. 321 const int group = (huffman_image[i] >> 8) & 0xffff; 322 huffman_image[i] = group; 323 if (group >= num_htree_groups) { 324 num_htree_groups = group + 1; 325 } 326 } 327 } 328 329 if (br->error_) goto Error; 330 331 assert(num_htree_groups <= 0x10000); 332 htree_groups = 333 (HTreeGroup*)WebPSafeCalloc((uint64_t)num_htree_groups, 334 sizeof(*htree_groups)); 335 if (htree_groups == NULL) { 336 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 337 goto Error; 338 } 339 340 for (i = 0; i < num_htree_groups; ++i) { 341 HuffmanTree* const htrees = htree_groups[i].htrees_; 342 for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) { 343 int alphabet_size = kAlphabetSize[j]; 344 if (j == 0 && color_cache_bits > 0) { 345 alphabet_size += 1 << color_cache_bits; 346 } 347 if (!ReadHuffmanCode(alphabet_size, dec, htrees + j)) goto Error; 348 } 349 } 350 351 // All OK. Finalize pointers and return. 352 hdr->huffman_image_ = huffman_image; 353 hdr->num_htree_groups_ = num_htree_groups; 354 hdr->htree_groups_ = htree_groups; 355 return 1; 356 357 Error: 358 free(huffman_image); 359 DeleteHtreeGroups(htree_groups, num_htree_groups); 360 return 0; 361 } 362 363 //------------------------------------------------------------------------------ 364 // Scaling. 365 366 static int AllocateAndInitRescaler(VP8LDecoder* const dec, VP8Io* const io) { 367 const int num_channels = 4; 368 const int in_width = io->mb_w; 369 const int out_width = io->scaled_width; 370 const int in_height = io->mb_h; 371 const int out_height = io->scaled_height; 372 const uint64_t work_size = 2 * num_channels * (uint64_t)out_width; 373 int32_t* work; // Rescaler work area. 374 const uint64_t scaled_data_size = num_channels * (uint64_t)out_width; 375 uint32_t* scaled_data; // Temporary storage for scaled BGRA data. 376 const uint64_t memory_size = sizeof(*dec->rescaler) + 377 work_size * sizeof(*work) + 378 scaled_data_size * sizeof(*scaled_data); 379 uint8_t* memory = (uint8_t*)WebPSafeCalloc(memory_size, sizeof(*memory)); 380 if (memory == NULL) { 381 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 382 return 0; 383 } 384 assert(dec->rescaler_memory == NULL); 385 dec->rescaler_memory = memory; 386 387 dec->rescaler = (WebPRescaler*)memory; 388 memory += sizeof(*dec->rescaler); 389 work = (int32_t*)memory; 390 memory += work_size * sizeof(*work); 391 scaled_data = (uint32_t*)memory; 392 393 WebPRescalerInit(dec->rescaler, in_width, in_height, (uint8_t*)scaled_data, 394 out_width, out_height, 0, num_channels, 395 in_width, out_width, in_height, out_height, work); 396 return 1; 397 } 398 399 //------------------------------------------------------------------------------ 400 // Export to ARGB 401 402 // We have special "export" function since we need to convert from BGRA 403 static int Export(WebPRescaler* const rescaler, WEBP_CSP_MODE colorspace, 404 int rgba_stride, uint8_t* const rgba) { 405 const uint32_t* const src = (const uint32_t*)rescaler->dst; 406 const int dst_width = rescaler->dst_width; 407 int num_lines_out = 0; 408 while (WebPRescalerHasPendingOutput(rescaler)) { 409 uint8_t* const dst = rgba + num_lines_out * rgba_stride; 410 WebPRescalerExportRow(rescaler); 411 VP8LConvertFromBGRA(src, dst_width, colorspace, dst); 412 ++num_lines_out; 413 } 414 return num_lines_out; 415 } 416 417 // Emit scaled rows. 418 static int EmitRescaledRows(const VP8LDecoder* const dec, 419 const uint32_t* const data, int in_stride, int mb_h, 420 uint8_t* const out, int out_stride) { 421 const WEBP_CSP_MODE colorspace = dec->output_->colorspace; 422 const uint8_t* const in = (const uint8_t*)data; 423 int num_lines_in = 0; 424 int num_lines_out = 0; 425 while (num_lines_in < mb_h) { 426 const uint8_t* const row_in = in + num_lines_in * in_stride; 427 uint8_t* const row_out = out + num_lines_out * out_stride; 428 num_lines_in += WebPRescalerImport(dec->rescaler, mb_h - num_lines_in, 429 row_in, in_stride); 430 num_lines_out += Export(dec->rescaler, colorspace, out_stride, row_out); 431 } 432 return num_lines_out; 433 } 434 435 // Emit rows without any scaling. 436 static int EmitRows(WEBP_CSP_MODE colorspace, 437 const uint32_t* const data, int in_stride, 438 int mb_w, int mb_h, 439 uint8_t* const out, int out_stride) { 440 int lines = mb_h; 441 const uint8_t* row_in = (const uint8_t*)data; 442 uint8_t* row_out = out; 443 while (lines-- > 0) { 444 VP8LConvertFromBGRA((const uint32_t*)row_in, mb_w, colorspace, row_out); 445 row_in += in_stride; 446 row_out += out_stride; 447 } 448 return mb_h; // Num rows out == num rows in. 449 } 450 451 //------------------------------------------------------------------------------ 452 // Export to YUVA 453 454 static void ConvertToYUVA(const uint32_t* const src, int width, int y_pos, 455 const WebPDecBuffer* const output) { 456 const WebPYUVABuffer* const buf = &output->u.YUVA; 457 // first, the luma plane 458 { 459 int i; 460 uint8_t* const y = buf->y + y_pos * buf->y_stride; 461 for (i = 0; i < width; ++i) { 462 const uint32_t p = src[i]; 463 y[i] = VP8RGBToY((p >> 16) & 0xff, (p >> 8) & 0xff, (p >> 0) & 0xff); 464 } 465 } 466 467 // then U/V planes 468 { 469 uint8_t* const u = buf->u + (y_pos >> 1) * buf->u_stride; 470 uint8_t* const v = buf->v + (y_pos >> 1) * buf->v_stride; 471 const int uv_width = width >> 1; 472 int i; 473 for (i = 0; i < uv_width; ++i) { 474 const uint32_t v0 = src[2 * i + 0]; 475 const uint32_t v1 = src[2 * i + 1]; 476 // VP8RGBToU/V expects four accumulated pixels. Hence we need to 477 // scale r/g/b value by a factor 2. We just shift v0/v1 one bit less. 478 const int r = ((v0 >> 15) & 0x1fe) + ((v1 >> 15) & 0x1fe); 479 const int g = ((v0 >> 7) & 0x1fe) + ((v1 >> 7) & 0x1fe); 480 const int b = ((v0 << 1) & 0x1fe) + ((v1 << 1) & 0x1fe); 481 if (!(y_pos & 1)) { // even lines: store values 482 u[i] = VP8RGBToU(r, g, b); 483 v[i] = VP8RGBToV(r, g, b); 484 } else { // odd lines: average with previous values 485 const int tmp_u = VP8RGBToU(r, g, b); 486 const int tmp_v = VP8RGBToV(r, g, b); 487 // Approximated average-of-four. But it's an acceptable diff. 488 u[i] = (u[i] + tmp_u + 1) >> 1; 489 v[i] = (v[i] + tmp_v + 1) >> 1; 490 } 491 } 492 if (width & 1) { // last pixel 493 const uint32_t v0 = src[2 * i + 0]; 494 const int r = (v0 >> 14) & 0x3fc; 495 const int g = (v0 >> 6) & 0x3fc; 496 const int b = (v0 << 2) & 0x3fc; 497 if (!(y_pos & 1)) { // even lines 498 u[i] = VP8RGBToU(r, g, b); 499 v[i] = VP8RGBToV(r, g, b); 500 } else { // odd lines (note: we could just skip this) 501 const int tmp_u = VP8RGBToU(r, g, b); 502 const int tmp_v = VP8RGBToV(r, g, b); 503 u[i] = (u[i] + tmp_u + 1) >> 1; 504 v[i] = (v[i] + tmp_v + 1) >> 1; 505 } 506 } 507 } 508 // Lastly, store alpha if needed. 509 if (buf->a != NULL) { 510 int i; 511 uint8_t* const a = buf->a + y_pos * buf->a_stride; 512 for (i = 0; i < width; ++i) a[i] = (src[i] >> 24); 513 } 514 } 515 516 static int ExportYUVA(const VP8LDecoder* const dec, int y_pos) { 517 WebPRescaler* const rescaler = dec->rescaler; 518 const uint32_t* const src = (const uint32_t*)rescaler->dst; 519 const int dst_width = rescaler->dst_width; 520 int num_lines_out = 0; 521 while (WebPRescalerHasPendingOutput(rescaler)) { 522 WebPRescalerExportRow(rescaler); 523 ConvertToYUVA(src, dst_width, y_pos, dec->output_); 524 ++y_pos; 525 ++num_lines_out; 526 } 527 return num_lines_out; 528 } 529 530 static int EmitRescaledRowsYUVA(const VP8LDecoder* const dec, 531 const uint32_t* const data, 532 int in_stride, int mb_h) { 533 const uint8_t* const in = (const uint8_t*)data; 534 int num_lines_in = 0; 535 int y_pos = dec->last_out_row_; 536 while (num_lines_in < mb_h) { 537 const uint8_t* const row_in = in + num_lines_in * in_stride; 538 num_lines_in += WebPRescalerImport(dec->rescaler, mb_h - num_lines_in, 539 row_in, in_stride); 540 y_pos += ExportYUVA(dec, y_pos); 541 } 542 return y_pos; 543 } 544 545 static int EmitRowsYUVA(const VP8LDecoder* const dec, 546 const uint32_t* const data, int in_stride, 547 int mb_w, int num_rows) { 548 int y_pos = dec->last_out_row_; 549 const uint8_t* row_in = (const uint8_t*)data; 550 while (num_rows-- > 0) { 551 ConvertToYUVA((const uint32_t*)row_in, mb_w, y_pos, dec->output_); 552 row_in += in_stride; 553 ++y_pos; 554 } 555 return y_pos; 556 } 557 558 //------------------------------------------------------------------------------ 559 // Cropping. 560 561 // Sets io->mb_y, io->mb_h & io->mb_w according to start row, end row and 562 // crop options. Also updates the input data pointer, so that it points to the 563 // start of the cropped window. 564 // Note that 'pixel_stride' is in units of 'uint32_t' (and not 'bytes). 565 // Returns true if the crop window is not empty. 566 static int SetCropWindow(VP8Io* const io, int y_start, int y_end, 567 const uint32_t** const in_data, int pixel_stride) { 568 assert(y_start < y_end); 569 assert(io->crop_left < io->crop_right); 570 if (y_end > io->crop_bottom) { 571 y_end = io->crop_bottom; // make sure we don't overflow on last row. 572 } 573 if (y_start < io->crop_top) { 574 const int delta = io->crop_top - y_start; 575 y_start = io->crop_top; 576 *in_data += pixel_stride * delta; 577 } 578 if (y_start >= y_end) return 0; // Crop window is empty. 579 580 *in_data += io->crop_left; 581 582 io->mb_y = y_start - io->crop_top; 583 io->mb_w = io->crop_right - io->crop_left; 584 io->mb_h = y_end - y_start; 585 return 1; // Non-empty crop window. 586 } 587 588 //------------------------------------------------------------------------------ 589 590 static WEBP_INLINE int GetMetaIndex( 591 const uint32_t* const image, int xsize, int bits, int x, int y) { 592 if (bits == 0) return 0; 593 return image[xsize * (y >> bits) + (x >> bits)]; 594 } 595 596 static WEBP_INLINE HTreeGroup* GetHtreeGroupForPos(VP8LMetadata* const hdr, 597 int x, int y) { 598 const int meta_index = GetMetaIndex(hdr->huffman_image_, hdr->huffman_xsize_, 599 hdr->huffman_subsample_bits_, x, y); 600 assert(meta_index < hdr->num_htree_groups_); 601 return hdr->htree_groups_ + meta_index; 602 } 603 604 //------------------------------------------------------------------------------ 605 // Main loop, with custom row-processing function 606 607 typedef void (*ProcessRowsFunc)(VP8LDecoder* const dec, int row); 608 609 static void ApplyInverseTransforms(VP8LDecoder* const dec, int num_rows, 610 const uint32_t* const rows) { 611 int n = dec->next_transform_; 612 const int cache_pixs = dec->width_ * num_rows; 613 const int start_row = dec->last_row_; 614 const int end_row = start_row + num_rows; 615 const uint32_t* rows_in = rows; 616 uint32_t* const rows_out = dec->argb_cache_; 617 618 // Inverse transforms. 619 // TODO: most transforms only need to operate on the cropped region only. 620 memcpy(rows_out, rows_in, cache_pixs * sizeof(*rows_out)); 621 while (n-- > 0) { 622 VP8LTransform* const transform = &dec->transforms_[n]; 623 VP8LInverseTransform(transform, start_row, end_row, rows_in, rows_out); 624 rows_in = rows_out; 625 } 626 } 627 628 // Processes (transforms, scales & color-converts) the rows decoded after the 629 // last call. 630 static void ProcessRows(VP8LDecoder* const dec, int row) { 631 const uint32_t* const rows = dec->argb_ + dec->width_ * dec->last_row_; 632 const int num_rows = row - dec->last_row_; 633 634 if (num_rows <= 0) return; // Nothing to be done. 635 ApplyInverseTransforms(dec, num_rows, rows); 636 637 // Emit output. 638 { 639 VP8Io* const io = dec->io_; 640 const uint32_t* rows_data = dec->argb_cache_; 641 if (!SetCropWindow(io, dec->last_row_, row, &rows_data, io->width)) { 642 // Nothing to output (this time). 643 } else { 644 const WebPDecBuffer* const output = dec->output_; 645 const int in_stride = io->width * sizeof(*rows_data); 646 if (output->colorspace < MODE_YUV) { // convert to RGBA 647 const WebPRGBABuffer* const buf = &output->u.RGBA; 648 uint8_t* const rgba = buf->rgba + dec->last_out_row_ * buf->stride; 649 const int num_rows_out = io->use_scaling ? 650 EmitRescaledRows(dec, rows_data, in_stride, io->mb_h, 651 rgba, buf->stride) : 652 EmitRows(output->colorspace, rows_data, in_stride, 653 io->mb_w, io->mb_h, rgba, buf->stride); 654 // Update 'last_out_row_'. 655 dec->last_out_row_ += num_rows_out; 656 } else { // convert to YUVA 657 dec->last_out_row_ = io->use_scaling ? 658 EmitRescaledRowsYUVA(dec, rows_data, in_stride, io->mb_h) : 659 EmitRowsYUVA(dec, rows_data, in_stride, io->mb_w, io->mb_h); 660 } 661 assert(dec->last_out_row_ <= output->height); 662 } 663 } 664 665 // Update 'last_row_'. 666 dec->last_row_ = row; 667 assert(dec->last_row_ <= dec->height_); 668 } 669 670 static int DecodeImageData(VP8LDecoder* const dec, 671 uint32_t* const data, int width, int height, 672 ProcessRowsFunc process_func) { 673 int ok = 1; 674 int col = 0, row = 0; 675 VP8LBitReader* const br = &dec->br_; 676 VP8LMetadata* const hdr = &dec->hdr_; 677 HTreeGroup* htree_group = hdr->htree_groups_; 678 uint32_t* src = data; 679 uint32_t* last_cached = data; 680 uint32_t* const src_end = data + width * height; 681 const int len_code_limit = NUM_LITERAL_CODES + NUM_LENGTH_CODES; 682 const int color_cache_limit = len_code_limit + hdr->color_cache_size_; 683 VP8LColorCache* const color_cache = 684 (hdr->color_cache_size_ > 0) ? &hdr->color_cache_ : NULL; 685 const int mask = hdr->huffman_mask_; 686 687 assert(htree_group != NULL); 688 689 while (!br->eos_ && src < src_end) { 690 int code; 691 // Only update when changing tile. Note we could use the following test: 692 // if "((((prev_col ^ col) | prev_row ^ row)) > mask)" -> tile changed 693 // but that's actually slower and requires storing the previous col/row 694 if ((col & mask) == 0) { 695 htree_group = GetHtreeGroupForPos(hdr, col, row); 696 } 697 VP8LFillBitWindow(br); 698 code = ReadSymbol(&htree_group->htrees_[GREEN], br); 699 if (code < NUM_LITERAL_CODES) { // Literal. 700 int red, green, blue, alpha; 701 red = ReadSymbol(&htree_group->htrees_[RED], br); 702 green = code; 703 VP8LFillBitWindow(br); 704 blue = ReadSymbol(&htree_group->htrees_[BLUE], br); 705 alpha = ReadSymbol(&htree_group->htrees_[ALPHA], br); 706 *src = (alpha << 24) + (red << 16) + (green << 8) + blue; 707 AdvanceByOne: 708 ++src; 709 ++col; 710 if (col >= width) { 711 col = 0; 712 ++row; 713 if ((process_func != NULL) && (row % NUM_ARGB_CACHE_ROWS == 0)) { 714 process_func(dec, row); 715 } 716 if (color_cache != NULL) { 717 while (last_cached < src) { 718 VP8LColorCacheInsert(color_cache, *last_cached++); 719 } 720 } 721 } 722 } else if (code < len_code_limit) { // Backward reference 723 int dist_code, dist; 724 const int length_sym = code - NUM_LITERAL_CODES; 725 const int length = GetCopyLength(length_sym, br); 726 const int dist_symbol = ReadSymbol(&htree_group->htrees_[DIST], br); 727 VP8LFillBitWindow(br); 728 dist_code = GetCopyDistance(dist_symbol, br); 729 dist = PlaneCodeToDistance(width, dist_code); 730 if (src - data < dist || src_end - src < length) { 731 ok = 0; 732 goto End; 733 } 734 { 735 int i; 736 for (i = 0; i < length; ++i) src[i] = src[i - dist]; 737 src += length; 738 } 739 col += length; 740 while (col >= width) { 741 col -= width; 742 ++row; 743 if ((process_func != NULL) && (row % NUM_ARGB_CACHE_ROWS == 0)) { 744 process_func(dec, row); 745 } 746 } 747 if (src < src_end) { 748 htree_group = GetHtreeGroupForPos(hdr, col, row); 749 if (color_cache != NULL) { 750 while (last_cached < src) { 751 VP8LColorCacheInsert(color_cache, *last_cached++); 752 } 753 } 754 } 755 } else if (code < color_cache_limit) { // Color cache. 756 const int key = code - len_code_limit; 757 assert(color_cache != NULL); 758 while (last_cached < src) { 759 VP8LColorCacheInsert(color_cache, *last_cached++); 760 } 761 *src = VP8LColorCacheLookup(color_cache, key); 762 goto AdvanceByOne; 763 } else { // Not reached. 764 ok = 0; 765 goto End; 766 } 767 ok = !br->error_; 768 if (!ok) goto End; 769 } 770 // Process the remaining rows corresponding to last row-block. 771 if (process_func != NULL) process_func(dec, row); 772 773 End: 774 if (br->error_ || !ok || (br->eos_ && src < src_end)) { 775 ok = 0; 776 dec->status_ = (!br->eos_) ? 777 VP8_STATUS_BITSTREAM_ERROR : VP8_STATUS_SUSPENDED; 778 } else if (src == src_end) { 779 dec->state_ = READ_DATA; 780 } 781 782 return ok; 783 } 784 785 // ----------------------------------------------------------------------------- 786 // VP8LTransform 787 788 static void ClearTransform(VP8LTransform* const transform) { 789 free(transform->data_); 790 transform->data_ = NULL; 791 } 792 793 // For security reason, we need to remap the color map to span 794 // the total possible bundled values, and not just the num_colors. 795 static int ExpandColorMap(int num_colors, VP8LTransform* const transform) { 796 int i; 797 const int final_num_colors = 1 << (8 >> transform->bits_); 798 uint32_t* const new_color_map = 799 (uint32_t*)WebPSafeMalloc((uint64_t)final_num_colors, 800 sizeof(*new_color_map)); 801 if (new_color_map == NULL) { 802 return 0; 803 } else { 804 uint8_t* const data = (uint8_t*)transform->data_; 805 uint8_t* const new_data = (uint8_t*)new_color_map; 806 new_color_map[0] = transform->data_[0]; 807 for (i = 4; i < 4 * num_colors; ++i) { 808 // Equivalent to AddPixelEq(), on a byte-basis. 809 new_data[i] = (data[i] + new_data[i - 4]) & 0xff; 810 } 811 for (; i < 4 * final_num_colors; ++i) 812 new_data[i] = 0; // black tail. 813 free(transform->data_); 814 transform->data_ = new_color_map; 815 } 816 return 1; 817 } 818 819 static int ReadTransform(int* const xsize, int const* ysize, 820 VP8LDecoder* const dec) { 821 int ok = 1; 822 VP8LBitReader* const br = &dec->br_; 823 VP8LTransform* transform = &dec->transforms_[dec->next_transform_]; 824 const VP8LImageTransformType type = 825 (VP8LImageTransformType)VP8LReadBits(br, 2); 826 827 // Each transform type can only be present once in the stream. 828 if (dec->transforms_seen_ & (1U << type)) { 829 return 0; // Already there, let's not accept the second same transform. 830 } 831 dec->transforms_seen_ |= (1U << type); 832 833 transform->type_ = type; 834 transform->xsize_ = *xsize; 835 transform->ysize_ = *ysize; 836 transform->data_ = NULL; 837 ++dec->next_transform_; 838 assert(dec->next_transform_ <= NUM_TRANSFORMS); 839 840 switch (type) { 841 case PREDICTOR_TRANSFORM: 842 case CROSS_COLOR_TRANSFORM: 843 transform->bits_ = VP8LReadBits(br, 3) + 2; 844 ok = DecodeImageStream(VP8LSubSampleSize(transform->xsize_, 845 transform->bits_), 846 VP8LSubSampleSize(transform->ysize_, 847 transform->bits_), 848 0, dec, &transform->data_); 849 break; 850 case COLOR_INDEXING_TRANSFORM: { 851 const int num_colors = VP8LReadBits(br, 8) + 1; 852 const int bits = (num_colors > 16) ? 0 853 : (num_colors > 4) ? 1 854 : (num_colors > 2) ? 2 855 : 3; 856 *xsize = VP8LSubSampleSize(transform->xsize_, bits); 857 transform->bits_ = bits; 858 ok = DecodeImageStream(num_colors, 1, 0, dec, &transform->data_); 859 ok = ok && ExpandColorMap(num_colors, transform); 860 break; 861 } 862 case SUBTRACT_GREEN: 863 break; 864 default: 865 assert(0); // can't happen 866 break; 867 } 868 869 return ok; 870 } 871 872 // ----------------------------------------------------------------------------- 873 // VP8LMetadata 874 875 static void InitMetadata(VP8LMetadata* const hdr) { 876 assert(hdr); 877 memset(hdr, 0, sizeof(*hdr)); 878 } 879 880 static void ClearMetadata(VP8LMetadata* const hdr) { 881 assert(hdr); 882 883 free(hdr->huffman_image_); 884 DeleteHtreeGroups(hdr->htree_groups_, hdr->num_htree_groups_); 885 VP8LColorCacheClear(&hdr->color_cache_); 886 InitMetadata(hdr); 887 } 888 889 // ----------------------------------------------------------------------------- 890 // VP8LDecoder 891 892 VP8LDecoder* VP8LNew(void) { 893 VP8LDecoder* const dec = (VP8LDecoder*)calloc(1, sizeof(*dec)); 894 if (dec == NULL) return NULL; 895 dec->status_ = VP8_STATUS_OK; 896 dec->action_ = READ_DIM; 897 dec->state_ = READ_DIM; 898 return dec; 899 } 900 901 void VP8LClear(VP8LDecoder* const dec) { 902 int i; 903 if (dec == NULL) return; 904 ClearMetadata(&dec->hdr_); 905 906 free(dec->argb_); 907 dec->argb_ = NULL; 908 for (i = 0; i < dec->next_transform_; ++i) { 909 ClearTransform(&dec->transforms_[i]); 910 } 911 dec->next_transform_ = 0; 912 dec->transforms_seen_ = 0; 913 914 free(dec->rescaler_memory); 915 dec->rescaler_memory = NULL; 916 917 dec->output_ = NULL; // leave no trace behind 918 } 919 920 void VP8LDelete(VP8LDecoder* const dec) { 921 if (dec != NULL) { 922 VP8LClear(dec); 923 free(dec); 924 } 925 } 926 927 static void UpdateDecoder(VP8LDecoder* const dec, int width, int height) { 928 VP8LMetadata* const hdr = &dec->hdr_; 929 const int num_bits = hdr->huffman_subsample_bits_; 930 dec->width_ = width; 931 dec->height_ = height; 932 933 hdr->huffman_xsize_ = VP8LSubSampleSize(width, num_bits); 934 hdr->huffman_mask_ = (num_bits == 0) ? ~0 : (1 << num_bits) - 1; 935 } 936 937 static int DecodeImageStream(int xsize, int ysize, 938 int is_level0, 939 VP8LDecoder* const dec, 940 uint32_t** const decoded_data) { 941 int ok = 1; 942 int transform_xsize = xsize; 943 int transform_ysize = ysize; 944 VP8LBitReader* const br = &dec->br_; 945 VP8LMetadata* const hdr = &dec->hdr_; 946 uint32_t* data = NULL; 947 int color_cache_bits = 0; 948 949 // Read the transforms (may recurse). 950 if (is_level0) { 951 while (ok && VP8LReadBits(br, 1)) { 952 ok = ReadTransform(&transform_xsize, &transform_ysize, dec); 953 } 954 } 955 956 // Color cache 957 if (ok && VP8LReadBits(br, 1)) { 958 color_cache_bits = VP8LReadBits(br, 4); 959 ok = (color_cache_bits >= 1 && color_cache_bits <= MAX_CACHE_BITS); 960 if (!ok) { 961 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 962 goto End; 963 } 964 } 965 966 // Read the Huffman codes (may recurse). 967 ok = ok && ReadHuffmanCodes(dec, transform_xsize, transform_ysize, 968 color_cache_bits, is_level0); 969 if (!ok) { 970 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 971 goto End; 972 } 973 974 // Finish setting up the color-cache 975 if (color_cache_bits > 0) { 976 hdr->color_cache_size_ = 1 << color_cache_bits; 977 if (!VP8LColorCacheInit(&hdr->color_cache_, color_cache_bits)) { 978 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 979 ok = 0; 980 goto End; 981 } 982 } else { 983 hdr->color_cache_size_ = 0; 984 } 985 UpdateDecoder(dec, transform_xsize, transform_ysize); 986 987 if (is_level0) { // level 0 complete 988 dec->state_ = READ_HDR; 989 goto End; 990 } 991 992 { 993 const uint64_t total_size = (uint64_t)transform_xsize * transform_ysize; 994 data = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*data)); 995 if (data == NULL) { 996 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 997 ok = 0; 998 goto End; 999 } 1000 } 1001 1002 // Use the Huffman trees to decode the LZ77 encoded data. 1003 ok = DecodeImageData(dec, data, transform_xsize, transform_ysize, NULL); 1004 ok = ok && !br->error_; 1005 1006 End: 1007 1008 if (!ok) { 1009 free(data); 1010 ClearMetadata(hdr); 1011 // If not enough data (br.eos_) resulted in BIT_STREAM_ERROR, update the 1012 // status appropriately. 1013 if (dec->status_ == VP8_STATUS_BITSTREAM_ERROR && dec->br_.eos_) { 1014 dec->status_ = VP8_STATUS_SUSPENDED; 1015 } 1016 } else { 1017 if (decoded_data != NULL) { 1018 *decoded_data = data; 1019 } else { 1020 // We allocate image data in this function only for transforms. At level 0 1021 // (that is: not the transforms), we shouldn't have allocated anything. 1022 assert(data == NULL); 1023 assert(is_level0); 1024 } 1025 if (!is_level0) ClearMetadata(hdr); // Clean up temporary data behind. 1026 } 1027 return ok; 1028 } 1029 1030 //------------------------------------------------------------------------------ 1031 // Allocate dec->argb_ and dec->argb_cache_ using dec->width_ and dec->height_ 1032 1033 static int AllocateARGBBuffers(VP8LDecoder* const dec, int final_width) { 1034 const uint64_t num_pixels = (uint64_t)dec->width_ * dec->height_; 1035 // Scratch buffer corresponding to top-prediction row for transforming the 1036 // first row in the row-blocks. 1037 const uint64_t cache_top_pixels = final_width; 1038 // Scratch buffer for temporary BGRA storage. 1039 const uint64_t cache_pixels = (uint64_t)final_width * NUM_ARGB_CACHE_ROWS; 1040 const uint64_t total_num_pixels = 1041 num_pixels + cache_top_pixels + cache_pixels; 1042 1043 assert(dec->width_ <= final_width); 1044 dec->argb_ = (uint32_t*)WebPSafeMalloc(total_num_pixels, sizeof(*dec->argb_)); 1045 if (dec->argb_ == NULL) { 1046 dec->argb_cache_ = NULL; // for sanity check 1047 dec->status_ = VP8_STATUS_OUT_OF_MEMORY; 1048 return 0; 1049 } 1050 dec->argb_cache_ = dec->argb_ + num_pixels + cache_top_pixels; 1051 return 1; 1052 } 1053 1054 //------------------------------------------------------------------------------ 1055 // Special row-processing that only stores the alpha data. 1056 1057 static void ExtractAlphaRows(VP8LDecoder* const dec, int row) { 1058 const int num_rows = row - dec->last_row_; 1059 const uint32_t* const in = dec->argb_ + dec->width_ * dec->last_row_; 1060 1061 if (num_rows <= 0) return; // Nothing to be done. 1062 ApplyInverseTransforms(dec, num_rows, in); 1063 1064 // Extract alpha (which is stored in the green plane). 1065 { 1066 const int width = dec->io_->width; // the final width (!= dec->width_) 1067 const int cache_pixs = width * num_rows; 1068 uint8_t* const dst = (uint8_t*)dec->io_->opaque + width * dec->last_row_; 1069 const uint32_t* const src = dec->argb_cache_; 1070 int i; 1071 for (i = 0; i < cache_pixs; ++i) dst[i] = (src[i] >> 8) & 0xff; 1072 } 1073 1074 dec->last_row_ = dec->last_out_row_ = row; 1075 } 1076 1077 int VP8LDecodeAlphaImageStream(int width, int height, const uint8_t* const data, 1078 size_t data_size, uint8_t* const output) { 1079 VP8Io io; 1080 int ok = 0; 1081 VP8LDecoder* const dec = VP8LNew(); 1082 if (dec == NULL) return 0; 1083 1084 dec->width_ = width; 1085 dec->height_ = height; 1086 dec->io_ = &io; 1087 1088 VP8InitIo(&io); 1089 WebPInitCustomIo(NULL, &io); // Just a sanity Init. io won't be used. 1090 io.opaque = output; 1091 io.width = width; 1092 io.height = height; 1093 1094 dec->status_ = VP8_STATUS_OK; 1095 VP8LInitBitReader(&dec->br_, data, data_size); 1096 1097 dec->action_ = READ_HDR; 1098 if (!DecodeImageStream(width, height, 1, dec, NULL)) goto Err; 1099 1100 // Allocate output (note that dec->width_ may have changed here). 1101 if (!AllocateARGBBuffers(dec, width)) goto Err; 1102 1103 // Decode (with special row processing). 1104 dec->action_ = READ_DATA; 1105 ok = DecodeImageData(dec, dec->argb_, dec->width_, dec->height_, 1106 ExtractAlphaRows); 1107 1108 Err: 1109 VP8LDelete(dec); 1110 return ok; 1111 } 1112 1113 //------------------------------------------------------------------------------ 1114 1115 int VP8LDecodeHeader(VP8LDecoder* const dec, VP8Io* const io) { 1116 int width, height, has_alpha; 1117 1118 if (dec == NULL) return 0; 1119 if (io == NULL) { 1120 dec->status_ = VP8_STATUS_INVALID_PARAM; 1121 return 0; 1122 } 1123 1124 dec->io_ = io; 1125 dec->status_ = VP8_STATUS_OK; 1126 VP8LInitBitReader(&dec->br_, io->data, io->data_size); 1127 if (!ReadImageInfo(&dec->br_, &width, &height, &has_alpha)) { 1128 dec->status_ = VP8_STATUS_BITSTREAM_ERROR; 1129 goto Error; 1130 } 1131 dec->state_ = READ_DIM; 1132 io->width = width; 1133 io->height = height; 1134 1135 dec->action_ = READ_HDR; 1136 if (!DecodeImageStream(width, height, 1, dec, NULL)) goto Error; 1137 return 1; 1138 1139 Error: 1140 VP8LClear(dec); 1141 assert(dec->status_ != VP8_STATUS_OK); 1142 return 0; 1143 } 1144 1145 int VP8LDecodeImage(VP8LDecoder* const dec) { 1146 VP8Io* io = NULL; 1147 WebPDecParams* params = NULL; 1148 1149 // Sanity checks. 1150 if (dec == NULL) return 0; 1151 1152 io = dec->io_; 1153 assert(io != NULL); 1154 params = (WebPDecParams*)io->opaque; 1155 assert(params != NULL); 1156 dec->output_ = params->output; 1157 assert(dec->output_ != NULL); 1158 1159 // Initialization. 1160 if (!WebPIoInitFromOptions(params->options, io, MODE_BGRA)) { 1161 dec->status_ = VP8_STATUS_INVALID_PARAM; 1162 goto Err; 1163 } 1164 1165 if (!AllocateARGBBuffers(dec, io->width)) goto Err; 1166 1167 if (io->use_scaling && !AllocateAndInitRescaler(dec, io)) goto Err; 1168 1169 // Decode. 1170 dec->action_ = READ_DATA; 1171 if (!DecodeImageData(dec, dec->argb_, dec->width_, dec->height_, 1172 ProcessRows)) { 1173 goto Err; 1174 } 1175 1176 // Cleanup. 1177 params->last_y = dec->last_out_row_; 1178 VP8LClear(dec); 1179 return 1; 1180 1181 Err: 1182 VP8LClear(dec); 1183 assert(dec->status_ != VP8_STATUS_OK); 1184 return 0; 1185 } 1186 1187 //------------------------------------------------------------------------------ 1188 1189 #if defined(__cplusplus) || defined(c_plusplus) 1190 } // extern "C" 1191 #endif 1192
