more bit allocation wip
[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 BITOVERFLOW 1000
42
43 int log2_frac(ec_uint32 val, int frac)
44 {
45    int i;
46    /* EC_ILOG() actually returns log2()+1, go figure */
47    int L = EC_ILOG(val)-1;
48    //printf ("in: %d %d ", val, L);
49    if (L>14)
50       val >>= L-14;
51    else if (L<14)
52       val <<= 14-L;
53    L <<= frac;
54    //printf ("%d\n", val);
55    for (i=0;i<frac;i++)
56    {
57       val = (val*val) >> 15;
58       //printf ("%d\n", val);
59       if (val > 16384)
60          L |= (1<<(frac-i-1));
61       else   
62          val <<= 1;
63    }
64    return L;
65 }
66
67 int log2_frac64(ec_uint64 val, int frac)
68 {
69    int i;
70    /* EC_ILOG64() actually returns log2()+1, go figure */
71    int L = EC_ILOG64(val)-1;
72    //printf ("in: %d %d ", val, L);
73    if (L>14)
74       val >>= L-14;
75    else if (L<14)
76       val <<= 14-L;
77    L <<= frac;
78    //printf ("%d\n", val);
79    for (i=0;i<frac;i++)
80    {
81       val = (val*val) >> 15;
82       //printf ("%d\n", val);
83       if (val > 16384)
84          L |= (1<<(frac-i-1));
85       else   
86          val <<= 1;
87    }
88    return L;
89 }
90
91 int bits2pulses(int bits, int N)
92 {
93    int i, b, prev;
94    /* FIXME: This is terribly inefficient. Do a bisection instead
95    but be careful about overflows */
96    prev = 0;
97    i=1;
98    b = log2_frac64(ncwrs64(N, i),0);
99    while (b<bits)
100    {
101       prev=b;
102       i++;
103       b = log2_frac64(ncwrs64(N, i),0);
104    }
105    if (bits-prev < b-bits)
106       i--;
107    return i;
108 }
109
110
111 struct alloc_data {
112    int len;
113    int **bits;
114    int **rev_bits;
115 };
116
117 void alloc_init(struct alloc_data *alloc, const CELTMode *m)
118 {
119    int i, prevN, BC;
120    const int *eBands = m->eBands;
121    alloc->bits = celt_alloc(m->nbEBands*sizeof(int*));
122    alloc->rev_bits = celt_alloc(m->nbEBands*sizeof(int*));
123    alloc->len = m->nbEBands;
124    BC = m->nbMdctBlocks*m->nbChannels;
125    prevN = -1;
126    for (i=0;i<alloc->len;i++)
127    {
128       int N = BC*(eBands[i+1]-eBands[i]);
129       if (N == prevN)
130       {
131          alloc->bits[i] = alloc->bits[i-1];
132          alloc->rev_bits[i] = alloc->rev_bits[i-1];
133       } else {
134          int j;
135          /* FIXME: We could save memory here */
136          alloc->bits[i] = celt_alloc(64*sizeof(int));
137          alloc->rev_bits[i] = celt_alloc(64*sizeof(int));
138          for (j=0;j<64;j++)
139          {
140             alloc->bits[i][j] = log2_frac64(ncwrs64(N, j),BITRES);
141             /* We could just update rev_bits here */
142             if (alloc->bits[i][j] > (60>>BITRES))
143                break;
144          }
145          for (;j<64;j++)
146             alloc->bits[i][j] = BITOVERFLOW;
147          for (j=0;j<32;j++)
148             alloc->rev_bits[i][j] = bits2pulses(j, N);
149          prevN = N;
150       }
151    }
152 }
153
154 void alloc_clear(struct alloc_data *alloc)
155 {
156    int i;
157    int *prevPtr = NULL;
158    for (i=0;i<alloc->len;i++)
159    {
160       if (alloc->bits[i] != prevPtr)
161       {
162          prevPtr = alloc->bits[i];
163          celt_free(alloc->bits[i]);
164          celt_free(alloc->rev_bits[i]);
165       }
166    }
167    celt_free(alloc->bits);
168    celt_free(alloc->rev_bits);
169 }
170
171
172 int compute_allocation(const CELTMode *m, int *pulses)
173 {
174    int i, N, BC, bits;
175    const int *eBands = m->eBands;
176    BC = m->nbMdctBlocks*m->nbChannels;
177    bits = 0;
178    for (i=0;i<m->nbEBands;i++)
179    {
180       int q;
181       N = BC*(eBands[i+1]-eBands[i]);
182       q = pulses[i];
183       if (q<=0)
184       {
185          bits += log2_frac64(eBands[i] - (eBands[i+1]-eBands[i]), 8) + (1<<8);
186          q = -q;
187       }
188       if (q != 0)
189          bits += log2_frac64(ncwrs64(N, pulses[i]), 8);
190    }
191    return (bits+255)>>8;
192 }
193
194
195 int vec_bits2pulses(int *bands, int *bits, int *pulses, int len, int B)
196 {
197    int i;
198    int sum=0;
199    for (i=0;i<len;i++)
200    {
201       int N = (bands[i+1]-bands[i])*B;
202       pulses[i] = bits2pulses(bits[i], N);
203       sum += log2_frac64(ncwrs(N, pulses[i]),8);
204    }
205    return (sum+255)>>8;
206 }
207
208 int interp_bits2pulses(int *bands, int *bits1, int *bits2, int total, int *pulses, int len, int B)
209 {
210    int i;
211    /* FIXME: This too is terribly inefficient. We should do a bisection instead */
212    for (i=0;i<16;i++)
213    {
214       int j;
215       int bits[len];
216       for (j=0;j<len;j++)
217          bits[j] = ((16-i)*bits1[j] + i*bits2[j]) >> 4;
218       if (vec_bits2pulses(bands, bits, pulses, len, B) > total)
219          break;
220    }
221    if (i==0)
222       return -1;
223    else {
224       int j;
225       int bits[len];
226       /* Get the previous one (that didn't bust). Should rewrite that anyway */
227       i--;
228       for (j=0;j<len;j++)
229          bits[j] = ((16-i)*bits1[j] + i*bits2[j]) >> 4;      
230       return vec_bits2pulses(bands, bits, pulses, len, B);
231    }
232 }
233
234 #if 0
235 int main()
236 {
237    int i;
238    /*for(i=1;i<2000000000;i+=1738)
239    {
240       printf ("%d %d\n", i, frac_log2(i, 10));
241    }*/
242    for (i=4;i<=32;i*=2)
243    {
244       int j;
245       for (j=0;j<30;j++)
246       {
247          printf ("%d %d %d\n", i, j, bits2pulses(j,i));
248       }
249    }
250    return 0;
251 }
252 #endif
253 #if 0
254 int main()
255 {
256    int i;
257    int bits[18] = {10, 9, 9, 8, 8, 8, 8, 8, 8, 8, 9, 10, 8, 9, 10, 11, 6, 7};
258    int bits1[18] = {8, 7, 7, 6, 6, 6, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5};
259    int bits2[18] = {15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15};
260    int bank[20] = {0,  4,  8, 12, 16, 20, 24, 28, 32, 38, 44, 52, 62, 74, 90,112,142,182, 232,256};
261    int pulses[18];
262    struct alloc_data alloc;
263    
264    alloc_init(&alloc, celt_mode0);
265    int b = vec_bits2pulses(bank, bits, pulses, 18, 1);
266    printf ("total: %d bits\n", b);
267    for (i=0;i<18;i++)
268       printf ("%d ", pulses[i]);
269    printf ("\n");
270    b = interp_bits2pulses(bank, bits1, bits2, 160, pulses, 18, 1);
271    printf ("total: %d bits\n", b);
272    for (i=0;i<18;i++)
273       printf ("%d ", pulses[i]);
274    printf ("\n");
275
276    alloc_clear(&alloc);
277    return 0;
278 }
279 #endif