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 "./vp8i_enc.h"
18#include "../dsp/dsp.h"
19#include "../utils/filters_utils.h"
20#include "../utils/quant_levels_utils.h"
21#include "../utils/utils.h"
22#include "../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 "../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 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 config.quality = 8.f * effort_level;
80 assert(config.quality >= 0 && config.quality <= 100.f);
81
82 // TODO(urvang): Temporary fix to avoid generating images that trigger
83 // a decoder bug related to alpha with color cache.
84 // See: https://code.google.com/p/webp/issues/detail?id=239
85 // Need to re-enable this later.
86 ok = (VP8LEncodeStream(&config, &picture, bw, 0 /*use_cache*/) == VP8_ENC_OK);
87 WebPPictureFree(&picture);
88 ok = ok && !bw->error_;
89 if (!ok) {
90 VP8LBitWriterWipeOut(bw);
91 return 0;
92 }
93 return 1;
94}
95
96// -----------------------------------------------------------------------------
97
98// Small struct to hold the result of a filter mode compression attempt.
99typedef struct {
100 size_t score;
101 VP8BitWriter bw;
102 WebPAuxStats stats;
103} FilterTrial;
104
105// This function always returns an initialized 'bw' object, even upon error.
106static int EncodeAlphaInternal(const uint8_t* const data, int width, int height,
107 int method, int filter, int reduce_levels,
108 int effort_level, // in [0..6] range
109 uint8_t* const tmp_alpha,
110 FilterTrial* result) {
111 int ok = 0;
112 const uint8_t* alpha_src;
113 WebPFilterFunc filter_func;
114 uint8_t header;
115 const size_t data_size = width * height;
116 const uint8_t* output = NULL;
117 size_t output_size = 0;
118 VP8LBitWriter tmp_bw;
119
120 assert((uint64_t)data_size == (uint64_t)width * height); // as per spec
121 assert(filter >= 0 && filter < WEBP_FILTER_LAST);
122 assert(method >= ALPHA_NO_COMPRESSION);
123 assert(method <= ALPHA_LOSSLESS_COMPRESSION);
124 assert(sizeof(header) == ALPHA_HEADER_LEN);
125
126 filter_func = WebPFilters[filter];
127 if (filter_func != NULL) {
128 filter_func(data, width, height, width, tmp_alpha);
129 alpha_src = tmp_alpha;
130 } else {
131 alpha_src = data;
132 }
133
134 if (method != ALPHA_NO_COMPRESSION) {
135 ok = VP8LBitWriterInit(&tmp_bw, data_size >> 3);
136 ok = ok && EncodeLossless(alpha_src, width, height, effort_level,
137 &tmp_bw, &result->stats);
138 if (ok) {
139 output = VP8LBitWriterFinish(&tmp_bw);
140 output_size = VP8LBitWriterNumBytes(&tmp_bw);
141 if (output_size > data_size) {
142 // compressed size is larger than source! Revert to uncompressed mode.
143 method = ALPHA_NO_COMPRESSION;
144 VP8LBitWriterWipeOut(&tmp_bw);
145 }
146 } else {
147 VP8LBitWriterWipeOut(&tmp_bw);
148 return 0;
149 }
150 }
151
152 if (method == ALPHA_NO_COMPRESSION) {
153 output = alpha_src;
154 output_size = data_size;
155 ok = 1;
156 }
157
158 // Emit final result.
159 header = method | (filter << 2);
160 if (reduce_levels) header |= ALPHA_PREPROCESSED_LEVELS << 4;
161
162 VP8BitWriterInit(&result->bw, ALPHA_HEADER_LEN + output_size);
163 ok = ok && VP8BitWriterAppend(&result->bw, &header, ALPHA_HEADER_LEN);
164 ok = ok && VP8BitWriterAppend(&result->bw, output, output_size);
165
166 if (method != ALPHA_NO_COMPRESSION) {
167 VP8LBitWriterWipeOut(&tmp_bw);
168 }
169 ok = ok && !result->bw.error_;
170 result->score = VP8BitWriterSize(&result->bw);
171 return ok;
172}
173
174// -----------------------------------------------------------------------------
175
176static int GetNumColors(const uint8_t* data, int width, int height,
177 int stride) {
178 int j;
179 int colors = 0;
180 uint8_t color[256] = { 0 };
181
182 for (j = 0; j < height; ++j) {
183 int i;
184 const uint8_t* const p = data + j * stride;
185 for (i = 0; i < width; ++i) {
186 color[p[i]] = 1;
187 }
188 }
189 for (j = 0; j < 256; ++j) {
190 if (color[j] > 0) ++colors;
191 }
192 return colors;
193}
194
195#define FILTER_TRY_NONE (1 << WEBP_FILTER_NONE)
196#define FILTER_TRY_ALL ((1 << WEBP_FILTER_LAST) - 1)
197
198// Given the input 'filter' option, return an OR'd bit-set of filters to try.
199static uint32_t GetFilterMap(const uint8_t* alpha, int width, int height,
200 int filter, int effort_level) {
201 uint32_t bit_map = 0U;
202 if (filter == WEBP_FILTER_FAST) {
203 // Quick estimate of the best candidate.
204 int try_filter_none = (effort_level > 3);
205 const int kMinColorsForFilterNone = 16;
206 const int kMaxColorsForFilterNone = 192;
207 const int num_colors = GetNumColors(alpha, width, height, width);
208 // For low number of colors, NONE yields better compression.
209 filter = (num_colors <= kMinColorsForFilterNone)
210 ? WEBP_FILTER_NONE
211 : WebPEstimateBestFilter(alpha, width, height, width);
212 bit_map |= 1 << filter;
213 // For large number of colors, try FILTER_NONE in addition to the best
214 // filter as well.
215 if (try_filter_none || num_colors > kMaxColorsForFilterNone) {
216 bit_map |= FILTER_TRY_NONE;
217 }
218 } else if (filter == WEBP_FILTER_NONE) {
219 bit_map = FILTER_TRY_NONE;
220 } else { // WEBP_FILTER_BEST -> try all
221 bit_map = FILTER_TRY_ALL;
222 }
223 return bit_map;
224}
225
226static void InitFilterTrial(FilterTrial* const score) {
227 score->score = (size_t)~0U;
228 VP8BitWriterInit(&score->bw, 0);
229}
230
231static int ApplyFiltersAndEncode(const uint8_t* alpha, int width, int height,
232 size_t data_size, int method, int filter,
233 int reduce_levels, int effort_level,
234 uint8_t** const output,
235 size_t* const output_size,
236 WebPAuxStats* const stats) {
237 int ok = 1;
238 FilterTrial best;
239 uint32_t try_map =
240 GetFilterMap(alpha, width, height, filter, effort_level);
241 InitFilterTrial(&best);
242
243 if (try_map != FILTER_TRY_NONE) {
244 uint8_t* filtered_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size);
245 if (filtered_alpha == NULL) return 0;
246
247 for (filter = WEBP_FILTER_NONE; ok && try_map; ++filter, try_map >>= 1) {
248 if (try_map & 1) {
249 FilterTrial trial;
250 ok = EncodeAlphaInternal(alpha, width, height, method, filter,
251 reduce_levels, effort_level, filtered_alpha,
252 &trial);
253 if (ok && trial.score < best.score) {
254 VP8BitWriterWipeOut(&best.bw);
255 best = trial;
256 } else {
257 VP8BitWriterWipeOut(&trial.bw);
258 }
259 }
260 }
261 WebPSafeFree(filtered_alpha);
262 } else {
263 ok = EncodeAlphaInternal(alpha, width, height, method, WEBP_FILTER_NONE,
264 reduce_levels, effort_level, NULL, &best);
265 }
266 if (ok) {
267 if (stats != NULL) {
268 stats->lossless_features = best.stats.lossless_features;
269 stats->histogram_bits = best.stats.histogram_bits;
270 stats->transform_bits = best.stats.transform_bits;
271 stats->cache_bits = best.stats.cache_bits;
272 stats->palette_size = best.stats.palette_size;
273 stats->lossless_size = best.stats.lossless_size;
274 stats->lossless_hdr_size = best.stats.lossless_hdr_size;
275 stats->lossless_data_size = best.stats.lossless_data_size;
276 }
277 *output_size = VP8BitWriterSize(&best.bw);
278 *output = VP8BitWriterBuf(&best.bw);
279 } else {
280 VP8BitWriterWipeOut(&best.bw);
281 }
282 return ok;
283}
284
285static int EncodeAlpha(VP8Encoder* const enc,
286 int quality, int method, int filter,
287 int effort_level,
288 uint8_t** const output, size_t* const output_size) {
289 const WebPPicture* const pic = enc->pic_;
290 const int width = pic->width;
291 const int height = pic->height;
292
293 uint8_t* quant_alpha = NULL;
294 const size_t data_size = width * height;
295 uint64_t sse = 0;
296 int ok = 1;
297 const int reduce_levels = (quality < 100);
298
299 // quick sanity checks
300 assert((uint64_t)data_size == (uint64_t)width * height); // as per spec
301 assert(enc != NULL && pic != NULL && pic->a != NULL);
302 assert(output != NULL && output_size != NULL);
303 assert(width > 0 && height > 0);
304 assert(pic->a_stride >= width);
305 assert(filter >= WEBP_FILTER_NONE && filter <= WEBP_FILTER_FAST);
306
307 if (quality < 0 || quality > 100) {
308 return 0;
309 }
310
311 if (method < ALPHA_NO_COMPRESSION || method > ALPHA_LOSSLESS_COMPRESSION) {
312 return 0;
313 }
314
315 if (method == ALPHA_NO_COMPRESSION) {
316 // Don't filter, as filtering will make no impact on compressed size.
317 filter = WEBP_FILTER_NONE;
318 }
319
320 quant_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size);
321 if (quant_alpha == NULL) {
322 return 0;
323 }
324
325 // Extract alpha data (width x height) from raw_data (stride x height).
326 WebPCopyPlane(pic->a, pic->a_stride, quant_alpha, width, width, height);
327
328 if (reduce_levels) { // No Quantization required for 'quality = 100'.
329 // 16 alpha levels gives quite a low MSE w.r.t original alpha plane hence
330 // mapped to moderate quality 70. Hence Quality:[0, 70] -> Levels:[2, 16]
331 // and Quality:]70, 100] -> Levels:]16, 256].
332 const int alpha_levels = (quality <= 70) ? (2 + quality / 5)
333 : (16 + (quality - 70) * 8);
334 ok = QuantizeLevels(quant_alpha, width, height, alpha_levels, &sse);
335 }
336
337 if (ok) {
338 VP8FiltersInit();
339 ok = ApplyFiltersAndEncode(quant_alpha, width, height, data_size, method,
340 filter, reduce_levels, effort_level, output,
341 output_size, pic->stats);
342 if (pic->stats != NULL) { // need stats?
343 pic->stats->coded_size += (int)(*output_size);
344 enc->sse_[3] = sse;
345 }
346 }
347
348 WebPSafeFree(quant_alpha);
349 return ok;
350}
351
352//------------------------------------------------------------------------------
353// Main calls
354
355static int CompressAlphaJob(VP8Encoder* const enc, void* dummy) {
356 const WebPConfig* config = enc->config_;
357 uint8_t* alpha_data = NULL;
358 size_t alpha_size = 0;
359 const int effort_level = config->method; // maps to [0..6]
360 const WEBP_FILTER_TYPE filter =
361 (config->alpha_filtering == 0) ? WEBP_FILTER_NONE :
362 (config->alpha_filtering == 1) ? WEBP_FILTER_FAST :
363 WEBP_FILTER_BEST;
364 if (!EncodeAlpha(enc, config->alpha_quality, config->alpha_compression,
365 filter, effort_level, &alpha_data, &alpha_size)) {
366 return 0;
367 }
368 if (alpha_size != (uint32_t)alpha_size) { // Sanity check.
369 WebPSafeFree(alpha_data);
370 return 0;
371 }
372 enc->alpha_data_size_ = (uint32_t)alpha_size;
373 enc->alpha_data_ = alpha_data;
374 (void)dummy;
375 return 1;
376}
377
378void VP8EncInitAlpha(VP8Encoder* const enc) {
379 WebPInitAlphaProcessing();
380 enc->has_alpha_ = WebPPictureHasTransparency(enc->pic_);
381 enc->alpha_data_ = NULL;
382 enc->alpha_data_size_ = 0;
383 if (enc->thread_level_ > 0) {
384 WebPWorker* const worker = &enc->alpha_worker_;
385 WebPGetWorkerInterface()->Init(worker);
386 worker->data1 = enc;
387 worker->data2 = NULL;
388 worker->hook = (WebPWorkerHook)CompressAlphaJob;
389 }
390}
391
392int VP8EncStartAlpha(VP8Encoder* const enc) {
393 if (enc->has_alpha_) {
394 if (enc->thread_level_ > 0) {
395 WebPWorker* const worker = &enc->alpha_worker_;
396 // Makes sure worker is good to go.
397 if (!WebPGetWorkerInterface()->Reset(worker)) {
398 return 0;
399 }
400 WebPGetWorkerInterface()->Launch(worker);
401 return 1;
402 } else {
403 return CompressAlphaJob(enc, NULL); // just do the job right away
404 }
405 }
406 return 1;
407}
408
409int VP8EncFinishAlpha(VP8Encoder* const enc) {
410 if (enc->has_alpha_) {
411 if (enc->thread_level_ > 0) {
412 WebPWorker* const worker = &enc->alpha_worker_;
413 if (!WebPGetWorkerInterface()->Sync(worker)) return 0; // error
414 }
415 }
416 return WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
417}
418
419int VP8EncDeleteAlpha(VP8Encoder* const enc) {
420 int ok = 1;
421 if (enc->thread_level_ > 0) {
422 WebPWorker* const worker = &enc->alpha_worker_;
423 // finish anything left in flight
424 ok = WebPGetWorkerInterface()->Sync(worker);
425 // still need to end the worker, even if !ok
426 WebPGetWorkerInterface()->End(worker);
427 }
428 WebPSafeFree(enc->alpha_data_);
429 enc->alpha_data_ = NULL;
430 enc->alpha_data_size_ = 0;
431 enc->has_alpha_ = 0;
432 return ok;
433}
434