removed // comments and added stack_alloc.h (not used everywhere yet)
[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             }
224          }
225       }
226       if (!incremented)
227       {
228          if (firstpass)
229             firstpass = 0;
230          else
231             break;
232       }
233    }
234    return (out+BITROUND) >> BITRES;
235 }
236
237 int compute_allocation(const CELTMode *m, int *offsets, int total, int *pulses)
238 {
239    int lo, hi, len;
240
241    len = m->nbEBands;
242    lo = 0;
243    hi = m->nbAllocVectors - 1;
244    while (hi-lo != 1)
245    {
246       int j;
247       int bits[len];
248       int pulses[len];
249       int mid = (lo+hi) >> 1;
250       for (j=0;j<len;j++)
251       {
252          bits[j] = (m->allocVectors[mid*len+j] + offsets[j])<<BITRES;
253          if (bits[j] < 0)
254             bits[j] = 0;
255          /*printf ("%d ", bits[j]);*/
256       }
257       /*printf ("\n");*/
258       if (vec_bits2pulses(m, m->eBands, bits, pulses, len) > total<<BITRES)
259          hi = mid;
260       else
261          lo = mid;
262       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
263    }
264    {
265       int bits1[len];
266       int bits2[len];
267       int j;
268       for (j=0;j<len;j++)
269       {
270          bits1[j] = m->allocVectors[lo*len+j] + offsets[j];
271          bits2[j] = m->allocVectors[hi*len+j] + offsets[j];
272          if (bits1[j] < 0)
273             bits1[j] = 0;
274          if (bits2[j] < 0)
275             bits2[j] = 0;
276       }
277       return interp_bits2pulses(m, bits1, bits2, total, pulses, len);
278    }
279 }
280
281 #if 0
282 int main()
283 {
284    int i;
285    printf ("log(128) = %d\n", EC_ILOG(128));
286    for(i=1;i<2000000000;i+=1738)
287    {
288       printf ("%d %d\n", i, log2_frac(i, 10));
289    }
290    return 0;
291 }
292 #endif
293 #if 0
294 int main()
295 {
296    int i;
297    int offsets[18] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
298    int bits[18] = {10, 9, 9, 8, 8, 8, 8, 8, 8, 8, 9, 10, 8, 9, 10, 11, 6, 7};
299    int bits1[18] = {8, 7, 7, 6, 6, 6, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5};
300    int bits2[18] = {15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15};
301    int bank[20] = {0,  4,  8, 12, 16, 20, 24, 28, 32, 38, 44, 52, 62, 74, 90,112,142,182, 232,256};
302    int pulses[18];
303    struct alloc_data alloc;
304    
305    alloc_init(&alloc, celt_mode0);
306    int b;
307    //b = vec_bits2pulses(&alloc, bank, bits, pulses, 18);
308    //printf ("total: %d bits\n", b);
309    //for (i=0;i<18;i++)
310    //   printf ("%d ", pulses[i]);
311    //printf ("\n");
312    //b = interp_bits2pulses(&alloc, bits1, bits2, 162, pulses, 18);
313    b = compute_allocation(&alloc, offsets, 190, pulses);
314    printf ("total: %d bits\n", b);
315    for (i=0;i<18;i++)
316       printf ("%d ", pulses[i]);
317    printf ("\n");
318
319    alloc_clear(&alloc);
320    return 0;
321 }
322 #endif