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
79    cache->nbBands = m->nbEBands;
80    cache->index = celt_alloc(sizeof(cache->index[0])*cache->nbBands*(LM+2));
81
82    for (i=0;i<=LM+1;i++)
83    {
84       int j;
85       for (j=0;j<cache->nbBands;j++)
86       {
87          int k;
88          int N = (eBands[j+1]-eBands[j])<<i>>1;
89          cache->index[i*cache->nbBands+j] = -1;
90          for (k=0;k<=i;k++)
91          {
92             int n;
93             for (n=0;n<cache->nbBands && (k!=i || n<j);n++)
94             {
95                if (N == (eBands[n+1]-eBands[n])<<k>>1)
96                {
97                   cache->index[i*cache->nbBands+j] =
98                         cache->index[k*cache->nbBands+n];
99                   break;
100                }
101             }
102          }
103          if (cache->index[i*cache->nbBands+j] == -1)
104          {
105             int K;
106             entryN[nbEntries] = N;
107             K = 0;
108             while (fits_in32(N,get_pulses(K+1)) && K<MAX_PSEUDO-1)
109                K++;
110             entryK[nbEntries] = K;
111             cache->index[i*cache->nbBands+j] = curr;
112             entryI[nbEntries] = curr;
113
114             curr += K+1;
115             nbEntries++;
116          }
117       }
118    }
119    cache->bits = celt_alloc(sizeof(unsigned char)*curr);
120    for (i=0;i<nbEntries;i++)
121    {
122       int j;
123       unsigned char *ptr = cache->bits+entryI[i];
124       celt_int16 tmp[MAX_PULSES];
125       get_required_bits(tmp, entryN[i], get_pulses(entryK[i]), BITRES);
126       for (j=1;j<=entryK[i];j++)
127          ptr[j] = tmp[get_pulses(j)]-1;
128       ptr[0] = entryK[i];
129    }
130 }
131
132 #endif /* !STATIC_MODES */
133
134
135
136 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)
137 {
138    int psum;
139    int lo, hi;
140    int j;
141    int logM;
142    const int C = CHANNELS(_C);
143    SAVE_STACK;
144
145    logM = log2_frac(M, BITRES);
146    lo = 0;
147    hi = 1<<BITRES;
148    while (hi-lo != 1)
149    {
150       int mid = (lo+hi)>>1;
151       psum = 0;
152       for (j=start;j<end;j++)
153          psum += (((1<<BITRES)-mid)*bits1[j] + mid*bits2[j])>>BITRES;
154       if (psum > (total<<BITRES))
155          hi = mid;
156       else
157          lo = mid;
158    }
159    psum = 0;
160    /*printf ("interp bisection gave %d\n", lo);*/
161    for (j=start;j<end;j++)
162    {
163       bits[j] = (((1<<BITRES)-lo)*bits1[j] + lo*bits2[j])>>BITRES;
164       psum += bits[j];
165    }
166    /* Allocate the remaining bits */
167    {
168       int left, perband;
169       left = (total<<BITRES)-psum;
170       perband = left/(end-start);
171       for (j=start;j<end;j++)
172          bits[j] += perband;
173       left = left-end*perband;
174       for (j=start;j<start+left;j++)
175          bits[j]++;
176    }
177    for (j=start;j<end;j++)
178    {
179       int N0, N, den;
180       int offset;
181       int fine_offset;
182       N0 = m->eBands[j+1]-m->eBands[j];
183       N=M*N0;
184       /* Compensate for the extra DoF in stereo */
185       den=(C*N+ ((C==2 && N>2) ? 1 : 0));
186
187       if (N0==1)
188          fine_offset = 19;
189       else if (N0<=4)
190          fine_offset = 14;
191       else
192          fine_offset = 12;
193
194       /* Offset for the number of fine bits compared to their "fair share" of total/N */
195       offset = N*C*((m->logN[j] + logM - 2*fine_offset)>>1);
196
197       /* Compensate for the prediction gain in stereo */
198       if (C==2)
199          offset -= 1<<BITRES;
200
201       ebits[j] = (bits[j] + offset + (den<<(BITRES-1))) / (den<<BITRES);
202
203       /* If we rounded down, make it a candidate for final fine energy pass */
204       fine_priority[j] = ebits[j]*(den<<BITRES) >= bits[j]+offset;
205
206       /* For N=1, all bits go to fine energy except for a single sign bit */
207       if (N==1)
208          ebits[j] = (bits[j]/C >> BITRES)-1;
209       /* Make sure the first bit is spent on fine energy */
210       if (ebits[j] < 1)
211          ebits[j] = 1;
212
213       /* Make sure not to bust */
214       if (C*ebits[j] > (bits[j]>>BITRES))
215          ebits[j] = bits[j]/C >> BITRES;
216
217       if (ebits[j]>7)
218          ebits[j]=7;
219       if (ebits[j]<0)
220          ebits[j]=0;
221
222       /* The bits used for fine allocation can't be used for pulses */
223       bits[j] -= C*ebits[j]<<BITRES;
224       if (bits[j] < 0)
225          bits[j] = 0;
226    }
227    RESTORE_STACK;
228 }
229
230 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)
231 {
232    int lo, hi, len, j;
233    const int C = CHANNELS(_C);
234    VARDECL(int, bits1);
235    VARDECL(int, bits2);
236    SAVE_STACK;
237    
238    len = m->nbEBands;
239    ALLOC(bits1, len, int);
240    ALLOC(bits2, len, int);
241
242    lo = 0;
243    hi = m->nbAllocVectors - 1;
244    while (hi-lo != 1)
245    {
246       int psum = 0;
247       int mid = (lo+hi) >> 1;
248       for (j=start;j<end;j++)
249       {
250          int N = m->eBands[j+1]-m->eBands[j];
251          bits1[j] = (C*M*N*m->allocVectors[mid*len+j] + offsets[j]);
252          if (bits1[j] < 0)
253             bits1[j] = 0;
254          psum += bits1[j];
255          /*printf ("%d ", bits[j]);*/
256       }
257       /*printf ("\n");*/
258       if (psum > (total<<BITRES))
259          hi = mid;
260       else
261          lo = mid;
262       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
263    }
264    /*printf ("interp between %d and %d\n", lo, hi);*/
265    for (j=start;j<end;j++)
266    {
267       int N = m->eBands[j+1]-m->eBands[j];
268       bits1[j] = C*M*N*m->allocVectors[lo*len+j] + offsets[j];
269       bits2[j] = C*M*N*m->allocVectors[hi*len+j] + offsets[j];
270       if (bits1[j] < 0)
271          bits1[j] = 0;
272       if (bits2[j] < 0)
273          bits2[j] = 0;
274    }
275    interp_bits2pulses(m, start, end, bits1, bits2, total, pulses, ebits, fine_priority, len, C, M);
276    RESTORE_STACK;
277 }
278