third_party/libwebp/enc/alpha.c

   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 "../utils/utils.h"
  21 #include "../webp/format_constants.h"
  22
  23 // -----------------------------------------------------------------------------
  24 // Encodes the given alpha data via specified compression method 'method'.
  25 // The pre-processing (quantization) is performed if 'quality' is less than 100.
  26 // For such cases, the encoding is lossy. The valid range is [0, 100] for
  27 // 'quality' and [0, 1] for 'method':
  28 //   'method = 0' - No compression;
  29 //   'method = 1' - Use lossless coder on the alpha plane only
  30 // 'filter' values [0, 4] correspond to prediction modes none, horizontal,
  31 // vertical & gradient filters. The prediction mode 4 will try all the
  32 // prediction modes 0 to 3 and pick the best one.
  33 // 'effort_level': specifies how much effort must be spent to try and reduce
  34 //  the compressed output size. In range 0 (quick) to 6 (slow).
  35 //
  36 // 'output' corresponds to the buffer containing compressed alpha data.
  37 //          This buffer is allocated by this method and caller should call
  38 //          WebPSafeFree(*output) when done.
  39 // 'output_size' corresponds to size of this compressed alpha buffer.
  40 //
  41 // Returns 1 on successfully encoding the alpha and
  42 //         0 if either:
  43 //           invalid quality or method, or
  44 //           memory allocation for the compressed data fails.
  45
  46 #include "../enc/vp8li.h"
  47
  48 static int EncodeLossless(const uint8_t* const data, int width, int height,
  49                           int effort_level,  // in [0..6] range
  50                           VP8LBitWriter* const bw,
  51                           WebPAuxStats* const stats) {
  52   int ok = 0;
  53   WebPConfig config;
  54   WebPPicture picture;
  55
  56   WebPPictureInit(&picture);
  57   picture.width = width;
  58   picture.height = height;
  59   picture.use_argb = 1;
  60   picture.stats = stats;
  61   if (!WebPPictureAlloc(&picture)) return 0;
  62
  63   // Transfer the alpha values to the green channel.
  64   {
  65     int i, j;
  66     uint32_t* dst = picture.argb;
  67     const uint8_t* src = data;
  68     for (j = 0; j < picture.height; ++j) {
  69       for (i = 0; i < picture.width; ++i) {
  70         dst[i] = src[i] << 8;  // we leave A/R/B channels zero'd.
  71       }
  72       src += width;
  73       dst += picture.argb_stride;
  74     }
  75   }
  76
  77   WebPConfigInit(&config);
  78   config.lossless = 1;
  79   config.method = effort_level;  // impact is very small
  80   // Set a low default quality for encoding alpha. Ensure that Alpha quality at
  81   // lower methods (3 and below) is less than the threshold for triggering
  82   // costly 'BackwardReferencesTraceBackwards'.
  83   config.quality = 8.f * effort_level;
  84   assert(config.quality >= 0 && config.quality <= 100.f);
  85
  86   ok = (VP8LEncodeStream(&config, &picture, bw) == VP8_ENC_OK);
  87   WebPPictureFree(&picture);
  88   ok = ok && !bw->error_;
  89   if (!ok) {
  90     VP8LBitWriterDestroy(bw);
  91     return 0;
  92   }
  93   return 1;
  94
  95 }
  96
  97 // -----------------------------------------------------------------------------
  98
  99 // Small struct to hold the result of a filter mode compression attempt.
 100 typedef struct {
 101   size_t score;
 102   VP8BitWriter bw;
 103   WebPAuxStats stats;
 104 } FilterTrial;
 105
 106 // This function always returns an initialized 'bw' object, even upon error.
 107 static int EncodeAlphaInternal(const uint8_t* const data, int width, int height,
 108                                int method, int filter, int reduce_levels,
 109                                int effort_level,  // in [0..6] range
 110                                uint8_t* const tmp_alpha,
 111                                FilterTrial* result) {
 112   int ok = 0;
 113   const uint8_t* alpha_src;
 114   WebPFilterFunc filter_func;
 115   uint8_t header;
 116   const size_t data_size = width * height;
 117   const uint8_t* output = NULL;
 118   size_t output_size = 0;
 119   VP8LBitWriter tmp_bw;
 120
 121   assert((uint64_t)data_size == (uint64_t)width * height);  // as per spec
 122   assert(filter >= 0 && filter < WEBP_FILTER_LAST);
 123   assert(method >= ALPHA_NO_COMPRESSION);
 124   assert(method <= ALPHA_LOSSLESS_COMPRESSION);
 125   assert(sizeof(header) == ALPHA_HEADER_LEN);
 126   // TODO(skal): have a common function and #define's to validate alpha params.
 127
 128   filter_func = WebPFilters[filter];
 129   if (filter_func != NULL) {
 130     filter_func(data, width, height, width, tmp_alpha);
 131     alpha_src = tmp_alpha;
 132   }  else {
 133     alpha_src = data;
 134   }
 135
 136   if (method != ALPHA_NO_COMPRESSION) {
 137     ok = VP8LBitWriterInit(&tmp_bw, data_size >> 3);
 138     ok = ok && EncodeLossless(alpha_src, width, height, effort_level,
 139                               &tmp_bw, &result->stats);
 140     if (ok) {
 141       output = VP8LBitWriterFinish(&tmp_bw);
 142       output_size = VP8LBitWriterNumBytes(&tmp_bw);
 143       if (output_size > data_size) {
 144         // compressed size is larger than source! Revert to uncompressed mode.
 145         method = ALPHA_NO_COMPRESSION;
 146         VP8LBitWriterDestroy(&tmp_bw);
 147       }
 148     } else {
 149       VP8LBitWriterDestroy(&tmp_bw);
 150       return 0;
 151     }
 152   }
 153
 154   if (method == ALPHA_NO_COMPRESSION) {
 155     output = alpha_src;
 156     output_size = data_size;
 157     ok = 1;
 158   }
 159
 160   // Emit final result.
 161   header = method | (filter << 2);
 162   if (reduce_levels) header |= ALPHA_PREPROCESSED_LEVELS << 4;
 163
 164   VP8BitWriterInit(&result->bw, ALPHA_HEADER_LEN + output_size);
 165   ok = ok && VP8BitWriterAppend(&result->bw, &header, ALPHA_HEADER_LEN);
 166   ok = ok && VP8BitWriterAppend(&result->bw, output, output_size);
 167
 168   if (method != ALPHA_NO_COMPRESSION) {
 169     VP8LBitWriterDestroy(&tmp_bw);
 170   }
 171   ok = ok && !result->bw.error_;
 172   result->score = VP8BitWriterSize(&result->bw);
 173   return ok;
 174 }
 175
 176 // -----------------------------------------------------------------------------
 177
 178 // TODO(skal): move to dsp/ ?
 179 static void CopyPlane(const uint8_t* src, int src_stride,
 180                       uint8_t* dst, int dst_stride, int width, int height) {
 181   while (height-- > 0) {
 182     memcpy(dst, src, width);
 183     src += src_stride;
 184     dst += dst_stride;
 185   }
 186 }
 187
 188 static int GetNumColors(const uint8_t* data, int width, int height,
 189                         int stride) {
 190   int j;
 191   int colors = 0;
 192   uint8_t color[256] = { 0 };
 193
 194   for (j = 0; j < height; ++j) {
 195     int i;
 196     const uint8_t* const p = data + j * stride;
 197     for (i = 0; i < width; ++i) {
 198       color[p[i]] = 1;
 199     }
 200   }
 201   for (j = 0; j < 256; ++j) {
 202     if (color[j] > 0) ++colors;
 203   }
 204   return colors;
 205 }
 206
 207 #define FILTER_TRY_NONE (1 << WEBP_FILTER_NONE)
 208 #define FILTER_TRY_ALL ((1 << WEBP_FILTER_LAST) - 1)
 209
 210 // Given the input 'filter' option, return an OR'd bit-set of filters to try.
 211 static uint32_t GetFilterMap(const uint8_t* alpha, int width, int height,
 212                              int filter, int effort_level) {
 213   uint32_t bit_map = 0U;
 214   if (filter == WEBP_FILTER_FAST) {
 215     // Quick estimate of the best candidate.
 216     int try_filter_none = (effort_level > 3);
 217     const int kMinColorsForFilterNone = 16;
 218     const int kMaxColorsForFilterNone = 192;
 219     const int num_colors = GetNumColors(alpha, width, height, width);
 220     // For low number of colors, NONE yields better compression.
 221     filter = (num_colors <= kMinColorsForFilterNone) ? WEBP_FILTER_NONE :
 222              EstimateBestFilter(alpha, width, height, width);
 223     bit_map |= 1 << filter;
 224     // For large number of colors, try FILTER_NONE in addition to the best
 225     // filter as well.
 226     if (try_filter_none || num_colors > kMaxColorsForFilterNone) {
 227       bit_map |= FILTER_TRY_NONE;
 228     }
 229   } else if (filter == WEBP_FILTER_NONE) {
 230     bit_map = FILTER_TRY_NONE;
 231   } else {  // WEBP_FILTER_BEST -> try all
 232     bit_map = FILTER_TRY_ALL;
 233   }
 234   return bit_map;
 235 }
 236
 237 static void InitFilterTrial(FilterTrial* const score) {
 238   score->score = (size_t)~0U;
 239   VP8BitWriterInit(&score->bw, 0);
 240 }
 241
 242 static int ApplyFiltersAndEncode(const uint8_t* alpha, int width, int height,
 243                                  size_t data_size, int method, int filter,
 244                                  int reduce_levels, int effort_level,
 245                                  uint8_t** const output,
 246                                  size_t* const output_size,
 247                                  WebPAuxStats* const stats) {
 248   int ok = 1;
 249   FilterTrial best;
 250   uint32_t try_map =
 251       GetFilterMap(alpha, width, height, filter, effort_level);
 252   InitFilterTrial(&best);
 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 (stats != NULL) *stats = best.stats;
 278     *output_size = VP8BitWriterSize(&best.bw);
 279     *output = VP8BitWriterBuf(&best.bw);
 280   } else {
 281     VP8BitWriterWipeOut(&best.bw);
 282   }
 283   return ok;
 284 }
 285
 286 static int EncodeAlpha(VP8Encoder* const enc,
 287                        int quality, int method, int filter,
 288                        int effort_level,
 289                        uint8_t** const output, size_t* const output_size) {
 290   const WebPPicture* const pic = enc->pic_;
 291   const int width = pic->width;
 292   const int height = pic->height;
 293
 294   uint8_t* quant_alpha = NULL;
 295   const size_t data_size = width * height;
 296   uint64_t sse = 0;
 297   int ok = 1;
 298   const int reduce_levels = (quality < 100);
 299
 300   // quick sanity checks
 301   assert((uint64_t)data_size == (uint64_t)width * height);  // as per spec
 302   assert(enc != NULL && pic != NULL && pic->a != NULL);
 303   assert(output != NULL && output_size != NULL);
 304   assert(width > 0 && height > 0);
 305   assert(pic->a_stride >= width);
 306   assert(filter >= WEBP_FILTER_NONE && filter <= WEBP_FILTER_FAST);
 307
 308   if (quality < 0 || quality > 100) {
 309     return 0;
 310   }
 311
 312   if (method < ALPHA_NO_COMPRESSION || method > ALPHA_LOSSLESS_COMPRESSION) {
 313     return 0;
 314   }
 315
 316   if (method == ALPHA_NO_COMPRESSION) {
 317     // Don't filter, as filtering will make no impact on compressed size.
 318     filter = WEBP_FILTER_NONE;
 319   }
 320
 321   quant_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size);
 322   if (quant_alpha == NULL) {
 323     return 0;
 324   }
 325
 326   // Extract alpha data (width x height) from raw_data (stride x height).
 327   CopyPlane(pic->a, pic->a_stride, quant_alpha, width, width, height);
 328
 329   if (reduce_levels) {  // No Quantization required for 'quality = 100'.
 330     // 16 alpha levels gives quite a low MSE w.r.t original alpha plane hence
 331     // mapped to moderate quality 70. Hence Quality:[0, 70] -> Levels:[2, 16]
 332     // and Quality:]70, 100] -> Levels:]16, 256].
 333     const int alpha_levels = (quality <= 70) ? (2 + quality / 5)
 334                                              : (16 + (quality - 70) * 8);
 335     ok = QuantizeLevels(quant_alpha, width, height, alpha_levels, &sse);
 336   }
 337
 338   if (ok) {
 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
 355 static 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
 378 void VP8EncInitAlpha(VP8Encoder* const enc) {
 379   enc->has_alpha_ = WebPPictureHasTransparency(enc->pic_);
 380   enc->alpha_data_ = NULL;
 381   enc->alpha_data_size_ = 0;
 382   if (enc->thread_level_ > 0) {
 383     WebPWorker* const worker = &enc->alpha_worker_;
 384     WebPGetWorkerInterface()->Init(worker);
 385     worker->data1 = enc;
 386     worker->data2 = NULL;
 387     worker->hook = (WebPWorkerHook)CompressAlphaJob;
 388   }
 389 }
 390
 391 int VP8EncStartAlpha(VP8Encoder* const enc) {
 392   if (enc->has_alpha_) {
 393     if (enc->thread_level_ > 0) {
 394       WebPWorker* const worker = &enc->alpha_worker_;
 395       // Makes sure worker is good to go.
 396       if (!WebPGetWorkerInterface()->Reset(worker)) {
 397         return 0;
 398       }
 399       WebPGetWorkerInterface()->Launch(worker);
 400       return 1;
 401     } else {
 402       return CompressAlphaJob(enc, NULL);   // just do the job right away
 403     }
 404   }
 405   return 1;
 406 }
 407
 408 int VP8EncFinishAlpha(VP8Encoder* const enc) {
 409   if (enc->has_alpha_) {
 410     if (enc->thread_level_ > 0) {
 411       WebPWorker* const worker = &enc->alpha_worker_;
 412       if (!WebPGetWorkerInterface()->Sync(worker)) return 0;  // error
 413     }
 414   }
 415   return WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
 416 }
 417
 418 int VP8EncDeleteAlpha(VP8Encoder* const enc) {
 419   int ok = 1;
 420   if (enc->thread_level_ > 0) {
 421     WebPWorker* const worker = &enc->alpha_worker_;
 422     // finish anything left in flight
 423     ok = WebPGetWorkerInterface()->Sync(worker);
 424     // still need to end the worker, even if !ok
 425     WebPGetWorkerInterface()->End(worker);
 426   }
 427   WebPSafeFree(enc->alpha_data_);
 428   enc->alpha_data_ = NULL;
 429   enc->alpha_data_size_ = 0;
 430   enc->has_alpha_ = 0;
 431   return ok;
 432 }
 433