in Extended/libwebp/src/enc/vp8l_enc.c [861:1064]
static WebPEncodingError EncodeImageInternal(
VP8LBitWriter* const bw, const uint32_t* const argb,
VP8LHashChain* const hash_chain, VP8LBackwardRefs refs_array[3], int width,
int height, int quality, int low_effort, int use_cache,
const CrunchConfig* const config, 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 uint32_t histogram_image_xysize =
VP8LSubSampleSize(width, histogram_bits) *
VP8LSubSampleSize(height, histogram_bits);
VP8LHistogramSet* histogram_image = NULL;
VP8LHistogram* tmp_histo = NULL;
int histogram_image_size = 0;
size_t bit_array_size = 0;
HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc(
3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree));
HuffmanTreeToken* tokens = NULL;
HuffmanTreeCode* huffman_codes = NULL;
VP8LBackwardRefs* refs_best;
VP8LBackwardRefs* refs_tmp;
uint16_t* const histogram_symbols =
(uint16_t*)WebPSafeMalloc(histogram_image_xysize,
sizeof(*histogram_symbols));
int lz77s_idx;
VP8LBitWriter bw_init = *bw, bw_best;
int hdr_size_tmp;
assert(histogram_bits >= MIN_HUFFMAN_BITS);
assert(histogram_bits <= MAX_HUFFMAN_BITS);
assert(hdr_size != NULL);
assert(data_size != NULL);
if (histogram_symbols == NULL) {
err = VP8_ENC_ERROR_OUT_OF_MEMORY;
goto Error;
}
if (use_cache) {
// If the value is different from zero, it has been set during the
// palette analysis.
if (*cache_bits == 0) *cache_bits = MAX_COLOR_CACHE_BITS;
} else {
*cache_bits = 0;
}
// '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.
if (huff_tree == NULL ||
!VP8LHashChainFill(hash_chain, quality, argb, width, height,
low_effort) ||
!VP8LBitWriterInit(&bw_best, 0) ||
(config->lz77s_types_to_try_size_ > 1 &&
!VP8LBitWriterClone(bw, &bw_best))) {
err = VP8_ENC_ERROR_OUT_OF_MEMORY;
goto Error;
}
for (lz77s_idx = 0; lz77s_idx < config->lz77s_types_to_try_size_;
++lz77s_idx) {
refs_best = VP8LGetBackwardReferences(
width, height, argb, quality, low_effort,
config->lz77s_types_to_try_[lz77s_idx], cache_bits, hash_chain,
&refs_array[0], &refs_array[1]);
if (refs_best == NULL) {
err = VP8_ENC_ERROR_OUT_OF_MEMORY;
goto Error;
}
// Keep the best references aside and use the other element from the first
// two as a temporary for later usage.
refs_tmp = &refs_array[refs_best == &refs_array[0] ? 1 : 0];
histogram_image =
VP8LAllocateHistogramSet(histogram_image_xysize, *cache_bits);
tmp_histo = VP8LAllocateHistogram(*cache_bits);
if (histogram_image == NULL || tmp_histo == NULL) {
err = VP8_ENC_ERROR_OUT_OF_MEMORY;
goto Error;
}
// Build histogram image and symbols from backward references.
if (!VP8LGetHistoImageSymbols(width, height, refs_best, quality, low_effort,
histogram_bits, *cache_bits, histogram_image,
tmp_histo, histogram_symbols)) {
err = VP8_ENC_ERROR_OUT_OF_MEMORY;
goto Error;
}
// Create Huffman bit lengths and codes for each histogram image.
histogram_image_size = histogram_image->size;
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.
VP8LFreeHistogram(tmp_histo);
tmp_histo = NULL;
// Color Cache parameters.
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);
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) {
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] = (symbol_index << 8);
if (symbol_index >= max_index) {
max_index = symbol_index + 1;
}
}
histogram_image_size = max_index;
VP8LPutBits(bw, histogram_bits - 2, 3);
err = EncodeImageNoHuffman(
bw, histogram_argb, hash_chain, refs_tmp, &refs_array[2],
VP8LSubSampleSize(width, histogram_bits),
VP8LSubSampleSize(height, histogram_bits), quality, low_effort);
WebPSafeFree(histogram_argb);
if (err != VP8_ENC_OK) goto Error;
}
}
// Store Huffman codes.
{
int i;
int max_tokens = 0;
// 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];
if (max_tokens < codes->num_symbols) {
max_tokens = codes->num_symbols;
}
}
tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens));
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);
ClearHuffmanTreeIfOnlyOneSymbol(codes);
}
}
// Store actual literals.
hdr_size_tmp = (int)(VP8LBitWriterNumBytes(bw) - init_byte_position);
err = StoreImageToBitMask(bw, width, histogram_bits, refs_best,
histogram_symbols, huffman_codes);
// Keep track of the smallest image so far.
if (lz77s_idx == 0 ||
VP8LBitWriterNumBytes(bw) < VP8LBitWriterNumBytes(&bw_best)) {
*hdr_size = hdr_size_tmp;
*data_size =
(int)(VP8LBitWriterNumBytes(bw) - init_byte_position - *hdr_size);
VP8LBitWriterSwap(bw, &bw_best);
}
// Reset the bit writer for the following iteration if any.
if (config->lz77s_types_to_try_size_ > 1) VP8LBitWriterReset(&bw_init, bw);
WebPSafeFree(tokens);
tokens = NULL;
if (huffman_codes != NULL) {
WebPSafeFree(huffman_codes->codes);
WebPSafeFree(huffman_codes);
huffman_codes = NULL;
}
}
VP8LBitWriterSwap(bw, &bw_best);
Error:
WebPSafeFree(tokens);
WebPSafeFree(huff_tree);
VP8LFreeHistogramSet(histogram_image);
VP8LFreeHistogram(tmp_histo);
if (huffman_codes != NULL) {
WebPSafeFree(huffman_codes->codes);
WebPSafeFree(huffman_codes);
}
WebPSafeFree(histogram_symbols);
VP8LBitWriterWipeOut(&bw_best);
return err;
}