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 "./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 434
