alpha_enc.c (16067B)
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 #include <string.h> 17 18 #include "src/dsp/dsp.h" 19 #include "src/webp/types.h" 20 #include "src/enc/vp8i_enc.h" 21 #include "src/utils/bit_writer_utils.h" 22 #include "src/utils/filters_utils.h" 23 #include "src/utils/quant_levels_utils.h" 24 #include "src/utils/thread_utils.h" 25 #include "src/utils/utils.h" 26 #include "src/webp/encode.h" 27 #include "src/webp/format_constants.h" 28 29 // ----------------------------------------------------------------------------- 30 // Encodes the given alpha data via specified compression method 'method'. 31 // The pre-processing (quantization) is performed if 'quality' is less than 100. 32 // For such cases, the encoding is lossy. The valid range is [0, 100] for 33 // 'quality' and [0, 1] for 'method': 34 // 'method = 0' - No compression; 35 // 'method = 1' - Use lossless coder on the alpha plane only 36 // 'filter' values [0, 4] correspond to prediction modes none, horizontal, 37 // vertical & gradient filters. The prediction mode 4 will try all the 38 // prediction modes 0 to 3 and pick the best one. 39 // 'effort_level': specifies how much effort must be spent to try and reduce 40 // the compressed output size. In range 0 (quick) to 6 (slow). 41 // 42 // 'output' corresponds to the buffer containing compressed alpha data. 43 // This buffer is allocated by this method and caller should call 44 // WebPSafeFree(*output) when done. 45 // 'output_size' corresponds to size of this compressed alpha buffer. 46 // 47 // Returns 1 on successfully encoding the alpha and 48 // 0 if either: 49 // invalid quality or method, or 50 // memory allocation for the compressed data fails. 51 52 #include "src/enc/vp8li_enc.h" 53 54 static int EncodeLossless(const uint8_t* const data, int width, int height, 55 int effort_level, // in [0..6] range 56 int use_quality_100, VP8LBitWriter* const bw, 57 WebPAuxStats* const stats) { 58 int ok = 0; 59 WebPConfig config; 60 WebPPicture picture; 61 62 if (!WebPPictureInit(&picture)) return 0; 63 picture.width = width; 64 picture.height = height; 65 picture.use_argb = 1; 66 picture.stats = stats; 67 if (!WebPPictureAlloc(&picture)) return 0; 68 69 // Transfer the alpha values to the green channel. 70 WebPDispatchAlphaToGreen(data, width, picture.width, picture.height, 71 picture.argb, picture.argb_stride); 72 73 if (!WebPConfigInit(&config)) return 0; 74 config.lossless = 1; 75 // Enable exact, or it would alter RGB values of transparent alpha, which is 76 // normally OK but not here since we are not encoding the input image but an 77 // internal encoding-related image containing necessary exact information in 78 // RGB channels. 79 config.exact = 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 // If the alpha quality is set to 100 and the method to 6, allow for a high 85 // lossless quality to trigger the cruncher. 86 config.quality = 87 (use_quality_100 && effort_level == 6) ? 100 : 8.f * effort_level; 88 assert(config.quality >= 0 && config.quality <= 100.f); 89 90 ok = VP8LEncodeStream(&config, &picture, bw); 91 WebPPictureFree(&picture); 92 ok = ok && !bw->error; 93 if (!ok) { 94 VP8LBitWriterWipeOut(bw); 95 return 0; 96 } 97 return 1; 98 } 99 100 // ----------------------------------------------------------------------------- 101 102 // Small struct to hold the result of a filter mode compression attempt. 103 typedef struct { 104 size_t score; 105 VP8BitWriter bw; 106 WebPAuxStats stats; 107 } FilterTrial; 108 109 // This function always returns an initialized 'bw' object, even upon error. 110 static int EncodeAlphaInternal(const uint8_t* const data, int width, int height, 111 int method, int filter, int reduce_levels, 112 int effort_level, // in [0..6] range 113 uint8_t* const tmp_alpha, 114 FilterTrial* result) { 115 int ok = 0; 116 const uint8_t* alpha_src; 117 WebPFilterFunc filter_func; 118 uint8_t header; 119 const size_t data_size = width * height; 120 const uint8_t* output = NULL; 121 size_t output_size = 0; 122 VP8LBitWriter tmp_bw; 123 124 assert((uint64_t)data_size == (uint64_t)width * height); // as per spec 125 assert(filter >= 0 && filter < WEBP_FILTER_LAST); 126 assert(method >= ALPHA_NO_COMPRESSION); 127 assert(method <= ALPHA_LOSSLESS_COMPRESSION); 128 assert(sizeof(header) == ALPHA_HEADER_LEN); 129 130 filter_func = WebPFilters[filter]; 131 if (filter_func != NULL) { 132 filter_func(data, width, height, width, tmp_alpha); 133 alpha_src = tmp_alpha; 134 } else { 135 alpha_src = data; 136 } 137 138 if (method != ALPHA_NO_COMPRESSION) { 139 ok = VP8LBitWriterInit(&tmp_bw, data_size >> 3); 140 ok = ok && EncodeLossless(alpha_src, width, height, effort_level, 141 !reduce_levels, &tmp_bw, &result->stats); 142 if (ok) { 143 output = VP8LBitWriterFinish(&tmp_bw); 144 if (tmp_bw.error) { 145 VP8LBitWriterWipeOut(&tmp_bw); 146 memset(&result->bw, 0, sizeof(result->bw)); 147 return 0; 148 } 149 output_size = VP8LBitWriterNumBytes(&tmp_bw); 150 if (output_size > data_size) { 151 // compressed size is larger than source! Revert to uncompressed mode. 152 method = ALPHA_NO_COMPRESSION; 153 VP8LBitWriterWipeOut(&tmp_bw); 154 } 155 } else { 156 VP8LBitWriterWipeOut(&tmp_bw); 157 memset(&result->bw, 0, sizeof(result->bw)); 158 return 0; 159 } 160 } 161 162 if (method == ALPHA_NO_COMPRESSION) { 163 output = alpha_src; 164 output_size = data_size; 165 ok = 1; 166 } 167 168 // Emit final result. 169 header = method | (filter << 2); 170 if (reduce_levels) header |= ALPHA_PREPROCESSED_LEVELS << 4; 171 172 if (!VP8BitWriterInit(&result->bw, ALPHA_HEADER_LEN + output_size)) ok = 0; 173 ok = ok && VP8BitWriterAppend(&result->bw, &header, ALPHA_HEADER_LEN); 174 ok = ok && VP8BitWriterAppend(&result->bw, output, output_size); 175 176 if (method != ALPHA_NO_COMPRESSION) { 177 VP8LBitWriterWipeOut(&tmp_bw); 178 } 179 ok = ok && !result->bw.error; 180 result->score = VP8BitWriterSize(&result->bw); 181 return ok; 182 } 183 184 // ----------------------------------------------------------------------------- 185 186 static int GetNumColors(const uint8_t* data, int width, int height, 187 int stride) { 188 int j; 189 int colors = 0; 190 uint8_t color[256] = { 0 }; 191 192 for (j = 0; j < height; ++j) { 193 int i; 194 const uint8_t* const p = data + j * stride; 195 for (i = 0; i < width; ++i) { 196 color[p[i]] = 1; 197 } 198 } 199 for (j = 0; j < 256; ++j) { 200 if (color[j] > 0) ++colors; 201 } 202 return colors; 203 } 204 205 #define FILTER_TRY_NONE (1 << WEBP_FILTER_NONE) 206 #define FILTER_TRY_ALL ((1 << WEBP_FILTER_LAST) - 1) 207 208 // Given the input 'filter' option, return an OR'd bit-set of filters to try. 209 static uint32_t GetFilterMap(const uint8_t* alpha, int width, int height, 210 int filter, int effort_level) { 211 uint32_t bit_map = 0U; 212 if (filter == WEBP_FILTER_FAST) { 213 // Quick estimate of the best candidate. 214 int try_filter_none = (effort_level > 3); 215 const int kMinColorsForFilterNone = 16; 216 const int kMaxColorsForFilterNone = 192; 217 const int num_colors = GetNumColors(alpha, width, height, width); 218 // For low number of colors, NONE yields better compression. 219 filter = (num_colors <= kMinColorsForFilterNone) 220 ? WEBP_FILTER_NONE 221 : WebPEstimateBestFilter(alpha, width, height, width); 222 bit_map |= 1 << filter; 223 // For large number of colors, try FILTER_NONE in addition to the best 224 // filter as well. 225 if (try_filter_none || num_colors > kMaxColorsForFilterNone) { 226 bit_map |= FILTER_TRY_NONE; 227 } 228 } else if (filter == WEBP_FILTER_NONE) { 229 bit_map = FILTER_TRY_NONE; 230 } else { // WEBP_FILTER_BEST -> try all 231 bit_map = FILTER_TRY_ALL; 232 } 233 return bit_map; 234 } 235 236 static void InitFilterTrial(FilterTrial* const score) { 237 score->score = (size_t)~0U; 238 VP8BitWriterInit(&score->bw, 0); 239 } 240 241 static int ApplyFiltersAndEncode(const uint8_t* alpha, int width, int height, 242 size_t data_size, int method, int filter, 243 int reduce_levels, int effort_level, 244 uint8_t** const output, 245 size_t* const output_size, 246 WebPAuxStats* const stats) { 247 int ok = 1; 248 FilterTrial best; 249 uint32_t try_map = 250 GetFilterMap(alpha, width, height, filter, effort_level); 251 InitFilterTrial(&best); 252 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 !defined(WEBP_DISABLE_STATS) 278 if (stats != NULL) { 279 stats->lossless_features = best.stats.lossless_features; 280 stats->histogram_bits = best.stats.histogram_bits; 281 stats->transform_bits = best.stats.transform_bits; 282 stats->cross_color_transform_bits = best.stats.cross_color_transform_bits; 283 stats->cache_bits = best.stats.cache_bits; 284 stats->palette_size = best.stats.palette_size; 285 stats->lossless_size = best.stats.lossless_size; 286 stats->lossless_hdr_size = best.stats.lossless_hdr_size; 287 stats->lossless_data_size = best.stats.lossless_data_size; 288 } 289 #else 290 (void)stats; 291 #endif 292 *output_size = VP8BitWriterSize(&best.bw); 293 *output = VP8BitWriterBuf(&best.bw); 294 } else { 295 VP8BitWriterWipeOut(&best.bw); 296 } 297 return ok; 298 } 299 300 static int EncodeAlpha(VP8Encoder* const enc, 301 int quality, int method, int filter, 302 int effort_level, 303 uint8_t** const output, size_t* const output_size) { 304 const WebPPicture* const pic = enc->pic; 305 const int width = pic->width; 306 const int height = pic->height; 307 308 uint8_t* quant_alpha = NULL; 309 const size_t data_size = width * height; 310 uint64_t sse = 0; 311 int ok = 1; 312 const int reduce_levels = (quality < 100); 313 314 // quick correctness checks 315 assert((uint64_t)data_size == (uint64_t)width * height); // as per spec 316 assert(enc != NULL && pic != NULL && pic->a != NULL); 317 assert(output != NULL && output_size != NULL); 318 assert(width > 0 && height > 0); 319 assert(pic->a_stride >= width); 320 assert(filter >= WEBP_FILTER_NONE && filter <= WEBP_FILTER_FAST); 321 322 if (quality < 0 || quality > 100) { 323 return WebPEncodingSetError(pic, VP8_ENC_ERROR_INVALID_CONFIGURATION); 324 } 325 326 if (method < ALPHA_NO_COMPRESSION || method > ALPHA_LOSSLESS_COMPRESSION) { 327 return WebPEncodingSetError(pic, VP8_ENC_ERROR_INVALID_CONFIGURATION); 328 } 329 330 if (method == ALPHA_NO_COMPRESSION) { 331 // Don't filter, as filtering will make no impact on compressed size. 332 filter = WEBP_FILTER_NONE; 333 } 334 335 quant_alpha = (uint8_t*)WebPSafeMalloc(1ULL, data_size); 336 if (quant_alpha == NULL) { 337 return WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY); 338 } 339 340 // Extract alpha data (width x height) from raw_data (stride x height). 341 WebPCopyPlane(pic->a, pic->a_stride, quant_alpha, width, width, height); 342 343 if (reduce_levels) { // No Quantization required for 'quality = 100'. 344 // 16 alpha levels gives quite a low MSE w.r.t original alpha plane hence 345 // mapped to moderate quality 70. Hence Quality:[0, 70] -> Levels:[2, 16] 346 // and Quality:]70, 100] -> Levels:]16, 256]. 347 const int alpha_levels = (quality <= 70) ? (2 + quality / 5) 348 : (16 + (quality - 70) * 8); 349 ok = QuantizeLevels(quant_alpha, width, height, alpha_levels, &sse); 350 } 351 352 if (ok) { 353 VP8FiltersInit(); 354 ok = ApplyFiltersAndEncode(quant_alpha, width, height, data_size, method, 355 filter, reduce_levels, effort_level, output, 356 output_size, pic->stats); 357 if (!ok) { 358 WebPEncodingSetError(pic, VP8_ENC_ERROR_OUT_OF_MEMORY); // imprecise 359 } 360 #if !defined(WEBP_DISABLE_STATS) 361 if (pic->stats != NULL) { // need stats? 362 pic->stats->coded_size += (int)(*output_size); 363 enc->sse[3] = sse; 364 } 365 #endif 366 } 367 368 WebPSafeFree(quant_alpha); 369 return ok; 370 } 371 372 //------------------------------------------------------------------------------ 373 // Main calls 374 375 static int CompressAlphaJob(void* arg1, void* unused) { 376 VP8Encoder* const enc = (VP8Encoder*)arg1; 377 const WebPConfig* config = enc->config; 378 uint8_t* alpha_data = NULL; 379 size_t alpha_size = 0; 380 const int effort_level = config->method; // maps to [0..6] 381 const WEBP_FILTER_TYPE filter = 382 (config->alpha_filtering == 0) ? WEBP_FILTER_NONE : 383 (config->alpha_filtering == 1) ? WEBP_FILTER_FAST : 384 WEBP_FILTER_BEST; 385 if (!EncodeAlpha(enc, config->alpha_quality, config->alpha_compression, 386 filter, effort_level, &alpha_data, &alpha_size)) { 387 return 0; 388 } 389 if (alpha_size != (uint32_t)alpha_size) { // Soundness check. 390 WebPSafeFree(alpha_data); 391 return 0; 392 } 393 enc->alpha_data_size = (uint32_t)alpha_size; 394 enc->alpha_data = alpha_data; 395 (void)unused; 396 return 1; 397 } 398 399 void VP8EncInitAlpha(VP8Encoder* const enc) { 400 WebPInitAlphaProcessing(); 401 enc->has_alpha = WebPPictureHasTransparency(enc->pic); 402 enc->alpha_data = NULL; 403 enc->alpha_data_size = 0; 404 if (enc->thread_level > 0) { 405 WebPWorker* const worker = &enc->alpha_worker; 406 WebPGetWorkerInterface()->Init(worker); 407 worker->data1 = enc; 408 worker->data2 = NULL; 409 worker->hook = CompressAlphaJob; 410 } 411 } 412 413 int VP8EncStartAlpha(VP8Encoder* const enc) { 414 if (enc->has_alpha) { 415 if (enc->thread_level > 0) { 416 WebPWorker* const worker = &enc->alpha_worker; 417 // Makes sure worker is good to go. 418 if (!WebPGetWorkerInterface()->Reset(worker)) { 419 return WebPEncodingSetError(enc->pic, VP8_ENC_ERROR_OUT_OF_MEMORY); 420 } 421 WebPGetWorkerInterface()->Launch(worker); 422 return 1; 423 } else { 424 return CompressAlphaJob(enc, NULL); // just do the job right away 425 } 426 } 427 return 1; 428 } 429 430 int VP8EncFinishAlpha(VP8Encoder* const enc) { 431 if (enc->has_alpha) { 432 if (enc->thread_level > 0) { 433 WebPWorker* const worker = &enc->alpha_worker; 434 if (!WebPGetWorkerInterface()->Sync(worker)) return 0; // error 435 } 436 } 437 return WebPReportProgress(enc->pic, enc->percent + 20, &enc->percent); 438 } 439 440 int VP8EncDeleteAlpha(VP8Encoder* const enc) { 441 int ok = 1; 442 if (enc->thread_level > 0) { 443 WebPWorker* const worker = &enc->alpha_worker; 444 // finish anything left in flight 445 ok = WebPGetWorkerInterface()->Sync(worker); 446 // still need to end the worker, even if !ok 447 WebPGetWorkerInterface()->End(worker); 448 } 449 WebPSafeFree(enc->alpha_data); 450 enc->alpha_data = NULL; 451 enc->alpha_data_size = 0; 452 enc->has_alpha = 0; 453 return ok; 454 }