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
18 #include "./backward_references.h"
19 #include "./histogram.h"
20 #include "./vp8enci.h"
21 #include "./vp8li.h"
22 #include "../dsp/lossless.h"
23 #include "../utils/bit_writer.h"
24 #include "../utils/huffman_encode.h"
25 #include "../utils/utils.h"
26 #include "../webp/format_constants.h"
27
28 #include "./delta_palettization.h"
29
30 #define PALETTE_KEY_RIGHT_SHIFT 22 // Key for 1K buffer.
31 // Maximum number of histogram images (sub-blocks).
32 #define MAX_HUFF_IMAGE_SIZE 2600
33
34 // Palette reordering for smaller sum of deltas (and for smaller storage).
35
PaletteCompareColorsForQsort(const void * p1,const void * p2)36 static int PaletteCompareColorsForQsort(const void* p1, const void* p2) {
37 const uint32_t a = WebPMemToUint32(p1);
38 const uint32_t b = WebPMemToUint32(p2);
39 assert(a != b);
40 return (a < b) ? -1 : 1;
41 }
42
PaletteComponentDistance(uint32_t v)43 static WEBP_INLINE uint32_t PaletteComponentDistance(uint32_t v) {
44 return (v <= 128) ? v : (256 - v);
45 }
46
47 // Computes a value that is related to the entropy created by the
48 // palette entry diff.
49 //
50 // Note that the last & 0xff is a no-operation in the next statement, but
51 // removed by most compilers and is here only for regularity of the code.
PaletteColorDistance(uint32_t col1,uint32_t col2)52 static WEBP_INLINE uint32_t PaletteColorDistance(uint32_t col1, uint32_t col2) {
53 const uint32_t diff = VP8LSubPixels(col1, col2);
54 const int kMoreWeightForRGBThanForAlpha = 9;
55 uint32_t score;
56 score = PaletteComponentDistance((diff >> 0) & 0xff);
57 score += PaletteComponentDistance((diff >> 8) & 0xff);
58 score += PaletteComponentDistance((diff >> 16) & 0xff);
59 score *= kMoreWeightForRGBThanForAlpha;
60 score += PaletteComponentDistance((diff >> 24) & 0xff);
61 return score;
62 }
63
SwapColor(uint32_t * const col1,uint32_t * const col2)64 static WEBP_INLINE void SwapColor(uint32_t* const col1, uint32_t* const col2) {
65 const uint32_t tmp = *col1;
66 *col1 = *col2;
67 *col2 = tmp;
68 }
69
GreedyMinimizeDeltas(uint32_t palette[],int num_colors)70 static void GreedyMinimizeDeltas(uint32_t palette[], int num_colors) {
71 // Find greedily always the closest color of the predicted color to minimize
72 // deltas in the palette. This reduces storage needs since the
73 // palette is stored with delta encoding.
74 uint32_t predict = 0x00000000;
75 int i, k;
76 for (i = 0; i < num_colors; ++i) {
77 int best_ix = i;
78 uint32_t best_score = ~0U;
79 for (k = i; k < num_colors; ++k) {
80 const uint32_t cur_score = PaletteColorDistance(palette[k], predict);
81 if (best_score > cur_score) {
82 best_score = cur_score;
83 best_ix = k;
84 }
85 }
86 SwapColor(&palette[best_ix], &palette[i]);
87 predict = palette[i];
88 }
89 }
90
91 // The palette has been sorted by alpha. This function checks if the other
92 // components of the palette have a monotonic development with regards to
93 // position in the palette. If all have monotonic development, there is
94 // no benefit to re-organize them greedily. A monotonic development
95 // would be spotted in green-only situations (like lossy alpha) or gray-scale
96 // images.
PaletteHasNonMonotonousDeltas(uint32_t palette[],int num_colors)97 static int PaletteHasNonMonotonousDeltas(uint32_t palette[], int num_colors) {
98 uint32_t predict = 0x000000;
99 int i;
100 uint8_t sign_found = 0x00;
101 for (i = 0; i < num_colors; ++i) {
102 const uint32_t diff = VP8LSubPixels(palette[i], predict);
103 const uint8_t rd = (diff >> 16) & 0xff;
104 const uint8_t gd = (diff >> 8) & 0xff;
105 const uint8_t bd = (diff >> 0) & 0xff;
106 if (rd != 0x00) {
107 sign_found |= (rd < 0x80) ? 1 : 2;
108 }
109 if (gd != 0x00) {
110 sign_found |= (gd < 0x80) ? 8 : 16;
111 }
112 if (bd != 0x00) {
113 sign_found |= (bd < 0x80) ? 64 : 128;
114 }
115 predict = palette[i];
116 }
117 return (sign_found & (sign_found << 1)) != 0; // two consequent signs.
118 }
119
120 // -----------------------------------------------------------------------------
121 // Palette
122
123 // If number of colors in the image is less than or equal to MAX_PALETTE_SIZE,
124 // creates a palette and returns true, else returns false.
AnalyzeAndCreatePalette(const WebPPicture * const pic,int low_effort,uint32_t palette[MAX_PALETTE_SIZE],int * const palette_size)125 static int AnalyzeAndCreatePalette(const WebPPicture* const pic,
126 int low_effort,
127 uint32_t palette[MAX_PALETTE_SIZE],
128 int* const palette_size) {
129 int i, x, y, key;
130 int num_colors = 0;
131 uint8_t in_use[MAX_PALETTE_SIZE * 4] = { 0 };
132 uint32_t colors[MAX_PALETTE_SIZE * 4];
133 static const uint32_t kHashMul = 0x1e35a7bd;
134 const uint32_t* argb = pic->argb;
135 const int width = pic->width;
136 const int height = pic->height;
137 uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0]
138
139 for (y = 0; y < height; ++y) {
140 for (x = 0; x < width; ++x) {
141 if (argb[x] == last_pix) {
142 continue;
143 }
144 last_pix = argb[x];
145 key = (kHashMul * last_pix) >> PALETTE_KEY_RIGHT_SHIFT;
146 while (1) {
147 if (!in_use[key]) {
148 colors[key] = last_pix;
149 in_use[key] = 1;
150 ++num_colors;
151 if (num_colors > MAX_PALETTE_SIZE) {
152 return 0;
153 }
154 break;
155 } else if (colors[key] == last_pix) {
156 // The color is already there.
157 break;
158 } else {
159 // Some other color sits there.
160 // Do linear conflict resolution.
161 ++key;
162 key &= (MAX_PALETTE_SIZE * 4 - 1); // key mask for 1K buffer.
163 }
164 }
165 }
166 argb += pic->argb_stride;
167 }
168
169 // TODO(skal): could we reuse in_use[] to speed up EncodePalette()?
170 num_colors = 0;
171 for (i = 0; i < (int)(sizeof(in_use) / sizeof(in_use[0])); ++i) {
172 if (in_use[i]) {
173 palette[num_colors] = colors[i];
174 ++num_colors;
175 }
176 }
177 *palette_size = num_colors;
178 qsort(palette, num_colors, sizeof(*palette), PaletteCompareColorsForQsort);
179 if (!low_effort && PaletteHasNonMonotonousDeltas(palette, num_colors)) {
180 GreedyMinimizeDeltas(palette, num_colors);
181 }
182 return 1;
183 }
184
185 // These five modes are evaluated and their respective entropy is computed.
186 typedef enum {
187 kDirect = 0,
188 kSpatial = 1,
189 kSubGreen = 2,
190 kSpatialSubGreen = 3,
191 kPalette = 4,
192 kNumEntropyIx = 5
193 } EntropyIx;
194
195 typedef enum {
196 kHistoAlpha = 0,
197 kHistoAlphaPred,
198 kHistoGreen,
199 kHistoGreenPred,
200 kHistoRed,
201 kHistoRedPred,
202 kHistoBlue,
203 kHistoBluePred,
204 kHistoRedSubGreen,
205 kHistoRedPredSubGreen,
206 kHistoBlueSubGreen,
207 kHistoBluePredSubGreen,
208 kHistoPalette,
209 kHistoTotal // Must be last.
210 } HistoIx;
211
AddSingleSubGreen(uint32_t p,uint32_t * r,uint32_t * b)212 static void AddSingleSubGreen(uint32_t p, uint32_t* r, uint32_t* b) {
213 const uint32_t green = p >> 8; // The upper bits are masked away later.
214 ++r[((p >> 16) - green) & 0xff];
215 ++b[(p - green) & 0xff];
216 }
217
AddSingle(uint32_t p,uint32_t * a,uint32_t * r,uint32_t * g,uint32_t * b)218 static void AddSingle(uint32_t p,
219 uint32_t* a, uint32_t* r, uint32_t* g, uint32_t* b) {
220 ++a[p >> 24];
221 ++r[(p >> 16) & 0xff];
222 ++g[(p >> 8) & 0xff];
223 ++b[(p & 0xff)];
224 }
225
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)226 static int AnalyzeEntropy(const uint32_t* argb,
227 int width, int height, int argb_stride,
228 int use_palette,
229 EntropyIx* const min_entropy_ix,
230 int* const red_and_blue_always_zero) {
231 // Allocate histogram set with cache_bits = 0.
232 uint32_t* const histo =
233 (uint32_t*)WebPSafeCalloc(kHistoTotal, sizeof(*histo) * 256);
234 if (histo != NULL) {
235 int i, x, y;
236 const uint32_t* prev_row = argb;
237 const uint32_t* curr_row = argb + argb_stride;
238 for (y = 1; y < height; ++y) {
239 uint32_t prev_pix = curr_row[0];
240 for (x = 1; x < width; ++x) {
241 const uint32_t pix = curr_row[x];
242 const uint32_t pix_diff = VP8LSubPixels(pix, prev_pix);
243 if ((pix_diff == 0) || (pix == prev_row[x])) continue;
244 prev_pix = pix;
245 AddSingle(pix,
246 &histo[kHistoAlpha * 256],
247 &histo[kHistoRed * 256],
248 &histo[kHistoGreen * 256],
249 &histo[kHistoBlue * 256]);
250 AddSingle(pix_diff,
251 &histo[kHistoAlphaPred * 256],
252 &histo[kHistoRedPred * 256],
253 &histo[kHistoGreenPred * 256],
254 &histo[kHistoBluePred * 256]);
255 AddSingleSubGreen(pix,
256 &histo[kHistoRedSubGreen * 256],
257 &histo[kHistoBlueSubGreen * 256]);
258 AddSingleSubGreen(pix_diff,
259 &histo[kHistoRedPredSubGreen * 256],
260 &histo[kHistoBluePredSubGreen * 256]);
261 {
262 // Approximate the palette by the entropy of the multiplicative hash.
263 const int hash = ((pix + (pix >> 19)) * 0x39c5fba7) >> 24;
264 ++histo[kHistoPalette * 256 + (hash & 0xff)];
265 }
266 }
267 prev_row = curr_row;
268 curr_row += argb_stride;
269 }
270 {
271 double entropy_comp[kHistoTotal];
272 double entropy[kNumEntropyIx];
273 EntropyIx k;
274 EntropyIx last_mode_to_analyze =
275 use_palette ? kPalette : kSpatialSubGreen;
276 int j;
277 // Let's add one zero to the predicted histograms. The zeros are removed
278 // too efficiently by the pix_diff == 0 comparison, at least one of the
279 // zeros is likely to exist.
280 ++histo[kHistoRedPredSubGreen * 256];
281 ++histo[kHistoBluePredSubGreen * 256];
282 ++histo[kHistoRedPred * 256];
283 ++histo[kHistoGreenPred * 256];
284 ++histo[kHistoBluePred * 256];
285 ++histo[kHistoAlphaPred * 256];
286
287 for (j = 0; j < kHistoTotal; ++j) {
288 entropy_comp[j] = VP8LBitsEntropy(&histo[j * 256], 256, NULL);
289 }
290 entropy[kDirect] = entropy_comp[kHistoAlpha] +
291 entropy_comp[kHistoRed] +
292 entropy_comp[kHistoGreen] +
293 entropy_comp[kHistoBlue];
294 entropy[kSpatial] = entropy_comp[kHistoAlphaPred] +
295 entropy_comp[kHistoRedPred] +
296 entropy_comp[kHistoGreenPred] +
297 entropy_comp[kHistoBluePred];
298 entropy[kSubGreen] = entropy_comp[kHistoAlpha] +
299 entropy_comp[kHistoRedSubGreen] +
300 entropy_comp[kHistoGreen] +
301 entropy_comp[kHistoBlueSubGreen];
302 entropy[kSpatialSubGreen] = entropy_comp[kHistoAlphaPred] +
303 entropy_comp[kHistoRedPredSubGreen] +
304 entropy_comp[kHistoGreenPred] +
305 entropy_comp[kHistoBluePredSubGreen];
306 // Palette mode seems more efficient in a breakeven case. Bias with 1.0.
307 entropy[kPalette] = entropy_comp[kHistoPalette] - 1.0;
308
309 *min_entropy_ix = kDirect;
310 for (k = kDirect + 1; k <= last_mode_to_analyze; ++k) {
311 if (entropy[*min_entropy_ix] > entropy[k]) {
312 *min_entropy_ix = k;
313 }
314 }
315 *red_and_blue_always_zero = 1;
316 // Let's check if the histogram of the chosen entropy mode has
317 // non-zero red and blue values. If all are zero, we can later skip
318 // the cross color optimization.
319 {
320 static const uint8_t kHistoPairs[5][2] = {
321 { kHistoRed, kHistoBlue },
322 { kHistoRedPred, kHistoBluePred },
323 { kHistoRedSubGreen, kHistoBlueSubGreen },
324 { kHistoRedPredSubGreen, kHistoBluePredSubGreen },
325 { kHistoRed, kHistoBlue }
326 };
327 const uint32_t* const red_histo =
328 &histo[256 * kHistoPairs[*min_entropy_ix][0]];
329 const uint32_t* const blue_histo =
330 &histo[256 * kHistoPairs[*min_entropy_ix][1]];
331 for (i = 1; i < 256; ++i) {
332 if ((red_histo[i] | blue_histo[i]) != 0) {
333 *red_and_blue_always_zero = 0;
334 break;
335 }
336 }
337 }
338 }
339 free(histo);
340 return 1;
341 } else {
342 return 0;
343 }
344 }
345
GetHistoBits(int method,int use_palette,int width,int height)346 static int GetHistoBits(int method, int use_palette, int width, int height) {
347 // Make tile size a function of encoding method (Range: 0 to 6).
348 int histo_bits = (use_palette ? 9 : 7) - method;
349 while (1) {
350 const int huff_image_size = VP8LSubSampleSize(width, histo_bits) *
351 VP8LSubSampleSize(height, histo_bits);
352 if (huff_image_size <= MAX_HUFF_IMAGE_SIZE) break;
353 ++histo_bits;
354 }
355 return (histo_bits < MIN_HUFFMAN_BITS) ? MIN_HUFFMAN_BITS :
356 (histo_bits > MAX_HUFFMAN_BITS) ? MAX_HUFFMAN_BITS : histo_bits;
357 }
358
GetTransformBits(int method,int histo_bits)359 static int GetTransformBits(int method, int histo_bits) {
360 const int max_transform_bits = (method < 4) ? 6 : (method > 4) ? 4 : 5;
361 return (histo_bits > max_transform_bits) ? max_transform_bits : histo_bits;
362 }
363
AnalyzeAndInit(VP8LEncoder * const enc)364 static int AnalyzeAndInit(VP8LEncoder* const enc) {
365 const WebPPicture* const pic = enc->pic_;
366 const int width = pic->width;
367 const int height = pic->height;
368 const int pix_cnt = width * height;
369 const WebPConfig* const config = enc->config_;
370 const int method = config->method;
371 const int low_effort = (config->method == 0);
372 // we round the block size up, so we're guaranteed to have
373 // at max MAX_REFS_BLOCK_PER_IMAGE blocks used:
374 int refs_block_size = (pix_cnt - 1) / MAX_REFS_BLOCK_PER_IMAGE + 1;
375 assert(pic != NULL && pic->argb != NULL);
376
377 enc->use_cross_color_ = 0;
378 enc->use_predict_ = 0;
379 enc->use_subtract_green_ = 0;
380 enc->use_palette_ =
381 AnalyzeAndCreatePalette(pic, low_effort,
382 enc->palette_, &enc->palette_size_);
383
384 // TODO(jyrki): replace the decision to be based on an actual estimate
385 // of entropy, or even spatial variance of entropy.
386 enc->histo_bits_ = GetHistoBits(method, enc->use_palette_,
387 pic->width, pic->height);
388 enc->transform_bits_ = GetTransformBits(method, enc->histo_bits_);
389
390 if (low_effort) {
391 // AnalyzeEntropy is somewhat slow.
392 enc->use_predict_ = !enc->use_palette_;
393 enc->use_subtract_green_ = !enc->use_palette_;
394 enc->use_cross_color_ = 0;
395 } else {
396 int red_and_blue_always_zero;
397 EntropyIx min_entropy_ix;
398 if (!AnalyzeEntropy(pic->argb, width, height, pic->argb_stride,
399 enc->use_palette_, &min_entropy_ix,
400 &red_and_blue_always_zero)) {
401 return 0;
402 }
403 enc->use_palette_ = (min_entropy_ix == kPalette);
404 enc->use_subtract_green_ =
405 (min_entropy_ix == kSubGreen) || (min_entropy_ix == kSpatialSubGreen);
406 enc->use_predict_ =
407 (min_entropy_ix == kSpatial) || (min_entropy_ix == kSpatialSubGreen);
408 enc->use_cross_color_ = red_and_blue_always_zero ? 0 : enc->use_predict_;
409 }
410
411 if (!VP8LHashChainInit(&enc->hash_chain_, pix_cnt)) return 0;
412
413 // palette-friendly input typically uses less literals
414 // -> reduce block size a bit
415 if (enc->use_palette_) refs_block_size /= 2;
416 VP8LBackwardRefsInit(&enc->refs_[0], refs_block_size);
417 VP8LBackwardRefsInit(&enc->refs_[1], refs_block_size);
418
419 return 1;
420 }
421
422 // Returns false in case of memory error.
GetHuffBitLengthsAndCodes(const VP8LHistogramSet * const histogram_image,HuffmanTreeCode * const huffman_codes)423 static int GetHuffBitLengthsAndCodes(
424 const VP8LHistogramSet* const histogram_image,
425 HuffmanTreeCode* const huffman_codes) {
426 int i, k;
427 int ok = 0;
428 uint64_t total_length_size = 0;
429 uint8_t* mem_buf = NULL;
430 const int histogram_image_size = histogram_image->size;
431 int max_num_symbols = 0;
432 uint8_t* buf_rle = NULL;
433 HuffmanTree* huff_tree = NULL;
434
435 // Iterate over all histograms and get the aggregate number of codes used.
436 for (i = 0; i < histogram_image_size; ++i) {
437 const VP8LHistogram* const histo = histogram_image->histograms[i];
438 HuffmanTreeCode* const codes = &huffman_codes[5 * i];
439 for (k = 0; k < 5; ++k) {
440 const int num_symbols =
441 (k == 0) ? VP8LHistogramNumCodes(histo->palette_code_bits_) :
442 (k == 4) ? NUM_DISTANCE_CODES : 256;
443 codes[k].num_symbols = num_symbols;
444 total_length_size += num_symbols;
445 }
446 }
447
448 // Allocate and Set Huffman codes.
449 {
450 uint16_t* codes;
451 uint8_t* lengths;
452 mem_buf = (uint8_t*)WebPSafeCalloc(total_length_size,
453 sizeof(*lengths) + sizeof(*codes));
454 if (mem_buf == NULL) goto End;
455
456 codes = (uint16_t*)mem_buf;
457 lengths = (uint8_t*)&codes[total_length_size];
458 for (i = 0; i < 5 * histogram_image_size; ++i) {
459 const int bit_length = huffman_codes[i].num_symbols;
460 huffman_codes[i].codes = codes;
461 huffman_codes[i].code_lengths = lengths;
462 codes += bit_length;
463 lengths += bit_length;
464 if (max_num_symbols < bit_length) {
465 max_num_symbols = bit_length;
466 }
467 }
468 }
469
470 buf_rle = (uint8_t*)WebPSafeMalloc(1ULL, max_num_symbols);
471 huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * max_num_symbols,
472 sizeof(*huff_tree));
473 if (buf_rle == NULL || huff_tree == NULL) goto End;
474
475 // Create Huffman trees.
476 for (i = 0; i < histogram_image_size; ++i) {
477 HuffmanTreeCode* const codes = &huffman_codes[5 * i];
478 VP8LHistogram* const histo = histogram_image->histograms[i];
479 VP8LCreateHuffmanTree(histo->literal_, 15, buf_rle, huff_tree, codes + 0);
480 VP8LCreateHuffmanTree(histo->red_, 15, buf_rle, huff_tree, codes + 1);
481 VP8LCreateHuffmanTree(histo->blue_, 15, buf_rle, huff_tree, codes + 2);
482 VP8LCreateHuffmanTree(histo->alpha_, 15, buf_rle, huff_tree, codes + 3);
483 VP8LCreateHuffmanTree(histo->distance_, 15, buf_rle, huff_tree, codes + 4);
484 }
485 ok = 1;
486 End:
487 WebPSafeFree(huff_tree);
488 WebPSafeFree(buf_rle);
489 if (!ok) {
490 WebPSafeFree(mem_buf);
491 memset(huffman_codes, 0, 5 * histogram_image_size * sizeof(*huffman_codes));
492 }
493 return ok;
494 }
495
StoreHuffmanTreeOfHuffmanTreeToBitMask(VP8LBitWriter * const bw,const uint8_t * code_length_bitdepth)496 static void StoreHuffmanTreeOfHuffmanTreeToBitMask(
497 VP8LBitWriter* const bw, const uint8_t* code_length_bitdepth) {
498 // RFC 1951 will calm you down if you are worried about this funny sequence.
499 // This sequence is tuned from that, but more weighted for lower symbol count,
500 // and more spiking histograms.
501 static const uint8_t kStorageOrder[CODE_LENGTH_CODES] = {
502 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
503 };
504 int i;
505 // Throw away trailing zeros:
506 int codes_to_store = CODE_LENGTH_CODES;
507 for (; codes_to_store > 4; --codes_to_store) {
508 if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
509 break;
510 }
511 }
512 VP8LPutBits(bw, codes_to_store - 4, 4);
513 for (i = 0; i < codes_to_store; ++i) {
514 VP8LPutBits(bw, code_length_bitdepth[kStorageOrder[i]], 3);
515 }
516 }
517
ClearHuffmanTreeIfOnlyOneSymbol(HuffmanTreeCode * const huffman_code)518 static void ClearHuffmanTreeIfOnlyOneSymbol(
519 HuffmanTreeCode* const huffman_code) {
520 int k;
521 int count = 0;
522 for (k = 0; k < huffman_code->num_symbols; ++k) {
523 if (huffman_code->code_lengths[k] != 0) {
524 ++count;
525 if (count > 1) return;
526 }
527 }
528 for (k = 0; k < huffman_code->num_symbols; ++k) {
529 huffman_code->code_lengths[k] = 0;
530 huffman_code->codes[k] = 0;
531 }
532 }
533
StoreHuffmanTreeToBitMask(VP8LBitWriter * const bw,const HuffmanTreeToken * const tokens,const int num_tokens,const HuffmanTreeCode * const huffman_code)534 static void StoreHuffmanTreeToBitMask(
535 VP8LBitWriter* const bw,
536 const HuffmanTreeToken* const tokens, const int num_tokens,
537 const HuffmanTreeCode* const huffman_code) {
538 int i;
539 for (i = 0; i < num_tokens; ++i) {
540 const int ix = tokens[i].code;
541 const int extra_bits = tokens[i].extra_bits;
542 VP8LPutBits(bw, huffman_code->codes[ix], huffman_code->code_lengths[ix]);
543 switch (ix) {
544 case 16:
545 VP8LPutBits(bw, extra_bits, 2);
546 break;
547 case 17:
548 VP8LPutBits(bw, extra_bits, 3);
549 break;
550 case 18:
551 VP8LPutBits(bw, extra_bits, 7);
552 break;
553 }
554 }
555 }
556
557 // 'huff_tree' and 'tokens' are pre-alloacted buffers.
StoreFullHuffmanCode(VP8LBitWriter * const bw,HuffmanTree * const huff_tree,HuffmanTreeToken * const tokens,const HuffmanTreeCode * const tree)558 static void StoreFullHuffmanCode(VP8LBitWriter* const bw,
559 HuffmanTree* const huff_tree,
560 HuffmanTreeToken* const tokens,
561 const HuffmanTreeCode* const tree) {
562 uint8_t code_length_bitdepth[CODE_LENGTH_CODES] = { 0 };
563 uint16_t code_length_bitdepth_symbols[CODE_LENGTH_CODES] = { 0 };
564 const int max_tokens = tree->num_symbols;
565 int num_tokens;
566 HuffmanTreeCode huffman_code;
567 huffman_code.num_symbols = CODE_LENGTH_CODES;
568 huffman_code.code_lengths = code_length_bitdepth;
569 huffman_code.codes = code_length_bitdepth_symbols;
570
571 VP8LPutBits(bw, 0, 1);
572 num_tokens = VP8LCreateCompressedHuffmanTree(tree, tokens, max_tokens);
573 {
574 uint32_t histogram[CODE_LENGTH_CODES] = { 0 };
575 uint8_t buf_rle[CODE_LENGTH_CODES] = { 0 };
576 int i;
577 for (i = 0; i < num_tokens; ++i) {
578 ++histogram[tokens[i].code];
579 }
580
581 VP8LCreateHuffmanTree(histogram, 7, buf_rle, huff_tree, &huffman_code);
582 }
583
584 StoreHuffmanTreeOfHuffmanTreeToBitMask(bw, code_length_bitdepth);
585 ClearHuffmanTreeIfOnlyOneSymbol(&huffman_code);
586 {
587 int trailing_zero_bits = 0;
588 int trimmed_length = num_tokens;
589 int write_trimmed_length;
590 int length;
591 int i = num_tokens;
592 while (i-- > 0) {
593 const int ix = tokens[i].code;
594 if (ix == 0 || ix == 17 || ix == 18) {
595 --trimmed_length; // discount trailing zeros
596 trailing_zero_bits += code_length_bitdepth[ix];
597 if (ix == 17) {
598 trailing_zero_bits += 3;
599 } else if (ix == 18) {
600 trailing_zero_bits += 7;
601 }
602 } else {
603 break;
604 }
605 }
606 write_trimmed_length = (trimmed_length > 1 && trailing_zero_bits > 12);
607 length = write_trimmed_length ? trimmed_length : num_tokens;
608 VP8LPutBits(bw, write_trimmed_length, 1);
609 if (write_trimmed_length) {
610 const int nbits = VP8LBitsLog2Ceiling(trimmed_length - 1);
611 const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2;
612 VP8LPutBits(bw, nbitpairs - 1, 3);
613 assert(trimmed_length >= 2);
614 VP8LPutBits(bw, trimmed_length - 2, nbitpairs * 2);
615 }
616 StoreHuffmanTreeToBitMask(bw, tokens, length, &huffman_code);
617 }
618 }
619
620 // 'huff_tree' and 'tokens' are pre-alloacted buffers.
StoreHuffmanCode(VP8LBitWriter * const bw,HuffmanTree * const huff_tree,HuffmanTreeToken * const tokens,const HuffmanTreeCode * const huffman_code)621 static void StoreHuffmanCode(VP8LBitWriter* const bw,
622 HuffmanTree* const huff_tree,
623 HuffmanTreeToken* const tokens,
624 const HuffmanTreeCode* const huffman_code) {
625 int i;
626 int count = 0;
627 int symbols[2] = { 0, 0 };
628 const int kMaxBits = 8;
629 const int kMaxSymbol = 1 << kMaxBits;
630
631 // Check whether it's a small tree.
632 for (i = 0; i < huffman_code->num_symbols && count < 3; ++i) {
633 if (huffman_code->code_lengths[i] != 0) {
634 if (count < 2) symbols[count] = i;
635 ++count;
636 }
637 }
638
639 if (count == 0) { // emit minimal tree for empty cases
640 // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0
641 VP8LPutBits(bw, 0x01, 4);
642 } else if (count <= 2 && symbols[0] < kMaxSymbol && symbols[1] < kMaxSymbol) {
643 VP8LPutBits(bw, 1, 1); // Small tree marker to encode 1 or 2 symbols.
644 VP8LPutBits(bw, count - 1, 1);
645 if (symbols[0] <= 1) {
646 VP8LPutBits(bw, 0, 1); // Code bit for small (1 bit) symbol value.
647 VP8LPutBits(bw, symbols[0], 1);
648 } else {
649 VP8LPutBits(bw, 1, 1);
650 VP8LPutBits(bw, symbols[0], 8);
651 }
652 if (count == 2) {
653 VP8LPutBits(bw, symbols[1], 8);
654 }
655 } else {
656 StoreFullHuffmanCode(bw, huff_tree, tokens, huffman_code);
657 }
658 }
659
WriteHuffmanCode(VP8LBitWriter * const bw,const HuffmanTreeCode * const code,int code_index)660 static WEBP_INLINE void WriteHuffmanCode(VP8LBitWriter* const bw,
661 const HuffmanTreeCode* const code,
662 int code_index) {
663 const int depth = code->code_lengths[code_index];
664 const int symbol = code->codes[code_index];
665 VP8LPutBits(bw, symbol, depth);
666 }
667
WriteHuffmanCodeWithExtraBits(VP8LBitWriter * const bw,const HuffmanTreeCode * const code,int code_index,int bits,int n_bits)668 static WEBP_INLINE void WriteHuffmanCodeWithExtraBits(
669 VP8LBitWriter* const bw,
670 const HuffmanTreeCode* const code,
671 int code_index,
672 int bits,
673 int n_bits) {
674 const int depth = code->code_lengths[code_index];
675 const int symbol = code->codes[code_index];
676 VP8LPutBits(bw, (bits << depth) | symbol, depth + n_bits);
677 }
678
StoreImageToBitMask(VP8LBitWriter * const bw,int width,int histo_bits,VP8LBackwardRefs * const refs,const uint16_t * histogram_symbols,const HuffmanTreeCode * const huffman_codes)679 static WebPEncodingError StoreImageToBitMask(
680 VP8LBitWriter* const bw, int width, int histo_bits,
681 VP8LBackwardRefs* const refs,
682 const uint16_t* histogram_symbols,
683 const HuffmanTreeCode* const huffman_codes) {
684 const int histo_xsize = histo_bits ? VP8LSubSampleSize(width, histo_bits) : 1;
685 const int tile_mask = (histo_bits == 0) ? 0 : -(1 << histo_bits);
686 // x and y trace the position in the image.
687 int x = 0;
688 int y = 0;
689 int tile_x = x & tile_mask;
690 int tile_y = y & tile_mask;
691 int histogram_ix = histogram_symbols[0];
692 const HuffmanTreeCode* codes = huffman_codes + 5 * histogram_ix;
693 VP8LRefsCursor c = VP8LRefsCursorInit(refs);
694 while (VP8LRefsCursorOk(&c)) {
695 const PixOrCopy* const v = c.cur_pos;
696 if ((tile_x != (x & tile_mask)) || (tile_y != (y & tile_mask))) {
697 tile_x = x & tile_mask;
698 tile_y = y & tile_mask;
699 histogram_ix = histogram_symbols[(y >> histo_bits) * histo_xsize +
700 (x >> histo_bits)];
701 codes = huffman_codes + 5 * histogram_ix;
702 }
703 if (PixOrCopyIsLiteral(v)) {
704 static const int order[] = { 1, 2, 0, 3 };
705 int k;
706 for (k = 0; k < 4; ++k) {
707 const int code = PixOrCopyLiteral(v, order[k]);
708 WriteHuffmanCode(bw, codes + k, code);
709 }
710 } else if (PixOrCopyIsCacheIdx(v)) {
711 const int code = PixOrCopyCacheIdx(v);
712 const int literal_ix = 256 + NUM_LENGTH_CODES + code;
713 WriteHuffmanCode(bw, codes, literal_ix);
714 } else {
715 int bits, n_bits;
716 int code;
717
718 const int distance = PixOrCopyDistance(v);
719 VP8LPrefixEncode(v->len, &code, &n_bits, &bits);
720 WriteHuffmanCodeWithExtraBits(bw, codes, 256 + code, bits, n_bits);
721
722 // Don't write the distance with the extra bits code since
723 // the distance can be up to 18 bits of extra bits, and the prefix
724 // 15 bits, totaling to 33, and our PutBits only supports up to 32 bits.
725 // TODO(jyrki): optimize this further.
726 VP8LPrefixEncode(distance, &code, &n_bits, &bits);
727 WriteHuffmanCode(bw, codes + 4, code);
728 VP8LPutBits(bw, bits, n_bits);
729 }
730 x += PixOrCopyLength(v);
731 while (x >= width) {
732 x -= width;
733 ++y;
734 }
735 VP8LRefsCursorNext(&c);
736 }
737 return bw->error_ ? VP8_ENC_ERROR_OUT_OF_MEMORY : VP8_ENC_OK;
738 }
739
740 // Special case of EncodeImageInternal() for cache-bits=0, histo_bits=31
EncodeImageNoHuffman(VP8LBitWriter * const bw,const uint32_t * const argb,VP8LHashChain * const hash_chain,VP8LBackwardRefs refs_array[2],int width,int height,int quality)741 static WebPEncodingError EncodeImageNoHuffman(VP8LBitWriter* const bw,
742 const uint32_t* const argb,
743 VP8LHashChain* const hash_chain,
744 VP8LBackwardRefs refs_array[2],
745 int width, int height,
746 int quality) {
747 int i;
748 int max_tokens = 0;
749 WebPEncodingError err = VP8_ENC_OK;
750 VP8LBackwardRefs* refs;
751 HuffmanTreeToken* tokens = NULL;
752 HuffmanTreeCode huffman_codes[5] = { { 0, NULL, NULL } };
753 const uint16_t histogram_symbols[1] = { 0 }; // only one tree, one symbol
754 int cache_bits = 0;
755 VP8LHistogramSet* histogram_image = NULL;
756 HuffmanTree* const huff_tree = (HuffmanTree*)WebPSafeMalloc(
757 3ULL * CODE_LENGTH_CODES, sizeof(*huff_tree));
758 if (huff_tree == NULL) {
759 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
760 goto Error;
761 }
762
763 // Calculate backward references from ARGB image.
764 refs = VP8LGetBackwardReferences(width, height, argb, quality, 0, &cache_bits,
765 hash_chain, refs_array);
766 if (refs == NULL) {
767 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
768 goto Error;
769 }
770 histogram_image = VP8LAllocateHistogramSet(1, cache_bits);
771 if (histogram_image == NULL) {
772 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
773 goto Error;
774 }
775
776 // Build histogram image and symbols from backward references.
777 VP8LHistogramStoreRefs(refs, histogram_image->histograms[0]);
778
779 // Create Huffman bit lengths and codes for each histogram image.
780 assert(histogram_image->size == 1);
781 if (!GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) {
782 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
783 goto Error;
784 }
785
786 // No color cache, no Huffman image.
787 VP8LPutBits(bw, 0, 1);
788
789 // Find maximum number of symbols for the huffman tree-set.
790 for (i = 0; i < 5; ++i) {
791 HuffmanTreeCode* const codes = &huffman_codes[i];
792 if (max_tokens < codes->num_symbols) {
793 max_tokens = codes->num_symbols;
794 }
795 }
796
797 tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens, sizeof(*tokens));
798 if (tokens == NULL) {
799 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
800 goto Error;
801 }
802
803 // Store Huffman codes.
804 for (i = 0; i < 5; ++i) {
805 HuffmanTreeCode* const codes = &huffman_codes[i];
806 StoreHuffmanCode(bw, huff_tree, tokens, codes);
807 ClearHuffmanTreeIfOnlyOneSymbol(codes);
808 }
809
810 // Store actual literals.
811 err = StoreImageToBitMask(bw, width, 0, refs, histogram_symbols,
812 huffman_codes);
813
814 Error:
815 WebPSafeFree(tokens);
816 WebPSafeFree(huff_tree);
817 VP8LFreeHistogramSet(histogram_image);
818 WebPSafeFree(huffman_codes[0].codes);
819 return err;
820 }
821
EncodeImageInternal(VP8LBitWriter * const bw,const uint32_t * const argb,VP8LHashChain * const hash_chain,VP8LBackwardRefs refs_array[2],int width,int height,int quality,int low_effort,int * cache_bits,int histogram_bits,size_t init_byte_position,int * const hdr_size,int * const data_size)822 static WebPEncodingError EncodeImageInternal(VP8LBitWriter* const bw,
823 const uint32_t* const argb,
824 VP8LHashChain* const hash_chain,
825 VP8LBackwardRefs refs_array[2],
826 int width, int height, int quality,
827 int low_effort, int* cache_bits,
828 int histogram_bits,
829 size_t init_byte_position,
830 int* const hdr_size,
831 int* const data_size) {
832 WebPEncodingError err = VP8_ENC_OK;
833 const uint32_t histogram_image_xysize =
834 VP8LSubSampleSize(width, histogram_bits) *
835 VP8LSubSampleSize(height, histogram_bits);
836 VP8LHistogramSet* histogram_image = NULL;
837 VP8LHistogramSet* tmp_histos = NULL;
838 int histogram_image_size = 0;
839 size_t bit_array_size = 0;
840 HuffmanTree* huff_tree = NULL;
841 HuffmanTreeToken* tokens = NULL;
842 HuffmanTreeCode* huffman_codes = NULL;
843 VP8LBackwardRefs refs;
844 VP8LBackwardRefs* best_refs;
845 uint16_t* const histogram_symbols =
846 (uint16_t*)WebPSafeMalloc(histogram_image_xysize,
847 sizeof(*histogram_symbols));
848 assert(histogram_bits >= MIN_HUFFMAN_BITS);
849 assert(histogram_bits <= MAX_HUFFMAN_BITS);
850 assert(hdr_size != NULL);
851 assert(data_size != NULL);
852
853 VP8LBackwardRefsInit(&refs, refs_array[0].block_size_);
854 if (histogram_symbols == NULL) {
855 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
856 goto Error;
857 }
858
859 *cache_bits = MAX_COLOR_CACHE_BITS;
860 // 'best_refs' is the reference to the best backward refs and points to one
861 // of refs_array[0] or refs_array[1].
862 // Calculate backward references from ARGB image.
863 best_refs = VP8LGetBackwardReferences(width, height, argb, quality,
864 low_effort, cache_bits, hash_chain,
865 refs_array);
866 if (best_refs == NULL || !VP8LBackwardRefsCopy(best_refs, &refs)) {
867 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
868 goto Error;
869 }
870 histogram_image =
871 VP8LAllocateHistogramSet(histogram_image_xysize, *cache_bits);
872 tmp_histos = VP8LAllocateHistogramSet(2, *cache_bits);
873 if (histogram_image == NULL || tmp_histos == NULL) {
874 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
875 goto Error;
876 }
877
878 // Build histogram image and symbols from backward references.
879 if (!VP8LGetHistoImageSymbols(width, height, &refs, quality, low_effort,
880 histogram_bits, *cache_bits, histogram_image,
881 tmp_histos, histogram_symbols)) {
882 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
883 goto Error;
884 }
885 // Create Huffman bit lengths and codes for each histogram image.
886 histogram_image_size = histogram_image->size;
887 bit_array_size = 5 * histogram_image_size;
888 huffman_codes = (HuffmanTreeCode*)WebPSafeCalloc(bit_array_size,
889 sizeof(*huffman_codes));
890 // Note: some histogram_image entries may point to tmp_histos[], so the latter
891 // need to outlive the following call to GetHuffBitLengthsAndCodes().
892 if (huffman_codes == NULL ||
893 !GetHuffBitLengthsAndCodes(histogram_image, huffman_codes)) {
894 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
895 goto Error;
896 }
897 // Free combined histograms.
898 VP8LFreeHistogramSet(histogram_image);
899 histogram_image = NULL;
900
901 // Free scratch histograms.
902 VP8LFreeHistogramSet(tmp_histos);
903 tmp_histos = NULL;
904
905 // Color Cache parameters.
906 if (*cache_bits > 0) {
907 VP8LPutBits(bw, 1, 1);
908 VP8LPutBits(bw, *cache_bits, 4);
909 } else {
910 VP8LPutBits(bw, 0, 1);
911 }
912
913 // Huffman image + meta huffman.
914 {
915 const int write_histogram_image = (histogram_image_size > 1);
916 VP8LPutBits(bw, write_histogram_image, 1);
917 if (write_histogram_image) {
918 uint32_t* const histogram_argb =
919 (uint32_t*)WebPSafeMalloc(histogram_image_xysize,
920 sizeof(*histogram_argb));
921 int max_index = 0;
922 uint32_t i;
923 if (histogram_argb == NULL) {
924 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
925 goto Error;
926 }
927 for (i = 0; i < histogram_image_xysize; ++i) {
928 const int symbol_index = histogram_symbols[i] & 0xffff;
929 histogram_argb[i] = (symbol_index << 8);
930 if (symbol_index >= max_index) {
931 max_index = symbol_index + 1;
932 }
933 }
934 histogram_image_size = max_index;
935
936 VP8LPutBits(bw, histogram_bits - 2, 3);
937 err = EncodeImageNoHuffman(bw, histogram_argb, hash_chain, refs_array,
938 VP8LSubSampleSize(width, histogram_bits),
939 VP8LSubSampleSize(height, histogram_bits),
940 quality);
941 WebPSafeFree(histogram_argb);
942 if (err != VP8_ENC_OK) goto Error;
943 }
944 }
945
946 // Store Huffman codes.
947 {
948 int i;
949 int max_tokens = 0;
950 huff_tree = (HuffmanTree*)WebPSafeMalloc(3ULL * CODE_LENGTH_CODES,
951 sizeof(*huff_tree));
952 if (huff_tree == NULL) {
953 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
954 goto Error;
955 }
956 // Find maximum number of symbols for the huffman tree-set.
957 for (i = 0; i < 5 * histogram_image_size; ++i) {
958 HuffmanTreeCode* const codes = &huffman_codes[i];
959 if (max_tokens < codes->num_symbols) {
960 max_tokens = codes->num_symbols;
961 }
962 }
963 tokens = (HuffmanTreeToken*)WebPSafeMalloc(max_tokens,
964 sizeof(*tokens));
965 if (tokens == NULL) {
966 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
967 goto Error;
968 }
969 for (i = 0; i < 5 * histogram_image_size; ++i) {
970 HuffmanTreeCode* const codes = &huffman_codes[i];
971 StoreHuffmanCode(bw, huff_tree, tokens, codes);
972 ClearHuffmanTreeIfOnlyOneSymbol(codes);
973 }
974 }
975
976 *hdr_size = (int)(VP8LBitWriterNumBytes(bw) - init_byte_position);
977 // Store actual literals.
978 err = StoreImageToBitMask(bw, width, histogram_bits, &refs,
979 histogram_symbols, huffman_codes);
980 *data_size =
981 (int)(VP8LBitWriterNumBytes(bw) - init_byte_position - *hdr_size);
982
983 Error:
984 WebPSafeFree(tokens);
985 WebPSafeFree(huff_tree);
986 VP8LFreeHistogramSet(histogram_image);
987 VP8LFreeHistogramSet(tmp_histos);
988 VP8LBackwardRefsClear(&refs);
989 if (huffman_codes != NULL) {
990 WebPSafeFree(huffman_codes->codes);
991 WebPSafeFree(huffman_codes);
992 }
993 WebPSafeFree(histogram_symbols);
994 return err;
995 }
996
997 // -----------------------------------------------------------------------------
998 // Transforms
999
ApplySubtractGreen(VP8LEncoder * const enc,int width,int height,VP8LBitWriter * const bw)1000 static void ApplySubtractGreen(VP8LEncoder* const enc, int width, int height,
1001 VP8LBitWriter* const bw) {
1002 VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
1003 VP8LPutBits(bw, SUBTRACT_GREEN, 2);
1004 VP8LSubtractGreenFromBlueAndRed(enc->argb_, width * height);
1005 }
1006
ApplyPredictFilter(const VP8LEncoder * const enc,int width,int height,int quality,int low_effort,VP8LBitWriter * const bw)1007 static WebPEncodingError ApplyPredictFilter(const VP8LEncoder* const enc,
1008 int width, int height,
1009 int quality, int low_effort,
1010 VP8LBitWriter* const bw) {
1011 const int pred_bits = enc->transform_bits_;
1012 const int transform_width = VP8LSubSampleSize(width, pred_bits);
1013 const int transform_height = VP8LSubSampleSize(height, pred_bits);
1014
1015 VP8LResidualImage(width, height, pred_bits, low_effort, enc->argb_,
1016 enc->argb_scratch_, enc->transform_data_,
1017 enc->config_->exact);
1018 VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
1019 VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2);
1020 assert(pred_bits >= 2);
1021 VP8LPutBits(bw, pred_bits - 2, 3);
1022 return EncodeImageNoHuffman(bw, enc->transform_data_,
1023 (VP8LHashChain*)&enc->hash_chain_,
1024 (VP8LBackwardRefs*)enc->refs_, // cast const away
1025 transform_width, transform_height,
1026 quality);
1027 }
1028
ApplyCrossColorFilter(const VP8LEncoder * const enc,int width,int height,int quality,VP8LBitWriter * const bw)1029 static WebPEncodingError ApplyCrossColorFilter(const VP8LEncoder* const enc,
1030 int width, int height,
1031 int quality,
1032 VP8LBitWriter* const bw) {
1033 const int ccolor_transform_bits = enc->transform_bits_;
1034 const int transform_width = VP8LSubSampleSize(width, ccolor_transform_bits);
1035 const int transform_height = VP8LSubSampleSize(height, ccolor_transform_bits);
1036
1037 VP8LColorSpaceTransform(width, height, ccolor_transform_bits, quality,
1038 enc->argb_, enc->transform_data_);
1039 VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
1040 VP8LPutBits(bw, CROSS_COLOR_TRANSFORM, 2);
1041 assert(ccolor_transform_bits >= 2);
1042 VP8LPutBits(bw, ccolor_transform_bits - 2, 3);
1043 return EncodeImageNoHuffman(bw, enc->transform_data_,
1044 (VP8LHashChain*)&enc->hash_chain_,
1045 (VP8LBackwardRefs*)enc->refs_, // cast const away
1046 transform_width, transform_height,
1047 quality);
1048 }
1049
1050 // -----------------------------------------------------------------------------
1051
WriteRiffHeader(const WebPPicture * const pic,size_t riff_size,size_t vp8l_size)1052 static WebPEncodingError WriteRiffHeader(const WebPPicture* const pic,
1053 size_t riff_size, size_t vp8l_size) {
1054 uint8_t riff[RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE + VP8L_SIGNATURE_SIZE] = {
1055 'R', 'I', 'F', 'F', 0, 0, 0, 0, 'W', 'E', 'B', 'P',
1056 'V', 'P', '8', 'L', 0, 0, 0, 0, VP8L_MAGIC_BYTE,
1057 };
1058 PutLE32(riff + TAG_SIZE, (uint32_t)riff_size);
1059 PutLE32(riff + RIFF_HEADER_SIZE + TAG_SIZE, (uint32_t)vp8l_size);
1060 if (!pic->writer(riff, sizeof(riff), pic)) {
1061 return VP8_ENC_ERROR_BAD_WRITE;
1062 }
1063 return VP8_ENC_OK;
1064 }
1065
WriteImageSize(const WebPPicture * const pic,VP8LBitWriter * const bw)1066 static int WriteImageSize(const WebPPicture* const pic,
1067 VP8LBitWriter* const bw) {
1068 const int width = pic->width - 1;
1069 const int height = pic->height - 1;
1070 assert(width < WEBP_MAX_DIMENSION && height < WEBP_MAX_DIMENSION);
1071
1072 VP8LPutBits(bw, width, VP8L_IMAGE_SIZE_BITS);
1073 VP8LPutBits(bw, height, VP8L_IMAGE_SIZE_BITS);
1074 return !bw->error_;
1075 }
1076
WriteRealAlphaAndVersion(VP8LBitWriter * const bw,int has_alpha)1077 static int WriteRealAlphaAndVersion(VP8LBitWriter* const bw, int has_alpha) {
1078 VP8LPutBits(bw, has_alpha, 1);
1079 VP8LPutBits(bw, VP8L_VERSION, VP8L_VERSION_BITS);
1080 return !bw->error_;
1081 }
1082
WriteImage(const WebPPicture * const pic,VP8LBitWriter * const bw,size_t * const coded_size)1083 static WebPEncodingError WriteImage(const WebPPicture* const pic,
1084 VP8LBitWriter* const bw,
1085 size_t* const coded_size) {
1086 WebPEncodingError err = VP8_ENC_OK;
1087 const uint8_t* const webpll_data = VP8LBitWriterFinish(bw);
1088 const size_t webpll_size = VP8LBitWriterNumBytes(bw);
1089 const size_t vp8l_size = VP8L_SIGNATURE_SIZE + webpll_size;
1090 const size_t pad = vp8l_size & 1;
1091 const size_t riff_size = TAG_SIZE + CHUNK_HEADER_SIZE + vp8l_size + pad;
1092
1093 err = WriteRiffHeader(pic, riff_size, vp8l_size);
1094 if (err != VP8_ENC_OK) goto Error;
1095
1096 if (!pic->writer(webpll_data, webpll_size, pic)) {
1097 err = VP8_ENC_ERROR_BAD_WRITE;
1098 goto Error;
1099 }
1100
1101 if (pad) {
1102 const uint8_t pad_byte[1] = { 0 };
1103 if (!pic->writer(pad_byte, 1, pic)) {
1104 err = VP8_ENC_ERROR_BAD_WRITE;
1105 goto Error;
1106 }
1107 }
1108 *coded_size = CHUNK_HEADER_SIZE + riff_size;
1109 return VP8_ENC_OK;
1110
1111 Error:
1112 return err;
1113 }
1114
1115 // -----------------------------------------------------------------------------
1116
1117 // Allocates the memory for argb (W x H) buffer, 2 rows of context for
1118 // prediction and transform data.
1119 // Flags influencing the memory allocated:
1120 // enc->transform_bits_
1121 // enc->use_predict_, enc->use_cross_color_
AllocateTransformBuffer(VP8LEncoder * const enc,int width,int height)1122 static WebPEncodingError AllocateTransformBuffer(VP8LEncoder* const enc,
1123 int width, int height) {
1124 WebPEncodingError err = VP8_ENC_OK;
1125 if (enc->argb_ == NULL) {
1126 const int tile_size = 1 << enc->transform_bits_;
1127 const uint64_t image_size = width * height;
1128 // Ensure enough size for tiles, as well as for two scanlines and two
1129 // extra pixels for CopyImageWithPrediction.
1130 const uint64_t argb_scratch_size =
1131 enc->use_predict_ ? tile_size * width + width + 2 : 0;
1132 const int transform_data_size =
1133 (enc->use_predict_ || enc->use_cross_color_)
1134 ? VP8LSubSampleSize(width, enc->transform_bits_) *
1135 VP8LSubSampleSize(height, enc->transform_bits_)
1136 : 0;
1137 const uint64_t total_size =
1138 image_size + WEBP_ALIGN_CST +
1139 argb_scratch_size + WEBP_ALIGN_CST +
1140 (uint64_t)transform_data_size;
1141 uint32_t* mem = (uint32_t*)WebPSafeMalloc(total_size, sizeof(*mem));
1142 if (mem == NULL) {
1143 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1144 goto Error;
1145 }
1146 enc->argb_ = mem;
1147 mem = (uint32_t*)WEBP_ALIGN(mem + image_size);
1148 enc->argb_scratch_ = mem;
1149 mem = (uint32_t*)WEBP_ALIGN(mem + argb_scratch_size);
1150 enc->transform_data_ = mem;
1151 enc->current_width_ = width;
1152 }
1153 Error:
1154 return err;
1155 }
1156
ClearTransformBuffer(VP8LEncoder * const enc)1157 static void ClearTransformBuffer(VP8LEncoder* const enc) {
1158 WebPSafeFree(enc->argb_);
1159 enc->argb_ = NULL;
1160 }
1161
MakeInputImageCopy(VP8LEncoder * const enc)1162 static WebPEncodingError MakeInputImageCopy(VP8LEncoder* const enc) {
1163 WebPEncodingError err = VP8_ENC_OK;
1164 const WebPPicture* const picture = enc->pic_;
1165 const int width = picture->width;
1166 const int height = picture->height;
1167 int y;
1168 err = AllocateTransformBuffer(enc, width, height);
1169 if (err != VP8_ENC_OK) return err;
1170 for (y = 0; y < height; ++y) {
1171 memcpy(enc->argb_ + y * width,
1172 picture->argb + y * picture->argb_stride,
1173 width * sizeof(*enc->argb_));
1174 }
1175 assert(enc->current_width_ == width);
1176 return VP8_ENC_OK;
1177 }
1178
1179 // -----------------------------------------------------------------------------
1180
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)1181 static void MapToPalette(const uint32_t palette[], int num_colors,
1182 uint32_t* const last_pix, int* const last_idx,
1183 const uint32_t* src, uint8_t* dst, int width) {
1184 int x;
1185 int prev_idx = *last_idx;
1186 uint32_t prev_pix = *last_pix;
1187 for (x = 0; x < width; ++x) {
1188 const uint32_t pix = src[x];
1189 if (pix != prev_pix) {
1190 int i;
1191 for (i = 0; i < num_colors; ++i) {
1192 if (pix == palette[i]) {
1193 prev_idx = i;
1194 prev_pix = pix;
1195 break;
1196 }
1197 }
1198 }
1199 dst[x] = prev_idx;
1200 }
1201 *last_idx = prev_idx;
1202 *last_pix = prev_pix;
1203 }
1204
1205 // Remap argb values in src[] to packed palettes entries in dst[]
1206 // using 'row' as a temporary buffer of size 'width'.
1207 // We assume that all src[] values have a corresponding entry in the palette.
1208 // Note: src[] can be the same as dst[]
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)1209 static WebPEncodingError ApplyPalette(const uint32_t* src, uint32_t src_stride,
1210 uint32_t* dst, uint32_t dst_stride,
1211 const uint32_t* palette, int palette_size,
1212 int width, int height, int xbits) {
1213 // TODO(skal): this tmp buffer is not needed if VP8LBundleColorMap() can be
1214 // made to work in-place.
1215 uint8_t* const tmp_row = (uint8_t*)WebPSafeMalloc(width, sizeof(*tmp_row));
1216 int i, x, y;
1217 int use_LUT = 1;
1218
1219 if (tmp_row == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY;
1220 for (i = 0; i < palette_size; ++i) {
1221 if ((palette[i] & 0xffff00ffu) != 0) {
1222 use_LUT = 0;
1223 break;
1224 }
1225 }
1226
1227 if (use_LUT) {
1228 uint8_t inv_palette[MAX_PALETTE_SIZE] = { 0 };
1229 for (i = 0; i < palette_size; ++i) {
1230 const int color = (palette[i] >> 8) & 0xff;
1231 inv_palette[color] = i;
1232 }
1233 for (y = 0; y < height; ++y) {
1234 for (x = 0; x < width; ++x) {
1235 const int color = (src[x] >> 8) & 0xff;
1236 tmp_row[x] = inv_palette[color];
1237 }
1238 VP8LBundleColorMap(tmp_row, width, xbits, dst);
1239 src += src_stride;
1240 dst += dst_stride;
1241 }
1242 } else {
1243 // Use 1 pixel cache for ARGB pixels.
1244 uint32_t last_pix = palette[0];
1245 int last_idx = 0;
1246 for (y = 0; y < height; ++y) {
1247 MapToPalette(palette, palette_size, &last_pix, &last_idx,
1248 src, tmp_row, width);
1249 VP8LBundleColorMap(tmp_row, width, xbits, dst);
1250 src += src_stride;
1251 dst += dst_stride;
1252 }
1253 }
1254 WebPSafeFree(tmp_row);
1255 return VP8_ENC_OK;
1256 }
1257
1258 // Note: Expects "enc->palette_" to be set properly.
MapImageFromPalette(VP8LEncoder * const enc,int in_place)1259 static WebPEncodingError MapImageFromPalette(VP8LEncoder* const enc,
1260 int in_place) {
1261 WebPEncodingError err = VP8_ENC_OK;
1262 const WebPPicture* const pic = enc->pic_;
1263 const int width = pic->width;
1264 const int height = pic->height;
1265 const uint32_t* const palette = enc->palette_;
1266 const uint32_t* src = in_place ? enc->argb_ : pic->argb;
1267 const int src_stride = in_place ? enc->current_width_ : pic->argb_stride;
1268 const int palette_size = enc->palette_size_;
1269 int xbits;
1270
1271 // Replace each input pixel by corresponding palette index.
1272 // This is done line by line.
1273 if (palette_size <= 4) {
1274 xbits = (palette_size <= 2) ? 3 : 2;
1275 } else {
1276 xbits = (palette_size <= 16) ? 1 : 0;
1277 }
1278
1279 err = AllocateTransformBuffer(enc, VP8LSubSampleSize(width, xbits), height);
1280 if (err != VP8_ENC_OK) return err;
1281
1282 err = ApplyPalette(src, src_stride,
1283 enc->argb_, enc->current_width_,
1284 palette, palette_size, width, height, xbits);
1285 return err;
1286 }
1287
1288 // Save palette_[] to bitstream.
EncodePalette(VP8LBitWriter * const bw,VP8LEncoder * const enc)1289 static WebPEncodingError EncodePalette(VP8LBitWriter* const bw,
1290 VP8LEncoder* const enc) {
1291 int i;
1292 uint32_t tmp_palette[MAX_PALETTE_SIZE];
1293 const int palette_size = enc->palette_size_;
1294 const uint32_t* const palette = enc->palette_;
1295 VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
1296 VP8LPutBits(bw, COLOR_INDEXING_TRANSFORM, 2);
1297 assert(palette_size >= 1 && palette_size <= MAX_PALETTE_SIZE);
1298 VP8LPutBits(bw, palette_size - 1, 8);
1299 for (i = palette_size - 1; i >= 1; --i) {
1300 tmp_palette[i] = VP8LSubPixels(palette[i], palette[i - 1]);
1301 }
1302 tmp_palette[0] = palette[0];
1303 return EncodeImageNoHuffman(bw, tmp_palette, &enc->hash_chain_, enc->refs_,
1304 palette_size, 1, 20 /* quality */);
1305 }
1306
1307 #ifdef WEBP_EXPERIMENTAL_FEATURES
1308
EncodeDeltaPalettePredictorImage(VP8LBitWriter * const bw,VP8LEncoder * const enc,int quality)1309 static WebPEncodingError EncodeDeltaPalettePredictorImage(
1310 VP8LBitWriter* const bw, VP8LEncoder* const enc, int quality) {
1311 const WebPPicture* const pic = enc->pic_;
1312 const int width = pic->width;
1313 const int height = pic->height;
1314
1315 const int pred_bits = 5;
1316 const int transform_width = VP8LSubSampleSize(width, pred_bits);
1317 const int transform_height = VP8LSubSampleSize(height, pred_bits);
1318 const int pred = 7; // default is Predictor7 (Top/Left Average)
1319 const int tiles_per_row = VP8LSubSampleSize(width, pred_bits);
1320 const int tiles_per_col = VP8LSubSampleSize(height, pred_bits);
1321 uint32_t* predictors;
1322 int tile_x, tile_y;
1323 WebPEncodingError err = VP8_ENC_OK;
1324
1325 predictors = (uint32_t*)WebPSafeMalloc(tiles_per_col * tiles_per_row,
1326 sizeof(*predictors));
1327 if (predictors == NULL) return VP8_ENC_ERROR_OUT_OF_MEMORY;
1328
1329 for (tile_y = 0; tile_y < tiles_per_col; ++tile_y) {
1330 for (tile_x = 0; tile_x < tiles_per_row; ++tile_x) {
1331 predictors[tile_y * tiles_per_row + tile_x] = 0xff000000u | (pred << 8);
1332 }
1333 }
1334
1335 VP8LPutBits(bw, TRANSFORM_PRESENT, 1);
1336 VP8LPutBits(bw, PREDICTOR_TRANSFORM, 2);
1337 VP8LPutBits(bw, pred_bits - 2, 3);
1338 err = EncodeImageNoHuffman(bw, predictors, &enc->hash_chain_,
1339 (VP8LBackwardRefs*)enc->refs_, // cast const away
1340 transform_width, transform_height,
1341 quality);
1342 WebPSafeFree(predictors);
1343 return err;
1344 }
1345
1346 #endif // WEBP_EXPERIMENTAL_FEATURES
1347
1348 // -----------------------------------------------------------------------------
1349 // VP8LEncoder
1350
VP8LEncoderNew(const WebPConfig * const config,const WebPPicture * const picture)1351 static VP8LEncoder* VP8LEncoderNew(const WebPConfig* const config,
1352 const WebPPicture* const picture) {
1353 VP8LEncoder* const enc = (VP8LEncoder*)WebPSafeCalloc(1ULL, sizeof(*enc));
1354 if (enc == NULL) {
1355 WebPEncodingSetError(picture, VP8_ENC_ERROR_OUT_OF_MEMORY);
1356 return NULL;
1357 }
1358 enc->config_ = config;
1359 enc->pic_ = picture;
1360
1361 VP8LEncDspInit();
1362
1363 return enc;
1364 }
1365
VP8LEncoderDelete(VP8LEncoder * enc)1366 static void VP8LEncoderDelete(VP8LEncoder* enc) {
1367 if (enc != NULL) {
1368 VP8LHashChainClear(&enc->hash_chain_);
1369 VP8LBackwardRefsClear(&enc->refs_[0]);
1370 VP8LBackwardRefsClear(&enc->refs_[1]);
1371 ClearTransformBuffer(enc);
1372 WebPSafeFree(enc);
1373 }
1374 }
1375
1376 // -----------------------------------------------------------------------------
1377 // Main call
1378
VP8LEncodeStream(const WebPConfig * const config,const WebPPicture * const picture,VP8LBitWriter * const bw)1379 WebPEncodingError VP8LEncodeStream(const WebPConfig* const config,
1380 const WebPPicture* const picture,
1381 VP8LBitWriter* const bw) {
1382 WebPEncodingError err = VP8_ENC_OK;
1383 const int quality = (int)config->quality;
1384 const int low_effort = (config->method == 0);
1385 const int width = picture->width;
1386 const int height = picture->height;
1387 VP8LEncoder* const enc = VP8LEncoderNew(config, picture);
1388 const size_t byte_position = VP8LBitWriterNumBytes(bw);
1389 int use_near_lossless = 0;
1390 int hdr_size = 0;
1391 int data_size = 0;
1392 int use_delta_palettization = 0;
1393
1394 if (enc == NULL) {
1395 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1396 goto Error;
1397 }
1398
1399 // ---------------------------------------------------------------------------
1400 // Analyze image (entropy, num_palettes etc)
1401
1402 if (!AnalyzeAndInit(enc)) {
1403 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1404 goto Error;
1405 }
1406
1407 // Apply near-lossless preprocessing.
1408 use_near_lossless = !enc->use_palette_ && (config->near_lossless < 100);
1409 if (use_near_lossless) {
1410 if (!VP8ApplyNearLossless(width, height, picture->argb,
1411 config->near_lossless)) {
1412 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1413 goto Error;
1414 }
1415 }
1416
1417 #ifdef WEBP_EXPERIMENTAL_FEATURES
1418 if (config->delta_palettization) {
1419 enc->use_predict_ = 1;
1420 enc->use_cross_color_ = 0;
1421 enc->use_subtract_green_ = 0;
1422 enc->use_palette_ = 1;
1423 err = MakeInputImageCopy(enc);
1424 if (err != VP8_ENC_OK) goto Error;
1425 err = WebPSearchOptimalDeltaPalette(enc);
1426 if (err != VP8_ENC_OK) goto Error;
1427 if (enc->use_palette_) {
1428 err = AllocateTransformBuffer(enc, width, height);
1429 if (err != VP8_ENC_OK) goto Error;
1430 err = EncodeDeltaPalettePredictorImage(bw, enc, quality);
1431 if (err != VP8_ENC_OK) goto Error;
1432 use_delta_palettization = 1;
1433 }
1434 }
1435 #endif // WEBP_EXPERIMENTAL_FEATURES
1436
1437 // Encode palette
1438 if (enc->use_palette_) {
1439 err = EncodePalette(bw, enc);
1440 if (err != VP8_ENC_OK) goto Error;
1441 err = MapImageFromPalette(enc, use_delta_palettization);
1442 if (err != VP8_ENC_OK) goto Error;
1443 }
1444 if (!use_delta_palettization) {
1445 // In case image is not packed.
1446 if (enc->argb_ == NULL) {
1447 err = MakeInputImageCopy(enc);
1448 if (err != VP8_ENC_OK) goto Error;
1449 }
1450
1451 // -------------------------------------------------------------------------
1452 // Apply transforms and write transform data.
1453
1454 if (enc->use_subtract_green_) {
1455 ApplySubtractGreen(enc, enc->current_width_, height, bw);
1456 }
1457
1458 if (enc->use_predict_) {
1459 err = ApplyPredictFilter(enc, enc->current_width_, height, quality,
1460 low_effort, bw);
1461 if (err != VP8_ENC_OK) goto Error;
1462 }
1463
1464 if (enc->use_cross_color_) {
1465 err = ApplyCrossColorFilter(enc, enc->current_width_,
1466 height, quality, bw);
1467 if (err != VP8_ENC_OK) goto Error;
1468 }
1469 }
1470
1471 VP8LPutBits(bw, !TRANSFORM_PRESENT, 1); // No more transforms.
1472
1473 // ---------------------------------------------------------------------------
1474 // Encode and write the transformed image.
1475 err = EncodeImageInternal(bw, enc->argb_, &enc->hash_chain_, enc->refs_,
1476 enc->current_width_, height, quality, low_effort,
1477 &enc->cache_bits_, enc->histo_bits_, byte_position,
1478 &hdr_size, &data_size);
1479 if (err != VP8_ENC_OK) goto Error;
1480
1481 if (picture->stats != NULL) {
1482 WebPAuxStats* const stats = picture->stats;
1483 stats->lossless_features = 0;
1484 if (enc->use_predict_) stats->lossless_features |= 1;
1485 if (enc->use_cross_color_) stats->lossless_features |= 2;
1486 if (enc->use_subtract_green_) stats->lossless_features |= 4;
1487 if (enc->use_palette_) stats->lossless_features |= 8;
1488 stats->histogram_bits = enc->histo_bits_;
1489 stats->transform_bits = enc->transform_bits_;
1490 stats->cache_bits = enc->cache_bits_;
1491 stats->palette_size = enc->palette_size_;
1492 stats->lossless_size = (int)(VP8LBitWriterNumBytes(bw) - byte_position);
1493 stats->lossless_hdr_size = hdr_size;
1494 stats->lossless_data_size = data_size;
1495 }
1496
1497 Error:
1498 VP8LEncoderDelete(enc);
1499 return err;
1500 }
1501
VP8LEncodeImage(const WebPConfig * const config,const WebPPicture * const picture)1502 int VP8LEncodeImage(const WebPConfig* const config,
1503 const WebPPicture* const picture) {
1504 int width, height;
1505 int has_alpha;
1506 size_t coded_size;
1507 int percent = 0;
1508 int initial_size;
1509 WebPEncodingError err = VP8_ENC_OK;
1510 VP8LBitWriter bw;
1511
1512 if (picture == NULL) return 0;
1513
1514 if (config == NULL || picture->argb == NULL) {
1515 err = VP8_ENC_ERROR_NULL_PARAMETER;
1516 WebPEncodingSetError(picture, err);
1517 return 0;
1518 }
1519
1520 width = picture->width;
1521 height = picture->height;
1522 // Initialize BitWriter with size corresponding to 16 bpp to photo images and
1523 // 8 bpp for graphical images.
1524 initial_size = (config->image_hint == WEBP_HINT_GRAPH) ?
1525 width * height : width * height * 2;
1526 if (!VP8LBitWriterInit(&bw, initial_size)) {
1527 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1528 goto Error;
1529 }
1530
1531 if (!WebPReportProgress(picture, 1, &percent)) {
1532 UserAbort:
1533 err = VP8_ENC_ERROR_USER_ABORT;
1534 goto Error;
1535 }
1536 // Reset stats (for pure lossless coding)
1537 if (picture->stats != NULL) {
1538 WebPAuxStats* const stats = picture->stats;
1539 memset(stats, 0, sizeof(*stats));
1540 stats->PSNR[0] = 99.f;
1541 stats->PSNR[1] = 99.f;
1542 stats->PSNR[2] = 99.f;
1543 stats->PSNR[3] = 99.f;
1544 stats->PSNR[4] = 99.f;
1545 }
1546
1547 // Write image size.
1548 if (!WriteImageSize(picture, &bw)) {
1549 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1550 goto Error;
1551 }
1552
1553 has_alpha = WebPPictureHasTransparency(picture);
1554 // Write the non-trivial Alpha flag and lossless version.
1555 if (!WriteRealAlphaAndVersion(&bw, has_alpha)) {
1556 err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1557 goto Error;
1558 }
1559
1560 if (!WebPReportProgress(picture, 5, &percent)) goto UserAbort;
1561
1562 // Encode main image stream.
1563 err = VP8LEncodeStream(config, picture, &bw);
1564 if (err != VP8_ENC_OK) goto Error;
1565
1566 // TODO(skal): have a fine-grained progress report in VP8LEncodeStream().
1567 if (!WebPReportProgress(picture, 90, &percent)) goto UserAbort;
1568
1569 // Finish the RIFF chunk.
1570 err = WriteImage(picture, &bw, &coded_size);
1571 if (err != VP8_ENC_OK) goto Error;
1572
1573 if (!WebPReportProgress(picture, 100, &percent)) goto UserAbort;
1574
1575 // Save size.
1576 if (picture->stats != NULL) {
1577 picture->stats->coded_size += (int)coded_size;
1578 picture->stats->lossless_size = (int)coded_size;
1579 }
1580
1581 if (picture->extra_info != NULL) {
1582 const int mb_w = (width + 15) >> 4;
1583 const int mb_h = (height + 15) >> 4;
1584 memset(picture->extra_info, 0, mb_w * mb_h * sizeof(*picture->extra_info));
1585 }
1586
1587 Error:
1588 if (bw.error_) err = VP8_ENC_ERROR_OUT_OF_MEMORY;
1589 VP8LBitWriterWipeOut(&bw);
1590 if (err != VP8_ENC_OK) {
1591 WebPEncodingSetError(picture, err);
1592 return 0;
1593 }
1594 return 1;
1595 }
1596
1597 //------------------------------------------------------------------------------
1598