Completely new transient analysis algorithm
[opus.git] / libcelt / rangedec.c
index 072e9c6..35bc193 100644 (file)
@@ -1,7 +1,39 @@
+/* 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"
 
    encoding for efficiency actually re-discovers many of the principles
    behind range encoding, and presents a good theoretical analysis of them.
 
-  This coder handles the end of the stream in a slightly more graceful fashion
-   than most arithmetic or range coders.
-  Once the final symbol has been encoded, the coder selects the code word with
-   the shortest number of bits that still falls within the final interval.
-  This method is not novel.
-  Here, by the length of the code word, we refer to the number of bits until
-   its final 1.
-  Any trailing zeros may be discarded, since the encoder, once it runs out of
-   input, will pad its buffer with zeros.
-
-  But this means that no encoded stream would ever have any zero bytes at the
-   end.
-  Since there are some coded representations we cannot produce, it implies that
-   there is still some redundancy in the stream.
-  In this case, we can pick a special byte value, RSV1, and should the stream
-   end in a sequence of zeros, followed by the RSV1 byte, we can code the
-   zeros, and discard the RSV1 byte.
-  The decoder, knowing that the encoder would never produce a sequence of zeros
-   at the end, would then know to add in the RSV1 byte if it observed it.
-
-  Now, the encoder would never produce a stream that ended in a sequence of
-   zeros followed by a RSV1 byte.
-  So, if the stream ends in a non-empty sequence of zeros, followed by any
-   positive number of RSV1 bytes, the last RSV1 byte is discarded.
-  The decoder, if it encounters a stream that ends in non-empty sequence of
-   zeros followed by any non-negative number of RSV1 bytes, adds an additional
-   RSV1 byte to the stream.
-  With this strategy, every possible sequence of input bytes is transformed to
-   one that could actually be produced by the encoder.
-
-  The only question is what non-zero value to use for RSV1.
-  We select 0x80, since it has the nice property of producing the shortest
-   possible byte streams when using our strategy for selecting a number within
-   the final interval to encode.
-  Clearly if the shortest possible code word that falls within the interval has
-   its last one bit as the most significant bit of the final byte, and the
-   previous bytes were a non-empty sequence of zeros followed by a non-negative
-   number of 0x80 bytes, then the last byte would be discarded.
-  If the shortest code word is not so formed, then no other code word in the
-   interval would result in any more bytes being discarded.
-  Any longer code word would have an additional one bit somewhere, and so would
-   require at a minimum that that byte would be coded.
-  If the shortest code word has a 1 before the final one that is preventing the
-   stream from ending in a non-empty sequence of zeros followed by a
-   non-negative number of 0x80's, then there is no code word of the same length
-   which contains that bit as a zero.
-  If there were, then we could simply leave that bit a 1, and drop all the bits
-   after it without leaving the interval, thus producing a shorter code word.
-
-  In this case, RSV1 can only drop 1 bit off the final stream.
-  Other choices could lead to savings of up to 8 bits for particular streams,
-   but this would produce the odd situation that a stream with more non-zero
-   bits is actually encoded in fewer bytes.
-
+  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",
@@ -123,8 +107,7 @@ static int ec_dec_in(ec_dec *_this){
   ret=ec_byte_read1(_this->buf);
   if(ret<0){
     ret=0;
-    /*Needed to make sure the above conditional only triggers once, and to keep
-       oc_dec_tell() operating correctly.*/
+    /*Needed to keep oc_dec_tell() operating correctly.*/
     ec_byte_adv1(_this->buf);
   }
   return ret;
@@ -132,7 +115,7 @@ static int ec_dec_in(ec_dec *_this){
 
 /*Normalizes the contents of dif and rng so that rng lies entirely in the
    high-order symbol.*/
-static void ec_dec_normalize(ec_dec *_this){
+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;
@@ -158,6 +141,10 @@ void ec_dec_init(ec_dec *_this,ec_byte_buffer *_buf){
   _this->dif=_this->rng-(_this->rem>>EC_SYM_BITS-EC_CODE_EXTRA);
   /*Normalize the interval.*/
   ec_dec_normalize(_this);
+  _this->end_byte=0; /* Required for platforms that have chars > 8 bits */
+  _this->end_bits_left=0;
+  _this->nb_end_bits=0;
+  _this->error=0;
 }
 
 
@@ -168,26 +155,64 @@ unsigned ec_decode(ec_dec *_this,unsigned _ft){
   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-1)/_this->nrm);
+   return (1<<_bits)-EC_MINI(s+1,1<<_bits);
+}
+
+unsigned ec_dec_bits(ec_dec *_this,unsigned bits){
+  unsigned value=0;
+  int count=0;
+  _this->nb_end_bits += bits;
+  while (bits>=_this->end_bits_left)
+  {
+    value |= _this->end_byte>>(8-_this->end_bits_left)<<count;
+    count += _this->end_bits_left;
+    bits -= _this->end_bits_left;
+    _this->end_byte=ec_byte_look_at_end(_this->buf);
+    _this->end_bits_left = 8;
+  }
+  value |= ((_this->end_byte>>(8-_this->end_bits_left))&((1<<bits)-1))<<count;
+  _this->end_bits_left -= bits;
+  return value;
+}
+
 void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){
   ec_uint32 s;
-  s=_this->nrm*(_ft-_fh);
+  s=IMUL32(_this->nrm,(_ft-_fh));
   _this->dif-=s;
-  _this->rng=_fl>0?_this->nrm*(_fh-_fl):_this->rng-s;
+  _this->rng=_fl>0?IMUL32(_this->nrm,(_fh-_fl)):_this->rng-s;
   ec_dec_normalize(_this);
 }
 
-long ec_dec_tell(ec_dec *_this,int _b){
+/*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 s;
+  ec_uint32 d;
+  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;
+}
+
+ec_uint32 ec_dec_tell(ec_dec *_this,int _b){
   ec_uint32 r;
   int       l;
-  long      nbits;
-  nbits=ec_byte_bytes(_this->buf)-(EC_CODE_BITS+EC_SYM_BITS-1)/EC_SYM_BITS<<3;
-  /*To handle the non-integral number of bits still left in the encoder state,
+  ec_uint32      nbits;
+  nbits=(ec_byte_bytes(_this->buf)-(EC_CODE_BITS+EC_SYM_BITS-1)/EC_SYM_BITS)*
+   EC_SYM_BITS;
+  /*To handle the non-integral number of bits still left in the decoder state,
      we compute the number of bits of low that must be encoded to ensure that
-     the value is inside the range for any possible subsequent bits.
-    Note that this is subtly different than the actual value we would end the
-     stream with, which tries to make as many of the trailing bits zeros as
-     possible.*/
-  nbits+=EC_CODE_BITS;
+     the value is inside the range for any possible subsequent bits.*/
+  nbits+=EC_CODE_BITS+1+_this->nb_end_bits;
   nbits<<=_b;
   l=EC_ILOG(_this->rng);
   r=_this->rng>>l-16;
@@ -200,40 +225,3 @@ long ec_dec_tell(ec_dec *_this,int _b){
   }
   return nbits-l;
 }
-
-#if 0
-int ec_dec_done(ec_dec *_this){
-  unsigned low;
-  int      ret;
-  /*Check to make sure we've used all the input bytes.
-    This ensures that no more ones would ever be inserted into the decoder.*/
-  if(_this->buf->ptr-ec_byte_get_buffer(_this->buf)<=
-   ec_byte_bytes(_this->buf)){
-    return 0;
-  }
-  /*We compute the smallest finitely odd fraction that fits inside the current
-     range, and write that to the stream.
-    This is guaranteed to yield the smallest possible encoding.*/
-  /*TODO: Fix this line, as it is wrong.
-    It doesn't seem worth being able to make this check to do an extra
-     subtraction for every symbol decoded.*/
-  low=/*What we want: _this->top-_this->rng; What we have:*/_this->dif
-  if(low){
-    unsigned end;
-    end=EC_CODE_TOP;
-    /*Ensure that the next free end is in the range.*/
-    if(end-low>=_this->rng){
-      unsigned msk;
-      msk=EC_CODE_TOP-1;
-      do{
-        msk>>=1;
-        end=(low+msk)&~msk|msk+1;
-      }
-      while(end-low>=_this->rng);
-    }
-    /*The remaining input should have been the next free end.*/
-    return end-low!=_this->dif;
-  }
-  return 1;
-}
-#endif