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 "./vp8enci.h"
18#include "../utils/filters.h"
19#include "../utils/quant_levels.h"
20#include "../webp/format_constants.h"
21
22#if defined(__cplusplus) || defined(c_plusplus)
23extern "C" {
24#endif
25
26// -----------------------------------------------------------------------------
27// Encodes the given alpha data via specified compression method 'method'.
28// The pre-processing (quantization) is performed if 'quality' is less than 100.
29// For such cases, the encoding is lossy. The valid range is [0, 100] for
30// 'quality' and [0, 1] for 'method':
31//   'method = 0' - No compression;
32//   'method = 1' - Use lossless coder on the alpha plane only
33// 'filter' values [0, 4] correspond to prediction modes none, horizontal,
34// vertical & gradient filters. The prediction mode 4 will try all the
35// prediction modes 0 to 3 and pick the best one.
36// 'effort_level': specifies how much effort must be spent to try and reduce
37//  the compressed output size. In range 0 (quick) to 6 (slow).
38//
39// 'output' corresponds to the buffer containing compressed alpha data.
40//          This buffer is allocated by this method and caller should call
41//          free(*output) when done.
42// 'output_size' corresponds to size of this compressed alpha buffer.
43//
44// Returns 1 on successfully encoding the alpha and
45//         0 if either:
46//           invalid quality or method, or
47//           memory allocation for the compressed data fails.
48
49#include "../enc/vp8li.h"
50
51static int EncodeLossless(const uint8_t* const data, int width, int height,
52                          int effort_level,  // in [0..6] range
53                          VP8BitWriter* const bw,
54                          WebPAuxStats* const stats) {
55  int ok = 0;
56  WebPConfig config;
57  WebPPicture picture;
58  VP8LBitWriter tmp_bw;
59
60  WebPPictureInit(&picture);
61  picture.width = width;
62  picture.height = height;
63  picture.use_argb = 1;
64  picture.stats = stats;
65  if (!WebPPictureAlloc(&picture)) return 0;
66
67  // Transfer the alpha values to the green channel.
68  {
69    int i, j;
70    uint32_t* dst = picture.argb;
71    const uint8_t* src = data;
72    for (j = 0; j < picture.height; ++j) {
73      for (i = 0; i < picture.width; ++i) {
74        dst[i] = (src[i] << 8) | 0xff000000u;
75      }
76      src += width;
77      dst += picture.argb_stride;
78    }
79  }
80
81  WebPConfigInit(&config);
82  config.lossless = 1;
83  config.method = effort_level;  // impact is very small
84  // Set a moderate default quality setting for alpha.
85  config.quality = 10.f * effort_level;
86  assert(config.quality >= 0 && config.quality <= 100.f);
87
88  ok = VP8LBitWriterInit(&tmp_bw, (width * height) >> 3);
89  ok = ok && (VP8LEncodeStream(&config, &picture, &tmp_bw) == VP8_ENC_OK);
90  WebPPictureFree(&picture);
91  if (ok) {
92    const uint8_t* const buffer = VP8LBitWriterFinish(&tmp_bw);
93    const size_t buffer_size = VP8LBitWriterNumBytes(&tmp_bw);
94    VP8BitWriterAppend(bw, buffer, buffer_size);
95  }
96  VP8LBitWriterDestroy(&tmp_bw);
97  return ok && !bw->error_;
98}
99
100// -----------------------------------------------------------------------------
101
102static int EncodeAlphaInternal(const uint8_t* const data, int width, int height,
103                               int method, int filter, int reduce_levels,
104                               int effort_level,  // in [0..6] range
105                               uint8_t* const tmp_alpha,
106                               VP8BitWriter* const bw,
107                               WebPAuxStats* const stats) {
108  int ok = 0;
109  const uint8_t* alpha_src;
110  WebPFilterFunc filter_func;
111  uint8_t header;
112  size_t expected_size;
113  const size_t data_size = width * height;
114
115  assert((uint64_t)data_size == (uint64_t)width * height);  // as per spec
116  assert(filter >= 0 && filter < WEBP_FILTER_LAST);
117  assert(method >= ALPHA_NO_COMPRESSION);
118  assert(method <= ALPHA_LOSSLESS_COMPRESSION);
119  assert(sizeof(header) == ALPHA_HEADER_LEN);
120  // TODO(skal): have a common function and #define's to validate alpha params.
121
122  expected_size =
123      (method == ALPHA_NO_COMPRESSION) ? (ALPHA_HEADER_LEN + data_size)
124                                       : (data_size >> 5);
125  header = method | (filter << 2);
126  if (reduce_levels) header |= ALPHA_PREPROCESSED_LEVELS << 4;
127
128  VP8BitWriterInit(bw, expected_size);
129  VP8BitWriterAppend(bw, &header, ALPHA_HEADER_LEN);
130
131  filter_func = WebPFilters[filter];
132  if (filter_func != NULL) {
133    filter_func(data, width, height, width, tmp_alpha);
134    alpha_src = tmp_alpha;
135  }  else {
136    alpha_src = data;
137  }
138
139  if (method == ALPHA_NO_COMPRESSION) {
140    ok = VP8BitWriterAppend(bw, alpha_src, width * height);
141    ok = ok && !bw->error_;
142  } else {
143    ok = EncodeLossless(alpha_src, width, height, effort_level, bw, stats);
144    VP8BitWriterFinish(bw);
145  }
146  return ok;
147}
148
149// -----------------------------------------------------------------------------
150
151// TODO(skal): move to dsp/ ?
152static void CopyPlane(const uint8_t* src, int src_stride,
153                      uint8_t* dst, int dst_stride, int width, int height) {
154  while (height-- > 0) {
155    memcpy(dst, src, width);
156    src += src_stride;
157    dst += dst_stride;
158  }
159}
160
161static int GetNumColors(const uint8_t* data, int width, int height,
162                        int stride) {
163  int j;
164  int colors = 0;
165  uint8_t color[256] = { 0 };
166
167  for (j = 0; j < height; ++j) {
168    int i;
169    const uint8_t* const p = data + j * stride;
170    for (i = 0; i < width; ++i) {
171      color[p[i]] = 1;
172    }
173  }
174  for (j = 0; j < 256; ++j) {
175    if (color[j] > 0) ++colors;
176  }
177  return colors;
178}
179
180static int EncodeAlpha(VP8Encoder* const enc,
181                       int quality, int method, int filter,
182                       int effort_level,
183                       uint8_t** const output, size_t* const output_size) {
184  const WebPPicture* const pic = enc->pic_;
185  const int width = pic->width;
186  const int height = pic->height;
187
188  uint8_t* quant_alpha = NULL;
189  const size_t data_size = width * height;
190  uint64_t sse = 0;
191  int ok = 1;
192  const int reduce_levels = (quality < 100);
193
194  // quick sanity checks
195  assert((uint64_t)data_size == (uint64_t)width * height);  // as per spec
196  assert(enc != NULL && pic != NULL && pic->a != NULL);
197  assert(output != NULL && output_size != NULL);
198  assert(width > 0 && height > 0);
199  assert(pic->a_stride >= width);
200  assert(filter >= WEBP_FILTER_NONE && filter <= WEBP_FILTER_FAST);
201
202  if (quality < 0 || quality > 100) {
203    return 0;
204  }
205
206  if (method < ALPHA_NO_COMPRESSION || method > ALPHA_LOSSLESS_COMPRESSION) {
207    return 0;
208  }
209
210  quant_alpha = (uint8_t*)malloc(data_size);
211  if (quant_alpha == NULL) {
212    return 0;
213  }
214
215  // Extract alpha data (width x height) from raw_data (stride x height).
216  CopyPlane(pic->a, pic->a_stride, quant_alpha, width, width, height);
217
218  if (reduce_levels) {  // No Quantization required for 'quality = 100'.
219    // 16 alpha levels gives quite a low MSE w.r.t original alpha plane hence
220    // mapped to moderate quality 70. Hence Quality:[0, 70] -> Levels:[2, 16]
221    // and Quality:]70, 100] -> Levels:]16, 256].
222    const int alpha_levels = (quality <= 70) ? (2 + quality / 5)
223                                             : (16 + (quality - 70) * 8);
224    ok = QuantizeLevels(quant_alpha, width, height, alpha_levels, &sse);
225  }
226
227  if (ok) {
228    VP8BitWriter bw;
229    int test_filter;
230    uint8_t* filtered_alpha = NULL;
231    int try_filter_none = (effort_level > 3);
232
233    if (filter == WEBP_FILTER_FAST) {  // Quick estimate of the best candidate.
234      const int kMinColorsForFilterNone = 16;
235      const int kMaxColorsForFilterNone = 192;
236      const int num_colors = GetNumColors(quant_alpha, width, height, width);
237      // For low number of colors, NONE yeilds better compression.
238      filter = (num_colors <= kMinColorsForFilterNone) ? WEBP_FILTER_NONE :
239               EstimateBestFilter(quant_alpha, width, height, width);
240      // For large number of colors, try FILTER_NONE in addition to the best
241      // filter as well.
242      if (num_colors > kMaxColorsForFilterNone) {
243        try_filter_none = 1;
244      }
245    }
246
247    // Test for WEBP_FILTER_NONE for higher effort levels.
248    if (try_filter_none || filter == WEBP_FILTER_NONE) {
249      ok = EncodeAlphaInternal(quant_alpha, width, height,
250                               method, WEBP_FILTER_NONE, reduce_levels,
251                               effort_level, NULL, &bw, pic->stats);
252
253      if (!ok) {
254        VP8BitWriterWipeOut(&bw);
255        goto End;
256      }
257    }
258    // Stop?
259    if (filter == WEBP_FILTER_NONE) {
260      goto Ok;
261    }
262
263    filtered_alpha = (uint8_t*)malloc(data_size);
264    ok = (filtered_alpha != NULL);
265    if (!ok) {
266      goto End;
267    }
268
269    // Try the other mode(s).
270    {
271      WebPAuxStats best_stats;
272      size_t best_score = try_filter_none ?
273                          VP8BitWriterSize(&bw) : (size_t)~0U;
274      int wipe_tmp_bw = try_filter_none;
275
276      memset(&best_stats, 0, sizeof(best_stats));  // prevent spurious warning
277      if (pic->stats != NULL) best_stats = *pic->stats;
278      for (test_filter =
279           try_filter_none ? WEBP_FILTER_HORIZONTAL : WEBP_FILTER_NONE;
280           ok && (test_filter <= WEBP_FILTER_GRADIENT);
281           ++test_filter) {
282        VP8BitWriter tmp_bw;
283        if (filter != WEBP_FILTER_BEST && test_filter != filter) {
284          continue;
285        }
286        ok = EncodeAlphaInternal(quant_alpha, width, height,
287                                 method, test_filter, reduce_levels,
288                                 effort_level, filtered_alpha, &tmp_bw,
289                                 pic->stats);
290        if (ok) {
291          const size_t score = VP8BitWriterSize(&tmp_bw);
292          if (score < best_score) {
293            // swap bitwriter objects.
294            VP8BitWriter tmp = tmp_bw;
295            tmp_bw = bw;
296            bw = tmp;
297            best_score = score;
298            if (pic->stats != NULL) best_stats = *pic->stats;
299          }
300        } else {
301          VP8BitWriterWipeOut(&bw);
302        }
303        if (wipe_tmp_bw) {
304          VP8BitWriterWipeOut(&tmp_bw);
305        }
306        wipe_tmp_bw = 1;  // For next filter trial for WEBP_FILTER_BEST.
307      }
308      if (pic->stats != NULL) *pic->stats = best_stats;
309    }
310 Ok:
311    if (ok) {
312      *output_size = VP8BitWriterSize(&bw);
313      *output = VP8BitWriterBuf(&bw);
314      if (pic->stats != NULL) {         // need stats?
315        pic->stats->coded_size += (int)(*output_size);
316        enc->sse_[3] = sse;
317      }
318    }
319    free(filtered_alpha);
320  }
321 End:
322  free(quant_alpha);
323  return ok;
324}
325
326
327//------------------------------------------------------------------------------
328// Main calls
329
330static int CompressAlphaJob(VP8Encoder* const enc, void* dummy) {
331  const WebPConfig* config = enc->config_;
332  uint8_t* alpha_data = NULL;
333  size_t alpha_size = 0;
334  const int effort_level = config->method;  // maps to [0..6]
335  const WEBP_FILTER_TYPE filter =
336      (config->alpha_filtering == 0) ? WEBP_FILTER_NONE :
337      (config->alpha_filtering == 1) ? WEBP_FILTER_FAST :
338                                       WEBP_FILTER_BEST;
339  if (!EncodeAlpha(enc, config->alpha_quality, config->alpha_compression,
340                   filter, effort_level, &alpha_data, &alpha_size)) {
341    return 0;
342  }
343  if (alpha_size != (uint32_t)alpha_size) {  // Sanity check.
344    free(alpha_data);
345    return 0;
346  }
347  enc->alpha_data_size_ = (uint32_t)alpha_size;
348  enc->alpha_data_ = alpha_data;
349  (void)dummy;
350  return 1;
351}
352
353void VP8EncInitAlpha(VP8Encoder* const enc) {
354  enc->has_alpha_ = WebPPictureHasTransparency(enc->pic_);
355  enc->alpha_data_ = NULL;
356  enc->alpha_data_size_ = 0;
357  if (enc->thread_level_ > 0) {
358    WebPWorker* const worker = &enc->alpha_worker_;
359    WebPWorkerInit(worker);
360    worker->data1 = enc;
361    worker->data2 = NULL;
362    worker->hook = (WebPWorkerHook)CompressAlphaJob;
363  }
364}
365
366int VP8EncStartAlpha(VP8Encoder* const enc) {
367  if (enc->has_alpha_) {
368    if (enc->thread_level_ > 0) {
369      WebPWorker* const worker = &enc->alpha_worker_;
370      if (!WebPWorkerReset(worker)) {    // Makes sure worker is good to go.
371        return 0;
372      }
373      WebPWorkerLaunch(worker);
374      return 1;
375    } else {
376      return CompressAlphaJob(enc, NULL);   // just do the job right away
377    }
378  }
379  return 1;
380}
381
382int VP8EncFinishAlpha(VP8Encoder* const enc) {
383  if (enc->has_alpha_) {
384    if (enc->thread_level_ > 0) {
385      WebPWorker* const worker = &enc->alpha_worker_;
386      if (!WebPWorkerSync(worker)) return 0;  // error
387    }
388  }
389  return WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
390}
391
392int VP8EncDeleteAlpha(VP8Encoder* const enc) {
393  int ok = 1;
394  if (enc->thread_level_ > 0) {
395    WebPWorker* const worker = &enc->alpha_worker_;
396    ok = WebPWorkerSync(worker);  // finish anything left in flight
397    WebPWorkerEnd(worker);  // still need to end the worker, even if !ok
398  }
399  free(enc->alpha_data_);
400  enc->alpha_data_ = NULL;
401  enc->alpha_data_size_ = 0;
402  enc->has_alpha_ = 0;
403  return ok;
404}
405
406#if defined(__cplusplus) || defined(c_plusplus)
407}    // extern "C"
408#endif
409