Merged the rate allocation atruct directly into the mode struct.
[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 #include "rate.h"
40
41 #define BITRES 4
42 #define BITROUND 8
43 #define BITOVERFLOW 10000
44
45 #define MAX_PULSES 64
46
47 static int log2_frac(ec_uint32 val, int frac)
48 {
49    int i;
50    /* EC_ILOG() actually returns log2()+1, go figure */
51    int L = EC_ILOG(val)-1;
52    //printf ("in: %d %d ", val, L);
53    if (L>14)
54       val >>= L-14;
55    else if (L<14)
56       val <<= 14-L;
57    L <<= frac;
58    //printf ("%d\n", val);
59    for (i=0;i<frac;i++)
60    {
61       val = (val*val) >> 15;
62       //printf ("%d\n", val);
63       if (val > 16384)
64          L |= (1<<(frac-i-1));
65       else   
66          val <<= 1;
67    }
68    return L;
69 }
70
71 static int log2_frac64(ec_uint64 val, int frac)
72 {
73    int i;
74    /* EC_ILOG64() actually returns log2()+1, go figure */
75    int L = EC_ILOG64(val)-1;
76    //printf ("in: %d %d ", val, L);
77    if (L>14)
78       val >>= L-14;
79    else if (L<14)
80       val <<= 14-L;
81    L <<= frac;
82    //printf ("%d\n", val);
83    for (i=0;i<frac;i++)
84    {
85       val = (val*val) >> 15;
86       //printf ("%d\n", val);
87       if (val > 16384)
88          L |= (1<<(frac-i-1));
89       else   
90          val <<= 1;
91    }
92    return L;
93 }
94
95 void compute_alloc_cache(CELTMode *m)
96 {
97    int i, prevN, BC;
98    int **bits;
99    const int *eBands = m->eBands;
100
101    bits = celt_alloc(m->nbEBands*sizeof(int*));
102    
103    BC = m->nbMdctBlocks*m->nbChannels;
104    prevN = -1;
105    for (i=0;i<m->nbEBands;i++)
106    {
107       int N = BC*(eBands[i+1]-eBands[i]);
108       if (N == prevN && eBands[i] < m->pitchEnd)
109       {
110          bits[i] = bits[i-1];
111       } else {
112          int j;
113          /* FIXME: We could save memory here */
114          bits[i] = celt_alloc(MAX_PULSES*sizeof(int));
115          for (j=0;j<MAX_PULSES;j++)
116          {
117             int done = 0;
118             int pulses = j;
119             /* For bands where there's no pitch, id 1 corresponds to intra prediction 
120             with no pulse. id 2 means intra prediction with one pulse, and so on.*/
121             if (eBands[i] >= m->pitchEnd)
122                pulses -= 1;
123             if (pulses < 0)
124                bits[i][j] = 0;
125             else {
126                bits[i][j] = log2_frac64(ncwrs64(N, pulses),BITRES);
127                /* FIXME: Could there be a better test for the max number of pulses that fit in 64 bits? */
128                if (bits[i][j] > (60<<BITRES))
129                   done = 1;
130                /* Add the intra-frame prediction bits */
131                if (eBands[i] >= m->pitchEnd)
132                {
133                   int max_pos = 2*eBands[i]-eBands[i+1];
134                   if (max_pos > 32)
135                      max_pos = 32;
136                   bits[i][j] += (1<<BITRES) + log2_frac(max_pos,BITRES);
137                }
138             }
139             if (done)
140                break;
141          }
142          for (;j<MAX_PULSES;j++)
143             bits[i][j] = BITOVERFLOW;
144          prevN = N;
145       }
146    }
147    m->bits = (const int * const *)bits;
148 }
149
150
151 int bits2pulses(const CELTMode *m, int band, int bits)
152 {
153    int lo, hi;
154    lo = 0;
155    hi = MAX_PULSES-1;
156    
157    while (hi-lo != 1)
158    {
159       int mid = (lo+hi)>>1;
160       if (m->bits[band][mid] >= bits)
161          hi = mid;
162       else
163          lo = mid;
164    }
165    if (bits-m->bits[band][lo] <= m->bits[band][hi]-bits)
166       return lo;
167    else
168       return hi;
169 }
170
171 int vec_bits2pulses(const CELTMode *m, const int *bands, int *bits, int *pulses, int len)
172 {
173    int i, BC;
174    int sum=0;
175    BC = m->nbMdctBlocks*m->nbChannels;
176
177    for (i=0;i<len;i++)
178    {
179       pulses[i] = bits2pulses(m, i, bits[i]);
180       sum += m->bits[i][pulses[i]];
181    }
182    //printf ("sum = %d\n", sum);
183    return sum;
184 }
185
186 int interp_bits2pulses(const CELTMode *m, int *bits1, int *bits2, int total, int *pulses, int len)
187 {
188    int lo, hi, out;
189    int j;
190    int bits[len];
191    const int *bands = m->eBands;
192    lo = 0;
193    hi = 1<<BITRES;
194    while (hi-lo != 1)
195    {
196       int mid = (lo+hi)>>1;
197       for (j=0;j<len;j++)
198          bits[j] = ((1<<BITRES)-mid)*bits1[j] + mid*bits2[j];
199       if (vec_bits2pulses(m, bands, bits, pulses, len) > total<<BITRES)
200          hi = mid;
201       else
202          lo = mid;
203    }
204    //printf ("interp bisection gave %d\n", lo);
205    for (j=0;j<len;j++)
206       bits[j] = ((1<<BITRES)-lo)*bits1[j] + lo*bits2[j];
207    out = vec_bits2pulses(m, bands, bits, pulses, len);
208    /* Do some refinement to use up all bits. In the first pass, we can only add pulses to 
209       bands that are under their allocated budget. In the second pass, anything goes */
210    int firstpass = 1;
211    while(1)
212    {
213       int incremented = 0;
214       for (j=0;j<len;j++)
215       {
216          if ((!firstpass || m->bits[j][pulses[j]] < bits[j]) && pulses[j]<MAX_PULSES-1)
217          {
218             if (out+m->bits[j][pulses[j]+1]-m->bits[j][pulses[j]] <= total<<BITRES)
219             {
220                out = out+m->bits[j][pulses[j]+1]-m->bits[j][pulses[j]];
221                pulses[j] += 1;
222                incremented = 1;
223                //printf ("INCREMENT %d\n", j);
224             }
225          }
226       }
227       if (!incremented)
228       {
229          if (firstpass)
230             firstpass = 0;
231          else
232             break;
233       }
234    }
235    return (out+BITROUND) >> BITRES;
236 }
237
238 int compute_allocation(const CELTMode *m, int *offsets, int total, int *pulses)
239 {
240    int lo, hi, len;
241
242    len = m->nbEBands;
243    lo = 0;
244    hi = m->nbAllocVectors - 1;
245    while (hi-lo != 1)
246    {
247       int j;
248       int bits[len];
249       int pulses[len];
250       int mid = (lo+hi) >> 1;
251       for (j=0;j<len;j++)
252       {
253          bits[j] = (m->allocVectors[mid*len+j] + offsets[j])<<BITRES;
254          if (bits[j] < 0)
255             bits[j] = 0;
256          //printf ("%d ", bits[j]);
257       }
258       //printf ("\n");
259       if (vec_bits2pulses(m, m->eBands, bits, pulses, len) > total<<BITRES)
260          hi = mid;
261       else
262          lo = mid;
263       //printf ("lo = %d, hi = %d\n", lo, hi);
264    }
265    {
266       int bits1[len];
267       int bits2[len];
268       int j;
269       for (j=0;j<len;j++)
270       {
271          bits1[j] = m->allocVectors[lo*len+j] + offsets[j];
272          bits2[j] = m->allocVectors[hi*len+j] + offsets[j];
273          if (bits1[j] < 0)
274             bits1[j] = 0;
275          if (bits2[j] < 0)
276             bits2[j] = 0;
277       }
278       return interp_bits2pulses(m, bits1, bits2, total, pulses, len);
279    }
280 }
281
282 #if 0
283 int main()
284 {
285    int i;
286    printf ("log(128) = %d\n", EC_ILOG(128));
287    for(i=1;i<2000000000;i+=1738)
288    {
289       printf ("%d %d\n", i, log2_frac(i, 10));
290    }
291    return 0;
292 }
293 #endif
294 #if 0
295 int main()
296 {
297    int i;
298    int offsets[18] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
299    int bits[18] = {10, 9, 9, 8, 8, 8, 8, 8, 8, 8, 9, 10, 8, 9, 10, 11, 6, 7};
300    int bits1[18] = {8, 7, 7, 6, 6, 6, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5};
301    int bits2[18] = {15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15};
302    int bank[20] = {0,  4,  8, 12, 16, 20, 24, 28, 32, 38, 44, 52, 62, 74, 90,112,142,182, 232,256};
303    int pulses[18];
304    struct alloc_data alloc;
305    
306    alloc_init(&alloc, celt_mode0);
307    int b;
308    //b = vec_bits2pulses(&alloc, bank, bits, pulses, 18);
309    //printf ("total: %d bits\n", b);
310    //for (i=0;i<18;i++)
311    //   printf ("%d ", pulses[i]);
312    //printf ("\n");
313    //b = interp_bits2pulses(&alloc, bits1, bits2, 162, pulses, 18);
314    b = compute_allocation(&alloc, offsets, 190, pulses);
315    printf ("total: %d bits\n", b);
316    for (i=0;i<18;i++)
317       printf ("%d ", pulses[i]);
318    printf ("\n");
319
320    alloc_clear(&alloc);
321    return 0;
322 }
323 #endif