ANS: Switch from PDFs to CDFs.
Make the RANS implementation operate on cumulative distribution
functions rather than individual probability distribution functions.
CDFs have shown themselves more flexible to work with.
Reduces decoding memory usage from scaling O(num_distributions *
symbol_resolution) to O(num_distributions).
No bitstream change. This is an purely implementation change.
Change-Id: I4e18d3a0a3d37a36a61487c3d778f9d088b0b374
diff --git a/test/vp10_ans_test.cc b/test/vp10_ans_test.cc
index 441583a..363161d 100644
--- a/test/vp10_ans_test.cc
+++ b/test/vp10_ans_test.cc
@@ -147,7 +147,7 @@
}
const rans_sym rans_sym_tab[] = {
- {70, 186}, {70, 116}, {100, 16}, {16, 0},
+ {16, 0}, {100, 16}, {70, 116}, {70, 186},
};
const int kDistinctSyms = sizeof(rans_sym_tab) / sizeof(rans_sym_tab[0]);
@@ -170,13 +170,9 @@
void rans_build_dec_tab(const struct rans_sym sym_tab[],
rans_dec_lut dec_tab) {
- int val = 0;
- int i;
- for (i = ans_p8_precision - 1; i >= 0; --i) {
- dec_tab[i].val = val;
- dec_tab[i].prob = sym_tab[val].prob;
- dec_tab[i].cum_prob = sym_tab[val].cum_prob;
- if (i == sym_tab[val].cum_prob) ++val;
+ dec_tab[0] = 0;
+ for (int i = 1; dec_tab[i - 1] < ans_p8_precision; ++i) {
+ dec_tab[i] = dec_tab[i - 1] + sym_tab[i - 1].prob;
}
}
