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