ref: a093f4df740b7680443e938775b4db2b0fa24844
parent: ef986e44211bc0fd3820700b61e552828a0d8c65
author: Timothy B. Terriberry <[email protected]>
date: Thu Feb 3 09:22:15 EST 2011
Refactor the entropy coder.
This unifies the byte buffer, encoder, and decoder into a single
struct.
The common encoder and decoder functions (such as ec_tell()) can
operate on either one, simplifying code which uses both.
The precision argument to ec_tell() has been removed.
It now comes in two precisions:
ec_tell() gives 1 bit precision in two operations, and
ec_tell_frac() gives 1/8th bit precision in... somewhat more.
ec_{enc|dec}_bit_prob() were removed (they are no longer needed).
Some of the byte buffer access functions were made static and
removed from the cross-module API.
All of the code in rangeenc.c and rangedec.c was merged into
entenc.c and entdec.c, respectively, as we are no longer
considering alternative backends.
rangeenc.c and rangede.c have been removed entirely.
This passes make check, after disabling the modes that we removed
support for in cf5d3a8c.
--- a/libcelt/Makefile.am
+++ b/libcelt/Makefile.am
@@ -16,8 +16,7 @@
# Sources for compilation in the library
libcelt@LIBCELT_SUFFIX@_la_SOURCES = bands.c celt.c cwrs.c ecintrin.h entcode.c \
entdec.c entenc.c header.c kiss_fft.c laplace.c mathops.c mdct.c \
- modes.c pitch.c plc.c quant_bands.c rangedec.c rangeenc.c rate.c \
- vq.c
+ modes.c pitch.c plc.c quant_bands.c rate.c vq.c
libcelt@LIBCELT_SUFFIX@_la_LDFLAGS = \
-version-info @CELT_LT_CURRENT@:@CELT_LT_REVISION@:@CELT_LT_AGE@ \
--- a/libcelt/bands.c
+++ b/libcelt/bands.c
@@ -636,7 +636,7 @@
in two and transmit the energy difference with the two half-bands. It
can be called recursively so bands can end up being split in 8 parts. */
static unsigned quant_band(int encode, const CELTMode *m, int i, celt_norm *X, celt_norm *Y,
- int N, int b, int spread, int B, int intensity, int tf_change, celt_norm *lowband, int resynth, void *ec,
+ int N, int b, int spread, int B, int intensity, int tf_change, celt_norm *lowband, int resynth, ec_ctx *ec,
celt_int32 *remaining_bits, int LM, celt_norm *lowband_out, const celt_ener *bandE, int level,
celt_uint32 *seed, celt_word16 gain, celt_norm *lowband_scratch, int fill)
{@@ -675,9 +675,9 @@
if (encode)
{sign = x[0]<0;
- ec_enc_bits((ec_enc*)ec, sign, 1);
+ ec_enc_bits(ec, sign, 1);
} else {- sign = ec_dec_bits((ec_dec*)ec, 1);
+ sign = ec_dec_bits(ec, 1);
}
*remaining_bits -= 1<<BITRES;
b-=1<<BITRES;
@@ -787,7 +787,7 @@
2) they are orthogonal. */
itheta = stereo_itheta(X, Y, stereo, N);
}
- tell = encode ? ec_enc_tell(ec, BITRES) : ec_dec_tell(ec, BITRES);
+ tell = ec_tell_frac(ec);
if (qn!=1)
{if (encode)
@@ -804,7 +804,7 @@
/* Use a probability of p0 up to itheta=8192 and then use 1 after */
if (encode)
{- ec_encode((ec_enc*)ec,x<=x0?p0*x:(x-1-x0)+(x0+1)*p0,x<=x0?p0*(x+1):(x-x0)+(x0+1)*p0,ft);
+ ec_encode(ec,x<=x0?p0*x:(x-1-x0)+(x0+1)*p0,x<=x0?p0*(x+1):(x-x0)+(x0+1)*p0,ft);
} else {int fs;
fs=ec_decode(ec,ft);
@@ -818,9 +818,9 @@
} else if (B0>1 || stereo) {/* Uniform pdf */
if (encode)
- ec_enc_uint((ec_enc*)ec, itheta, qn+1);
+ ec_enc_uint(ec, itheta, qn+1);
else
- itheta = ec_dec_uint((ec_dec*)ec, qn+1);
+ itheta = ec_dec_uint(ec, qn+1);
} else {int fs=1, ft;
ft = ((qn>>1)+1)*((qn>>1)+1);
@@ -832,12 +832,12 @@
fl = itheta <= (qn>>1) ? itheta*(itheta + 1)>>1 :
ft - ((qn + 1 - itheta)*(qn + 2 - itheta)>>1);
- ec_encode((ec_enc*)ec, fl, fl+fs, ft);
+ ec_encode(ec, fl, fl+fs, ft);
} else {/* Triangular pdf */
int fl=0;
int fm;
- fm = ec_decode((ec_dec*)ec, ft);
+ fm = ec_decode(ec, ft);
if (fm < ((qn>>1)*((qn>>1) + 1)>>1))
{@@ -853,7 +853,7 @@
fl = ft - ((qn + 1 - itheta)*(qn + 2 - itheta)>>1);
}
- ec_dec_update((ec_dec*)ec, fl, fl+fs, ft);
+ ec_dec_update(ec, fl, fl+fs, ft);
}
}
itheta = (celt_int32)itheta*16384/qn;
@@ -888,8 +888,7 @@
inv = 0;
itheta = 0;
}
- qalloc = (encode ? ec_enc_tell(ec, BITRES) : ec_dec_tell(ec, BITRES))
- - tell;
+ qalloc = ec_tell_frac(ec) - tell;
b -= qalloc;
orig_fill = fill;
@@ -946,9 +945,9 @@
{/* Here we only need to encode a sign for the side */
sign = x2[0]*y2[1] - x2[1]*y2[0] < 0;
- ec_enc_bits((ec_enc*)ec, sign, 1);
+ ec_enc_bits(ec, sign, 1);
} else {- sign = ec_dec_bits((ec_dec*)ec, 1);
+ sign = ec_dec_bits(ec, 1);
}
}
sign = 1-2*sign;
@@ -1059,9 +1058,9 @@
/* Finally do the actual quantization */
if (encode)
- cm = alg_quant(X, N, K, spread, B, resynth, (ec_enc*)ec, gain);
+ cm = alg_quant(X, N, K, spread, B, resynth, ec, gain);
else
- cm = alg_unquant(X, N, K, spread, B, (ec_dec*)ec, gain);
+ cm = alg_unquant(X, N, K, spread, B, ec, gain);
} else {/* If there's no pulse, fill the band anyway */
int j;
@@ -1160,7 +1159,7 @@
void quant_all_bands(int encode, const CELTMode *m, int start, int end,
celt_norm *_X, celt_norm *_Y, unsigned char *collapse_masks, const celt_ener *bandE, int *pulses,
int shortBlocks, int spread, int dual_stereo, int intensity, int *tf_res, int resynth,
- celt_int32 total_bits, celt_int32 balance, void *ec, int LM, int codedBands, ec_uint32 *seed)
+ celt_int32 total_bits, celt_int32 balance, ec_ctx *ec, int LM, int codedBands, ec_uint32 *seed)
{int i;
celt_int32 remaining_bits;
@@ -1201,10 +1200,7 @@
else
Y = NULL;
N = M*eBands[i+1]-M*eBands[i];
- if (encode)
- tell = ec_enc_tell((ec_enc*)ec, BITRES);
- else
- tell = ec_dec_tell((ec_dec*)ec, BITRES);
+ tell = ec_tell_frac(ec);
/* Compute how many bits we want to allocate to this band */
if (i != start)
--- a/libcelt/bands.h
+++ b/libcelt/bands.h
@@ -88,7 +88,7 @@
void quant_all_bands(int encode, const CELTMode *m, int start, int end,
celt_norm * X, celt_norm * Y, unsigned char *collapse_masks, const celt_ener *bandE, int *pulses,
int time_domain, int fold, int dual_stereo, int intensity, int *tf_res, int resynth,
- celt_int32 total_bits, celt_int32 balance, void *enc, int M, int codedBands, ec_uint32 *seed);
+ celt_int32 total_bits, celt_int32 balance, ec_ctx *ec, int M, int codedBands, ec_uint32 *seed);
void stereo_decision(const CELTMode *m, celt_norm * restrict X, int *stereo_mode, int len, int M);
--- a/libcelt/celt.c
+++ b/libcelt/celt.c
@@ -691,8 +691,8 @@
int logp;
ec_uint32 budget;
ec_uint32 tell;
- budget = enc->buf->storage*8;
- tell = ec_enc_tell(enc, 0);
+ budget = enc->storage*8;
+ tell = ec_tell(enc);
logp = isTransient ? 2 : 4;
/* Reserve space to code the tf_select decision. */
tf_select_rsv = LM>0 && tell+logp+1 <= budget;
@@ -703,7 +703,7 @@
if (tell+logp<=budget)
{ec_enc_bit_logp(enc, tf_res[i] ^ curr, logp);
- tell = ec_enc_tell(enc, 0);
+ tell = ec_tell(enc);
curr = tf_res[i];
tf_changed |= curr;
}
@@ -732,8 +732,8 @@
ec_uint32 budget;
ec_uint32 tell;
- budget = dec->buf->storage*8;
- tell = ec_dec_tell(dec, 0);
+ budget = dec->storage*8;
+ tell = ec_tell(dec);
logp = isTransient ? 2 : 4;
tf_select_rsv = LM>0 && tell+logp+1<=budget;
budget -= tf_select_rsv;
@@ -743,7 +743,7 @@
if (tell+logp<=budget)
{curr ^= ec_dec_bit_logp(dec, logp);
- tell = ec_dec_tell(dec, 0);
+ tell = ec_tell(dec);
tf_changed |= curr;
}
tf_res[i] = curr;
@@ -871,8 +871,7 @@
#endif
int i, c, N;
int bits;
- ec_byte_buffer buf;
- ec_enc _enc;
+ ec_enc _enc;
VARDECL(celt_sig, in);
VARDECL(celt_sig, freq);
VARDECL(celt_norm, X);
@@ -944,7 +943,7 @@
tell=1;
nbFilledBytes=0;
} else {- tell=ec_enc_tell(enc, 0);
+ tell=ec_tell(enc);
nbFilledBytes=(tell+4)>>3;
}
nbAvailableBytes = nbCompressedBytes - nbFilledBytes;
@@ -966,8 +965,7 @@
if (enc==NULL)
{- ec_byte_writeinit_buffer(&buf, compressed, nbCompressedBytes);
- ec_enc_init(&_enc,&buf);
+ ec_enc_init(&_enc, compressed, nbCompressedBytes);
enc = &_enc;
}
@@ -993,7 +991,7 @@
{nbCompressedBytes = nbFilledBytes+max_allowed;
nbAvailableBytes = max_allowed;
- ec_byte_shrink(enc->buf, nbCompressedBytes);
+ ec_enc_shrink(enc, nbCompressedBytes);
}
}
}
@@ -1058,12 +1056,12 @@
effectiveBytes=nbCompressedBytes=IMIN(nbCompressedBytes, nbFilledBytes+2);
total_bits=nbCompressedBytes*8;
nbAvailableBytes=2;
- ec_byte_shrink(enc->buf, nbCompressedBytes);
+ ec_enc_shrink(enc, nbCompressedBytes);
}
/* Pretend we've filled all the remaining bits with zeros
(that's what the initialiser did anyway) */
tell = nbCompressedBytes*8;
- enc->nbits_total+=tell-ec_enc_tell(enc,0);
+ enc->nbits_total+=tell-ec_tell(enc);
}
#ifdef ENABLE_POSTFILTER
if (nbAvailableBytes>12*C && st->start==0 && !silence && !st->disable_pf && st->complexity >= 5)
@@ -1131,7 +1129,7 @@
ec_enc_bits(enc, pitch_index-(16<<octave), 4+octave);
pitch_index -= 1;
ec_enc_bits(enc, qg, 3);
- if (ec_enc_tell(enc, 0)+2<=total_bits)
+ if (ec_tell(enc)+2<=total_bits)
ec_enc_icdf(enc, prefilter_tapset, tapset_icdf, 2);
else
prefilter_tapset = 0;
@@ -1177,7 +1175,7 @@
isTransient = 0;
shortBlocks = 0;
- if (LM>0 && ec_enc_tell(enc, 0)+3<=total_bits)
+ if (LM>0 && ec_tell(enc)+3<=total_bits)
{if (st->complexity > 1)
{@@ -1235,7 +1233,7 @@
tf_encode(st->start, st->end, isTransient, tf_res, LM, tf_select, enc);
st->spread_decision = SPREAD_NORMAL;
- if (ec_enc_tell(enc, 0)+4<=total_bits)
+ if (ec_tell(enc)+4<=total_bits)
{if (shortBlocks || st->complexity < 3 || nbAvailableBytes < 10*C)
{@@ -1284,7 +1282,7 @@
dynalloc_logp = 6;
total_bits<<=BITRES;
total_boost = 0;
- tell = ec_enc_tell(enc, BITRES);
+ tell = ec_tell_frac(enc);
for (i=st->start;i<st->end;i++)
{int width, quanta;
@@ -1303,7 +1301,7 @@
int flag;
flag = j<offsets[i];
ec_enc_bit_logp(enc, flag, dynalloc_loop_logp);
- tell = ec_enc_tell(enc, BITRES);
+ tell = ec_tell_frac(enc);
if (!flag)
break;
boost += quanta;
@@ -1321,7 +1319,7 @@
alloc_trim = alloc_trim_analysis(st->mode, X, bandLogE,
st->mode->nbEBands, LM, C, N);
ec_enc_icdf(enc, alloc_trim, trim_icdf, 7);
- tell = ec_enc_tell(enc, BITRES);
+ tell = ec_tell_frac(enc);
}
/* Variable bitrate */
@@ -1396,7 +1394,7 @@
}
nbCompressedBytes = IMIN(nbCompressedBytes,nbAvailableBytes+nbFilledBytes);
/* This moves the raw bits to take into account the new compressed size */
- ec_byte_shrink(enc->buf, nbCompressedBytes);
+ ec_enc_shrink(enc, nbCompressedBytes);
}
if (C==2)
{@@ -1434,7 +1432,7 @@
ALLOC(fine_priority, st->mode->nbEBands, int);
/* bits = packet size - where we are - safety*/
- bits = (nbCompressedBytes*8<<BITRES) - ec_enc_tell(enc, BITRES) - 1;
+ bits = (nbCompressedBytes*8<<BITRES) - ec_tell_frac(enc) - 1;
anti_collapse_rsv = isTransient&&LM>=2&&bits>=(LM+2<<BITRES) ? (1<<BITRES) : 0;
bits -= anti_collapse_rsv;
codedBands = compute_allocation(st->mode, st->start, st->end, offsets, cap,
@@ -1466,7 +1464,7 @@
anti_collapse_on = st->consec_transient<2;
ec_enc_bits(enc, anti_collapse_on, 1);
}
- quant_energy_finalise(st->mode, st->start, st->end, oldBandE, error, fine_quant, fine_priority, nbCompressedBytes*8-ec_enc_tell(enc, 0), enc, C);
+ quant_energy_finalise(st->mode, st->start, st->end, oldBandE, error, fine_quant, fine_priority, nbCompressedBytes*8-ec_tell(enc), enc, C);
if (silence)
{@@ -1594,7 +1592,7 @@
ec_enc_done(enc);
RESTORE_STACK;
- if (ec_enc_get_error(enc))
+ if (ec_get_error(enc))
return CELT_CORRUPTED_DATA;
else
return nbCompressedBytes;
@@ -2135,7 +2133,6 @@
int spread_decision;
int bits;
ec_dec _dec;
- ec_byte_buffer buf;
VARDECL(celt_sig, freq);
VARDECL(celt_norm, X);
VARDECL(celt_ener, bandE);
@@ -2230,8 +2227,7 @@
if (dec == NULL)
{- ec_byte_readinit(&buf,(unsigned char*)data,len);
- ec_dec_init(&_dec,&buf);
+ ec_dec_init(&_dec,(unsigned char*)data,len);
dec = &_dec;
}
@@ -2246,7 +2242,7 @@
}
total_bits = len*8;
- tell = ec_dec_tell(dec, 0);
+ tell = ec_tell(dec);
if (tell==1)
silence = ec_dec_bit_logp(dec, 15);
@@ -2256,7 +2252,7 @@
{/* Pretend we've read all the remaining bits */
tell = len*8;
- dec->nbits_total+=tell-ec_dec_tell(dec,0);
+ dec->nbits_total+=tell-ec_tell(dec);
}
postfilter_gain = 0;
@@ -2271,7 +2267,7 @@
octave = ec_dec_uint(dec, 6);
postfilter_pitch = (16<<octave)+ec_dec_bits(dec, 4+octave)-1;
qg = ec_dec_bits(dec, 3);
- if (ec_dec_tell(dec, 0)+2<=total_bits)
+ if (ec_tell(dec)+2<=total_bits)
postfilter_tapset = ec_dec_icdf(dec, tapset_icdf, 2);
postfilter_gain = QCONST16(.09375f,15)*(qg+1);
#else /* ENABLE_POSTFILTER */
@@ -2279,13 +2275,13 @@
return CELT_CORRUPTED_DATA;
#endif /* ENABLE_POSTFILTER */
}
- tell = ec_dec_tell(dec, 0);
+ tell = ec_tell(dec);
}
if (LM > 0 && tell+3 <= total_bits)
{isTransient = ec_dec_bit_logp(dec, 3);
- tell = ec_dec_tell(dec, 0);
+ tell = ec_tell(dec);
}
else
isTransient = 0;
@@ -2304,7 +2300,7 @@
ALLOC(tf_res, st->mode->nbEBands, int);
tf_decode(st->start, st->end, isTransient, tf_res, LM, dec);
- tell = ec_dec_tell(dec, 0);
+ tell = ec_tell(dec);
spread_decision = SPREAD_NORMAL;
if (tell+4 <= total_bits)
spread_decision = ec_dec_icdf(dec, spread_icdf, 5);
@@ -2318,7 +2314,7 @@
dynalloc_logp = 6;
total_bits<<=BITRES;
- tell = ec_dec_tell(dec, BITRES);
+ tell = ec_tell_frac(dec);
for (i=st->start;i<st->end;i++)
{int width, quanta;
@@ -2334,7 +2330,7 @@
{int flag;
flag = ec_dec_bit_logp(dec, dynalloc_loop_logp);
- tell = ec_dec_tell(dec, BITRES);
+ tell = ec_tell_frac(dec);
if (!flag)
break;
boost += quanta;
@@ -2351,7 +2347,7 @@
alloc_trim = tell+(6<<BITRES) <= total_bits ?
ec_dec_icdf(dec, trim_icdf, 7) : 5;
- bits = (len*8<<BITRES) - ec_dec_tell(dec, BITRES) - 1;
+ bits = (len*8<<BITRES) - ec_tell_frac(dec) - 1;
anti_collapse_rsv = isTransient&&LM>=2&&bits>=(LM+2<<BITRES) ? (1<<BITRES) : 0;
bits -= anti_collapse_rsv;
codedBands = compute_allocation(st->mode, st->start, st->end, offsets, cap,
@@ -2372,7 +2368,7 @@
}
unquant_energy_finalise(st->mode, st->start, st->end, oldBandE,
- fine_quant, fine_priority, len*8-ec_dec_tell(dec, 0), dec, C);
+ fine_quant, fine_priority, len*8-ec_tell(dec), dec, C);
if (anti_collapse_on)
anti_collapse(st->mode, X, collapse_masks, LM, C, CC, N,
@@ -2476,7 +2472,7 @@
deemphasis(out_syn, pcm, N, CC, st->downsample, st->mode->preemph, st->preemph_memD);
st->loss_count = 0;
RESTORE_STACK;
- if (ec_dec_tell(dec,0) > 8*len || ec_dec_get_error(dec))
+ if (ec_tell(dec) > 8*len || ec_get_error(dec))
return CELT_CORRUPTED_DATA;
else
return CELT_OK;
--- a/libcelt/entcode.c
+++ b/libcelt/entcode.c
@@ -1,4 +1,4 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
+/* Copyright (c) 2001-2011 Timothy B. Terriberry
*/
/*
Redistribution and use in source and binary forms, with or without
@@ -37,14 +37,8 @@
-
-
-
-
+#if !defined(EC_CLZ)
int ec_ilog(ec_uint32 _v){-#if defined(EC_CLZ)
- return EC_CLZ0-EC_CLZ(_v);
-#else
/*On a Pentium M, this branchless version tested as the fastest on
1,000,000,000 random 32-bit integers, edging out a similar version with
branches, and a 256-entry LUT version.*/
@@ -65,6 +59,36 @@
ret|=m;
ret+=!!(_v&0x2);
return ret;
-#endif
}
+#endif
+
+ec_uint32 ec_tell_frac(ec_ctx *_this){+ ec_uint32 nbits;
+ ec_uint32 r;
+ int l;
+ int i;
+ /*To handle the non-integral number of bits still left in the encoder/decoder
+ state, we compute the worst-case number of bits of val that must be
+ encoded to ensure that the value is inside the range for any possible
+ subsequent bits.
+ The computation here is independent of val itself (the decoder does not
+ even track that value), even though the real number of bits used after
+ ec_enc_done() may be 1 smaller if rng is a power of two and the
+ corresponding trailing bits of val are all zeros.
+ If we did try to track that special case, then coding a value with a
+ probability of 1/(1<<n) might sometimes appear to use more than n bits.
+ This may help explain the surprising result that a newly initialized
+ encoder or decoder claims to have used 1 bit.*/
+ nbits=_this->nbits_total<<BITRES;
+ l=EC_ILOG(_this->rng);
+ r=_this->rng>>l-16;
+ for(i=BITRES;i-->0;){+ int b;
+ r=r*r>>15;
+ b=(int)(r>>16);
+ l=l<<1|b;
+ r>>=b;
+ }
+ return nbits-l;
+}
--- a/libcelt/entcode.h
+++ b/libcelt/entcode.h
@@ -1,4 +1,4 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
+/* Copyright (c) 2001-2011 Timothy B. Terriberry
Copyright (c) 2008-2009 Xiph.Org Foundation */
/*
Redistribution and use in source and binary forms, with or without
@@ -42,7 +42,9 @@
typedef celt_int32 ec_int32;
typedef celt_uint32 ec_uint32;
typedef size_t ec_window;
-typedef struct ec_byte_buffer ec_byte_buffer;
+typedef struct ec_ctx ec_ctx;
+typedef struct ec_ctx ec_enc;
+typedef struct ec_ctx ec_dec;
@@ -52,39 +54,81 @@
/*The number of bits to use for the range-coded part of unsigned integers.*/
# define EC_UINT_BITS (8)
+/*The resolution of fractional-precision bit usage measurements, i.e.,
+ 3 => 1/8th bits.*/
+# define BITRES 3
-/*Simple libogg1-style buffer.*/
-struct ec_byte_buffer{- unsigned char *buf;
- ec_uint32 offs;
- ec_uint32 end_offs;
- ec_uint32 storage;
+
+/*The entropy encoder/decoder context.
+ We use the same structure for both, so that common functions like ec_tell()
+ can be used on either one.*/
+struct ec_ctx{+ /*Buffered input/output.*/
+ unsigned char *buf;
+ /*The size of the buffer.*/
+ ec_uint32 storage;
+ /*The offset at which the last byte containing raw bits was read/written.*/
+ ec_uint32 end_offs;
+ /*Bits that will be read from/written at the end.*/
+ ec_window end_window;
+ /*Number of valid bits in end_window.*/
+ int nend_bits;
+ /*The total number of whole bits read/written.
+ This does not include partial bits currently in the range coder.*/
+ int nbits_total;
+ /*The offset at which the next range coder byte will be read/written.*/
+ ec_uint32 offs;
+ /*The number of values in the current range.*/
+ ec_uint32 rng;
+ /*In the decoder: the difference between the top of the current range and
+ the input value, minus one.
+ In the encoder: the low end of the current range.*/
+ ec_uint32 val;
+ /*In the decoder: the saved normalization factor from ec_decode().
+ In the encoder: the number of oustanding carry propagating symbols.*/
+ ec_uint32 ext;
+ /*A buffered input/output symbol, awaiting carry propagation.*/
+ int rem;
+ /*Nonzero if an error occurred.*/
+ int error;
};
-/*Encoding functions.*/
-void ec_byte_writeinit_buffer(ec_byte_buffer *_b, unsigned char *_buf, ec_uint32 _size);
-void ec_byte_shrink(ec_byte_buffer *_b, ec_uint32 _size);
-int ec_byte_write(ec_byte_buffer *_b,unsigned _value);
-int ec_byte_write_at_end(ec_byte_buffer *_b,unsigned _value);
-int ec_byte_write_done(ec_byte_buffer *_b,int _start_bits_available,
- unsigned _end_byte,int _end_bits_used);
-/*Decoding functions.*/
-void ec_byte_readinit(ec_byte_buffer *_b,unsigned char *_buf,ec_uint32 _bytes);
-int ec_byte_read(ec_byte_buffer *_b);
-int ec_byte_read_from_end(ec_byte_buffer *_b);
+
/*Shared functions.*/
-static inline void ec_byte_reset(ec_byte_buffer *_b){- _b->offs=_b->end_offs=0;
+static inline void ec_reset(ec_ctx *_this){+ _this->offs=_this->end_offs=0;
}
-static inline ec_uint32 ec_byte_bytes(ec_byte_buffer *_b){- return _b->offs;
+static inline ec_uint32 ec_range_bytes(ec_ctx *_this){+ return _this->offs;
}
-static inline unsigned char *ec_byte_get_buffer(ec_byte_buffer *_b){- return _b->buf;
+static inline unsigned char *ec_get_buffer(ec_ctx *_this){+ return _this->buf;
}
+
+static inline int ec_get_error(ec_ctx *_this){+ return _this->error;
+}
+
+/*Returns the number of bits "used" by the encoded or decoded symbols so far.
+ This same number can be computed in either the encoder or the decoder, and is
+ suitable for making coding decisions.
+ Return: The number of bits.
+ This will always be slightly larger than the exact value (e.g., all
+ rounding error is in the positive direction).*/
+static inline int ec_tell(ec_ctx *_this){+ return _this->nbits_total-EC_ILOG(_this->rng);
+}
+
+/*Returns the number of bits "used" by the encoded or decoded symbols so far.
+ This same number can be computed in either the encoder or the decoder, and is
+ suitable for making coding decisions.
+ Return: The number of bits scaled by 2**BITRES.
+ This will always be slightly larger than the exact value (e.g., all
+ rounding error is in the positive direction).*/
+ec_uint32 ec_tell_frac(ec_ctx *_this);
int ec_ilog(ec_uint32 _v);
--- a/libcelt/entdec.c
+++ b/libcelt/entdec.c
@@ -1,4 +1,4 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
+/* Copyright (c) 2001-2011 Timothy B. Terriberry
Copyright (c) 2008-2009 Xiph.Org Foundation */
/*
Redistribution and use in source and binary forms, with or without
@@ -34,24 +34,180 @@
#endif
#include <stddef.h>
-#include "entdec.h"
#include "os_support.h"
#include "arch.h"
+#include "entdec.h"
+#include "mfrngcod.h"
-void ec_byte_readinit(ec_byte_buffer *_b,unsigned char *_buf,ec_uint32 _bytes){- _b->buf=_buf;
- _b->offs=_b->end_offs=0;
- _b->storage=_bytes;
+
+
+/*A range decoder.
+ This is an entropy decoder based upon \cite{Mar79}, which is itself a+ rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}.+ It is very similar to arithmetic encoding, except that encoding is done with
+ digits in any base, instead of with bits, and so it is faster when using
+ larger bases (i.e.: a byte).
+ The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$+ is the base, longer than the theoretical optimum, but to my knowledge there
+ is no published justification for this claim.
+ This only seems true when using near-infinite precision arithmetic so that
+ the process is carried out with no rounding errors.
+
+ IBM (the author's employer) never sought to patent the idea, and to my
+ knowledge the algorithm is unencumbered by any patents, though its
+ performance is very competitive with proprietary arithmetic coding.
+ The two are based on very similar ideas, however.
+ An excellent description of implementation details is available at
+ http://www.arturocampos.com/ac_range.html
+ A recent work \cite{MNW98} which proposes several changes to arithmetic+ encoding for efficiency actually re-discovers many of the principles
+ behind range encoding, and presents a good theoretical analysis of them.
+
+ End of stream is handled by writing out the smallest number of bits that
+ ensures that the stream will be correctly decoded regardless of the value of
+ any subsequent bits.
+ ec_tell() can be used to determine how many bits were needed to decode
+ all the symbols thus far; other data can be packed in the remaining bits of
+ the input buffer.
+ @PHDTHESIS{Pas76,+ author="Richard Clark Pasco",
+ title="Source coding algorithms for fast data compression",
+ school="Dept. of Electrical Engineering, Stanford University",
+ address="Stanford, CA",
+ month=May,
+ year=1976
+ }
+ @INPROCEEDINGS{Mar79,+ author="Martin, G.N.N.",
+ title="Range encoding: an algorithm for removing redundancy from a digitised
+ message",
+ booktitle="Video & Data Recording Conference",
+ year=1979,
+ address="Southampton",
+ month=Jul
+ }
+ @ARTICLE{MNW98,+ author="Alistair Moffat and Radford Neal and Ian H. Witten",
+ title="Arithmetic Coding Revisited",
+ journal="{ACM} Transactions on Information Systems",+ year=1998,
+ volume=16,
+ number=3,
+ pages="256--294",
+ month=Jul,
+ URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
+ }*/
+
+
+
+static int ec_read_byte(ec_dec *_this){+ return _this->offs<_this->storage?_this->buf[_this->offs++]:0;
}
-int ec_byte_read(ec_byte_buffer *_b){- return _b->offs<_b->storage?_b->buf[_b->offs++]:0;
+static int ec_read_byte_from_end(ec_dec *_this){+ return _this->end_offs<_this->storage?
+ _this->buf[_this->storage-++(_this->end_offs)]:0;
}
-int ec_byte_read_from_end(ec_byte_buffer *_b){- return _b->end_offs<_b->storage?_b->buf[_b->storage-++(_b->end_offs)]:0;
+
+/*Normalizes the contents of val and rng so that rng lies entirely in the
+ high-order symbol.*/
+static void ec_dec_normalize(ec_dec *_this){+ /*If the range is too small, rescale it and input some bits.*/
+ while(_this->rng<=EC_CODE_BOT){+ int sym;
+ _this->nbits_total+=EC_SYM_BITS;
+ _this->rng<<=EC_SYM_BITS;
+ /*Use up the remaining bits from our last symbol.*/
+ sym=_this->rem;
+ /*Read the next value from the input.*/
+ _this->rem=ec_read_byte(_this);
+ /*Take the rest of the bits we need from this new symbol.*/
+ sym=(sym<<EC_SYM_BITS|_this->rem)>>EC_SYM_BITS-EC_CODE_EXTRA;
+ /*And subtract them from val, capped to be less than EC_CODE_TOP.*/
+ _this->val=(_this->val<<EC_SYM_BITS)+(EC_SYM_MAX&~sym)&EC_CODE_TOP-1;
+ }
}
+void ec_dec_init(ec_dec *_this,unsigned char *_buf,ec_uint32 _storage){+ _this->buf=_buf;
+ _this->storage=_storage;
+ _this->end_offs=0;
+ _this->end_window=0;
+ _this->nend_bits=0;
+ _this->offs=0;
+ _this->rng=1U<<EC_CODE_EXTRA;
+ _this->rem=ec_read_byte(_this);
+ _this->val=_this->rng-1-(_this->rem>>EC_SYM_BITS-EC_CODE_EXTRA);
+ _this->error=0;
+ /*Normalize the interval.*/
+ ec_dec_normalize(_this);
+ /*This is the offset from which ec_tell() will subtract partial bits.
+ This must be after the initial ec_dec_normalize(), or you will have to
+ compensate for the bits that are read there.*/
+ _this->nbits_total=EC_CODE_BITS+1;
+}
+
+
+unsigned ec_decode(ec_dec *_this,unsigned _ft){+ unsigned s;
+ _this->ext=_this->rng/_ft;
+ s=(unsigned)(_this->val/_this->ext);
+ return _ft-EC_MINI(s+1,_ft);
+}
+
+unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){+ unsigned s;
+ _this->ext=_this->rng>>_bits;
+ s=(unsigned)(_this->val/_this->ext);
+ return (1<<_bits)-EC_MINI(s+1,1<<_bits);
+}
+
+void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){+ ec_uint32 s;
+ s=IMUL32(_this->ext,_ft-_fh);
+ _this->val-=s;
+ _this->rng=_fl>0?IMUL32(_this->ext,_fh-_fl):_this->rng-s;
+ ec_dec_normalize(_this);
+}
+
+/*The probability of having a "one" is 1/(1<<_logp).*/
+int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){+ ec_uint32 r;
+ ec_uint32 d;
+ ec_uint32 s;
+ int ret;
+ r=_this->rng;
+ d=_this->val;
+ s=r>>_logp;
+ ret=d<s;
+ if(!ret)_this->val=d-s;
+ _this->rng=ret?s:r-s;
+ ec_dec_normalize(_this);
+ return ret;
+}
+
+int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){+ ec_uint32 r;
+ ec_uint32 d;
+ ec_uint32 s;
+ ec_uint32 t;
+ int ret;
+ s=_this->rng;
+ d=_this->val;
+ r=s>>_ftb;
+ ret=-1;
+ do{+ t=s;
+ s=IMUL32(r,_icdf[++ret]);
+ }
+ while(d<s);
+ _this->val=d-s;
+ _this->rng=t-s;
+ ec_dec_normalize(_this);
+ return ret;
+}
+
ec_uint32 ec_dec_uint(ec_dec *_this,ec_uint32 _ft){unsigned ft;
unsigned s;
@@ -79,6 +235,24 @@
}
}
-int ec_dec_get_error(ec_dec *_this){- return _this->error;
+ec_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){+ ec_window window;
+ int available;
+ ec_uint32 ret;
+ window=_this->end_window;
+ available=_this->nend_bits;
+ if(available<_bits){+ do{+ window|=(ec_window)ec_read_byte_from_end(_this)<<available;
+ available+=EC_SYM_BITS;
+ }
+ while(available<=EC_WINDOW_SIZE-EC_SYM_BITS);
+ }
+ ret=(ec_uint32)window&((ec_uint32)1<<_bits)-1;
+ window>>=_bits;
+ available-=_bits;
+ _this->end_window=window;
+ _this->nend_bits=available;
+ _this->nbits_total+=_bits;
+ return ret;
}
--- a/libcelt/entdec.h
+++ b/libcelt/entdec.h
@@ -1,4 +1,4 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
+/* Copyright (c) 2001-2011 Timothy B. Terriberry
Copyright (c) 2008-2009 Xiph.Org Foundation */
/*
Redistribution and use in source and binary forms, with or without
@@ -36,38 +36,11 @@
-typedef struct ec_dec ec_dec;
-
-
-
-/*The entropy decoder.*/
-struct ec_dec{- /*The buffer to decode.*/
- ec_byte_buffer *buf;
- /*The remainder of a buffered input symbol.*/
- int rem;
- /*The number of values in the current range.*/
- ec_uint32 rng;
- /*The difference between the top of the current range and the input value,
- minus one.*/
- ec_uint32 dif;
- /*Normalization factor.*/
- ec_uint32 nrm;
- /*Bits that were written at the end.*/
- ec_window end_window;
- /*Number of valid bits in end_window.*/
- int nend_bits;
- /*The total number of whole bits read.*/
- int nbits_total;
- /*Nonzero if an error occurred.*/
- int error;
-};
-
-
/*Initializes the decoder.
_buf: The input buffer to use.
Return: 0 on success, or a negative value on error.*/
-void ec_dec_init(ec_dec *_this,ec_byte_buffer *_buf);
+void ec_dec_init(ec_dec *_this,unsigned char *_buf,ec_uint32 _storage);
+
/*Calculates the cumulative frequency for the next symbol.
This can then be fed into the probability model to determine what that
symbol is, and the additional frequency information required to advance to
@@ -82,6 +55,8 @@
up to and including the one encoded is fh, then the returned value
will fall in the range [fl,fh).*/
unsigned ec_decode(ec_dec *_this,unsigned _ft);
+
+/*Equivalent to ec_decode() with _ft==1<<_bits.*/
unsigned ec_decode_bin(ec_dec *_this,unsigned _bits);
/*Advance the decoder past the next symbol using the frequency information the
@@ -97,22 +72,11 @@
_ft: The total frequency of the symbols in the alphabet the symbol decoded
was encoded in.
This must be the same as passed to the preceding call to ec_decode().*/
-void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,
- unsigned _ft);
-/*Extracts a sequence of raw bits from the stream.
- The bits must have been encoded with ec_enc_bits().
- No call to ec_dec_update() is necessary after this call.
- _ftb: The number of bits to extract.
- This must be between 0 and 25, inclusive.
- Return: The decoded bits.*/
-ec_uint32 ec_dec_bits(ec_dec *_this,unsigned _ftb);
-/*Extracts a raw unsigned integer with a non-power-of-2 range from the stream.
- The bits must have been encoded with ec_enc_uint().
- No call to ec_dec_update() is necessary after this call.
- _ft: The number of integers that can be decoded (one more than the max).
- This must be at least one, and no more than 2**32-1.
- Return: The decoded bits.*/
-ec_uint32 ec_dec_uint(ec_dec *_this,ec_uint32 _ft);
+void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft);
+
+/* Decode a bit that has a 1/(1<<_logp) probability of being a one */
+int ec_dec_bit_logp(ec_dec *_this,unsigned _logp);
+
/*Decodes a symbol given an "inverse" CDF table.
No call to ec_dec_update() is necessary after this call.
_icdf: The "inverse" CDF, such that symbol s falls in the range
@@ -123,23 +87,20 @@
Return: The decoded symbol s.*/
int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb);
-/* Decode a bit that has a _prob/65536 probability of being a one */
-int ec_dec_bit_prob(ec_dec *_this,unsigned _prob);
+/*Extracts a raw unsigned integer with a non-power-of-2 range from the stream.
+ The bits must have been encoded with ec_enc_uint().
+ No call to ec_dec_update() is necessary after this call.
+ _ft: The number of integers that can be decoded (one more than the max).
+ This must be at least one, and no more than 2**32-1.
+ Return: The decoded bits.*/
+ec_uint32 ec_dec_uint(ec_dec *_this,ec_uint32 _ft);
-/* Decode a bit that has a 1/(1<<_logp) probability of being a one */
-int ec_dec_bit_logp(ec_dec *_this,unsigned _logp);
-
-/*Returns the number of bits "used" by the encoded symbols so far.
- This same number can be computed by the encoder, and is suitable for making
- coding decisions.
- _b: The number of extra bits of precision to include.
- At most 16 will be accurate.
- Return: The number of bits scaled by 2**_b.
- This will always be slightly larger than the exact value (e.g., all
- rounding error is in the positive direction).*/
-ec_uint32 ec_dec_tell(ec_dec *_this,int _b);
-
-/*Return: A nonzero value if any error has been detected during decoding.*/
-int ec_dec_get_error(ec_dec *_this);
+/*Extracts a sequence of raw bits from the stream.
+ The bits must have been encoded with ec_enc_bits().
+ No call to ec_dec_update() is necessary after this call.
+ _ftb: The number of bits to extract.
+ This must be between 0 and 25, inclusive.
+ Return: The decoded bits.*/
+ec_uint32 ec_dec_bits(ec_dec *_this,unsigned _ftb);
#endif
--- a/libcelt/entenc.c
+++ b/libcelt/entenc.c
@@ -1,4 +1,4 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
+/* Copyright (c) 2001-2011 Timothy B. Terriberry
Copyright (c) 2008-2009 Xiph.Org Foundation */
/*
Redistribution and use in source and binary forms, with or without
@@ -33,58 +33,154 @@
# include "config.h"
#endif
#include "os_support.h"
-#include "entenc.h"
#include "arch.h"
+#include "entenc.h"
+#include "mfrngcod.h"
-void ec_byte_writeinit_buffer(ec_byte_buffer *_b,
- unsigned char *_buf,ec_uint32 _size){- _b->buf=_buf;
- _b->end_offs=_b->offs=0;
- _b->storage=_size;
-}
-void ec_byte_shrink(ec_byte_buffer *_b,ec_uint32 _size){- celt_assert(_b->offs+_b->end_offs<=_size);
- CELT_MOVE(_b->buf+_size-_b->end_offs,
- _b->buf+_b->storage-_b->end_offs,_b->end_offs);
- _b->storage=_size;
-}
+/*A range encoder.
+ See entdec.c and the references for implementation details \cite{Mar79,MNW98}.-int ec_byte_write(ec_byte_buffer *_b,unsigned _value){- if(_b->offs+_b->end_offs>=_b->storage)return -1;
- _b->buf[_b->offs++]=(unsigned char)_value;
+ @INPROCEEDINGS{Mar79,+ author="Martin, G.N.N.",
+ title="Range encoding: an algorithm for removing redundancy from a digitised
+ message",
+ booktitle="Video \& Data Recording Conference",
+ year=1979,
+ address="Southampton",
+ month=Jul
+ }
+ @ARTICLE{MNW98,+ author="Alistair Moffat and Radford Neal and Ian H. Witten",
+ title="Arithmetic Coding Revisited",
+ journal="{ACM} Transactions on Information Systems",+ year=1998,
+ volume=16,
+ number=3,
+ pages="256--294",
+ month=Jul,
+ URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
+ }*/
+
+
+
+static int ec_write_byte(ec_enc *_this,unsigned _value){+ if(_this->offs+_this->end_offs>=_this->storage)return -1;
+ _this->buf[_this->offs++]=(unsigned char)_value;
return 0;
}
-int ec_byte_write_at_end(ec_byte_buffer *_b,unsigned _value){- if(_b->offs+_b->end_offs>=_b->storage)return -1;
- _b->buf[_b->storage-++(_b->end_offs)]=(unsigned char)_value;
+static int ec_write_byte_at_end(ec_enc *_this,unsigned _value){+ if(_this->offs+_this->end_offs>=_this->storage)return -1;
+ _this->buf[_this->storage-++(_this->end_offs)]=(unsigned char)_value;
return 0;
}
-int ec_byte_write_done(ec_byte_buffer *_b,int _start_bits_available,
- unsigned _end_byte,int _end_bits_used){- int ret;
- CELT_MEMSET(_b->buf+_b->offs,0,_b->storage-_b->offs-_b->end_offs);
- ret=0;
- if(_end_bits_used>0){- if(_b->offs+_b->end_offs>=_b->storage){- /*If there's no range coder data at all, give up.*/
- if(_b->end_offs>=_b->storage)return -1;
- /*If we've busted, don't add too many extra bits to the last byte; it
- would corrupt the range coder data, and that's more important.*/
- if(_start_bits_available<_end_bits_used){- _end_bits_used=_start_bits_available;
- _end_byte&=(1<<_start_bits_available)-1;
- ret=-1;
- }
+
+/*Outputs a symbol, with a carry bit.
+ If there is a potential to propagate a carry over several symbols, they are
+ buffered until it can be determined whether or not an actual carry will
+ occur.
+ If the counter for the buffered symbols overflows, then the stream becomes
+ undecodable.
+ This gives a theoretical limit of a few billion symbols in a single packet on
+ 32-bit systems.
+ The alternative is to truncate the range in order to force a carry, but
+ requires similar carry tracking in the decoder, needlessly slowing it down.*/
+static void ec_enc_carry_out(ec_enc *_this,int _c){+ if(_c!=EC_SYM_MAX){+ /*No further carry propagation possible, flush buffer.*/
+ int carry;
+ carry=_c>>EC_SYM_BITS;
+ /*Don't output a byte on the first write.
+ This compare should be taken care of by branch-prediction thereafter.*/
+ if(_this->rem>=0)_this->error|=ec_write_byte(_this,_this->rem+carry);
+ if(_this->ext>0){+ unsigned sym;
+ sym=EC_SYM_MAX+carry&EC_SYM_MAX;
+ do _this->error|=ec_write_byte(_this,sym);
+ while(--(_this->ext)>0);
}
- _b->buf[_b->storage-_b->end_offs-1]|=_end_byte;
+ _this->rem=_c&EC_SYM_MAX;
}
- return ret;
+ else _this->ext++;
}
+static void ec_enc_normalize(ec_enc *_this){+ /*If the range is too small, output some bits and rescale it.*/
+ while(_this->rng<=EC_CODE_BOT){+ ec_enc_carry_out(_this,(int)(_this->val>>EC_CODE_SHIFT));
+ /*Move the next-to-high-order symbol into the high-order position.*/
+ _this->val=_this->val<<EC_SYM_BITS&EC_CODE_TOP-1;
+ _this->rng<<=EC_SYM_BITS;
+ _this->nbits_total+=EC_SYM_BITS;
+ }
+}
+
+void ec_enc_init(ec_enc *_this,unsigned char *_buf,ec_uint32 _size){+ _this->buf=_buf;
+ _this->end_offs=0;
+ _this->end_window=0;
+ _this->nend_bits=0;
+ /*This is the offset from which ec_tell() will subtract partial bits.*/
+ _this->nbits_total=EC_CODE_BITS+1;
+ _this->offs=0;
+ _this->rng=EC_CODE_TOP;
+ _this->rem=-1;
+ _this->val=0;
+ _this->ext=0;
+ _this->storage=_size;
+ _this->error=0;
+}
+
+void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){+ ec_uint32 r;
+ r=_this->rng/_ft;
+ if(_fl>0){+ _this->val+=_this->rng-IMUL32(r,(_ft-_fl));
+ _this->rng=IMUL32(r,(_fh-_fl));
+ }
+ else _this->rng-=IMUL32(r,(_ft-_fh));
+ ec_enc_normalize(_this);
+}
+
+void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){+ ec_uint32 r;
+ r=_this->rng>>_bits;
+ if(_fl>0){+ _this->val+=_this->rng-IMUL32(r,((1<<_bits)-_fl));
+ _this->rng=IMUL32(r,(_fh-_fl));
+ }
+ else _this->rng-=IMUL32(r,((1<<_bits)-_fh));
+ ec_enc_normalize(_this);
+}
+
+/*The probability of having a "one" is 1/(1<<_logp).*/
+void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){+ ec_uint32 r;
+ ec_uint32 s;
+ ec_uint32 l;
+ r=_this->rng;
+ l=_this->val;
+ s=r>>_logp;
+ r-=s;
+ if(_val)_this->val=l+r;
+ _this->rng=_val?s:r;
+ ec_enc_normalize(_this);
+}
+
+void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){+ ec_uint32 r;
+ r=_this->rng>>_ftb;
+ if(_s>0){+ _this->val+=_this->rng-IMUL32(r,_icdf[_s-1]);
+ _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
+ }
+ else _this->rng-=IMUL32(r,_icdf[_s]);
+ ec_enc_normalize(_this);
+}
+
void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft){unsigned ft;
unsigned fl;
@@ -103,6 +199,81 @@
else ec_encode(_this,_fl,_fl+1,_ft+1);
}
-int ec_enc_get_error(ec_enc *_this){- return _this->error;
+void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,unsigned _bits){+ ec_window window;
+ int used;
+ window=_this->end_window;
+ used=_this->nend_bits;
+ if(used+_bits>EC_WINDOW_SIZE){+ do{+ _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
+ window>>=EC_SYM_BITS;
+ used-=EC_SYM_BITS;
+ }
+ while(used>=EC_SYM_BITS);
+ }
+ window|=(ec_window)_fl<<used;
+ used+=_bits;
+ _this->end_window=window;
+ _this->nend_bits=used;
+ _this->nbits_total+=_bits;
+}
+
+void ec_enc_shrink(ec_enc *_this,ec_uint32 _size){+ celt_assert(_this->offs+_this->end_offs<=_size);
+ CELT_MOVE(_this->buf+_size-_this->end_offs,
+ _this->buf+_this->storage-_this->end_offs,_this->end_offs);
+ _this->storage=_size;
+}
+
+void ec_enc_done(ec_enc *_this){+ ec_window window;
+ int used;
+ ec_uint32 msk;
+ ec_uint32 end;
+ int l;
+ /*We output the minimum number of bits that ensures that the symbols encoded
+ thus far will be decoded correctly regardless of the bits that follow.*/
+ l=EC_CODE_BITS-EC_ILOG(_this->rng);
+ msk=EC_CODE_TOP-1>>l;
+ end=_this->val+msk&~msk;
+ if((end|msk)>=_this->val+_this->rng){+ l++;
+ msk>>=1;
+ end=_this->val+msk&~msk;
+ }
+ while(l>0){+ ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
+ end=end<<EC_SYM_BITS&EC_CODE_TOP-1;
+ l-=EC_SYM_BITS;
+ }
+ /*If we have a buffered byte flush it into the output buffer.*/
+ if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
+ /*If we have buffered extra bits, flush them as well.*/
+ window=_this->end_window;
+ used=_this->nend_bits;
+ while(used>=EC_SYM_BITS){+ _this->error|=ec_write_byte_at_end(_this,(unsigned)window&EC_SYM_MAX);
+ window>>=EC_SYM_BITS;
+ used-=EC_SYM_BITS;
+ }
+ /*Clear any excess space and add any remaining extra bits to the last byte.*/
+ if(!_this->error){+ CELT_MEMSET(_this->buf+_this->offs,0,
+ _this->storage-_this->offs-_this->end_offs);
+ if(used>0){+ /*If there's no range coder data at all, give up.*/
+ if(_this->end_offs>=_this->storage)_this->error=-1;
+ else{+ l=-l;
+ /*If we've busted, don't add too many extra bits to the last byte; it
+ would corrupt the range coder data, and that's more important.*/
+ if(_this->offs+_this->end_offs>=_this->storage&&l<used){+ window&=(1<<l)-1;
+ _this->error=-1;
+ }
+ }
+ _this->buf[_this->storage-_this->end_offs-1]|=(unsigned char)window;
+ }
+ }
}
--- a/libcelt/entenc.h
+++ b/libcelt/entenc.h
@@ -1,4 +1,4 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
+/* Copyright (c) 2001-2011 Timothy B. Terriberry
Copyright (c) 2008-2009 Xiph.Org Foundation */
/*
Redistribution and use in source and binary forms, with or without
@@ -36,37 +36,10 @@
-typedef struct ec_enc ec_enc;
-
-
-
-/*The entropy encoder.*/
-struct ec_enc{- /*Buffered output.*/
- ec_byte_buffer *buf;
- /*A buffered output symbol, awaiting carry propagation.*/
- int rem;
- /*Number of extra carry propagating symbols.*/
- size_t ext;
- /*The number of values in the current range.*/
- ec_uint32 rng;
- /*The low end of the current range (inclusive).*/
- ec_uint32 low;
- /*Bits that will be written at the end.*/
- ec_window end_window;
- /*Number of valid bits in end_window.*/
- int nend_bits;
- /*The total number of whole bits written.*/
- int nbits_total;
- /*Nonzero if an error occurred.*/
- int error;
-};
-
-
/*Initializes the encoder.
- _buf: The buffer to store output bytes in.
- This must have already been initialized for writing and reset.*/
-void ec_enc_init(ec_enc *_this,ec_byte_buffer *_buf);
+ _buf: The buffer to store output bytes in.
+ _size: The size of the buffer, in chars.*/
+void ec_enc_init(ec_enc *_this,unsigned char *_buf,ec_uint32 _size);
/*Encodes a symbol given its frequency information.
The frequency information must be discernable by the decoder, assuming it
has read only the previous symbols from the stream.
@@ -81,22 +54,10 @@
decoded value will fall.
_ft: The sum of the frequencies of all the symbols*/
void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft);
+
+/*Equivalent to ec_encode() with _ft==1<<_bits.*/
void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits);
-/*Encodes a sequence of raw bits in the stream.
- _fl: The bits to encode.
- _ftb: The number of bits to encode.
- This must be between 0 and 25, inclusive.*/
-void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,unsigned _ftb);
-/*Encodes a raw unsigned integer in the stream.
- _fl: The integer to encode.
- _ft: The number of integers that can be encoded (one more than the max).
- This must be at least one, and no more than 2**32-1.*/
-void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft);
-
-/* Encode a bit that has a _prob/65536 probability of being a one */
-void ec_enc_bit_prob(ec_enc *_this,int val,unsigned _prob);
-
/* Encode a bit that has a 1/(1<<_logp) probability of being a one */
void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp);
@@ -109,22 +70,31 @@
_ftb: The number of bits of precision in the cumulative distribution.*/
void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb);
-/*Returns the number of bits "used" by the encoded symbols so far.
- This same number can be computed by the decoder, and is suitable for making
- coding decisions.
- _b: The number of extra bits of precision to include.
- At most 16 will be accurate.
- Return: The number of bits scaled by 2**_b.
- This will always be slightly larger than the exact value (e.g., all
- rounding error is in the positive direction).*/
-ec_uint32 ec_enc_tell(ec_enc *_this,int _b);
+/*Encodes a raw unsigned integer in the stream.
+ _fl: The integer to encode.
+ _ft: The number of integers that can be encoded (one more than the max).
+ This must be at least one, and no more than 2**32-1.*/
+void ec_enc_uint(ec_enc *_this,ec_uint32 _fl,ec_uint32 _ft);
+/*Encodes a sequence of raw bits in the stream.
+ _fl: The bits to encode.
+ _ftb: The number of bits to encode.
+ This must be between 0 and 25, inclusive.*/
+void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,unsigned _ftb);
+
+/*Compacts the data to fit in the target size.
+ This moves up the raw bits at the end of the current buffer so they are at
+ the end of the new buffer size.
+ The caller must ensure that the amount of data that's already been written
+ will fit in the new size.
+ _size: The number of bytes in the new buffer.
+ This must be large enough to contain the bits already written, and
+ must be no larger than the existing size.*/
+void ec_enc_shrink(ec_enc *_this,ec_uint32 _size);
+
/*Indicates that there are no more symbols to encode.
All reamining output bytes are flushed to the output buffer.
ec_enc_init() must be called before the encoder can be used again.*/
void ec_enc_done(ec_enc *_this);
-
-/*Returns a nonzero value if any error has been detected during encoding*/
-int ec_enc_get_error(ec_enc *_this);
#endif
--- a/libcelt/quant_bands.c
+++ b/libcelt/quant_bands.c
@@ -218,7 +218,7 @@
qi0 = qi;
/* If we don't have enough bits to encode all the energy, just assume
something safe. */
- tell = ec_enc_tell(enc, 0);
+ tell = ec_tell(enc);
bits_left = budget-tell-3*C*(end-i);
if (i!=start && bits_left < 30)
{@@ -272,7 +272,6 @@
VARDECL(celt_word16, oldEBands_intra);
VARDECL(celt_word16, error_intra);
ec_enc enc_start_state;
- ec_byte_buffer buf_start_state;
ec_uint32 tell;
int badness1=0;
SAVE_STACK;
@@ -283,7 +282,7 @@
else
*delayedIntra = 0;
- tell = ec_enc_tell(enc, 0);
+ tell = ec_tell(enc);
if (tell+3 > budget)
two_pass = intra = 0;
@@ -297,7 +296,6 @@
#endif
enc_start_state = *enc;
- buf_start_state = *(enc->buf);
ALLOC(oldEBands_intra, C*m->nbEBands, celt_word16);
ALLOC(error_intra, C*m->nbEBands, celt_word16);
@@ -312,7 +310,6 @@
if (!intra)
{ec_enc enc_intra_state;
- ec_byte_buffer buf_intra_state;
int tell_intra;
ec_uint32 nstart_bytes;
ec_uint32 nintra_bytes;
@@ -319,31 +316,28 @@
int badness2;
VARDECL(unsigned char, intra_bits);
- tell_intra = ec_enc_tell(enc, 3);
+ tell_intra = ec_tell_frac(enc);
enc_intra_state = *enc;
- buf_intra_state = *(enc->buf);
- nstart_bytes = ec_byte_bytes(&buf_start_state);
- nintra_bytes = ec_byte_bytes(&buf_intra_state);
+ nstart_bytes = ec_range_bytes(&enc_start_state);
+ nintra_bytes = ec_range_bytes(&enc_intra_state);
ALLOC(intra_bits, nintra_bytes-nstart_bytes, unsigned char);
/* Copy bits from intra bit-stream */
CELT_COPY(intra_bits,
- ec_byte_get_buffer(&buf_intra_state) + nstart_bytes,
+ ec_get_buffer(&enc_intra_state) + nstart_bytes,
nintra_bytes - nstart_bytes);
*enc = enc_start_state;
- *(enc->buf) = buf_start_state;
badness2 = quant_coarse_energy_impl(m, start, end, eBands, oldEBands, budget,
tell, e_prob_model[LM][intra], error, enc, C, LM, 0, max_decay);
- if (two_pass && (badness1 < badness2 || (badness1 == badness2 && ec_enc_tell(enc, 3) > tell_intra)))
+ if (two_pass && (badness1 < badness2 || (badness1 == badness2 && ec_tell_frac(enc) > tell_intra)))
{*enc = enc_intra_state;
- *(enc->buf) = buf_intra_state;
/* Copy intra bits to bit-stream */
- CELT_COPY(ec_byte_get_buffer(&buf_intra_state) + nstart_bytes,
+ CELT_COPY(ec_get_buffer(&enc_intra_state) + nstart_bytes,
intra_bits, nintra_bytes - nstart_bytes);
CELT_COPY(oldEBands, oldEBands_intra, C*end);
CELT_COPY(error, error_intra, C*end);
@@ -444,7 +438,7 @@
coef = pred_coef[LM];
}
- budget = dec->buf->storage*8;
+ budget = dec->storage*8;
/* Decode at a fixed coarse resolution */
for (i=start;i<end;i++)
@@ -454,7 +448,7 @@
int qi;
celt_word32 q;
celt_word32 tmp;
- tell = ec_dec_tell(dec, 0);
+ tell = ec_tell(dec);
if(budget-tell>=15)
{int pi;
--- a/libcelt/rangedec.c
+++ /dev/null
@@ -1,260 +1,0 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
- Copyright (c) 2008-2009 Xiph.Org Foundation */
-/*
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
-
- - Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
-
- - Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-
- - Neither the name of the Xiph.org Foundation nor the names of its
- contributors may be used to endorse or promote products derived from
- this software without specific prior written permission.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR
- CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-*/
-
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include "arch.h"
-#include "entdec.h"
-#include "mfrngcod.h"
-
-
-
-/*A range decoder.
- This is an entropy decoder based upon \cite{Mar79}, which is itself a- rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}.- It is very similar to arithmetic encoding, except that encoding is done with
- digits in any base, instead of with bits, and so it is faster when using
- larger bases (i.e.: a byte).
- The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$- is the base, longer than the theoretical optimum, but to my knowledge there
- is no published justification for this claim.
- This only seems true when using near-infinite precision arithmetic so that
- the process is carried out with no rounding errors.
-
- IBM (the author's employer) never sought to patent the idea, and to my
- knowledge the algorithm is unencumbered by any patents, though its
- performance is very competitive with proprietary arithmetic coding.
- The two are based on very similar ideas, however.
- An excellent description of implementation details is available at
- http://www.arturocampos.com/ac_range.html
- A recent work \cite{MNW98} which proposes several changes to arithmetic- encoding for efficiency actually re-discovers many of the principles
- behind range encoding, and presents a good theoretical analysis of them.
-
- End of stream is handled by writing out the smallest number of bits that
- ensures that the stream will be correctly decoded regardless of the value of
- any subsequent bits.
- ec_dec_tell() can be used to determine how many bits were needed to decode
- all the symbols thus far; other data can be packed in the remaining bits of
- the input buffer.
- @PHDTHESIS{Pas76,- author="Richard Clark Pasco",
- title="Source coding algorithms for fast data compression",
- school="Dept. of Electrical Engineering, Stanford University",
- address="Stanford, CA",
- month=May,
- year=1976
- }
- @INPROCEEDINGS{Mar79,- author="Martin, G.N.N.",
- title="Range encoding: an algorithm for removing redundancy from a digitised
- message",
- booktitle="Video & Data Recording Conference",
- year=1979,
- address="Southampton",
- month=Jul
- }
- @ARTICLE{MNW98,- author="Alistair Moffat and Radford Neal and Ian H. Witten",
- title="Arithmetic Coding Revisited",
- journal="{ACM} Transactions on Information Systems",- year=1998,
- volume=16,
- number=3,
- pages="256--294",
- month=Jul,
- URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
- }*/
-
-
-/*Normalizes the contents of dif and rng so that rng lies entirely in the
- high-order symbol.*/
-static inline void ec_dec_normalize(ec_dec *_this){- /*If the range is too small, rescale it and input some bits.*/
- while(_this->rng<=EC_CODE_BOT){- int sym;
- _this->nbits_total+=EC_SYM_BITS;
- _this->rng<<=EC_SYM_BITS;
- /*Use up the remaining bits from our last symbol.*/
- sym=_this->rem;
- /*Read the next value from the input.*/
- _this->rem=ec_byte_read(_this->buf);
- /*Take the rest of the bits we need from this new symbol.*/
- sym=(sym<<EC_SYM_BITS|_this->rem)>>EC_SYM_BITS-EC_CODE_EXTRA;
- /*And subtract them from dif, capped to be less than EC_CODE_TOP.*/
- _this->dif=(_this->dif<<EC_SYM_BITS)+(EC_SYM_MAX&~sym)&EC_CODE_TOP-1;
- }
-}
-
-void ec_dec_init(ec_dec *_this,ec_byte_buffer *_buf){- _this->buf=_buf;
- _this->rem=ec_byte_read(_buf);
- _this->rng=1U<<EC_CODE_EXTRA;
- _this->dif=_this->rng-1-(_this->rem>>EC_SYM_BITS-EC_CODE_EXTRA);
- /*Normalize the interval.*/
- ec_dec_normalize(_this);
- _this->end_window=0;
- _this->nend_bits=0;
- /*This is the offset from which ec_enc_tell() will subtract partial bits.
- This must be after the initial ec_dec_normalize(), or you will have to
- compensate for the bits that are read there.*/
- _this->nbits_total=EC_CODE_BITS+1;
- _this->error=0;
-}
-
-
-unsigned ec_decode(ec_dec *_this,unsigned _ft){- unsigned s;
- _this->nrm=_this->rng/_ft;
- s=(unsigned)(_this->dif/_this->nrm);
- return _ft-EC_MINI(s+1,_ft);
-}
-
-unsigned ec_decode_bin(ec_dec *_this,unsigned _bits){- unsigned s;
- _this->nrm=_this->rng>>_bits;
- s=(unsigned)(_this->dif/_this->nrm);
- return (1<<_bits)-EC_MINI(s+1,1<<_bits);
-}
-
-void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){- ec_uint32 s;
- s=IMUL32(_this->nrm,_ft-_fh);
- _this->dif-=s;
- _this->rng=_fl>0?IMUL32(_this->nrm,_fh-_fl):_this->rng-s;
- ec_dec_normalize(_this);
-}
-
-/*The probability of having a "one" is given in 1/65536.*/
-int ec_dec_bit_prob(ec_dec *_this,unsigned _prob){- ec_uint32 r;
- ec_uint32 d;
- ec_uint32 s;
- int val;
- r=_this->rng;
- d=_this->dif;
- s=(r>>16)*_prob;
- val=d<s;
- if(!val)_this->dif=d-s;
- _this->rng=val?s:r-s;
- ec_dec_normalize(_this);
- return val;
-}
-
-/*The probability of having a "one" is 1/(1<<_logp).*/
-int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){- ec_uint32 r;
- ec_uint32 d;
- ec_uint32 s;
- int val;
- r=_this->rng;
- d=_this->dif;
- s=r>>_logp;
- val=d<s;
- if(!val)_this->dif=d-s;
- _this->rng=val?s:r-s;
- ec_dec_normalize(_this);
- return val;
-}
-
-int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){- ec_uint32 r;
- ec_uint32 d;
- ec_uint32 s;
- ec_uint32 t;
- int val;
- s=_this->rng;
- d=_this->dif;
- r=s>>_ftb;
- val=0;
- do{- t=s;
- s=IMUL32(r,_icdf[val++]);
- }
- while(d<s);
- _this->dif=d-s;
- _this->rng=t-s;
- ec_dec_normalize(_this);
- return val-1;
-}
-
-ec_uint32 ec_dec_bits(ec_dec *_this,unsigned _bits){- ec_window window;
- int available;
- ec_uint32 ret;
- window=_this->end_window;
- available=_this->nend_bits;
- if(available<_bits){- do{- window|=(ec_window)ec_byte_read_from_end(_this->buf)<<available;
- available+=EC_SYM_BITS;
- }
- while(available<=EC_WINDOW_SIZE-EC_SYM_BITS);
- }
- ret=(ec_uint32)window&((ec_uint32)1<<_bits)-1;
- window>>=_bits;
- available-=_bits;
- _this->end_window=window;
- _this->nend_bits=available;
- _this->nbits_total+=_bits;
- return ret;
-}
-
-ec_uint32 ec_dec_tell(ec_dec *_this,int _b){- ec_uint32 nbits;
- ec_uint32 r;
- int l;
- /*To handle the non-integral number of bits still left in the decoder state,
- we compute the worst-case number of bits of low that must be encoded to
- ensure that the value is inside the range for any possible subsequent
- bits.
- The computation here is independent of low itself (the decoder does not
- even track that value), even though the real number of bits used after
- ec_enc_done() may be 1 smaller if rng is a power of two and the
- corresponding trailing bits of low are all zeros.
- If we did try to track that special case, then coding a value with a
- probability of 1/(1<<n) might sometimes appear to use more than n bits.
- This may help explain the surprising result that a newly initialized
- decoder claims to have used 1 bit.*/
- nbits=_this->nbits_total<<_b;
- l=EC_ILOG(_this->rng);
- r=_this->rng>>l-16;
- while(_b-->0){- int b;
- r=r*r>>15;
- b=(int)(r>>16);
- l=l<<1|b;
- r>>=b;
- }
- return nbits-l;
-}
--- a/libcelt/rangeenc.c
+++ /dev/null
@@ -1,267 +1,0 @@
-/* Copyright (c) 2001-2008 Timothy B. Terriberry
- Copyright (c) 2008-2009 Xiph.Org Foundation */
-/*
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
-
- - Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
-
- - Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-
- - Neither the name of the Xiph.org Foundation nor the names of its
- contributors may be used to endorse or promote products derived from
- this software without specific prior written permission.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR
- CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
- LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-*/
-
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include "arch.h"
-#include "entenc.h"
-#include "mfrngcod.h"
-
-
-
-/*A range encoder.
- See rangedec.c and the references for implementation details
- \cite{Mar79,MNW98}.-
- @INPROCEEDINGS{Mar79,- author="Martin, G.N.N.",
- title="Range encoding: an algorithm for removing redundancy from a digitised
- message",
- booktitle="Video \& Data Recording Conference",
- year=1979,
- address="Southampton",
- month=Jul
- }
- @ARTICLE{MNW98,- author="Alistair Moffat and Radford Neal and Ian H. Witten",
- title="Arithmetic Coding Revisited",
- journal="{ACM} Transactions on Information Systems",- year=1998,
- volume=16,
- number=3,
- pages="256--294",
- month=Jul,
- URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
- }*/
-
-
-
-/*Outputs a symbol, with a carry bit.
- If there is a potential to propagate a carry over several symbols, they are
- buffered until it can be determined whether or not an actual carry will
- occur.
- If the counter for the buffered symbols overflows, then the stream becomes
- undecodable.
- This gives a theoretical limit of a few billion symbols in a single packet on
- 32-bit systems.
- The alternative is to truncate the range in order to force a carry, but
- requires similar carry tracking in the decoder, needlessly slowing it down.*/
-static void ec_enc_carry_out(ec_enc *_this,int _c){- if(_c!=EC_SYM_MAX){- /*No further carry propagation possible, flush buffer.*/
- int carry;
- carry=_c>>EC_SYM_BITS;
- /*Don't output a byte on the first write.
- This compare should be taken care of by branch-prediction thereafter.*/
- if(_this->rem>=0)_this->error|=ec_byte_write(_this->buf,_this->rem+carry);
- if(_this->ext>0){- unsigned sym;
- sym=EC_SYM_MAX+carry&EC_SYM_MAX;
- do _this->error|=ec_byte_write(_this->buf,sym);
- while(--(_this->ext)>0);
- }
- _this->rem=_c&EC_SYM_MAX;
- }
- else _this->ext++;
-}
-
-static inline void ec_enc_normalize(ec_enc *_this){- /*If the range is too small, output some bits and rescale it.*/
- while(_this->rng<=EC_CODE_BOT){- ec_enc_carry_out(_this,(int)(_this->low>>EC_CODE_SHIFT));
- /*Move the next-to-high-order symbol into the high-order position.*/
- _this->low=_this->low<<EC_SYM_BITS&EC_CODE_TOP-1;
- _this->rng<<=EC_SYM_BITS;
- _this->nbits_total+=EC_SYM_BITS;
- }
-}
-
-void ec_enc_init(ec_enc *_this,ec_byte_buffer *_buf){- _this->buf=_buf;
- _this->rem=-1;
- _this->ext=0;
- _this->low=0;
- _this->rng=EC_CODE_TOP;
- _this->end_window=0;
- _this->nend_bits=0;
- /*This is the offset from which ec_enc_tell() will subtract partial bits.*/
- _this->nbits_total=EC_CODE_BITS+1;
- _this->error=0;
-}
-
-void ec_encode(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _ft){- ec_uint32 r;
- r=_this->rng/_ft;
- if(_fl>0){- _this->low+=_this->rng-IMUL32(r,(_ft-_fl));
- _this->rng=IMUL32(r,(_fh-_fl));
- }
- else _this->rng-=IMUL32(r,(_ft-_fh));
- ec_enc_normalize(_this);
-}
-
-void ec_encode_bin(ec_enc *_this,unsigned _fl,unsigned _fh,unsigned _bits){- ec_uint32 r;
- r=_this->rng>>_bits;
- if(_fl>0){- _this->low+=_this->rng-IMUL32(r,((1<<_bits)-_fl));
- _this->rng=IMUL32(r,(_fh-_fl));
- }
- else _this->rng-=IMUL32(r,((1<<_bits)-_fh));
- ec_enc_normalize(_this);
-}
-
-/*The probability of having a "one" is given in 1/65536.*/
-void ec_enc_bit_prob(ec_enc *_this,int _val,unsigned _prob){- ec_uint32 r;
- ec_uint32 s;
- ec_uint32 l;
- r=_this->rng;
- l=_this->low;
- s=(r>>16)*_prob;
- r-=s;
- if(_val)_this->low=l+r;
- _this->rng=_val?s:r;
- ec_enc_normalize(_this);
-}
-
-/*The probability of having a "one" is 1/(1<<_logp).*/
-void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){- ec_uint32 r;
- ec_uint32 s;
- ec_uint32 l;
- r=_this->rng;
- l=_this->low;
- s=r>>_logp;
- r-=s;
- if(_val)_this->low=l+r;
- _this->rng=_val?s:r;
- ec_enc_normalize(_this);
-}
-
-void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){- ec_uint32 r;
- r=_this->rng>>_ftb;
- if(_s>0){- _this->low+=_this->rng-IMUL32(r,_icdf[_s-1]);
- _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
- }
- else _this->rng-=IMUL32(r,_icdf[_s]);
- ec_enc_normalize(_this);
-}
-
-void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,unsigned _bits){- ec_window window;
- int used;
- window=_this->end_window;
- used=_this->nend_bits;
- if(used+_bits>EC_WINDOW_SIZE){- do{- _this->error|=
- ec_byte_write_at_end(_this->buf,(unsigned)window&EC_SYM_MAX);
- window>>=EC_SYM_BITS;
- used-=EC_SYM_BITS;
- }
- while(used>=EC_SYM_BITS);
- }
- window|=(ec_window)_fl<<used;
- used+=_bits;
- _this->end_window=window;
- _this->nend_bits=used;
- _this->nbits_total+=_bits;
-}
-
-ec_uint32 ec_enc_tell(ec_enc *_this,int _b){- ec_uint32 nbits;
- ec_uint32 r;
- int l;
- /*To handle the non-integral number of bits still left in the decoder state,
- we compute the worst-case number of bits of low that must be encoded to
- ensure that the value is inside the range for any possible subsequent
- bits.
- The computation here is independent of low itself (the decoder does not
- even track that value), even though the real number of bits used after
- ec_enc_done() may be 1 smaller if rng is a power of two and the
- corresponding trailing bits of low are all zeros.
- If we did try to track that special case, then coding a value with a
- probability of 1/(1<<n) might sometimes appear to use more than n bits.
- This may help explain the surprising result that a newly initialized
- encoder claims to have used 1 bit.*/
- nbits=_this->nbits_total<<_b;
- l=EC_ILOG(_this->rng);
- r=_this->rng>>l-16;
- while(_b-->0){- int b;
- r=r*r>>15;
- b=(int)(r>>16);
- l=l<<1|b;
- r>>=b;
- }
- return nbits-l;
-}
-
-void ec_enc_done(ec_enc *_this){- ec_window window;
- int used;
- ec_uint32 msk;
- ec_uint32 end;
- int l;
- /*We output the minimum number of bits that ensures that the symbols encoded
- thus far will be decoded correctly regardless of the bits that follow.*/
- l=EC_CODE_BITS-EC_ILOG(_this->rng);
- msk=EC_CODE_TOP-1>>l;
- end=_this->low+msk&~msk;
- if((end|msk)>=_this->low+_this->rng){- l++;
- msk>>=1;
- end=_this->low+msk&~msk;
- }
- while(l>0){- ec_enc_carry_out(_this,(int)(end>>EC_CODE_SHIFT));
- end=end<<EC_SYM_BITS&EC_CODE_TOP-1;
- l-=EC_SYM_BITS;
- }
- /*If we have a buffered byte flush it into the output buffer.*/
- if(_this->rem>=0||_this->ext>0)ec_enc_carry_out(_this,0);
- /*If we have buffered extra bits, flush them as well.*/
- window=_this->end_window;
- used=_this->nend_bits;
- while(used>=EC_SYM_BITS){- _this->error|=
- ec_byte_write_at_end(_this->buf,(unsigned)window&EC_SYM_MAX);
- window>>=EC_SYM_BITS;
- used-=EC_SYM_BITS;
- }
- /*Clear any excess space and add any remaining extra bits to the last byte.*/
- if(!_this->error)_this->error=ec_byte_write_done(_this->buf,-l,window,used);
-}
--- a/libcelt/rate.c
+++ b/libcelt/rate.c
@@ -254,7 +254,7 @@
static inline int interp_bits2pulses(const CELTMode *m, int start, int end, int skip_start,
const int *bits1, const int *bits2, const int *thresh, const int *cap, int total, celt_int32 *_balance,
int skip_rsv, int *intensity, int intensity_rsv, int *dual_stereo, int dual_stereo_rsv, int *bits,
- int *ebits, int *fine_priority, int _C, int LM, void *ec, int encode, int prev)
+ int *ebits, int *fine_priority, int _C, int LM, ec_ctx *ec, int encode, int prev)
{int psum;
int lo, hi;
@@ -359,11 +359,11 @@
fluctuating in and out.*/
if (band_bits > ((j<prev?7:9)*band_width<<LM<<BITRES)>>4)
{- ec_enc_bit_logp((ec_enc *)ec, 1, 1);
+ ec_enc_bit_logp(ec, 1, 1);
break;
}
- ec_enc_bit_logp((ec_enc *)ec, 0, 1);
- } else if (ec_dec_bit_logp((ec_dec *)ec, 1)) {+ ec_enc_bit_logp(ec, 0, 1);
+ } else if (ec_dec_bit_logp(ec, 1)) {break;
}
/*We used a bit to skip this band.*/
@@ -393,10 +393,10 @@
if (encode)
{*intensity = IMIN(*intensity, codedBands);
- ec_enc_uint((ec_enc *)ec, *intensity-start, codedBands+1-start);
+ ec_enc_uint(ec, *intensity-start, codedBands+1-start);
}
else
- *intensity = start+ec_dec_uint((ec_dec *)ec, codedBands+1-start);
+ *intensity = start+ec_dec_uint(ec, codedBands+1-start);
}
else
*intensity = 0;
@@ -408,9 +408,9 @@
if (dual_stereo_rsv > 0)
{if (encode)
- ec_enc_bit_logp((ec_enc *)ec, *dual_stereo, 1);
+ ec_enc_bit_logp(ec, *dual_stereo, 1);
else
- *dual_stereo = ec_dec_bit_logp((ec_dec *)ec, 1);
+ *dual_stereo = ec_dec_bit_logp(ec, 1);
}
else
*dual_stereo = 0;
@@ -527,7 +527,7 @@
}
int compute_allocation(const CELTMode *m, int start, int end, const int *offsets, const int *cap, int alloc_trim, int *intensity, int *dual_stereo,
- int total, celt_int32 *balance, int *pulses, int *ebits, int *fine_priority, int _C, int LM, void *ec, int encode, int prev)
+ int total, celt_int32 *balance, int *pulses, int *ebits, int *fine_priority, int _C, int LM, ec_ctx *ec, int encode, int prev)
{int lo, hi, len, j;
const int C = CHANNELS(_C);
--- a/libcelt/rate.h
+++ b/libcelt/rate.h
@@ -40,7 +40,6 @@
#define MAX_FINE_BITS 8
-#define BITRES 3
#define FINE_OFFSET 21
#define QTHETA_OFFSET 4
#define QTHETA_OFFSET_TWOPHASE 16
@@ -106,7 +105,7 @@
@return Total number of bits allocated
*/
int compute_allocation(const CELTMode *m, int start, int end, const int *offsets, const int *cap, int alloc_trim, int *intensity, int *dual_stero,
- int total, celt_int32 *balance, int *pulses, int *ebits, int *fine_priority, int _C, int LM, void *ec, int encode, int prev);
+ int total, celt_int32 *balance, int *pulses, int *ebits, int *fine_priority, int _C, int LM, ec_ctx *ec, int encode, int prev);
#endif
--- a/tests/cwrs32-test.c
+++ b/tests/cwrs32-test.c
@@ -7,8 +7,6 @@
#define CELT_C
#include "../libcelt/stack_alloc.h"
-#include "../libcelt/rangeenc.c"
-#include "../libcelt/rangedec.c"
#include "../libcelt/entenc.c"
#include "../libcelt/entdec.c"
#include "../libcelt/entcode.c"
--- a/tests/ectest.c
+++ b/tests/ectest.c
@@ -11,8 +11,6 @@
#include "entdec.h"
#include <string.h>
-#include "../libcelt/rangeenc.c"
-#include "../libcelt/rangedec.c"
#include "../libcelt/entenc.c"
#include "../libcelt/entdec.c"
#include "../libcelt/entcode.c"
@@ -24,7 +22,6 @@
#define DATA_SIZE2 10000
int main(int _argc,char **_argv){- ec_byte_buffer buf;
ec_enc enc;
ec_dec dec;
long nbits;
@@ -50,8 +47,7 @@
seed = time(NULL);
/*Testing encoding of raw bit values.*/
ptr = malloc(DATA_SIZE);
- ec_byte_writeinit_buffer(&buf, ptr, DATA_SIZE);
- ec_enc_init(&enc,&buf);
+ ec_enc_init(&enc,ptr, DATA_SIZE);
for(ft=2;ft<1024;ft++){ for(i=0;i<ft;i++){entropy+=log(ft)*M_LOG2E;
@@ -62,9 +58,9 @@
for(ftb=0;ftb<16;ftb++){ for(i=0;i<(1<<ftb);i++){entropy+=ftb;
- nbits=ec_enc_tell(&enc,0);
+ nbits=ec_tell(&enc);
ec_enc_bits(&enc,i,ftb);
- nbits2=ec_enc_tell(&enc,0);
+ nbits2=ec_tell(&enc);
if(nbits2-nbits!=ftb){fprintf(stderr,"Used %li bits to encode %i bits directly.\n",
nbits2-nbits,ftb);
@@ -72,14 +68,13 @@
}
}
}
- nbits=ec_enc_tell(&enc,4);
+ nbits=ec_tell_frac(&enc);
ec_enc_done(&enc);
fprintf(stderr,
"Encoded %0.2lf bits of entropy to %0.2lf bits (%0.3lf%% wasted).\n",
- entropy,ldexp(nbits,-4),100*(nbits-ldexp(entropy,4))/nbits);
- fprintf(stderr,"Packed to %li bytes.\n",(long)ec_byte_bytes(&buf));
- ec_byte_readinit(&buf,ptr,DATA_SIZE);
- ec_dec_init(&dec,&buf);
+ entropy,ldexp(nbits,-3),100*(nbits-ldexp(entropy,3))/nbits);
+ fprintf(stderr,"Packed to %li bytes.\n",(long)ec_range_bytes(&enc));
+ ec_dec_init(&dec,ptr,DATA_SIZE);
for(ft=2;ft<1024;ft++){ for(i=0;i<ft;i++){sym=ec_dec_uint(&dec,ft);
@@ -98,11 +93,11 @@
}
}
}
- nbits2=ec_dec_tell(&dec,4);
+ nbits2=ec_tell_frac(&dec);
if(nbits!=nbits2){fprintf(stderr,
"Reported number of bits used was %0.2lf, should be %0.2lf.\n",
- ldexp(nbits2,-4),ldexp(nbits,-4));
+ ldexp(nbits2,-3),ldexp(nbits,-3));
ret=-1;
}
srand(seed);
@@ -117,10 +112,9 @@
sz=rand()/((RAND_MAX>>(rand()%9))+1);
data=(unsigned *)malloc(sz*sizeof(*data));
tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
- ec_byte_writeinit_buffer(&buf, ptr, DATA_SIZE2);
- ec_enc_init(&enc,&buf);
+ ec_enc_init(&enc,ptr,DATA_SIZE2);
zeros = rand()%13==0;
- tell[0]=ec_enc_tell(&enc, 3);
+ tell[0]=ec_tell_frac(&enc);
for(j=0;j<sz;j++){if (zeros)
data[j]=0;
@@ -127,31 +121,30 @@
else
data[j]=rand()%ft;
ec_enc_uint(&enc,data[j],ft);
- tell[j+1]=ec_enc_tell(&enc, 3);
+ tell[j+1]=ec_tell_frac(&enc);
}
if (rand()%2==0)
- while(ec_enc_tell(&enc, 0)%8 != 0)
+ while(ec_tell(&enc)%8 != 0)
ec_enc_uint(&enc, rand()%2, 2);
- tell_bits = ec_enc_tell(&enc, 0);
+ tell_bits = ec_tell(&enc);
ec_enc_done(&enc);
- if(tell_bits!=ec_enc_tell(&enc,0)){- fprintf(stderr,"tell() changed after ec_enc_done(): %i instead of %i (Random seed: %u)\n",
- ec_enc_tell(&enc,0),tell_bits,seed);
+ if(tell_bits!=ec_tell(&enc)){+ fprintf(stderr,"ec_tell() changed after ec_enc_done(): %i instead of %i (Random seed: %u)\n",
+ ec_tell(&enc),tell_bits,seed);
ret=-1;
}
- if ((tell_bits+7)/8 < ec_byte_bytes(&buf))
+ if ((tell_bits+7)/8 < ec_range_bytes(&enc))
{- fprintf (stderr, "tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
- ec_byte_bytes(&buf), (tell_bits+7)/8,seed);
+ fprintf (stderr, "ec_tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
+ ec_range_bytes(&enc), (tell_bits+7)/8,seed);
ret=-1;
}
- tell_bits -= 8*ec_byte_bytes(&buf);
- ec_byte_readinit(&buf,ptr,DATA_SIZE2);
- ec_dec_init(&dec,&buf);
- if(ec_dec_tell(&dec,3)!=tell[0]){+ tell_bits -= 8*ec_range_bytes(&enc);
+ ec_dec_init(&dec,ptr,DATA_SIZE2);
+ if(ec_tell_frac(&dec)!=tell[0]){fprintf(stderr,
"Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
- 0,ec_dec_tell(&dec,3),tell[0],seed);
+ 0,ec_tell_frac(&dec),tell[0],seed);
}
for(j=0;j<sz;j++){sym=ec_dec_uint(&dec,ft);
@@ -161,10 +154,10 @@
sym,data[j],ft,j,sz,seed);
ret=-1;
}
- if(ec_dec_tell(&dec,3)!=tell[j+1]){+ if(ec_tell_frac(&dec)!=tell[j+1]){fprintf(stderr,
"Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
- j+1,ec_dec_tell(&dec,3),tell[j+1],seed);
+ j+1,ec_tell_frac(&dec),tell[j+1],seed);
}
}
free(tell);
@@ -182,9 +175,8 @@
data=(unsigned *)malloc(sz*sizeof(*data));
tell=(unsigned *)malloc((sz+1)*sizeof(*tell));
enc_method=(unsigned *)malloc(sz*sizeof(*enc_method));
- ec_byte_writeinit_buffer(&buf, ptr, DATA_SIZE2);
- ec_enc_init(&enc,&buf);
- tell[0]=ec_enc_tell(&enc,3);
+ ec_enc_init(&enc,ptr,DATA_SIZE2);
+ tell[0]=ec_tell_frac(&enc);
for(j=0;j<sz;j++){data[j]=rand()/((RAND_MAX>>1)+1);
logp1[j]=(rand()%15)+1;
@@ -208,20 +200,19 @@
ec_enc_icdf(&enc,data[j],icdf,logp1[j]);
}break;
}
- tell[j+1]=ec_enc_tell(&enc,3);
+ tell[j+1]=ec_tell_frac(&enc);
}
ec_enc_done(&enc);
- if((ec_enc_tell(&enc,0)+7)/8<ec_byte_bytes(&buf)){+ if((ec_tell(&enc)+7)/8<ec_range_bytes(&enc)){fprintf(stderr,"tell() lied, there's %i bytes instead of %d (Random seed: %u)\n",
- ec_byte_bytes(&buf),(ec_enc_tell(&enc,0)+7)/8,seed);
+ ec_range_bytes(&enc),(ec_tell(&enc)+7)/8,seed);
ret=-1;
}
- ec_byte_readinit(&buf,ptr,DATA_SIZE2);
- ec_dec_init(&dec,&buf);
- if(ec_dec_tell(&dec,3)!=tell[0]){+ ec_dec_init(&dec,ptr,DATA_SIZE2);
+ if(ec_tell_frac(&dec)!=tell[0]){fprintf(stderr,
"Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
- 0,ec_dec_tell(&dec,3),tell[0],seed);
+ 0,ec_tell_frac(&dec),tell[0],seed);
}
for(j=0;j<sz;j++){int fs;
@@ -258,10 +249,10 @@
enc_method[j],dec_method);
ret=-1;
}
- if(ec_dec_tell(&dec,3)!=tell[j+1]){+ if(ec_tell_frac(&dec)!=tell[j+1]){fprintf(stderr,
"Tell mismatch between encoder and decoder at symbol %i: %i instead of %i (Random seed: %u).\n",
- j+1,ec_dec_tell(&dec,3),tell[j+1],seed);
+ j+1,ec_tell_frac(&dec),tell[j+1],seed);
}
}
free(enc_method);
--- a/tests/laplace-test.c
+++ b/tests/laplace-test.c
@@ -8,8 +8,6 @@
#define CELT_C
#include "../libcelt/stack_alloc.h"
-#include "../libcelt/rangeenc.c"
-#include "../libcelt/rangedec.c"
#include "../libcelt/entenc.c"
#include "../libcelt/entdec.c"
#include "../libcelt/entcode.c"
@@ -30,14 +28,11 @@
int ret = 0;
ec_enc enc;
ec_dec dec;
- ec_byte_buffer buf;
unsigned char *ptr;
int val[10000], decay[10000];
ALLOC_STACK;
ptr = malloc(DATA_SIZE);
- ec_byte_writeinit_buffer(&buf, ptr, DATA_SIZE);
- //ec_byte_writeinit(&buf);
- ec_enc_init(&enc,&buf);
+ ec_enc_init(&enc,ptr,DATA_SIZE);
val[0] = 3; decay[0] = 6000;
val[1] = 0; decay[1] = 5800;
@@ -53,8 +48,7 @@
ec_enc_done(&enc);
- ec_byte_readinit(&buf,ec_byte_get_buffer(&buf),ec_byte_bytes(&buf));
- ec_dec_init(&dec,&buf);
+ ec_dec_init(&dec,ec_get_buffer(&enc),ec_range_bytes(&enc));
for (i=0;i<10000;i++)
{--- a/tests/tandem-test.c
+++ b/tests/tandem-test.c
@@ -168,7 +168,7 @@
int main(int argc, char *argv[])
{#ifdef CUSTOM_MODES
- int sizes[8]={960,480,240,120,512,256,128,64};+ int sizes[8]={960,512,480,256,240,128,120,64};#else
int sizes[4]={960,480,240,120};#endif
@@ -193,8 +193,8 @@
for (ch = 1; ch <= 2; ch++) {async_tandem(48000, sizes[n], ch, 12000 * ch, 128000 * ch);
async_tandem(44100, sizes[n], ch, 12000 * ch, 128000 * ch);
- async_tandem(32000, sizes[n], ch, 12000 * ch, 128000 * ch);
- async_tandem(16000, sizes[n], ch, 12000 * ch, 64000 * ch);
+ if(n>0)async_tandem(32000, sizes[n], ch, 12000 * ch, 128000 * ch);
+ if(n>2)async_tandem(16000, sizes[n], ch, 12000 * ch, 64000 * ch);
}
}
#else