/* * Copyright (c) 2001-2016, Alliance for Open Media. All rights reserved * * This source code is subject to the terms of the BSD 2 Clause License and * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License * was not distributed with this source code in the LICENSE file, you can * obtain it at www.aomedia.org/license/software. If the Alliance for Open * Media Patent License 1.0 was not distributed with this source code in the * PATENTS file, you can obtain it at www.aomedia.org/license/patent. */ /* clang-format off */ #ifdef HAVE_CONFIG_H # include "config.h" #endif #include #include "aom_dsp/entdec.h" #include "aom_dsp/entenc.h" #include "av1/common/generic_code.h" #include "av1/common/odintrin.h" #include "pvq_encoder.h" /** Encodes a value from 0 to N-1 (with N up to 16) based on a cdf and adapts * the cdf accordingly. * * @param [in,out] enc range encoder * @param [in] val variable being encoded * @param [in,out] cdf CDF of the variable (Q15) * @param [in] n number of values possible * @param [in,out] count number of symbols encoded with that cdf so far * @param [in] rate adaptation rate shift (smaller is faster) */ void od_encode_cdf_adapt_q15(od_ec_enc *ec, int val, uint16_t *cdf, int n, int *count, int rate) { int i; if (*count == 0) { /* On the first call, we normalize the cdf to (32768 - n). This should eventually be moved to the state init, but for now it makes it much easier to experiment and convert symbols to the Q15 adaptation.*/ int ft; ft = cdf[n - 1]; for (i = 0; i < n; i++) { cdf[i] = cdf[i]*32768/ft; } } od_ec_encode_cdf_q15(ec, val, cdf, n); aom_cdf_adapt_q15(val, cdf, n, count, rate); } /** Encodes a value from 0 to N-1 (with N up to 16) based on a cdf and adapts * the cdf accordingly. * * @param [in,out] enc range encoder * @param [in] val variable being encoded * @param [in] cdf CDF of the variable (Q15) * @param [in] n number of values possible * @param [in] increment adaptation speed (Q15) */ void od_encode_cdf_adapt(od_ec_enc *ec, int val, uint16_t *cdf, int n, int increment) { int i; od_ec_encode_cdf_unscaled(ec, val, cdf, n); if (cdf[n-1] + increment > 32767) { for (i = 0; i < n; i++) { /* Second term ensures that the pdf is non-null */ cdf[i] = (cdf[i] >> 1) + i + 1; } } for (i = val; i < n; i++) cdf[i] += increment; } /** Encodes a random variable using a "generic" model, assuming that the * distribution is one-sided (zero and up), has a single mode, and decays * exponentially past the model. * * @param [in,out] enc range encoder * @param [in,out] model generic probability model * @param [in] x variable being encoded * @param [in] max largest value possible * @param [in,out] ExQ16 expectation of x (adapted) * @param [in] integration integration period of ExQ16 (leaky average over * 1<> 1); /* Choose the cdf to use: we have two per "octave" of ExQ16 */ id = OD_MINI(GENERIC_TABLES - 1, lg_q1); cdf = model->cdf[id]; xs = (x + (1 << shift >> 1)) >> shift; ms = (max + (1 << shift >> 1)) >> shift; OD_ASSERT(max == -1 || xs <= ms); if (max == -1) od_ec_encode_cdf_unscaled(enc, OD_MINI(15, xs), cdf, 16); else { od_ec_encode_cdf_unscaled(enc, OD_MINI(15, xs), cdf, OD_MINI(ms + 1, 16)); } if (xs >= 15) { int e; unsigned decay; /* Estimate decay based on the assumption that the distribution is close to Laplacian for large values. We should probably have an adaptive estimate instead. Note: The 2* is a kludge that's not fully understood yet. */ OD_ASSERT(*ex_q16 < INT_MAX >> 1); e = ((2**ex_q16 >> 8) + (1 << shift >> 1)) >> shift; decay = OD_MAXI(2, OD_MINI(254, 256*e/(e + 256))); /* Encode the tail of the distribution assuming exponential decay. */ od_laplace_encode_special(enc, xs - 15, decay, (max == -1) ? -1 : ms - 15); } if (shift != 0) { int special; /* Because of the rounding, there's only half the number of possibilities for xs=0. */ special = xs == 0; if (shift - special > 0) { od_ec_enc_bits(enc, x - (xs << shift) + (!special << (shift - 1)), shift - special); } } generic_model_update(model, ex_q16, x, xs, id, integration); OD_LOG((OD_LOG_ENTROPY_CODER, OD_LOG_DEBUG, "enc: %d %d %d %d %d %x", *ex_q16, x, shift, id, xs, enc->rng)); } /** Estimates the cost of encoding a value with generic_encode(). * * @param [in,out] model generic probability model * @param [in] x variable being encoded * @param [in] max largest value possible * @param [in,out] ExQ16 expectation of x (adapted) * @return number of bits (approximation) */ double generic_encode_cost(generic_encoder *model, int x, int max, int *ex_q16) { int lg_q1; int shift; int id; uint16_t *cdf; int xs; int ms; int extra; if (max == 0) return 0; lg_q1 = log_ex(*ex_q16); /* If expectation is too large, shift x to ensure that all we have past xs=15 is the exponentially decaying tail of the distribution */ shift = OD_MAXI(0, (lg_q1 - 5) >> 1); /* Choose the cdf to use: we have two per "octave" of ExQ16 */ id = OD_MINI(GENERIC_TABLES - 1, lg_q1); cdf = model->cdf[id]; xs = (x + (1 << shift >> 1)) >> shift; ms = (max + (1 << shift >> 1)) >> shift; OD_ASSERT(max == -1 || xs <= ms); extra = 0; if (shift) extra = shift - (xs == 0); xs = OD_MINI(15, xs); /* Shortcut: assume it's going to cost 2 bits for the Laplace coder. */ if (xs == 15) extra += 2; if (max == -1) { return extra - OD_LOG2((double)(cdf[xs] - (xs == 0 ? 0 : cdf[xs - 1]))/ cdf[15]); } else { return extra - OD_LOG2((double)(cdf[xs] - (xs == 0 ? 0 : cdf[xs - 1]))/ cdf[OD_MINI(ms, 15)]); } } /*Estimates the cost of encoding a value with a given CDF.*/ double od_encode_cdf_cost(int val, uint16_t *cdf, int n) { int total_prob; int prev_prob; double val_prob; OD_ASSERT(n > 0); total_prob = cdf[n - 1]; if (val == 0) { prev_prob = 0; } else { prev_prob = cdf[val - 1]; } val_prob = (cdf[val] - prev_prob) / (double)total_prob; return -OD_LOG2(val_prob); }