tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

vp8l_enc.c (71847B)

      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 lossless encoder.
     11 //
     12 // Author: Vikas Arora (vikaas.arora@gmail.com)
     13 //
     14 
     15 #include <assert.h>
     16 #include <stdlib.h>
     17 #include <string.h>
     18 
     19 #include "src/dsp/lossless.h"
     20 #include "src/dsp/lossless_common.h"
     21 #include "src/enc/backward_references_enc.h"
     22 #include "src/enc/histogram_enc.h"
     23 #include "src/enc/vp8i_enc.h"
     24 #include "src/enc/vp8li_enc.h"
     25 #include "src/utils/bit_writer_utils.h"
     26 #include "src/utils/huffman_encode_utils.h"
     27 #include "src/utils/palette.h"
     28 #include "src/utils/thread_utils.h"
     29 #include "src/utils/utils.h"
     30 #include "src/webp/encode.h"
     31 #include "src/webp/format_constants.h"
     32 #include "src/webp/types.h"
     33 
     34 // Maximum number of histogram images (sub-blocks).
     35 #define MAX_HUFF_IMAGE_SIZE       2600
     36 #define MAX_HUFFMAN_BITS (MIN_HUFFMAN_BITS + (1 << NUM_HUFFMAN_BITS) - 1)
     37 // Empirical value for which it becomes too computationally expensive to
     38 // compute the best predictor image.
     39 #define MAX_PREDICTOR_IMAGE_SIZE (1 << 14)
     40 
     41 // -----------------------------------------------------------------------------
     42 // Palette
     43 
     44 // These five modes are evaluated and their respective entropy is computed.
     45 typedef enum {
     46  kDirect = 0,
     47  kSpatial = 1,
     48  kSubGreen = 2,
     49  kSpatialSubGreen = 3,
     50  kPalette = 4,
     51  kPaletteAndSpatial = 5,
     52  kNumEntropyIx = 6
     53 } EntropyIx;
     54 
     55 typedef enum {
     56  kHistoAlpha = 0,
     57  kHistoAlphaPred,
     58  kHistoGreen,
     59  kHistoGreenPred,
     60  kHistoRed,
     61  kHistoRedPred,
     62  kHistoBlue,
     63  kHistoBluePred,
     64  kHistoRedSubGreen,
     65  kHistoRedPredSubGreen,
     66  kHistoBlueSubGreen,
     67  kHistoBluePredSubGreen,
     68  kHistoPalette,
     69  kHistoTotal  // Must be last.
     70 } HistoIx;
     71 
     72 
     73 #define NUM_BUCKETS 256
     74 
     75 typedef uint32_t HistogramBuckets[NUM_BUCKETS];
     76 
     77 // Keeping track of histograms, indexed by HistoIx.
     78 // Ideally, this would just be a struct with meaningful fields, but the
     79 // calculation of `entropy_comp` uses the index. One refactoring at a time :)
     80 typedef struct {
     81  HistogramBuckets category[kHistoTotal];
     82 } Histograms;
     83 
     84 static void AddSingleSubGreen(uint32_t p,
     85                              HistogramBuckets r, HistogramBuckets b) {
     86  const int green = (int)p >> 8;  // The upper bits are masked away later.
     87  ++r[(((int)p >> 16) - green) & 0xff];
     88  ++b[(((int)p >>  0) - green) & 0xff];
     89 }
     90 
     91 static void AddSingle(uint32_t p,
     92                      HistogramBuckets a, HistogramBuckets r,
     93                      HistogramBuckets g, HistogramBuckets b) {
     94  ++a[(p >> 24) & 0xff];
     95  ++r[(p >> 16) & 0xff];
     96  ++g[(p >>  8) & 0xff];
     97  ++b[(p >>  0) & 0xff];
     98 }
     99 
    100 static WEBP_INLINE uint8_t HashPix(uint32_t pix) {
    101  // Note that masking with 0xffffffffu is for preventing an
    102  // 'unsigned int overflow' warning. Doesn't impact the compiled code.
    103  return ((((uint64_t)pix + (pix >> 19)) * 0x39c5fba7ull) & 0xffffffffu) >> 24;
    104 }
    105 
    106 static int AnalyzeEntropy(const uint32_t* argb,
    107                          int width, int height, int argb_stride,
    108                          int use_palette,
    109                          int palette_size, int transform_bits,
    110                          EntropyIx* const min_entropy_ix,
    111                          int* const red_and_blue_always_zero) {
    112  Histograms* histo;
    113 
    114  if (use_palette && palette_size <= 16) {
    115    // In the case of small palettes, we pack 2, 4 or 8 pixels together. In
    116    // practice, small palettes are better than any other transform.
    117    *min_entropy_ix = kPalette;
    118    *red_and_blue_always_zero = 1;
    119    return 1;
    120  }
    121 
    122  histo = (Histograms*)WebPSafeCalloc(1, sizeof(*histo));
    123  if (histo != NULL) {
    124    int i, x, y;
    125    const uint32_t* prev_row = NULL;
    126    const uint32_t* curr_row = argb;
    127    uint32_t pix_prev = argb[0];  // Skip the first pixel.
    128    for (y = 0; y < height; ++y) {
    129      for (x = 0; x < width; ++x) {
    130        const uint32_t pix = curr_row[x];
    131        const uint32_t pix_diff = VP8LSubPixels(pix, pix_prev);
    132        pix_prev = pix;
    133        if ((pix_diff == 0) || (prev_row != NULL && pix == prev_row[x])) {
    134          continue;
    135        }
    136        AddSingle(pix,
    137                  histo->category[kHistoAlpha],
    138                  histo->category[kHistoRed],
    139                  histo->category[kHistoGreen],
    140                  histo->category[kHistoBlue]);
    141        AddSingle(pix_diff,
    142                  histo->category[kHistoAlphaPred],
    143                  histo->category[kHistoRedPred],
    144                  histo->category[kHistoGreenPred],
    145                  histo->category[kHistoBluePred]);
    146        AddSingleSubGreen(pix,
    147                          histo->category[kHistoRedSubGreen],
    148                          histo->category[kHistoBlueSubGreen]);
    149        AddSingleSubGreen(pix_diff,
    150                          histo->category[kHistoRedPredSubGreen],
    151                          histo->category[kHistoBluePredSubGreen]);
    152        {
    153          // Approximate the palette by the entropy of the multiplicative hash.
    154          const uint8_t hash = HashPix(pix);
    155          ++histo->category[kHistoPalette][hash];
    156        }
    157      }
    158      prev_row = curr_row;
    159      curr_row += argb_stride;
    160    }
    161    {
    162      uint64_t entropy_comp[kHistoTotal];
    163      uint64_t entropy[kNumEntropyIx];
    164      int k;
    165      int last_mode_to_analyze = use_palette ? kPalette : kSpatialSubGreen;
    166      int j;
    167      // Let's add one zero to the predicted histograms. The zeros are removed
    168      // too efficiently by the pix_diff == 0 comparison, at least one of the
    169      // zeros is likely to exist.
    170      ++histo->category[kHistoRedPredSubGreen][0];
    171      ++histo->category[kHistoBluePredSubGreen][0];
    172      ++histo->category[kHistoRedPred][0];
    173      ++histo->category[kHistoGreenPred][0];
    174      ++histo->category[kHistoBluePred][0];
    175      ++histo->category[kHistoAlphaPred][0];
    176 
    177      for (j = 0; j < kHistoTotal; ++j) {
    178        entropy_comp[j] = VP8LBitsEntropy(histo->category[j], NUM_BUCKETS);
    179      }
    180      entropy[kDirect] = entropy_comp[kHistoAlpha] +
    181          entropy_comp[kHistoRed] +
    182          entropy_comp[kHistoGreen] +
    183          entropy_comp[kHistoBlue];
    184      entropy[kSpatial] = entropy_comp[kHistoAlphaPred] +
    185          entropy_comp[kHistoRedPred] +
    186          entropy_comp[kHistoGreenPred] +
    187          entropy_comp[kHistoBluePred];
    188      entropy[kSubGreen] = entropy_comp[kHistoAlpha] +
    189          entropy_comp[kHistoRedSubGreen] +
    190          entropy_comp[kHistoGreen] +
    191          entropy_comp[kHistoBlueSubGreen];
    192      entropy[kSpatialSubGreen] = entropy_comp[kHistoAlphaPred] +
    193          entropy_comp[kHistoRedPredSubGreen] +
    194          entropy_comp[kHistoGreenPred] +
    195          entropy_comp[kHistoBluePredSubGreen];
    196      entropy[kPalette] = entropy_comp[kHistoPalette];
    197 
    198      // When including transforms, there is an overhead in bits from
    199      // storing them. This overhead is small but matters for small images.
    200      // For spatial, there are 14 transformations.
    201      entropy[kSpatial] += (uint64_t)VP8LSubSampleSize(width, transform_bits) *
    202                           VP8LSubSampleSize(height, transform_bits) *
    203                           VP8LFastLog2(14);
    204      // For color transforms: 24 as only 3 channels are considered in a
    205      // ColorTransformElement.
    206      entropy[kSpatialSubGreen] +=
    207          (uint64_t)VP8LSubSampleSize(width, transform_bits) *
    208          VP8LSubSampleSize(height, transform_bits) * VP8LFastLog2(24);
    209      // For palettes, add the cost of storing the palette.
    210      // We empirically estimate the cost of a compressed entry as 8 bits.
    211      // The palette is differential-coded when compressed hence a much
    212      // lower cost than sizeof(uint32_t)*8.
    213      entropy[kPalette] += (palette_size * 8ull) << LOG_2_PRECISION_BITS;
    214 
    215      *min_entropy_ix = kDirect;
    216      for (k = kDirect + 1; k <= last_mode_to_analyze; ++k) {
    217        if (entropy[*min_entropy_ix] > entropy[k]) {
    218          *min_entropy_ix = (EntropyIx)k;
    219        }
    220      }
    221      assert((int)*min_entropy_ix <= last_mode_to_analyze);
    222      *red_and_blue_always_zero = 1;
    223      // Let's check if the histogram of the chosen entropy mode has
    224      // non-zero red and blue values. If all are zero, we can later skip
    225      // the cross color optimization.
    226      {
    227        static const uint8_t kHistoPairs[5][2] = {
    228          { kHistoRed, kHistoBlue },
    229          { kHistoRedPred, kHistoBluePred },
    230          { kHistoRedSubGreen, kHistoBlueSubGreen },
    231          { kHistoRedPredSubGreen, kHistoBluePredSubGreen },
    232          { kHistoRed, kHistoBlue }
    233        };
    234        const HistogramBuckets* const red_histo =
    235            &histo->category[kHistoPairs[*min_entropy_ix][0]];
    236        const HistogramBuckets* const blue_histo =
    237            &histo->category[kHistoPairs[*min_entropy_ix][1]];
    238        for (i = 1; i < NUM_BUCKETS; ++i) {
    239          if (((*red_histo)[i] | (*blue_histo)[i]) != 0) {
    240            *red_and_blue_always_zero = 0;
    241            break;
    242          }
    243        }
    244      }
    245    }
    246    WebPSafeFree(histo);
    247    return 1;
    248  } else {
    249    return 0;
    250  }
    251 }
    252 
    253 // Clamp histogram and transform bits.
    254 static int ClampBits(int width, int height, int bits, int min_bits,
    255                     int max_bits, int image_size_max) {
    256  int image_size;
    257  bits = (bits < min_bits) ? min_bits : (bits > max_bits) ? max_bits : bits;
    258  image_size = VP8LSubSampleSize(width, bits) * VP8LSubSampleSize(height, bits);
    259  while (bits < max_bits && image_size > image_size_max) {
    260    ++bits;
    261    image_size =
    262        VP8LSubSampleSize(width, bits) * VP8LSubSampleSize(height, bits);
    263  }
    264  // In case the bits reduce the image too much, choose the smallest value
    265  // setting the histogram image size to 1.
    266  while (bits > min_bits && image_size == 1) {
    267    image_size = VP8LSubSampleSize(width, bits - 1) *
    268                 VP8LSubSampleSize(height, bits - 1);
    269    if (image_size != 1) break;
    270    --bits;
    271  }
    272  return bits;
    273 }
    274 
    275 static int GetHistoBits(int method, int use_palette, int width, int height) {
    276  // Make tile size a function of encoding method (Range: 0 to 6).
    277  const int histo_bits = (use_palette ? 9 : 7) - method;
    278  return ClampBits(width, height, histo_bits, MIN_HUFFMAN_BITS,
    279                   MAX_HUFFMAN_BITS, MAX_HUFF_IMAGE_SIZE);
    280 }
    281 
    282 static int GetTransformBits(int method, int histo_bits) {
    283  const int max_transform_bits = (method < 4) ? 6 : (method > 4) ? 4 : 5;
    284  const int res =
    285      (histo_bits > max_transform_bits) ? max_transform_bits : histo_bits;
    286  assert(res <= MAX_TRANSFORM_BITS);
    287  return res;
    288 }
    289 
    290 // Set of parameters to be used in each iteration of the cruncher.
    291 #define CRUNCH_SUBCONFIGS_MAX 2
    292 typedef struct {
    293  int lz77;
    294  int do_no_cache;
    295 } CrunchSubConfig;
    296 typedef struct {
    297  int entropy_idx;
    298  PaletteSorting palette_sorting_type;
    299  CrunchSubConfig sub_configs[CRUNCH_SUBCONFIGS_MAX];
    300  int sub_configs_size;
    301 } CrunchConfig;
    302 
    303 // +2 because we add a palette sorting configuration for kPalette and
    304 // kPaletteAndSpatial.
    305 #define CRUNCH_CONFIGS_MAX (kNumEntropyIx + 2 * kPaletteSortingNum)
    306 
    307 static int EncoderAnalyze(VP8LEncoder* const enc,
    308                          CrunchConfig crunch_configs[CRUNCH_CONFIGS_MAX],
    309                          int* const crunch_configs_size,
    310                          int* const red_and_blue_always_zero) {
    311  const WebPPicture* const pic = enc->pic;
    312  const int width = pic->width;
    313  const int height = pic->height;
    314  const WebPConfig* const config = enc->config;
    315  const int method = config->method;
    316  const int low_effort = (config->method == 0);
    317  int i;
    318  int use_palette, transform_bits;
    319  int n_lz77s;
    320  // If set to 0, analyze the cache with the computed cache value. If 1, also
    321  // analyze with no-cache.
    322  int do_no_cache = 0;
    323  assert(pic != NULL && pic->argb != NULL);
    324 
    325  // Check whether a palette is possible.
    326  enc->palette_size = GetColorPalette(pic, enc->palette_sorted);
    327  use_palette = (enc->palette_size <= MAX_PALETTE_SIZE);
    328  if (!use_palette) {
    329    enc->palette_size = 0;
    330  }
    331 
    332  // Empirical bit sizes.
    333  enc->histo_bits = GetHistoBits(method, use_palette,
    334                                 pic->width, pic->height);
    335  transform_bits = GetTransformBits(method, enc->histo_bits);
    336  enc->predictor_transform_bits = transform_bits;
    337  enc->cross_color_transform_bits = transform_bits;
    338 
    339  if (low_effort) {
    340    // AnalyzeEntropy is somewhat slow.
    341    crunch_configs[0].entropy_idx = use_palette ? kPalette : kSpatialSubGreen;
    342    crunch_configs[0].palette_sorting_type =
    343        use_palette ? kSortedDefault : kUnusedPalette;
    344    n_lz77s = 1;
    345    *crunch_configs_size = 1;
    346  } else {
    347    EntropyIx min_entropy_ix;
    348    // Try out multiple LZ77 on images with few colors.
    349    n_lz77s = (enc->palette_size > 0 && enc->palette_size <= 16) ? 2 : 1;
    350    if (!AnalyzeEntropy(pic->argb, width, height, pic->argb_stride, use_palette,
    351                        enc->palette_size, transform_bits, &min_entropy_ix,
    352                        red_and_blue_always_zero)) {
    353      return 0;
    354    }
    355    if (method == 6 && config->quality == 100) {
    356      do_no_cache = 1;
    357      // Go brute force on all transforms.
    358      *crunch_configs_size = 0;
    359      for (i = 0; i < kNumEntropyIx; ++i) {
    360        // We can only apply kPalette or kPaletteAndSpatial if we can indeed use
    361        // a palette.
    362        if ((i != kPalette && i != kPaletteAndSpatial) || use_palette) {
    363          assert(*crunch_configs_size < CRUNCH_CONFIGS_MAX);
    364          if (use_palette && (i == kPalette || i == kPaletteAndSpatial)) {
    365            int sorting_method;
    366            for (sorting_method = 0; sorting_method < kPaletteSortingNum;
    367                 ++sorting_method) {
    368              const PaletteSorting typed_sorting_method =
    369                  (PaletteSorting)sorting_method;
    370              // TODO(vrabaud) kSortedDefault should be tested. It is omitted
    371              // for now for backward compatibility.
    372              if (typed_sorting_method == kUnusedPalette ||
    373                  typed_sorting_method == kSortedDefault) {
    374                continue;
    375              }
    376              crunch_configs[(*crunch_configs_size)].entropy_idx = i;
    377              crunch_configs[(*crunch_configs_size)].palette_sorting_type =
    378                  typed_sorting_method;
    379              ++*crunch_configs_size;
    380            }
    381          } else {
    382            crunch_configs[(*crunch_configs_size)].entropy_idx = i;
    383            crunch_configs[(*crunch_configs_size)].palette_sorting_type =
    384                kUnusedPalette;
    385            ++*crunch_configs_size;
    386          }
    387        }
    388      }
    389    } else {
    390      // Only choose the guessed best transform.
    391      *crunch_configs_size = 1;
    392      crunch_configs[0].entropy_idx = min_entropy_ix;
    393      crunch_configs[0].palette_sorting_type =
    394          use_palette ? kMinimizeDelta : kUnusedPalette;
    395      if (config->quality >= 75 && method == 5) {
    396        // Test with and without color cache.
    397        do_no_cache = 1;
    398        // If we have a palette, also check in combination with spatial.
    399        if (min_entropy_ix == kPalette) {
    400          *crunch_configs_size = 2;
    401          crunch_configs[1].entropy_idx = kPaletteAndSpatial;
    402          crunch_configs[1].palette_sorting_type = kMinimizeDelta;
    403        }
    404      }
    405    }
    406  }
    407  // Fill in the different LZ77s.
    408  assert(n_lz77s <= CRUNCH_SUBCONFIGS_MAX);
    409  for (i = 0; i < *crunch_configs_size; ++i) {
    410    int j;
    411    for (j = 0; j < n_lz77s; ++j) {
    412      assert(j < CRUNCH_SUBCONFIGS_MAX);
    413      crunch_configs[i].sub_configs[j].lz77 =
    414          (j == 0) ? kLZ77Standard | kLZ77RLE : kLZ77Box;
    415      crunch_configs[i].sub_configs[j].do_no_cache = do_no_cache;
    416    }
    417    crunch_configs[i].sub_configs_size = n_lz77s;
    418  }
    419  return 1;
    420 }
    421 
    422 static int EncoderInit(VP8LEncoder* const enc) {
    423  const WebPPicture* const pic = enc->pic;
    424  const int width = pic->width;
    425  const int height = pic->height;
    426  const int pix_cnt = width * height;
    427  // we round the block size up, so we're guaranteed to have
    428  // at most MAX_REFS_BLOCK_PER_IMAGE blocks used:
    429  const int refs_block_size = (pix_cnt - 1) / MAX_REFS_BLOCK_PER_IMAGE + 1;
    430  int i;
    431  if (!VP8LHashChainInit(&enc->hash_chain, pix_cnt)) return 0;
    432 
    433  for (i = 0; i < 4; ++i) VP8LBackwardRefsInit(&enc->refs[i], refs_block_size);
    434 
    435  return 1;
    436 }
    437 
    438 // Returns false in case of memory error.
    439 static int GetHuffBitLengthsAndCodes(
    440    const VP8LHistogramSet* const histogram_image,
    441    HuffmanTreeCode* const huffman_codes) {
    442  int i, k;
    443  int ok = 0;
    444  uint64_t total_length_size = 0;
    445  uint8_t* mem_buf = NULL;
    446  const int histogram_image_size = histogram_image->size;
    447  int max_num_symbols = 0;
    448  uint8_t* buf_rle = NULL;
    449  HuffmanTree* huff_tree = NULL;
    450 
    451  // Iterate over all histograms and get the aggregate number of codes used.
    452  for (i = 0; i < histogram_image_size; ++i) {
    453    const VP8LHistogram* const histo = histogram_image->histograms[i];
    454    HuffmanTreeCode* const codes = &huffman_codes[5 * i];
    455    assert(histo != NULL);
    456    for (k = 0; k < 5; ++k) {
    457      const int num_symbols =
    458          (k == 0) ? VP8LHistogramNumCodes(histo->palette_code_bits) :
    459          (k == 4) ? NUM_DISTANCE_CODES : 256;
    460      codes[k].num_symbols = num_symbols;
    461      total_length_size += num_symbols;
    462    }
    463  }
    464 
    465  // Allocate and Set Huffman codes.
    466  {
    467    uint16_t* codes;
    468    uint8_t* lengths;
    469    mem_buf = (uint8_t*)WebPSafeCalloc(total_length_size,
    470                                       sizeof(*lengths) + sizeof(*codes));
    471    if (mem_buf == NULL) goto End;
    472 
    473    codes = (uint16_t*)mem_buf;
    474    lengths = (uint8_t*)&codes[total_length_size];
    475    for (i = 0; i < 5 * histogram_image_size; ++i) {
    476      const int bit_length = huffman_codes[i].num_symbols;
    477      huffman_codes[i].codes = codes;
    478      huffman_codes[i].code_lengths = lengths;
    479      codes += bit_length;
    480      lengths += bit_length;
    481      if (max_num_symbols < bit_length) {
    482        max_num_symbols = bit_length;
    483      }
    484    }
    485  }
    486 
    487  buf_rle = (uint8_t*)WebPSafeMalloc(1ULL, max_num_symbols);
    488  huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * max_num_symbols,
    489                                           sizeof(*huff_tree));
    490  if (buf_rle == NULL || huff_tree == NULL) goto End;
    491 
    492  // Create Huffman trees.
    493  for (i = 0; i < histogram_image_size; ++i) {
    494    HuffmanTreeCode* const codes = &huffman_codes[5 * i];
    495    VP8LHistogram* const histo = histogram_image->histograms[i];
    496    VP8LCreateHuffmanTree(histo->literal, 15, buf_rle, huff_tree, codes + 0);
    497    VP8LCreateHuffmanTree(histo->red, 15, buf_rle, huff_tree, codes + 1);
    498    VP8LCreateHuffmanTree(histo->blue, 15, buf_rle, huff_tree, codes + 2);
    499    VP8LCreateHuffmanTree(histo->alpha, 15, buf_rle, huff_tree, codes + 3);
    500    VP8LCreateHuffmanTree(histo->distance, 15, buf_rle, huff_tree, codes + 4);
    501  }
    502  ok = 1;
    503 End:
    504  WebPSafeFree(huff_tree);
    505  WebPSafeFree(buf_rle);
    506  if (!ok) {
    507    WebPSafeFree(mem_buf);
    508    memset(huffman_codes, 0, 5 * histogram_image_size * sizeof(*huffman_codes));
    509  }
    510  return ok;
    511 }
    512 
    513 static void StoreHuffmanTreeOfHuffmanTreeToBitMask(
    514    VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) {
    515  // RFC 1951 will calm you down if you are worried about this funny sequence.
    516  // This sequence is tuned from that, but more weighted for lower symbol count,
    517  // and more spiking histograms.
    518  static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = {
    519    17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
    520  };
    521  int i;
    522  // Throw away trailing zeros:
    523  int codes_to_store = CODE_LENGTH_CODES;
    524  for (; codes_to_store > 4; --codes_to_store) {
    525    if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
    526      break;
    527    }
    528  }
    529  VP8LPutBits(bw, codes_to_store - 4, 4);
    530  for (i = 0; i < codes_to_store; ++i) {
    531    VP8LPutBits(bw, code_length_bitdepth[kStorageOrder[i]], 3);
    532  }
    533 }
    534 
    535 static void ClearHuffmanTreeIfOnlyOneSymbol(
    536    HuffmanTreeCode* const huffman_code) {
    537  int k;
    538  int count = 0;
    539  for (k = 0; k < huffman_code->num_symbols; ++k) {
    540    if (huffman_code->code_lengths[k] != 0) {
    541      ++count;
    542      if (count > 1) return;
    543    }
    544  }
    545  for (k = 0; k < huffman_code->num_symbols; ++k) {
    546    huffman_code->code_lengths[k] = 0;
    547    huffman_code->codes[k] = 0;
    548  }
    549 }
    550 
    551 static void StoreHuffmanTreeToBitMask(
    552    VP8LBitWriter* const bw,
    553    const HuffmanTreeToken* const tokens, const int num_tokens,
    554    const HuffmanTreeCode* const huffman_code) {
    555  int i;
    556  for (i = 0; i < num_tokens; ++i) {
    557    const int ix = tokens[i].code;
    558    const int extra_bits = tokens[i].extra_bits;
    559    VP8LPutBits(bw, huffman_code->codes[ix], huffman_code->code_lengths[ix]);
    560    switch (ix) {
    561      case 16:
    562        VP8LPutBits(bw, extra_bits, 2);
    563        break;
    564      case 17:
    565        VP8LPutBits(bw, extra_bits, 3);
    566        break;
    567      case 18:
    568        VP8LPutBits(bw, extra_bits, 7);
    569        break;
    570    }
    571  }
    572 }
    573 
    574 // 'huff_tree' and 'tokens' are pre-alloacted buffers.
    575 static void StoreFullHuffmanCode(VP8LBitWriter* const bw,
    576                                 HuffmanTree* const huff_tree,
    577                                 HuffmanTreeToken* const tokens,
    578                                 const HuffmanTreeCode* const tree) {
    579  uint8_t code_length_bitdepth[CODE_LENGTH_CODES] = { 0 };
    580  uint16_t code_length_bitdepth_symbols[CODE_LENGTH_CODES] = { 0 };
    581  const int max_tokens = tree->num_symbols;
    582  int num_tokens;
    583  HuffmanTreeCode huffman_code;
    584  huffman_code.num_symbols = CODE_LENGTH_CODES;
    585  huffman_code.code_lengths = code_length_bitdepth;
    586  huffman_code.codes = code_length_bitdepth_symbols;
    587 
    588  VP8LPutBits(bw, 0, 1);
    589  num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens);
    590  {
    591    uint32_t histogram[CODE_LENGTH_CODES] = { 0 };
    592    uint8_t buf_rle[CODE_LENGTH_CODES] = { 0 };
    593    int i;
    594    for (i = 0; i < num_tokens; ++i) {
    595      ++histogram[tokens[i].code];
    596    }
    597 
    598    VP8LCreateHuffmanTree(histogram, 7, buf_rle, huff_tree, &huffman_code);
    599  }
    600 
    601  StoreHuffmanTreeOfHuffmanTreeToBitMask(bw, code_length_bitdepth);
    602  ClearHuffmanTreeIfOnlyOneSymbol(&huffman_code);
    603  {
    604    int trailing_zero_bits = 0;
    605    int trimmed_length = num_tokens;
    606    int write_trimmed_length;
    607    int length;
    608    int i = num_tokens;
    609    while (i-- > 0) {
    610      const int ix = tokens[i].code;
    611      if (ix == 0 || ix == 17 || ix == 18) {
    612        --trimmed_length;   // discount trailing zeros
    613        trailing_zero_bits += code_length_bitdepth[ix];
    614        if (ix == 17) {
    615          trailing_zero_bits += 3;
    616        } else if (ix == 18) {
    617          trailing_zero_bits += 7;
    618        }
    619      } else {
    620        break;
    621      }
    622    }
    623    write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12);
    624    length = write_trimmed_length ? trimmed_length : num_tokens;
    625    VP8LPutBits(bw, write_trimmed_length, 1);
    626    if (write_trimmed_length) {
    627      if (trimmed_length == 2) {
    628        VP8LPutBits(bw, 0, 3 + 2);     // nbitpairs=1, trimmed_length=2
    629      } else {
    630        const int nbits = BitsLog2Floor(trimmed_length - 2);
    631        const int nbitpairs = nbits / 2 + 1;
    632        assert(trimmed_length > 2);
    633        assert(nbitpairs - 1 < 8);
    634        VP8LPutBits(bw, nbitpairs - 1, 3);
    635        VP8LPutBits(bw, trimmed_length - 2, nbitpairs * 2);
    636      }
    637    }
    638    StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code);
    639  }
    640 }
    641 
    642 // 'huff_tree' and 'tokens' are pre-alloacted buffers.
    643 static void StoreHuffmanCode(VP8LBitWriter* const bw,
    644                             HuffmanTree* const huff_tree,
    645                             HuffmanTreeToken* const tokens,
    646                             const HuffmanTreeCode* const huffman_code) {
    647  int i;
    648  int count = 0;
    649  int symbols[2] = { 0, 0 };
    650  const int kMaxBits = 8;
    651  const int kMaxSymbol = 1 << kMaxBits;
    652 
    653  // Check whether it's a small tree.
    654  for (i = 0; i < huffman_code->num_symbols && count < 3; ++i) {
    655    if (huffman_code->code_lengths[i] != 0) {
    656      if (count < 2) symbols[count] = i;
    657      ++count;
    658    }
    659  }
    660 
    661  if (count == 0) {   // emit minimal tree for empty cases
    662    // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0
    663    VP8LPutBits(bw, 0x01, 4);
    664  } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) {
    665    VP8LPutBits(bw, 1, 1);  // Small tree marker to encode 1 or 2 symbols.
    666    VP8LPutBits(bw, count - 1, 1);
    667    if (symbols[0] <= 1) {
    668      VP8LPutBits(bw, 0, 1);  // Code bit for small (1 bit) symbol value.
    669      VP8LPutBits(bw, symbols[0], 1);
    670    } else {
    671      VP8LPutBits(bw, 1, 1);
    672      VP8LPutBits(bw, symbols[0], 8);
    673    }
    674    if (count == 2) {
    675      VP8LPutBits(bw, symbols[1], 8);
    676    }
    677  } else {
    678    StoreFullHuffmanCode(bw, huff_tree, tokens, huffman_code);
    679  }
    680 }
    681 
    682 static WEBP_INLINE void WriteHuffmanCode(VP8LBitWriter* const bw,
    683                             const HuffmanTreeCode* const code,
    684                             int code_index) {
    685  const int depth = code->code_lengths[code_index];
    686  const int symbol = code->codes[code_index];
    687  VP8LPutBits(bw, symbol, depth);
    688 }
    689 
    690 static WEBP_INLINE void WriteHuffmanCodeWithExtraBits(
    691    VP8LBitWriter* const bw,
    692    const HuffmanTreeCode* const code,
    693    int code_index,
    694    int bits,
    695    int n_bits) {
    696  const int depth = code->code_lengths[code_index];
    697  const int symbol = code->codes[code_index];
    698  VP8LPutBits(bw, (bits << depth) | symbol, depth + n_bits);
    699 }
    700 
    701 static int StoreImageToBitMask(VP8LBitWriter* const bw, int width,
    702                               int histo_bits,
    703                               const VP8LBackwardRefs* const refs,
    704                               const uint32_t* histogram_symbols,
    705                               const HuffmanTreeCode* const huffman_codes,
    706                               const WebPPicture* const pic) {
    707  const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1;
    708  const int tile_mask = (histo_bits == 0) ? 0 : -(1 << histo_bits);
    709  // x and y trace the position in the image.
    710  int x = 0;
    711  int y = 0;
    712  int tile_x = x & tile_mask;
    713  int tile_y = y & tile_mask;
    714  int histogram_ix = (histogram_symbols[0] >> 8) & 0xffff;
    715  const HuffmanTreeCode* codes = huffman_codes + 5 * histogram_ix;
    716  VP8LRefsCursor c = VP8LRefsCursorInit(refs);
    717  while (VP8LRefsCursorOk(&c)) {
    718    const PixOrCopy* const v = c.cur_pos;
    719    if ((tile_x != (x & tile_mask)) || (tile_y != (y & tile_mask))) {
    720      tile_x = x & tile_mask;
    721      tile_y = y & tile_mask;
    722      histogram_ix = (histogram_symbols[(y >> histo_bits) * histo_xsize +
    723                                        (x >> histo_bits)] >>
    724                      8) &
    725                     0xffff;
    726      codes = huffman_codes + 5 * histogram_ix;
    727    }
    728    if (PixOrCopyIsLiteral(v)) {
    729      static const uint8_t order[] = { 1, 2, 0, 3 };
    730      int k;
    731      for (k = 0; k < 4; ++k) {
    732        const int code = PixOrCopyLiteral(v, order[k]);
    733        WriteHuffmanCode(bw, codes + k, code);
    734      }
    735    } else if (PixOrCopyIsCacheIdx(v)) {
    736      const int code = PixOrCopyCacheIdx(v);
    737      const int literal_ix = 256 + NUM_LENGTH_CODES + code;
    738      WriteHuffmanCode(bw, codes, literal_ix);
    739    } else {
    740      int bits, n_bits;
    741      int code;
    742 
    743      const int distance = PixOrCopyDistance(v);
    744      VP8LPrefixEncode(v->len, &code, &n_bits, &bits);
    745      WriteHuffmanCodeWithExtraBits(bw, codes, 256 + code, bits, n_bits);
    746 
    747      // Don't write the distance with the extra bits code since
    748      // the distance can be up to 18 bits of extra bits, and the prefix
    749      // 15 bits, totaling to 33, and our PutBits only supports up to 32 bits.
    750      VP8LPrefixEncode(distance, &code, &n_bits, &bits);
    751      WriteHuffmanCode(bw, codes + 4, code);
    752      VP8LPutBits(bw, bits, n_bits);
    753    }
    754    x += PixOrCopyLength(v);
    755    while (x >= width) {
    756      x -= width;
    757      ++y;
    758    }
    759    VP8LRefsCursorNext(&c);
    760  }
    761  if (bw->error) {
    762    return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    763  }
    764  return 1;
    765 }
    766 
    767 // Special case of EncodeImageInternal() for cache-bits=0, histo_bits=31.
    768 // pic and percent are for progress.
    769 static int EncodeImageNoHuffman(VP8LBitWriter* const bw,
    770                                const uint32_t* const argb,
    771                                VP8LHashChain* const hash_chain,
    772                                VP8LBackwardRefs* const refs_array, int width,
    773                                int height, int quality, int low_effort,
    774                                const WebPPicture* const pic, int percent_range,
    775                                int* const percent) {
    776  int i;
    777  int max_tokens = 0;
    778  VP8LBackwardRefs* refs;
    779  HuffmanTreeToken* tokens = NULL;
    780  HuffmanTreeCode huffman_codes[5] = {{0, NULL, NULL}};
    781  const uint32_t histogram_symbols[1] = {0};  // only one tree, one symbol
    782  int cache_bits = 0;
    783  VP8LHistogramSet* histogram_image = NULL;
    784  HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc(
    785      3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree));
    786  if (huff_tree == NULL) {
    787    WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    788    goto Error;
    789  }
    790 
    791  // Calculate backward references from ARGB image.
    792  if (!VP8LHashChainFill(hash_chain, quality, argb, width, height, low_effort,
    793                         pic, percent_range / 2, percent)) {
    794    goto Error;
    795  }
    796  if (!VP8LGetBackwardReferences(width, height, argb, quality, /*low_effort=*/0,
    797                                 kLZ77Standard | kLZ77RLE, cache_bits,
    798                                 /*do_no_cache=*/0, hash_chain, refs_array,
    799                                 &cache_bits, pic,
    800                                 percent_range - percent_range / 2, percent)) {
    801    goto Error;
    802  }
    803  refs = &refs_array[0];
    804  histogram_image = VP8LAllocateHistogramSet(1, cache_bits);
    805  if (histogram_image == NULL) {
    806    WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    807    goto Error;
    808  }
    809  VP8LHistogramSetClear(histogram_image);
    810 
    811  // Build histogram image and symbols from backward references.
    812  VP8LHistogramStoreRefs(refs, /*distance_modifier=*/NULL,
    813                         /*distance_modifier_arg0=*/0,
    814                         histogram_image->histograms[0]);
    815 
    816  // Create Huffman bit lengths and codes for each histogram image.
    817  assert(histogram_image->size == 1);
    818  if (!GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) {
    819    WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    820    goto Error;
    821  }
    822 
    823  // No color cache, no Huffman image.
    824  VP8LPutBits(bw, 0, 1);
    825 
    826  // Find maximum number of symbols for the huffman tree-set.
    827  for (i = 0; i < 5; ++i) {
    828    HuffmanTreeCode* const codes = &huffman_codes[i];
    829    if (max_tokens < codes->num_symbols) {
    830      max_tokens = codes->num_symbols;
    831    }
    832  }
    833 
    834  tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens));
    835  if (tokens == NULL) {
    836    WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    837    goto Error;
    838  }
    839 
    840  // Store Huffman codes.
    841  for (i = 0; i < 5; ++i) {
    842    HuffmanTreeCode* const codes = &huffman_codes[i];
    843    StoreHuffmanCode(bw, huff_tree, tokens, codes);
    844    ClearHuffmanTreeIfOnlyOneSymbol(codes);
    845  }
    846 
    847  // Store actual literals.
    848  if (!StoreImageToBitMask(bw, width, 0, refs, histogram_symbols, huffman_codes,
    849                           pic)) {
    850    goto Error;
    851  }
    852 
    853 Error:
    854  WebPSafeFree(tokens);
    855  WebPSafeFree(huff_tree);
    856  VP8LFreeHistogramSet(histogram_image);
    857  WebPSafeFree(huffman_codes[0].codes);
    858  return (pic->error_code == VP8_ENC_OK);
    859 }
    860 
    861 // pic and percent are for progress.
    862 static int EncodeImageInternal(
    863    VP8LBitWriter* const bw, const uint32_t* const argb,
    864    VP8LHashChain* const hash_chain, VP8LBackwardRefs refs_array[4], int width,
    865    int height, int quality, int low_effort, const CrunchConfig* const config,
    866    int* cache_bits, int histogram_bits_in, size_t init_byte_position,
    867    int* const hdr_size, int* const data_size, const WebPPicture* const pic,
    868    int percent_range, int* const percent) {
    869  const uint32_t histogram_image_xysize =
    870      VP8LSubSampleSize(width, histogram_bits_in) *
    871      VP8LSubSampleSize(height, histogram_bits_in);
    872  int remaining_percent = percent_range;
    873  int percent_start = *percent;
    874  VP8LHistogramSet* histogram_image = NULL;
    875  VP8LHistogram* tmp_histo = NULL;
    876  uint32_t i, histogram_image_size = 0;
    877  size_t bit_array_size = 0;
    878  HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc(
    879      3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree));
    880  HuffmanTreeToken* tokens = NULL;
    881  HuffmanTreeCode* huffman_codes = NULL;
    882  uint32_t* const histogram_argb = (uint32_t*)WebPSafeMalloc(
    883      histogram_image_xysize, sizeof(*histogram_argb));
    884  int sub_configs_idx;
    885  int cache_bits_init, write_histogram_image;
    886  VP8LBitWriter bw_init = *bw, bw_best;
    887  int hdr_size_tmp;
    888  VP8LHashChain hash_chain_histogram;  // histogram image hash chain
    889  size_t bw_size_best = ~(size_t)0;
    890  assert(histogram_bits_in >= MIN_HUFFMAN_BITS);
    891  assert(histogram_bits_in <= MAX_HUFFMAN_BITS);
    892  assert(hdr_size != NULL);
    893  assert(data_size != NULL);
    894 
    895  memset(&hash_chain_histogram, 0, sizeof(hash_chain_histogram));
    896  if (!VP8LBitWriterInit(&bw_best, 0)) {
    897    WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    898    goto Error;
    899  }
    900 
    901  // Make sure we can allocate the different objects.
    902  if (huff_tree == NULL || histogram_argb == NULL ||
    903      !VP8LHashChainInit(&hash_chain_histogram, histogram_image_xysize)) {
    904    WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    905    goto Error;
    906  }
    907 
    908  percent_range = remaining_percent / 5;
    909  if (!VP8LHashChainFill(hash_chain, quality, argb, width, height,
    910                         low_effort, pic, percent_range, percent)) {
    911    goto Error;
    912  }
    913  percent_start += percent_range;
    914  remaining_percent -= percent_range;
    915 
    916  // If the value is different from zero, it has been set during the palette
    917  // analysis.
    918  cache_bits_init = (*cache_bits == 0) ? MAX_COLOR_CACHE_BITS : *cache_bits;
    919  // If several iterations will happen, clone into bw_best.
    920  if ((config->sub_configs_size > 1 || config->sub_configs[0].do_no_cache) &&
    921      !VP8LBitWriterClone(bw, &bw_best)) {
    922    WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    923    goto Error;
    924  }
    925 
    926  for (sub_configs_idx = 0; sub_configs_idx < config->sub_configs_size;
    927       ++sub_configs_idx) {
    928    const CrunchSubConfig* const sub_config =
    929        &config->sub_configs[sub_configs_idx];
    930    int cache_bits_best, i_cache;
    931    int i_remaining_percent = remaining_percent / config->sub_configs_size;
    932    int i_percent_range = i_remaining_percent / 4;
    933    i_remaining_percent -= i_percent_range;
    934 
    935    if (!VP8LGetBackwardReferences(
    936            width, height, argb, quality, low_effort, sub_config->lz77,
    937            cache_bits_init, sub_config->do_no_cache, hash_chain,
    938            &refs_array[0], &cache_bits_best, pic, i_percent_range, percent)) {
    939      goto Error;
    940    }
    941 
    942    for (i_cache = 0; i_cache < (sub_config->do_no_cache ? 2 : 1); ++i_cache) {
    943      const int cache_bits_tmp = (i_cache == 0) ? cache_bits_best : 0;
    944      int histogram_bits = histogram_bits_in;
    945      // Speed-up: no need to study the no-cache case if it was already studied
    946      // in i_cache == 0.
    947      if (i_cache == 1 && cache_bits_best == 0) break;
    948 
    949      // Reset the bit writer for this iteration.
    950      VP8LBitWriterReset(&bw_init, bw);
    951 
    952      // Build histogram image and symbols from backward references.
    953      histogram_image =
    954          VP8LAllocateHistogramSet(histogram_image_xysize, cache_bits_tmp);
    955      tmp_histo = VP8LAllocateHistogram(cache_bits_tmp);
    956      if (histogram_image == NULL || tmp_histo == NULL) {
    957        WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    958        goto Error;
    959      }
    960 
    961      i_percent_range = i_remaining_percent / 3;
    962      i_remaining_percent -= i_percent_range;
    963      if (!VP8LGetHistoImageSymbols(
    964              width, height, &refs_array[i_cache], quality, low_effort,
    965              histogram_bits, cache_bits_tmp, histogram_image, tmp_histo,
    966              histogram_argb, pic, i_percent_range, percent)) {
    967        goto Error;
    968      }
    969      // Create Huffman bit lengths and codes for each histogram image.
    970      histogram_image_size = histogram_image->size;
    971      bit_array_size = 5 * histogram_image_size;
    972      huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size,
    973                                                       sizeof(*huffman_codes));
    974      // Note: some histogram_image entries may point to tmp_histos[], so the
    975      // latter need to outlive the following call to
    976      // GetHuffBitLengthsAndCodes().
    977      if (huffman_codes == NULL ||
    978          !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) {
    979        WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
    980        goto Error;
    981      }
    982      // Free combined histograms.
    983      VP8LFreeHistogramSet(histogram_image);
    984      histogram_image = NULL;
    985 
    986      // Free scratch histograms.
    987      VP8LFreeHistogram(tmp_histo);
    988      tmp_histo = NULL;
    989 
    990      // Color Cache parameters.
    991      if (cache_bits_tmp > 0) {
    992        VP8LPutBits(bw, 1, 1);
    993        VP8LPutBits(bw, cache_bits_tmp, 4);
    994      } else {
    995        VP8LPutBits(bw, 0, 1);
    996      }
    997 
    998      // Huffman image + meta huffman.
    999      histogram_image_size = 0;
   1000      for (i = 0; i < histogram_image_xysize; ++i) {
   1001        if (histogram_argb[i] >= histogram_image_size) {
   1002          histogram_image_size = histogram_argb[i] + 1;
   1003        }
   1004        histogram_argb[i] <<= 8;
   1005      }
   1006 
   1007      write_histogram_image = (histogram_image_size > 1);
   1008      VP8LPutBits(bw, write_histogram_image, 1);
   1009      if (write_histogram_image) {
   1010        VP8LOptimizeSampling(histogram_argb, width, height, histogram_bits_in,
   1011                             MAX_HUFFMAN_BITS, &histogram_bits);
   1012        VP8LPutBits(bw, histogram_bits - 2, 3);
   1013        i_percent_range = i_remaining_percent / 2;
   1014        i_remaining_percent -= i_percent_range;
   1015        if (!EncodeImageNoHuffman(
   1016                bw, histogram_argb, &hash_chain_histogram, &refs_array[2],
   1017                VP8LSubSampleSize(width, histogram_bits),
   1018                VP8LSubSampleSize(height, histogram_bits), quality, low_effort,
   1019                pic, i_percent_range, percent)) {
   1020          goto Error;
   1021        }
   1022      }
   1023 
   1024      // Store Huffman codes.
   1025      {
   1026        int max_tokens = 0;
   1027        // Find maximum number of symbols for the huffman tree-set.
   1028        for (i = 0; i < 5 * histogram_image_size; ++i) {
   1029          HuffmanTreeCode* const codes = &huffman_codes[i];
   1030          if (max_tokens < codes->num_symbols) {
   1031            max_tokens = codes->num_symbols;
   1032          }
   1033        }
   1034        tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens));
   1035        if (tokens == NULL) {
   1036          WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1037          goto Error;
   1038        }
   1039        for (i = 0; i < 5 * histogram_image_size; ++i) {
   1040          HuffmanTreeCode* const codes = &huffman_codes[i];
   1041          StoreHuffmanCode(bw, huff_tree, tokens, codes);
   1042          ClearHuffmanTreeIfOnlyOneSymbol(codes);
   1043        }
   1044      }
   1045      // Store actual literals.
   1046      hdr_size_tmp = (int)(VP8LBitWriterNumBytes(bw) - init_byte_position);
   1047      if (!StoreImageToBitMask(bw, width, histogram_bits, &refs_array[i_cache],
   1048                               histogram_argb, huffman_codes, pic)) {
   1049        goto Error;
   1050      }
   1051      // Keep track of the smallest image so far.
   1052      if (VP8LBitWriterNumBytes(bw) < bw_size_best) {
   1053        bw_size_best = VP8LBitWriterNumBytes(bw);
   1054        *cache_bits = cache_bits_tmp;
   1055        *hdr_size = hdr_size_tmp;
   1056        *data_size =
   1057            (int)(VP8LBitWriterNumBytes(bw) - init_byte_position - *hdr_size);
   1058        VP8LBitWriterSwap(bw, &bw_best);
   1059      }
   1060      WebPSafeFree(tokens);
   1061      tokens = NULL;
   1062      if (huffman_codes != NULL) {
   1063        WebPSafeFree(huffman_codes->codes);
   1064        WebPSafeFree(huffman_codes);
   1065        huffman_codes = NULL;
   1066      }
   1067    }
   1068  }
   1069  VP8LBitWriterSwap(bw, &bw_best);
   1070 
   1071  if (!WebPReportProgress(pic, percent_start + remaining_percent, percent)) {
   1072    goto Error;
   1073  }
   1074 
   1075 Error:
   1076  WebPSafeFree(tokens);
   1077  WebPSafeFree(huff_tree);
   1078  VP8LFreeHistogramSet(histogram_image);
   1079  VP8LFreeHistogram(tmp_histo);
   1080  VP8LHashChainClear(&hash_chain_histogram);
   1081  if (huffman_codes != NULL) {
   1082    WebPSafeFree(huffman_codes->codes);
   1083    WebPSafeFree(huffman_codes);
   1084  }
   1085  WebPSafeFree(histogram_argb);
   1086  VP8LBitWriterWipeOut(&bw_best);
   1087  return (pic->error_code == VP8_ENC_OK);
   1088 }
   1089 
   1090 // -----------------------------------------------------------------------------
   1091 // Transforms
   1092 
   1093 static void ApplySubtractGreen(VP8LEncoder* const enc, int width, int height,
   1094                               VP8LBitWriter* const bw) {
   1095  VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
   1096  VP8LPutBits(bw, SUBTRACT_GREEN_TRANSFORM, 2);
   1097  VP8LSubtractGreenFromBlueAndRed(enc->argb, width * height);
   1098 }
   1099 
   1100 static int ApplyPredictFilter(VP8LEncoder* const enc, int width, int height,
   1101                              int quality, int low_effort,
   1102                              int used_subtract_green, VP8LBitWriter* const bw,
   1103                              int percent_range, int* const percent,
   1104                              int* const best_bits) {
   1105  const int near_lossless_strength =
   1106      enc->use_palette ? 100 : enc->config->near_lossless;
   1107  const int max_bits = ClampBits(width, height, enc->predictor_transform_bits,
   1108                                 MIN_TRANSFORM_BITS, MAX_TRANSFORM_BITS,
   1109                                 MAX_PREDICTOR_IMAGE_SIZE);
   1110  const int min_bits = ClampBits(
   1111      width, height,
   1112      max_bits - 2 * (enc->config->method > 4 ? enc->config->method - 4 : 0),
   1113      MIN_TRANSFORM_BITS, MAX_TRANSFORM_BITS, MAX_PREDICTOR_IMAGE_SIZE);
   1114 
   1115  if (!VP8LResidualImage(width, height, min_bits, max_bits, low_effort,
   1116                         enc->argb, enc->argb_scratch, enc->transform_data,
   1117                         near_lossless_strength, enc->config->exact,
   1118                         used_subtract_green, enc->pic, percent_range / 2,
   1119                         percent, best_bits)) {
   1120    return 0;
   1121  }
   1122  VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
   1123  VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2);
   1124  assert(*best_bits >= MIN_TRANSFORM_BITS && *best_bits <= MAX_TRANSFORM_BITS);
   1125  VP8LPutBits(bw, *best_bits - MIN_TRANSFORM_BITS, NUM_TRANSFORM_BITS);
   1126  return EncodeImageNoHuffman(
   1127      bw, enc->transform_data, &enc->hash_chain, &enc->refs[0],
   1128      VP8LSubSampleSize(width, *best_bits),
   1129      VP8LSubSampleSize(height, *best_bits), quality, low_effort, enc->pic,
   1130      percent_range - percent_range / 2, percent);
   1131 }
   1132 
   1133 static int ApplyCrossColorFilter(VP8LEncoder* const enc, int width, int height,
   1134                                 int quality, int low_effort,
   1135                                 VP8LBitWriter* const bw, int percent_range,
   1136                                 int* const percent, int* const best_bits) {
   1137  const int min_bits = enc->cross_color_transform_bits;
   1138 
   1139  if (!VP8LColorSpaceTransform(width, height, min_bits, quality, enc->argb,
   1140                               enc->transform_data, enc->pic, percent_range / 2,
   1141                               percent, best_bits)) {
   1142    return 0;
   1143  }
   1144  VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
   1145  VP8LPutBits(bw, CROSS_COLOR_TRANSFORM, 2);
   1146  assert(*best_bits >= MIN_TRANSFORM_BITS && *best_bits <= MAX_TRANSFORM_BITS);
   1147  VP8LPutBits(bw, *best_bits - MIN_TRANSFORM_BITS, NUM_TRANSFORM_BITS);
   1148  return EncodeImageNoHuffman(
   1149      bw, enc->transform_data, &enc->hash_chain, &enc->refs[0],
   1150      VP8LSubSampleSize(width, *best_bits),
   1151      VP8LSubSampleSize(height, *best_bits), quality, low_effort, enc->pic,
   1152      percent_range - percent_range / 2, percent);
   1153 }
   1154 
   1155 // -----------------------------------------------------------------------------
   1156 
   1157 static int WriteRiffHeader(const WebPPicture* const pic, size_t riff_size,
   1158                           size_t vp8l_size) {
   1159  uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = {
   1160    'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P',
   1161    'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE,
   1162  };
   1163  PutLE32(riff + TAG_SIZE, (uint32_t)riff_size);
   1164  PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size);
   1165  return pic->writer(riff, sizeof(riff), pic);
   1166 }
   1167 
   1168 static int WriteImageSize(const WebPPicture* const pic,
   1169                          VP8LBitWriter* const bw) {
   1170  const int width = pic->width - 1;
   1171  const int height = pic->height - 1;
   1172  assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION);
   1173 
   1174  VP8LPutBits(bw, width, VP8L_IMAGE_SIZE_BITS);
   1175  VP8LPutBits(bw, height, VP8L_IMAGE_SIZE_BITS);
   1176  return !bw->error;
   1177 }
   1178 
   1179 static int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) {
   1180  VP8LPutBits(bw, has_alpha, 1);
   1181  VP8LPutBits(bw, VP8L_VERSION, VP8L_VERSION_BITS);
   1182  return !bw->error;
   1183 }
   1184 
   1185 static int WriteImage(const WebPPicture* const pic, VP8LBitWriter* const bw,
   1186                      size_t* const coded_size) {
   1187  const uint8_t* const webpll_data = VP8LBitWriterFinish(bw);
   1188  const size_t webpll_size = VP8LBitWriterNumBytes(bw);
   1189  const size_t vp8l_size = VP8L_SIGNATURE_SIZE + webpll_size;
   1190  const size_t pad = vp8l_size & 1;
   1191  const size_t riff_size = TAG_SIZE + CHUNK_HEADER_SIZE + vp8l_size + pad;
   1192  *coded_size = 0;
   1193 
   1194  if (bw->error) {
   1195    return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1196  }
   1197 
   1198  if (!WriteRiffHeader(pic, riff_size, vp8l_size) ||
   1199      !pic->writer(webpll_data, webpll_size, pic)) {
   1200    return WebPEncodingSetError(pic, VP8_ENC_ERROR_BAD_WRITE);
   1201  }
   1202 
   1203  if (pad) {
   1204    const uint8_t pad_byte[1] = { 0 };
   1205    if (!pic->writer(pad_byte, 1, pic)) {
   1206      return WebPEncodingSetError(pic, VP8_ENC_ERROR_BAD_WRITE);
   1207    }
   1208  }
   1209  *coded_size = CHUNK_HEADER_SIZE + riff_size;
   1210  return 1;
   1211 }
   1212 
   1213 // -----------------------------------------------------------------------------
   1214 
   1215 static void ClearTransformBuffer(VP8LEncoder* const enc) {
   1216  WebPSafeFree(enc->transform_mem);
   1217  enc->transform_mem = NULL;
   1218  enc->transform_mem_size = 0;
   1219 }
   1220 
   1221 // Allocates the memory for argb (W x H) buffer, 2 rows of context for
   1222 // prediction and transform data.
   1223 // Flags influencing the memory allocated:
   1224 //  enc->transform_bits
   1225 //  enc->use_predict, enc->use_cross_color
   1226 static int AllocateTransformBuffer(VP8LEncoder* const enc, int width,
   1227                                   int height) {
   1228  const uint64_t image_size = (uint64_t)width * height;
   1229  // VP8LResidualImage needs room for 2 scanlines of uint32 pixels with an extra
   1230  // pixel in each, plus 2 regular scanlines of bytes.
   1231  // TODO(skal): Clean up by using arithmetic in bytes instead of words.
   1232  const uint64_t argb_scratch_size =
   1233      enc->use_predict ? (width + 1) * 2 + (width * 2 + sizeof(uint32_t) - 1) /
   1234                                               sizeof(uint32_t)
   1235                        : 0;
   1236  const uint64_t transform_data_size =
   1237      (enc->use_predict || enc->use_cross_color)
   1238          ? (uint64_t)VP8LSubSampleSize(width, MIN_TRANSFORM_BITS) *
   1239                VP8LSubSampleSize(height, MIN_TRANSFORM_BITS)
   1240          : 0;
   1241  const uint64_t max_alignment_in_words =
   1242      (WEBP_ALIGN_CST + sizeof(uint32_t) - 1) / sizeof(uint32_t);
   1243  const uint64_t mem_size = image_size + max_alignment_in_words +
   1244                            argb_scratch_size + max_alignment_in_words +
   1245                            transform_data_size;
   1246  uint32_t* mem = enc->transform_mem;
   1247  if (mem == NULL || mem_size > enc->transform_mem_size) {
   1248    ClearTransformBuffer(enc);
   1249    mem = (uint32_t*)WebPSafeMalloc(mem_size, sizeof(*mem));
   1250    if (mem == NULL) {
   1251      return WebPEncodingSetError(enc->pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1252    }
   1253    enc->transform_mem = mem;
   1254    enc->transform_mem_size = (size_t)mem_size;
   1255    enc->argb_content = kEncoderNone;
   1256  }
   1257  enc->argb = mem;
   1258  mem = (uint32_t*)WEBP_ALIGN(mem + image_size);
   1259  enc->argb_scratch = mem;
   1260  mem = (uint32_t*)WEBP_ALIGN(mem + argb_scratch_size);
   1261  enc->transform_data = mem;
   1262 
   1263  enc->current_width = width;
   1264  return 1;
   1265 }
   1266 
   1267 static int MakeInputImageCopy(VP8LEncoder* const enc) {
   1268  const WebPPicture* const picture = enc->pic;
   1269  const int width = picture->width;
   1270  const int height = picture->height;
   1271 
   1272  if (!AllocateTransformBuffer(enc, width, height)) return 0;
   1273  if (enc->argb_content == kEncoderARGB) return 1;
   1274 
   1275  {
   1276    uint32_t* dst = enc->argb;
   1277    const uint32_t* src = picture->argb;
   1278    int y;
   1279    for (y = 0; y < height; ++y) {
   1280      memcpy(dst, src, width * sizeof(*dst));
   1281      dst += width;
   1282      src += picture->argb_stride;
   1283    }
   1284  }
   1285  enc->argb_content = kEncoderARGB;
   1286  assert(enc->current_width == width);
   1287  return 1;
   1288 }
   1289 
   1290 // -----------------------------------------------------------------------------
   1291 
   1292 #define APPLY_PALETTE_GREEDY_MAX 4
   1293 
   1294 static WEBP_INLINE uint32_t SearchColorGreedy(const uint32_t palette[],
   1295                                              int palette_size,
   1296                                              uint32_t color) {
   1297  (void)palette_size;
   1298  assert(palette_size < APPLY_PALETTE_GREEDY_MAX);
   1299  assert(3 == APPLY_PALETTE_GREEDY_MAX - 1);
   1300  if (color == palette[0]) return 0;
   1301  if (color == palette[1]) return 1;
   1302  if (color == palette[2]) return 2;
   1303  return 3;
   1304 }
   1305 
   1306 static WEBP_INLINE uint32_t ApplyPaletteHash0(uint32_t color) {
   1307  // Focus on the green color.
   1308  return (color >> 8) & 0xff;
   1309 }
   1310 
   1311 #define PALETTE_INV_SIZE_BITS 11
   1312 #define PALETTE_INV_SIZE (1 << PALETTE_INV_SIZE_BITS)
   1313 
   1314 static WEBP_INLINE uint32_t ApplyPaletteHash1(uint32_t color) {
   1315  // Forget about alpha.
   1316  return ((uint32_t)((color & 0x00ffffffu) * 4222244071ull)) >>
   1317         (32 - PALETTE_INV_SIZE_BITS);
   1318 }
   1319 
   1320 static WEBP_INLINE uint32_t ApplyPaletteHash2(uint32_t color) {
   1321  // Forget about alpha.
   1322  return ((uint32_t)((color & 0x00ffffffu) * ((1ull << 31) - 1))) >>
   1323         (32 - PALETTE_INV_SIZE_BITS);
   1324 }
   1325 
   1326 // Use 1 pixel cache for ARGB pixels.
   1327 #define APPLY_PALETTE_FOR(COLOR_INDEX) do {         \
   1328  uint32_t prev_pix = palette[0];                   \
   1329  uint32_t prev_idx = 0;                            \
   1330  for (y = 0; y < height; ++y) {                    \
   1331    for (x = 0; x < width; ++x) {                   \
   1332      const uint32_t pix = src[x];                  \
   1333      if (pix != prev_pix) {                        \
   1334        prev_idx = COLOR_INDEX;                     \
   1335        prev_pix = pix;                             \
   1336      }                                             \
   1337      tmp_row[x] = prev_idx;                        \
   1338    }                                               \
   1339    VP8LBundleColorMap(tmp_row, width, xbits, dst); \
   1340    src += src_stride;                              \
   1341    dst += dst_stride;                              \
   1342  }                                                 \
   1343 } while (0)
   1344 
   1345 // Remap argb values in src[] to packed palettes entries in dst[]
   1346 // using 'row' as a temporary buffer of size 'width'.
   1347 // We assume that all src[] values have a corresponding entry in the palette.
   1348 // Note: src[] can be the same as dst[]
   1349 static int ApplyPalette(const uint32_t* src, uint32_t src_stride, uint32_t* dst,
   1350                        uint32_t dst_stride, const uint32_t* palette,
   1351                        int palette_size, int width, int height, int xbits,
   1352                        const WebPPicture* const pic) {
   1353  // TODO(skal): this tmp buffer is not needed if VP8LBundleColorMap() can be
   1354  // made to work in-place.
   1355  uint8_t* const tmp_row = (uint8_t*)WebPSafeMalloc(width, sizeof(*tmp_row));
   1356  int x, y;
   1357 
   1358  if (tmp_row == NULL) {
   1359    return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1360  }
   1361 
   1362  if (palette_size < APPLY_PALETTE_GREEDY_MAX) {
   1363    APPLY_PALETTE_FOR(SearchColorGreedy(palette, palette_size, pix));
   1364  } else {
   1365    int i, j;
   1366    uint16_t buffer[PALETTE_INV_SIZE];
   1367    uint32_t (*const hash_functions[])(uint32_t) = {
   1368        ApplyPaletteHash0, ApplyPaletteHash1, ApplyPaletteHash2
   1369    };
   1370 
   1371    // Try to find a perfect hash function able to go from a color to an index
   1372    // within 1 << PALETTE_INV_SIZE_BITS in order to build a hash map to go
   1373    // from color to index in palette.
   1374    for (i = 0; i < 3; ++i) {
   1375      int use_LUT = 1;
   1376      // Set each element in buffer to max uint16_t.
   1377      memset(buffer, 0xff, sizeof(buffer));
   1378      for (j = 0; j < palette_size; ++j) {
   1379        const uint32_t ind = hash_functions[i](palette[j]);
   1380        if (buffer[ind] != 0xffffu) {
   1381          use_LUT = 0;
   1382          break;
   1383        } else {
   1384          buffer[ind] = j;
   1385        }
   1386      }
   1387      if (use_LUT) break;
   1388    }
   1389 
   1390    if (i == 0) {
   1391      APPLY_PALETTE_FOR(buffer[ApplyPaletteHash0(pix)]);
   1392    } else if (i == 1) {
   1393      APPLY_PALETTE_FOR(buffer[ApplyPaletteHash1(pix)]);
   1394    } else if (i == 2) {
   1395      APPLY_PALETTE_FOR(buffer[ApplyPaletteHash2(pix)]);
   1396    } else {
   1397      uint32_t idx_map[MAX_PALETTE_SIZE];
   1398      uint32_t palette_sorted[MAX_PALETTE_SIZE];
   1399      PrepareMapToPalette(palette, palette_size, palette_sorted, idx_map);
   1400      APPLY_PALETTE_FOR(
   1401          idx_map[SearchColorNoIdx(palette_sorted, pix, palette_size)]);
   1402    }
   1403  }
   1404  WebPSafeFree(tmp_row);
   1405  return 1;
   1406 }
   1407 #undef APPLY_PALETTE_FOR
   1408 #undef PALETTE_INV_SIZE_BITS
   1409 #undef PALETTE_INV_SIZE
   1410 #undef APPLY_PALETTE_GREEDY_MAX
   1411 
   1412 // Note: Expects "enc->palette" to be set properly.
   1413 static int MapImageFromPalette(VP8LEncoder* const enc) {
   1414  const WebPPicture* const pic = enc->pic;
   1415  const int width = pic->width;
   1416  const int height = pic->height;
   1417  const uint32_t* const palette = enc->palette;
   1418  const int palette_size = enc->palette_size;
   1419  int xbits;
   1420 
   1421  // Replace each input pixel by corresponding palette index.
   1422  // This is done line by line.
   1423  if (palette_size <= 4) {
   1424    xbits = (palette_size <= 2) ? 3 : 2;
   1425  } else {
   1426    xbits = (palette_size <= 16) ? 1 : 0;
   1427  }
   1428 
   1429  if (!AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height)) {
   1430    return 0;
   1431  }
   1432  if (!ApplyPalette(pic->argb, pic->argb_stride, enc->argb,
   1433                    enc->current_width, palette, palette_size, width, height,
   1434                    xbits, pic)) {
   1435    return 0;
   1436  }
   1437  enc->argb_content = kEncoderPalette;
   1438  return 1;
   1439 }
   1440 
   1441 // Save palette[] to bitstream.
   1442 static int EncodePalette(VP8LBitWriter* const bw, int low_effort,
   1443                         VP8LEncoder* const enc, int percent_range,
   1444                         int* const percent) {
   1445  int i;
   1446  uint32_t tmp_palette[MAX_PALETTE_SIZE];
   1447  const int palette_size = enc->palette_size;
   1448  const uint32_t* const palette = enc->palette;
   1449  // If the last element is 0, do not store it and count on automatic palette
   1450  // 0-filling. This can only happen if there is no pixel packing, hence if
   1451  // there are strictly more than 16 colors (after 0 is removed).
   1452  const uint32_t encoded_palette_size =
   1453      (enc->palette[palette_size - 1] == 0 && palette_size > 17)
   1454          ? palette_size - 1
   1455          : palette_size;
   1456  VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
   1457  VP8LPutBits(bw, COLOR_INDEXING_TRANSFORM, 2);
   1458  assert(palette_size >= 1 && palette_size <= MAX_PALETTE_SIZE);
   1459  VP8LPutBits(bw, encoded_palette_size - 1, 8);
   1460  for (i = encoded_palette_size - 1; i >= 1; --i) {
   1461    tmp_palette[i] = VP8LSubPixels(palette[i], palette[i - 1]);
   1462  }
   1463  tmp_palette[0] = palette[0];
   1464  return EncodeImageNoHuffman(
   1465      bw, tmp_palette, &enc->hash_chain, &enc->refs[0], encoded_palette_size,
   1466      1, /*quality=*/20, low_effort, enc->pic, percent_range, percent);
   1467 }
   1468 
   1469 // -----------------------------------------------------------------------------
   1470 // VP8LEncoder
   1471 
   1472 static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config,
   1473                                   const WebPPicture* const picture) {
   1474  VP8LEncoder* const enc = (VP8LEncoder*)WebPSafeCalloc(1ULL, sizeof(*enc));
   1475  if (enc == NULL) {
   1476    WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1477    return NULL;
   1478  }
   1479  enc->config = config;
   1480  enc->pic = picture;
   1481  enc->argb_content = kEncoderNone;
   1482 
   1483  VP8LEncDspInit();
   1484 
   1485  return enc;
   1486 }
   1487 
   1488 static void VP8LEncoderDelete(VP8LEncoder* enc) {
   1489  if (enc != NULL) {
   1490    int i;
   1491    VP8LHashChainClear(&enc->hash_chain);
   1492    for (i = 0; i < 4; ++i) VP8LBackwardRefsClear(&enc->refs[i]);
   1493    ClearTransformBuffer(enc);
   1494    WebPSafeFree(enc);
   1495  }
   1496 }
   1497 
   1498 // -----------------------------------------------------------------------------
   1499 // Main call
   1500 
   1501 typedef struct {
   1502  const WebPConfig* config;
   1503  const WebPPicture* picture;
   1504  VP8LBitWriter* bw;
   1505  VP8LEncoder* enc;
   1506  CrunchConfig crunch_configs[CRUNCH_CONFIGS_MAX];
   1507  int num_crunch_configs;
   1508  int red_and_blue_always_zero;
   1509  WebPAuxStats* stats;
   1510 } StreamEncodeContext;
   1511 
   1512 static int EncodeStreamHook(void* input, void* data2) {
   1513  StreamEncodeContext* const params = (StreamEncodeContext*)input;
   1514  const WebPConfig* const config = params->config;
   1515  const WebPPicture* const picture = params->picture;
   1516  VP8LBitWriter* const bw = params->bw;
   1517  VP8LEncoder* const enc = params->enc;
   1518  const CrunchConfig* const crunch_configs = params->crunch_configs;
   1519  const int num_crunch_configs = params->num_crunch_configs;
   1520  const int red_and_blue_always_zero = params->red_and_blue_always_zero;
   1521 #if !defined(WEBP_DISABLE_STATS)
   1522  WebPAuxStats* const stats = params->stats;
   1523 #endif
   1524  const int quality = (int)config->quality;
   1525  const int low_effort = (config->method == 0);
   1526 #if (WEBP_NEAR_LOSSLESS == 1)
   1527  const int width = picture->width;
   1528 #endif
   1529  const int height = picture->height;
   1530  const size_t byte_position = VP8LBitWriterNumBytes(bw);
   1531  int percent = 2;  // for WebPProgressHook
   1532 #if (WEBP_NEAR_LOSSLESS == 1)
   1533  int use_near_lossless = 0;
   1534 #endif
   1535  int hdr_size = 0;
   1536  int data_size = 0;
   1537  int idx;
   1538  size_t best_size = ~(size_t)0;
   1539  VP8LBitWriter bw_init = *bw, bw_best;
   1540  (void)data2;
   1541 
   1542  if (!VP8LBitWriterInit(&bw_best, 0) ||
   1543      (num_crunch_configs > 1 && !VP8LBitWriterClone(bw, &bw_best))) {
   1544    WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1545    goto Error;
   1546  }
   1547 
   1548  for (idx = 0; idx < num_crunch_configs; ++idx) {
   1549    const int entropy_idx = crunch_configs[idx].entropy_idx;
   1550    int remaining_percent = 97 / num_crunch_configs, percent_range;
   1551    int predictor_transform_bits = 0, cross_color_transform_bits = 0;
   1552    enc->use_palette =
   1553        (entropy_idx == kPalette) || (entropy_idx == kPaletteAndSpatial);
   1554    enc->use_subtract_green =
   1555        (entropy_idx == kSubGreen) || (entropy_idx == kSpatialSubGreen);
   1556    enc->use_predict = (entropy_idx == kSpatial) ||
   1557                       (entropy_idx == kSpatialSubGreen) ||
   1558                       (entropy_idx == kPaletteAndSpatial);
   1559    // When using a palette, R/B==0, hence no need to test for cross-color.
   1560    if (low_effort || enc->use_palette) {
   1561      enc->use_cross_color = 0;
   1562    } else {
   1563      enc->use_cross_color = red_and_blue_always_zero ? 0 : enc->use_predict;
   1564    }
   1565    // Reset any parameter in the encoder that is set in the previous iteration.
   1566    enc->cache_bits = 0;
   1567    VP8LBackwardRefsClear(&enc->refs[0]);
   1568    VP8LBackwardRefsClear(&enc->refs[1]);
   1569 
   1570 #if (WEBP_NEAR_LOSSLESS == 1)
   1571    // Apply near-lossless preprocessing.
   1572    use_near_lossless = (config->near_lossless < 100) && !enc->use_palette &&
   1573                        !enc->use_predict;
   1574    if (use_near_lossless) {
   1575      if (!AllocateTransformBuffer(enc, width, height)) goto Error;
   1576      if ((enc->argb_content != kEncoderNearLossless) &&
   1577          !VP8ApplyNearLossless(picture, config->near_lossless, enc->argb)) {
   1578        WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1579        goto Error;
   1580      }
   1581      enc->argb_content = kEncoderNearLossless;
   1582    } else {
   1583      enc->argb_content = kEncoderNone;
   1584    }
   1585 #else
   1586    enc->argb_content = kEncoderNone;
   1587 #endif
   1588 
   1589    // Encode palette
   1590    if (enc->use_palette) {
   1591      if (!PaletteSort(crunch_configs[idx].palette_sorting_type, enc->pic,
   1592                       enc->palette_sorted, enc->palette_size,
   1593                       enc->palette)) {
   1594        WebPEncodingSetError(enc->pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1595        goto Error;
   1596      }
   1597      percent_range = remaining_percent / 4;
   1598      if (!EncodePalette(bw, low_effort, enc, percent_range, &percent)) {
   1599        goto Error;
   1600      }
   1601      remaining_percent -= percent_range;
   1602      if (!MapImageFromPalette(enc)) goto Error;
   1603      // If using a color cache, do not have it bigger than the number of
   1604      // colors.
   1605      if (enc->palette_size < (1 << MAX_COLOR_CACHE_BITS)) {
   1606        enc->cache_bits = BitsLog2Floor(enc->palette_size) + 1;
   1607      }
   1608    }
   1609    // In case image is not packed.
   1610    if (enc->argb_content != kEncoderNearLossless &&
   1611        enc->argb_content != kEncoderPalette) {
   1612      if (!MakeInputImageCopy(enc)) goto Error;
   1613    }
   1614 
   1615    // -------------------------------------------------------------------------
   1616    // Apply transforms and write transform data.
   1617 
   1618    if (enc->use_subtract_green) {
   1619      ApplySubtractGreen(enc, enc->current_width, height, bw);
   1620    }
   1621 
   1622    if (enc->use_predict) {
   1623      percent_range = remaining_percent / 3;
   1624      if (!ApplyPredictFilter(enc, enc->current_width, height, quality,
   1625                              low_effort, enc->use_subtract_green, bw,
   1626                              percent_range, &percent,
   1627                              &predictor_transform_bits)) {
   1628        goto Error;
   1629      }
   1630      remaining_percent -= percent_range;
   1631    }
   1632 
   1633    if (enc->use_cross_color) {
   1634      percent_range = remaining_percent / 2;
   1635      if (!ApplyCrossColorFilter(enc, enc->current_width, height, quality,
   1636                                 low_effort, bw, percent_range, &percent,
   1637                                 &cross_color_transform_bits)) {
   1638        goto Error;
   1639      }
   1640      remaining_percent -= percent_range;
   1641    }
   1642 
   1643    VP8LPutBits(bw, !TRANSFORM_PRESENT, 1);  // No more transforms.
   1644 
   1645    // -------------------------------------------------------------------------
   1646    // Encode and write the transformed image.
   1647    if (!EncodeImageInternal(
   1648            bw, enc->argb, &enc->hash_chain, enc->refs, enc->current_width,
   1649            height, quality, low_effort, &crunch_configs[idx],
   1650            &enc->cache_bits, enc->histo_bits, byte_position, &hdr_size,
   1651            &data_size, picture, remaining_percent, &percent)) {
   1652      goto Error;
   1653    }
   1654 
   1655    // If we are better than what we already have.
   1656    if (VP8LBitWriterNumBytes(bw) < best_size) {
   1657      best_size = VP8LBitWriterNumBytes(bw);
   1658      // Store the BitWriter.
   1659      VP8LBitWriterSwap(bw, &bw_best);
   1660 #if !defined(WEBP_DISABLE_STATS)
   1661      // Update the stats.
   1662      if (stats != NULL) {
   1663        stats->lossless_features = 0;
   1664        if (enc->use_predict) stats->lossless_features |= 1;
   1665        if (enc->use_cross_color) stats->lossless_features |= 2;
   1666        if (enc->use_subtract_green) stats->lossless_features |= 4;
   1667        if (enc->use_palette) stats->lossless_features |= 8;
   1668        stats->histogram_bits = enc->histo_bits;
   1669        stats->transform_bits = predictor_transform_bits;
   1670        stats->cross_color_transform_bits = cross_color_transform_bits;
   1671        stats->cache_bits = enc->cache_bits;
   1672        stats->palette_size = enc->palette_size;
   1673        stats->lossless_size = (int)(best_size - byte_position);
   1674        stats->lossless_hdr_size = hdr_size;
   1675        stats->lossless_data_size = data_size;
   1676      }
   1677 #endif
   1678    }
   1679    // Reset the bit writer for the following iteration if any.
   1680    if (num_crunch_configs > 1) VP8LBitWriterReset(&bw_init, bw);
   1681  }
   1682  VP8LBitWriterSwap(&bw_best, bw);
   1683 
   1684 Error:
   1685  VP8LBitWriterWipeOut(&bw_best);
   1686  // The hook should return false in case of error.
   1687  return (params->picture->error_code == VP8_ENC_OK);
   1688 }
   1689 
   1690 int VP8LEncodeStream(const WebPConfig* const config,
   1691                     const WebPPicture* const picture,
   1692                     VP8LBitWriter* const bw_main) {
   1693  VP8LEncoder* const enc_main = VP8LEncoderNew(config, picture);
   1694  VP8LEncoder* enc_side = NULL;
   1695  CrunchConfig crunch_configs[CRUNCH_CONFIGS_MAX];
   1696  int num_crunch_configs_main, num_crunch_configs_side = 0;
   1697  int idx;
   1698  int red_and_blue_always_zero = 0;
   1699  WebPWorker worker_main, worker_side;
   1700  StreamEncodeContext params_main, params_side;
   1701  // The main thread uses picture->stats, the side thread uses stats_side.
   1702  WebPAuxStats stats_side;
   1703  VP8LBitWriter bw_side;
   1704  WebPPicture picture_side;
   1705  const WebPWorkerInterface* const worker_interface = WebPGetWorkerInterface();
   1706  int ok_main;
   1707 
   1708  if (enc_main == NULL || !VP8LBitWriterInit(&bw_side, 0)) {
   1709    VP8LEncoderDelete(enc_main);
   1710    return WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1711  }
   1712 
   1713  // Avoid "garbage value" error from Clang's static analysis tool.
   1714  if (!WebPPictureInit(&picture_side)) {
   1715    goto Error;
   1716  }
   1717 
   1718  // Analyze image (entropy, num_palettes etc)
   1719  if (!EncoderAnalyze(enc_main, crunch_configs, &num_crunch_configs_main,
   1720                      &red_and_blue_always_zero) ||
   1721      !EncoderInit(enc_main)) {
   1722    WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1723    goto Error;
   1724  }
   1725 
   1726  // Split the configs between the main and side threads (if any).
   1727  if (config->thread_level > 0) {
   1728    num_crunch_configs_side = num_crunch_configs_main / 2;
   1729    for (idx = 0; idx < num_crunch_configs_side; ++idx) {
   1730      params_side.crunch_configs[idx] =
   1731          crunch_configs[num_crunch_configs_main - num_crunch_configs_side +
   1732                         idx];
   1733    }
   1734    params_side.num_crunch_configs = num_crunch_configs_side;
   1735  }
   1736  num_crunch_configs_main -= num_crunch_configs_side;
   1737  for (idx = 0; idx < num_crunch_configs_main; ++idx) {
   1738    params_main.crunch_configs[idx] = crunch_configs[idx];
   1739  }
   1740  params_main.num_crunch_configs = num_crunch_configs_main;
   1741 
   1742  // Fill in the parameters for the thread workers.
   1743  {
   1744    const int params_size = (num_crunch_configs_side > 0) ? 2 : 1;
   1745    for (idx = 0; idx < params_size; ++idx) {
   1746      // Create the parameters for each worker.
   1747      WebPWorker* const worker = (idx == 0) ? &worker_main : &worker_side;
   1748      StreamEncodeContext* const param =
   1749          (idx == 0) ? &params_main : &params_side;
   1750      param->config = config;
   1751      param->red_and_blue_always_zero = red_and_blue_always_zero;
   1752      if (idx == 0) {
   1753        param->picture = picture;
   1754        param->stats = picture->stats;
   1755        param->bw = bw_main;
   1756        param->enc = enc_main;
   1757      } else {
   1758        // Create a side picture (error_code is not thread-safe).
   1759        if (!WebPPictureView(picture, /*left=*/0, /*top=*/0, picture->width,
   1760                             picture->height, &picture_side)) {
   1761          assert(0);
   1762        }
   1763        picture_side.progress_hook = NULL;  // Progress hook is not thread-safe.
   1764        param->picture = &picture_side;  // No need to free a view afterwards.
   1765        param->stats = (picture->stats == NULL) ? NULL : &stats_side;
   1766        // Create a side bit writer.
   1767        if (!VP8LBitWriterClone(bw_main, &bw_side)) {
   1768          WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1769          goto Error;
   1770        }
   1771        param->bw = &bw_side;
   1772        // Create a side encoder.
   1773        enc_side = VP8LEncoderNew(config, &picture_side);
   1774        if (enc_side == NULL || !EncoderInit(enc_side)) {
   1775          WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1776          goto Error;
   1777        }
   1778        // Copy the values that were computed for the main encoder.
   1779        enc_side->histo_bits = enc_main->histo_bits;
   1780        enc_side->predictor_transform_bits =
   1781            enc_main->predictor_transform_bits;
   1782        enc_side->cross_color_transform_bits =
   1783            enc_main->cross_color_transform_bits;
   1784        enc_side->palette_size = enc_main->palette_size;
   1785        memcpy(enc_side->palette, enc_main->palette,
   1786               sizeof(enc_main->palette));
   1787        memcpy(enc_side->palette_sorted, enc_main->palette_sorted,
   1788               sizeof(enc_main->palette_sorted));
   1789        param->enc = enc_side;
   1790      }
   1791      // Create the workers.
   1792      worker_interface->Init(worker);
   1793      worker->data1 = param;
   1794      worker->data2 = NULL;
   1795      worker->hook = EncodeStreamHook;
   1796    }
   1797  }
   1798 
   1799  // Start the second thread if needed.
   1800  if (num_crunch_configs_side != 0) {
   1801    if (!worker_interface->Reset(&worker_side)) {
   1802      WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1803      goto Error;
   1804    }
   1805 #if !defined(WEBP_DISABLE_STATS)
   1806    // This line is here and not in the param initialization above to remove a
   1807    // Clang static analyzer warning.
   1808    if (picture->stats != NULL) {
   1809      memcpy(&stats_side, picture->stats, sizeof(stats_side));
   1810    }
   1811 #endif
   1812    worker_interface->Launch(&worker_side);
   1813  }
   1814  // Execute the main thread.
   1815  worker_interface->Execute(&worker_main);
   1816  ok_main = worker_interface->Sync(&worker_main);
   1817  worker_interface->End(&worker_main);
   1818  if (num_crunch_configs_side != 0) {
   1819    // Wait for the second thread.
   1820    const int ok_side = worker_interface->Sync(&worker_side);
   1821    worker_interface->End(&worker_side);
   1822    if (!ok_main || !ok_side) {
   1823      if (picture->error_code == VP8_ENC_OK) {
   1824        assert(picture_side.error_code != VP8_ENC_OK);
   1825        WebPEncodingSetError(picture, picture_side.error_code);
   1826      }
   1827      goto Error;
   1828    }
   1829    if (VP8LBitWriterNumBytes(&bw_side) < VP8LBitWriterNumBytes(bw_main)) {
   1830      VP8LBitWriterSwap(bw_main, &bw_side);
   1831 #if !defined(WEBP_DISABLE_STATS)
   1832      if (picture->stats != NULL) {
   1833        memcpy(picture->stats, &stats_side, sizeof(*picture->stats));
   1834      }
   1835 #endif
   1836    }
   1837  }
   1838 
   1839 Error:
   1840  VP8LBitWriterWipeOut(&bw_side);
   1841  VP8LEncoderDelete(enc_main);
   1842  VP8LEncoderDelete(enc_side);
   1843  return (picture->error_code == VP8_ENC_OK);
   1844 }
   1845 
   1846 #undef CRUNCH_CONFIGS_MAX
   1847 #undef CRUNCH_SUBCONFIGS_MAX
   1848 
   1849 int VP8LEncodeImage(const WebPConfig* const config,
   1850                    const WebPPicture* const picture) {
   1851  int width, height;
   1852  int has_alpha;
   1853  size_t coded_size;
   1854  int percent = 0;
   1855  int initial_size;
   1856  VP8LBitWriter bw;
   1857 
   1858  if (picture == NULL) return 0;
   1859 
   1860  if (config == NULL || picture->argb == NULL) {
   1861    return WebPEncodingSetError(picture, VP8_ENC_ERROR_NULL_PARAMETER);
   1862  }
   1863 
   1864  width = picture->width;
   1865  height = picture->height;
   1866  // Initialize BitWriter with size corresponding to 16 bpp to photo images and
   1867  // 8 bpp for graphical images.
   1868  initial_size = (config->image_hint == WEBP_HINT_GRAPH) ?
   1869      width * height : width * height * 2;
   1870  if (!VP8LBitWriterInit(&bw, initial_size)) {
   1871    WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1872    goto Error;
   1873  }
   1874 
   1875  if (!WebPReportProgress(picture, 1, &percent)) {
   1876 UserAbort:
   1877    WebPEncodingSetError(picture, VP8_ENC_ERROR_USER_ABORT);
   1878    goto Error;
   1879  }
   1880  // Reset stats (for pure lossless coding)
   1881  if (picture->stats != NULL) {
   1882    WebPAuxStats* const stats = picture->stats;
   1883    memset(stats, 0, sizeof(*stats));
   1884    stats->PSNR[0] = 99.f;
   1885    stats->PSNR[1] = 99.f;
   1886    stats->PSNR[2] = 99.f;
   1887    stats->PSNR[3] = 99.f;
   1888    stats->PSNR[4] = 99.f;
   1889  }
   1890 
   1891  // Write image size.
   1892  if (!WriteImageSize(picture, &bw)) {
   1893    WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1894    goto Error;
   1895  }
   1896 
   1897  has_alpha = WebPPictureHasTransparency(picture);
   1898  // Write the non-trivial Alpha flag and lossless version.
   1899  if (!WriteRealAlphaAndVersion(&bw, has_alpha)) {
   1900    WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1901    goto Error;
   1902  }
   1903 
   1904  if (!WebPReportProgress(picture, 2, &percent)) goto UserAbort;
   1905 
   1906  // Encode main image stream.
   1907  if (!VP8LEncodeStream(config, picture, &bw)) goto Error;
   1908 
   1909  if (!WebPReportProgress(picture, 99, &percent)) goto UserAbort;
   1910 
   1911  // Finish the RIFF chunk.
   1912  if (!WriteImage(picture, &bw, &coded_size)) goto Error;
   1913 
   1914  if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort;
   1915 
   1916 #if !defined(WEBP_DISABLE_STATS)
   1917  // Save size.
   1918  if (picture->stats != NULL) {
   1919    picture->stats->coded_size += (int)coded_size;
   1920    picture->stats->lossless_size = (int)coded_size;
   1921  }
   1922 #endif
   1923 
   1924  if (picture->extra_info != NULL) {
   1925    const int mb_w = (width + 15) >> 4;
   1926    const int mb_h = (height + 15) >> 4;
   1927    memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info));
   1928  }
   1929 
   1930 Error:
   1931  if (bw.error) {
   1932    WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
   1933  }
   1934  VP8LBitWriterWipeOut(&bw);
   1935  return (picture->error_code == VP8_ENC_OK);
   1936 }
   1937 
   1938 //------------------------------------------------------------------------------