ans_test.cc 6.55 KB
Newer Older
1
/*
2
 * Copyright (c) 2016, Alliance for Open Media. All rights reserved
3
 *
4 5 6 7 8 9
 * 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.
10 11 12 13 14 15 16 17 18
 */

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <ctime>
#include <utility>
#include <vector>

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 26 27
namespace {
typedef std::vector<std::pair<uint8_t, bool> > PvVec;

28
const int kPrintStats = 0;
29 30
// Use a small buffer size to exercise ANS window spills or buffer growth
const int kBufAnsSize = 1 << 8;
31

32 33
PvVec abs_encode_build_vals(int iters) {
  PvVec ret;
34
  libaom_test::ACMRandom gen(0x30317076);
35 36 37 38 39 40 41 42
  double entropy = 0;
  for (int i = 0; i < iters; ++i) {
    uint8_t p;
    do {
      p = gen.Rand8();
    } while (p == 0);  // zero is not a valid coding probability
    bool b = gen.Rand8() < p;
    ret.push_back(std::make_pair(static_cast<uint8_t>(p), b));
43 44 45 46
    if (kPrintStats) {
      double d = p / 256.;
      entropy += -d * log2(d) - (1 - d) * log2(1 - d);
    }
47
  }
48
  if (kPrintStats) printf("entropy %f\n", entropy);
49 50 51
  return ret;
}

52
bool check_rabs(const PvVec &pv_vec, uint8_t *buf) {
53
  BufAnsCoder a;
54 55
  a.size = kBufAnsSize;
  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 65
  int offset = buf_ans_write_end(&a);
  aom_buf_ans_free(&a);
66 67
  bool okay = true;
  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 73
  start = std::clock();
  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 77
  }
  std::clock_t dec_time = std::clock() - start;
  if (!okay) return false;
78 79 80 81
  if (kPrintStats)
    printf("uABS size %d enc_time %f dec_time %f\n", offset,
           static_cast<float>(enc_time) / CLOCKS_PER_SEC,
           static_cast<float>(dec_time) / CLOCKS_PER_SEC);
Yaowu Xu's avatar
Yaowu Xu committed
82
  return ans_read_end(&d) != 0;
83 84
}

85 86
const aom_cdf_prob spareto65[] = { 8320, 6018, 4402, 3254, 4259,
                                   3919, 2057, 492,  45,   2 };
87

Alex Converse's avatar
Alex Converse committed
88
const int kRansSymbols =
89
    static_cast<int>(sizeof(spareto65) / sizeof(spareto65[0]));
90

91 92 93 94 95
struct rans_sym {
  aom_cdf_prob prob;
  aom_cdf_prob cum_prob;  // not-inclusive
};

96 97 98 99 100 101 102
std::vector<int> ans_encode_build_vals(rans_sym *const tab, int iters) {
  aom_cdf_prob sum = 0;
  for (int i = 0; i < kRansSymbols; ++i) {
    tab[i].cum_prob = sum;
    tab[i].prob = spareto65[i];
    sum += spareto65[i];
  }
103
  std::vector<int> p_to_sym;
Alex Converse's avatar
Alex Converse committed
104
  for (int i = 0; i < kRansSymbols; ++i) {
105 106
    p_to_sym.insert(p_to_sym.end(), tab[i].prob, i);
  }
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 112
    int sym =
        p_to_sym[((gen.Rand8() << 8) + gen.Rand8()) & (RANS_PRECISION - 1)];
113 114 115 116 117
    ret.push_back(sym);
  }
  return ret;
}

Alex Converse's avatar
Alex Converse committed
118 119
void rans_build_dec_tab(const struct rans_sym sym_tab[],
                        aom_cdf_prob *dec_tab) {
120 121 122
  unsigned int sum = 0;
  for (int i = 0; sum < RANS_PRECISION; ++i) {
    dec_tab[i] = sum += sym_tab[i].prob;
123 124 125 126 127
  }
}

bool check_rans(const std::vector<int> &sym_vec, const rans_sym *const tab,
                uint8_t *buf) {
128
  BufAnsCoder a;
129 130
  a.size = kBufAnsSize;
  aom_buf_ans_alloc(&a, NULL);
131
  buf_ans_write_init(&a, buf);
Alex Converse's avatar
Alex Converse committed
132
  aom_cdf_prob dec_tab[kRansSymbols];
133 134 135
  rans_build_dec_tab(tab, dec_tab);

  std::clock_t start = std::clock();
136 137
  for (std::vector<int>::const_iterator it = sym_vec.begin();
       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 143
  int offset = buf_ans_write_end(&a);
  aom_buf_ans_free(&a);
144 145
  bool okay = true;
  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 151 152 153 154 155 156
  start = std::clock();
  for (std::vector<int>::const_iterator it = sym_vec.begin();
       it != sym_vec.end(); ++it) {
    okay &= rans_read(&d, dec_tab) == *it;
  }
  std::clock_t dec_time = std::clock() - start;
  if (!okay) return false;
157 158 159 160
  if (kPrintStats)
    printf("rANS size %d enc_time %f dec_time %f\n", offset,
           static_cast<float>(enc_time) / CLOCKS_PER_SEC,
           static_cast<float>(dec_time) / CLOCKS_PER_SEC);
Yaowu Xu's avatar
Yaowu Xu committed
161
  return ans_read_end(&d) != 0;
162 163
}

164
class AbsTestFix : public ::testing::Test {
165 166 167 168 169 170 171 172
 protected:
  static void SetUpTestCase() { pv_vec_ = abs_encode_build_vals(kNumBools); }
  virtual void SetUp() { buf_ = new uint8_t[kNumBools / 8]; }
  virtual void TearDown() { delete[] buf_; }
  static const int kNumBools = 100000000;
  static PvVec pv_vec_;
  uint8_t *buf_;
};
173
PvVec AbsTestFix::pv_vec_;
174

175
class AnsTestFix : public ::testing::Test {
176 177
 protected:
  static void SetUpTestCase() {
178
    sym_vec_ = ans_encode_build_vals(rans_sym_tab_, kNumSyms);
179 180 181 182 183
  }
  virtual void SetUp() { buf_ = new uint8_t[kNumSyms / 2]; }
  virtual void TearDown() { delete[] buf_; }
  static const int kNumSyms = 25000000;
  static std::vector<int> sym_vec_;
184
  static rans_sym rans_sym_tab_[kRansSymbols];
185 186
  uint8_t *buf_;
};
187 188
std::vector<int> AnsTestFix::sym_vec_;
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 193
  EXPECT_TRUE(check_rans(sym_vec_, rans_sym_tab_, buf_));
}
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
TEST(AnsTest, FinalStateSerialization) {
  for (unsigned i = L_BASE; i < L_BASE * IO_BASE; ++i) {
    uint8_t buf[8];
    AnsCoder c;
    ans_write_init(&c, buf);
    c.state = i;
    const int written_size = ans_write_end(&c);
    ASSERT_LT(static_cast<size_t>(written_size), sizeof(buf));
    AnsDecoder d;
#if ANS_MAX_SYMBOLS
    // There is no real data window here because no symbols are sent through
    // ans (only synthetic states), so use a dummy value
    d.window_size = 1024;
#endif
    const int read_init_status = ans_read_init(&d, buf, written_size);
    EXPECT_EQ(read_init_status, 0);
    EXPECT_EQ(d.state, i);
  }
}
213
}  // namespace