test/boolcoder_test.cc

/*
 * Copyright (c) 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.
 */

#include <math.h>
#include <stdlib.h>
#include <string.h>

#include <vector>

#include "gtest/gtest.h"

#include "test/acm_random.h"
#include "aom/aom_integer.h"
#include "aom_dsp/bitreader.h"
#include "aom_dsp/bitwriter.h"

using libaom_test::ACMRandom;

namespace {
const int num_tests = 10;
}  // namespace

TEST(AV1, TestBitIO) {
  ACMRandom rnd(ACMRandom::DeterministicSeed());
  for (int n = 0; n < num_tests; ++n) {
    for (int method = 0; method <= 7; ++method) {  // we generate various proba
      const int kBitsToTest = 1000;
      uint8_t probas[kBitsToTest];

      for (int i = 0; i < kBitsToTest; ++i) {
        const int parity = i & 1;
        /* clang-format off */
        probas[i] =
          (method == 0) ? 0 : (method == 1) ? 255 :
          (method == 2) ? 128 :
          (method == 3) ? rnd.Rand8() :
          (method == 4) ? (parity ? 0 : 255) :
            // alternate between low and high proba:
            (method == 5) ? (parity ? rnd(128) : 255 - rnd(128)) :
            (method == 6) ?
            (parity ? rnd(64) : 255 - rnd(64)) :
            (parity ? rnd(32) : 255 - rnd(32));
        /* clang-format on */
      }
      for (int bit_method = 0; bit_method <= 3; ++bit_method) {
        const int random_seed = 6432;
        const int kBufferSize = 10000;
        ACMRandom bit_rnd(random_seed);
        aom_writer bw;
        uint8_t bw_buffer[kBufferSize];
        aom_start_encode(&bw, bw_buffer, sizeof(bw_buffer));

        int bit = (bit_method == 0) ? 0 : (bit_method == 1) ? 1 : 0;
        for (int i = 0; i < kBitsToTest; ++i) {
          if (bit_method == 2) {
            bit = (i & 1);
          } else if (bit_method == 3) {
            bit = bit_rnd(2);
          }
          aom_write(&bw, bit, static_cast<int>(probas[i]));
        }

        GTEST_ASSERT_GE(aom_stop_encode(&bw), 0);

        aom_reader br;
        aom_reader_init(&br, bw_buffer, bw.pos);
        bit_rnd.Reset(random_seed);
        for (int i = 0; i < kBitsToTest; ++i) {
          if (bit_method == 2) {
            bit = (i & 1);
          } else if (bit_method == 3) {
            bit = bit_rnd(2);
          }
          GTEST_ASSERT_EQ(aom_read(&br, probas[i], nullptr), bit)
              << "pos: " << i << " / " << kBitsToTest
              << " bit_method: " << bit_method << " method: " << method;
        }
      }
    }
  }
}

#define FRAC_DIFF_TOTAL_ERROR 0.18

TEST(AV1, TestTell) {
  const int kBufferSize = 10000;
  aom_writer bw;
  uint8_t bw_buffer[kBufferSize];
  const int kSymbols = 1024;
  // Coders are noisier at low probabilities, so we start at p = 4.
  for (int p = 4; p < 256; p++) {
    double probability = p / 256.;
    aom_start_encode(&bw, bw_buffer, sizeof(bw_buffer));
    for (int i = 0; i < kSymbols; i++) {
      aom_write(&bw, 0, p);
    }
    GTEST_ASSERT_GE(aom_stop_encode(&bw), 0);
    aom_reader br;
    aom_reader_init(&br, bw_buffer, bw.pos);
    uint32_t last_tell = aom_reader_tell(&br);
    uint32_t last_tell_frac = aom_reader_tell_frac(&br);
    double frac_diff_total = 0;
    GTEST_ASSERT_GE(aom_reader_tell(&br), 0u);
    GTEST_ASSERT_LE(aom_reader_tell(&br), 1u);
    ASSERT_FALSE(aom_reader_has_overflowed(&br));
    for (int i = 0; i < kSymbols; i++) {
      aom_read(&br, p, nullptr);
      uint32_t tell = aom_reader_tell(&br);
      uint32_t tell_frac = aom_reader_tell_frac(&br);
      GTEST_ASSERT_GE(tell, last_tell)
          << "tell: " << tell << ", last_tell: " << last_tell;
      GTEST_ASSERT_GE(tell_frac, last_tell_frac)
          << "tell_frac: " << tell_frac
          << ", last_tell_frac: " << last_tell_frac;
      // Frac tell should round up to tell.
      GTEST_ASSERT_EQ(tell, (tell_frac + 7) >> 3);
      last_tell = tell;
      frac_diff_total +=
          fabs(((tell_frac - last_tell_frac) / 8.0) + log2(probability));
      last_tell_frac = tell_frac;
    }
    const uint32_t expected = (uint32_t)(-kSymbols * log2(probability));
    // Last tell should be close to the expected value.
    GTEST_ASSERT_LE(last_tell, expected + 20) << " last_tell: " << last_tell;
    // The average frac_diff error should be pretty small.
    GTEST_ASSERT_LE(frac_diff_total / kSymbols, FRAC_DIFF_TOTAL_ERROR)
        << " frac_diff_total: " << frac_diff_total;
    ASSERT_FALSE(aom_reader_has_overflowed(&br));
  }
}

TEST(AV1, TestHasOverflowed) {
  const int kBufferSize = 10000;
  aom_writer bw;
  uint8_t bw_buffer[kBufferSize];
  const int kSymbols = 1024;
  // Coders are noisier at low probabilities, so we start at p = 4.
  for (int p = 4; p < 256; p++) {
    aom_start_encode(&bw, bw_buffer, sizeof(bw_buffer));
    for (int i = 0; i < kSymbols; i++) {
      aom_write(&bw, 1, p);
    }
    GTEST_ASSERT_GE(aom_stop_encode(&bw), 0);
    aom_reader br;
    aom_reader_init(&br, bw_buffer, bw.pos);
    ASSERT_FALSE(aom_reader_has_overflowed(&br));
    for (int i = 0; i < kSymbols; i++) {
      GTEST_ASSERT_EQ(aom_read(&br, p, nullptr), 1);
      ASSERT_FALSE(aom_reader_has_overflowed(&br));
    }
    // In the worst case, the encoder uses just a tiny fraction of the last
    // byte in the buffer. So to guarantee that aom_reader_has_overflowed()
    // returns true, we have to consume very nearly 8 additional bits of data.
    // In the worse case, one of the bits in that byte will be 1, and the rest
    // will be zero. Once we are past that 1 bit, when the probability of
    // reading zero symbol from aom_read() is high, each additional symbol read
    // will consume very little additional data (in the case that p == 255,
    // approximately -log_2(255/256) ~= 0.0056 bits). In that case it would
    // take around 178 calls to consume more than 8 bits. That is only an upper
    // bound. In practice we are not guaranteed to hit the worse case and can
    // get away with 174 calls.
    for (int i = 0; i < 174; i++) {
      aom_read(&br, p, nullptr);
    }
    ASSERT_TRUE(aom_reader_has_overflowed(&br));
  }
}

// Fills cdf with a random CDF of nsymbs symbols and a zero counter.
static void RandomCdf(ACMRandom *rnd, int nsymbs, aom_cdf_prob *cdf) {
  int prev = 0;
  for (int i = 0; i < nsymbs - 1; ++i) {
    // Room for the symbols left, each with at least one unit.
    const int left = nsymbs - 1 - i;
    const int span = CDF_PROB_TOP - prev - left;
    prev += 1 + (*rnd)(span);
    cdf[i] = AOM_ICDF(prev);
  }
  cdf[nsymbs - 1] = AOM_ICDF(CDF_PROB_TOP);
  cdf[nsymbs] = 0;
}

// aom_write_symbol_state() and aom_write_bit_state() keep the range coder
// state in a local copy. They must write the same bytes as
// aom_write_symbol() and aom_write_bit() and adapt the CDFs the same way.
TEST(AV1, TestWriteSymbolState) {
  ACMRandom rnd(ACMRandom::DeterministicSeed());
  const int kSymbols = 20000;
  const int kMaxSymbs = 16;
  const int kNumCdfs = kMaxSymbs - 1;
  const int kBufferSize = 3 * kSymbols;
  for (int n = 0; n < num_tests; ++n) {
    aom_cdf_prob cdf_a[kNumCdfs][CDF_SIZE(kMaxSymbs)];
    aom_cdf_prob cdf_b[kNumCdfs][CDF_SIZE(kMaxSymbs)];
    aom_cdf_prob cdf_r[kNumCdfs][CDF_SIZE(kMaxSymbs)];
    for (int k = 0; k < kNumCdfs; ++k) RandomCdf(&rnd, k + 2, cdf_a[k]);
    memcpy(cdf_b, cdf_a, sizeof(cdf_a));
    memcpy(cdf_r, cdf_a, sizeof(cdf_a));
    const uint8_t allow_update_cdf = n & 1;
    std::vector<int> kinds(kSymbols);
    std::vector<int> values(kSymbols);
    std::vector<uint8_t> buf_a(kBufferSize);
    std::vector<uint8_t> buf_b(kBufferSize);
    aom_writer wa;
    aom_writer wb;
    aom_start_encode(&wa, buf_a.data(), kBufferSize);
    aom_start_encode(&wb, buf_b.data(), kBufferSize);
    wa.allow_update_cdf = allow_update_cdf;
    wb.allow_update_cdf = allow_update_cdf;
    od_ec_enc_state st = od_ec_enc_get_state(&wb.ec);
    for (int i = 0; i < kSymbols; ++i) {
      // kind 0 is a bit, kind k > 0 a symbol coded with cdf_*[k - 1].
      const int kind = rnd(kNumCdfs + 5) - 4;
      kinds[i] = kind > 0 ? kind : 0;
      // Mix in a write through the plain path now and then. It works on the
      // state stored in the writer.
      const bool plain = rnd(100) == 0;
      if (plain) od_ec_enc_set_state(&wb.ec, &st);
      if (kinds[i] == 0) {
        values[i] = rnd(2);
        aom_write_bit(&wa, values[i]);
        if (plain) {
          aom_write_bit(&wb, values[i]);
        } else {
          aom_write_bit_state(&wb, &st, values[i]);
        }
      } else {
        const int k = kinds[i] - 1;
        values[i] = rnd(k + 2);
        aom_write_symbol(&wa, values[i], cdf_a[k], k + 2);
        if (plain) {
          aom_write_symbol(&wb, values[i], cdf_b[k], k + 2);
        } else {
          aom_write_symbol_state(&wb, &st, values[i], cdf_b[k], k + 2);
        }
      }
      if (plain) {
        ASSERT_EQ(aom_tell_size(&wa), aom_tell_size(&wb)) << "symbol " << i;
        st = od_ec_enc_get_state(&wb.ec);
      }
    }
    od_ec_enc_set_state(&wb.ec, &st);
    GTEST_ASSERT_GE(aom_stop_encode(&wa), 0);
    GTEST_ASSERT_GE(aom_stop_encode(&wb), 0);
    ASSERT_EQ(wa.pos, wb.pos);
    EXPECT_EQ(memcmp(buf_a.data(), buf_b.data(), wa.pos), 0);
    EXPECT_EQ(memcmp(cdf_a, cdf_b, sizeof(cdf_a)), 0);

    aom_reader br;
    aom_reader_init(&br, buf_b.data(), wb.pos);
    br.allow_update_cdf = allow_update_cdf;
    for (int i = 0; i < kSymbols; ++i) {
      if (kinds[i] == 0) {
        GTEST_ASSERT_EQ(aom_read_bit(&br, nullptr), values[i]) << "pos " << i;
      } else {
        const int k = kinds[i] - 1;
        GTEST_ASSERT_EQ(aom_read_symbol(&br, cdf_r[k], k + 2, nullptr),
                        values[i])
            << "pos " << i;
      }
    }
    EXPECT_EQ(memcmp(cdf_a, cdf_r, sizeof(cdf_a)), 0);
  }
}