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