2c0af2299617a7c26e3d056b45adf7d9f6678019
[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 C, 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 = C*M*(eBands[i+1]-eBands[i]);
64       if (N == prevN && M*eBands[i] < m->pitchEnd)
65       {
66          bits[i] = bits[i-1];
67       } else {
68          bits[i] = celt_alloc(MAX_PSEUDO*sizeof(celt_int16));
69          if (bits[i]!=NULL) {
70             int j;
71             celt_int16 tmp[MAX_PULSES];
72             get_required_bits(tmp, N, MAX_PULSES, BITRES);
73             for (j=0;j<MAX_PSEUDO;j++)
74                bits[i][j] = tmp[get_pulses(j)];
75          } else {
76             error=1;
77          }
78          prevN = N;
79       }
80    }
81    if (error)
82    {
83       const celt_int16 *prevPtr = NULL;
84       if (bits!=NULL)
85       {
86          for (i=0;i<m->nbEBands;i++)
87          {
88             if (bits[i] != prevPtr)
89             {
90                prevPtr = bits[i];
91                celt_free((int*)bits[i]);
92             }
93          }
94       free(bits);
95       bits=NULL;
96       }   
97    }
98    return bits;
99 }
100
101 #endif /* !STATIC_MODES */
102
103
104
105 static inline void interp_bits2pulses(const CELTMode *m, int start, int *bits1, int *bits2, int total, int *bits, int *ebits, int *fine_priority, int len, int _C, int M)
106 {
107    int psum;
108    int lo, hi;
109    int j;
110    int logM;
111    const int C = CHANNELS(_C);
112    SAVE_STACK;
113
114    logM = log2_frac(M, BITRES);
115    lo = 0;
116    hi = 1<<BITRES;
117    while (hi-lo != 1)
118    {
119       int mid = (lo+hi)>>1;
120       psum = 0;
121       for (j=start;j<len;j++)
122          psum += (((1<<BITRES)-mid)*bits1[j] + mid*bits2[j])>>BITRES;
123       if (psum > (total<<BITRES))
124          hi = mid;
125       else
126          lo = mid;
127    }
128    psum = 0;
129    /*printf ("interp bisection gave %d\n", lo);*/
130    for (j=start;j<len;j++)
131    {
132       bits[j] = (((1<<BITRES)-lo)*bits1[j] + lo*bits2[j])>>BITRES;
133       psum += bits[j];
134    }
135    /* Allocate the remaining bits */
136    {
137       int left, perband;
138       left = (total<<BITRES)-psum;
139       perband = left/(len-start);
140       for (j=start;j<len;j++)
141          bits[j] += perband;
142       left = left-len*perband;
143       for (j=start;j<start+left;j++)
144          bits[j]++;
145    }
146    for (j=start;j<len;j++)
147    {
148       int N, d;
149       int offset;
150
151       N=M*(m->eBands[j+1]-m->eBands[j]);
152       /* Compensate for the extra DoF in stereo */
153       d=(C*N+ ((C==2 && N>2) ? 1 : 0))<<BITRES; 
154       offset = FINE_OFFSET - m->logN[j] - logM;
155       /* Offset for the number of fine bits compared to their "fair share" of total/N */
156       offset = bits[j]-offset*N*C;
157       /* Compensate for the prediction gain in stereo */
158       if (C==2)
159          offset -= 1<<BITRES;
160       if (offset < 0)
161          offset = 0;
162       ebits[j] = (2*offset+d)/(2*d);
163       fine_priority[j] = ebits[j]*d >= offset;
164
165       /* Make sure not to bust */
166       if (C*ebits[j] > (bits[j]>>BITRES))
167          ebits[j] = bits[j]/C >> BITRES;
168
169       if (ebits[j]>7)
170          ebits[j]=7;
171       /* The bits used for fine allocation can't be used for pulses */
172       bits[j] -= C*ebits[j]<<BITRES;
173       if (bits[j] < 0)
174          bits[j] = 0;
175    }
176    RESTORE_STACK;
177 }
178
179 void compute_allocation(const CELTMode *m, int start, int *offsets, int total, int *pulses, int *ebits, int *fine_priority, int _C, int M)
180 {
181    int lo, hi, len, j;
182    const int C = CHANNELS(_C);
183    VARDECL(int, bits1);
184    VARDECL(int, bits2);
185    SAVE_STACK;
186    
187    len = m->nbEBands;
188    ALLOC(bits1, len, int);
189    ALLOC(bits2, len, int);
190
191    lo = 0;
192    hi = m->nbAllocVectors - 1;
193    while (hi-lo != 1)
194    {
195       int psum = 0;
196       int mid = (lo+hi) >> 1;
197       for (j=start;j<len;j++)
198       {
199          bits1[j] = (C*M*m->allocVectors[mid*len+j] + offsets[j]);
200          if (bits1[j] < 0)
201             bits1[j] = 0;
202          psum += bits1[j];
203          /*printf ("%d ", bits[j]);*/
204       }
205       /*printf ("\n");*/
206       if (psum > (total<<BITRES))
207          hi = mid;
208       else
209          lo = mid;
210       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
211    }
212    /*printf ("interp between %d and %d\n", lo, hi);*/
213    for (j=start;j<len;j++)
214    {
215       bits1[j] = C*M*m->allocVectors[lo*len+j] + offsets[j];
216       bits2[j] = C*M*m->allocVectors[hi*len+j] + offsets[j];
217       if (bits1[j] < 0)
218          bits1[j] = 0;
219       if (bits2[j] < 0)
220          bits2[j] = 0;
221    }
222    interp_bits2pulses(m, start, bits1, bits2, total, pulses, ebits, fine_priority, len, C, M);
223    RESTORE_STACK;
224 }
225