1885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Copyright (c) 2001-2011 Timothy B. Terriberry 2885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org*/ 3885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* 4885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org Redistribution and use in source and binary forms, with or without 5885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org modification, are permitted provided that the following conditions 6885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org are met: 7885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 8885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org - Redistributions of source code must retain the above copyright 9885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org notice, this list of conditions and the following disclaimer. 10885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 11885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org - Redistributions in binary form must reproduce the above copyright 12885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org notice, this list of conditions and the following disclaimer in the 13885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org documentation and/or other materials provided with the distribution. 14885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 15885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 18885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 19885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 20885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 21885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 22885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 23885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 24885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 25885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org*/ 27885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 28885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef HAVE_CONFIG_H 29885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "config.h" 30885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 31885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 32885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "entcode.h" 33885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "arch.h" 34885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 35885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#if !defined(EC_CLZ) 366b6bee25314cfac02cc555cddedb9680c63a26d6sergeyu@chromium.org/*This is a fallback for systems where we don't know how to access 376b6bee25314cfac02cc555cddedb9680c63a26d6sergeyu@chromium.org a BSR or CLZ instruction (see ecintrin.h). 386b6bee25314cfac02cc555cddedb9680c63a26d6sergeyu@chromium.org If you are optimizing Opus on a new platform and it has a native CLZ or 396b6bee25314cfac02cc555cddedb9680c63a26d6sergeyu@chromium.org BZR (e.g. cell, MIPS, x86, etc) then making it available to Opus will be 406b6bee25314cfac02cc555cddedb9680c63a26d6sergeyu@chromium.org an easy performance win.*/ 41885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgint ec_ilog(opus_uint32 _v){ 42885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*On a Pentium M, this branchless version tested as the fastest on 43885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 1,000,000,000 random 32-bit integers, edging out a similar version with 44885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org branches, and a 256-entry LUT version.*/ 45885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int ret; 46885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int m; 47885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ret=!!_v; 48885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org m=!!(_v&0xFFFF0000)<<4; 49885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _v>>=m; 50885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ret|=m; 51885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org m=!!(_v&0xFF00)<<3; 52885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _v>>=m; 53885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ret|=m; 54885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org m=!!(_v&0xF0)<<2; 55885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _v>>=m; 56885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ret|=m; 57885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org m=!!(_v&0xC)<<1; 58885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org _v>>=m; 59885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ret|=m; 60885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ret+=!!(_v&0x2); 61885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org return ret; 62885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 63885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif 64885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org 65885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgopus_uint32 ec_tell_frac(ec_ctx *_this){ 66885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 nbits; 67885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org opus_uint32 r; 68885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int l; 69885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int i; 70885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org /*To handle the non-integral number of bits still left in the encoder/decoder 71885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org state, we compute the worst-case number of bits of val that must be 72885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org encoded to ensure that the value is inside the range for any possible 73885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org subsequent bits. 74885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org The computation here is independent of val itself (the decoder does not 75885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org even track that value), even though the real number of bits used after 76885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org ec_enc_done() may be 1 smaller if rng is a power of two and the 77885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org corresponding trailing bits of val are all zeros. 78885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org If we did try to track that special case, then coding a value with a 79885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org probability of 1/(1<<n) might sometimes appear to use more than n bits. 80885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org This may help explain the surprising result that a newly initialized 81885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org encoder or decoder claims to have used 1 bit.*/ 82885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org nbits=_this->nbits_total<<BITRES; 83885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org l=EC_ILOG(_this->rng); 84885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r=_this->rng>>(l-16); 85885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org for(i=BITRES;i-->0;){ 86885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org int b; 87885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r=r*r>>15; 88885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org b=(int)(r>>16); 89885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org l=l<<1|b; 90885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org r>>=b; 91885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org } 92885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org return nbits-l; 93885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org} 94