daala_ec: Convert the encoder to use iCDFs
This only changes the internal coding engine. We convert CDFs into
iCDFs at the "bool" writer <-> daala_ec boundary.
Encoder output should not change, and all streams should remain
decodable without decoder changes.
Change-Id: Id3ac7352926497bf6f7bc371ab9bc76e9a3569d5
diff --git a/aom_dsp/daalaboolwriter.h b/aom_dsp/daalaboolwriter.h
index 2f4cab1..c4466fc 100644
--- a/aom_dsp/daalaboolwriter.h
+++ b/aom_dsp/daalaboolwriter.h
@@ -50,7 +50,7 @@
bitstream_queue_push(bit, cdf, 2);
#endif
- od_ec_encode_bool_q15(&w->ec, bit, p);
+ od_ec_encode_bool_q15(&w->ec, bit, OD_ICDF(p));
}
#if CONFIG_RAWBITS
@@ -73,7 +73,16 @@
bitstream_queue_push(symb, cdf, nsymbs);
#endif
+#if CONFIG_EC_SMALLMUL
+ {
+ aom_cdf_prob icdf[16];
+ int i;
+ for (i = 0; i < nsymbs; i++) icdf[i] = OD_ICDF(cdf[i]);
+ od_ec_encode_cdf_q15(&w->ec, symb, icdf, nsymbs);
+ }
+#else
od_ec_encode_cdf_q15(&w->ec, symb, cdf, nsymbs);
+#endif
}
#ifdef __cplusplus
diff --git a/aom_dsp/entcode.h b/aom_dsp/entcode.h
index b88fd9d..534959e 100644
--- a/aom_dsp/entcode.h
+++ b/aom_dsp/entcode.h
@@ -28,6 +28,16 @@
3 => 1/8th bits.*/
#define OD_BITRES (3)
+/*With CONFIG_EC_SMALLMUL, the value stored in a CDF is 32768 minus the actual
+ Q15 cumulative probability (an "inverse" CDF).
+ This function converts from one representation to the other (and is its own
+ inverse).*/
+#if CONFIG_EC_SMALLMUL
+#define OD_ICDF(x) (32768U - (x))
+#else
+#define OD_ICDF(x) (x)
+#endif
+
/*See entcode.c for further documentation.*/
OD_WARN_UNUSED_RESULT uint32_t od_ec_tell_frac(uint32_t nbits_total,
diff --git a/aom_dsp/entenc.c b/aom_dsp/entenc.c
index 399252d..a350f27 100644
--- a/aom_dsp/entenc.c
+++ b/aom_dsp/entenc.c
@@ -146,27 +146,30 @@
fl: The cumulative frequency of all symbols that come before the one to be
encoded.
fh: The cumulative frequency of all symbols up to and including the one to
- be encoded.*/
+ be encoded.
+ {EC_SMALLMUL} Both values are 32768 minus that.*/
static void od_ec_encode_q15(od_ec_enc *enc, unsigned fl, unsigned fh) {
od_ec_window l;
unsigned r;
unsigned u;
unsigned v;
- OD_ASSERT(fl < fh);
- OD_ASSERT(fh <= 32768U);
l = enc->low;
r = enc->rng;
OD_ASSERT(32768U <= r);
#if CONFIG_EC_SMALLMUL
- if (fl > 0) {
- u = (r >> 8) * (uint32_t)(32768U - fl) >> 7;
- v = (r >> 8) * (uint32_t)(32768U - fh) >> 7;
+ OD_ASSERT(fh < fl);
+ OD_ASSERT(fl <= 32768U);
+ if (fl < 32768U) {
+ u = (r >> 8) * (uint32_t)fl >> 7;
+ v = (r >> 8) * (uint32_t)fh >> 7;
l += r - u;
r = u - v;
} else {
- r -= (r >> 8) * (uint32_t)(32768U - fh) >> 7;
+ r -= (r >> 8) * (uint32_t)fh >> 7;
}
#else
+ OD_ASSERT(fl < fh);
+ OD_ASSERT(fh <= 32768U);
u = fl * (uint32_t)r >> 15;
v = fh * (uint32_t)r >> 15;
r = v - u;
@@ -174,33 +177,37 @@
#endif
od_ec_enc_normalize(enc, l, r);
#if OD_MEASURE_EC_OVERHEAD
- enc->entropy -= OD_LOG2((double)(fh - fl) / 32768.);
+ enc->entropy -= OD_LOG2((double)(OD_ICDF(fh) - OD_ICDF(fl)) / 32768.);
enc->nb_symbols++;
#endif
}
-/*Encode a bit that has an fz probability of being a zero in Q15.
+/*Encode a single binary value.
val: The value to encode (0 or 1).
- fz: The probability that val is zero, scaled by 32768.*/
-void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned fz) {
+ {EC_SMALLMUL} f: The probability that the val is one, scaled by 32768.
+ {else} f: The probability that val is zero, scaled by 32768.*/
+void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned f) {
od_ec_window l;
unsigned r;
unsigned v;
- OD_ASSERT(0 < fz);
- OD_ASSERT(fz < 32768U);
+ OD_ASSERT(0 < f);
+ OD_ASSERT(f < 32768U);
l = enc->low;
r = enc->rng;
OD_ASSERT(32768U <= r);
#if CONFIG_EC_SMALLMUL
- v = r - ((r >> 8) * (uint32_t)(32768U - fz) >> 7);
+ v = (r >> 8) * (uint32_t)f >> 7;
+ if (val) l += r - v;
+ r = val ? v : r - v;
#else
- v = fz * (uint32_t)r >> 15;
-#endif
+ v = f * (uint32_t)r >> 15;
if (val) l += v;
r = val ? r - v : v;
+#endif
od_ec_enc_normalize(enc, l, r);
#if OD_MEASURE_EC_OVERHEAD
- enc->entropy -= OD_LOG2((double)(val ? 32768 - fz : fz) / 32768.);
+ enc->entropy -=
+ OD_LOG2((double)(val ? 32768 - OD_ICDF(f) : OD_ICDF(f)) / 32768.);
enc->nb_symbols++;
#endif
}
@@ -218,8 +225,8 @@
(void)nsyms;
OD_ASSERT(s >= 0);
OD_ASSERT(s < nsyms);
- OD_ASSERT(cdf[nsyms - 1] == 32768U);
- od_ec_encode_q15(enc, s > 0 ? cdf[s - 1] : 0, cdf[s]);
+ OD_ASSERT(cdf[nsyms - 1] == OD_ICDF(32768U));
+ od_ec_encode_q15(enc, s > 0 ? cdf[s - 1] : OD_ICDF(0), cdf[s]);
}
#if CONFIG_RAWBITS
diff --git a/aom_dsp/entenc.h b/aom_dsp/entenc.h
index b143bbc..314b363 100644
--- a/aom_dsp/entenc.h
+++ b/aom_dsp/entenc.h
@@ -62,7 +62,7 @@
void od_ec_enc_reset(od_ec_enc *enc) OD_ARG_NONNULL(1);
void od_ec_enc_clear(od_ec_enc *enc) OD_ARG_NONNULL(1);
-void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned fz_q15)
+void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned f_q15)
OD_ARG_NONNULL(1);
void od_ec_encode_cdf_q15(od_ec_enc *enc, int s, const uint16_t *cdf, int nsyms)
OD_ARG_NONNULL(1) OD_ARG_NONNULL(3);
