test/ans_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 <assert.h>
  13 #include <math.h>
  14 #include <stdio.h>
  15 #include <ctime>
  16 #include <utility>
  17 #include <vector>
  18
  19 #include "third_party/googletest/src/googletest/include/gtest/gtest.h"
  20
  21 #include "test/acm_random.h"
  22 #include "aom_dsp/ansreader.h"
  23 #include "aom_dsp/buf_ans.h"
  24
  25 namespace {
  26 typedef std::vector<std::pair<uint8_t, bool> > PvVec;
  27
  28 const int kPrintStats = 0;
  29 // Use a small buffer size to exercise ANS window spills or buffer growth
  30 const int kBufAnsSize = 1 << 8;
  31
  32 PvVec abs_encode_build_vals(int iters) {
  33   PvVec ret;
  34   libaom_test::ACMRandom gen(0x30317076);
  35   double entropy = 0;
  36   for (int i = 0; i < iters; ++i) {
  37     uint8_t p;
  38     do {
  39       p = gen.Rand8();
  40     } while (p == 0);  // zero is not a valid coding probability
  41     bool b = gen.Rand8() < p;
  42     ret.push_back(std::make_pair(static_cast<uint8_t>(p), b));
  43     if (kPrintStats) {
  44       double d = p / 256.;
  45       entropy += -d * log2(d) - (1 - d) * log2(1 - d);
  46     }
  47   }
  48   if (kPrintStats) printf("entropy %f\n", entropy);
  49   return ret;
  50 }
  51
  52 bool check_rabs(const PvVec &pv_vec, uint8_t *buf) {
  53   BufAnsCoder a;
  54   a.size = kBufAnsSize;
  55   aom_buf_ans_alloc(&a, NULL);
  56   buf_ans_write_init(&a, buf);
  57
  58   std::clock_t start = std::clock();
  59   for (PvVec::const_iterator it = pv_vec.begin(); it != pv_vec.end(); ++it) {
  60     buf_rabs_write(&a, it->second, 256 - it->first);
  61   }
  62   aom_buf_ans_flush(&a);
  63   std::clock_t enc_time = std::clock() - start;
  64   int offset = buf_ans_write_end(&a);
  65   aom_buf_ans_free(&a);
  66   bool okay = true;
  67   AnsDecoder d;
  68 #if ANS_MAX_SYMBOLS
  69   d.window_size = kBufAnsSize;
  70 #endif
  71   if (ans_read_init(&d, buf, offset)) return false;
  72   start = std::clock();
  73   for (PvVec::const_iterator it = pv_vec.begin(); it != pv_vec.end(); ++it) {
  74     okay = okay && (rabs_read(&d, 256 - it->first) != 0) == it->second;
  75   }
  76   std::clock_t dec_time = std::clock() - start;
  77   if (!okay) return false;
  78   if (kPrintStats)
  79     printf("uABS size %d enc_time %f dec_time %f\n", offset,
  80            static_cast<float>(enc_time) / CLOCKS_PER_SEC,
  81            static_cast<float>(dec_time) / CLOCKS_PER_SEC);
  82   return ans_read_end(&d) != 0;
  83 }
  84
  85 const aom_cdf_prob spareto65[] = { 8320, 6018, 4402, 3254, 4259,
  86                                    3919, 2057, 492,  45,   2 };
  87
  88 const int kRansSymbols =
  89     static_cast<int>(sizeof(spareto65) / sizeof(spareto65[0]));
  90
  91 struct rans_sym {
  92   aom_cdf_prob prob;
  93   aom_cdf_prob cum_prob;  // not-inclusive
  94 };
  95
  96 std::vector<int> ans_encode_build_vals(rans_sym *const tab, int iters) {
  97   aom_cdf_prob sum = 0;
  98   for (int i = 0; i < kRansSymbols; ++i) {
  99     tab[i].cum_prob = sum;
 100     tab[i].prob = spareto65[i];
 101     sum += spareto65[i];
 102   }
 103   std::vector<int> p_to_sym;
 104   for (int i = 0; i < kRansSymbols; ++i) {
 105     p_to_sym.insert(p_to_sym.end(), tab[i].prob, i);
 106   }
 107   assert(p_to_sym.size() == RANS_PRECISION);
 108   std::vector<int> ret;
 109   libaom_test::ACMRandom gen(18543637);
 110   for (int i = 0; i < iters; ++i) {
 111     int sym =
 112         p_to_sym[((gen.Rand8() << 8) + gen.Rand8()) & (RANS_PRECISION - 1)];
 113     ret.push_back(sym);
 114   }
 115   return ret;
 116 }
 117
 118 void rans_build_dec_tab(const struct rans_sym sym_tab[],
 119                         aom_cdf_prob *dec_tab) {
 120   unsigned int sum = 0;
 121   for (int i = 0; sum < RANS_PRECISION; ++i) {
 122     dec_tab[i] = sum += sym_tab[i].prob;
 123   }
 124 }
 125
 126 bool check_rans(const std::vector<int> &sym_vec, const rans_sym *const tab,
 127                 uint8_t *buf) {
 128   BufAnsCoder a;
 129   a.size = kBufAnsSize;
 130   aom_buf_ans_alloc(&a, NULL);
 131   buf_ans_write_init(&a, buf);
 132   aom_cdf_prob dec_tab[kRansSymbols];
 133   rans_build_dec_tab(tab, dec_tab);
 134
 135   std::clock_t start = std::clock();
 136   for (std::vector<int>::const_iterator it = sym_vec.begin();
 137        it != sym_vec.end(); ++it) {
 138     buf_rans_write(&a, tab[*it].cum_prob, tab[*it].prob);
 139   }
 140   aom_buf_ans_flush(&a);
 141   std::clock_t enc_time = std::clock() - start;
 142   int offset = buf_ans_write_end(&a);
 143   aom_buf_ans_free(&a);
 144   bool okay = true;
 145   AnsDecoder d;
 146 #if ANS_MAX_SYMBOLS
 147   d.window_size = kBufAnsSize;
 148 #endif
 149   if (ans_read_init(&d, buf, offset)) return false;
 150   start = std::clock();
 151   for (std::vector<int>::const_iterator it = sym_vec.begin();
 152        it != sym_vec.end(); ++it) {
 153     okay &= rans_read(&d, dec_tab) == *it;
 154   }
 155   std::clock_t dec_time = std::clock() - start;
 156   if (!okay) return false;
 157   if (kPrintStats)
 158     printf("rANS size %d enc_time %f dec_time %f\n", offset,
 159            static_cast<float>(enc_time) / CLOCKS_PER_SEC,
 160            static_cast<float>(dec_time) / CLOCKS_PER_SEC);
 161   return ans_read_end(&d) != 0;
 162 }
 163
 164 class AbsTestFix : public ::testing::Test {
 165  protected:
 166   static void SetUpTestCase() { pv_vec_ = abs_encode_build_vals(kNumBools); }
 167   virtual void SetUp() { buf_ = new uint8_t[kNumBools / 8]; }
 168   virtual void TearDown() { delete[] buf_; }
 169   static const int kNumBools = 100000000;
 170   static PvVec pv_vec_;
 171   uint8_t *buf_;
 172 };
 173 PvVec AbsTestFix::pv_vec_;
 174
 175 class AnsTestFix : public ::testing::Test {
 176  protected:
 177   static void SetUpTestCase() {
 178     sym_vec_ = ans_encode_build_vals(rans_sym_tab_, kNumSyms);
 179   }
 180   virtual void SetUp() { buf_ = new uint8_t[kNumSyms / 2]; }
 181   virtual void TearDown() { delete[] buf_; }
 182   static const int kNumSyms = 25000000;
 183   static std::vector<int> sym_vec_;
 184   static rans_sym rans_sym_tab_[kRansSymbols];
 185   uint8_t *buf_;
 186 };
 187 std::vector<int> AnsTestFix::sym_vec_;
 188 rans_sym AnsTestFix::rans_sym_tab_[kRansSymbols];
 189
 190 TEST_F(AbsTestFix, Rabs) { EXPECT_TRUE(check_rabs(pv_vec_, buf_)); }
 191 TEST_F(AnsTestFix, Rans) {
 192   EXPECT_TRUE(check_rans(sym_vec_, rans_sym_tab_, buf_));
 193 }
 194 TEST(AnsTest, FinalStateSerialization) {
 195   for (unsigned i = L_BASE; i < L_BASE * IO_BASE; ++i) {
 196     uint8_t buf[8];
 197     AnsCoder c;
 198     ans_write_init(&c, buf);
 199     c.state = i;
 200     const int written_size = ans_write_end(&c);
 201     ASSERT_LT(static_cast<size_t>(written_size), sizeof(buf));
 202     AnsDecoder d;
 203 #if ANS_MAX_SYMBOLS
 204     // There is no real data window here because no symbols are sent through
 205     // ans (only synthetic states), so use a dummy value
 206     d.window_size = 1024;
 207 #endif
 208     const int read_init_status = ans_read_init(&d, buf, written_size);
 209     EXPECT_EQ(read_init_status, 0);
 210     EXPECT_EQ(d.state, i);
 211   }
 212 }
 213 }  // namespace