1 // Copyright 2011 Google Inc. All Rights Reserved. 2 // 3 // This code is licensed under the same terms as WebM: 4 // Software License Agreement: http://www.webmproject.org/license/software/ 5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/ 6 // ----------------------------------------------------------------------------- 7 // 8 // Quantization 9 // 10 // Author: Skal (pascal.massimino (at) gmail.com) 11 12 #include <assert.h> 13 #include <math.h> 14 15 #include "./vp8enci.h" 16 #include "./cost.h" 17 18 #define DO_TRELLIS_I4 1 19 #define DO_TRELLIS_I16 1 // not a huge gain, but ok at low bitrate. 20 #define DO_TRELLIS_UV 0 // disable trellis for UV. Risky. Not worth. 21 #define USE_TDISTO 1 22 23 #define MID_ALPHA 64 // neutral value for susceptibility 24 #define MIN_ALPHA 30 // lowest usable value for susceptibility 25 #define MAX_ALPHA 100 // higher meaninful value for susceptibility 26 27 #define SNS_TO_DQ 0.9 // Scaling constant between the sns value and the QP 28 // power-law modulation. Must be strictly less than 1. 29 30 #define I4_PENALTY 4000 // Rate-penalty for quick i4/i16 decision 31 32 #define MULT_8B(a, b) (((a) * (b) + 128) >> 8) 33 34 #if defined(__cplusplus) || defined(c_plusplus) 35 extern "C" { 36 #endif 37 38 //------------------------------------------------------------------------------ 39 40 static WEBP_INLINE int clip(int v, int m, int M) { 41 return v < m ? m : v > M ? M : v; 42 } 43 44 static const uint8_t kZigzag[16] = { 45 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15 46 }; 47 48 static const uint8_t kDcTable[128] = { 49 4, 5, 6, 7, 8, 9, 10, 10, 50 11, 12, 13, 14, 15, 16, 17, 17, 51 18, 19, 20, 20, 21, 21, 22, 22, 52 23, 23, 24, 25, 25, 26, 27, 28, 53 29, 30, 31, 32, 33, 34, 35, 36, 54 37, 37, 38, 39, 40, 41, 42, 43, 55 44, 45, 46, 46, 47, 48, 49, 50, 56 51, 52, 53, 54, 55, 56, 57, 58, 57 59, 60, 61, 62, 63, 64, 65, 66, 58 67, 68, 69, 70, 71, 72, 73, 74, 59 75, 76, 76, 77, 78, 79, 80, 81, 60 82, 83, 84, 85, 86, 87, 88, 89, 61 91, 93, 95, 96, 98, 100, 101, 102, 62 104, 106, 108, 110, 112, 114, 116, 118, 63 122, 124, 126, 128, 130, 132, 134, 136, 64 138, 140, 143, 145, 148, 151, 154, 157 65 }; 66 67 static const uint16_t kAcTable[128] = { 68 4, 5, 6, 7, 8, 9, 10, 11, 69 12, 13, 14, 15, 16, 17, 18, 19, 70 20, 21, 22, 23, 24, 25, 26, 27, 71 28, 29, 30, 31, 32, 33, 34, 35, 72 36, 37, 38, 39, 40, 41, 42, 43, 73 44, 45, 46, 47, 48, 49, 50, 51, 74 52, 53, 54, 55, 56, 57, 58, 60, 75 62, 64, 66, 68, 70, 72, 74, 76, 76 78, 80, 82, 84, 86, 88, 90, 92, 77 94, 96, 98, 100, 102, 104, 106, 108, 78 110, 112, 114, 116, 119, 122, 125, 128, 79 131, 134, 137, 140, 143, 146, 149, 152, 80 155, 158, 161, 164, 167, 170, 173, 177, 81 181, 185, 189, 193, 197, 201, 205, 209, 82 213, 217, 221, 225, 229, 234, 239, 245, 83 249, 254, 259, 264, 269, 274, 279, 284 84 }; 85 86 static const uint16_t kAcTable2[128] = { 87 8, 8, 9, 10, 12, 13, 15, 17, 88 18, 20, 21, 23, 24, 26, 27, 29, 89 31, 32, 34, 35, 37, 38, 40, 41, 90 43, 44, 46, 48, 49, 51, 52, 54, 91 55, 57, 58, 60, 62, 63, 65, 66, 92 68, 69, 71, 72, 74, 75, 77, 79, 93 80, 82, 83, 85, 86, 88, 89, 93, 94 96, 99, 102, 105, 108, 111, 114, 117, 95 120, 124, 127, 130, 133, 136, 139, 142, 96 145, 148, 151, 155, 158, 161, 164, 167, 97 170, 173, 176, 179, 184, 189, 193, 198, 98 203, 207, 212, 217, 221, 226, 230, 235, 99 240, 244, 249, 254, 258, 263, 268, 274, 100 280, 286, 292, 299, 305, 311, 317, 323, 101 330, 336, 342, 348, 354, 362, 370, 379, 102 385, 393, 401, 409, 416, 424, 432, 440 103 }; 104 105 static const uint16_t kCoeffThresh[16] = { 106 0, 10, 20, 30, 107 10, 20, 30, 30, 108 20, 30, 30, 30, 109 30, 30, 30, 30 110 }; 111 112 // TODO(skal): tune more. Coeff thresholding? 113 static const uint8_t kBiasMatrices[3][16] = { // [3] = [luma-ac,luma-dc,chroma] 114 { 96, 96, 96, 96, 115 96, 96, 96, 96, 116 96, 96, 96, 96, 117 96, 96, 96, 96 }, 118 { 96, 96, 96, 96, 119 96, 96, 96, 96, 120 96, 96, 96, 96, 121 96, 96, 96, 96 }, 122 { 96, 96, 96, 96, 123 96, 96, 96, 96, 124 96, 96, 96, 96, 125 96, 96, 96, 96 } 126 }; 127 128 // Sharpening by (slightly) raising the hi-frequency coeffs (only for trellis). 129 // Hack-ish but helpful for mid-bitrate range. Use with care. 130 static const uint8_t kFreqSharpening[16] = { 131 0, 30, 60, 90, 132 30, 60, 90, 90, 133 60, 90, 90, 90, 134 90, 90, 90, 90 135 }; 136 137 //------------------------------------------------------------------------------ 138 // Initialize quantization parameters in VP8Matrix 139 140 // Returns the average quantizer 141 static int ExpandMatrix(VP8Matrix* const m, int type) { 142 int i; 143 int sum = 0; 144 for (i = 2; i < 16; ++i) { 145 m->q_[i] = m->q_[1]; 146 } 147 for (i = 0; i < 16; ++i) { 148 const int j = kZigzag[i]; 149 const int bias = kBiasMatrices[type][j]; 150 m->iq_[j] = (1 << QFIX) / m->q_[j]; 151 m->bias_[j] = BIAS(bias); 152 // TODO(skal): tune kCoeffThresh[] 153 m->zthresh_[j] = ((256 /*+ kCoeffThresh[j]*/ - bias) * m->q_[j] + 127) >> 8; 154 m->sharpen_[j] = (kFreqSharpening[j] * m->q_[j]) >> 11; 155 sum += m->q_[j]; 156 } 157 return (sum + 8) >> 4; 158 } 159 160 static void SetupMatrices(VP8Encoder* enc) { 161 int i; 162 const int tlambda_scale = 163 (enc->method_ >= 4) ? enc->config_->sns_strength 164 : 0; 165 const int num_segments = enc->segment_hdr_.num_segments_; 166 for (i = 0; i < num_segments; ++i) { 167 VP8SegmentInfo* const m = &enc->dqm_[i]; 168 const int q = m->quant_; 169 int q4, q16, quv; 170 m->y1_.q_[0] = kDcTable[clip(q + enc->dq_y1_dc_, 0, 127)]; 171 m->y1_.q_[1] = kAcTable[clip(q, 0, 127)]; 172 173 m->y2_.q_[0] = kDcTable[ clip(q + enc->dq_y2_dc_, 0, 127)] * 2; 174 m->y2_.q_[1] = kAcTable2[clip(q + enc->dq_y2_ac_, 0, 127)]; 175 176 m->uv_.q_[0] = kDcTable[clip(q + enc->dq_uv_dc_, 0, 117)]; 177 m->uv_.q_[1] = kAcTable[clip(q + enc->dq_uv_ac_, 0, 127)]; 178 179 q4 = ExpandMatrix(&m->y1_, 0); 180 q16 = ExpandMatrix(&m->y2_, 1); 181 quv = ExpandMatrix(&m->uv_, 2); 182 183 // TODO: Switch to kLambda*[] tables? 184 { 185 m->lambda_i4_ = (3 * q4 * q4) >> 7; 186 m->lambda_i16_ = (3 * q16 * q16); 187 m->lambda_uv_ = (3 * quv * quv) >> 6; 188 m->lambda_mode_ = (1 * q4 * q4) >> 7; 189 m->lambda_trellis_i4_ = (7 * q4 * q4) >> 3; 190 m->lambda_trellis_i16_ = (q16 * q16) >> 2; 191 m->lambda_trellis_uv_ = (quv *quv) << 1; 192 m->tlambda_ = (tlambda_scale * q4) >> 5; 193 } 194 } 195 } 196 197 //------------------------------------------------------------------------------ 198 // Initialize filtering parameters 199 200 // Very small filter-strength values have close to no visual effect. So we can 201 // save a little decoding-CPU by turning filtering off for these. 202 #define FSTRENGTH_CUTOFF 3 203 204 static void SetupFilterStrength(VP8Encoder* const enc) { 205 int i; 206 const int level0 = enc->config_->filter_strength; 207 for (i = 0; i < NUM_MB_SEGMENTS; ++i) { 208 // Segments with lower quantizer will be less filtered. TODO: tune (wrt SNS) 209 const int level = level0 * 256 * enc->dqm_[i].quant_ / 128; 210 const int f = level / (256 + enc->dqm_[i].beta_); 211 enc->dqm_[i].fstrength_ = (f < FSTRENGTH_CUTOFF) ? 0 : (f > 63) ? 63 : f; 212 } 213 // We record the initial strength (mainly for the case of 1-segment only). 214 enc->filter_hdr_.level_ = enc->dqm_[0].fstrength_; 215 enc->filter_hdr_.simple_ = (enc->config_->filter_type == 0); 216 enc->filter_hdr_.sharpness_ = enc->config_->filter_sharpness; 217 } 218 219 //------------------------------------------------------------------------------ 220 221 // Note: if you change the values below, remember that the max range 222 // allowed by the syntax for DQ_UV is [-16,16]. 223 #define MAX_DQ_UV (6) 224 #define MIN_DQ_UV (-4) 225 226 // We want to emulate jpeg-like behaviour where the expected "good" quality 227 // is around q=75. Internally, our "good" middle is around c=50. So we 228 // map accordingly using linear piece-wise function 229 static double QualityToCompression(double c) { 230 const double linear_c = (c < 0.75) ? c * (2. / 3.) : 2. * c - 1.; 231 // The file size roughly scales as pow(quantizer, 3.). Actually, the 232 // exponent is somewhere between 2.8 and 3.2, but we're mostly interested 233 // in the mid-quant range. So we scale the compressibility inversely to 234 // this power-law: quant ~= compression ^ 1/3. This law holds well for 235 // low quant. Finer modelling for high-quant would make use of kAcTable[] 236 // more explicitly. 237 const double v = pow(linear_c, 1 / 3.); 238 return v; 239 } 240 241 static double QualityToJPEGCompression(double c, double alpha) { 242 // We map the complexity 'alpha' and quality setting 'c' to a compression 243 // exponent empirically matched to the compression curve of libjpeg6b. 244 // On average, the WebP output size will be roughly similar to that of a 245 // JPEG file compressed with same quality factor. 246 const double amin = 0.30; 247 const double amax = 0.85; 248 const double exp_min = 0.4; 249 const double exp_max = 0.9; 250 const double slope = (exp_min - exp_max) / (amax - amin); 251 // Linearly interpolate 'expn' from exp_min to exp_max 252 // in the [amin, amax] range. 253 const double expn = (alpha > amax) ? exp_min 254 : (alpha < amin) ? exp_max 255 : exp_max + slope * (alpha - amin); 256 const double v = pow(c, expn); 257 return v; 258 } 259 260 static int SegmentsAreEquivalent(const VP8SegmentInfo* const S1, 261 const VP8SegmentInfo* const S2) { 262 return (S1->quant_ == S2->quant_) && (S1->fstrength_ == S2->fstrength_); 263 } 264 265 static void SimplifySegments(VP8Encoder* const enc) { 266 int map[NUM_MB_SEGMENTS] = { 0, 1, 2, 3 }; 267 const int num_segments = enc->segment_hdr_.num_segments_; 268 int num_final_segments = 1; 269 int s1, s2; 270 for (s1 = 1; s1 < num_segments; ++s1) { // find similar segments 271 const VP8SegmentInfo* const S1 = &enc->dqm_[s1]; 272 int found = 0; 273 // check if we already have similar segment 274 for (s2 = 0; s2 < num_final_segments; ++s2) { 275 const VP8SegmentInfo* const S2 = &enc->dqm_[s2]; 276 if (SegmentsAreEquivalent(S1, S2)) { 277 found = 1; 278 break; 279 } 280 } 281 map[s1] = s2; 282 if (!found) { 283 if (num_final_segments != s1) { 284 enc->dqm_[num_final_segments] = enc->dqm_[s1]; 285 } 286 ++num_final_segments; 287 } 288 } 289 if (num_final_segments < num_segments) { // Remap 290 int i = enc->mb_w_ * enc->mb_h_; 291 while (i-- > 0) enc->mb_info_[i].segment_ = map[enc->mb_info_[i].segment_]; 292 enc->segment_hdr_.num_segments_ = num_final_segments; 293 // Replicate the trailing segment infos (it's mostly cosmetics) 294 for (i = num_final_segments; i < num_segments; ++i) { 295 enc->dqm_[i] = enc->dqm_[num_final_segments - 1]; 296 } 297 } 298 } 299 300 void VP8SetSegmentParams(VP8Encoder* const enc, float quality) { 301 int i; 302 int dq_uv_ac, dq_uv_dc; 303 const int num_segments = enc->segment_hdr_.num_segments_; 304 const double amp = SNS_TO_DQ * enc->config_->sns_strength / 100. / 128.; 305 const double Q = quality / 100.; 306 const double c_base = enc->config_->emulate_jpeg_size ? 307 QualityToJPEGCompression(Q, enc->alpha_ / 255.) : 308 QualityToCompression(Q); 309 for (i = 0; i < num_segments; ++i) { 310 // We modulate the base coefficient to accommodate for the quantization 311 // susceptibility and allow denser segments to be quantized more. 312 const double expn = 1. - amp * enc->dqm_[i].alpha_; 313 const double c = pow(c_base, expn); 314 const int q = (int)(127. * (1. - c)); 315 assert(expn > 0.); 316 enc->dqm_[i].quant_ = clip(q, 0, 127); 317 } 318 319 // purely indicative in the bitstream (except for the 1-segment case) 320 enc->base_quant_ = enc->dqm_[0].quant_; 321 322 // fill-in values for the unused segments (required by the syntax) 323 for (i = num_segments; i < NUM_MB_SEGMENTS; ++i) { 324 enc->dqm_[i].quant_ = enc->base_quant_; 325 } 326 327 // uv_alpha_ is normally spread around ~60. The useful range is 328 // typically ~30 (quite bad) to ~100 (ok to decimate UV more). 329 // We map it to the safe maximal range of MAX/MIN_DQ_UV for dq_uv. 330 dq_uv_ac = (enc->uv_alpha_ - MID_ALPHA) * (MAX_DQ_UV - MIN_DQ_UV) 331 / (MAX_ALPHA - MIN_ALPHA); 332 // we rescale by the user-defined strength of adaptation 333 dq_uv_ac = dq_uv_ac * enc->config_->sns_strength / 100; 334 // and make it safe. 335 dq_uv_ac = clip(dq_uv_ac, MIN_DQ_UV, MAX_DQ_UV); 336 // We also boost the dc-uv-quant a little, based on sns-strength, since 337 // U/V channels are quite more reactive to high quants (flat DC-blocks 338 // tend to appear, and are displeasant). 339 dq_uv_dc = -4 * enc->config_->sns_strength / 100; 340 dq_uv_dc = clip(dq_uv_dc, -15, 15); // 4bit-signed max allowed 341 342 enc->dq_y1_dc_ = 0; // TODO(skal): dq-lum 343 enc->dq_y2_dc_ = 0; 344 enc->dq_y2_ac_ = 0; 345 enc->dq_uv_dc_ = dq_uv_dc; 346 enc->dq_uv_ac_ = dq_uv_ac; 347 348 SetupFilterStrength(enc); // initialize segments' filtering, eventually 349 350 if (num_segments > 1) SimplifySegments(enc); 351 352 SetupMatrices(enc); // finalize quantization matrices 353 } 354 355 //------------------------------------------------------------------------------ 356 // Form the predictions in cache 357 358 // Must be ordered using {DC_PRED, TM_PRED, V_PRED, H_PRED} as index 359 const int VP8I16ModeOffsets[4] = { I16DC16, I16TM16, I16VE16, I16HE16 }; 360 const int VP8UVModeOffsets[4] = { C8DC8, C8TM8, C8VE8, C8HE8 }; 361 362 // Must be indexed using {B_DC_PRED -> B_HU_PRED} as index 363 const int VP8I4ModeOffsets[NUM_BMODES] = { 364 I4DC4, I4TM4, I4VE4, I4HE4, I4RD4, I4VR4, I4LD4, I4VL4, I4HD4, I4HU4 365 }; 366 367 void VP8MakeLuma16Preds(const VP8EncIterator* const it) { 368 const VP8Encoder* const enc = it->enc_; 369 const uint8_t* const left = it->x_ ? enc->y_left_ : NULL; 370 const uint8_t* const top = it->y_ ? enc->y_top_ + it->x_ * 16 : NULL; 371 VP8EncPredLuma16(it->yuv_p_, left, top); 372 } 373 374 void VP8MakeChroma8Preds(const VP8EncIterator* const it) { 375 const VP8Encoder* const enc = it->enc_; 376 const uint8_t* const left = it->x_ ? enc->u_left_ : NULL; 377 const uint8_t* const top = it->y_ ? enc->uv_top_ + it->x_ * 16 : NULL; 378 VP8EncPredChroma8(it->yuv_p_, left, top); 379 } 380 381 void VP8MakeIntra4Preds(const VP8EncIterator* const it) { 382 VP8EncPredLuma4(it->yuv_p_, it->i4_top_); 383 } 384 385 //------------------------------------------------------------------------------ 386 // Quantize 387 388 // Layout: 389 // +----+ 390 // |YYYY| 0 391 // |YYYY| 4 392 // |YYYY| 8 393 // |YYYY| 12 394 // +----+ 395 // |UUVV| 16 396 // |UUVV| 20 397 // +----+ 398 399 const int VP8Scan[16 + 4 + 4] = { 400 // Luma 401 0 + 0 * BPS, 4 + 0 * BPS, 8 + 0 * BPS, 12 + 0 * BPS, 402 0 + 4 * BPS, 4 + 4 * BPS, 8 + 4 * BPS, 12 + 4 * BPS, 403 0 + 8 * BPS, 4 + 8 * BPS, 8 + 8 * BPS, 12 + 8 * BPS, 404 0 + 12 * BPS, 4 + 12 * BPS, 8 + 12 * BPS, 12 + 12 * BPS, 405 406 0 + 0 * BPS, 4 + 0 * BPS, 0 + 4 * BPS, 4 + 4 * BPS, // U 407 8 + 0 * BPS, 12 + 0 * BPS, 8 + 4 * BPS, 12 + 4 * BPS // V 408 }; 409 410 //------------------------------------------------------------------------------ 411 // Distortion measurement 412 413 static const uint16_t kWeightY[16] = { 414 38, 32, 20, 9, 32, 28, 17, 7, 20, 17, 10, 4, 9, 7, 4, 2 415 }; 416 417 static const uint16_t kWeightTrellis[16] = { 418 #if USE_TDISTO == 0 419 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16 420 #else 421 30, 27, 19, 11, 422 27, 24, 17, 10, 423 19, 17, 12, 8, 424 11, 10, 8, 6 425 #endif 426 }; 427 428 // Init/Copy the common fields in score. 429 static void InitScore(VP8ModeScore* const rd) { 430 rd->D = 0; 431 rd->SD = 0; 432 rd->R = 0; 433 rd->nz = 0; 434 rd->score = MAX_COST; 435 } 436 437 static void CopyScore(VP8ModeScore* const dst, const VP8ModeScore* const src) { 438 dst->D = src->D; 439 dst->SD = src->SD; 440 dst->R = src->R; 441 dst->nz = src->nz; // note that nz is not accumulated, but just copied. 442 dst->score = src->score; 443 } 444 445 static void AddScore(VP8ModeScore* const dst, const VP8ModeScore* const src) { 446 dst->D += src->D; 447 dst->SD += src->SD; 448 dst->R += src->R; 449 dst->nz |= src->nz; // here, new nz bits are accumulated. 450 dst->score += src->score; 451 } 452 453 //------------------------------------------------------------------------------ 454 // Performs trellis-optimized quantization. 455 456 // Trellis 457 458 typedef struct { 459 int prev; // best previous 460 int level; // level 461 int sign; // sign of coeff_i 462 score_t cost; // bit cost 463 score_t error; // distortion = sum of (|coeff_i| - level_i * Q_i)^2 464 int ctx; // context (only depends on 'level'. Could be spared.) 465 } Node; 466 467 // If a coefficient was quantized to a value Q (using a neutral bias), 468 // we test all alternate possibilities between [Q-MIN_DELTA, Q+MAX_DELTA] 469 // We don't test negative values though. 470 #define MIN_DELTA 0 // how much lower level to try 471 #define MAX_DELTA 1 // how much higher 472 #define NUM_NODES (MIN_DELTA + 1 + MAX_DELTA) 473 #define NODE(n, l) (nodes[(n) + 1][(l) + MIN_DELTA]) 474 475 static WEBP_INLINE void SetRDScore(int lambda, VP8ModeScore* const rd) { 476 // TODO: incorporate the "* 256" in the tables? 477 rd->score = rd->R * lambda + 256 * (rd->D + rd->SD); 478 } 479 480 static WEBP_INLINE score_t RDScoreTrellis(int lambda, score_t rate, 481 score_t distortion) { 482 return rate * lambda + 256 * distortion; 483 } 484 485 static int TrellisQuantizeBlock(const VP8EncIterator* const it, 486 int16_t in[16], int16_t out[16], 487 int ctx0, int coeff_type, 488 const VP8Matrix* const mtx, 489 int lambda) { 490 ProbaArray* const last_costs = it->enc_->proba_.coeffs_[coeff_type]; 491 CostArray* const costs = it->enc_->proba_.level_cost_[coeff_type]; 492 const int first = (coeff_type == 0) ? 1 : 0; 493 Node nodes[17][NUM_NODES]; 494 int best_path[3] = {-1, -1, -1}; // store best-last/best-level/best-previous 495 score_t best_score; 496 int best_node; 497 int last = first - 1; 498 int n, m, p, nz; 499 500 { 501 score_t cost; 502 score_t max_error; 503 const int thresh = mtx->q_[1] * mtx->q_[1] / 4; 504 const int last_proba = last_costs[VP8EncBands[first]][ctx0][0]; 505 506 // compute maximal distortion. 507 max_error = 0; 508 for (n = first; n < 16; ++n) { 509 const int j = kZigzag[n]; 510 const int err = in[j] * in[j]; 511 max_error += kWeightTrellis[j] * err; 512 if (err > thresh) last = n; 513 } 514 // we don't need to go inspect up to n = 16 coeffs. We can just go up 515 // to last + 1 (inclusive) without losing much. 516 if (last < 15) ++last; 517 518 // compute 'skip' score. This is the max score one can do. 519 cost = VP8BitCost(0, last_proba); 520 best_score = RDScoreTrellis(lambda, cost, max_error); 521 522 // initialize source node. 523 n = first - 1; 524 for (m = -MIN_DELTA; m <= MAX_DELTA; ++m) { 525 NODE(n, m).cost = 0; 526 NODE(n, m).error = max_error; 527 NODE(n, m).ctx = ctx0; 528 } 529 } 530 531 // traverse trellis. 532 for (n = first; n <= last; ++n) { 533 const int j = kZigzag[n]; 534 const int Q = mtx->q_[j]; 535 const int iQ = mtx->iq_[j]; 536 const int B = BIAS(0x00); // neutral bias 537 // note: it's important to take sign of the _original_ coeff, 538 // so we don't have to consider level < 0 afterward. 539 const int sign = (in[j] < 0); 540 int coeff0 = (sign ? -in[j] : in[j]) + mtx->sharpen_[j]; 541 int level0; 542 if (coeff0 > 2047) coeff0 = 2047; 543 544 level0 = QUANTDIV(coeff0, iQ, B); 545 // test all alternate level values around level0. 546 for (m = -MIN_DELTA; m <= MAX_DELTA; ++m) { 547 Node* const cur = &NODE(n, m); 548 int delta_error, new_error; 549 score_t cur_score = MAX_COST; 550 int level = level0 + m; 551 int last_proba; 552 553 cur->sign = sign; 554 cur->level = level; 555 cur->ctx = (level == 0) ? 0 : (level == 1) ? 1 : 2; 556 if (level >= 2048 || level < 0) { // node is dead? 557 cur->cost = MAX_COST; 558 continue; 559 } 560 last_proba = last_costs[VP8EncBands[n + 1]][cur->ctx][0]; 561 562 // Compute delta_error = how much coding this level will 563 // subtract as distortion to max_error 564 new_error = coeff0 - level * Q; 565 delta_error = 566 kWeightTrellis[j] * (coeff0 * coeff0 - new_error * new_error); 567 568 // Inspect all possible non-dead predecessors. Retain only the best one. 569 for (p = -MIN_DELTA; p <= MAX_DELTA; ++p) { 570 const Node* const prev = &NODE(n - 1, p); 571 const int prev_ctx = prev->ctx; 572 const uint16_t* const tcost = costs[VP8EncBands[n]][prev_ctx]; 573 const score_t total_error = prev->error - delta_error; 574 score_t cost, base_cost, score; 575 576 if (prev->cost >= MAX_COST) { // dead node? 577 continue; 578 } 579 580 // Base cost of both terminal/non-terminal 581 base_cost = prev->cost + VP8LevelCost(tcost, level); 582 583 // Examine node assuming it's a non-terminal one. 584 cost = base_cost; 585 if (level && n < 15) { 586 cost += VP8BitCost(1, last_proba); 587 } 588 score = RDScoreTrellis(lambda, cost, total_error); 589 if (score < cur_score) { 590 cur_score = score; 591 cur->cost = cost; 592 cur->error = total_error; 593 cur->prev = p; 594 } 595 596 // Now, record best terminal node (and thus best entry in the graph). 597 if (level) { 598 cost = base_cost; 599 if (n < 15) cost += VP8BitCost(0, last_proba); 600 score = RDScoreTrellis(lambda, cost, total_error); 601 if (score < best_score) { 602 best_score = score; 603 best_path[0] = n; // best eob position 604 best_path[1] = m; // best level 605 best_path[2] = p; // best predecessor 606 } 607 } 608 } 609 } 610 } 611 612 // Fresh start 613 memset(in + first, 0, (16 - first) * sizeof(*in)); 614 memset(out + first, 0, (16 - first) * sizeof(*out)); 615 if (best_path[0] == -1) { 616 return 0; // skip! 617 } 618 619 // Unwind the best path. 620 // Note: best-prev on terminal node is not necessarily equal to the 621 // best_prev for non-terminal. So we patch best_path[2] in. 622 n = best_path[0]; 623 best_node = best_path[1]; 624 NODE(n, best_node).prev = best_path[2]; // force best-prev for terminal 625 nz = 0; 626 627 for (; n >= first; --n) { 628 const Node* const node = &NODE(n, best_node); 629 const int j = kZigzag[n]; 630 out[n] = node->sign ? -node->level : node->level; 631 nz |= (node->level != 0); 632 in[j] = out[n] * mtx->q_[j]; 633 best_node = node->prev; 634 } 635 return nz; 636 } 637 638 #undef NODE 639 640 //------------------------------------------------------------------------------ 641 // Performs: difference, transform, quantize, back-transform, add 642 // all at once. Output is the reconstructed block in *yuv_out, and the 643 // quantized levels in *levels. 644 645 static int ReconstructIntra16(VP8EncIterator* const it, 646 VP8ModeScore* const rd, 647 uint8_t* const yuv_out, 648 int mode) { 649 const VP8Encoder* const enc = it->enc_; 650 const uint8_t* const ref = it->yuv_p_ + VP8I16ModeOffsets[mode]; 651 const uint8_t* const src = it->yuv_in_ + Y_OFF; 652 const VP8SegmentInfo* const dqm = &enc->dqm_[it->mb_->segment_]; 653 int nz = 0; 654 int n; 655 int16_t tmp[16][16], dc_tmp[16]; 656 657 for (n = 0; n < 16; ++n) { 658 VP8FTransform(src + VP8Scan[n], ref + VP8Scan[n], tmp[n]); 659 } 660 VP8FTransformWHT(tmp[0], dc_tmp); 661 nz |= VP8EncQuantizeBlock(dc_tmp, rd->y_dc_levels, 0, &dqm->y2_) << 24; 662 663 if (DO_TRELLIS_I16 && it->do_trellis_) { 664 int x, y; 665 VP8IteratorNzToBytes(it); 666 for (y = 0, n = 0; y < 4; ++y) { 667 for (x = 0; x < 4; ++x, ++n) { 668 const int ctx = it->top_nz_[x] + it->left_nz_[y]; 669 const int non_zero = 670 TrellisQuantizeBlock(it, tmp[n], rd->y_ac_levels[n], ctx, 0, 671 &dqm->y1_, dqm->lambda_trellis_i16_); 672 it->top_nz_[x] = it->left_nz_[y] = non_zero; 673 nz |= non_zero << n; 674 } 675 } 676 } else { 677 for (n = 0; n < 16; ++n) { 678 nz |= VP8EncQuantizeBlock(tmp[n], rd->y_ac_levels[n], 1, &dqm->y1_) << n; 679 } 680 } 681 682 // Transform back 683 VP8ITransformWHT(dc_tmp, tmp[0]); 684 for (n = 0; n < 16; n += 2) { 685 VP8ITransform(ref + VP8Scan[n], tmp[n], yuv_out + VP8Scan[n], 1); 686 } 687 688 return nz; 689 } 690 691 static int ReconstructIntra4(VP8EncIterator* const it, 692 int16_t levels[16], 693 const uint8_t* const src, 694 uint8_t* const yuv_out, 695 int mode) { 696 const VP8Encoder* const enc = it->enc_; 697 const uint8_t* const ref = it->yuv_p_ + VP8I4ModeOffsets[mode]; 698 const VP8SegmentInfo* const dqm = &enc->dqm_[it->mb_->segment_]; 699 int nz = 0; 700 int16_t tmp[16]; 701 702 VP8FTransform(src, ref, tmp); 703 if (DO_TRELLIS_I4 && it->do_trellis_) { 704 const int x = it->i4_ & 3, y = it->i4_ >> 2; 705 const int ctx = it->top_nz_[x] + it->left_nz_[y]; 706 nz = TrellisQuantizeBlock(it, tmp, levels, ctx, 3, &dqm->y1_, 707 dqm->lambda_trellis_i4_); 708 } else { 709 nz = VP8EncQuantizeBlock(tmp, levels, 0, &dqm->y1_); 710 } 711 VP8ITransform(ref, tmp, yuv_out, 0); 712 return nz; 713 } 714 715 static int ReconstructUV(VP8EncIterator* const it, VP8ModeScore* const rd, 716 uint8_t* const yuv_out, int mode) { 717 const VP8Encoder* const enc = it->enc_; 718 const uint8_t* const ref = it->yuv_p_ + VP8UVModeOffsets[mode]; 719 const uint8_t* const src = it->yuv_in_ + U_OFF; 720 const VP8SegmentInfo* const dqm = &enc->dqm_[it->mb_->segment_]; 721 int nz = 0; 722 int n; 723 int16_t tmp[8][16]; 724 725 for (n = 0; n < 8; ++n) { 726 VP8FTransform(src + VP8Scan[16 + n], ref + VP8Scan[16 + n], tmp[n]); 727 } 728 if (DO_TRELLIS_UV && it->do_trellis_) { 729 int ch, x, y; 730 for (ch = 0, n = 0; ch <= 2; ch += 2) { 731 for (y = 0; y < 2; ++y) { 732 for (x = 0; x < 2; ++x, ++n) { 733 const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y]; 734 const int non_zero = 735 TrellisQuantizeBlock(it, tmp[n], rd->uv_levels[n], ctx, 2, 736 &dqm->uv_, dqm->lambda_trellis_uv_); 737 it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] = non_zero; 738 nz |= non_zero << n; 739 } 740 } 741 } 742 } else { 743 for (n = 0; n < 8; ++n) { 744 nz |= VP8EncQuantizeBlock(tmp[n], rd->uv_levels[n], 0, &dqm->uv_) << n; 745 } 746 } 747 748 for (n = 0; n < 8; n += 2) { 749 VP8ITransform(ref + VP8Scan[16 + n], tmp[n], yuv_out + VP8Scan[16 + n], 1); 750 } 751 return (nz << 16); 752 } 753 754 //------------------------------------------------------------------------------ 755 // RD-opt decision. Reconstruct each modes, evalue distortion and bit-cost. 756 // Pick the mode is lower RD-cost = Rate + lamba * Distortion. 757 758 static void SwapPtr(uint8_t** a, uint8_t** b) { 759 uint8_t* const tmp = *a; 760 *a = *b; 761 *b = tmp; 762 } 763 764 static void SwapOut(VP8EncIterator* const it) { 765 SwapPtr(&it->yuv_out_, &it->yuv_out2_); 766 } 767 768 static void PickBestIntra16(VP8EncIterator* const it, VP8ModeScore* const rd) { 769 const VP8Encoder* const enc = it->enc_; 770 const VP8SegmentInfo* const dqm = &enc->dqm_[it->mb_->segment_]; 771 const int lambda = dqm->lambda_i16_; 772 const int tlambda = dqm->tlambda_; 773 const uint8_t* const src = it->yuv_in_ + Y_OFF; 774 VP8ModeScore rd16; 775 int mode; 776 777 rd->mode_i16 = -1; 778 for (mode = 0; mode < NUM_PRED_MODES; ++mode) { 779 uint8_t* const tmp_dst = it->yuv_out2_ + Y_OFF; // scratch buffer 780 int nz; 781 782 // Reconstruct 783 nz = ReconstructIntra16(it, &rd16, tmp_dst, mode); 784 785 // Measure RD-score 786 rd16.D = VP8SSE16x16(src, tmp_dst); 787 rd16.SD = tlambda ? MULT_8B(tlambda, VP8TDisto16x16(src, tmp_dst, kWeightY)) 788 : 0; 789 rd16.R = VP8GetCostLuma16(it, &rd16); 790 rd16.R += VP8FixedCostsI16[mode]; 791 792 // Since we always examine Intra16 first, we can overwrite *rd directly. 793 SetRDScore(lambda, &rd16); 794 if (mode == 0 || rd16.score < rd->score) { 795 CopyScore(rd, &rd16); 796 rd->mode_i16 = mode; 797 rd->nz = nz; 798 memcpy(rd->y_ac_levels, rd16.y_ac_levels, sizeof(rd16.y_ac_levels)); 799 memcpy(rd->y_dc_levels, rd16.y_dc_levels, sizeof(rd16.y_dc_levels)); 800 SwapOut(it); 801 } 802 } 803 SetRDScore(dqm->lambda_mode_, rd); // finalize score for mode decision. 804 VP8SetIntra16Mode(it, rd->mode_i16); 805 } 806 807 //------------------------------------------------------------------------------ 808 809 // return the cost array corresponding to the surrounding prediction modes. 810 static const uint16_t* GetCostModeI4(VP8EncIterator* const it, 811 const uint8_t modes[16]) { 812 const int preds_w = it->enc_->preds_w_; 813 const int x = (it->i4_ & 3), y = it->i4_ >> 2; 814 const int left = (x == 0) ? it->preds_[y * preds_w - 1] : modes[it->i4_ - 1]; 815 const int top = (y == 0) ? it->preds_[-preds_w + x] : modes[it->i4_ - 4]; 816 return VP8FixedCostsI4[top][left]; 817 } 818 819 static int PickBestIntra4(VP8EncIterator* const it, VP8ModeScore* const rd) { 820 const VP8Encoder* const enc = it->enc_; 821 const VP8SegmentInfo* const dqm = &enc->dqm_[it->mb_->segment_]; 822 const int lambda = dqm->lambda_i4_; 823 const int tlambda = dqm->tlambda_; 824 const uint8_t* const src0 = it->yuv_in_ + Y_OFF; 825 uint8_t* const best_blocks = it->yuv_out2_ + Y_OFF; 826 int total_header_bits = 0; 827 VP8ModeScore rd_best; 828 829 if (enc->max_i4_header_bits_ == 0) { 830 return 0; 831 } 832 833 InitScore(&rd_best); 834 rd_best.score = 211; // '211' is the value of VP8BitCost(0, 145) 835 VP8IteratorStartI4(it); 836 do { 837 VP8ModeScore rd_i4; 838 int mode; 839 int best_mode = -1; 840 const uint8_t* const src = src0 + VP8Scan[it->i4_]; 841 const uint16_t* const mode_costs = GetCostModeI4(it, rd->modes_i4); 842 uint8_t* best_block = best_blocks + VP8Scan[it->i4_]; 843 uint8_t* tmp_dst = it->yuv_p_ + I4TMP; // scratch buffer. 844 845 InitScore(&rd_i4); 846 VP8MakeIntra4Preds(it); 847 for (mode = 0; mode < NUM_BMODES; ++mode) { 848 VP8ModeScore rd_tmp; 849 int16_t tmp_levels[16]; 850 851 // Reconstruct 852 rd_tmp.nz = 853 ReconstructIntra4(it, tmp_levels, src, tmp_dst, mode) << it->i4_; 854 855 // Compute RD-score 856 rd_tmp.D = VP8SSE4x4(src, tmp_dst); 857 rd_tmp.SD = 858 tlambda ? MULT_8B(tlambda, VP8TDisto4x4(src, tmp_dst, kWeightY)) 859 : 0; 860 rd_tmp.R = VP8GetCostLuma4(it, tmp_levels); 861 rd_tmp.R += mode_costs[mode]; 862 863 SetRDScore(lambda, &rd_tmp); 864 if (best_mode < 0 || rd_tmp.score < rd_i4.score) { 865 CopyScore(&rd_i4, &rd_tmp); 866 best_mode = mode; 867 SwapPtr(&tmp_dst, &best_block); 868 memcpy(rd_best.y_ac_levels[it->i4_], tmp_levels, sizeof(tmp_levels)); 869 } 870 } 871 SetRDScore(dqm->lambda_mode_, &rd_i4); 872 AddScore(&rd_best, &rd_i4); 873 total_header_bits += mode_costs[best_mode]; 874 if (rd_best.score >= rd->score || 875 total_header_bits > enc->max_i4_header_bits_) { 876 return 0; 877 } 878 // Copy selected samples if not in the right place already. 879 if (best_block != best_blocks + VP8Scan[it->i4_]) 880 VP8Copy4x4(best_block, best_blocks + VP8Scan[it->i4_]); 881 rd->modes_i4[it->i4_] = best_mode; 882 it->top_nz_[it->i4_ & 3] = it->left_nz_[it->i4_ >> 2] = (rd_i4.nz ? 1 : 0); 883 } while (VP8IteratorRotateI4(it, best_blocks)); 884 885 // finalize state 886 CopyScore(rd, &rd_best); 887 VP8SetIntra4Mode(it, rd->modes_i4); 888 SwapOut(it); 889 memcpy(rd->y_ac_levels, rd_best.y_ac_levels, sizeof(rd->y_ac_levels)); 890 return 1; // select intra4x4 over intra16x16 891 } 892 893 //------------------------------------------------------------------------------ 894 895 static void PickBestUV(VP8EncIterator* const it, VP8ModeScore* const rd) { 896 const VP8Encoder* const enc = it->enc_; 897 const VP8SegmentInfo* const dqm = &enc->dqm_[it->mb_->segment_]; 898 const int lambda = dqm->lambda_uv_; 899 const uint8_t* const src = it->yuv_in_ + U_OFF; 900 uint8_t* const tmp_dst = it->yuv_out2_ + U_OFF; // scratch buffer 901 uint8_t* const dst0 = it->yuv_out_ + U_OFF; 902 VP8ModeScore rd_best; 903 int mode; 904 905 rd->mode_uv = -1; 906 InitScore(&rd_best); 907 for (mode = 0; mode < NUM_PRED_MODES; ++mode) { 908 VP8ModeScore rd_uv; 909 910 // Reconstruct 911 rd_uv.nz = ReconstructUV(it, &rd_uv, tmp_dst, mode); 912 913 // Compute RD-score 914 rd_uv.D = VP8SSE16x8(src, tmp_dst); 915 rd_uv.SD = 0; // TODO: should we call TDisto? it tends to flatten areas. 916 rd_uv.R = VP8GetCostUV(it, &rd_uv); 917 rd_uv.R += VP8FixedCostsUV[mode]; 918 919 SetRDScore(lambda, &rd_uv); 920 if (mode == 0 || rd_uv.score < rd_best.score) { 921 CopyScore(&rd_best, &rd_uv); 922 rd->mode_uv = mode; 923 memcpy(rd->uv_levels, rd_uv.uv_levels, sizeof(rd->uv_levels)); 924 memcpy(dst0, tmp_dst, UV_SIZE); // TODO: SwapUVOut() ? 925 } 926 } 927 VP8SetIntraUVMode(it, rd->mode_uv); 928 AddScore(rd, &rd_best); 929 } 930 931 //------------------------------------------------------------------------------ 932 // Final reconstruction and quantization. 933 934 static void SimpleQuantize(VP8EncIterator* const it, VP8ModeScore* const rd) { 935 const VP8Encoder* const enc = it->enc_; 936 const int is_i16 = (it->mb_->type_ == 1); 937 int nz = 0; 938 939 if (is_i16) { 940 nz = ReconstructIntra16(it, rd, it->yuv_out_ + Y_OFF, it->preds_[0]); 941 } else { 942 VP8IteratorStartI4(it); 943 do { 944 const int mode = 945 it->preds_[(it->i4_ & 3) + (it->i4_ >> 2) * enc->preds_w_]; 946 const uint8_t* const src = it->yuv_in_ + Y_OFF + VP8Scan[it->i4_]; 947 uint8_t* const dst = it->yuv_out_ + Y_OFF + VP8Scan[it->i4_]; 948 VP8MakeIntra4Preds(it); 949 nz |= ReconstructIntra4(it, rd->y_ac_levels[it->i4_], 950 src, dst, mode) << it->i4_; 951 } while (VP8IteratorRotateI4(it, it->yuv_out_ + Y_OFF)); 952 } 953 954 nz |= ReconstructUV(it, rd, it->yuv_out_ + U_OFF, it->mb_->uv_mode_); 955 rd->nz = nz; 956 } 957 958 // Refine intra16/intra4 sub-modes based on distortion only (not rate). 959 static void DistoRefine(VP8EncIterator* const it, int try_both_i4_i16) { 960 const int is_i16 = (it->mb_->type_ == 1); 961 score_t best_score = MAX_COST; 962 963 if (try_both_i4_i16 || is_i16) { 964 int mode; 965 int best_mode = -1; 966 for (mode = 0; mode < NUM_PRED_MODES; ++mode) { 967 const uint8_t* const ref = it->yuv_p_ + VP8I16ModeOffsets[mode]; 968 const uint8_t* const src = it->yuv_in_ + Y_OFF; 969 const score_t score = VP8SSE16x16(src, ref); 970 if (score < best_score) { 971 best_mode = mode; 972 best_score = score; 973 } 974 } 975 VP8SetIntra16Mode(it, best_mode); 976 } 977 if (try_both_i4_i16 || !is_i16) { 978 uint8_t modes_i4[16]; 979 // We don't evaluate the rate here, but just account for it through a 980 // constant penalty (i4 mode usually needs more bits compared to i16). 981 score_t score_i4 = (score_t)I4_PENALTY; 982 983 VP8IteratorStartI4(it); 984 do { 985 int mode; 986 int best_sub_mode = -1; 987 score_t best_sub_score = MAX_COST; 988 const uint8_t* const src = it->yuv_in_ + Y_OFF + VP8Scan[it->i4_]; 989 990 // TODO(skal): we don't really need the prediction pixels here, 991 // but just the distortion against 'src'. 992 VP8MakeIntra4Preds(it); 993 for (mode = 0; mode < NUM_BMODES; ++mode) { 994 const uint8_t* const ref = it->yuv_p_ + VP8I4ModeOffsets[mode]; 995 const score_t score = VP8SSE4x4(src, ref); 996 if (score < best_sub_score) { 997 best_sub_mode = mode; 998 best_sub_score = score; 999 } 1000 } 1001 modes_i4[it->i4_] = best_sub_mode; 1002 score_i4 += best_sub_score; 1003 if (score_i4 >= best_score) break; 1004 } while (VP8IteratorRotateI4(it, it->yuv_in_ + Y_OFF)); 1005 if (score_i4 < best_score) { 1006 VP8SetIntra4Mode(it, modes_i4); 1007 } 1008 } 1009 } 1010 1011 //------------------------------------------------------------------------------ 1012 // Entry point 1013 1014 int VP8Decimate(VP8EncIterator* const it, VP8ModeScore* const rd, 1015 VP8RDLevel rd_opt) { 1016 int is_skipped; 1017 const int method = it->enc_->method_; 1018 1019 InitScore(rd); 1020 1021 // We can perform predictions for Luma16x16 and Chroma8x8 already. 1022 // Luma4x4 predictions needs to be done as-we-go. 1023 VP8MakeLuma16Preds(it); 1024 VP8MakeChroma8Preds(it); 1025 1026 if (rd_opt > RD_OPT_NONE) { 1027 it->do_trellis_ = (rd_opt >= RD_OPT_TRELLIS_ALL); 1028 PickBestIntra16(it, rd); 1029 if (method >= 2) { 1030 PickBestIntra4(it, rd); 1031 } 1032 PickBestUV(it, rd); 1033 if (rd_opt == RD_OPT_TRELLIS) { // finish off with trellis-optim now 1034 it->do_trellis_ = 1; 1035 SimpleQuantize(it, rd); 1036 } 1037 } else { 1038 // For method == 2, pick the best intra4/intra16 based on SSE (~tad slower). 1039 // For method <= 1, we refine intra4 or intra16 (but don't re-examine mode). 1040 DistoRefine(it, (method >= 2)); 1041 SimpleQuantize(it, rd); 1042 } 1043 is_skipped = (rd->nz == 0); 1044 VP8SetSkip(it, is_skipped); 1045 return is_skipped; 1046 } 1047 1048 #if defined(__cplusplus) || defined(c_plusplus) 1049 } // extern "C" 1050 #endif 1051
