1// Copyright 2011 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// Alpha-plane compression.
11//
12// Author: Skal (pascal.massimino@gmail.com)
13
14#include <assert.h>
15#include <stdlib.h>
16#include <string.h>
17
18#include "src/enc/vp8i_enc.h"
19#include "src/dsp/dsp.h"
20#include "src/utils/filters_utils.h"
21#include "src/utils/quant_levels_utils.h"
22#include "src/utils/utils.h"
23#include "src/webp/format_constants.h"
24
25// -----------------------------------------------------------------------------
26// Encodes the given alpha data via specified compression method 'method'.
27// The pre-processing (quantization) is performed if 'quality' is less than 100.
28// For such cases, the encoding is lossy. The valid range is [0, 100] for
29// 'quality' and [0, 1] for 'method':
30// 'method = 0' - No compression;
31// 'method = 1' - Use lossless coder on the alpha plane only
32// 'filter' values [0, 4] correspond to prediction modes none, horizontal,
33// vertical & gradient filters. The prediction mode 4 will try all the
34// prediction modes 0 to 3 and pick the best one.
35// 'effort_level': specifies how much effort must be spent to try and reduce
36// the compressed output size. In range 0 (quick) to 6 (slow).
37//
38// 'output' corresponds to the buffer containing compressed alpha data.
39// This buffer is allocated by this method and caller should call
40// WebPSafeFree(*output) when done.
41// 'output_size' corresponds to size of this compressed alpha buffer.
42//
43// Returns 1 on successfully encoding the alpha and
44// 0 if either:
45// invalid quality or method, or
46// memory allocation for the compressed data fails.
47
48#include "src/enc/vp8li_enc.h"
49
50static int EncodeLossless(const uint8_t* const data, int width, int height,
51 int effort_level, // in [0..6] range
52 int use_quality_100, VP8LBitWriter* const bw,
53 WebPAuxStats* const stats) {
54 int ok = 0;
55 WebPConfig config;
56 WebPPicture picture;
57
58 WebPPictureInit(&picture);
59 picture.width = width;
60 picture.height = height;
61 picture.use_argb = 1;
62 picture.stats = stats;
63 if (!WebPPictureAlloc(&picture)) return 0;
64
65 // Transfer the alpha values to the green channel.
66 WebPDispatchAlphaToGreen(data, width, picture.width, picture.height,
67 picture.argb, picture.argb_stride);
68
69 WebPConfigInit(&config);
70 config.lossless = 1;
71 // Enable exact, or it would alter RGB values of transparent alpha, which is
72 // normally OK but not here since we are not encoding the input image but an
73 // internal encoding-related image containing necessary exact information in
74 // RGB channels.
75 config.exact = 1;
76 config.method = effort_level; // impact is very small
77 // Set a low default quality for encoding alpha. Ensure that Alpha quality at
78 // lower methods (3 and below) is less than the threshold for triggering
79 // costly 'BackwardReferencesTraceBackwards'.
80 // If the alpha quality is set to 100 and the method to 6, allow for a high
81 // lossless quality to trigger the cruncher.
82 config.quality =
83 (use_quality_100 && effort_level == 6) ? 100 : 8.f * effort_level;
84 assert(config.quality >= 0 && config.quality <= 100.f);
85
86 // TODO(urvang): Temporary fix to avoid generating images that trigger
87 // a decoder bug related to alpha with color cache.
88 // See: https://code.google.com/p/webp/issues/detail?id=239
89 // Need to re-enable this later.
90 ok = VP8LEncodeStream(&config, &picture, bw, /*use_cache=*/0);
91 WebPPictureFree(&picture);
92 ok = ok && !bw->error_;
93 if (!ok) {
94 VP8LBitWriterWipeOut(bw);
95 return 0;
96 }
97 return 1;
98}
99
100// -----------------------------------------------------------------------------
101
102// Small struct to hold the result of a filter mode compression attempt.
103typedef struct {
104 size_t score;
105 VP8BitWriter bw;
106 WebPAuxStats stats;
107} FilterTrial;
108
109// This function always returns an initialized 'bw' object, even upon error.
110static int EncodeAlphaInternal(const uint8_t* const data, int width, int height,
111 int method, int filter, int reduce_levels,
112 int effort_level, // in [0..6] range
113 uint8_t* const tmp_alpha,
114 FilterTrial* result) {
115 int ok = 0;
116 const uint8_t* alpha_src;
117 WebPFilterFunc filter_func;
118 uint8_t header;
119 const size_t data_size = width * height;
120 const uint8_t* output = NULL;
121 size_t output_size = 0;
122 VP8LBitWriter tmp_bw;
123
124 assert((uint64_t)data_size == (uint64_t)width * height); // as per spec
125 assert(filter >= 0 && filter < WEBP_FILTER_LAST);
126 assert(method >= ALPHA_NO_COMPRESSION);
127 assert(method <= ALPHA_LOSSLESS_COMPRESSION);
128 assert(sizeof(header) == ALPHA_HEADER_LEN);
129
130 filter_func = WebPFilters[filter];
131 if (filter_func != NULL) {
132 filter_func(data, width, height, width, tmp_alpha);
133 alpha_src = tmp_alpha;
134 } else {
135 alpha_src = data;
136 }
137
138 if (method != ALPHA_NO_COMPRESSION) {
139 ok = VP8LBitWriterInit(&tmp_bw, data_size >> 3);
140 ok = ok && EncodeLossless(alpha_src, width, height, effort_level,
141 !reduce_levels, &tmp_bw, &result->stats);
142 if (ok) {
143 output = VP8LBitWriterFinish(&tmp_bw);
144 if (tmp_bw.error_) {
145 VP8LBitWriterWipeOut(&tmp_bw);
146 memset(&result->bw, 0, sizeof(result->bw));
147 return 0;
148 }
149 output_size = VP8LBitWriterNumBytes(&tmp_bw);
150 if (output_size > data_size) {
151 // compressed size is larger than source! Revert to uncompressed mode.
152 method = ALPHA_NO_COMPRESSION;
153 VP8LBitWriterWipeOut(&tmp_bw);
154 }
155 } else {
156 VP8LBitWriterWipeOut(&tmp_bw);
157 memset(&result->bw, 0, sizeof(result->bw));
158 return 0;
159 }
160 }
161
162 if (method == ALPHA_NO_COMPRESSION) {
163 output = alpha_src;
164 output_size = data_size;
165 ok = 1;
166 }
167
168 // Emit final result.
169 header = method | (filter << 2);
170 if (reduce_levels) header |= ALPHA_PREPROCESSED_LEVELS << 4;
171
172 if (!VP8BitWriterInit(&result->bw, ALPHA_HEADER_LEN + output_size)) ok = 0;
173 ok = ok && VP8BitWriterAppend(&result->bw, &header, ALPHA_HEADER_LEN);
174 ok = ok && VP8BitWriterAppend(&result->bw, output, output_size);
175
176 if (method != ALPHA_NO_COMPRESSION) {
177 VP8LBitWriterWipeOut(&tmp_bw);
178 }
179 ok = ok && !result->bw.error_;
180 result->score = VP8BitWriterSize(&result->bw);
181 return ok;
182}
183
184// -----------------------------------------------------------------------------
185
186static int GetNumColors(const uint8_t* data, int width, int height,
187 int stride) {
188 int j;
189 int colors = 0;
190 uint8_t color[256] = { 0 };
191
192 for (j = 0; j < height; ++j) {
193 int i;
194 const uint8_t* const p = data + j * stride;
195 for (i = 0; i < width; ++i) {
196 color[p[i]] = 1;
197 }
198 }
199 for (j = 0; j < 256; ++j) {
200 if (color[j] > 0) ++colors;
201 }
202 return colors;
203}
204
205#define FILTER_TRY_NONE (1 << WEBP_FILTER_NONE)
206#define FILTER_TRY_ALL ((1 << WEBP_FILTER_LAST) - 1)
207
208// Given the input 'filter' option, return an OR'd bit-set of filters to try.
209static uint32_t GetFilterMap(const uint8_t* alpha, int width, int height,
210 int filter, int effort_level) {
211 uint32_t bit_map = 0U;
212 if (filter == WEBP_FILTER_FAST) {
213 // Quick estimate of the best candidate.
214 int try_filter_none = (effort_level > 3);
215 const int kMinColorsForFilterNone = 16;
216 const int kMaxColorsForFilterNone = 192;
217 const int num_colors = GetNumColors(alpha, width, height, width);
218 // For low number of colors, NONE yields better compression.
219 filter = (num_colors <= kMinColorsForFilterNone)
220 ? WEBP_FILTER_NONE
221 : WebPEstimateBestFilter(alpha, width, height, width);
222 bit_map |= 1 << filter;
223 // For large number of colors, try FILTER_NONE in addition to the best
224 // filter as well.
225 if (try_filter_none || num_colors > kMaxColorsForFilterNone) {
226 bit_map |= FILTER_TRY_NONE;
227 }
228 } else if (filter == WEBP_FILTER_NONE) {
229 bit_map = FILTER_TRY_NONE;
230 } else { // WEBP_FILTER_BEST -> try all
231 bit_map = FILTER_TRY_ALL;
232 }
233 return bit_map;
234}
235
236static void InitFilterTrial(FilterTrial* const score) {
237 score->score = (size_t)~0U;
238 VP8BitWriterInit(&score->bw, 0);
239}
240
241static int ApplyFiltersAndEncode(const uint8_t* alpha, int width, int height,
242 size_t data_size, int method, int filter,
243 int reduce_levels, int effort_level,
244 uint8_t** const output,
245 size_t* const output_size,
246 WebPAuxStats* const stats) {
247 int ok = 1;
248 FilterTrial best;
249 uint32_t try_map =
250 GetFilterMap(alpha, width, height, filter, effort_level);
251 InitFilterTrial(&best);
252
253 if (try_map != FILTER_TRY_NONE) {
254 uint8_t* filtered_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size);
255 if (filtered_alpha == NULL) return 0;
256
257 for (filter = WEBP_FILTER_NONE; ok && try_map; ++filter, try_map >>= 1) {
258 if (try_map & 1) {
259 FilterTrial trial;
260 ok = EncodeAlphaInternal(alpha, width, height, method, filter,
261 reduce_levels, effort_level, filtered_alpha,
262 &trial);
263 if (ok && trial.score < best.score) {
264 VP8BitWriterWipeOut(&best.bw);
265 best = trial;
266 } else {
267 VP8BitWriterWipeOut(&trial.bw);
268 }
269 }
270 }
271 WebPSafeFree(filtered_alpha);
272 } else {
273 ok = EncodeAlphaInternal(alpha, width, height, method, WEBP_FILTER_NONE,
274 reduce_levels, effort_level, NULL, &best);
275 }
276 if (ok) {
277#if !defined(WEBP_DISABLE_STATS)
278 if (stats != NULL) {
279 stats->lossless_features = best.stats.lossless_features;
280 stats->histogram_bits = best.stats.histogram_bits;
281 stats->transform_bits = best.stats.transform_bits;
282 stats->cache_bits = best.stats.cache_bits;
283 stats->palette_size = best.stats.palette_size;
284 stats->lossless_size = best.stats.lossless_size;
285 stats->lossless_hdr_size = best.stats.lossless_hdr_size;
286 stats->lossless_data_size = best.stats.lossless_data_size;
287 }
288#else
289 (void)stats;
290#endif
291 *output_size = VP8BitWriterSize(&best.bw);
292 *output = VP8BitWriterBuf(&best.bw);
293 } else {
294 VP8BitWriterWipeOut(&best.bw);
295 }
296 return ok;
297}
298
299static int EncodeAlpha(VP8Encoder* const enc,
300 int quality, int method, int filter,
301 int effort_level,
302 uint8_t** const output, size_t* const output_size) {
303 const WebPPicture* const pic = enc->pic_;
304 const int width = pic->width;
305 const int height = pic->height;
306
307 uint8_t* quant_alpha = NULL;
308 const size_t data_size = width * height;
309 uint64_t sse = 0;
310 int ok = 1;
311 const int reduce_levels = (quality < 100);
312
313 // quick correctness checks
314 assert((uint64_t)data_size == (uint64_t)width * height); // as per spec
315 assert(enc != NULL && pic != NULL && pic->a != NULL);
316 assert(output != NULL && output_size != NULL);
317 assert(width > 0 && height > 0);
318 assert(pic->a_stride >= width);
319 assert(filter >= WEBP_FILTER_NONE && filter <= WEBP_FILTER_FAST);
320
321 if (quality < 0 || quality > 100) {
322 return WebPEncodingSetError(pic, VP8_ENC_ERROR_INVALID_CONFIGURATION);
323 }
324
325 if (method < ALPHA_NO_COMPRESSION || method > ALPHA_LOSSLESS_COMPRESSION) {
326 return WebPEncodingSetError(pic, VP8_ENC_ERROR_INVALID_CONFIGURATION);
327 }
328
329 if (method == ALPHA_NO_COMPRESSION) {
330 // Don't filter, as filtering will make no impact on compressed size.
331 filter = WEBP_FILTER_NONE;
332 }
333
334 quant_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size);
335 if (quant_alpha == NULL) {
336 return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY);
337 }
338
339 // Extract alpha data (width x height) from raw_data (stride x height).
340 WebPCopyPlane(pic->a, pic->a_stride, quant_alpha, width, width, height);
341
342 if (reduce_levels) { // No Quantization required for 'quality = 100'.
343 // 16 alpha levels gives quite a low MSE w.r.t original alpha plane hence
344 // mapped to moderate quality 70. Hence Quality:[0, 70] -> Levels:[2, 16]
345 // and Quality:]70, 100] -> Levels:]16, 256].
346 const int alpha_levels = (quality <= 70) ? (2 + quality / 5)
347 : (16 + (quality - 70) * 8);
348 ok = QuantizeLevels(quant_alpha, width, height, alpha_levels, &sse);
349 }
350
351 if (ok) {
352 VP8FiltersInit();
353 ok = ApplyFiltersAndEncode(quant_alpha, width, height, data_size, method,
354 filter, reduce_levels, effort_level, output,
355 output_size, pic->stats);
356 if (!ok) {
357 WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY); // imprecise
358 }
359#if !defined(WEBP_DISABLE_STATS)
360 if (pic->stats != NULL) { // need stats?
361 pic->stats->coded_size += (int)(*output_size);
362 enc->sse_[3] = sse;
363 }
364#endif
365 }
366
367 WebPSafeFree(quant_alpha);
368 return ok;
369}
370
371//------------------------------------------------------------------------------
372// Main calls
373
374static int CompressAlphaJob(void* arg1, void* unused) {
375 VP8Encoder* const enc = (VP8Encoder*)arg1;
376 const WebPConfig* config = enc->config_;
377 uint8_t* alpha_data = NULL;
378 size_t alpha_size = 0;
379 const int effort_level = config->method; // maps to [0..6]
380 const WEBP_FILTER_TYPE filter =
381 (config->alpha_filtering == 0) ? WEBP_FILTER_NONE :
382 (config->alpha_filtering == 1) ? WEBP_FILTER_FAST :
383 WEBP_FILTER_BEST;
384 if (!EncodeAlpha(enc, config->alpha_quality, config->alpha_compression,
385 filter, effort_level, &alpha_data, &alpha_size)) {
386 return 0;
387 }
388 if (alpha_size != (uint32_t)alpha_size) { // Soundness check.
389 WebPSafeFree(alpha_data);
390 return 0;
391 }
392 enc->alpha_data_size_ = (uint32_t)alpha_size;
393 enc->alpha_data_ = alpha_data;
394 (void)unused;
395 return 1;
396}
397
398void VP8EncInitAlpha(VP8Encoder* const enc) {
399 WebPInitAlphaProcessing();
400 enc->has_alpha_ = WebPPictureHasTransparency(enc->pic_);
401 enc->alpha_data_ = NULL;
402 enc->alpha_data_size_ = 0;
403 if (enc->thread_level_ > 0) {
404 WebPWorker* const worker = &enc->alpha_worker_;
405 WebPGetWorkerInterface()->Init(worker);
406 worker->data1 = enc;
407 worker->data2 = NULL;
408 worker->hook = CompressAlphaJob;
409 }
410}
411
412int VP8EncStartAlpha(VP8Encoder* const enc) {
413 if (enc->has_alpha_) {
414 if (enc->thread_level_ > 0) {
415 WebPWorker* const worker = &enc->alpha_worker_;
416 // Makes sure worker is good to go.
417 if (!WebPGetWorkerInterface()->Reset(worker)) {
418 return WebPEncodingSetError(enc->pic_, VP8_ENC_ERROR_OUT_OF_MEMORY);
419 }
420 WebPGetWorkerInterface()->Launch(worker);
421 return 1;
422 } else {
423 return CompressAlphaJob(enc, NULL); // just do the job right away
424 }
425 }
426 return 1;
427}
428
429int VP8EncFinishAlpha(VP8Encoder* const enc) {
430 if (enc->has_alpha_) {
431 if (enc->thread_level_ > 0) {
432 WebPWorker* const worker = &enc->alpha_worker_;
433 if (!WebPGetWorkerInterface()->Sync(worker)) return 0; // error
434 }
435 }
436 return WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
437}
438
439int VP8EncDeleteAlpha(VP8Encoder* const enc) {
440 int ok = 1;
441 if (enc->thread_level_ > 0) {
442 WebPWorker* const worker = &enc->alpha_worker_;
443 // finish anything left in flight
444 ok = WebPGetWorkerInterface()->Sync(worker);
445 // still need to end the worker, even if !ok
446 WebPGetWorkerInterface()->End(worker);
447 }
448 WebPSafeFree(enc->alpha_data_);
449 enc->alpha_data_ = NULL;
450 enc->alpha_data_size_ = 0;
451 enc->has_alpha_ = 0;
452 return ok;
453}
454