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 "../webp/format_constants.h"
  21
  22 #if defined(__cplusplus) || defined(c_plusplus)
  23 extern "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
  51 static 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
 102 static 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/ ?
 152 static 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
 161 static 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
 180 static 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
 330 static 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
 353 void 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
 366 int 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
 382 int 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
 392 int 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