qoffset tuning
[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       N0 = m->eBands[j+1]-m->eBands[j];
185       N=M*N0;
186       /* Compensate for the extra DoF in stereo */
187       den=(C*N+ ((C==2 && N>2) ? 1 : 0));
188
189       /* Offset for the number of fine bits compared to their "fair share" of total/N */
190       offset = N*C*(((m->logN[j] + logM)>>1)-FINE_OFFSET);
191
192       /* N=2 is the only point that doesn't match the curve */
193       if (N==2)
194          offset += N*C<<BITRES>>2;
195
196       /* Changing the offset for allocating the second and third fine energy bit */
197       if (bits[j] + offset < den*2<<BITRES)
198          offset += (m->logN[j] + logM)*N*C>>2;
199       else if (bits[j] + offset < den*3<<BITRES)
200          offset += (m->logN[j] + logM)*N*C>>3;
201
202       ebits[j] = (bits[j] + offset + (den<<(BITRES-1))) / (den<<BITRES);
203
204       /* If we rounded down, make it a candidate for final fine energy pass */
205       fine_priority[j] = ebits[j]*(den<<BITRES) >= bits[j]+offset;
206
207       /* For N=1, all bits go to fine energy except for a single sign bit */
208       if (N==1)
209          ebits[j] = (bits[j]/C >> BITRES)-1;
210       /* Make sure the first bit is spent on fine energy */
211       if (ebits[j] < 1)
212          ebits[j] = 1;
213
214       /* Make sure not to bust */
215       if (C*ebits[j] > (bits[j]>>BITRES))
216          ebits[j] = bits[j]/C >> BITRES;
217
218       if (ebits[j]>7)
219          ebits[j]=7;
220       if (ebits[j]<0)
221          ebits[j]=0;
222
223       /* The bits used for fine allocation can't be used for pulses */
224       bits[j] -= C*ebits[j]<<BITRES;
225       if (bits[j] < 0)
226          bits[j] = 0;
227    }
228    RESTORE_STACK;
229 }
230
231 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)
232 {
233    int lo, hi, len, j;
234    const int C = CHANNELS(_C);
235    VARDECL(int, bits1);
236    VARDECL(int, bits2);
237    SAVE_STACK;
238    
239    len = m->nbEBands;
240    ALLOC(bits1, len, int);
241    ALLOC(bits2, len, int);
242
243    lo = 0;
244    hi = m->nbAllocVectors - 1;
245    while (hi-lo != 1)
246    {
247       int psum = 0;
248       int mid = (lo+hi) >> 1;
249       for (j=start;j<end;j++)
250       {
251          int N = m->eBands[j+1]-m->eBands[j];
252          bits1[j] = (C*M*N*m->allocVectors[mid*len+j] + offsets[j]);
253          if (bits1[j] < 0)
254             bits1[j] = 0;
255          psum += bits1[j];
256          /*printf ("%d ", bits[j]);*/
257       }
258       /*printf ("\n");*/
259       if (psum > (total<<BITRES))
260          hi = mid;
261       else
262          lo = mid;
263       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
264    }
265    /*printf ("interp between %d and %d\n", lo, hi);*/
266    for (j=start;j<end;j++)
267    {
268       int N = m->eBands[j+1]-m->eBands[j];
269       bits1[j] = C*M*N*m->allocVectors[lo*len+j] + offsets[j];
270       bits2[j] = C*M*N*m->allocVectors[hi*len+j] + offsets[j];
271       if (bits1[j] < 0)
272          bits1[j] = 0;
273       if (bits2[j] < 0)
274          bits2[j] = 0;
275    }
276    interp_bits2pulses(m, start, end, bits1, bits2, total, pulses, ebits, fine_priority, len, C, M);
277    RESTORE_STACK;
278 }
279