ghost/libentcode/rangedec.c

   1 #include <stddef.h>
   2 #include "entdec.h"
   3 #include "mfrngcod.h"
   4
   5
   6
   7 /*A range decoder.
   8   This is an entropy decoder based upon \cite{Mar79}, which is itself a
   9    rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}.
  10   It is very similar to arithmetic encoding, except that encoding is done with
  11    digits in any base, instead of with bits, and so it is faster when using
  12    larger bases (i.e.: a byte).
  13   The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$
  14    is the base, longer than the theoretical optimum, but to my knowledge there
  15    is no published justification for this claim.
  16   This only seems true when using near-infinite precision arithmetic so that
  17    the process is carried out with no rounding errors.
  18
  19   IBM (the author's employer) never sought to patent the idea, and to my
  20    knowledge the algorithm is unencumbered by any patents, though its
  21    performance is very competitive with proprietary arithmetic coding.
  22   The two are based on very similar ideas, however.
  23   An excellent description of implementation details is available at
  24    http://www.arturocampos.com/ac_range.html
  25   A recent work \cite{MNW98} which proposes several changes to arithmetic
  26    encoding for efficiency actually re-discovers many of the principles
  27    behind range encoding, and presents a good theoretical analysis of them.
  28
  29   This coder handles the end of the stream in a slightly more graceful fashion
  30    than most arithmetic or range coders.
  31   Once the final symbol has been encoded, the coder selects the code word with
  32    the shortest number of bits that still falls within the final interval.
  33   This method is not novel.
  34   Here, by the length of the code word, we refer to the number of bits until
  35    its final 1.
  36   Any trailing zeros may be discarded, since the encoder, once it runs out of
  37    input, will pad its buffer with zeros.
  38
  39   But this means that no encoded stream would ever have any zero bytes at the
  40    end.
  41   Since there are some coded representations we cannot produce, it implies that
  42    there is still some redundancy in the stream.
  43   In this case, we can pick a special byte value, RSV1, and should the stream
  44    end in a sequence of zeros, followed by the RSV1 byte, we can code the
  45    zeros, and discard the RSV1 byte.
  46   The decoder, knowing that the encoder would never produce a sequence of zeros
  47    at the end, would then know to add in the RSV1 byte if it observed it.
  48
  49   Now, the encoder would never produce a stream that ended in a sequence of
  50    zeros followed by a RSV1 byte.
  51   So, if the stream ends in a non-empty sequence of zeros, followed by any
  52    positive number of RSV1 bytes, the last RSV1 byte is discarded.
  53   The decoder, if it encounters a stream that ends in non-empty sequence of
  54    zeros followed by any non-negative number of RSV1 bytes, adds an additional
  55    RSV1 byte to the stream.
  56   With this strategy, every possible sequence of input bytes is transformed to
  57    one that could actually be produced by the encoder.
  58
  59   The only question is what non-zero value to use for RSV1.
  60   We select 0x80, since it has the nice property of producing the shortest
  61    possible byte streams when using our strategy for selecting a number within
  62    the final interval to encode.
  63   Clearly if the shortest possible code word that falls within the interval has
  64    its last one bit as the most significant bit of the final byte, and the
  65    previous bytes were a non-empty sequence of zeros followed by a non-negative
  66    number of 0x80 bytes, then the last byte would be discarded.
  67   If the shortest code word is not so formed, then no other code word in the
  68    interval would result in any more bytes being discarded.
  69   Any longer code word would have an additional one bit somewhere, and so would
  70    require at a minimum that that byte would be coded.
  71   If the shortest code word has a 1 before the final one that is preventing the
  72    stream from ending in a non-empty sequence of zeros followed by a
  73    non-negative number of 0x80's, then there is no code word of the same length
  74    which contains that bit as a zero.
  75   If there were, then we could simply leave that bit a 1, and drop all the bits
  76    after it without leaving the interval, thus producing a shorter code word.
  77
  78   In this case, RSV1 can only drop 1 bit off the final stream.
  79   Other choices could lead to savings of up to 8 bits for particular streams,
  80    but this would produce the odd situation that a stream with more non-zero
  81    bits is actually encoded in fewer bytes.
  82
  83   @PHDTHESIS{Pas76,
  84     author="Richard Clark Pasco",
  85     title="Source coding algorithms for fast data compression",
  86     school="Dept. of Electrical Engineering, Stanford University",
  87     address="Stanford, CA",
  88     month=May,
  89     year=1976
  90   }
  91   @INPROCEEDINGS{Mar79,
  92    author="Martin, G.N.N.",
  93    title="Range encoding: an algorithm for removing redundancy from a digitised
  94     message",
  95    booktitle="Video & Data Recording Conference",
  96    year=1979,
  97    address="Southampton",
  98    month=Jul
  99   }
 100   @ARTICLE{MNW98,
 101    author="Alistair Moffat and Radford Neal and Ian H. Witten",
 102    title="Arithmetic Coding Revisited",
 103    journal="{ACM} Transactions on Information Systems",
 104    year=1998,
 105    volume=16,
 106    number=3,
 107    pages="256--294",
 108    month=Jul,
 109    URL="http://www.stanford.edu/class/ee398/handouts/papers/Moffat98ArithmCoding.pdf"
 110   }*/
 111
 112
 113 #include <stdio.h>
 114
 115 /*Gets the next byte of input.
 116   After all the bytes in the current packet have been consumed, and the extra
 117    end code returned if needed, this function will continue to return zero each
 118    time it is called.
 119   Return: The next byte of input.*/
 120 static int ec_dec_in(ec_dec *_this){
 121   int ret;
 122   ret=ec_byte_read1(_this->buf);
 123   if(ret<0){
 124     unsigned char *buf;
 125     long           i;
 126     i=ec_byte_bytes(_this->buf);
 127     buf=ec_byte_get_buffer(_this->buf);
 128     /*Breaking abstraction: don't do this at home, kids.*/
 129     if(_this->buf->storage==i&&i>0){
 130       unsigned char *buf;
 131       buf=ec_byte_get_buffer(_this->buf);
 132       /*If we end in a string of 0 or more EC_FOF_RSV1 bytes preceded by a
 133          zero, return an extra EC_FOF_RSV1 byte.*/
 134       do i--;
 135       while(i>0&&buf[i]==EC_FOF_RSV1);
 136       if(!buf[i])ret=EC_FOF_RSV1;
 137       else ret=0;
 138     }
 139     else ret=0;
 140     /*Needed to make sure the above conditional only triggers once, and to keep
 141        oc_dec_tell() operating correctly.*/
 142     ec_byte_adv1(_this->buf);
 143   }
 144   return ret;
 145 }
 146
 147 /*Normalizes the contents of dif and rng so that rng lies entirely in the
 148    high-order symbol.*/
 149 static void ec_dec_normalize(ec_dec *_this){
 150   /*If the range is too small, rescale it and input some bits.*/
 151   while(_this->rng<=EC_CODE_BOT){
 152     int sym;
 153     _this->rng<<=EC_SYM_BITS;
 154     /*Use up the remaining bits from our last symbol.*/
 155     sym=_this->rem<<EC_CODE_EXTRA&EC_SYM_MAX;
 156     /*Read the next value from the input.*/
 157     _this->rem=ec_dec_in(_this);
 158     /*Take the rest of the bits we need from this new symbol.*/
 159     sym|=_this->rem>>EC_SYM_BITS-EC_CODE_EXTRA;
 160     _this->dif=(_this->dif<<EC_SYM_BITS)-sym&EC_CODE_MASK;
 161     /*dif can never be larger than EC_CODE_TOP.
 162       This is equivalent to the slightly more readable:
 163       if(_this->dif>EC_CODE_TOP)_this->dif-=EC_CODE_TOP;*/
 164     _this->dif^=_this->dif&_this->dif-1&EC_CODE_TOP;
 165   }
 166 }
 167
 168 void ec_dec_init(ec_dec *_this,ec_byte_buffer *_buf){
 169   _this->buf=_buf;
 170   _this->rem=ec_dec_in(_this);
 171   _this->rng=1U<<EC_CODE_EXTRA;
 172   _this->dif=_this->rng-(_this->rem>>EC_SYM_BITS-EC_CODE_EXTRA);
 173   /*Normalize the interval.*/
 174   ec_dec_normalize(_this);
 175 }
 176
 177
 178 unsigned ec_decode(ec_dec *_this,unsigned _ft){
 179   unsigned s;
 180   _this->nrm=_this->rng/_ft;
 181   s=(unsigned)((_this->dif-1)/_this->nrm);
 182   return _ft-EC_MINI(s+1,_ft);
 183 }
 184
 185 void ec_dec_update(ec_dec *_this,unsigned _fl,unsigned _fh,unsigned _ft){
 186   ec_uint32 s;
 187   s=_this->nrm*(_ft-_fh);
 188   _this->dif-=s;
 189   _this->rng=_fl>0?_this->nrm*(_fh-_fl):_this->rng-s;
 190   ec_dec_normalize(_this);
 191 }
 192
 193 long ec_dec_tell(ec_dec *_this,int _b){
 194   ec_uint32 r;
 195   int       l;
 196   long      nbits;
 197   nbits=ec_byte_bytes(_this->buf)-(EC_CODE_BITS+EC_SYM_BITS-1)/EC_SYM_BITS<<3;
 198   /*To handle the non-integral number of bits still left in the encoder state,
 199      we compute the number of bits of low that must be encoded to ensure that
 200      the value is inside the range for any possible subsequent bits.
 201     Note that this is subtly different than the actual value we would end the
 202      stream with, which tries to make as many of the trailing bits zeros as
 203      possible.*/
 204   nbits+=EC_CODE_BITS;
 205   nbits<<=_b;
 206   l=EC_ILOG(_this->rng);
 207   r=_this->rng>>l-16;
 208   while(_b-->0){
 209     int b;
 210     r=r*r>>15;
 211     b=(int)(r>>16);
 212     l=l<<1|b;
 213     r>>=b;
 214   }
 215   return nbits-l;
 216 }
 217
 218 #if 0
 219 int ec_dec_done(ec_dec *_this){
 220   unsigned low;
 221   int      ret;
 222   /*Check to make sure we've used all the input bytes.
 223     This ensures that no more ones would ever be inserted into the decoder.*/
 224   if(_this->buf->ptr-ec_byte_get_buffer(_this->buf)<=
 225    ec_byte_bytes(_this->buf)){
 226     return 0;
 227   }
 228   /*We compute the smallest finitely odd fraction that fits inside the current
 229      range, and write that to the stream.
 230     This is guaranteed to yield the smallest possible encoding.*/
 231   /*TODO: Fix this line, as it is wrong.
 232     It doesn't seem worth being able to make this check to do an extra
 233      subtraction for every symbol decoded.*/
 234   low=/*What we want: _this->top-_this->rng; What we have:*/_this->dif
 235   if(low){
 236     unsigned end;
 237     end=EC_CODE_TOP;
 238     /*Ensure that the next free end is in the range.*/
 239     if(end-low>=_this->rng){
 240       unsigned msk;
 241       msk=EC_CODE_TOP-1;
 242       do{
 243         msk>>=1;
 244         end=(low+msk)&~msk|msk+1;
 245       }
 246       while(end-low>=_this->rng);
 247     }
 248     /*The remaining input should have been the next free end.*/
 249     return end-low!=_this->dif;
 250   }
 251   return 1;
 252 }
 253 #endif