// Copyright 2012 Google Inc. All Rights Reserved.

//

// Use of this source code is governed by a BSD-style license

// that can be found in the COPYING file in the root of the source

// tree. An additional intellectual property rights grant can be found

// in the file PATENTS. All contributing project authors may

// be found in the AUTHORS file in the root of the source tree.

// -----------------------------------------------------------------------------

//

// main entry for the decoder

//

// Authors: Vikas Arora (vikaas.arora@gmail.com)

//          Jyrki Alakuijala (jyrki@google.com)

#include <assert.h>

#include <stddef.h>

#include <stdlib.h>

#include <string.h>

#include "src/dec/alphai_dec.h"

#include "src/dec/common_dec.h"

#include "src/dec/vp8_dec.h"

#include "src/dec/vp8li_dec.h"

#include "src/dec/webpi_dec.h"

#include "src/dsp/dsp.h"

#include "src/dsp/lossless.h"

#include "src/dsp/lossless_common.h"

#include "src/dsp/yuv.h"

#include "src/utils/bit_reader_utils.h"

#include "src/utils/color_cache_utils.h"

#include "src/utils/huffman_utils.h"

#include "src/utils/rescaler_utils.h"

#include "src/utils/utils.h"

#include "src/webp/decode.h"

#include "src/webp/format_constants.h"

#include "src/webp/types.h"

WEBP_ASSUME_UNSAFE_INDEXABLE_ABI

#define NUM_ARGB_CACHE_ROWS 16

static const int kCodeLengthLiterals = 16;

static const int kCodeLengthRepeatCode = 16;

static const uint8_t kCodeLengthExtraBits[3] = {2, 3, 7};

static const uint8_t kCodeLengthRepeatOffsets[3] = {3, 3, 11};

// -----------------------------------------------------------------------------

//  Five Huffman codes are used at each meta code:

//  1. green + length prefix codes + color cache codes,

//  2. alpha,

//  3. red,

//  4. blue, and,

//  5. distance prefix codes.

typedef enum { GREEN = 0, RED = 1, BLUE = 2, ALPHA = 3, DIST = 4 } HuffIndex;

static const uint16_t kAlphabetSize[HUFFMAN_CODES_PER_META_CODE] = {

    NUM_LITERAL_CODES + NUM_LENGTH_CODES, NUM_LITERAL_CODES, NUM_LITERAL_CODES,

    NUM_LITERAL_CODES, NUM_DISTANCE_CODES};

static const uint8_t kLiteralMap[HUFFMAN_CODES_PER_META_CODE] = {0, 1, 1, 1, 0};

#define NUM_CODE_LENGTH_CODES 19

static const uint8_t kCodeLengthCodeOrder[NUM_CODE_LENGTH_CODES] = {

    17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

#define CODE_TO_PLANE_CODES 120

static const uint8_t kCodeToPlane[CODE_TO_PLANE_CODES] = {

    0x18, 0x07, 0x17, 0x19, 0x28, 0x06, 0x27, 0x29, 0x16, 0x1a, 0x26, 0x2a,

    0x38, 0x05, 0x37, 0x39, 0x15, 0x1b, 0x36, 0x3a, 0x25, 0x2b, 0x48, 0x04,

    0x47, 0x49, 0x14, 0x1c, 0x35, 0x3b, 0x46, 0x4a, 0x24, 0x2c, 0x58, 0x45,

    0x4b, 0x34, 0x3c, 0x03, 0x57, 0x59, 0x13, 0x1d, 0x56, 0x5a, 0x23, 0x2d,

    0x44, 0x4c, 0x55, 0x5b, 0x33, 0x3d, 0x68, 0x02, 0x67, 0x69, 0x12, 0x1e,

    0x66, 0x6a, 0x22, 0x2e, 0x54, 0x5c, 0x43, 0x4d, 0x65, 0x6b, 0x32, 0x3e,

    0x78, 0x01, 0x77, 0x79, 0x53, 0x5d, 0x11, 0x1f, 0x64, 0x6c, 0x42, 0x4e,

    0x76, 0x7a, 0x21, 0x2f, 0x75, 0x7b, 0x31, 0x3f, 0x63, 0x6d, 0x52, 0x5e,

    0x00, 0x74, 0x7c, 0x41, 0x4f, 0x10, 0x20, 0x62, 0x6e, 0x30, 0x73, 0x7d,

    0x51, 0x5f, 0x40, 0x72, 0x7e, 0x61, 0x6f, 0x50, 0x71, 0x7f, 0x60, 0x70};

// Memory needed for lookup tables of one Huffman tree group. Red, blue, alpha

// and distance alphabets are constant (256 for red, blue and alpha, 40 for

// distance) and lookup table sizes for them in worst case are 630 and 410

// respectively. Size of green alphabet depends on color cache size and is equal

// to 256 (green component values) + 24 (length prefix values)

// + color_cache_size (between 0 and 2048).

// All values computed for 8-bit first level lookup with Mark Adler's tool:

// https://github.com/madler/zlib/blob/v1.2.5/examples/enough.c

#define FIXED_TABLE_SIZE (630 * 3 + 410)

static const uint16_t kTableSize[12] = {

    FIXED_TABLE_SIZE + 654,  FIXED_TABLE_SIZE + 656,  FIXED_TABLE_SIZE + 658,

    FIXED_TABLE_SIZE + 662,  FIXED_TABLE_SIZE + 670,  FIXED_TABLE_SIZE + 686,

    FIXED_TABLE_SIZE + 718,  FIXED_TABLE_SIZE + 782,  FIXED_TABLE_SIZE + 912,

    FIXED_TABLE_SIZE + 1168, FIXED_TABLE_SIZE + 1680, FIXED_TABLE_SIZE + 2704};

static int VP8LSetError(VP8LDecoder* const dec, VP8StatusCode error) {

  // The oldest error reported takes precedence over the new one.

  if (dec->status == VP8_STATUS_OK || dec->status == VP8_STATUS_SUSPENDED) {

    dec->status = error;

  }

  return 0;

}

static int DecodeImageStream(int xsize, int ysize, int is_level0,

                             VP8LDecoder* const dec,

                             uint32_t** const decoded_data);

//------------------------------------------------------------------------------

int VP8LCheckSignature(const uint8_t* const WEBP_COUNTED_BY(size) data,

                       size_t size) {

  return (size >= VP8L_FRAME_HEADER_SIZE && data[0] == VP8L_MAGIC_BYTE &&

          (data[4] >> 5) == 0);  // version

}

static int ReadImageInfo(VP8LBitReader* const br, int* const width,

                         int* const height, int* const has_alpha) {

  if (VP8LReadBits(br, 8) != VP8L_MAGIC_BYTE) return 0;

  *width = VP8LReadBits(br, VP8L_IMAGE_SIZE_BITS) + 1;

  *height = VP8LReadBits(br, VP8L_IMAGE_SIZE_BITS) + 1;

  *has_alpha = VP8LReadBits(br, 1);

  if (VP8LReadBits(br, VP8L_VERSION_BITS) != 0) return 0;

  return !br->eos;

}

int VP8LGetInfo(const uint8_t* WEBP_COUNTED_BY(data_size) data,

                size_t data_size, int* const width, int* const height,

                int* const has_alpha) {

  if (data == NULL || data_size < VP8L_FRAME_HEADER_SIZE) {

    return 0;  // not enough data

  } else if (!VP8LCheckSignature(data, data_size)) {

    return 0;  // bad signature

  } else {

    int w, h, a;

    VP8LBitReader br;

    VP8LInitBitReader(&br, data, data_size);

    if (!ReadImageInfo(&br, &w, &h, &a)) {

      return 0;

    }

    if (width != NULL) *width = w;

    if (height != NULL) *height = h;

    if (has_alpha != NULL) *has_alpha = a;

    return 1;

  }

}

//------------------------------------------------------------------------------

static WEBP_INLINE int GetCopyDistance(int distance_symbol,

                                       VP8LBitReader* const br) {

  int extra_bits, offset;

  if (distance_symbol < 4) {

    return distance_symbol + 1;

  }

  extra_bits = (distance_symbol - 2) >> 1;

  offset = (2 + (distance_symbol & 1)) << extra_bits;

  return offset + VP8LReadBits(br, extra_bits) + 1;

}

static WEBP_INLINE int GetCopyLength(int length_symbol,

                                     VP8LBitReader* const br) {

  // Length and distance prefixes are encoded the same way.

  return GetCopyDistance(length_symbol, br);

}

static WEBP_INLINE int PlaneCodeToDistance(int xsize, int plane_code) {

  if (plane_code > CODE_TO_PLANE_CODES) {

    return plane_code - CODE_TO_PLANE_CODES;

  } else {

    const int dist_code = kCodeToPlane[plane_code - 1];

    const int yoffset = dist_code >> 4;

    const int xoffset = 8 - (dist_code & 0xf);

    const int dist = yoffset * xsize + xoffset;

    return (dist >= 1) ? dist : 1;  // dist<1 can happen if xsize is very small

  }

}

//------------------------------------------------------------------------------

// Decodes the next Huffman code from bit-stream.

// VP8LFillBitWindow(br) needs to be called at minimum every second call

// to ReadSymbol, in order to pre-fetch enough bits.

static WEBP_INLINE int ReadSymbol(const HuffmanCode* table,

                                  VP8LBitReader* const br) {

  int nbits;

  uint32_t val = VP8LPrefetchBits(br);

  table += val & HUFFMAN_TABLE_MASK;

  nbits = table->bits - HUFFMAN_TABLE_BITS;

  if (nbits > 0) {

    VP8LSetBitPos(br, br->bit_pos + HUFFMAN_TABLE_BITS);

    val = VP8LPrefetchBits(br);

    table += table->value;

    table += val & ((1 << nbits) - 1);

  }

  VP8LSetBitPos(br, br->bit_pos + table->bits);

  return table->value;

}

// Reads packed symbol depending on GREEN channel

#define BITS_SPECIAL_MARKER 0x100  // something large enough (and a bit-mask)

#define PACKED_NON_LITERAL_CODE 0  // must be < NUM_LITERAL_CODES

static WEBP_INLINE int ReadPackedSymbols(const HTreeGroup* group,

                                         VP8LBitReader* const br,

                                         uint32_t* const dst) {

  const uint32_t val = VP8LPrefetchBits(br) & (HUFFMAN_PACKED_TABLE_SIZE - 1);

  const HuffmanCode32 code = group->packed_table[val];

  assert(group->use_packed_table);

  if (code.bits < BITS_SPECIAL_MARKER) {

    VP8LSetBitPos(br, br->bit_pos + code.bits);

    *dst = code.value;

    return PACKED_NON_LITERAL_CODE;

  } else {

    VP8LSetBitPos(br, br->bit_pos + code.bits - BITS_SPECIAL_MARKER);

    assert(code.value >= NUM_LITERAL_CODES);

    return code.value;

  }

}

static int AccumulateHCode(HuffmanCode hcode, int shift,

                           HuffmanCode32* const huff) {

  huff->bits += hcode.bits;

  huff->value |= (uint32_t)hcode.value << shift;

  assert(huff->bits <= HUFFMAN_TABLE_BITS);

  return hcode.bits;

}

static void BuildPackedTable(HTreeGroup* const htree_group) {

  uint32_t code;

  for (code = 0; code < HUFFMAN_PACKED_TABLE_SIZE; ++code) {

    uint32_t bits = code;

    HuffmanCode32* const huff = &htree_group->packed_table[bits];

    HuffmanCode hcode = htree_group->htrees[GREEN][bits];

    if (hcode.value >= NUM_LITERAL_CODES) {

      huff->bits = hcode.bits + BITS_SPECIAL_MARKER;

      huff->value = hcode.value;

    } else {

      huff->bits = 0;

      huff->value = 0;

      bits >>= AccumulateHCode(hcode, 8, huff);

      bits >>= AccumulateHCode(htree_group->htrees[RED][bits], 16, huff);

      bits >>= AccumulateHCode(htree_group->htrees[BLUE][bits], 0, huff);

      bits >>= AccumulateHCode(htree_group->htrees[ALPHA][bits], 24, huff);

      (void)bits;

    }

  }

}

static int ReadHuffmanCodeLengths(VP8LDecoder* const dec,

                                  const int* const code_length_code_lengths,

                                  int num_symbols, int* const code_lengths) {

  int ok = 0;

  VP8LBitReader* const br = &dec->br;

  int symbol;

  int max_symbol;

  int prev_code_len = DEFAULT_CODE_LENGTH;

  HuffmanTables tables;

  const int* WEBP_BIDI_INDEXABLE const bounded_code_lengths =

      WEBP_UNSAFE_FORGE_BIDI_INDEXABLE(

          const int*, code_length_code_lengths,

          NUM_CODE_LENGTH_CODES * sizeof(*code_length_code_lengths));

  if (!VP8LHuffmanTablesAllocate(1 << LENGTHS_TABLE_BITS, &tables) ||

      !VP8LBuildHuffmanTable(&tables, LENGTHS_TABLE_BITS, bounded_code_lengths,

                             NUM_CODE_LENGTH_CODES)) {

    goto End;

  }

  if (VP8LReadBits(br, 1)) {  // use length

    const int length_nbits = 2 + 2 * VP8LReadBits(br, 3);

    max_symbol = 2 + VP8LReadBits(br, length_nbits);

    if (max_symbol > num_symbols) {

      goto End;

    }

  } else {

    max_symbol = num_symbols;

  }

  symbol = 0;

  while (symbol < num_symbols) {

    const HuffmanCode* p;

    int code_len;

    if (max_symbol-- == 0) break;

    VP8LFillBitWindow(br);

    p = &tables.curr_segment->start[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK];

    VP8LSetBitPos(br, br->bit_pos + p->bits);

    code_len = p->value;

    if (code_len < kCodeLengthLiterals) {

      code_lengths[symbol++] = code_len;

      if (code_len != 0) prev_code_len = code_len;

    } else {

      const int use_prev = (code_len == kCodeLengthRepeatCode);

      const int slot = code_len - kCodeLengthLiterals;

      const int extra_bits = kCodeLengthExtraBits[slot];

      const int repeat_offset = kCodeLengthRepeatOffsets[slot];

      int repeat = VP8LReadBits(br, extra_bits) + repeat_offset;

      if (symbol + repeat > num_symbols) {

        goto End;

      } else {

        const int length = use_prev ? prev_code_len : 0;

        while (repeat-- > 0) code_lengths[symbol++] = length;

      }

    }

  }

  ok = 1;

End:

  VP8LHuffmanTablesDeallocate(&tables);

  if (!ok) return VP8LSetError(dec, VP8_STATUS_BITSTREAM_ERROR);

  return ok;

}

// 'code_lengths' is pre-allocated temporary buffer, used for creating Huffman

// tree.

static int ReadHuffmanCode(int alphabet_size, VP8LDecoder* const dec,

                           int* const code_lengths,

                           HuffmanTables* const table) {

  int ok = 0;

  int size = 0;

  VP8LBitReader* const br = &dec->br;

  const int simple_code = VP8LReadBits(br, 1);

  WEBP_UNSAFE_MEMSET(code_lengths, 0, alphabet_size * sizeof(*code_lengths));

  if (simple_code) {  // Read symbols, codes & code lengths directly.

    const int num_symbols = VP8LReadBits(br, 1) + 1;

    const int first_symbol_len_code = VP8LReadBits(br, 1);

    // The first code is either 1 bit or 8 bit code.

    int symbol = VP8LReadBits(br, (first_symbol_len_code == 0) ? 1 : 8);

    code_lengths[symbol] = 1;

    // The second code (if present), is always 8 bits long.

    if (num_symbols == 2) {

      symbol = VP8LReadBits(br, 8);

      code_lengths[symbol] = 1;

    }

    ok = 1;

  } else {  // Decode Huffman-coded code lengths.

    int i;

    int code_length_code_lengths[NUM_CODE_LENGTH_CODES] = {0};

    const int num_codes = VP8LReadBits(br, 4) + 4;

    assert(num_codes <= NUM_CODE_LENGTH_CODES);

    for (i = 0; i < num_codes; ++i) {

      code_length_code_lengths[kCodeLengthCodeOrder[i]] = VP8LReadBits(br, 3);

    }

    ok = ReadHuffmanCodeLengths(dec, code_length_code_lengths, alphabet_size,

                                code_lengths);

  }

  ok = ok && !br->eos;

  if (ok) {

    const int* WEBP_BIDI_INDEXABLE const bounded_code_lengths =

        WEBP_UNSAFE_FORGE_BIDI_INDEXABLE(const int*, code_lengths,

                                         alphabet_size * sizeof(int));

    size = VP8LBuildHuffmanTable(table, HUFFMAN_TABLE_BITS,

                                 bounded_code_lengths, alphabet_size);

  }

  if (!ok || size == 0) {

    return VP8LSetError(dec, VP8_STATUS_BITSTREAM_ERROR);

  }

  return size;

}

static int ReadHuffmanCodes(VP8LDecoder* const dec, int xsize, int ysize,

                            int color_cache_bits, int allow_recursion) {

  int i;

  VP8LBitReader* const br = &dec->br;

  VP8LMetadata* const hdr = &dec->hdr;

  uint32_t* huffman_image = NULL;

  HTreeGroup* htree_groups = NULL;

  HuffmanTables* huffman_tables = &hdr->huffman_tables;

  int num_htree_groups = 1;

  int num_htree_groups_max = 1;

  int* mapping = NULL;

  int ok = 0;

  // Check the table has been 0 initialized (through InitMetadata).

  assert(huffman_tables->root.start == NULL);

  assert(huffman_tables->curr_segment == NULL);

  if (allow_recursion && VP8LReadBits(br, 1)) {

    // use meta Huffman codes.

    const int huffman_precision =

        MIN_HUFFMAN_BITS + VP8LReadBits(br, NUM_HUFFMAN_BITS);

    const int huffman_xsize = VP8LSubSampleSize(xsize, huffman_precision);

    const int huffman_ysize = VP8LSubSampleSize(ysize, huffman_precision);

    const int huffman_pixs = huffman_xsize * huffman_ysize;

    if (!DecodeImageStream(huffman_xsize, huffman_ysize, /*is_level0=*/0, dec,

                           &huffman_image)) {

      goto Error;

    }

    hdr->huffman_subsample_bits = huffman_precision;

    for (i = 0; i < huffman_pixs; ++i) {

      // The huffman data is stored in red and green bytes.

      const int group = (huffman_image[i] >> 8) & 0xffff;

      huffman_image[i] = group;

      if (group >= num_htree_groups_max) {

        num_htree_groups_max = group + 1;

      }

    }

    // Check the validity of num_htree_groups_max. If it seems too big, use a

    // smaller value for later. This will prevent big memory allocations to end

    // up with a bad bitstream anyway.

    // The value of 1000 is totally arbitrary. We know that num_htree_groups_max

    // is smaller than (1 << 16) and should be smaller than the number of pixels

    // (though the format allows it to be bigger).

    if (num_htree_groups_max > 1000 || num_htree_groups_max > xsize * ysize) {

      // Create a mapping from the used indices to the minimal set of used

      // values [0, num_htree_groups)

      mapping = (int*)WebPSafeMalloc(num_htree_groups_max, sizeof(*mapping));

      if (mapping == NULL) {

        VP8LSetError(dec, VP8_STATUS_OUT_OF_MEMORY);

        goto Error;

      }

      // -1 means a value is unmapped, and therefore unused in the Huffman

      // image.

      WEBP_UNSAFE_MEMSET(mapping, 0xff,

                         num_htree_groups_max * sizeof(*mapping));

      for (num_htree_groups = 0, i = 0; i < huffman_pixs; ++i) {

        // Get the current mapping for the group and remap the Huffman image.

        int* const mapped_group = &mapping[huffman_image[i]];

        if (*mapped_group == -1) *mapped_group = num_htree_groups++;

        huffman_image[i] = *mapped_group;

      }

    } else {

      num_htree_groups = num_htree_groups_max;

    }

  }

  if (br->eos) goto Error;

  if (!ReadHuffmanCodesHelper(color_cache_bits, num_htree_groups,

                              num_htree_groups_max, mapping, dec,

                              huffman_tables, &htree_groups)) {

    goto Error;

  }

  ok = 1;

  // All OK. Finalize pointers.

  hdr->huffman_image = huffman_image;

  hdr->num_htree_groups = num_htree_groups;

  hdr->htree_groups = htree_groups;

Error:

  WebPSafeFree(mapping);

  if (!ok) {

    WebPSafeFree(huffman_image);

    VP8LHuffmanTablesDeallocate(huffman_tables);

    VP8LHtreeGroupsFree(htree_groups);

  }

  return ok;

}

int ReadHuffmanCodesHelper(int color_cache_bits, int num_htree_groups,

                           int num_htree_groups_max, const int* const mapping,

                           VP8LDecoder* const dec,

                           HuffmanTables* const huffman_tables,

                           HTreeGroup** const htree_groups) {

  int i, j, ok = 0;

  const int max_alphabet_size =

      kAlphabetSize[0] + ((color_cache_bits > 0) ? 1 << color_cache_bits : 0);

  const int table_size = kTableSize[color_cache_bits];

  int* code_lengths = NULL;

  int total_huffman_table_size;

  if ((mapping == NULL && num_htree_groups != num_htree_groups_max) ||

      num_htree_groups > num_htree_groups_max) {

    goto Error;

  }

  code_lengths =

      (int*)WebPSafeCalloc((uint64_t)max_alphabet_size, sizeof(*code_lengths));

  *htree_groups = VP8LHtreeGroupsNew(num_htree_groups);

  // MAX_HUFF_IMAGE_SIZE is above what the libwebp encoder allows so something

  // fishy might be happening. Do not allocate too much yet.

  total_huffman_table_size =

      (num_htree_groups_max > MAX_HUFF_IMAGE_SIZE ? MAX_HUFF_IMAGE_SIZE

                                                  : num_htree_groups) *

      table_size;

  if (*htree_groups == NULL || code_lengths == NULL ||

      !VP8LHuffmanTablesAllocate(total_huffman_table_size, huffman_tables)) {

    VP8LSetError(dec, VP8_STATUS_OUT_OF_MEMORY);

    goto Error;

  }

  for (i = 0; i < num_htree_groups_max; ++i) {

    // If the index "i" is unused in the Huffman image, just make sure the

    // coefficients are valid but do not store them.

    if (mapping != NULL && mapping[i] == -1) {

      for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) {

        int alphabet_size = kAlphabetSize[j];

        if (j == 0 && color_cache_bits > 0) {

          alphabet_size += (1 << color_cache_bits);

        }

        // Passing in NULL so that nothing gets filled.

        if (!ReadHuffmanCode(alphabet_size, dec, code_lengths, NULL)) {

          goto Error;

        }

      }

    } else {

      HTreeGroup* const htree_group =

          &(*htree_groups)[(mapping == NULL) ? i : mapping[i]];

      HuffmanCode** const htrees = htree_group->htrees;

      int size;

      int total_size = 0;

      int is_trivial_literal = 1;

      int max_bits = 0;

      for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) {

        int alphabet_size = kAlphabetSize[j];

        if (j == 0 && color_cache_bits > 0) {

          alphabet_size += (1 << color_cache_bits);

        }

        size =

            ReadHuffmanCode(alphabet_size, dec, code_lengths, huffman_tables);

        htrees[j] = huffman_tables->curr_segment->curr_table;

        if (size == 0) {

          goto Error;

        }

        if (is_trivial_literal && kLiteralMap[j] == 1) {

          is_trivial_literal = (htrees[j]->bits == 0);

        }

        total_size += htrees[j]->bits;

        huffman_tables->curr_segment->curr_table += size;

        if (j <= ALPHA) {

          int local_max_bits = code_lengths[0];

          int k;

          for (k = 1; k < alphabet_size; ++k) {

            if (code_lengths[k] > local_max_bits) {

              local_max_bits = code_lengths[k];

            }

          }

          max_bits += local_max_bits;

        }

      }

      htree_group->is_trivial_literal = is_trivial_literal;

      htree_group->is_trivial_code = 0;

      if (is_trivial_literal) {

        const int red = htrees[RED][0].value;

        const int blue = htrees[BLUE][0].value;

        const int alpha = htrees[ALPHA][0].value;

        htree_group->literal_arb = ((uint32_t)alpha << 24) | (red << 16) | blue;

        if (total_size == 0 && htrees[GREEN][0].value < NUM_LITERAL_CODES) {

          htree_group->is_trivial_code = 1;

          htree_group->literal_arb |= htrees[GREEN][0].value << 8;

        }

      }

      htree_group->use_packed_table =

          !htree_group->is_trivial_code && (max_bits < HUFFMAN_PACKED_BITS);

      if (htree_group->use_packed_table) BuildPackedTable(htree_group);

    }

  }

  ok = 1;

Error:

  WebPSafeFree(code_lengths);

  if (!ok) {

    VP8LHuffmanTablesDeallocate(huffman_tables);

    VP8LHtreeGroupsFree(*htree_groups);

    *htree_groups = NULL;

  }

  return ok;

}

//------------------------------------------------------------------------------

// Scaling.

#if !defined(WEBP_REDUCE_SIZE)

static int AllocateAndInitRescaler(VP8LDecoder* const dec, VP8Io* const io) {

  const int num_channels = 4;

  const int in_width = io->mb_w;

  const int out_width = io->scaled_width;

  const int in_height = io->mb_h;

  const int out_height = io->scaled_height;

  const uint64_t work_size = 2 * num_channels * (uint64_t)out_width;

  rescaler_t* WEBP_BIDI_INDEXABLE work;  // Rescaler work area.

  const uint64_t scaled_data_size = (uint64_t)out_width;

  uint32_t* WEBP_BIDI_INDEXABLE

      scaled_data;  // Temporary storage for scaled BGRA data.

  const uint64_t memory_size = sizeof(*dec->rescaler) +

                               work_size * sizeof(*work) +

                               scaled_data_size * sizeof(*scaled_data);

  uint8_t* WEBP_BIDI_INDEXABLE memory =

      (uint8_t*)WebPSafeMalloc(memory_size, sizeof(*memory));

  if (memory == NULL) {

    return VP8LSetError(dec, VP8_STATUS_OUT_OF_MEMORY);

  }

  assert(dec->rescaler_memory == NULL);

  dec->rescaler_memory = memory;

  dec->rescaler = (WebPRescaler*)memory;

  memory += sizeof(*dec->rescaler);

  work = (rescaler_t*)memory;

  memory += work_size * sizeof(*work);

  scaled_data = (uint32_t*)memory;

  if (!WebPRescalerInit(dec->rescaler, in_width, in_height,

                        (uint8_t*)scaled_data, out_width, out_height, 0,

                        num_channels, work)) {

    return 0;

  }

  return 1;

}

#endif  // WEBP_REDUCE_SIZE

//------------------------------------------------------------------------------

// Export to ARGB

#if !defined(WEBP_REDUCE_SIZE)

// We have special "export" function since we need to convert from BGRA

static int Export(WebPRescaler* const rescaler, WEBP_CSP_MODE colorspace,

                  int rgba_stride, uint8_t* const rgba) {

  uint32_t* const src = (uint32_t*)rescaler->dst;

  uint8_t* dst = rgba;

  const int dst_width = rescaler->dst_width;

  int num_lines_out = 0;

  while (WebPRescalerHasPendingOutput(rescaler)) {

    WebPRescalerExportRow(rescaler);

    WebPMultARGBRow(src, dst_width, 1);

    VP8LConvertFromBGRA(src, dst_width, colorspace, dst);

    dst += rgba_stride;

    ++num_lines_out;

  }

  return num_lines_out;

}

// Emit scaled rows.

static int EmitRescaledRowsRGBA(const VP8LDecoder* const dec, uint8_t* in,

                                int in_stride, int mb_h, uint8_t* const out,

                                int out_stride) {

  const WEBP_CSP_MODE colorspace = dec->output->colorspace;

  int num_lines_in = 0;

  int num_lines_out = 0;

  while (num_lines_in < mb_h) {

    uint8_t* const row_in = in + (ptrdiff_t)num_lines_in * in_stride;

    uint8_t* const row_out = out + (ptrdiff_t)num_lines_out * out_stride;

    const int lines_left = mb_h - num_lines_in;

    const int needed_lines = WebPRescaleNeededLines(dec->rescaler, lines_left);

    int lines_imported;

    assert(needed_lines > 0 && needed_lines <= lines_left);

    WebPMultARGBRows(row_in, in_stride, dec->rescaler->src_width, needed_lines,

                     0);

    lines_imported =

        WebPRescalerImport(dec->rescaler, lines_left, row_in, in_stride);

    assert(lines_imported == needed_lines);

    num_lines_in += lines_imported;

    num_lines_out += Export(dec->rescaler, colorspace, out_stride, row_out);

  }

  return num_lines_out;

}

#endif  // WEBP_REDUCE_SIZE

// Emit rows without any scaling.

static int EmitRows(WEBP_CSP_MODE colorspace, const uint8_t* row_in,

                    int in_stride, int mb_w, int mb_h, uint8_t* const out,

                    int out_stride) {

  int lines = mb_h;

  uint8_t* row_out = out;

  while (lines-- > 0) {

    VP8LConvertFromBGRA((const uint32_t*)row_in, mb_w, colorspace, row_out);

    row_in += in_stride;

    row_out += out_stride;

  }

  return mb_h;  // Num rows out == num rows in.

}

//------------------------------------------------------------------------------

// Export to YUVA

static void ConvertToYUVA(const uint32_t* const src, int width, int y_pos,

                          const WebPDecBuffer* const output) {

  const WebPYUVABuffer* const buf = &output->u.YUVA;

  // first, the luma plane

  WebPConvertARGBToY(src, buf->y + (ptrdiff_t)y_pos * buf->y_stride, width);

  // then U/V planes

  {

    uint8_t* const u = buf->u + (ptrdiff_t)(y_pos >> 1) * buf->u_stride;

    uint8_t* const v = buf->v + (ptrdiff_t)(y_pos >> 1) * buf->v_stride;

    // even lines: store values

    // odd lines: average with previous values

    WebPConvertARGBToUV(src, u, v, width, !(y_pos & 1));

  }

  // Lastly, store alpha if needed.

  if (buf->a != NULL) {

    uint8_t* const a = buf->a + (ptrdiff_t)y_pos * buf->a_stride;

#if defined(WORDS_BIGENDIAN)

    WebPExtractAlpha((uint8_t*)src + 0, 0, width, 1, a, 0);

#else

    WebPExtractAlpha((uint8_t*)src + 3, 0, width, 1, a, 0);

#endif

  }

}

static int ExportYUVA(const VP8LDecoder* const dec, int y_pos) {

  WebPRescaler* const rescaler = dec->rescaler;

  uint32_t* const src = (uint32_t*)rescaler->dst;

  const int dst_width = rescaler->dst_width;

  int num_lines_out = 0;

  while (WebPRescalerHasPendingOutput(rescaler)) {

    WebPRescalerExportRow(rescaler);

    WebPMultARGBRow(src, dst_width, 1);

    ConvertToYUVA(src, dst_width, y_pos, dec->output);

    ++y_pos;

    ++num_lines_out;

  }

  return num_lines_out;

}

static int EmitRescaledRowsYUVA(const VP8LDecoder* const dec, uint8_t* in,

                                int in_stride, int mb_h) {

  int num_lines_in = 0;

  int y_pos = dec->last_out_row;

  while (num_lines_in < mb_h) {

    const int lines_left = mb_h - num_lines_in;

    const int needed_lines = WebPRescaleNeededLines(dec->rescaler, lines_left);

    int lines_imported;

    WebPMultARGBRows(in, in_stride, dec->rescaler->src_width, needed_lines, 0);

    lines_imported =

        WebPRescalerImport(dec->rescaler, lines_left, in, in_stride);

    assert(lines_imported == needed_lines);

    num_lines_in += lines_imported;

    in += (ptrdiff_t)needed_lines * in_stride;

    y_pos += ExportYUVA(dec, y_pos);

  }

  return y_pos;

}

// Returns true if alpha[] has non-0xff values.

static int CheckNonOpaque(const uint8_t* alpha, int width, int height,

                          int y_step) {

  WebPInitAlphaProcessing();

  for (; height-- > 0; alpha += y_step) {

    if (WebPHasAlpha8b(alpha, width)) return 1;

  }

  return 0;

}

static int EmitRowsYUVA(const uint8_t* const in, const VP8Io* const io,

                        int in_stride, uint16_t* tmp_rgb,

                        VP8LDecoder* const dec) {

  int y_pos = dec->last_out_row;

  const int width = io->mb_w;

  int num_rows = io->mb_h;

  const int y_pos_final = y_pos + num_rows;

  const int y_stride = dec->output->u.YUVA.y_stride;

  const int uv_stride = dec->output->u.YUVA.u_stride;

  const int a_stride = dec->output->u.YUVA.a_stride;

  uint8_t* dst_a = dec->output->u.YUVA.a;

  uint8_t* dst_y = dec->output->u.YUVA.y + (ptrdiff_t)y_pos * y_stride;

  uint8_t* dst_u = dec->output->u.YUVA.u + (ptrdiff_t)(y_pos >> 1) * uv_stride;

  uint8_t* dst_v = dec->output->u.YUVA.v + (ptrdiff_t)(y_pos >> 1) * uv_stride;

  const uint8_t* r_ptr = in + CHANNEL_OFFSET(1);

  const uint8_t* g_ptr = in + CHANNEL_OFFSET(2);

  const uint8_t* b_ptr = in + CHANNEL_OFFSET(3);

  const uint8_t* a_ptr = NULL;

  int has_alpha = 0;

  // Make sure the lines are processed two by two from the start.

  assert(y_pos % 2 == 0);

  // Make sure num_rows is even. y_pos_final will check if it not.

  num_rows &= ~1;

  if (dst_a) {

    dst_a += (ptrdiff_t)y_pos * a_stride;

    a_ptr = in + CHANNEL_OFFSET(0);

    has_alpha = CheckNonOpaque(a_ptr, width, num_rows, in_stride);

  }

  // Process pairs of lines.

  WebPImportYUVAFromRGBA(r_ptr, g_ptr, b_ptr, a_ptr, /*step=*/4, in_stride,

                         has_alpha, width, num_rows, tmp_rgb, y_stride,

                         uv_stride, a_stride, dst_y, dst_u, dst_v, dst_a);

  y_pos += num_rows;

  if (y_pos_final == io->crop_bottom - io->crop_top && y_pos < y_pos_final) {

    assert(y_pos + 1 == y_pos_final);

    // If we output the last line of an image with odd height.

    dst_y += (ptrdiff_t)num_rows * y_stride;

    dst_u += (ptrdiff_t)(num_rows >> 1) * uv_stride;

    dst_v += (ptrdiff_t)(num_rows >> 1) * uv_stride;

    r_ptr += (ptrdiff_t)num_rows * in_stride;

    g_ptr += (ptrdiff_t)num_rows * in_stride;

    b_ptr += (ptrdiff_t)num_rows * in_stride;

    if (dst_a) {

      dst_a += (ptrdiff_t)num_rows * a_stride;

      a_ptr += (ptrdiff_t)num_rows * in_stride;

      has_alpha = CheckNonOpaque(a_ptr, width, /*height=*/1, in_stride);

    }

    WebPImportYUVAFromRGBALastLine(r_ptr, g_ptr, b_ptr, a_ptr, /*step=*/4,

                                   has_alpha, width, tmp_rgb, dst_y, dst_u,

                                   dst_v, dst_a);

    y_pos = y_pos_final;

  }

  return y_pos;

}

//------------------------------------------------------------------------------

// Cropping.

// Sets io->mb_y, io->mb_h & io->mb_w according to start row, end row and

// crop options. Also updates the input data pointer, so that it points to the

// start of the cropped window. Note that pixels are in ARGB format even if

// 'in_data' is uint8_t*.

// Returns true if the crop window is not empty.

static int SetCropWindow(VP8Io* const io, int y_start, int y_end,

                         uint8_t** const in_data, int pixel_stride) {

  assert(y_start < y_end);

  assert(io->crop_left < io->crop_right);

  if (y_end > io->crop_bottom) {

    y_end = io->crop_bottom;  // make sure we don't overflow on last row.

  }

  if (y_start < io->crop_top) {

    const int delta = io->crop_top - y_start;

    y_start = io->crop_top;

    *in_data += (ptrdiff_t)delta * pixel_stride;

  }

  if (y_start >= y_end) return 0;  // Crop window is empty.

  *in_data += io->crop_left * sizeof(uint32_t);

  io->mb_y = y_start - io->crop_top;

  io->mb_w = io->crop_right - io->crop_left;

  io->mb_h = y_end - y_start;

  return 1;  // Non-empty crop window.

}

//------------------------------------------------------------------------------

static WEBP_INLINE int GetMetaIndex(const uint32_t* const image, int xsize,

                                    int bits, int x, int y) {

  if (bits == 0) return 0;

  return image[xsize * (y >> bits) + (x >> bits)];

}

static WEBP_INLINE HTreeGroup* GetHtreeGroupForPos(VP8LMetadata* const hdr,

                                                   int x, int y) {

  const int meta_index = GetMetaIndex(hdr->huffman_image, hdr->huffman_xsize,

                                      hdr->huffman_subsample_bits, x, y);

  assert(meta_index < hdr->num_htree_groups);

  return hdr->htree_groups + meta_index;

}

//------------------------------------------------------------------------------

// Main loop, with custom row-processing function

// If 'wait_for_biggest_batch' is true, wait for enough data to fill the

// argb_cache as much as possible (usually NUM_ARGB_CACHE_ROWS).

typedef void (*ProcessRowsFunc)(VP8LDecoder* const dec, int row,

                                int wait_for_biggest_batch);

static void ApplyInverseTransforms(VP8LDecoder* const dec, int start_row,

                                   int num_rows, const uint32_t* const rows) {

  int n = dec->next_transform;

  const int cache_pixs = dec->width * num_rows;

  const int end_row = start_row + num_rows;

  const uint32_t* rows_in = rows;

  uint32_t* const rows_out = dec->argb_cache;

  // Inverse transforms.

  while (n-- > 0) {

    VP8LTransform* const transform = &dec->transforms[n];

    VP8LInverseTransform(transform, start_row, end_row, rows_in, rows_out);

    rows_in = rows_out;

  }

  if (rows_in != rows_out) {

    // No transform called, hence just copy.

    WEBP_UNSAFE_MEMCPY(rows_out, rows_in, cache_pixs * sizeof(*rows_out));

  }

}

// Processes (transforms, scales & color-converts) the rows decoded after the

// last call.

static void ProcessRows(VP8LDecoder* const dec, int row,

                        int wait_for_biggest_batch) {

  const uint32_t* const rows = dec->pixels + dec->width * dec->last_row;

  int num_rows;

  // In case of YUV conversion and if we do not need to get to the last row.

  if (wait_for_biggest_batch) {

    // In case of YUV conversion, and if we do not use the whole cropping

    // region.

    if (!WebPIsRGBMode(dec->output->colorspace) && row >= dec->io->crop_top &&

        row < dec->io->crop_bottom) {

      // Make sure the number of rows to process is even.

      if ((row - dec->io->crop_top) % 2 != 0) return;

      // Make sure the cache is as full as possible.

      if (row % NUM_ARGB_CACHE_ROWS != 0 &&

          (row + 1) % NUM_ARGB_CACHE_ROWS != 0) {

        return;

      }

    } else {

      if (row % NUM_ARGB_CACHE_ROWS != 0) return;

    }

  }

  num_rows = row - dec->last_row;

  assert(row <= dec->io->crop_bottom);

  // We can't process more than NUM_ARGB_CACHE_ROWS at a time (that's the size

  // of argb_cache), but we currently don't need more than that.

  assert(num_rows <= NUM_ARGB_CACHE_ROWS);

  if (num_rows > 0) {  // Emit output.

    VP8Io* const io = dec->io;

    uint8_t* rows_data = (uint8_t*)dec->argb_cache;

    const int in_stride = io->width * sizeof(uint32_t);  // in unit of RGBA

    ApplyInverseTransforms(dec, dec->last_row, num_rows, rows);

    if (!SetCropWindow(io, dec->last_row, row, &rows_data, in_stride)) {

      // Nothing to output (this time).

    } else {

      const WebPDecBuffer* const output = dec->output;

      if (WebPIsRGBMode(output->colorspace)) {  // convert to RGBA

        const WebPRGBABuffer* const buf = &output->u.RGBA;

        uint8_t* const rgba =

            buf->rgba + (ptrdiff_t)dec->last_out_row * buf->stride;

        const int num_rows_out =

#if !defined(WEBP_REDUCE_SIZE)

            io->use_scaling ? EmitRescaledRowsRGBA(dec, rows_data, in_stride,

                                                   io->mb_h, rgba, buf->stride)

                            :

#endif  // WEBP_REDUCE_SIZE

                            EmitRows(output->colorspace, rows_data, in_stride,

                                     io->mb_w, io->mb_h, rgba, buf->stride);

        // Update 'last_out_row'.

        dec->last_out_row += num_rows_out;

      } else {  // convert to YUVA

        dec->last_out_row =

            io->use_scaling

                ? EmitRescaledRowsYUVA(dec, rows_data, in_stride, io->mb_h)

                : EmitRowsYUVA(rows_data, io, in_stride,

                               dec->accumulated_rgb_pixels, dec);

      }

      assert(dec->last_out_row <= output->height);

    }

  }

  // Update 'last_row'.

  dec->last_row = row;

  assert(dec->last_row <= dec->height);

}

// Row-processing for the special case when alpha data contains only one

// transform (color indexing), and trivial non-green literals.

static int Is8bOptimizable(const VP8LMetadata* const hdr) {

  int i;

  if (hdr->color_cache_size > 0) return 0;

  // When the Huffman tree contains only one symbol, we can skip the

  // call to ReadSymbol() for red/blue/alpha channels.

  for (i = 0; i < hdr->num_htree_groups; ++i) {

    HuffmanCode** const htrees = hdr->htree_groups[i].htrees;

    if (htrees[RED][0].bits > 0) return 0;

    if (htrees[BLUE][0].bits > 0) return 0;

    if (htrees[ALPHA][0].bits > 0) return 0;

  }

  return 1;

}

static void AlphaApplyFilter(ALPHDecoder* const alph_dec, int first_row,

                             int last_row, uint8_t* out, int stride) {

  if (alph_dec->filter != WEBP_FILTER_NONE) {

    int y;

    const uint8_t* prev_line = alph_dec->prev_line;

    assert(WebPUnfilters[alph_dec->filter] != NULL);

    for (y = first_row; y < last_row; ++y) {

      WebPUnfilters[alph_dec->filter](prev_line, out, out, stride);

      prev_line = out;

      out += stride;

    }

    alph_dec->prev_line = prev_line;

  }

}

static void ExtractPalettedAlphaRows(VP8LDecoder* const dec, int last_row) {

  // For vertical and gradient filtering, we need to decode the part above the

  // crop_top row, in order to have the correct spatial predictors.

  ALPHDecoder* const alph_dec = (ALPHDecoder*)dec->io->opaque;

  const int top_row = (alph_dec->filter == WEBP_FILTER_NONE ||

                       alph_dec->filter == WEBP_FILTER_HORIZONTAL)

                          ? dec->io->crop_top

                          : dec->last_row;

  const int first_row = (dec->last_row < top_row) ? top_row : dec->last_row;

  assert(last_row <= dec->io->crop_bottom);

  if (last_row > first_row) {

    // Special method for paletted alpha data. We only process the cropped area.

    const int width = dec->io->width;