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