third_party/aom/test/boolcoder_test.cc

   1 /*
   2  * Copyright (c) 2016, Alliance for Open Media. All rights reserved
   3  *
   4  * This source code is subject to the terms of the BSD 2 Clause License and
   5  * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
   6  * was not distributed with this source code in the LICENSE file, you can
   7  * obtain it at www.aomedia.org/license/software. If the Alliance for Open
   8  * Media Patent License 1.0 was not distributed with this source code in the
   9  * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
  10  */
  11
  12 #include <math.h>
  13 #include <stdlib.h>
  14 #include <string.h>
  15
  16 #include "third_party/googletest/src/googletest/include/gtest/gtest.h"
  17
  18 #include "test/acm_random.h"
  19 #include "aom/aom_integer.h"
  20 #include "aom_dsp/bitreader.h"
  21 #include "aom_dsp/bitwriter.h"
  22
  23 using libaom_test::ACMRandom;
  24
  25 namespace {
  26 const int num_tests = 10;
  27 }  // namespace
  28
  29 TEST(AV1, TestBitIO) {
  30   ACMRandom rnd(ACMRandom::DeterministicSeed());
  31   for (int n = 0; n < num_tests; ++n) {
  32     for (int method = 0; method <= 7; ++method) {  // we generate various proba
  33       const int kBitsToTest = 1000;
  34       uint8_t probas[kBitsToTest];
  35
  36       for (int i = 0; i < kBitsToTest; ++i) {
  37         const int parity = i & 1;
  38         /* clang-format off */
  39         probas[i] =
  40           (method == 0) ? 0 : (method == 1) ? 255 :
  41           (method == 2) ? 128 :
  42           (method == 3) ? rnd.Rand8() :
  43           (method == 4) ? (parity ? 0 : 255) :
  44             // alternate between low and high proba:
  45             (method == 5) ? (parity ? rnd(128) : 255 - rnd(128)) :
  46             (method == 6) ?
  47             (parity ? rnd(64) : 255 - rnd(64)) :
  48             (parity ? rnd(32) : 255 - rnd(32));
  49         /* clang-format on */
  50       }
  51       for (int bit_method = 0; bit_method <= 3; ++bit_method) {
  52         const int random_seed = 6432;
  53         const int kBufferSize = 10000;
  54         ACMRandom bit_rnd(random_seed);
  55         aom_writer bw;
  56         uint8_t bw_buffer[kBufferSize];
  57         aom_start_encode(&bw, bw_buffer);
  58
  59         int bit = (bit_method == 0) ? 0 : (bit_method == 1) ? 1 : 0;
  60         for (int i = 0; i < kBitsToTest; ++i) {
  61           if (bit_method == 2) {
  62             bit = (i & 1);
  63           } else if (bit_method == 3) {
  64             bit = bit_rnd(2);
  65           }
  66           aom_write(&bw, bit, static_cast<int>(probas[i]));
  67         }
  68
  69         aom_stop_encode(&bw);
  70
  71         aom_reader br;
  72         aom_reader_init(&br, bw_buffer, bw.pos);
  73         bit_rnd.Reset(random_seed);
  74         for (int i = 0; i < kBitsToTest; ++i) {
  75           if (bit_method == 2) {
  76             bit = (i & 1);
  77           } else if (bit_method == 3) {
  78             bit = bit_rnd(2);
  79           }
  80           GTEST_ASSERT_EQ(aom_read(&br, probas[i], NULL), bit)
  81               << "pos: " << i << " / " << kBitsToTest
  82               << " bit_method: " << bit_method << " method: " << method;
  83         }
  84       }
  85     }
  86   }
  87 }
  88
  89 #define FRAC_DIFF_TOTAL_ERROR 0.18
  90
  91 TEST(AV1, TestTell) {
  92   const int kBufferSize = 10000;
  93   aom_writer bw;
  94   uint8_t bw_buffer[kBufferSize];
  95   const int kSymbols = 1024;
  96   // Coders are noisier at low probabilities, so we start at p = 4.
  97   for (int p = 4; p < 256; p++) {
  98     double probability = p / 256.;
  99     aom_start_encode(&bw, bw_buffer);
 100     for (int i = 0; i < kSymbols; i++) {
 101       aom_write(&bw, 0, p);
 102     }
 103     aom_stop_encode(&bw);
 104     aom_reader br;
 105     aom_reader_init(&br, bw_buffer, bw.pos);
 106     uint32_t last_tell = aom_reader_tell(&br);
 107     uint32_t last_tell_frac = aom_reader_tell_frac(&br);
 108     double frac_diff_total = 0;
 109     GTEST_ASSERT_GE(aom_reader_tell(&br), 0u);
 110     GTEST_ASSERT_LE(aom_reader_tell(&br), 1u);
 111     ASSERT_FALSE(aom_reader_has_overflowed(&br));
 112     for (int i = 0; i < kSymbols; i++) {
 113       aom_read(&br, p, NULL);
 114       uint32_t tell = aom_reader_tell(&br);
 115       uint32_t tell_frac = aom_reader_tell_frac(&br);
 116       GTEST_ASSERT_GE(tell, last_tell)
 117           << "tell: " << tell << ", last_tell: " << last_tell;
 118       GTEST_ASSERT_GE(tell_frac, last_tell_frac)
 119           << "tell_frac: " << tell_frac
 120           << ", last_tell_frac: " << last_tell_frac;
 121       // Frac tell should round up to tell.
 122       GTEST_ASSERT_EQ(tell, (tell_frac + 7) >> 3);
 123       last_tell = tell;
 124       frac_diff_total +=
 125           fabs(((tell_frac - last_tell_frac) / 8.0) + log2(probability));
 126       last_tell_frac = tell_frac;
 127     }
 128     const uint32_t expected = (uint32_t)(-kSymbols * log2(probability));
 129     // Last tell should be close to the expected value.
 130     GTEST_ASSERT_LE(last_tell, expected + 20) << " last_tell: " << last_tell;
 131     // The average frac_diff error should be pretty small.
 132     GTEST_ASSERT_LE(frac_diff_total / kSymbols, FRAC_DIFF_TOTAL_ERROR)
 133         << " frac_diff_total: " << frac_diff_total;
 134     ASSERT_FALSE(aom_reader_has_overflowed(&br));
 135   }
 136 }
 137
 138 TEST(AV1, TestHasOverflowed) {
 139   const int kBufferSize = 10000;
 140   aom_writer bw;
 141   uint8_t bw_buffer[kBufferSize];
 142   const int kSymbols = 1024;
 143   // Coders are noisier at low probabilities, so we start at p = 4.
 144   for (int p = 4; p < 256; p++) {
 145     aom_start_encode(&bw, bw_buffer);
 146     for (int i = 0; i < kSymbols; i++) {
 147       aom_write(&bw, 1, p);
 148     }
 149     aom_stop_encode(&bw);
 150     aom_reader br;
 151     aom_reader_init(&br, bw_buffer, bw.pos);
 152     ASSERT_FALSE(aom_reader_has_overflowed(&br));
 153     for (int i = 0; i < kSymbols; i++) {
 154       GTEST_ASSERT_EQ(aom_read(&br, p, NULL), 1);
 155       ASSERT_FALSE(aom_reader_has_overflowed(&br));
 156     }
 157     // In the worst case, the encoder uses just a tiny fraction of the last
 158     // byte in the buffer. So to guarantee that aom_reader_has_overflowed()
 159     // returns true, we have to consume very nearly 8 additional bits of data.
 160     // In the worse case, one of the bits in that byte will be 1, and the rest
 161     // will be zero. Once we are past that 1 bit, when the probability of
 162     // reading zero symbol from aom_read() is high, each additional symbol read
 163     // will consume very little additional data (in the case that p == 255,
 164     // approximately -log_2(255/256) ~= 0.0056 bits). In that case it would
 165     // take around 178 calls to consume more than 8 bits. That is only an upper
 166     // bound. In practice we are not guaranteed to hit the worse case and can
 167     // get away with 174 calls.
 168     for (int i = 0; i < 174; i++) {
 169       aom_read(&br, p, NULL);
 170     }
 171     ASSERT_TRUE(aom_reader_has_overflowed(&br));
 172   }
 173 }