src/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                           VP8BitWriter* const bw,
  51                           WebPAuxStats* const stats) {
  52   int ok = 0;
  53   WebPConfig config;
  54   WebPPicture picture;
  55   VP8LBitWriter tmp_bw;
  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   {
  66     int i, j;
  67     uint32_t* dst = picture.argb;
  68     const uint8_t* src = data;
  69     for (j = 0; j < picture.height; ++j) {
  70       for (i = 0; i < picture.width; ++i) {
  71         dst[i] = src[i] << 8;  // we leave A/R/B channels zero'd.
  72       }
  73       src += width;
  74       dst += picture.argb_stride;
  75     }
  76   }
  77
  78   WebPConfigInit(&config);
  79   config.lossless = 1;
  80   config.method = effort_level;  // impact is very small
  81   // Set a low default quality for encoding alpha. Ensure that Alpha quality at
  82   // lower methods (3 and below) is less than the threshold for triggering
  83   // costly 'BackwardReferencesTraceBackwards'.
  84   config.quality = 8.f * effort_level;
  85   assert(config.quality >= 0 && config.quality <= 100.f);
  86
  87   ok = VP8LBitWriterInit(&tmp_bw, (width * height) >> 3);
  88   ok = ok && (VP8LEncodeStream(&config, &picture, &tmp_bw) == VP8_ENC_OK);
  89   WebPPictureFree(&picture);
  90   if (ok) {
  91     const uint8_t* const buffer = VP8LBitWriterFinish(&tmp_bw);
  92     const size_t buffer_size = VP8LBitWriterNumBytes(&tmp_bw);
  93     VP8BitWriterAppend(bw, buffer, buffer_size);
  94   }
  95   VP8LBitWriterDestroy(&tmp_bw);
  96   return ok && !bw->error_;
  97 }
  98
  99 // -----------------------------------------------------------------------------
 100
 101 // Small struct to hold the result of a filter mode compression attempt.
 102 typedef 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.
 109 static 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   size_t expected_size;
 119   const size_t data_size = width * height;
 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   expected_size =
 129       (method == ALPHA_NO_COMPRESSION) ? (ALPHA_HEADER_LEN + data_size)
 130                                        : (data_size >> 5);
 131   header = method | (filter << 2);
 132   if (reduce_levels) header |= ALPHA_PREPROCESSED_LEVELS << 4;
 133
 134   VP8BitWriterInit(&result->bw, expected_size);
 135   VP8BitWriterAppend(&result->bw, &header, ALPHA_HEADER_LEN);
 136
 137   filter_func = WebPFilters[filter];
 138   if (filter_func != NULL) {
 139     filter_func(data, width, height, width, tmp_alpha);
 140     alpha_src = tmp_alpha;
 141   }  else {
 142     alpha_src = data;
 143   }
 144
 145   if (method == ALPHA_NO_COMPRESSION) {
 146     ok = VP8BitWriterAppend(&result->bw, alpha_src, width * height);
 147     ok = ok && !result->bw.error_;
 148   } else {
 149     ok = EncodeLossless(alpha_src, width, height, effort_level,
 150                         &result->bw, &result->stats);
 151     VP8BitWriterFinish(&result->bw);
 152   }
 153   result->score = VP8BitWriterSize(&result->bw);
 154   return ok;
 155 }
 156
 157 // -----------------------------------------------------------------------------
 158
 159 // TODO(skal): move to dsp/ ?
 160 static void CopyPlane(const uint8_t* src, int src_stride,
 161                       uint8_t* dst, int dst_stride, int width, int height) {
 162   while (height-- > 0) {
 163     memcpy(dst, src, width);
 164     src += src_stride;
 165     dst += dst_stride;
 166   }
 167 }
 168
 169 static int GetNumColors(const uint8_t* data, int width, int height,
 170                         int stride) {
 171   int j;
 172   int colors = 0;
 173   uint8_t color[256] = { 0 };
 174
 175   for (j = 0; j < height; ++j) {
 176     int i;
 177     const uint8_t* const p = data + j * stride;
 178     for (i = 0; i < width; ++i) {
 179       color[p[i]] = 1;
 180     }
 181   }
 182   for (j = 0; j < 256; ++j) {
 183     if (color[j] > 0) ++colors;
 184   }
 185   return colors;
 186 }
 187
 188 #define FILTER_TRY_NONE (1 << WEBP_FILTER_NONE)
 189 #define FILTER_TRY_ALL ((1 << WEBP_FILTER_LAST) - 1)
 190
 191 // Given the input 'filter' option, return an OR'd bit-set of filters to try.
 192 static uint32_t GetFilterMap(const uint8_t* alpha, int width, int height,
 193                              int filter, int effort_level) {
 194   uint32_t bit_map = 0U;
 195   if (filter == WEBP_FILTER_FAST) {
 196     // Quick estimate of the best candidate.
 197     int try_filter_none = (effort_level > 3);
 198     const int kMinColorsForFilterNone = 16;
 199     const int kMaxColorsForFilterNone = 192;
 200     const int num_colors = GetNumColors(alpha, width, height, width);
 201     // For low number of colors, NONE yields better compression.
 202     filter = (num_colors <= kMinColorsForFilterNone) ? WEBP_FILTER_NONE :
 203              EstimateBestFilter(alpha, width, height, width);
 204     bit_map |= 1 << filter;
 205     // For large number of colors, try FILTER_NONE in addition to the best
 206     // filter as well.
 207     if (try_filter_none || num_colors > kMaxColorsForFilterNone) {
 208       bit_map |= FILTER_TRY_NONE;
 209     }
 210   } else if (filter == WEBP_FILTER_NONE) {
 211     bit_map = FILTER_TRY_NONE;
 212   } else {  // WEBP_FILTER_BEST -> try all
 213     bit_map = FILTER_TRY_ALL;
 214   }
 215   return bit_map;
 216 }
 217
 218 static void InitFilterTrial(FilterTrial* const score) {
 219   score->score = (size_t)~0U;
 220   VP8BitWriterInit(&score->bw, 0);
 221 }
 222
 223 static int ApplyFiltersAndEncode(const uint8_t* alpha, int width, int height,
 224                                  size_t data_size, int method, int filter,
 225                                  int reduce_levels, int effort_level,
 226                                  uint8_t** const output,
 227                                  size_t* const output_size,
 228                                  WebPAuxStats* const stats) {
 229   int ok = 1;
 230   FilterTrial best;
 231   uint32_t try_map =
 232       GetFilterMap(alpha, width, height, filter, effort_level);
 233   InitFilterTrial(&best);
 234   if (try_map != FILTER_TRY_NONE) {
 235     uint8_t* filtered_alpha =  (uint8_t*)WebPSafeMalloc(1ULL, data_size);
 236     if (filtered_alpha == NULL) return 0;
 237
 238     for (filter = WEBP_FILTER_NONE; ok && try_map; ++filter, try_map >>= 1) {
 239       if (try_map & 1) {
 240         FilterTrial trial;
 241         ok = EncodeAlphaInternal(alpha, width, height, method, filter,
 242                                  reduce_levels, effort_level, filtered_alpha,
 243                                  &trial);
 244         if (ok && trial.score < best.score) {
 245           VP8BitWriterWipeOut(&best.bw);
 246           best = trial;
 247         } else {
 248           VP8BitWriterWipeOut(&trial.bw);
 249         }
 250       }
 251     }
 252     WebPSafeFree(filtered_alpha);
 253   } else {
 254     ok = EncodeAlphaInternal(alpha, width, height, method, WEBP_FILTER_NONE,
 255                              reduce_levels, effort_level, NULL, &best);
 256   }
 257   if (ok) {
 258     if (stats != NULL) *stats = best.stats;
 259     *output_size = VP8BitWriterSize(&best.bw);
 260     *output = VP8BitWriterBuf(&best.bw);
 261   } else {
 262     VP8BitWriterWipeOut(&best.bw);
 263   }
 264   return ok;
 265 }
 266
 267 static int EncodeAlpha(VP8Encoder* const enc,
 268                        int quality, int method, int filter,
 269                        int effort_level,
 270                        uint8_t** const output, size_t* const output_size) {
 271   const WebPPicture* const pic = enc->pic_;
 272   const int width = pic->width;
 273   const int height = pic->height;
 274
 275   uint8_t* quant_alpha = NULL;
 276   const size_t data_size = width * height;
 277   uint64_t sse = 0;
 278   int ok = 1;
 279   const int reduce_levels = (quality < 100);
 280
 281   // quick sanity checks
 282   assert((uint64_t)data_size == (uint64_t)width * height);  // as per spec
 283   assert(enc != NULL && pic != NULL && pic->a != NULL);
 284   assert(output != NULL && output_size != NULL);
 285   assert(width > 0 && height > 0);
 286   assert(pic->a_stride >= width);
 287   assert(filter >= WEBP_FILTER_NONE && filter <= WEBP_FILTER_FAST);
 288
 289   if (quality < 0 || quality > 100) {
 290     return 0;
 291   }
 292
 293   if (method < ALPHA_NO_COMPRESSION || method > ALPHA_LOSSLESS_COMPRESSION) {
 294     return 0;
 295   }
 296
 297   if (method == ALPHA_NO_COMPRESSION) {
 298     // Don't filter, as filtering will make no impact on compressed size.
 299     filter = WEBP_FILTER_NONE;
 300   }
 301
 302   quant_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size);
 303   if (quant_alpha == NULL) {
 304     return 0;
 305   }
 306
 307   // Extract alpha data (width x height) from raw_data (stride x height).
 308   CopyPlane(pic->a, pic->a_stride, quant_alpha, width, width, height);
 309
 310   if (reduce_levels) {  // No Quantization required for 'quality = 100'.
 311     // 16 alpha levels gives quite a low MSE w.r.t original alpha plane hence
 312     // mapped to moderate quality 70. Hence Quality:[0, 70] -> Levels:[2, 16]
 313     // and Quality:]70, 100] -> Levels:]16, 256].
 314     const int alpha_levels = (quality <= 70) ? (2 + quality / 5)
 315                                              : (16 + (quality - 70) * 8);
 316     ok = QuantizeLevels(quant_alpha, width, height, alpha_levels, &sse);
 317   }
 318
 319   if (ok) {
 320     ok = ApplyFiltersAndEncode(quant_alpha, width, height, data_size, method,
 321                                filter, reduce_levels, effort_level, output,
 322                                output_size, pic->stats);
 323     if (pic->stats != NULL) {  // need stats?
 324       pic->stats->coded_size += (int)(*output_size);
 325       enc->sse_[3] = sse;
 326     }
 327   }
 328
 329   WebPSafeFree(quant_alpha);
 330   return ok;
 331 }
 332
 333 //------------------------------------------------------------------------------
 334 // Main calls
 335
 336 static int CompressAlphaJob(VP8Encoder* const enc, void* dummy) {
 337   const WebPConfig* config = enc->config_;
 338   uint8_t* alpha_data = NULL;
 339   size_t alpha_size = 0;
 340   const int effort_level = config->method;  // maps to [0..6]
 341   const WEBP_FILTER_TYPE filter =
 342       (config->alpha_filtering == 0) ? WEBP_FILTER_NONE :
 343       (config->alpha_filtering == 1) ? WEBP_FILTER_FAST :
 344                                        WEBP_FILTER_BEST;
 345   if (!EncodeAlpha(enc, config->alpha_quality, config->alpha_compression,
 346                    filter, effort_level, &alpha_data, &alpha_size)) {
 347     return 0;
 348   }
 349   if (alpha_size != (uint32_t)alpha_size) {  // Sanity check.
 350     WebPSafeFree(alpha_data);
 351     return 0;
 352   }
 353   enc->alpha_data_size_ = (uint32_t)alpha_size;
 354   enc->alpha_data_ = alpha_data;
 355   (void)dummy;
 356   return 1;
 357 }
 358
 359 void VP8EncInitAlpha(VP8Encoder* const enc) {
 360   enc->has_alpha_ = WebPPictureHasTransparency(enc->pic_);
 361   enc->alpha_data_ = NULL;
 362   enc->alpha_data_size_ = 0;
 363   if (enc->thread_level_ > 0) {
 364     WebPWorker* const worker = &enc->alpha_worker_;
 365     WebPGetWorkerInterface()->Init(worker);
 366     worker->data1 = enc;
 367     worker->data2 = NULL;
 368     worker->hook = (WebPWorkerHook)CompressAlphaJob;
 369   }
 370 }
 371
 372 int VP8EncStartAlpha(VP8Encoder* const enc) {
 373   if (enc->has_alpha_) {
 374     if (enc->thread_level_ > 0) {
 375       WebPWorker* const worker = &enc->alpha_worker_;
 376       // Makes sure worker is good to go.
 377       if (!WebPGetWorkerInterface()->Reset(worker)) {
 378         return 0;
 379       }
 380       WebPGetWorkerInterface()->Launch(worker);
 381       return 1;
 382     } else {
 383       return CompressAlphaJob(enc, NULL);   // just do the job right away
 384     }
 385   }
 386   return 1;
 387 }
 388
 389 int VP8EncFinishAlpha(VP8Encoder* const enc) {
 390   if (enc->has_alpha_) {
 391     if (enc->thread_level_ > 0) {
 392       WebPWorker* const worker = &enc->alpha_worker_;
 393       if (!WebPGetWorkerInterface()->Sync(worker)) return 0;  // error
 394     }
 395   }
 396   return WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
 397 }
 398
 399 int VP8EncDeleteAlpha(VP8Encoder* const enc) {
 400   int ok = 1;
 401   if (enc->thread_level_ > 0) {
 402     WebPWorker* const worker = &enc->alpha_worker_;
 403     // finish anything left in flight
 404     ok = WebPGetWorkerInterface()->Sync(worker);
 405     // still need to end the worker, even if !ok
 406     WebPGetWorkerInterface()->End(worker);
 407   }
 408   WebPSafeFree(enc->alpha_data_);
 409   enc->alpha_data_ = NULL;
 410   enc->alpha_data_size_ = 0;
 411   enc->has_alpha_ = 0;
 412   return ok;
 413 }
 414