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

non-ascii characters from the source.

Got authorization from all copyright holders

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

This fixes a number of issues for platforms with a 16-bit int, but
 by no means all of them.
The type change for ec_window (for platforms where sizeof(size_t)==2)
 will break ABI (but not API) compatibility with libsilk and libopus,
 and reduce speed on x86-64, but allows the code to work in real-mode
 DOS without using the huge memory model, which is useful for testing
 16-bit int compliance.

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

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.

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

This stores the caps array in 32nd bits/sample instead of 1/2 bits
 scaled by LM and the channel count, which is slightly less
 less accurate for the last two bands, and much more accurate for
 all the other bands.
A constant offset is subtracted to allow it to represent values
 larger than 255 in 8 bits (the range of unoffset values is
 77...304).
In addition, this replaces the last modeline in the allocation table
 with the caps array, allowing the initial interpolation to
 allocate 8 bits/sample or more, which was otherwise impossible.

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

9b34bd83 caused serious regressions for 240-sample frame stereo,
 because the previous qb limit was _always_ hit for two-phase
 stereo.
Two-phase stereo really does operate with a different model (for
 example, the single bit allocated to the side should really
 probably be thought of as a sign bit for qtheta, but we don't
 count it as part of qtheta's allocation).
The old code was equivalent to a separate two-phase offset of 12,
 however Greg Maxwell's testing demonstrates that 16 performs
 best.

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

Previously, we would only split a band if it was allocated more than
 32 bits.
However, the N=4 codebook can only produce about 22.5 bits, and two
 N=2 bands combined can only produce 26 bits, including 8 bits for
 qtheta, so if we wait until we allocate 32, we're guaranteed to fall
 short.
Several of the larger bands come pretty far from filling 32 bits as
 well, though their split versions will.

Greg Maxwell also suggested adding an offset to the threshold to
 account for the inefficiency of using qtheta compared to another
 VQ dimension.
This patch uses 1 bit as a placeholder, as it's a clear
 improvement, but we may adjust this later after collecting data on
 more possibilities over more files.

Instead of just dumping excess bits into the first band after
 allocation, use them to initialize the rebalancing loop in
 quant_all_bands().
This allows these bits to be redistributed over several bands, like
 normal.

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

Use measured cross-entropy to estimate the real cost of coding
 qtheta given the allocated qb parameter, instead of the entropy of
 the PDF.
This is generally much lower, and reduces waste at high rates.
This patch also removes some intermediate rounding from this
 computation.

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

This extends the previous rebalancing for fine energy in N=1 bands
 to also allocate extra fine bits for bands that go over their cap.

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

The previous "dumb cap" of (64<<LM)*(C<<BITRES) was not actually
 achievable by many (most) bands, and did not take the cost of
 coding theta for splits into account, and so was too small for some
 bands.
This patch adds code to compute a fairly accurate estimate of the
 real maximum per-band rate (an estimate only because of rounding
 effects and the fact that the bit usage for theta is variable),
 which is then truncated and stored in an 8-bit table in the mode.

This gives improved quality at all rates over 160 kbps/channel,
 prevents bits from being wasted all the way up to 255 kbps/channel
 (the maximum rate allowed, and approximately the maximum number of
 bits that can usefully be used regardless of the allocation), and
 prevents dynalloc and trim from producing enormous waste
 (eliminating the need for encoder logic to prevent this).

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

This patch makes all symbols conditional on whether or not there's
 enough space left in the buffer to code them, and eliminates much
 of the redundancy in the side information.

A summary of the major changes:
* The isTransient flag is moved up to before the the coarse energy.
  If there are not enough bits to code the coarse energy, the flag
   would get forced to 0, meaning what energy values were coded
   would get interpreted incorrectly.
  This might not be the end of the world, and I'd be willing to
   move it back given a compelling argument.
* Coarse energy switches coding schemes when there are less than 15
   bits left in the packet:
  - With at least 2 bits remaining, the change in energy is forced
     to the range [-1...1] and coded with 1 bit (for 0) or 2 bits
     (for +/-1).
  - With only 1 bit remaining, the change in energy is forced to
     the range [-1...0] and coded with one bit.
  - If there is less than 1 bit remaining, the change in energy is
     forced to -1.
    This effectively low-passes bands whose energy is consistently
     starved; this might be undesirable, but letting the default be
     zero is unstable, which is worse.
* The tf_select flag gets moved back after the per-band tf_res
   flags again, and is now skipped entirely when none of the
   tf_res flags are set, and the default value is the same for
   either alternative.
* dynalloc boosting is now limited so that it stops once it's given
   a band all the remaining bits in the frame, or when it hits the
   "stupid cap" of (64<<LM)*(C<<BITRES) used during allocation.
* If dynalloc boosing has allocated all the remaining bits in the
   frame, the alloc trim parameter does not get encoded (it would
   have no effect).
* The intensity stereo offset is now limited to the range
   [start...codedBands], and thus doesn't get coded until after
   all of the skip decisions.
  Some space is reserved for it up front, and gradually given back
   as each band is skipped.
* The dual stereo flag is coded only if intensity>start, since
   otherwise it has no effect.
  It is now coded after the intensity flag.
* The space reserved for the final skip flag, the intensity stereo
   offset, and the dual stereo flag is now redistributed to all
   bands equally if it is unused.
  Before, the skip flag's bit was given to the band that stopped
   skipping without it (usually a dynalloc boosted band).

In order to enable simple interaction between VBR and these
 packet-size enforced limits, many of which are encountered before
 VBR is run, the maximum packet size VBR will allow is computed at
 the beginning of the encoding function, and the buffer reduced to
 that size immediately.
Later, when it is time to make the VBR decision, the minimum packet
 size is set high enough to ensure that no decision made thus far
 will have been affected by the packet size.
As long as this is smaller than the up-front maximum, all of the
 encoder's decisions will remain in-sync with the decoder.
If it is larger than the up-front maximum, the packet size is kept
 at that maximum, also ensuring sync.
The minimum used now is slightly larger than it used to be, because
 it also includes the bits added for dynalloc boosting.
Such boosting is shut off by the encoder at low rates, and so
 should not cause any serious issues at the rates where we would
 actually run out of room before compute_allocation().

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.

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

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.

This improves the allocation for 2.5 ms frames.

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.

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

Excess fractions of a bit can't be re-used in N=1 bands during
 quant_all_bands() because there's no shape, only a sign bit.
This meant that all the fractional bits in these bands accumulated,
 often up to 5 or 6 bits for stereo, until the first band with N>1,
 where they were dumped all at once.
This patch moves the rebalancing for N=1 bands to
 interp_bits2pulses() instead, where excess bits still have a
 chance to be moved into fine energy.