av1/encoder/laplace_encoder.c

/*
 * 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>

#include "aom_dsp/entdec.h"
#include "aom_dsp/entenc.h"
#include "av1/common/odintrin.h"
#include "av1/common/pvq.h"
#include "pvq_encoder.h"

static void od_encode_pvq_split(od_ec_enc *ec, od_pvq_codeword_ctx *adapt,
 int count, int sum, int ctx) {
  int shift;
  int rest;
  int fctx;
  if (sum == 0) return;
  shift = OD_MAXI(0, OD_ILOG(sum) - 3);
  if (shift) {
    rest = count & ((1 << shift) - 1);
    count >>= shift;
    sum >>= shift;
  }
  fctx = 7*ctx + sum - 1;
  od_encode_cdf_adapt(ec, count, adapt->pvq_split_cdf[fctx],
   sum + 1, adapt->pvq_split_increment);
  if (shift) od_ec_enc_bits(ec, rest, shift);
}

void od_encode_band_pvq_splits(od_ec_enc *ec, od_pvq_codeword_ctx *adapt,
 const int *y, int n, int k, int level) {
  int mid;
  int i;
  int count_right;
  if (n <= 1 || k == 0) return;
  if (k == 1 && n <= 16) {
    int cdf_id;
    int pos;
    cdf_id = od_pvq_k1_ctx(n, level == 0);
    for (pos = 0; !y[pos]; pos++);
    OD_ASSERT(pos < n);
    od_encode_cdf_adapt(ec, pos, adapt->pvq_k1_cdf[cdf_id], n,
     adapt->pvq_k1_increment);
  }
  else {
    mid = n >> 1;
    count_right = k;
    for (i = 0; i < mid; i++) count_right -= abs(y[i]);
    od_encode_pvq_split(ec, adapt, count_right, k, od_pvq_size_ctx(n));
    od_encode_band_pvq_splits(ec, adapt, y, mid, k - count_right, level + 1);
    od_encode_band_pvq_splits(ec, adapt, y + mid, n - mid, count_right,
     level + 1);
  }
}

/** Encodes the tail of a Laplace-distributed variable, i.e. it doesn't
 * do anything special for the zero case.
 *
 * @param [in,out] enc     range encoder
 * @param [in]     x       variable to encode (has to be positive)
 * @param [in]     decay   decay factor of the distribution in Q8 format,
 * i.e. pdf ~= decay^x
 * @param [in]     max     maximum possible value of x (used to truncate
 * the pdf)
 */
void od_laplace_encode_special(od_ec_enc *enc, int x, unsigned decay, int max) {
  int shift;
  int xs;
  int ms;
  int sym;
  const uint16_t *cdf;
  shift = 0;
  if (max == 0) return;
  /* We don't want a large decay value because that would require too many
     symbols. However, it's OK if the max is below 15. */
  while (((max >> shift) >= 15 || max == -1) && decay > 235) {
    decay = (decay*decay + 128) >> 8;
    shift++;
  }
  OD_ASSERT(x <= max || max == -1);
  decay = OD_MINI(decay, 254);
  decay = OD_MAXI(decay, 2);
  xs = x >> shift;
  ms = max >> shift;
  cdf = EXP_CDF_TABLE[(decay + 1) >> 1];
  OD_LOG((OD_LOG_PVQ, OD_LOG_DEBUG, "decay = %d", decay));
  do {
    sym = OD_MINI(xs, 15);
    {
      int i;
      OD_LOG((OD_LOG_PVQ, OD_LOG_DEBUG, "%d %d %d %d %d\n", x, xs, shift,
       sym, max));
      for (i = 0; i < 16; i++) {
        OD_LOG_PARTIAL((OD_LOG_PVQ, OD_LOG_DEBUG, "%d ", cdf[i]));
      }
      OD_LOG_PARTIAL((OD_LOG_PVQ, OD_LOG_DEBUG, "\n"));
    }
    if (ms > 0 && ms < 15) {
      /* Simple way of truncating the pdf when we have a bound */
      od_ec_encode_cdf_unscaled(enc, sym, cdf, ms + 1);
    }
    else {
      od_ec_encode_cdf_q15(enc, sym, cdf, 16);
    }
    xs -= 15;
    ms -= 15;
  }
  while (sym >= 15 && ms != 0);
  if (shift) od_ec_enc_bits(enc, x & ((1 << shift) - 1), shift);
}

/** Encodes a Laplace-distributed variable for use in PVQ
 *
 * @param [in,out] enc  range encoder
 * @param [in]     x    variable to encode (including sign)
 * @param [in]     ExQ8 expectation of the absolute value of x in Q8
 * @param [in]     K    maximum value of |x|
 */
void od_laplace_encode(od_ec_enc *enc, int x, int ex_q8, int k) {
  int j;
  int shift;
  int xs;
  uint16_t cdf[16];
  int sym;
  int decay;
  int offset;
  /* shift down x if expectation is too high */
  shift = OD_ILOG(ex_q8) - 11;
  if (shift < 0) shift = 0;
  /* Apply the shift with rounding to Ex, K and xs */
  ex_q8 = (ex_q8 + (1 << shift >> 1)) >> shift;
  k = (k + (1 << shift >> 1)) >> shift;
  xs = (x + (1 << shift >> 1)) >> shift;
  decay = OD_MINI(254, 256*ex_q8/(ex_q8 + 256));
  offset = LAPLACE_OFFSET[(decay + 1) >> 1];
  for (j = 0; j < 16; j++) {
    cdf[j] = EXP_CDF_TABLE[(decay + 1) >> 1][j] - offset;
  }
  sym = xs;
  if (sym > 15) sym = 15;
  /* Simple way of truncating the pdf when we have a bound */
  if (k != 0) od_ec_encode_cdf_unscaled(enc, sym, cdf, OD_MINI(k + 1, 16));
  if (shift) {
    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);
    }
  }
  /* Handle the exponentially-decaying tail of the distribution */
  OD_ASSERT(xs - 15 <= k - 15);
  if (xs >= 15) od_laplace_encode_special(enc, xs - 15, decay, k - 15);
}

static void laplace_encode_vector_delta(od_ec_enc *enc, const od_coeff *y, int n, int k,
                                        int32_t *curr, const int32_t *means) {
  int i;
  int prev;
  int sum_ex;
  int sum_c;
  int first;
  int k_left;
  int coef;
  prev = 0;
  sum_ex = 0;
  sum_c = 0;
  first = 1;
  k_left = k;
  coef = 256*means[OD_ADAPT_COUNT_Q8]/
   (1 + means[OD_ADAPT_COUNT_EX_Q8]);
  coef = OD_MAXI(coef, 1);
  for (i = 0; i < n; i++) {
    if (y[i] != 0) {
      int j;
      int count;
      int mag;
      mag = abs(y[i]);
      count = i - prev;
      if (first) {
        int decay;
        int ex = coef*(n - prev)/k_left;
        if (ex > 65280) decay = 255;
        else {
          decay = OD_MINI(255,
           (int)((256*ex/(ex + 256) + (ex>>5)*ex/((n + 1)*(n - 1)*(n - 1)))));
        }
        /*Update mean position.*/
        OD_ASSERT(count <= n - 1);
        od_laplace_encode_special(enc, count, decay, n - 1);
        first = 0;
      }
      else od_laplace_encode(enc, count, coef*(n - prev)/k_left, n - prev - 1);
      sum_ex += 256*(n - prev);
      sum_c += count*k_left;
      od_ec_enc_bits(enc, y[i] < 0, 1);
      for (j = 0; j < mag - 1; j++) {
        od_laplace_encode(enc, 0, coef*(n - i)/(k_left - 1 - j), n - i - 1);
        sum_ex += 256*(n - i);
      }
      k_left -= mag;
      prev = i;
      if (k_left == 0) break;
    }
  }
  if (k > 0) {
    curr[OD_ADAPT_COUNT_Q8] = 256*sum_c;
    curr[OD_ADAPT_COUNT_EX_Q8] = sum_ex;
  }
  else {
    curr[OD_ADAPT_COUNT_Q8] = OD_ADAPT_NO_VALUE;
    curr[OD_ADAPT_COUNT_EX_Q8] = OD_ADAPT_NO_VALUE;
  }
  curr[OD_ADAPT_K_Q8] = 0;
  curr[OD_ADAPT_SUM_EX_Q8] = 0;
}

/** Encodes a vector of integers assumed to come from rounding a sequence of
 * Laplace-distributed real values in decreasing order of variance.
 *
 * @param [in,out] enc range encoder
 * @param [in]     y     vector to encode
 * @param [in]     N     dimension of the vector
 * @param [in]     K     sum of the absolute value of components of y
 * @param [out]    curr  Adaptation context output, may alias means.
 * @param [in]     means Adaptation context input.
 */
void od_laplace_encode_vector(od_ec_enc *enc, const od_coeff *y, int n, int k,
                           int32_t *curr, const int32_t *means) {
  int i;
  int sum_ex;
  int kn;
  int exp_q8;
  int mean_k_q8;
  int mean_sum_ex_q8;
  int ran_delta;
  ran_delta = 0;
  if (k <= 1) {
    laplace_encode_vector_delta(enc, y, n, k, curr, means);
    return;
  }
  sum_ex = 0;
  kn = k;
  /* Estimates the factor relating pulses_left and positions_left to E(|x|) */
  mean_k_q8 = means[OD_ADAPT_K_Q8];
  mean_sum_ex_q8 = means[OD_ADAPT_SUM_EX_Q8];
  if (mean_k_q8 < 1 << 23) exp_q8 = 256*mean_k_q8/(1 + mean_sum_ex_q8);
  else exp_q8 = mean_k_q8/(1 + (mean_sum_ex_q8 >> 8));
  for (i = 0; i < n; i++) {
    int ex;
    int x;
    if (kn == 0) break;
    if (kn <= 1 && i != n - 1) {
      laplace_encode_vector_delta(enc, y + i, n - i, kn, curr, means);
      ran_delta = 1;
      break;
    }
    x = abs(y[i]);
    /* Expected value of x (round-to-nearest) is
       expQ8*pulses_left/positions_left */
    ex = (2*exp_q8*kn + (n - i))/(2*(n - i));
    if (ex > kn*256) ex = kn*256;
    sum_ex += (2*256*kn + (n - i))/(2*(n - i));
    /* No need to encode the magnitude for the last bin. */
    if (i != n - 1) od_laplace_encode(enc, x, ex, kn);
    if (x != 0) od_ec_enc_bits(enc, y[i] < 0, 1);
    kn -= x;
  }
  /* Adapting the estimates for expQ8 */
  if (!ran_delta) {
    curr[OD_ADAPT_COUNT_Q8] = OD_ADAPT_NO_VALUE;
    curr[OD_ADAPT_COUNT_EX_Q8] = OD_ADAPT_NO_VALUE;
  }
  curr[OD_ADAPT_K_Q8] = k - kn;
  curr[OD_ADAPT_SUM_EX_Q8] = sum_ex;
}