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