f22ab44c899cbc53f3808fb07f678ae67d461db7
[opus.git] / libcelt / rate.c
1 /* (C) 2007 Jean-Marc Valin, CSIRO
2 */
3 /*
4    Redistribution and use in source and binary forms, with or without
5    modification, are permitted provided that the following conditions
6    are met:
7    
8    - Redistributions of source code must retain the above copyright
9    notice, this list of conditions and the following disclaimer.
10    
11    - Redistributions in binary form must reproduce the above copyright
12    notice, this list of conditions and the following disclaimer in the
13    documentation and/or other materials provided with the distribution.
14    
15    - Neither the name of the Xiph.org Foundation nor the names of its
16    contributors may be used to endorse or promote products derived from
17    this software without specific prior written permission.
18    
19    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
23    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include <math.h>
33 #include "modes.h"
34 #include "cwrs.h"
35 #include "arch.h"
36 #include "os_support.h"
37
38 #include "entcode.h"
39
40 #define BITRES 4
41 #define BITROUND 8
42 #define BITOVERFLOW 1000
43
44 #define MAX_PULSES 64
45
46 int log2_frac(ec_uint32 val, int frac)
47 {
48    int i;
49    /* EC_ILOG() actually returns log2()+1, go figure */
50    int L = EC_ILOG(val)-1;
51    //printf ("in: %d %d ", val, L);
52    if (L>14)
53       val >>= L-14;
54    else if (L<14)
55       val <<= 14-L;
56    L <<= frac;
57    //printf ("%d\n", val);
58    for (i=0;i<frac;i++)
59    {
60       val = (val*val) >> 15;
61       //printf ("%d\n", val);
62       if (val > 16384)
63          L |= (1<<(frac-i-1));
64       else   
65          val <<= 1;
66    }
67    return L;
68 }
69
70 int log2_frac64(ec_uint64 val, int frac)
71 {
72    int i;
73    /* EC_ILOG64() actually returns log2()+1, go figure */
74    int L = EC_ILOG64(val)-1;
75    //printf ("in: %d %d ", val, L);
76    if (L>14)
77       val >>= L-14;
78    else if (L<14)
79       val <<= 14-L;
80    L <<= frac;
81    //printf ("%d\n", val);
82    for (i=0;i<frac;i++)
83    {
84       val = (val*val) >> 15;
85       //printf ("%d\n", val);
86       if (val > 16384)
87          L |= (1<<(frac-i-1));
88       else   
89          val <<= 1;
90    }
91    return L;
92 }
93
94 int bits2pulses0(int bits, int N)
95 {
96    int i, b, prev;
97    /* FIXME: This is terribly inefficient. Do a bisection instead
98    but be careful about overflows */
99    prev = 0;
100    i=1;
101    b = log2_frac64(ncwrs64(N, i),0);
102    while (b<bits)
103    {
104       prev=b;
105       i++;
106       b = log2_frac64(ncwrs64(N, i),0);
107    }
108    if (bits-prev < b-bits)
109       i--;
110    return i;
111 }
112
113
114 struct alloc_data {
115    int len;
116    const int *bands;
117    int **bits;
118    int **rev_bits;
119 };
120
121 void alloc_init(struct alloc_data *alloc, const CELTMode *m)
122 {
123    int i, prevN, BC;
124    const int *eBands = m->eBands;
125    
126    alloc->len = m->nbEBands;
127    alloc->bands = m->eBands;
128    alloc->bits = celt_alloc(m->nbEBands*sizeof(int*));
129    alloc->rev_bits = celt_alloc(m->nbEBands*sizeof(int*));
130    
131    BC = m->nbMdctBlocks*m->nbChannels;
132    prevN = -1;
133    for (i=0;i<alloc->len;i++)
134    {
135       int N = BC*(eBands[i+1]-eBands[i]);
136       if (N == prevN)
137       {
138          alloc->bits[i] = alloc->bits[i-1];
139          alloc->rev_bits[i] = alloc->rev_bits[i-1];
140       } else {
141          int j;
142          /* FIXME: We could save memory here */
143          alloc->bits[i] = celt_alloc(MAX_PULSES*sizeof(int));
144          alloc->rev_bits[i] = celt_alloc(MAX_PULSES*sizeof(int));
145          for (j=0;j<MAX_PULSES;j++)
146          {
147             alloc->bits[i][j] = log2_frac64(ncwrs64(N, j),BITRES);
148             /* We could just update rev_bits here */
149             if (alloc->bits[i][j] > (60<<BITRES))
150                break;
151          }
152          for (;j<MAX_PULSES;j++)
153             alloc->bits[i][j] = BITOVERFLOW;
154          for (j=0;j<32;j++)
155             alloc->rev_bits[i][j] = bits2pulses0(j, N);
156          prevN = N;
157       }
158    }
159 }
160
161 void alloc_clear(struct alloc_data *alloc)
162 {
163    int i;
164    int *prevPtr = NULL;
165    for (i=0;i<alloc->len;i++)
166    {
167       if (alloc->bits[i] != prevPtr)
168       {
169          prevPtr = alloc->bits[i];
170          celt_free(alloc->bits[i]);
171          celt_free(alloc->rev_bits[i]);
172       }
173    }
174    celt_free(alloc->bits);
175    celt_free(alloc->rev_bits);
176 }
177
178
179 int compute_allocation(const CELTMode *m, int *pulses)
180 {
181    int i, N, BC, bits;
182    const int *eBands = m->eBands;
183    BC = m->nbMdctBlocks*m->nbChannels;
184    bits = 0;
185    for (i=0;i<m->nbEBands;i++)
186    {
187       int q;
188       N = BC*(eBands[i+1]-eBands[i]);
189       q = pulses[i];
190       if (q<=0)
191       {
192          bits += log2_frac64(eBands[i] - (eBands[i+1]-eBands[i]), 8) + (1<<8);
193          q = -q;
194       }
195       if (q != 0)
196          bits += log2_frac64(ncwrs64(N, pulses[i]), 8);
197    }
198    return (bits+255)>>8;
199 }
200
201 int bits2pulses(const struct alloc_data *alloc, int band, int bits)
202 {
203    int lo, hi;
204    lo = 0;
205    hi = MAX_PULSES;
206    
207    while (hi-lo != 1)
208    {
209       int mid = (lo+hi)>>1;
210       if (alloc->bits[band][mid] >= bits)
211          hi = mid;
212       else
213          lo = mid;
214    }
215    if (bits-alloc->bits[band][lo] <= alloc->bits[band][hi]-bits)
216       return lo;
217    else
218       return hi;
219 }
220
221 int vec_bits2pulses(const struct alloc_data *alloc, const int *bands, int *bits, int *pulses, int len, int B)
222 {
223    int i;
224    int sum=0;
225    for (i=0;i<len;i++)
226    {
227       int N = (bands[i+1]-bands[i])*B;
228       pulses[i] = bits2pulses(alloc, i, bits[i]);
229       sum += alloc->bits[i][pulses[i]];
230    }
231    return sum;
232 }
233
234 #if 0
235 int interp_bits2pulses(const struct alloc_data *alloc, int *bits1, int *bits2, int total, int *pulses, int len, int B)
236 {
237    int i;
238    const int *bands = alloc->bands;
239    /* FIXME: This too is terribly inefficient. We should do a bisection instead */
240    for (i=0;i<16;i++)
241    {
242       int j;
243       int bits[len];
244       for (j=0;j<len;j++)
245          bits[j] = ((16-i)*bits1[j] + i*bits2[j]);
246       if (vec_bits2pulses(alloc, bands, bits, pulses, len, B) > total)
247          break;
248    }
249    if (i==0)
250       return -1;
251    else {
252       int j;
253       int bits[len];
254       /* Get the previous one (that didn't bust). Should rewrite that anyway */
255       i--;
256       for (j=0;j<len;j++)
257          bits[j] = ((16-i)*bits1[j] + i*bits2[j]);
258       return vec_bits2pulses(alloc, bands, bits, pulses, len, B);
259    }
260 }
261 #else
262 int interp_bits2pulses(const struct alloc_data *alloc, int *bits1, int *bits2, int total, int *pulses, int len, int B)
263 {
264    int lo, hi, out;
265    int j;
266    int bits[len];
267    int used_bits[len];
268    const int *bands = alloc->bands;
269    lo = 0;
270    hi = 1<<BITRES;
271    while (hi-lo != 1)
272    {
273       int mid = (lo+hi)>>1;
274       for (j=0;j<len;j++)
275          bits[j] = ((1<<BITRES)-mid)*bits1[j] + mid*bits2[j];
276       if (vec_bits2pulses(alloc, bands, bits, pulses, len, B) > total<<BITRES)
277          hi = mid;
278       else
279          lo = mid;
280    }
281    
282    for (j=0;j<len;j++)
283       bits[j] = ((1<<BITRES)-lo)*bits1[j] + lo*bits2[j];
284    out = vec_bits2pulses(alloc, bands, bits, pulses, len, B);
285    /* Do some refinement to use up all bits */
286    while(1)
287    {
288       int incremented = 0;
289       for (j=0;j<len;j++)
290       {
291          if (alloc->bits[j][pulses[j]] < bits[j])
292          {
293             if (out+alloc->bits[j][pulses[j]+1]-alloc->bits[j][pulses[j]] <= total<<BITRES)
294             {
295                out = out+alloc->bits[j][pulses[j]+1]-alloc->bits[j][pulses[j]];
296                pulses[j] += 1;
297                incremented = 1;
298             }
299          }
300       }
301       if (!incremented)
302          break;
303    }
304    return (out+BITROUND) >> BITRES;
305 }
306 #endif
307
308 #if 0
309 int main()
310 {
311    int i;
312    /*for(i=1;i<2000000000;i+=1738)
313    {
314       printf ("%d %d\n", i, frac_log2(i, 10));
315    }*/
316    for (i=4;i<=32;i*=2)
317    {
318       int j;
319       for (j=0;j<30;j++)
320       {
321          printf ("%d %d %d\n", i, j, bits2pulses(j,i));
322       }
323    }
324    return 0;
325 }
326 #endif
327 #if 0
328 int main()
329 {
330    int i;
331    int bits[18] = {10, 9, 9, 8, 8, 8, 8, 8, 8, 8, 9, 10, 8, 9, 10, 11, 6, 7};
332    int bits1[18] = {8, 7, 7, 6, 6, 6, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5};
333    int bits2[18] = {15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15};
334    int bank[20] = {0,  4,  8, 12, 16, 20, 24, 28, 32, 38, 44, 52, 62, 74, 90,112,142,182, 232,256};
335    int pulses[18];
336    struct alloc_data alloc;
337    
338    alloc_init(&alloc, celt_mode0);
339    int b = vec_bits2pulses(&alloc, bank, bits, pulses, 18, 1);
340    printf ("total: %d bits\n", b);
341    for (i=0;i<18;i++)
342       printf ("%d ", pulses[i]);
343    printf ("\n");
344    b = interp_bits2pulses(&alloc, bits1, bits2, 162, pulses, 18, 1);
345    printf ("total: %d bits\n", b);
346    for (i=0;i<18;i++)
347       printf ("%d ", pulses[i]);
348    printf ("\n");
349
350    alloc_clear(&alloc);
351    return 0;
352 }
353 #endif