Updated static modes for new pulse cache.
[opus.git] / libcelt / rate.c
1 /* Copyright (c) 2007-2008 CSIRO
2    Copyright (c) 2007-2009 Xiph.Org Foundation
3    Written by Jean-Marc Valin */
4 /*
5    Redistribution and use in source and binary forms, with or without
6    modification, are permitted provided that the following conditions
7    are met:
8    
9    - Redistributions of source code must retain the above copyright
10    notice, this list of conditions and the following disclaimer.
11    
12    - Redistributions in binary form must reproduce the above copyright
13    notice, this list of conditions and the following disclaimer in the
14    documentation and/or other materials provided with the distribution.
15    
16    - Neither the name of the Xiph.org Foundation nor the names of its
17    contributors may be used to endorse or promote products derived from
18    this software without specific prior written permission.
19    
20    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
24    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #ifdef HAVE_CONFIG_H
34 #include "config.h"
35 #endif
36
37 #include <math.h>
38 #include "modes.h"
39 #include "cwrs.h"
40 #include "arch.h"
41 #include "os_support.h"
42
43 #include "entcode.h"
44 #include "rate.h"
45
46
47 #ifndef STATIC_MODES
48
49 /*Determines if V(N,K) fits in a 32-bit unsigned integer.
50   N and K are themselves limited to 15 bits.*/
51 static int fits_in32(int _n, int _k)
52 {
53    static const celt_int16 maxN[15] = {
54       32767, 32767, 32767, 1476, 283, 109,  60,  40,
55        29,  24,  20,  18,  16,  14,  13};
56    static const celt_int16 maxK[15] = {
57       32767, 32767, 32767, 32767, 1172, 238,  95,  53,
58        36,  27,  22,  18,  16,  15,  13};
59    if (_n>=14)
60    {
61       if (_k>=14)
62          return 0;
63       else
64          return _n <= maxN[_k];
65    } else {
66       return _k <= maxK[_n];
67    }
68 }
69
70 void compute_pulse_cache(CELTMode *m, int LM)
71 {
72    int i;
73    int curr=0;
74    int nbEntries=0;
75    int entryN[100], entryK[100], entryI[100];
76    const celt_int16 *eBands = m->eBands;
77    PulseCache *cache = &m->cache;
78    celt_int16 *cindex;
79    unsigned char *bits;
80
81    cindex = celt_alloc(sizeof(cache->index[0])*m->nbEBands*(LM+2));
82    cache->index = cindex;
83
84    for (i=0;i<=LM+1;i++)
85    {
86       int j;
87       for (j=0;j<m->nbEBands;j++)
88       {
89          int k;
90          int N = (eBands[j+1]-eBands[j])<<i>>1;
91          cindex[i*m->nbEBands+j] = -1;
92          for (k=0;k<=i;k++)
93          {
94             int n;
95             for (n=0;n<m->nbEBands && (k!=i || n<j);n++)
96             {
97                if (N == (eBands[n+1]-eBands[n])<<k>>1)
98                {
99                   cindex[i*m->nbEBands+j] = cindex[k*m->nbEBands+n];
100                   break;
101                }
102             }
103          }
104          if (cache->index[i*m->nbEBands+j] == -1 && N!=0)
105          {
106             int K;
107             entryN[nbEntries] = N;
108             K = 0;
109             while (fits_in32(N,get_pulses(K+1)) && K<MAX_PSEUDO-1)
110                K++;
111             entryK[nbEntries] = K;
112             cindex[i*m->nbEBands+j] = curr;
113             entryI[nbEntries] = curr;
114
115             curr += K+1;
116             nbEntries++;
117          }
118       }
119    }
120    bits = celt_alloc(sizeof(unsigned char)*curr);
121    cache->bits = bits;
122    cache->size = curr;
123    for (i=0;i<nbEntries;i++)
124    {
125       int j;
126       unsigned char *ptr = bits+entryI[i];
127       celt_int16 tmp[MAX_PULSES];
128       get_required_bits(tmp, entryN[i], get_pulses(entryK[i]), BITRES);
129       for (j=1;j<=entryK[i];j++)
130          ptr[j] = tmp[get_pulses(j)]-1;
131       ptr[0] = entryK[i];
132    }
133 }
134
135 #endif /* !STATIC_MODES */
136
137
138
139 static inline void interp_bits2pulses(const CELTMode *m, int start, int end, int *bits1, int *bits2, int total, int *bits, int *ebits, int *fine_priority, int len, int _C, int M)
140 {
141    int psum;
142    int lo, hi;
143    int j;
144    int logM;
145    const int C = CHANNELS(_C);
146    SAVE_STACK;
147
148    logM = log2_frac(M, BITRES);
149    lo = 0;
150    hi = 1<<BITRES;
151    while (hi-lo != 1)
152    {
153       int mid = (lo+hi)>>1;
154       psum = 0;
155       for (j=start;j<end;j++)
156          psum += (((1<<BITRES)-mid)*bits1[j] + mid*bits2[j])>>BITRES;
157       if (psum > (total<<BITRES))
158          hi = mid;
159       else
160          lo = mid;
161    }
162    psum = 0;
163    /*printf ("interp bisection gave %d\n", lo);*/
164    for (j=start;j<end;j++)
165    {
166       bits[j] = (((1<<BITRES)-lo)*bits1[j] + lo*bits2[j])>>BITRES;
167       psum += bits[j];
168    }
169    /* Allocate the remaining bits */
170    {
171       int left, perband;
172       left = (total<<BITRES)-psum;
173       perband = left/(end-start);
174       for (j=start;j<end;j++)
175          bits[j] += perband;
176       left = left-end*perband;
177       for (j=start;j<start+left;j++)
178          bits[j]++;
179    }
180    for (j=start;j<end;j++)
181    {
182       int N0, N, den;
183       int offset;
184       int fine_offset;
185       N0 = m->eBands[j+1]-m->eBands[j];
186       N=M*N0;
187       /* Compensate for the extra DoF in stereo */
188       den=(C*N+ ((C==2 && N>2) ? 1 : 0));
189
190       if (N0==1)
191          fine_offset = 19;
192       else if (N0<=4)
193          fine_offset = 14;
194       else
195          fine_offset = 12;
196
197       /* Offset for the number of fine bits compared to their "fair share" of total/N */
198       offset = N*C*((m->logN[j] + logM - 2*fine_offset)>>1);
199
200       /* Compensate for the prediction gain in stereo */
201       if (C==2)
202          offset -= 1<<BITRES;
203
204       ebits[j] = (bits[j] + offset + (den<<(BITRES-1))) / (den<<BITRES);
205
206       /* If we rounded down, make it a candidate for final fine energy pass */
207       fine_priority[j] = ebits[j]*(den<<BITRES) >= bits[j]+offset;
208
209       /* For N=1, all bits go to fine energy except for a single sign bit */
210       if (N==1)
211          ebits[j] = (bits[j]/C >> BITRES)-1;
212       /* Make sure the first bit is spent on fine energy */
213       if (ebits[j] < 1)
214          ebits[j] = 1;
215
216       /* Make sure not to bust */
217       if (C*ebits[j] > (bits[j]>>BITRES))
218          ebits[j] = bits[j]/C >> BITRES;
219
220       if (ebits[j]>7)
221          ebits[j]=7;
222       if (ebits[j]<0)
223          ebits[j]=0;
224
225       /* The bits used for fine allocation can't be used for pulses */
226       bits[j] -= C*ebits[j]<<BITRES;
227       if (bits[j] < 0)
228          bits[j] = 0;
229    }
230    RESTORE_STACK;
231 }
232
233 void compute_allocation(const CELTMode *m, int start, int end, int *offsets, int total, int *pulses, int *ebits, int *fine_priority, int _C, int M)
234 {
235    int lo, hi, len, j;
236    const int C = CHANNELS(_C);
237    VARDECL(int, bits1);
238    VARDECL(int, bits2);
239    SAVE_STACK;
240    
241    len = m->nbEBands;
242    ALLOC(bits1, len, int);
243    ALLOC(bits2, len, int);
244
245    lo = 0;
246    hi = m->nbAllocVectors - 1;
247    while (hi-lo != 1)
248    {
249       int psum = 0;
250       int mid = (lo+hi) >> 1;
251       for (j=start;j<end;j++)
252       {
253          int N = m->eBands[j+1]-m->eBands[j];
254          bits1[j] = (C*M*N*m->allocVectors[mid*len+j] + offsets[j]);
255          if (bits1[j] < 0)
256             bits1[j] = 0;
257          psum += bits1[j];
258          /*printf ("%d ", bits[j]);*/
259       }
260       /*printf ("\n");*/
261       if (psum > (total<<BITRES))
262          hi = mid;
263       else
264          lo = mid;
265       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
266    }
267    /*printf ("interp between %d and %d\n", lo, hi);*/
268    for (j=start;j<end;j++)
269    {
270       int N = m->eBands[j+1]-m->eBands[j];
271       bits1[j] = C*M*N*m->allocVectors[lo*len+j] + offsets[j];
272       bits2[j] = C*M*N*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    interp_bits2pulses(m, start, end, bits1, bits2, total, pulses, ebits, fine_priority, len, C, M);
279    RESTORE_STACK;
280 }
281