diff options
Diffstat (limited to 'src/3rdparty/libwebp/src/enc/vp8l.c')
| -rw-r--r-- | src/3rdparty/libwebp/src/enc/vp8l.c | 986 |
1 files changed, 669 insertions, 317 deletions
diff --git a/src/3rdparty/libwebp/src/enc/vp8l.c b/src/3rdparty/libwebp/src/enc/vp8l.c index c2bb13d..db94e78 100644 --- a/src/3rdparty/libwebp/src/enc/vp8l.c +++ b/src/3rdparty/libwebp/src/enc/vp8l.c @@ -13,10 +13,10 @@ // #include <assert.h> -#include <stdio.h> #include <stdlib.h> #include "./backward_references.h" +#include "./histogram.h" #include "./vp8enci.h" #include "./vp8li.h" #include "../dsp/lossless.h" @@ -25,23 +25,105 @@ #include "../utils/utils.h" #include "../webp/format_constants.h" +#include "./delta_palettization.h" + #define PALETTE_KEY_RIGHT_SHIFT 22 // Key for 1K buffer. -#define MAX_HUFF_IMAGE_SIZE (16 * 1024 * 1024) -#define MAX_COLORS_FOR_GRAPH 64 +// Maximum number of histogram images (sub-blocks). +#define MAX_HUFF_IMAGE_SIZE 2600 -// ----------------------------------------------------------------------------- -// Palette +// Palette reordering for smaller sum of deltas (and for smaller storage). -static int CompareColors(const void* p1, const void* p2) { - const uint32_t a = *(const uint32_t*)p1; - const uint32_t b = *(const uint32_t*)p2; +static int PaletteCompareColorsForQsort(const void* p1, const void* p2) { + const uint32_t a = WebPMemToUint32(p1); + const uint32_t b = WebPMemToUint32(p2); assert(a != b); return (a < b) ? -1 : 1; } +static WEBP_INLINE uint32_t PaletteComponentDistance(uint32_t v) { + return (v <= 128) ? v : (256 - v); +} + +// Computes a value that is related to the entropy created by the +// palette entry diff. +// +// Note that the last & 0xff is a no-operation in the next statement, but +// removed by most compilers and is here only for regularity of the code. +static WEBP_INLINE uint32_t PaletteColorDistance(uint32_t col1, uint32_t col2) { + const uint32_t diff = VP8LSubPixels(col1, col2); + const int kMoreWeightForRGBThanForAlpha = 9; + uint32_t score; + score = PaletteComponentDistance((diff >> 0) & 0xff); + score += PaletteComponentDistance((diff >> 8) & 0xff); + score += PaletteComponentDistance((diff >> 16) & 0xff); + score *= kMoreWeightForRGBThanForAlpha; + score += PaletteComponentDistance((diff >> 24) & 0xff); + return score; +} + +static WEBP_INLINE void SwapColor(uint32_t* const col1, uint32_t* const col2) { + const uint32_t tmp = *col1; + *col1 = *col2; + *col2 = tmp; +} + +static void GreedyMinimizeDeltas(uint32_t palette[], int num_colors) { + // Find greedily always the closest color of the predicted color to minimize + // deltas in the palette. This reduces storage needs since the + // palette is stored with delta encoding. + uint32_t predict = 0x00000000; + int i, k; + for (i = 0; i < num_colors; ++i) { + int best_ix = i; + uint32_t best_score = ~0U; + for (k = i; k < num_colors; ++k) { + const uint32_t cur_score = PaletteColorDistance(palette[k], predict); + if (best_score > cur_score) { + best_score = cur_score; + best_ix = k; + } + } + SwapColor(&palette[best_ix], &palette[i]); + predict = palette[i]; + } +} + +// The palette has been sorted by alpha. This function checks if the other +// components of the palette have a monotonic development with regards to +// position in the palette. If all have monotonic development, there is +// no benefit to re-organize them greedily. A monotonic development +// would be spotted in green-only situations (like lossy alpha) or gray-scale +// images. +static int PaletteHasNonMonotonousDeltas(uint32_t palette[], int num_colors) { + uint32_t predict = 0x000000; + int i; + uint8_t sign_found = 0x00; + for (i = 0; i < num_colors; ++i) { + const uint32_t diff = VP8LSubPixels(palette[i], predict); + const uint8_t rd = (diff >> 16) & 0xff; + const uint8_t gd = (diff >> 8) & 0xff; + const uint8_t bd = (diff >> 0) & 0xff; + if (rd != 0x00) { + sign_found |= (rd < 0x80) ? 1 : 2; + } + if (gd != 0x00) { + sign_found |= (gd < 0x80) ? 8 : 16; + } + if (bd != 0x00) { + sign_found |= (bd < 0x80) ? 64 : 128; + } + predict = palette[i]; + } + return (sign_found & (sign_found << 1)) != 0; // two consequent signs. +} + +// ----------------------------------------------------------------------------- +// Palette + // If number of colors in the image is less than or equal to MAX_PALETTE_SIZE, // creates a palette and returns true, else returns false. static int AnalyzeAndCreatePalette(const WebPPicture* const pic, + int low_effort, uint32_t palette[MAX_PALETTE_SIZE], int* const palette_size) { int i, x, y, key; @@ -92,84 +174,240 @@ static int AnalyzeAndCreatePalette(const WebPPicture* const pic, ++num_colors; } } - - qsort(palette, num_colors, sizeof(*palette), CompareColors); *palette_size = num_colors; + qsort(palette, num_colors, sizeof(*palette), PaletteCompareColorsForQsort); + if (!low_effort && PaletteHasNonMonotonousDeltas(palette, num_colors)) { + GreedyMinimizeDeltas(palette, num_colors); + } return 1; } -static int AnalyzeEntropy(const uint32_t* argb, - int width, int height, int argb_stride, - double* const nonpredicted_bits, - double* const predicted_bits) { - int x, y; - const uint32_t* last_line = NULL; - uint32_t last_pix = argb[0]; // so we're sure that pix_diff == 0 +// These five modes are evaluated and their respective entropy is computed. +typedef enum { + kDirect = 0, + kSpatial = 1, + kSubGreen = 2, + kSpatialSubGreen = 3, + kPalette = 4, + kNumEntropyIx = 5 +} EntropyIx; + +typedef enum { + kHistoAlpha = 0, + kHistoAlphaPred, + kHistoGreen, + kHistoGreenPred, + kHistoRed, + kHistoRedPred, + kHistoBlue, + kHistoBluePred, + kHistoRedSubGreen, + kHistoRedPredSubGreen, + kHistoBlueSubGreen, + kHistoBluePredSubGreen, + kHistoPalette, + kHistoTotal // Must be last. +} HistoIx; + +static void AddSingleSubGreen(uint32_t p, uint32_t* r, uint32_t* b) { + const uint32_t green = p >> 8; // The upper bits are masked away later. + ++r[((p >> 16) - green) & 0xff]; + ++b[(p - green) & 0xff]; +} - VP8LHistogramSet* const histo_set = VP8LAllocateHistogramSet(2, 0); - if (histo_set == NULL) return 0; +static void AddSingle(uint32_t p, + uint32_t* a, uint32_t* r, uint32_t* g, uint32_t* b) { + ++a[p >> 24]; + ++r[(p >> 16) & 0xff]; + ++g[(p >> 8) & 0xff]; + ++b[(p & 0xff)]; +} - for (y = 0; y < height; ++y) { - for (x = 0; x < width; ++x) { - const uint32_t pix = argb[x]; - const uint32_t pix_diff = VP8LSubPixels(pix, last_pix); - if (pix_diff == 0) continue; - if (last_line != NULL && pix == last_line[x]) { - continue; +static int AnalyzeEntropy(const uint32_t* argb, + int width, int height, int argb_stride, + int use_palette, + EntropyIx* const min_entropy_ix, + int* const red_and_blue_always_zero) { + // Allocate histogram set with cache_bits = 0. + uint32_t* const histo = + (uint32_t*)WebPSafeCalloc(kHistoTotal, sizeof(*histo) * 256); + if (histo != NULL) { + int i, x, y; + const uint32_t* prev_row = argb; + const uint32_t* curr_row = argb + argb_stride; + for (y = 1; y < height; ++y) { + uint32_t prev_pix = curr_row[0]; + for (x = 1; x < width; ++x) { + const uint32_t pix = curr_row[x]; + const uint32_t pix_diff = VP8LSubPixels(pix, prev_pix); + if ((pix_diff == 0) || (pix == prev_row[x])) continue; + prev_pix = pix; + AddSingle(pix, + &histo[kHistoAlpha * 256], + &histo[kHistoRed * 256], + &histo[kHistoGreen * 256], + &histo[kHistoBlue * 256]); + AddSingle(pix_diff, + &histo[kHistoAlphaPred * 256], + &histo[kHistoRedPred * 256], + &histo[kHistoGreenPred * 256], + &histo[kHistoBluePred * 256]); + AddSingleSubGreen(pix, + &histo[kHistoRedSubGreen * 256], + &histo[kHistoBlueSubGreen * 256]); + AddSingleSubGreen(pix_diff, + &histo[kHistoRedPredSubGreen * 256], + &histo[kHistoBluePredSubGreen * 256]); + { + // Approximate the palette by the entropy of the multiplicative hash. + const int hash = ((pix + (pix >> 19)) * 0x39c5fba7) >> 24; + ++histo[kHistoPalette * 256 + (hash & 0xff)]; + } + } + prev_row = curr_row; + curr_row += argb_stride; + } + { + double entropy_comp[kHistoTotal]; + double entropy[kNumEntropyIx]; + EntropyIx k; + EntropyIx last_mode_to_analyze = + use_palette ? kPalette : kSpatialSubGreen; + int j; + // Let's add one zero to the predicted histograms. The zeros are removed + // too efficiently by the pix_diff == 0 comparison, at least one of the + // zeros is likely to exist. + ++histo[kHistoRedPredSubGreen * 256]; + ++histo[kHistoBluePredSubGreen * 256]; + ++histo[kHistoRedPred * 256]; + ++histo[kHistoGreenPred * 256]; + ++histo[kHistoBluePred * 256]; + ++histo[kHistoAlphaPred * 256]; + + for (j = 0; j < kHistoTotal; ++j) { + entropy_comp[j] = VP8LBitsEntropy(&histo[j * 256], 256, NULL); } - last_pix = pix; + entropy[kDirect] = entropy_comp[kHistoAlpha] + + entropy_comp[kHistoRed] + + entropy_comp[kHistoGreen] + + entropy_comp[kHistoBlue]; + entropy[kSpatial] = entropy_comp[kHistoAlphaPred] + + entropy_comp[kHistoRedPred] + + entropy_comp[kHistoGreenPred] + + entropy_comp[kHistoBluePred]; + entropy[kSubGreen] = entropy_comp[kHistoAlpha] + + entropy_comp[kHistoRedSubGreen] + + entropy_comp[kHistoGreen] + + entropy_comp[kHistoBlueSubGreen]; + entropy[kSpatialSubGreen] = entropy_comp[kHistoAlphaPred] + + entropy_comp[kHistoRedPredSubGreen] + + entropy_comp[kHistoGreenPred] + + entropy_comp[kHistoBluePredSubGreen]; + // Palette mode seems more efficient in a breakeven case. Bias with 1.0. + entropy[kPalette] = entropy_comp[kHistoPalette] - 1.0; + + *min_entropy_ix = kDirect; + for (k = kDirect + 1; k <= last_mode_to_analyze; ++k) { + if (entropy[*min_entropy_ix] > entropy[k]) { + *min_entropy_ix = k; + } + } + *red_and_blue_always_zero = 1; + // Let's check if the histogram of the chosen entropy mode has + // non-zero red and blue values. If all are zero, we can later skip + // the cross color optimization. { - const PixOrCopy pix_token = PixOrCopyCreateLiteral(pix); - const PixOrCopy pix_diff_token = PixOrCopyCreateLiteral(pix_diff); - VP8LHistogramAddSinglePixOrCopy(histo_set->histograms[0], &pix_token); - VP8LHistogramAddSinglePixOrCopy(histo_set->histograms[1], - &pix_diff_token); + static const uint8_t kHistoPairs[5][2] = { + { kHistoRed, kHistoBlue }, + { kHistoRedPred, kHistoBluePred }, + { kHistoRedSubGreen, kHistoBlueSubGreen }, + { kHistoRedPredSubGreen, kHistoBluePredSubGreen }, + { kHistoRed, kHistoBlue } + }; + const uint32_t* const red_histo = + &histo[256 * kHistoPairs[*min_entropy_ix][0]]; + const uint32_t* const blue_histo = + &histo[256 * kHistoPairs[*min_entropy_ix][1]]; + for (i = 1; i < 256; ++i) { + if ((red_histo[i] | blue_histo[i]) != 0) { + *red_and_blue_always_zero = 0; + break; + } + } } } - last_line = argb; - argb += argb_stride; + free(histo); + return 1; + } else { + return 0; } - *nonpredicted_bits = VP8LHistogramEstimateBitsBulk(histo_set->histograms[0]); - *predicted_bits = VP8LHistogramEstimateBitsBulk(histo_set->histograms[1]); - VP8LFreeHistogramSet(histo_set); - return 1; } -static int AnalyzeAndInit(VP8LEncoder* const enc, WebPImageHint image_hint) { +static int GetHistoBits(int method, int use_palette, int width, int height) { + // Make tile size a function of encoding method (Range: 0 to 6). + int histo_bits = (use_palette ? 9 : 7) - method; + while (1) { + const int huff_image_size = VP8LSubSampleSize(width, histo_bits) * + VP8LSubSampleSize(height, histo_bits); + if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break; + ++histo_bits; + } + return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS : + (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits; +} + +static int GetTransformBits(int method, int histo_bits) { + const int max_transform_bits = (method < 4) ? 6 : (method > 4) ? 4 : 5; + return (histo_bits > max_transform_bits) ? max_transform_bits : histo_bits; +} + +static int AnalyzeAndInit(VP8LEncoder* const enc) { const WebPPicture* const pic = enc->pic_; const int width = pic->width; const int height = pic->height; const int pix_cnt = width * height; + const WebPConfig* const config = enc->config_; + const int method = config->method; + const int low_effort = (config->method == 0); // we round the block size up, so we're guaranteed to have // at max MAX_REFS_BLOCK_PER_IMAGE blocks used: int refs_block_size = (pix_cnt - 1) / MAX_REFS_BLOCK_PER_IMAGE + 1; assert(pic != NULL && pic->argb != NULL); + enc->use_cross_color_ = 0; + enc->use_predict_ = 0; + enc->use_subtract_green_ = 0; enc->use_palette_ = - AnalyzeAndCreatePalette(pic, enc->palette_, &enc->palette_size_); + AnalyzeAndCreatePalette(pic, low_effort, + enc->palette_, &enc->palette_size_); - if (image_hint == WEBP_HINT_GRAPH) { - if (enc->use_palette_ && enc->palette_size_ < MAX_COLORS_FOR_GRAPH) { - enc->use_palette_ = 0; - } - } + // TODO(jyrki): replace the decision to be based on an actual estimate + // of entropy, or even spatial variance of entropy. + enc->histo_bits_ = GetHistoBits(method, enc->use_palette_, + pic->width, pic->height); + enc->transform_bits_ = GetTransformBits(method, enc->histo_bits_); - if (!enc->use_palette_) { - if (image_hint == WEBP_HINT_PHOTO) { - enc->use_predict_ = 1; - enc->use_cross_color_ = 1; - } else { - double non_pred_entropy, pred_entropy; - if (!AnalyzeEntropy(pic->argb, width, height, pic->argb_stride, - &non_pred_entropy, &pred_entropy)) { - return 0; - } - if (pred_entropy < 0.95 * non_pred_entropy) { - enc->use_predict_ = 1; - enc->use_cross_color_ = 1; - } + if (low_effort) { + // AnalyzeEntropy is somewhat slow. + enc->use_predict_ = !enc->use_palette_; + enc->use_subtract_green_ = !enc->use_palette_; + enc->use_cross_color_ = 0; + } else { + int red_and_blue_always_zero; + EntropyIx min_entropy_ix; + if (!AnalyzeEntropy(pic->argb, width, height, pic->argb_stride, + enc->use_palette_, &min_entropy_ix, + &red_and_blue_always_zero)) { + return 0; } + enc->use_palette_ = (min_entropy_ix == kPalette); + enc->use_subtract_green_ = + (min_entropy_ix == kSubGreen) || (min_entropy_ix == kSpatialSubGreen); + enc->use_predict_ = + (min_entropy_ix == kSpatial) || (min_entropy_ix == kSpatialSubGreen); + enc->use_cross_color_ = red_and_blue_always_zero ? 0 : enc->use_predict_; } + if (!VP8LHashChainInit(&enc->hash_chain_, pix_cnt)) return 0; // palette-friendly input typically uses less literals @@ -271,9 +509,9 @@ static void StoreHuffmanTreeOfHuffmanTreeToBitMask( break; } } - VP8LWriteBits(bw, 4, codes_to_store - 4); + VP8LPutBits(bw, codes_to_store - 4, 4); for (i = 0; i < codes_to_store; ++i) { - VP8LWriteBits(bw, 3, code_length_bitdepth[kStorageOrder[i]]); + VP8LPutBits(bw, code_length_bitdepth[kStorageOrder[i]], 3); } } @@ -301,16 +539,16 @@ static void StoreHuffmanTreeToBitMask( for (i = 0; i < num_tokens; ++i) { const int ix = tokens[i].code; const int extra_bits = tokens[i].extra_bits; - VP8LWriteBits(bw, huffman_code->code_lengths[ix], huffman_code->codes[ix]); + VP8LPutBits(bw, huffman_code->codes[ix], huffman_code->code_lengths[ix]); switch (ix) { case 16: - VP8LWriteBits(bw, 2, extra_bits); + VP8LPutBits(bw, extra_bits, 2); break; case 17: - VP8LWriteBits(bw, 3, extra_bits); + VP8LPutBits(bw, extra_bits, 3); break; case 18: - VP8LWriteBits(bw, 7, extra_bits); + VP8LPutBits(bw, extra_bits, 7); break; } } @@ -330,7 +568,7 @@ static void StoreFullHuffmanCode(VP8LBitWriter* const bw, huffman_code.code_lengths = code_length_bitdepth; huffman_code.codes = code_length_bitdepth_symbols; - VP8LWriteBits(bw, 1, 0); + VP8LPutBits(bw, 0, 1); num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens); { uint32_t histogram[CODE_LENGTH_CODES] = { 0 }; @@ -367,13 +605,13 @@ static void StoreFullHuffmanCode(VP8LBitWriter* const bw, } write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12); length = write_trimmed_length ? trimmed_length : num_tokens; - VP8LWriteBits(bw, 1, write_trimmed_length); + VP8LPutBits(bw, write_trimmed_length, 1); if (write_trimmed_length) { const int nbits = VP8LBitsLog2Ceiling(trimmed_length - 1); const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2; - VP8LWriteBits(bw, 3, nbitpairs - 1); + VP8LPutBits(bw, nbitpairs - 1, 3); assert(trimmed_length >= 2); - VP8LWriteBits(bw, nbitpairs * 2, trimmed_length - 2); + VP8LPutBits(bw, trimmed_length - 2, nbitpairs * 2); } StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code); } @@ -400,31 +638,42 @@ static void StoreHuffmanCode(VP8LBitWriter* const bw, if (count == 0) { // emit minimal tree for empty cases // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0 - VP8LWriteBits(bw, 4, 0x01); + VP8LPutBits(bw, 0x01, 4); } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) { - VP8LWriteBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols. - VP8LWriteBits(bw, 1, count - 1); + VP8LPutBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols. + VP8LPutBits(bw, count - 1, 1); if (symbols[0] <= 1) { - VP8LWriteBits(bw, 1, 0); // Code bit for small (1 bit) symbol value. - VP8LWriteBits(bw, 1, symbols[0]); + VP8LPutBits(bw, 0, 1); // Code bit for small (1 bit) symbol value. + VP8LPutBits(bw, symbols[0], 1); } else { - VP8LWriteBits(bw, 1, 1); - VP8LWriteBits(bw, 8, symbols[0]); + VP8LPutBits(bw, 1, 1); + VP8LPutBits(bw, symbols[0], 8); } if (count == 2) { - VP8LWriteBits(bw, 8, symbols[1]); + VP8LPutBits(bw, symbols[1], 8); } } else { StoreFullHuffmanCode(bw, huff_tree, tokens, huffman_code); } } -static void WriteHuffmanCode(VP8LBitWriter* const bw, +static WEBP_INLINE void WriteHuffmanCode(VP8LBitWriter* const bw, const HuffmanTreeCode* const code, int code_index) { const int depth = code->code_lengths[code_index]; const int symbol = code->codes[code_index]; - VP8LWriteBits(bw, depth, symbol); + VP8LPutBits(bw, symbol, depth); +} + +static WEBP_INLINE void WriteHuffmanCodeWithExtraBits( + VP8LBitWriter* const bw, + const HuffmanTreeCode* const code, + int code_index, + int bits, + int n_bits) { + const int depth = code->code_lengths[code_index]; + const int symbol = code->codes[code_index]; + VP8LPutBits(bw, (bits << depth) | symbol, depth + n_bits); } static WebPEncodingError StoreImageToBitMask( @@ -432,40 +681,51 @@ static WebPEncodingError StoreImageToBitMask( VP8LBackwardRefs* const refs, const uint16_t* histogram_symbols, const HuffmanTreeCode* const huffman_codes) { + const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1; + const int tile_mask = (histo_bits == 0) ? 0 : -(1 << histo_bits); // x and y trace the position in the image. int x = 0; int y = 0; - const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1; + int tile_x = x & tile_mask; + int tile_y = y & tile_mask; + int histogram_ix = histogram_symbols[0]; + const HuffmanTreeCode* codes = huffman_codes + 5 * histogram_ix; VP8LRefsCursor c = VP8LRefsCursorInit(refs); while (VP8LRefsCursorOk(&c)) { const PixOrCopy* const v = c.cur_pos; - const int histogram_ix = histogram_symbols[histo_bits ? - (y >> histo_bits) * histo_xsize + - (x >> histo_bits) : 0]; - const HuffmanTreeCode* const codes = huffman_codes + 5 * histogram_ix; - if (PixOrCopyIsCacheIdx(v)) { - const int code = PixOrCopyCacheIdx(v); - const int literal_ix = 256 + NUM_LENGTH_CODES + code; - WriteHuffmanCode(bw, codes, literal_ix); - } else if (PixOrCopyIsLiteral(v)) { + if ((tile_x != (x & tile_mask)) || (tile_y != (y & tile_mask))) { + tile_x = x & tile_mask; + tile_y = y & tile_mask; + histogram_ix = histogram_symbols[(y >> histo_bits) * histo_xsize + + (x >> histo_bits)]; + codes = huffman_codes + 5 * histogram_ix; + } + if (PixOrCopyIsLiteral(v)) { static const int order[] = { 1, 2, 0, 3 }; int k; for (k = 0; k < 4; ++k) { const int code = PixOrCopyLiteral(v, order[k]); WriteHuffmanCode(bw, codes + k, code); } + } else if (PixOrCopyIsCacheIdx(v)) { + const int code = PixOrCopyCacheIdx(v); + const int literal_ix = 256 + NUM_LENGTH_CODES + code; + WriteHuffmanCode(bw, codes, literal_ix); } else { int bits, n_bits; - int code, distance; + int code; + const int distance = PixOrCopyDistance(v); VP8LPrefixEncode(v->len, &code, &n_bits, &bits); - WriteHuffmanCode(bw, codes, 256 + code); - VP8LWriteBits(bw, n_bits, bits); + WriteHuffmanCodeWithExtraBits(bw, codes, 256 + code, bits, n_bits); - distance = PixOrCopyDistance(v); + // Don't write the distance with the extra bits code since + // the distance can be up to 18 bits of extra bits, and the prefix + // 15 bits, totaling to 33, and our PutBits only supports up to 32 bits. + // TODO(jyrki): optimize this further. VP8LPrefixEncode(distance, &code, &n_bits, &bits); WriteHuffmanCode(bw, codes + 4, code); - VP8LWriteBits(bw, n_bits, bits); + VP8LPutBits(bw, bits, n_bits); } x += PixOrCopyLength(v); while (x >= width) { @@ -491,21 +751,28 @@ static WebPEncodingError EncodeImageNoHuffman(VP8LBitWriter* const bw, HuffmanTreeToken* tokens = NULL; HuffmanTreeCode huffman_codes[5] = { { 0, NULL, NULL } }; const uint16_t histogram_symbols[1] = { 0 }; // only one tree, one symbol - VP8LHistogramSet* const histogram_image = VP8LAllocateHistogramSet(1, 0); + int cache_bits = 0; + VP8LHistogramSet* histogram_image = NULL; HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc( 3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree)); - if (histogram_image == NULL || huff_tree == NULL) { + if (huff_tree == NULL) { err = VP8_ENC_ERROR_OUT_OF_MEMORY; goto Error; } // Calculate backward references from ARGB image. - refs = VP8LGetBackwardReferences(width, height, argb, quality, 0, 1, + refs = VP8LGetBackwardReferences(width, height, argb, quality, 0, &cache_bits, hash_chain, refs_array); if (refs == NULL) { err = VP8_ENC_ERROR_OUT_OF_MEMORY; goto Error; } + histogram_image = VP8LAllocateHistogramSet(1, cache_bits); + if (histogram_image == NULL) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; + } + // Build histogram image and symbols from backward references. VP8LHistogramStoreRefs(refs, histogram_image->histograms[0]); @@ -517,7 +784,7 @@ static WebPEncodingError EncodeImageNoHuffman(VP8LBitWriter* const bw, } // No color cache, no Huffman image. - VP8LWriteBits(bw, 1, 0); + VP8LPutBits(bw, 0, 1); // Find maximum number of symbols for the huffman tree-set. for (i = 0; i < 5; ++i) { @@ -557,16 +824,17 @@ static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, VP8LHashChain* const hash_chain, VP8LBackwardRefs refs_array[2], int width, int height, int quality, - int cache_bits, - int histogram_bits) { + int low_effort, int* cache_bits, + int histogram_bits, + size_t init_byte_position, + int* const hdr_size, + int* const data_size) { WebPEncodingError err = VP8_ENC_OK; - const int use_2d_locality = 1; - const int use_color_cache = (cache_bits > 0); const uint32_t histogram_image_xysize = VP8LSubSampleSize(width, histogram_bits) * VP8LSubSampleSize(height, histogram_bits); - VP8LHistogramSet* histogram_image = - VP8LAllocateHistogramSet(histogram_image_xysize, cache_bits); + VP8LHistogramSet* histogram_image = NULL; + VP8LHistogramSet* tmp_histos = NULL; int histogram_image_size = 0; size_t bit_array_size = 0; HuffmanTree* huff_tree = NULL; @@ -579,28 +847,39 @@ static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, sizeof(*histogram_symbols)); assert(histogram_bits >= MIN_HUFFMAN_BITS); assert(histogram_bits <= MAX_HUFFMAN_BITS); + assert(hdr_size != NULL); + assert(data_size != NULL); VP8LBackwardRefsInit(&refs, refs_array[0].block_size_); - if (histogram_image == NULL || histogram_symbols == NULL) { - VP8LFreeHistogramSet(histogram_image); - WebPSafeFree(histogram_symbols); - return 0; + if (histogram_symbols == NULL) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; } + *cache_bits = MAX_COLOR_CACHE_BITS; // 'best_refs' is the reference to the best backward refs and points to one // of refs_array[0] or refs_array[1]. // Calculate backward references from ARGB image. best_refs = VP8LGetBackwardReferences(width, height, argb, quality, - cache_bits, use_2d_locality, - hash_chain, refs_array); + low_effort, cache_bits, hash_chain, + refs_array); if (best_refs == NULL || !VP8LBackwardRefsCopy(best_refs, &refs)) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; goto Error; } + histogram_image = + VP8LAllocateHistogramSet(histogram_image_xysize, *cache_bits); + tmp_histos = VP8LAllocateHistogramSet(2, *cache_bits); + if (histogram_image == NULL || tmp_histos == NULL) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; + } + // Build histogram image and symbols from backward references. - if (!VP8LGetHistoImageSymbols(width, height, &refs, - quality, histogram_bits, cache_bits, - histogram_image, - histogram_symbols)) { + if (!VP8LGetHistoImageSymbols(width, height, &refs, quality, low_effort, + histogram_bits, *cache_bits, histogram_image, + tmp_histos, histogram_symbols)) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; goto Error; } // Create Huffman bit lengths and codes for each histogram image. @@ -608,41 +887,53 @@ static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, bit_array_size = 5 * histogram_image_size; huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size, sizeof(*huffman_codes)); + // Note: some histogram_image entries may point to tmp_histos[], so the latter + // need to outlive the following call to GetHuffBitLengthsAndCodes(). if (huffman_codes == NULL || !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; goto Error; } // Free combined histograms. VP8LFreeHistogramSet(histogram_image); histogram_image = NULL; + // Free scratch histograms. + VP8LFreeHistogramSet(tmp_histos); + tmp_histos = NULL; + // Color Cache parameters. - VP8LWriteBits(bw, 1, use_color_cache); - if (use_color_cache) { - VP8LWriteBits(bw, 4, cache_bits); + if (*cache_bits > 0) { + VP8LPutBits(bw, 1, 1); + VP8LPutBits(bw, *cache_bits, 4); + } else { + VP8LPutBits(bw, 0, 1); } // Huffman image + meta huffman. { const int write_histogram_image = (histogram_image_size > 1); - VP8LWriteBits(bw, 1, write_histogram_image); + VP8LPutBits(bw, write_histogram_image, 1); if (write_histogram_image) { uint32_t* const histogram_argb = (uint32_t*)WebPSafeMalloc(histogram_image_xysize, sizeof(*histogram_argb)); int max_index = 0; uint32_t i; - if (histogram_argb == NULL) goto Error; + if (histogram_argb == NULL) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; + } for (i = 0; i < histogram_image_xysize; ++i) { const int symbol_index = histogram_symbols[i] & 0xffff; - histogram_argb[i] = 0xff000000 | (symbol_index << 8); + histogram_argb[i] = (symbol_index << 8); if (symbol_index >= max_index) { max_index = symbol_index + 1; } } histogram_image_size = max_index; - VP8LWriteBits(bw, 3, histogram_bits - 2); + VP8LPutBits(bw, histogram_bits - 2, 3); err = EncodeImageNoHuffman(bw, histogram_argb, hash_chain, refs_array, VP8LSubSampleSize(width, histogram_bits), VP8LSubSampleSize(height, histogram_bits), @@ -658,7 +949,10 @@ static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, int max_tokens = 0; huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree)); - if (huff_tree == NULL) goto Error; + if (huff_tree == NULL) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; + } // Find maximum number of symbols for the huffman tree-set. for (i = 0; i < 5 * histogram_image_size; ++i) { HuffmanTreeCode* const codes = &huffman_codes[i]; @@ -668,7 +962,10 @@ static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, } tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens)); - if (tokens == NULL) goto Error; + if (tokens == NULL) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; + } for (i = 0; i < 5 * histogram_image_size; ++i) { HuffmanTreeCode* const codes = &huffman_codes[i]; StoreHuffmanCode(bw, huff_tree, tokens, codes); @@ -676,14 +973,18 @@ static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, } } + *hdr_size = (int)(VP8LBitWriterNumBytes(bw) - init_byte_position); // Store actual literals. err = StoreImageToBitMask(bw, width, histogram_bits, &refs, histogram_symbols, huffman_codes); + *data_size = + (int)(VP8LBitWriterNumBytes(bw) - init_byte_position - *hdr_size); Error: WebPSafeFree(tokens); WebPSafeFree(huff_tree); VP8LFreeHistogramSet(histogram_image); + VP8LFreeHistogramSet(tmp_histos); VP8LBackwardRefsClear(&refs); if (huffman_codes != NULL) { WebPSafeFree(huffman_codes->codes); @@ -696,59 +997,28 @@ static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw, // ----------------------------------------------------------------------------- // Transforms -// Check if it would be a good idea to subtract green from red and blue. We -// only impact entropy in red/blue components, don't bother to look at others. -static WebPEncodingError EvalAndApplySubtractGreen(VP8LEncoder* const enc, - int width, int height, - VP8LBitWriter* const bw) { - if (!enc->use_palette_) { - int i; - const uint32_t* const argb = enc->argb_; - double bit_cost_before, bit_cost_after; - // Allocate histogram with cache_bits = 1. - VP8LHistogram* const histo = VP8LAllocateHistogram(1); - if (histo == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; - for (i = 0; i < width * height; ++i) { - const uint32_t c = argb[i]; - ++histo->red_[(c >> 16) & 0xff]; - ++histo->blue_[(c >> 0) & 0xff]; - } - bit_cost_before = VP8LHistogramEstimateBits(histo); - - VP8LHistogramInit(histo, 1); - for (i = 0; i < width * height; ++i) { - const uint32_t c = argb[i]; - const int green = (c >> 8) & 0xff; - ++histo->red_[((c >> 16) - green) & 0xff]; - ++histo->blue_[((c >> 0) - green) & 0xff]; - } - bit_cost_after = VP8LHistogramEstimateBits(histo); - VP8LFreeHistogram(histo); - - // Check if subtracting green yields low entropy. - enc->use_subtract_green_ = (bit_cost_after < bit_cost_before); - if (enc->use_subtract_green_) { - VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); - VP8LWriteBits(bw, 2, SUBTRACT_GREEN); - VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height); - } - } - return VP8_ENC_OK; +static void ApplySubtractGreen(VP8LEncoder* const enc, int width, int height, + VP8LBitWriter* const bw) { + VP8LPutBits(bw, TRANSFORM_PRESENT, 1); + VP8LPutBits(bw, SUBTRACT_GREEN, 2); + VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height); } static WebPEncodingError ApplyPredictFilter(const VP8LEncoder* const enc, - int width, int height, int quality, + int width, int height, + int quality, int low_effort, VP8LBitWriter* const bw) { const int pred_bits = enc->transform_bits_; const int transform_width = VP8LSubSampleSize(width, pred_bits); const int transform_height = VP8LSubSampleSize(height, pred_bits); - VP8LResidualImage(width, height, pred_bits, enc->argb_, enc->argb_scratch_, - enc->transform_data_); - VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); - VP8LWriteBits(bw, 2, PREDICTOR_TRANSFORM); + VP8LResidualImage(width, height, pred_bits, low_effort, enc->argb_, + enc->argb_scratch_, enc->transform_data_, + enc->config_->exact); + VP8LPutBits(bw, TRANSFORM_PRESENT, 1); + VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2); assert(pred_bits >= 2); - VP8LWriteBits(bw, 3, pred_bits - 2); + VP8LPutBits(bw, pred_bits - 2, 3); return EncodeImageNoHuffman(bw, enc->transform_data_, (VP8LHashChain*)&enc->hash_chain_, (VP8LBackwardRefs*)enc->refs_, // cast const away @@ -766,10 +1036,10 @@ static WebPEncodingError ApplyCrossColorFilter(const VP8LEncoder* const enc, VP8LColorSpaceTransform(width, height, ccolor_transform_bits, quality, enc->argb_, enc->transform_data_); - VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); - VP8LWriteBits(bw, 2, CROSS_COLOR_TRANSFORM); + VP8LPutBits(bw, TRANSFORM_PRESENT, 1); + VP8LPutBits(bw, CROSS_COLOR_TRANSFORM, 2); assert(ccolor_transform_bits >= 2); - VP8LWriteBits(bw, 3, ccolor_transform_bits - 2); + VP8LPutBits(bw, ccolor_transform_bits - 2, 3); return EncodeImageNoHuffman(bw, enc->transform_data_, (VP8LHashChain*)&enc->hash_chain_, (VP8LBackwardRefs*)enc->refs_, // cast const away @@ -799,14 +1069,14 @@ static int WriteImageSize(const WebPPicture* const pic, const int height = pic->height - 1; assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION); - VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, width); - VP8LWriteBits(bw, VP8L_IMAGE_SIZE_BITS, height); + VP8LPutBits(bw, width, VP8L_IMAGE_SIZE_BITS); + VP8LPutBits(bw, height, VP8L_IMAGE_SIZE_BITS); return !bw->error_; } static int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) { - VP8LWriteBits(bw, 1, has_alpha); - VP8LWriteBits(bw, VP8L_VERSION_BITS, VP8L_VERSION); + VP8LPutBits(bw, has_alpha, 1); + VP8LPutBits(bw, VP8L_VERSION, VP8L_VERSION_BITS); return !bw->error_; } @@ -846,39 +1116,107 @@ static WebPEncodingError WriteImage(const WebPPicture* const pic, // Allocates the memory for argb (W x H) buffer, 2 rows of context for // prediction and transform data. +// Flags influencing the memory allocated: +// enc->transform_bits_ +// enc->use_predict_, enc->use_cross_color_ static WebPEncodingError AllocateTransformBuffer(VP8LEncoder* const enc, int width, int height) { WebPEncodingError err = VP8_ENC_OK; - const int tile_size = 1 << enc->transform_bits_; - const uint64_t image_size = width * height; - const uint64_t argb_scratch_size = tile_size * width + width; - const int transform_data_size = - VP8LSubSampleSize(width, enc->transform_bits_) * - VP8LSubSampleSize(height, enc->transform_bits_); - const uint64_t total_size = - image_size + argb_scratch_size + (uint64_t)transform_data_size; - uint32_t* mem = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*mem)); - if (mem == NULL) { - err = VP8_ENC_ERROR_OUT_OF_MEMORY; - goto Error; + if (enc->argb_ == NULL) { + const int tile_size = 1 << enc->transform_bits_; + const uint64_t image_size = width * height; + // Ensure enough size for tiles, as well as for two scanlines and two + // extra pixels for CopyImageWithPrediction. + const uint64_t argb_scratch_size = + enc->use_predict_ ? tile_size * width + width + 2 : 0; + const int transform_data_size = + (enc->use_predict_ || enc->use_cross_color_) + ? VP8LSubSampleSize(width, enc->transform_bits_) * + VP8LSubSampleSize(height, enc->transform_bits_) + : 0; + const uint64_t total_size = + image_size + WEBP_ALIGN_CST + + argb_scratch_size + WEBP_ALIGN_CST + + (uint64_t)transform_data_size; + uint32_t* mem = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*mem)); + if (mem == NULL) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; + } + enc->argb_ = mem; + mem = (uint32_t*)WEBP_ALIGN(mem + image_size); + enc->argb_scratch_ = mem; + mem = (uint32_t*)WEBP_ALIGN(mem + argb_scratch_size); + enc->transform_data_ = mem; + enc->current_width_ = width; } - enc->argb_ = mem; - mem += image_size; - enc->argb_scratch_ = mem; - mem += argb_scratch_size; - enc->transform_data_ = mem; - enc->current_width_ = width; - Error: return err; } -static void ApplyPalette(uint32_t* src, uint32_t* dst, - uint32_t src_stride, uint32_t dst_stride, - const uint32_t* palette, int palette_size, - int width, int height, int xbits, uint8_t* row) { +static void ClearTransformBuffer(VP8LEncoder* const enc) { + WebPSafeFree(enc->argb_); + enc->argb_ = NULL; +} + +static WebPEncodingError MakeInputImageCopy(VP8LEncoder* const enc) { + WebPEncodingError err = VP8_ENC_OK; + const WebPPicture* const picture = enc->pic_; + const int width = picture->width; + const int height = picture->height; + int y; + err = AllocateTransformBuffer(enc, width, height); + if (err != VP8_ENC_OK) return err; + for (y = 0; y < height; ++y) { + memcpy(enc->argb_ + y * width, + picture->argb + y * picture->argb_stride, + width * sizeof(*enc->argb_)); + } + assert(enc->current_width_ == width); + return VP8_ENC_OK; +} + +// ----------------------------------------------------------------------------- + +static void MapToPalette(const uint32_t palette[], int num_colors, + uint32_t* const last_pix, int* const last_idx, + const uint32_t* src, uint8_t* dst, int width) { + int x; + int prev_idx = *last_idx; + uint32_t prev_pix = *last_pix; + for (x = 0; x < width; ++x) { + const uint32_t pix = src[x]; + if (pix != prev_pix) { + int i; + for (i = 0; i < num_colors; ++i) { + if (pix == palette[i]) { + prev_idx = i; + prev_pix = pix; + break; + } + } + } + dst[x] = prev_idx; + } + *last_idx = prev_idx; + *last_pix = prev_pix; +} + +// Remap argb values in src[] to packed palettes entries in dst[] +// using 'row' as a temporary buffer of size 'width'. +// We assume that all src[] values have a corresponding entry in the palette. +// Note: src[] can be the same as dst[] +static WebPEncodingError ApplyPalette(const uint32_t* src, uint32_t src_stride, + uint32_t* dst, uint32_t dst_stride, + const uint32_t* palette, int palette_size, + int width, int height, int xbits) { + // TODO(skal): this tmp buffer is not needed if VP8LBundleColorMap() can be + // made to work in-place. + uint8_t* const tmp_row = (uint8_t*)WebPSafeMalloc(width, sizeof(*tmp_row)); int i, x, y; int use_LUT = 1; + + if (tmp_row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; for (i = 0; i < palette_size; ++i) { if ((palette[i] & 0xffff00ffu) != 0) { use_LUT = 0; @@ -895,9 +1233,9 @@ static void ApplyPalette(uint32_t* src, uint32_t* dst, for (y = 0; y < height; ++y) { for (x = 0; x < width; ++x) { const int color = (src[x] >> 8) & 0xff; - row[x] = inv_palette[color]; + tmp_row[x] = inv_palette[color]; } - VP8LBundleColorMap(row, width, xbits, dst); + VP8LBundleColorMap(tmp_row, width, xbits, dst); src += src_stride; dst += dst_stride; } @@ -906,41 +1244,28 @@ static void ApplyPalette(uint32_t* src, uint32_t* dst, uint32_t last_pix = palette[0]; int last_idx = 0; for (y = 0; y < height; ++y) { - for (x = 0; x < width; ++x) { - const uint32_t pix = src[x]; - if (pix != last_pix) { - for (i = 0; i < palette_size; ++i) { - if (pix == palette[i]) { - last_idx = i; - last_pix = pix; - break; - } - } - } - row[x] = last_idx; - } - VP8LBundleColorMap(row, width, xbits, dst); + MapToPalette(palette, palette_size, &last_pix, &last_idx, + src, tmp_row, width); + VP8LBundleColorMap(tmp_row, width, xbits, dst); src += src_stride; dst += dst_stride; } } + WebPSafeFree(tmp_row); + return VP8_ENC_OK; } // Note: Expects "enc->palette_" to be set properly. -// Also, "enc->palette_" will be modified after this call and should not be used -// later. -static WebPEncodingError EncodePalette(VP8LBitWriter* const bw, - VP8LEncoder* const enc, int quality) { +static WebPEncodingError MapImageFromPalette(VP8LEncoder* const enc, + int in_place) { WebPEncodingError err = VP8_ENC_OK; - int i; const WebPPicture* const pic = enc->pic_; - uint32_t* src = pic->argb; - uint32_t* dst; const int width = pic->width; const int height = pic->height; - uint32_t* const palette = enc->palette_; + const uint32_t* const palette = enc->palette_; + const uint32_t* src = in_place ? enc->argb_ : pic->argb; + const int src_stride = in_place ? enc->current_width_ : pic->argb_stride; const int palette_size = enc->palette_size_; - uint8_t* row = NULL; int xbits; // Replace each input pixel by corresponding palette index. @@ -952,67 +1277,74 @@ static WebPEncodingError EncodePalette(VP8LBitWriter* const bw, } err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height); - if (err != VP8_ENC_OK) goto Error; - dst = enc->argb_; - - row = (uint8_t*)WebPSafeMalloc(width, sizeof(*row)); - if (row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; + if (err != VP8_ENC_OK) return err; - ApplyPalette(src, dst, pic->argb_stride, enc->current_width_, - palette, palette_size, width, height, xbits, row); + err = ApplyPalette(src, src_stride, + enc->argb_, enc->current_width_, + palette, palette_size, width, height, xbits); + return err; +} - // Save palette to bitstream. - VP8LWriteBits(bw, 1, TRANSFORM_PRESENT); - VP8LWriteBits(bw, 2, COLOR_INDEXING_TRANSFORM); - assert(palette_size >= 1); - VP8LWriteBits(bw, 8, palette_size - 1); +// Save palette_[] to bitstream. +static WebPEncodingError EncodePalette(VP8LBitWriter* const bw, + VP8LEncoder* const enc) { + int i; + uint32_t tmp_palette[MAX_PALETTE_SIZE]; + const int palette_size = enc->palette_size_; + const uint32_t* const palette = enc->palette_; + VP8LPutBits(bw, TRANSFORM_PRESENT, 1); + VP8LPutBits(bw, COLOR_INDEXING_TRANSFORM, 2); + assert(palette_size >= 1 && palette_size <= MAX_PALETTE_SIZE); + VP8LPutBits(bw, palette_size - 1, 8); for (i = palette_size - 1; i >= 1; --i) { - palette[i] = VP8LSubPixels(palette[i], palette[i - 1]); + tmp_palette[i] = VP8LSubPixels(palette[i], palette[i - 1]); } - err = EncodeImageNoHuffman(bw, palette, &enc->hash_chain_, enc->refs_, - palette_size, 1, quality); - - Error: - WebPSafeFree(row); - return err; + tmp_palette[0] = palette[0]; + return EncodeImageNoHuffman(bw, tmp_palette, &enc->hash_chain_, enc->refs_, + palette_size, 1, 20 /* quality */); } -// ----------------------------------------------------------------------------- +#ifdef WEBP_EXPERIMENTAL_FEATURES -static int GetHistoBits(int method, int use_palette, int width, int height) { - const int hist_size = VP8LGetHistogramSize(MAX_COLOR_CACHE_BITS); - // Make tile size a function of encoding method (Range: 0 to 6). - int histo_bits = (use_palette ? 9 : 7) - method; - while (1) { - const int huff_image_size = VP8LSubSampleSize(width, histo_bits) * - VP8LSubSampleSize(height, histo_bits); - if ((uint64_t)huff_image_size * hist_size <= MAX_HUFF_IMAGE_SIZE) break; - ++histo_bits; - } - return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS : - (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits; -} +static WebPEncodingError EncodeDeltaPalettePredictorImage( + VP8LBitWriter* const bw, VP8LEncoder* const enc, int quality) { + const WebPPicture* const pic = enc->pic_; + const int width = pic->width; + const int height = pic->height; -static int GetTransformBits(int method, int histo_bits) { - const int max_transform_bits = (method < 4) ? 6 : (method > 4) ? 4 : 5; - return (histo_bits > max_transform_bits) ? max_transform_bits : histo_bits; -} + const int pred_bits = 5; + const int transform_width = VP8LSubSampleSize(width, pred_bits); + const int transform_height = VP8LSubSampleSize(height, pred_bits); + const int pred = 7; // default is Predictor7 (Top/Left Average) + const int tiles_per_row = VP8LSubSampleSize(width, pred_bits); + const int tiles_per_col = VP8LSubSampleSize(height, pred_bits); + uint32_t* predictors; + int tile_x, tile_y; + WebPEncodingError err = VP8_ENC_OK; -static int GetCacheBits(float quality) { - return (quality <= 25.f) ? 0 : 7; -} + predictors = (uint32_t*)WebPSafeMalloc(tiles_per_col * tiles_per_row, + sizeof(*predictors)); + if (predictors == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY; -static void FinishEncParams(VP8LEncoder* const enc) { - const WebPConfig* const config = enc->config_; - const WebPPicture* const pic = enc->pic_; - const int method = config->method; - const float quality = config->quality; - const int use_palette = enc->use_palette_; - enc->histo_bits_ = GetHistoBits(method, use_palette, pic->width, pic->height); - enc->transform_bits_ = GetTransformBits(method, enc->histo_bits_); - enc->cache_bits_ = GetCacheBits(quality); + for (tile_y = 0; tile_y < tiles_per_col; ++tile_y) { + for (tile_x = 0; tile_x < tiles_per_row; ++tile_x) { + predictors[tile_y * tiles_per_row + tile_x] = 0xff000000u | (pred << 8); + } + } + + VP8LPutBits(bw, TRANSFORM_PRESENT, 1); + VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2); + VP8LPutBits(bw, pred_bits - 2, 3); + err = EncodeImageNoHuffman(bw, predictors, &enc->hash_chain_, + (VP8LBackwardRefs*)enc->refs_, // cast const away + transform_width, transform_height, + quality); + WebPSafeFree(predictors); + return err; } +#endif // WEBP_EXPERIMENTAL_FEATURES + // ----------------------------------------------------------------------------- // VP8LEncoder @@ -1026,7 +1358,7 @@ static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config, enc->config_ = config; enc->pic_ = picture; - VP8LDspInit(); + VP8LEncDspInit(); return enc; } @@ -1036,7 +1368,7 @@ static void VP8LEncoderDelete(VP8LEncoder* enc) { VP8LHashChainClear(&enc->hash_chain_); VP8LBackwardRefsClear(&enc->refs_[0]); VP8LBackwardRefsClear(&enc->refs_[1]); - WebPSafeFree(enc->argb_); + ClearTransformBuffer(enc); WebPSafeFree(enc); } } @@ -1049,10 +1381,15 @@ WebPEncodingError VP8LEncodeStream(const WebPConfig* const config, VP8LBitWriter* const bw) { WebPEncodingError err = VP8_ENC_OK; const int quality = (int)config->quality; + const int low_effort = (config->method == 0); const int width = picture->width; const int height = picture->height; VP8LEncoder* const enc = VP8LEncoderNew(config, picture); const size_t byte_position = VP8LBitWriterNumBytes(bw); + int use_near_lossless = 0; + int hdr_size = 0; + int data_size = 0; + int use_delta_palettization = 0; if (enc == NULL) { err = VP8_ENC_ERROR_OUT_OF_MEMORY; @@ -1062,70 +1399,83 @@ WebPEncodingError VP8LEncodeStream(const WebPConfig* const config, // --------------------------------------------------------------------------- // Analyze image (entropy, num_palettes etc) - if (!AnalyzeAndInit(enc, config->image_hint)) { + if (!AnalyzeAndInit(enc)) { err = VP8_ENC_ERROR_OUT_OF_MEMORY; goto Error; } - FinishEncParams(enc); - - if (enc->use_palette_) { - err = EncodePalette(bw, enc, quality); - if (err != VP8_ENC_OK) goto Error; - // Color cache is disabled for palette. - enc->cache_bits_ = 0; + // Apply near-lossless preprocessing. + use_near_lossless = !enc->use_palette_ && (config->near_lossless < 100); + if (use_near_lossless) { + if (!VP8ApplyNearLossless(width, height, picture->argb, + config->near_lossless)) { + err = VP8_ENC_ERROR_OUT_OF_MEMORY; + goto Error; + } } - // In case image is not packed. - if (enc->argb_ == NULL) { - int y; - err = AllocateTransformBuffer(enc, width, height); +#ifdef WEBP_EXPERIMENTAL_FEATURES + if (config->delta_palettization) { + enc->use_predict_ = 1; + enc->use_cross_color_ = 0; + enc->use_subtract_green_ = 0; + enc->use_palette_ = 1; + err = MakeInputImageCopy(enc); if (err != VP8_ENC_OK) goto Error; - assert(enc->argb_ != NULL); - for (y = 0; y < height; ++y) { - memcpy(enc->argb_ + y * width, - picture->argb + y * picture->argb_stride, - width * sizeof(*enc->argb_)); + err = WebPSearchOptimalDeltaPalette(enc); + if (err != VP8_ENC_OK) goto Error; + if (enc->use_palette_) { + err = AllocateTransformBuffer(enc, width, height); + if (err != VP8_ENC_OK) goto Error; + err = EncodeDeltaPalettePredictorImage(bw, enc, quality); + if (err != VP8_ENC_OK) goto Error; + use_delta_palettization = 1; } - enc->current_width_ = width; } +#endif // WEBP_EXPERIMENTAL_FEATURES - // --------------------------------------------------------------------------- - // Apply transforms and write transform data. - - err = EvalAndApplySubtractGreen(enc, enc->current_width_, height, bw); - if (err != VP8_ENC_OK) goto Error; - - if (enc->use_predict_) { - err = ApplyPredictFilter(enc, enc->current_width_, height, quality, bw); + // Encode palette + if (enc->use_palette_) { + err = EncodePalette(bw, enc); if (err != VP8_ENC_OK) goto Error; - } - - if (enc->use_cross_color_) { - err = ApplyCrossColorFilter(enc, enc->current_width_, height, quality, bw); + err = MapImageFromPalette(enc, use_delta_palettization); if (err != VP8_ENC_OK) goto Error; } + if (!use_delta_palettization) { + // In case image is not packed. + if (enc->argb_ == NULL) { + err = MakeInputImageCopy(enc); + if (err != VP8_ENC_OK) goto Error; + } - VP8LWriteBits(bw, 1, !TRANSFORM_PRESENT); // No more transforms. + // ------------------------------------------------------------------------- + // Apply transforms and write transform data. - // --------------------------------------------------------------------------- - // Estimate the color cache size. + if (enc->use_subtract_green_) { + ApplySubtractGreen(enc, enc->current_width_, height, bw); + } - if (enc->cache_bits_ > 0) { - if (!VP8LCalculateEstimateForCacheSize(enc->argb_, enc->current_width_, - height, quality, &enc->hash_chain_, - &enc->refs_[0], &enc->cache_bits_)) { - err = VP8_ENC_ERROR_OUT_OF_MEMORY; - goto Error; + if (enc->use_predict_) { + err = ApplyPredictFilter(enc, enc->current_width_, height, quality, + low_effort, bw); + if (err != VP8_ENC_OK) goto Error; + } + + if (enc->use_cross_color_) { + err = ApplyCrossColorFilter(enc, enc->current_width_, + height, quality, bw); + if (err != VP8_ENC_OK) goto Error; } } + VP8LPutBits(bw, !TRANSFORM_PRESENT, 1); // No more transforms. + // --------------------------------------------------------------------------- // Encode and write the transformed image. - err = EncodeImageInternal(bw, enc->argb_, &enc->hash_chain_, enc->refs_, - enc->current_width_, height, quality, - enc->cache_bits_, enc->histo_bits_); + enc->current_width_, height, quality, low_effort, + &enc->cache_bits_, enc->histo_bits_, byte_position, + &hdr_size, &data_size); if (err != VP8_ENC_OK) goto Error; if (picture->stats != NULL) { @@ -1140,6 +1490,8 @@ WebPEncodingError VP8LEncodeStream(const WebPConfig* const config, stats->cache_bits = enc->cache_bits_; stats->palette_size = enc->palette_size_; stats->lossless_size = (int)(VP8LBitWriterNumBytes(bw) - byte_position); + stats->lossless_hdr_size = hdr_size; + stats->lossless_data_size = data_size; } Error: @@ -1170,7 +1522,7 @@ int VP8LEncodeImage(const WebPConfig* const config, // Initialize BitWriter with size corresponding to 16 bpp to photo images and // 8 bpp for graphical images. initial_size = (config->image_hint == WEBP_HINT_GRAPH) ? - width * height : width * height * 2; + width * height : width * height * 2; if (!VP8LBitWriterInit(&bw, initial_size)) { err = VP8_ENC_ERROR_OUT_OF_MEMORY; goto Error; @@ -1234,7 +1586,7 @@ int VP8LEncodeImage(const WebPConfig* const config, Error: if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY; - VP8LBitWriterDestroy(&bw); + VP8LBitWriterWipeOut(&bw); if (err != VP8_ENC_OK) { WebPEncodingSetError(picture, err); return 0; |