Limiting intra-frame prediction codebook to 32 entries (plus sign)
[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 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 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
96 void alloc_init(struct alloc_data *alloc, const CELTMode *m)
97 {
98    int i, prevN, BC;
99    const int *eBands = m->eBands;
100    
101    alloc->mode = m;
102    alloc->len = m->nbEBands;
103    alloc->bands = m->eBands;
104    alloc->bits = celt_alloc(m->nbEBands*sizeof(int*));
105    
106    BC = m->nbMdctBlocks*m->nbChannels;
107    prevN = -1;
108    for (i=0;i<alloc->len;i++)
109    {
110       int N = BC*(eBands[i+1]-eBands[i]);
111       if (N == prevN && eBands[i] < m->pitchEnd)
112       {
113          alloc->bits[i] = alloc->bits[i-1];
114       } else {
115          int j;
116          /* FIXME: We could save memory here */
117          alloc->bits[i] = celt_alloc(MAX_PULSES*sizeof(int));
118          for (j=0;j<MAX_PULSES;j++)
119          {
120             int done = 0;
121             alloc->bits[i][j] = log2_frac64(ncwrs64(N, j),BITRES);
122             /* FIXME: Could there be a better test for the max number of pulses that fit in 64 bits? */
123             if (alloc->bits[i][j] > (60<<BITRES))
124                done = 1;
125             /* Add the intra-frame prediction bits */
126             if (eBands[i] >= m->pitchEnd)
127             {
128                int max_pos = 2*eBands[i]-eBands[i+1];
129                if (max_pos > 32)
130                   max_pos = 32;
131                alloc->bits[i][j] += (1<<BITRES) + log2_frac(max_pos,BITRES);
132             }
133             /* We could just update rev_bits here */
134             if (done)
135                break;
136          }
137          for (;j<MAX_PULSES;j++)
138             alloc->bits[i][j] = BITOVERFLOW;
139          prevN = N;
140       }
141    }
142 }
143
144 void alloc_clear(struct alloc_data *alloc)
145 {
146    int i;
147    int *prevPtr = NULL;
148    for (i=0;i<alloc->len;i++)
149    {
150       if (alloc->bits[i] != prevPtr)
151       {
152          prevPtr = alloc->bits[i];
153          celt_free(alloc->bits[i]);
154       }
155    }
156    celt_free(alloc->bits);
157 }
158
159 int bits2pulses(const struct alloc_data *alloc, int band, int bits)
160 {
161    int lo, hi;
162    lo = 0;
163    hi = MAX_PULSES-1;
164    
165    while (hi-lo != 1)
166    {
167       int mid = (lo+hi)>>1;
168       if (alloc->bits[band][mid] >= bits)
169          hi = mid;
170       else
171          lo = mid;
172    }
173    if (bits-alloc->bits[band][lo] <= alloc->bits[band][hi]-bits)
174       return lo;
175    else
176       return hi;
177 }
178
179 int vec_bits2pulses(const struct alloc_data *alloc, const int *bands, int *bits, int *pulses, int len)
180 {
181    int i, BC;
182    int sum=0;
183    BC = alloc->mode->nbMdctBlocks*alloc->mode->nbChannels;
184
185    for (i=0;i<len;i++)
186    {
187       int N = (bands[i+1]-bands[i])*BC;
188       pulses[i] = bits2pulses(alloc, i, bits[i]);
189       sum += alloc->bits[i][pulses[i]];
190    }
191    //printf ("sum = %d\n", sum);
192    return sum;
193 }
194
195 int interp_bits2pulses(const struct alloc_data *alloc, int *bits1, int *bits2, int total, int *pulses, int len)
196 {
197    int lo, hi, out;
198    int j;
199    int bits[len];
200    const int *bands = alloc->bands;
201    lo = 0;
202    hi = 1<<BITRES;
203    while (hi-lo != 1)
204    {
205       int mid = (lo+hi)>>1;
206       for (j=0;j<len;j++)
207          bits[j] = ((1<<BITRES)-mid)*bits1[j] + mid*bits2[j];
208       if (vec_bits2pulses(alloc, bands, bits, pulses, len) > total<<BITRES)
209          hi = mid;
210       else
211          lo = mid;
212    }
213    //printf ("interp bisection gave %d\n", lo);
214    for (j=0;j<len;j++)
215       bits[j] = ((1<<BITRES)-lo)*bits1[j] + lo*bits2[j];
216    out = vec_bits2pulses(alloc, bands, bits, pulses, len);
217    /* Do some refinement to use up all bits */
218    while(1)
219    {
220       int incremented = 0;
221       for (j=0;j<len;j++)
222       {
223          if (alloc->bits[j][pulses[j]] < bits[j] && pulses[j]<MAX_PULSES-1)
224          {
225             if (out+alloc->bits[j][pulses[j]+1]-alloc->bits[j][pulses[j]] <= total<<BITRES)
226             {
227                out = out+alloc->bits[j][pulses[j]+1]-alloc->bits[j][pulses[j]];
228                pulses[j] += 1;
229                incremented = 1;
230                //printf ("INCREMENT %d\n", j);
231             }
232          }
233       }
234       if (!incremented)
235          break;
236    }
237    return (out+BITROUND) >> BITRES;
238 }
239
240 int compute_allocation(const struct alloc_data *alloc, int *offsets, int total, int *pulses)
241 {
242    int lo, hi, len;
243    const CELTMode *m;
244
245    m = alloc->mode;
246    len = m->nbEBands;
247    lo = 0;
248    hi = m->nbAllocVectors - 1;
249    while (hi-lo != 1)
250    {
251       int j;
252       int bits[len];
253       int pulses[len];
254       int mid = (lo+hi) >> 1;
255       for (j=0;j<len;j++)
256       {
257          bits[j] = (m->allocVectors[mid*len+j] + offsets[j])<<BITRES;
258          if (bits[j] < 0)
259             bits[j] = 0;
260          //printf ("%d ", bits[j]);
261       }
262       //printf ("\n");
263       if (vec_bits2pulses(alloc, alloc->bands, bits, pulses, len) > total<<BITRES)
264          hi = mid;
265       else
266          lo = mid;
267       //printf ("lo = %d, hi = %d\n", lo, hi);
268    }
269    {
270       int bits1[len];
271       int bits2[len];
272       int j;
273       for (j=0;j<len;j++)
274       {
275          bits1[j] = m->allocVectors[lo*len+j] + offsets[j];
276          bits2[j] = m->allocVectors[hi*len+j] + offsets[j];
277          if (bits1[j] < 0)
278             bits1[j] = 0;
279          if (bits2[j] < 0)
280             bits2[j] = 0;
281       }
282       return interp_bits2pulses(alloc, bits1, bits2, total, pulses, len);
283    }
284 }
285
286 #if 0
287 int main()
288 {
289    int i;
290    printf ("log(128) = %d\n", EC_ILOG(128));
291    for(i=1;i<2000000000;i+=1738)
292    {
293       printf ("%d %d\n", i, log2_frac(i, 10));
294    }
295    return 0;
296 }
297 #endif
298 #if 0
299 int main()
300 {
301    int i;
302    int offsets[18] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
303    int bits[18] = {10, 9, 9, 8, 8, 8, 8, 8, 8, 8, 9, 10, 8, 9, 10, 11, 6, 7};
304    int bits1[18] = {8, 7, 7, 6, 6, 6, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5};
305    int bits2[18] = {15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15};
306    int bank[20] = {0,  4,  8, 12, 16, 20, 24, 28, 32, 38, 44, 52, 62, 74, 90,112,142,182, 232,256};
307    int pulses[18];
308    struct alloc_data alloc;
309    
310    alloc_init(&alloc, celt_mode0);
311    int b;
312    //b = vec_bits2pulses(&alloc, bank, bits, pulses, 18);
313    //printf ("total: %d bits\n", b);
314    //for (i=0;i<18;i++)
315    //   printf ("%d ", pulses[i]);
316    //printf ("\n");
317    //b = interp_bits2pulses(&alloc, bits1, bits2, 162, pulses, 18);
318    b = compute_allocation(&alloc, offsets, 190, pulses);
319    printf ("total: %d bits\n", b);
320    for (i=0;i<18;i++)
321       printf ("%d ", pulses[i]);
322    printf ("\n");
323
324    alloc_clear(&alloc);
325    return 0;
326 }
327 #endif