Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

This renames ec_dec_cdf() to ec_dec_icdf(), and changes the
 functionality to use an "inverse" CDF table, where
 icdf[i]=ft-cdf[i+1].
The first entry is omitted entirely.
It also adds a corresonding ec_enc_icdf() to the encoder, which uses
 the same table.
One could use ec_encode_bin() by converting the values in the tables
 back to normal CDF values, but the icdf[] table already has them in
 the form ec_encode_bin() wants to use them, so there's no reason to
 translate them and then translate them back.

This is done primarily to allow SILK to use the range coder with
 8-bit probability tables containing cumulative frequencies that
 span the full range 0...256.
With an 8-bit table, the final 256 of a normal CDF becomes 0 in the
 "inverse" CDF.
It's the 0 at the start of a normal CDF which would become 256, but
 this is the value we omit, as it already has to be special-cased in
 the encoder, and is not used at all in the decoder.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

The band where intensity stereo begins was being coded as an
 absolute value, rather than relative to start, even though the
 range of values in the bitstream was limited as if it was being
 coded relative to start (meaning there would be desync if
 intensity was sufficiently large).

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

Previously it was coded for all bands, even when not all of them
 were being used.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

The valid bands range from [start,end) everywhere, with start<end.
Therefore end should never be 0, and should be allowed to extend
 all the way to mode->nbEBands.
This patch does _not_ enforce that start<end, and it does _not_
 handle clearing oldBandE[] when the valid range changes, which
 are separate issues.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

cf874373 raised the limit from 7 to 8 for N>1 bands in
 interp_bits2pulses(), but did not raise the corresponding limits
 for N=1 bands, or for [un]quant_energy_finalise().
This commit raises all of the limits to the same value, 8.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

This way if a band doesn't get the fine bits we want because it
 wasn't allocated enough bits to start with, then we will still
 give it priority for any spare bits after PVQ.

Compensate for the fact that the side "energy" is not preserved
when the split ends up starving one segment.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

The tf_res bits are useless without tf_select, so move it up before
 them.
This allows the tf_res bits to be interpreted directly as they're
 decoded.

ec_byte_read() ec_byte_read_from_end() had different return types.
ec_dec_bits() was storing its return value as int instead of
 ec_uint32, which will break if int is only 16 bits.

Also updates the TI dsplib macros to use the same EC_CLZ mechanism
 as everything else.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

For our current usage, this doesn't matter, but is more consistent
 with the rest of the API.
We may want to reduce this to an unsigned char[], but I'd rather
 coordinate that optimization with SILK's planned reduction to
 8-bit CDFs, as we may be able to use the same code.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

This ensures that the various alternative routines in the entropy
 encoder and decoder (e.g., ec_{enc|dec}_bit_logp()) really are
 just specialized optimizations of the same general ec_encode()
 and ec_decode() routines.
This is done by randomly picking one to encode with for each symbol,
 and randomly picking a different one to decode with.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

Introduced by 30df6cf3.
This should have only affected the output in the case where the last
 few extra bits caused us to bust, and wouldn't have prevented us
 from detecting the error.

This simplifies a good bit of the error handling, and should make it
 impossible to overrun the buffer in the encoder or decoder, while
 still allowing tell() to operate correctly after a bust.
The encoder now tries to keep the range coder data intact after a
 bust instead of corrupting it with extra bits data, though this is
 not a guarantee (too many extra bits may have already been flushed).
It also now correctly reports errors when the bust occurs merging the
 last byte of range coder and extra bits.

A number of abstraction barrier violations were cleaned up, as well.
This patch also includes a number of minor performance improvements:
 ec_{enc|dec}_bits() in particular should be much faster.

Finally, tf_select was changed to be coded with the range coder
 rather than extra bits, so that it is at the front of the packet
 (for unequal error protection robustness).

This means we're "time-ordered" in all cases except when increasing
the time resolution on frames that already use short blocks.
There's no reordering when increasing the frequency resolution
on short blocks.

Dynalloc becomes 2x more likely every time we use it, until it
reaches a probability of 1/4. Allocation increments now have
a floor of 1/8 bit/sample and a ceiling of 1 bit/sample.

Gregory Maxwell authored 14 years ago and Jean-Marc Valin committed 14 years ago

 The modeline-bisection and interpolator have used different criteria
for the minimum coding threshold since the introduction of the
"backwards done" in 405e6a99. This meant that a lower modeline could be
selected which the interpolator was never able to get under the maximum
allocation. This patch makes the modeline selection search use the same
criteria as the interpolator.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

This removes an XOR, an ADD, and an AND, and replaces them with
 an AND NOT in ec_dec_normalize().
Also, simplify the loop structure of ec_dec_cdf() and eliminate a
 CMOV.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

All of our usage of ec_{enc|dec}_bit_prob had the probability of a
 "one" being a power of two.
This adds a new ec_{enc|dec}_bit_logp() function that takes this
 explicitly into account.
It introduces less rounding error than the bit_prob version, does not
 require 17-bit integers to be emulated by ec_{encode|decode}_bin(),
 and does not require any multiplies or divisions at all.
It is exactly equivalent to
 ec_encode_bin(enc,_val?0:(1<<_logp)-1,(1<<_logp)-(_val?1:0),1<<_logp)

The old ec_{enc|dec}_bit_prob functions are left in place for now,
 because I am not sure if SILK is still using them or not when
 combined in Opus.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

It turns out to be more convenient to store dif=low+rng-code-1
 instead of dif=low+rng-code.
This gets rid of a decrement in the normal decode path, replaces a
 decrement and an "and" in the normalization loop with a single
 add, and makes it clear that the new ec_dec_cdf() will not result
 in an infinite loop.
This does not change the bitstream.

This decodes a value encoded with ec_encode_bin() without using any
 divisions.
It is only meant for small alphabets.
If a symbol can take on a large number of possible values, a binary
 search would be better.

This patch also converts spread_decision to use it, since it is
 faster and introduces less rounding error to encode a single
 decision for the entire value than to encode it a bit at a time.

This improves the allocation for 2.5 ms frames.

These were stored internally in one order and in the bitstream in a
 different order.
Both used bare constants, making it unclear what either actually
 meant.
This changes them to use the same order, gives them named constants,
 and renames all the "fold" decision stuff to "spread" instead,
 since that is what it is really controlling.

Also, now forcing MS stereo for 2.5 frames because the current
analysis isn't reliable.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

The bisection search in compute_allocation() was not using the same
 method to count psum as interp_bits2pulses, i.e., it did not
 include the 64*C<<BITRES<<LM allocation ceiling (this adds at most
 84 max operations/frame, and so should have a trivial CPU cost).
Again, I wouldn't want to try to explain why these are different in
 a spec, so let's make them the same.

In addition, the procedure used to fill in bits1 and bits2 after the
 bisection search was not the same as the one used during the
 bisection search.
I.e., the
      if (bits1[j] > 0)
               bits1[j] += trim_offset[j];
 step was not also done for bits2, so bits1[j] + bits2[j] would not
 be equal to what was computed earlier for the hi line, and would
 not be guaranteed to be larger than total.
We now compute both allocation lines in the same manner, and then
 obtain bits2 by subtracting them, instead of trying to compute the
 offset from bits1 up front.

Finally, there was nothing to stop a bitstream from boosting a band
 beyond the number of bits remaining, which means that bits1 would
 not produce an allocation less than or equal to total, which means
 that some bands would receive a negative allocation in the decoder
 when the "left over" negative bits were redistributed to other
 bands.
This patch only adds the dynalloc offset to allocation lines greater
 than 0, so that an all-zeros floor still exists; the effect is that
 a dynalloc boost gets linearly scaled between allocation lines 0 and
 1, and is constant (like it was before) after that.
We don't have to add the extra condition to the bisection search,
 because it never examines allocation line 0.
This re-writes the indexing in the search to make that explicit;
 it was tested and gives exactly the same results in exactly the
 same number of iterations as the old search.

Timothy B. Terriberry authored 14 years ago and Jean-Marc Valin committed 14 years ago

Commit 8e447678 increased the number of cases where we end skipping
 without explicit signaling.
Before, this would cause the bit we reserved for this purpose to
 either a) get grabbed by some N=1 band to code its sign bits or
 b) wind up as part of the fine energy at the end.
This patch gives it back to the band where we stopped skipping,
 which is either the first band, or a band that was boosted by
 dynalloc.
This allows the bit to be used for shape coding in that band, and
 allows the better computation of the fine offset, since the band
 knows it will get that bit in advance.

With this change, we now guarantee that the number of bits allocated
 by compute_allocation() is exactly equal to the input total, less
 the bits consumed by skip flags during allocation itself (assuming
 total was non-negative; for negative total, no bits are emitted,
 and no bits are allocated).

Gregory Maxwell authored 14 years ago and Jean-Marc Valin committed 14 years ago

Terminate the coding of skip bits at the last dynalloc boosted band. Otherwise the bitstream allows non-sensible behavior by the encoder (dynallocing bits into a band and then skipping it). This reduces skip bit overhead by about 2-3% at moderate bitrates with the current encoder.