generic_encoder.c 6.01 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/*
 * 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 <stdio.h>

20
#include "aom_dsp/bitwriter.h"
21 22 23 24 25 26 27
#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.
 *
28
 * @param [in,out] w     multi-symbol entropy encoder
29 30 31 32 33 34
 * @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)
 */
35
void aom_encode_cdf_adapt_q15(aom_writer *w, int val, uint16_t *cdf, int n,
36 37 38 39 40 41 42 43 44 45 46 47
 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;
    }
  }
48
  aom_write_cdf(w, val, cdf, n);
49
  aom_cdf_adapt_q15(val, cdf, n, count, rate);
50 51 52 53 54 55 56 57 58 59 60
}

/** 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)
 */
61
void aom_encode_cdf_adapt(aom_writer *w, int val, uint16_t *cdf, int n,
62 63
 int increment) {
  int i;
64
  aom_write_cdf_unscaled(w, val, cdf, n);
65 66 67 68 69 70 71 72 73 74 75 76 77
  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.
 *
78
 * @param [in,out] w     multi-symbol entropy encoder
79 80 81 82 83 84
 * @param [in,out] model generic probability model
 * @param [in]     x     variable being encoded
 * @param [in,out] ExQ16 expectation of x (adapted)
 * @param [in]     integration integration period of ExQ16 (leaky average over
 * 1<<integration samples)
 */
85
void generic_encode(aom_writer *w, generic_encoder *model, int x,
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
 int *ex_q16, int integration) {
  int lg_q1;
  int shift;
  int id;
  uint16_t *cdf;
  int xs;
  lg_q1 = log_ex(*ex_q16);
  OD_LOG((OD_LOG_ENTROPY_CODER, OD_LOG_DEBUG,
   "%d %d", *ex_q16, lg_q1));
  /* 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;
103
  aom_write_symbol_pvq(w, OD_MINI(15, xs), cdf, 16);
104 105 106 107 108 109 110 111 112 113 114
  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. */
115
    aom_laplace_encode_special(w, xs - 15, decay);
116 117 118 119 120 121 122
  }
  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) {
123
      aom_write_literal(w, x - (xs << shift) + (!special << (shift - 1)),
124 125 126
       shift - special);
    }
  }
127
  generic_model_update(ex_q16, x, integration);
128 129 130 131 132 133 134 135 136 137 138
  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,out] ExQ16 expectation of x (adapted)
 * @return number of bits (approximation)
 */
139
double generic_encode_cost(generic_encoder *model, int x, int *ex_q16) {
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
  int lg_q1;
  int shift;
  int id;
  uint16_t *cdf;
  int xs;
  int extra;
  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;
  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;
160 161
  return
      extra - OD_LOG2((double)(cdf[xs] - (xs == 0 ? 0 : cdf[xs - 1]))/cdf[15]);
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
}

/*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);
}