michael@0: /* Copyright (c) 2001-2011 Timothy B. Terriberry
michael@0: */
michael@0: /*
michael@0:    Redistribution and use in source and binary forms, with or without
michael@0:    modification, are permitted provided that the following conditions
michael@0:    are met:
michael@0: 
michael@0:    - Redistributions of source code must retain the above copyright
michael@0:    notice, this list of conditions and the following disclaimer.
michael@0: 
michael@0:    - Redistributions in binary form must reproduce the above copyright
michael@0:    notice, this list of conditions and the following disclaimer in the
michael@0:    documentation and/or other materials provided with the distribution.
michael@0: 
michael@0:    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
michael@0:    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
michael@0:    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
michael@0:    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
michael@0:    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
michael@0:    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
michael@0:    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
michael@0:    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
michael@0:    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
michael@0:    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
michael@0:    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0: */
michael@0: 
michael@0: #ifdef HAVE_CONFIG_H
michael@0: #include "config.h"
michael@0: #endif
michael@0: 
michael@0: #include "entcode.h"
michael@0: #include "arch.h"
michael@0: 
michael@0: #if !defined(EC_CLZ)
michael@0: /*This is a fallback for systems where we don't know how to access
michael@0:    a BSR or CLZ instruction (see ecintrin.h).
michael@0:   If you are optimizing Opus on a new platform and it has a native CLZ or
michael@0:    BZR (e.g. cell, MIPS, x86, etc) then making it available to Opus will be
michael@0:    an easy performance win.*/
michael@0: int ec_ilog(opus_uint32 _v){
michael@0:   /*On a Pentium M, this branchless version tested as the fastest on
michael@0:      1,000,000,000 random 32-bit integers, edging out a similar version with
michael@0:      branches, and a 256-entry LUT version.*/
michael@0:   int ret;
michael@0:   int m;
michael@0:   ret=!!_v;
michael@0:   m=!!(_v&0xFFFF0000)<<4;
michael@0:   _v>>=m;
michael@0:   ret|=m;
michael@0:   m=!!(_v&0xFF00)<<3;
michael@0:   _v>>=m;
michael@0:   ret|=m;
michael@0:   m=!!(_v&0xF0)<<2;
michael@0:   _v>>=m;
michael@0:   ret|=m;
michael@0:   m=!!(_v&0xC)<<1;
michael@0:   _v>>=m;
michael@0:   ret|=m;
michael@0:   ret+=!!(_v&0x2);
michael@0:   return ret;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: opus_uint32 ec_tell_frac(ec_ctx *_this){
michael@0:   opus_uint32 nbits;
michael@0:   opus_uint32 r;
michael@0:   int         l;
michael@0:   int         i;
michael@0:   /*To handle the non-integral number of bits still left in the encoder/decoder
michael@0:      state, we compute the worst-case number of bits of val that must be
michael@0:      encoded to ensure that the value is inside the range for any possible
michael@0:      subsequent bits.
michael@0:     The computation here is independent of val itself (the decoder does not
michael@0:      even track that value), even though the real number of bits used after
michael@0:      ec_enc_done() may be 1 smaller if rng is a power of two and the
michael@0:      corresponding trailing bits of val are all zeros.
michael@0:     If we did try to track that special case, then coding a value with a
michael@0:      probability of 1/(1<<n) might sometimes appear to use more than n bits.
michael@0:     This may help explain the surprising result that a newly initialized
michael@0:      encoder or decoder claims to have used 1 bit.*/
michael@0:   nbits=_this->nbits_total<<BITRES;
michael@0:   l=EC_ILOG(_this->rng);
michael@0:   r=_this->rng>>(l-16);
michael@0:   for(i=BITRES;i-->0;){
michael@0:     int b;
michael@0:     r=r*r>>15;
michael@0:     b=(int)(r>>16);
michael@0:     l=l<<1|b;
michael@0:     r>>=b;
michael@0:   }
michael@0:   return nbits-l;
michael@0: }