|
Chris@69
|
1 /* Copyright (c) 2001-2011 Timothy B. Terriberry
|
|
Chris@69
|
2 */
|
|
Chris@69
|
3 /*
|
|
Chris@69
|
4 Redistribution and use in source and binary forms, with or without
|
|
Chris@69
|
5 modification, are permitted provided that the following conditions
|
|
Chris@69
|
6 are met:
|
|
Chris@69
|
7
|
|
Chris@69
|
8 - Redistributions of source code must retain the above copyright
|
|
Chris@69
|
9 notice, this list of conditions and the following disclaimer.
|
|
Chris@69
|
10
|
|
Chris@69
|
11 - Redistributions in binary form must reproduce the above copyright
|
|
Chris@69
|
12 notice, this list of conditions and the following disclaimer in the
|
|
Chris@69
|
13 documentation and/or other materials provided with the distribution.
|
|
Chris@69
|
14
|
|
Chris@69
|
15 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
|
Chris@69
|
16 ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
|
Chris@69
|
17 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
|
|
Chris@69
|
18 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
|
|
Chris@69
|
19 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
Chris@69
|
20 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
Chris@69
|
21 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
Chris@69
|
22 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
|
|
Chris@69
|
23 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
|
Chris@69
|
24 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
|
Chris@69
|
25 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
Chris@69
|
26 */
|
|
Chris@69
|
27
|
|
Chris@69
|
28 #ifdef HAVE_CONFIG_H
|
|
Chris@69
|
29 #include "config.h"
|
|
Chris@69
|
30 #endif
|
|
Chris@69
|
31
|
|
Chris@69
|
32 #include "entcode.h"
|
|
Chris@69
|
33 #include "arch.h"
|
|
Chris@69
|
34
|
|
Chris@69
|
35 #if !defined(EC_CLZ)
|
|
Chris@69
|
36 /*This is a fallback for systems where we don't know how to access
|
|
Chris@69
|
37 a BSR or CLZ instruction (see ecintrin.h).
|
|
Chris@69
|
38 If you are optimizing Opus on a new platform and it has a native CLZ or
|
|
Chris@69
|
39 BZR (e.g. cell, MIPS, x86, etc) then making it available to Opus will be
|
|
Chris@69
|
40 an easy performance win.*/
|
|
Chris@69
|
41 int ec_ilog(opus_uint32 _v){
|
|
Chris@69
|
42 /*On a Pentium M, this branchless version tested as the fastest on
|
|
Chris@69
|
43 1,000,000,000 random 32-bit integers, edging out a similar version with
|
|
Chris@69
|
44 branches, and a 256-entry LUT version.*/
|
|
Chris@69
|
45 int ret;
|
|
Chris@69
|
46 int m;
|
|
Chris@69
|
47 ret=!!_v;
|
|
Chris@69
|
48 m=!!(_v&0xFFFF0000)<<4;
|
|
Chris@69
|
49 _v>>=m;
|
|
Chris@69
|
50 ret|=m;
|
|
Chris@69
|
51 m=!!(_v&0xFF00)<<3;
|
|
Chris@69
|
52 _v>>=m;
|
|
Chris@69
|
53 ret|=m;
|
|
Chris@69
|
54 m=!!(_v&0xF0)<<2;
|
|
Chris@69
|
55 _v>>=m;
|
|
Chris@69
|
56 ret|=m;
|
|
Chris@69
|
57 m=!!(_v&0xC)<<1;
|
|
Chris@69
|
58 _v>>=m;
|
|
Chris@69
|
59 ret|=m;
|
|
Chris@69
|
60 ret+=!!(_v&0x2);
|
|
Chris@69
|
61 return ret;
|
|
Chris@69
|
62 }
|
|
Chris@69
|
63 #endif
|
|
Chris@69
|
64
|
|
Chris@69
|
65 #if 1
|
|
Chris@69
|
66 /* This is a faster version of ec_tell_frac() that takes advantage
|
|
Chris@69
|
67 of the low (1/8 bit) resolution to use just a linear function
|
|
Chris@69
|
68 followed by a lookup to determine the exact transition thresholds. */
|
|
Chris@69
|
69 opus_uint32 ec_tell_frac(ec_ctx *_this){
|
|
Chris@69
|
70 static const unsigned correction[8] =
|
|
Chris@69
|
71 {35733, 38967, 42495, 46340,
|
|
Chris@69
|
72 50535, 55109, 60097, 65535};
|
|
Chris@69
|
73 opus_uint32 nbits;
|
|
Chris@69
|
74 opus_uint32 r;
|
|
Chris@69
|
75 int l;
|
|
Chris@69
|
76 unsigned b;
|
|
Chris@69
|
77 nbits=_this->nbits_total<<BITRES;
|
|
Chris@69
|
78 l=EC_ILOG(_this->rng);
|
|
Chris@69
|
79 r=_this->rng>>(l-16);
|
|
Chris@69
|
80 b = (r>>12)-8;
|
|
Chris@69
|
81 b += r>correction[b];
|
|
Chris@69
|
82 l = (l<<3)+b;
|
|
Chris@69
|
83 return nbits-l;
|
|
Chris@69
|
84 }
|
|
Chris@69
|
85 #else
|
|
Chris@69
|
86 opus_uint32 ec_tell_frac(ec_ctx *_this){
|
|
Chris@69
|
87 opus_uint32 nbits;
|
|
Chris@69
|
88 opus_uint32 r;
|
|
Chris@69
|
89 int l;
|
|
Chris@69
|
90 int i;
|
|
Chris@69
|
91 /*To handle the non-integral number of bits still left in the encoder/decoder
|
|
Chris@69
|
92 state, we compute the worst-case number of bits of val that must be
|
|
Chris@69
|
93 encoded to ensure that the value is inside the range for any possible
|
|
Chris@69
|
94 subsequent bits.
|
|
Chris@69
|
95 The computation here is independent of val itself (the decoder does not
|
|
Chris@69
|
96 even track that value), even though the real number of bits used after
|
|
Chris@69
|
97 ec_enc_done() may be 1 smaller if rng is a power of two and the
|
|
Chris@69
|
98 corresponding trailing bits of val are all zeros.
|
|
Chris@69
|
99 If we did try to track that special case, then coding a value with a
|
|
Chris@69
|
100 probability of 1/(1<<n) might sometimes appear to use more than n bits.
|
|
Chris@69
|
101 This may help explain the surprising result that a newly initialized
|
|
Chris@69
|
102 encoder or decoder claims to have used 1 bit.*/
|
|
Chris@69
|
103 nbits=_this->nbits_total<<BITRES;
|
|
Chris@69
|
104 l=EC_ILOG(_this->rng);
|
|
Chris@69
|
105 r=_this->rng>>(l-16);
|
|
Chris@69
|
106 for(i=BITRES;i-->0;){
|
|
Chris@69
|
107 int b;
|
|
Chris@69
|
108 r=r*r>>15;
|
|
Chris@69
|
109 b=(int)(r>>16);
|
|
Chris@69
|
110 l=l<<1|b;
|
|
Chris@69
|
111 r>>=b;
|
|
Chris@69
|
112 }
|
|
Chris@69
|
113 return nbits-l;
|
|
Chris@69
|
114 }
|
|
Chris@69
|
115 #endif
|
|
Chris@69
|
116
|
|
Chris@69
|
117 #ifdef USE_SMALL_DIV_TABLE
|
|
Chris@69
|
118 /* Result of 2^32/(2*i+1), except for i=0. */
|
|
Chris@69
|
119 const opus_uint32 SMALL_DIV_TABLE[129] = {
|
|
Chris@69
|
120 0xFFFFFFFF, 0x55555555, 0x33333333, 0x24924924,
|
|
Chris@69
|
121 0x1C71C71C, 0x1745D174, 0x13B13B13, 0x11111111,
|
|
Chris@69
|
122 0x0F0F0F0F, 0x0D79435E, 0x0C30C30C, 0x0B21642C,
|
|
Chris@69
|
123 0x0A3D70A3, 0x097B425E, 0x08D3DCB0, 0x08421084,
|
|
Chris@69
|
124 0x07C1F07C, 0x07507507, 0x06EB3E45, 0x06906906,
|
|
Chris@69
|
125 0x063E7063, 0x05F417D0, 0x05B05B05, 0x0572620A,
|
|
Chris@69
|
126 0x05397829, 0x05050505, 0x04D4873E, 0x04A7904A,
|
|
Chris@69
|
127 0x047DC11F, 0x0456C797, 0x04325C53, 0x04104104,
|
|
Chris@69
|
128 0x03F03F03, 0x03D22635, 0x03B5CC0E, 0x039B0AD1,
|
|
Chris@69
|
129 0x0381C0E0, 0x0369D036, 0x03531DEC, 0x033D91D2,
|
|
Chris@69
|
130 0x0329161F, 0x03159721, 0x03030303, 0x02F14990,
|
|
Chris@69
|
131 0x02E05C0B, 0x02D02D02, 0x02C0B02C, 0x02B1DA46,
|
|
Chris@69
|
132 0x02A3A0FD, 0x0295FAD4, 0x0288DF0C, 0x027C4597,
|
|
Chris@69
|
133 0x02702702, 0x02647C69, 0x02593F69, 0x024E6A17,
|
|
Chris@69
|
134 0x0243F6F0, 0x0239E0D5, 0x02302302, 0x0226B902,
|
|
Chris@69
|
135 0x021D9EAD, 0x0214D021, 0x020C49BA, 0x02040810,
|
|
Chris@69
|
136 0x01FC07F0, 0x01F44659, 0x01ECC07B, 0x01E573AC,
|
|
Chris@69
|
137 0x01DE5D6E, 0x01D77B65, 0x01D0CB58, 0x01CA4B30,
|
|
Chris@69
|
138 0x01C3F8F0, 0x01BDD2B8, 0x01B7D6C3, 0x01B20364,
|
|
Chris@69
|
139 0x01AC5701, 0x01A6D01A, 0x01A16D3F, 0x019C2D14,
|
|
Chris@69
|
140 0x01970E4F, 0x01920FB4, 0x018D3018, 0x01886E5F,
|
|
Chris@69
|
141 0x0183C977, 0x017F405F, 0x017AD220, 0x01767DCE,
|
|
Chris@69
|
142 0x01724287, 0x016E1F76, 0x016A13CD, 0x01661EC6,
|
|
Chris@69
|
143 0x01623FA7, 0x015E75BB, 0x015AC056, 0x01571ED3,
|
|
Chris@69
|
144 0x01539094, 0x01501501, 0x014CAB88, 0x0149539E,
|
|
Chris@69
|
145 0x01460CBC, 0x0142D662, 0x013FB013, 0x013C995A,
|
|
Chris@69
|
146 0x013991C2, 0x013698DF, 0x0133AE45, 0x0130D190,
|
|
Chris@69
|
147 0x012E025C, 0x012B404A, 0x01288B01, 0x0125E227,
|
|
Chris@69
|
148 0x01234567, 0x0120B470, 0x011E2EF3, 0x011BB4A4,
|
|
Chris@69
|
149 0x01194538, 0x0116E068, 0x011485F0, 0x0112358E,
|
|
Chris@69
|
150 0x010FEF01, 0x010DB20A, 0x010B7E6E, 0x010953F3,
|
|
Chris@69
|
151 0x01073260, 0x0105197F, 0x0103091B, 0x01010101
|
|
Chris@69
|
152 };
|
|
Chris@69
|
153 #endif
|
