Fixes some minor issues found by scan build
[opus.git] / celt / bands.c
1 /* Copyright (c) 2007-2008 CSIRO
2    Copyright (c) 2007-2009 Xiph.Org Foundation
3    Copyright (c) 2008-2009 Gregory Maxwell
4    Written by Jean-Marc Valin and Gregory Maxwell */
5 /*
6    Redistribution and use in source and binary forms, with or without
7    modification, are permitted provided that the following conditions
8    are met:
9
10    - Redistributions of source code must retain the above copyright
11    notice, this list of conditions and the following disclaimer.
12
13    - Redistributions in binary form must reproduce the above copyright
14    notice, this list of conditions and the following disclaimer in the
15    documentation and/or other materials provided with the distribution.
16
17    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
21    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
25    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
26    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 #ifdef HAVE_CONFIG_H
31 #include "config.h"
32 #endif
33
34 #include <math.h>
35 #include "bands.h"
36 #include "modes.h"
37 #include "vq.h"
38 #include "cwrs.h"
39 #include "stack_alloc.h"
40 #include "os_support.h"
41 #include "mathops.h"
42 #include "rate.h"
43 #include "quant_bands.h"
44 #include "pitch.h"
45
46 int hysteresis_decision(opus_val16 val, const opus_val16 *thresholds, const opus_val16 *hysteresis, int N, int prev)
47 {
48    int i;
49    for (i=0;i<N;i++)
50    {
51       if (val < thresholds[i])
52          break;
53    }
54    if (i>prev && val < thresholds[prev]+hysteresis[prev])
55       i=prev;
56    if (i<prev && val > thresholds[prev-1]-hysteresis[prev-1])
57       i=prev;
58    return i;
59 }
60
61 opus_uint32 celt_lcg_rand(opus_uint32 seed)
62 {
63    return 1664525 * seed + 1013904223;
64 }
65
66 /* This is a cos() approximation designed to be bit-exact on any platform. Bit exactness
67    with this approximation is important because it has an impact on the bit allocation */
68 static opus_int16 bitexact_cos(opus_int16 x)
69 {
70    opus_int32 tmp;
71    opus_int16 x2;
72    tmp = (4096+((opus_int32)(x)*(x)))>>13;
73    celt_assert(tmp<=32767);
74    x2 = tmp;
75    x2 = (32767-x2) + FRAC_MUL16(x2, (-7651 + FRAC_MUL16(x2, (8277 + FRAC_MUL16(-626, x2)))));
76    celt_assert(x2<=32766);
77    return 1+x2;
78 }
79
80 static int bitexact_log2tan(int isin,int icos)
81 {
82    int lc;
83    int ls;
84    lc=EC_ILOG(icos);
85    ls=EC_ILOG(isin);
86    icos<<=15-lc;
87    isin<<=15-ls;
88    return (ls-lc)*(1<<11)
89          +FRAC_MUL16(isin, FRAC_MUL16(isin, -2597) + 7932)
90          -FRAC_MUL16(icos, FRAC_MUL16(icos, -2597) + 7932);
91 }
92
93 #ifdef FIXED_POINT
94 /* Compute the amplitude (sqrt energy) in each of the bands */
95 void compute_band_energies(const CELTMode *m, const celt_sig *X, celt_ener *bandE, int end, int C, int M)
96 {
97    int i, c, N;
98    const opus_int16 *eBands = m->eBands;
99    N = M*m->shortMdctSize;
100    c=0; do {
101       for (i=0;i<end;i++)
102       {
103          int j;
104          opus_val32 maxval=0;
105          opus_val32 sum = 0;
106
107          j=M*eBands[i]; do {
108             maxval = MAX32(maxval, X[j+c*N]);
109             maxval = MAX32(maxval, -X[j+c*N]);
110          } while (++j<M*eBands[i+1]);
111
112          if (maxval > 0)
113          {
114             int shift = celt_ilog2(maxval)-10;
115             j=M*eBands[i]; do {
116                sum = MAC16_16(sum, EXTRACT16(VSHR32(X[j+c*N],shift)),
117                                    EXTRACT16(VSHR32(X[j+c*N],shift)));
118             } while (++j<M*eBands[i+1]);
119             /* We're adding one here to ensure the normalized band isn't larger than unity norm */
120             bandE[i+c*m->nbEBands] = EPSILON+VSHR32(EXTEND32(celt_sqrt(sum)),-shift);
121          } else {
122             bandE[i+c*m->nbEBands] = EPSILON;
123          }
124          /*printf ("%f ", bandE[i+c*m->nbEBands]);*/
125       }
126    } while (++c<C);
127    /*printf ("\n");*/
128 }
129
130 /* Normalise each band such that the energy is one. */
131 void normalise_bands(const CELTMode *m, const celt_sig * OPUS_RESTRICT freq, celt_norm * OPUS_RESTRICT X, const celt_ener *bandE, int end, int C, int M)
132 {
133    int i, c, N;
134    const opus_int16 *eBands = m->eBands;
135    N = M*m->shortMdctSize;
136    c=0; do {
137       i=0; do {
138          opus_val16 g;
139          int j,shift;
140          opus_val16 E;
141          shift = celt_zlog2(bandE[i+c*m->nbEBands])-13;
142          E = VSHR32(bandE[i+c*m->nbEBands], shift);
143          g = EXTRACT16(celt_rcp(SHL32(E,3)));
144          j=M*eBands[i]; do {
145             X[j+c*N] = MULT16_16_Q15(VSHR32(freq[j+c*N],shift-1),g);
146          } while (++j<M*eBands[i+1]);
147       } while (++i<end);
148    } while (++c<C);
149 }
150
151 #else /* FIXED_POINT */
152 /* Compute the amplitude (sqrt energy) in each of the bands */
153 void compute_band_energies(const CELTMode *m, const celt_sig *X, celt_ener *bandE, int end, int C, int M)
154 {
155    int i, c, N;
156    const opus_int16 *eBands = m->eBands;
157    N = M*m->shortMdctSize;
158    c=0; do {
159       for (i=0;i<end;i++)
160       {
161          int j;
162          opus_val32 sum = 1e-27f;
163          for (j=M*eBands[i];j<M*eBands[i+1];j++)
164             sum += X[j+c*N]*X[j+c*N];
165          bandE[i+c*m->nbEBands] = celt_sqrt(sum);
166          /*printf ("%f ", bandE[i+c*m->nbEBands]);*/
167       }
168    } while (++c<C);
169    /*printf ("\n");*/
170 }
171
172 /* Normalise each band such that the energy is one. */
173 void normalise_bands(const CELTMode *m, const celt_sig * OPUS_RESTRICT freq, celt_norm * OPUS_RESTRICT X, const celt_ener *bandE, int end, int C, int M)
174 {
175    int i, c, N;
176    const opus_int16 *eBands = m->eBands;
177    N = M*m->shortMdctSize;
178    c=0; do {
179       for (i=0;i<end;i++)
180       {
181          int j;
182          opus_val16 g = 1.f/(1e-27f+bandE[i+c*m->nbEBands]);
183          for (j=M*eBands[i];j<M*eBands[i+1];j++)
184             X[j+c*N] = freq[j+c*N]*g;
185       }
186    } while (++c<C);
187 }
188
189 #endif /* FIXED_POINT */
190
191 /* De-normalise the energy to produce the synthesis from the unit-energy bands */
192 void denormalise_bands(const CELTMode *m, const celt_norm * OPUS_RESTRICT X,
193       celt_sig * OPUS_RESTRICT freq, const opus_val16 *bandLogE, int start, int end, int C, int M)
194 {
195    int i, c, N;
196    const opus_int16 *eBands = m->eBands;
197    N = M*m->shortMdctSize;
198    celt_assert2(C<=2, "denormalise_bands() not implemented for >2 channels");
199    c=0; do {
200       celt_sig * OPUS_RESTRICT f;
201       const celt_norm * OPUS_RESTRICT x;
202       f = freq+c*N;
203       x = X+c*N+M*eBands[start];
204       for (i=0;i<M*eBands[start];i++)
205          *f++ = 0;
206       for (i=start;i<end;i++)
207       {
208          int j, band_end;
209          opus_val16 g;
210          opus_val16 lg;
211 #ifdef FIXED_POINT
212          int shift;
213 #endif
214          j=M*eBands[i];
215          band_end = M*eBands[i+1];
216          lg = ADD16(bandLogE[i+c*m->nbEBands], SHL16((opus_val16)eMeans[i],6));
217 #ifdef FIXED_POINT
218          /* Handle the integer part of the log energy */
219          shift = 16-(lg>>DB_SHIFT);
220          if (shift>31)
221          {
222             shift=0;
223             g=0;
224          } else {
225             /* Handle the fractional part. */
226             g = celt_exp2_frac(lg&((1<<DB_SHIFT)-1));
227          }
228 #else
229          g = celt_exp2(lg);
230 #endif
231          do {
232             *f++ = SHR32(MULT16_16(*x++, g), shift);
233          } while (++j<band_end);
234       }
235       celt_assert(start <= end);
236       for (i=M*eBands[end];i<N;i++)
237          *f++ = 0;
238    } while (++c<C);
239 }
240
241 /* This prevents energy collapse for transients with multiple short MDCTs */
242 void anti_collapse(const CELTMode *m, celt_norm *X_, unsigned char *collapse_masks, int LM, int C, int size,
243       int start, int end, opus_val16 *logE, opus_val16 *prev1logE,
244       opus_val16 *prev2logE, int *pulses, opus_uint32 seed)
245 {
246    int c, i, j, k;
247    for (i=start;i<end;i++)
248    {
249       int N0;
250       opus_val16 thresh, sqrt_1;
251       int depth;
252 #ifdef FIXED_POINT
253       int shift;
254       opus_val32 thresh32;
255 #endif
256
257       N0 = m->eBands[i+1]-m->eBands[i];
258       /* depth in 1/8 bits */
259       depth = (1+pulses[i])/((m->eBands[i+1]-m->eBands[i])<<LM);
260
261 #ifdef FIXED_POINT
262       thresh32 = SHR32(celt_exp2(-SHL16(depth, 10-BITRES)),1);
263       thresh = MULT16_32_Q15(QCONST16(0.5f, 15), MIN32(32767,thresh32));
264       {
265          opus_val32 t;
266          t = N0<<LM;
267          shift = celt_ilog2(t)>>1;
268          t = SHL32(t, (7-shift)<<1);
269          sqrt_1 = celt_rsqrt_norm(t);
270       }
271 #else
272       thresh = .5f*celt_exp2(-.125f*depth);
273       sqrt_1 = celt_rsqrt(N0<<LM);
274 #endif
275
276       c=0; do
277       {
278          celt_norm *X;
279          opus_val16 prev1;
280          opus_val16 prev2;
281          opus_val32 Ediff;
282          opus_val16 r;
283          int renormalize=0;
284          prev1 = prev1logE[c*m->nbEBands+i];
285          prev2 = prev2logE[c*m->nbEBands+i];
286          if (C==1)
287          {
288             prev1 = MAX16(prev1,prev1logE[m->nbEBands+i]);
289             prev2 = MAX16(prev2,prev2logE[m->nbEBands+i]);
290          }
291          Ediff = EXTEND32(logE[c*m->nbEBands+i])-EXTEND32(MIN16(prev1,prev2));
292          Ediff = MAX32(0, Ediff);
293
294 #ifdef FIXED_POINT
295          if (Ediff < 16384)
296          {
297             opus_val32 r32 = SHR32(celt_exp2(-EXTRACT16(Ediff)),1);
298             r = 2*MIN16(16383,r32);
299          } else {
300             r = 0;
301          }
302          if (LM==3)
303             r = MULT16_16_Q14(23170, MIN32(23169, r));
304          r = SHR16(MIN16(thresh, r),1);
305          r = SHR32(MULT16_16_Q15(sqrt_1, r),shift);
306 #else
307          /* r needs to be multiplied by 2 or 2*sqrt(2) depending on LM because
308             short blocks don't have the same energy as long */
309          r = 2.f*celt_exp2(-Ediff);
310          if (LM==3)
311             r *= 1.41421356f;
312          r = MIN16(thresh, r);
313          r = r*sqrt_1;
314 #endif
315          X = X_+c*size+(m->eBands[i]<<LM);
316          for (k=0;k<1<<LM;k++)
317          {
318             /* Detect collapse */
319             if (!(collapse_masks[i*C+c]&1<<k))
320             {
321                /* Fill with noise */
322                for (j=0;j<N0;j++)
323                {
324                   seed = celt_lcg_rand(seed);
325                   X[(j<<LM)+k] = (seed&0x8000 ? r : -r);
326                }
327                renormalize = 1;
328             }
329          }
330          /* We just added some energy, so we need to renormalise */
331          if (renormalize)
332             renormalise_vector(X, N0<<LM, Q15ONE);
333       } while (++c<C);
334    }
335 }
336
337 static void intensity_stereo(const CELTMode *m, celt_norm *X, celt_norm *Y, const celt_ener *bandE, int bandID, int N)
338 {
339    int i = bandID;
340    int j;
341    opus_val16 a1, a2;
342    opus_val16 left, right;
343    opus_val16 norm;
344 #ifdef FIXED_POINT
345    int shift = celt_zlog2(MAX32(bandE[i], bandE[i+m->nbEBands]))-13;
346 #endif
347    left = VSHR32(bandE[i],shift);
348    right = VSHR32(bandE[i+m->nbEBands],shift);
349    norm = EPSILON + celt_sqrt(EPSILON+MULT16_16(left,left)+MULT16_16(right,right));
350    a1 = DIV32_16(SHL32(EXTEND32(left),14),norm);
351    a2 = DIV32_16(SHL32(EXTEND32(right),14),norm);
352    for (j=0;j<N;j++)
353    {
354       celt_norm r, l;
355       l = X[j];
356       r = Y[j];
357       X[j] = MULT16_16_Q14(a1,l) + MULT16_16_Q14(a2,r);
358       /* Side is not encoded, no need to calculate */
359    }
360 }
361
362 static void stereo_split(celt_norm *X, celt_norm *Y, int N)
363 {
364    int j;
365    for (j=0;j<N;j++)
366    {
367       celt_norm r, l;
368       l = MULT16_16_Q15(QCONST16(.70710678f,15), X[j]);
369       r = MULT16_16_Q15(QCONST16(.70710678f,15), Y[j]);
370       X[j] = l+r;
371       Y[j] = r-l;
372    }
373 }
374
375 static void stereo_merge(celt_norm *X, celt_norm *Y, opus_val16 mid, int N)
376 {
377    int j;
378    opus_val32 xp=0, side=0;
379    opus_val32 El, Er;
380    opus_val16 mid2;
381 #ifdef FIXED_POINT
382    int kl, kr;
383 #endif
384    opus_val32 t, lgain, rgain;
385
386    /* Compute the norm of X+Y and X-Y as |X|^2 + |Y|^2 +/- sum(xy) */
387    dual_inner_prod(Y, X, Y, N, &xp, &side);
388    /* Compensating for the mid normalization */
389    xp = MULT16_32_Q15(mid, xp);
390    /* mid and side are in Q15, not Q14 like X and Y */
391    mid2 = SHR32(mid, 1);
392    El = MULT16_16(mid2, mid2) + side - 2*xp;
393    Er = MULT16_16(mid2, mid2) + side + 2*xp;
394    if (Er < QCONST32(6e-4f, 28) || El < QCONST32(6e-4f, 28))
395    {
396       for (j=0;j<N;j++)
397          Y[j] = X[j];
398       return;
399    }
400
401 #ifdef FIXED_POINT
402    kl = celt_ilog2(El)>>1;
403    kr = celt_ilog2(Er)>>1;
404 #endif
405    t = VSHR32(El, (kl-7)<<1);
406    lgain = celt_rsqrt_norm(t);
407    t = VSHR32(Er, (kr-7)<<1);
408    rgain = celt_rsqrt_norm(t);
409
410 #ifdef FIXED_POINT
411    if (kl < 7)
412       kl = 7;
413    if (kr < 7)
414       kr = 7;
415 #endif
416
417    for (j=0;j<N;j++)
418    {
419       celt_norm r, l;
420       /* Apply mid scaling (side is already scaled) */
421       l = MULT16_16_Q15(mid, X[j]);
422       r = Y[j];
423       X[j] = EXTRACT16(PSHR32(MULT16_16(lgain, SUB16(l,r)), kl+1));
424       Y[j] = EXTRACT16(PSHR32(MULT16_16(rgain, ADD16(l,r)), kr+1));
425    }
426 }
427
428 /* Decide whether we should spread the pulses in the current frame */
429 int spreading_decision(const CELTMode *m, celt_norm *X, int *average,
430       int last_decision, int *hf_average, int *tapset_decision, int update_hf,
431       int end, int C, int M)
432 {
433    int i, c, N0;
434    int sum = 0, nbBands=0;
435    const opus_int16 * OPUS_RESTRICT eBands = m->eBands;
436    int decision;
437    int hf_sum=0;
438
439    celt_assert(end>0);
440
441    N0 = M*m->shortMdctSize;
442
443    if (M*(eBands[end]-eBands[end-1]) <= 8)
444       return SPREAD_NONE;
445    c=0; do {
446       for (i=0;i<end;i++)
447       {
448          int j, N, tmp=0;
449          int tcount[3] = {0,0,0};
450          celt_norm * OPUS_RESTRICT x = X+M*eBands[i]+c*N0;
451          N = M*(eBands[i+1]-eBands[i]);
452          if (N<=8)
453             continue;
454          /* Compute rough CDF of |x[j]| */
455          for (j=0;j<N;j++)
456          {
457             opus_val32 x2N; /* Q13 */
458
459             x2N = MULT16_16(MULT16_16_Q15(x[j], x[j]), N);
460             if (x2N < QCONST16(0.25f,13))
461                tcount[0]++;
462             if (x2N < QCONST16(0.0625f,13))
463                tcount[1]++;
464             if (x2N < QCONST16(0.015625f,13))
465                tcount[2]++;
466          }
467
468          /* Only include four last bands (8 kHz and up) */
469          if (i>m->nbEBands-4)
470             hf_sum += 32*(tcount[1]+tcount[0])/N;
471          tmp = (2*tcount[2] >= N) + (2*tcount[1] >= N) + (2*tcount[0] >= N);
472          sum += tmp*256;
473          nbBands++;
474       }
475    } while (++c<C);
476
477    if (update_hf)
478    {
479       if (hf_sum)
480          hf_sum /= C*(4-m->nbEBands+end);
481       *hf_average = (*hf_average+hf_sum)>>1;
482       hf_sum = *hf_average;
483       if (*tapset_decision==2)
484          hf_sum += 4;
485       else if (*tapset_decision==0)
486          hf_sum -= 4;
487       if (hf_sum > 22)
488          *tapset_decision=2;
489       else if (hf_sum > 18)
490          *tapset_decision=1;
491       else
492          *tapset_decision=0;
493    }
494    /*printf("%d %d %d\n", hf_sum, *hf_average, *tapset_decision);*/
495    celt_assert(nbBands>0); /* end has to be non-zero */
496    sum /= nbBands;
497    /* Recursive averaging */
498    sum = (sum+*average)>>1;
499    *average = sum;
500    /* Hysteresis */
501    sum = (3*sum + (((3-last_decision)<<7) + 64) + 2)>>2;
502    if (sum < 80)
503    {
504       decision = SPREAD_AGGRESSIVE;
505    } else if (sum < 256)
506    {
507       decision = SPREAD_NORMAL;
508    } else if (sum < 384)
509    {
510       decision = SPREAD_LIGHT;
511    } else {
512       decision = SPREAD_NONE;
513    }
514 #ifdef FUZZING
515    decision = rand()&0x3;
516    *tapset_decision=rand()%3;
517 #endif
518    return decision;
519 }
520
521 /* Indexing table for converting from natural Hadamard to ordery Hadamard
522    This is essentially a bit-reversed Gray, on top of which we've added
523    an inversion of the order because we want the DC at the end rather than
524    the beginning. The lines are for N=2, 4, 8, 16 */
525 static const int ordery_table[] = {
526        1,  0,
527        3,  0,  2,  1,
528        7,  0,  4,  3,  6,  1,  5,  2,
529       15,  0,  8,  7, 12,  3, 11,  4, 14,  1,  9,  6, 13,  2, 10,  5,
530 };
531
532 static void deinterleave_hadamard(celt_norm *X, int N0, int stride, int hadamard)
533 {
534    int i,j;
535    VARDECL(celt_norm, tmp);
536    int N;
537    SAVE_STACK;
538    N = N0*stride;
539    ALLOC(tmp, N, celt_norm);
540    celt_assert(stride>0);
541    if (hadamard)
542    {
543       const int *ordery = ordery_table+stride-2;
544       for (i=0;i<stride;i++)
545       {
546          for (j=0;j<N0;j++)
547             tmp[ordery[i]*N0+j] = X[j*stride+i];
548       }
549    } else {
550       for (i=0;i<stride;i++)
551          for (j=0;j<N0;j++)
552             tmp[i*N0+j] = X[j*stride+i];
553    }
554    for (j=0;j<N;j++)
555       X[j] = tmp[j];
556    RESTORE_STACK;
557 }
558
559 static void interleave_hadamard(celt_norm *X, int N0, int stride, int hadamard)
560 {
561    int i,j;
562    VARDECL(celt_norm, tmp);
563    int N;
564    SAVE_STACK;
565    N = N0*stride;
566    ALLOC(tmp, N, celt_norm);
567    if (hadamard)
568    {
569       const int *ordery = ordery_table+stride-2;
570       for (i=0;i<stride;i++)
571          for (j=0;j<N0;j++)
572             tmp[j*stride+i] = X[ordery[i]*N0+j];
573    } else {
574       for (i=0;i<stride;i++)
575          for (j=0;j<N0;j++)
576             tmp[j*stride+i] = X[i*N0+j];
577    }
578    for (j=0;j<N;j++)
579       X[j] = tmp[j];
580    RESTORE_STACK;
581 }
582
583 void haar1(celt_norm *X, int N0, int stride)
584 {
585    int i, j;
586    N0 >>= 1;
587    for (i=0;i<stride;i++)
588       for (j=0;j<N0;j++)
589       {
590          celt_norm tmp1, tmp2;
591          tmp1 = MULT16_16_Q15(QCONST16(.70710678f,15), X[stride*2*j+i]);
592          tmp2 = MULT16_16_Q15(QCONST16(.70710678f,15), X[stride*(2*j+1)+i]);
593          X[stride*2*j+i] = tmp1 + tmp2;
594          X[stride*(2*j+1)+i] = tmp1 - tmp2;
595       }
596 }
597
598 static int compute_qn(int N, int b, int offset, int pulse_cap, int stereo)
599 {
600    static const opus_int16 exp2_table8[8] =
601       {16384, 17866, 19483, 21247, 23170, 25267, 27554, 30048};
602    int qn, qb;
603    int N2 = 2*N-1;
604    if (stereo && N==2)
605       N2--;
606    /* The upper limit ensures that in a stereo split with itheta==16384, we'll
607        always have enough bits left over to code at least one pulse in the
608        side; otherwise it would collapse, since it doesn't get folded. */
609    qb = IMIN(b-pulse_cap-(4<<BITRES), (b+N2*offset)/N2);
610
611    qb = IMIN(8<<BITRES, qb);
612
613    if (qb<(1<<BITRES>>1)) {
614       qn = 1;
615    } else {
616       qn = exp2_table8[qb&0x7]>>(14-(qb>>BITRES));
617       qn = (qn+1)>>1<<1;
618    }
619    celt_assert(qn <= 256);
620    return qn;
621 }
622
623 struct band_ctx {
624    int encode;
625    const CELTMode *m;
626    int i;
627    int intensity;
628    int spread;
629    int tf_change;
630    ec_ctx *ec;
631    opus_int32 remaining_bits;
632    const celt_ener *bandE;
633    opus_uint32 seed;
634 };
635
636 struct split_ctx {
637    int inv;
638    int imid;
639    int iside;
640    int delta;
641    int itheta;
642    int qalloc;
643 };
644
645 static void compute_theta(struct band_ctx *ctx, struct split_ctx *sctx,
646       celt_norm *X, celt_norm *Y, int N, int *b, int B, int B0,
647       int LM,
648       int stereo, int *fill)
649 {
650    int qn;
651    int itheta=0;
652    int delta;
653    int imid, iside;
654    int qalloc;
655    int pulse_cap;
656    int offset;
657    opus_int32 tell;
658    int inv=0;
659    int encode;
660    const CELTMode *m;
661    int i;
662    int intensity;
663    ec_ctx *ec;
664    const celt_ener *bandE;
665
666    encode = ctx->encode;
667    m = ctx->m;
668    i = ctx->i;
669    intensity = ctx->intensity;
670    ec = ctx->ec;
671    bandE = ctx->bandE;
672
673    /* Decide on the resolution to give to the split parameter theta */
674    pulse_cap = m->logN[i]+LM*(1<<BITRES);
675    offset = (pulse_cap>>1) - (stereo&&N==2 ? QTHETA_OFFSET_TWOPHASE : QTHETA_OFFSET);
676    qn = compute_qn(N, *b, offset, pulse_cap, stereo);
677    if (stereo && i>=intensity)
678       qn = 1;
679    if (encode)
680    {
681       /* theta is the atan() of the ratio between the (normalized)
682          side and mid. With just that parameter, we can re-scale both
683          mid and side because we know that 1) they have unit norm and
684          2) they are orthogonal. */
685       itheta = stereo_itheta(X, Y, stereo, N);
686    }
687    tell = ec_tell_frac(ec);
688    if (qn!=1)
689    {
690       if (encode)
691          itheta = (itheta*qn+8192)>>14;
692
693       /* Entropy coding of the angle. We use a uniform pdf for the
694          time split, a step for stereo, and a triangular one for the rest. */
695       if (stereo && N>2)
696       {
697          int p0 = 3;
698          int x = itheta;
699          int x0 = qn/2;
700          int ft = p0*(x0+1) + x0;
701          /* Use a probability of p0 up to itheta=8192 and then use 1 after */
702          if (encode)
703          {
704             ec_encode(ec,x<=x0?p0*x:(x-1-x0)+(x0+1)*p0,x<=x0?p0*(x+1):(x-x0)+(x0+1)*p0,ft);
705          } else {
706             int fs;
707             fs=ec_decode(ec,ft);
708             if (fs<(x0+1)*p0)
709                x=fs/p0;
710             else
711                x=x0+1+(fs-(x0+1)*p0);
712             ec_dec_update(ec,x<=x0?p0*x:(x-1-x0)+(x0+1)*p0,x<=x0?p0*(x+1):(x-x0)+(x0+1)*p0,ft);
713             itheta = x;
714          }
715       } else if (B0>1 || stereo) {
716          /* Uniform pdf */
717          if (encode)
718             ec_enc_uint(ec, itheta, qn+1);
719          else
720             itheta = ec_dec_uint(ec, qn+1);
721       } else {
722          int fs=1, ft;
723          ft = ((qn>>1)+1)*((qn>>1)+1);
724          if (encode)
725          {
726             int fl;
727
728             fs = itheta <= (qn>>1) ? itheta + 1 : qn + 1 - itheta;
729             fl = itheta <= (qn>>1) ? itheta*(itheta + 1)>>1 :
730              ft - ((qn + 1 - itheta)*(qn + 2 - itheta)>>1);
731
732             ec_encode(ec, fl, fl+fs, ft);
733          } else {
734             /* Triangular pdf */
735             int fl=0;
736             int fm;
737             fm = ec_decode(ec, ft);
738
739             if (fm < ((qn>>1)*((qn>>1) + 1)>>1))
740             {
741                itheta = (isqrt32(8*(opus_uint32)fm + 1) - 1)>>1;
742                fs = itheta + 1;
743                fl = itheta*(itheta + 1)>>1;
744             }
745             else
746             {
747                itheta = (2*(qn + 1)
748                 - isqrt32(8*(opus_uint32)(ft - fm - 1) + 1))>>1;
749                fs = qn + 1 - itheta;
750                fl = ft - ((qn + 1 - itheta)*(qn + 2 - itheta)>>1);
751             }
752
753             ec_dec_update(ec, fl, fl+fs, ft);
754          }
755       }
756       itheta = (opus_int32)itheta*16384/qn;
757       if (encode && stereo)
758       {
759          if (itheta==0)
760             intensity_stereo(m, X, Y, bandE, i, N);
761          else
762             stereo_split(X, Y, N);
763       }
764       /* NOTE: Renormalising X and Y *may* help fixed-point a bit at very high rate.
765                Let's do that at higher complexity */
766    } else if (stereo) {
767       if (encode)
768       {
769          inv = itheta > 8192;
770          if (inv)
771          {
772             int j;
773             for (j=0;j<N;j++)
774                Y[j] = -Y[j];
775          }
776          intensity_stereo(m, X, Y, bandE, i, N);
777       }
778       if (*b>2<<BITRES && ctx->remaining_bits > 2<<BITRES)
779       {
780          if (encode)
781             ec_enc_bit_logp(ec, inv, 2);
782          else
783             inv = ec_dec_bit_logp(ec, 2);
784       } else
785          inv = 0;
786       itheta = 0;
787    }
788    qalloc = ec_tell_frac(ec) - tell;
789    *b -= qalloc;
790
791    if (itheta == 0)
792    {
793       imid = 32767;
794       iside = 0;
795       *fill &= (1<<B)-1;
796       delta = -16384;
797    } else if (itheta == 16384)
798    {
799       imid = 0;
800       iside = 32767;
801       *fill &= ((1<<B)-1)<<B;
802       delta = 16384;
803    } else {
804       imid = bitexact_cos((opus_int16)itheta);
805       iside = bitexact_cos((opus_int16)(16384-itheta));
806       /* This is the mid vs side allocation that minimizes squared error
807          in that band. */
808       delta = FRAC_MUL16((N-1)<<7,bitexact_log2tan(iside,imid));
809    }
810
811    sctx->inv = inv;
812    sctx->imid = imid;
813    sctx->iside = iside;
814    sctx->delta = delta;
815    sctx->itheta = itheta;
816    sctx->qalloc = qalloc;
817 }
818 static unsigned quant_band_n1(struct band_ctx *ctx, celt_norm *X, celt_norm *Y, int b,
819       celt_norm *lowband_out)
820 {
821 #ifdef RESYNTH
822    int resynth = 1;
823 #else
824    int resynth = !ctx->encode;
825 #endif
826    int c;
827    int stereo;
828    celt_norm *x = X;
829    int encode;
830    ec_ctx *ec;
831
832    encode = ctx->encode;
833    ec = ctx->ec;
834
835    stereo = Y != NULL;
836    c=0; do {
837       int sign=0;
838       if (ctx->remaining_bits>=1<<BITRES)
839       {
840          if (encode)
841          {
842             sign = x[0]<0;
843             ec_enc_bits(ec, sign, 1);
844          } else {
845             sign = ec_dec_bits(ec, 1);
846          }
847          ctx->remaining_bits -= 1<<BITRES;
848          b-=1<<BITRES;
849       }
850       if (resynth)
851          x[0] = sign ? -NORM_SCALING : NORM_SCALING;
852       x = Y;
853    } while (++c<1+stereo);
854    if (lowband_out)
855       lowband_out[0] = SHR16(X[0],4);
856    return 1;
857 }
858
859 /* This function is responsible for encoding and decoding a mono partition.
860    It can split the band in two and transmit the energy difference with
861    the two half-bands. It can be called recursively so bands can end up being
862    split in 8 parts. */
863 static unsigned quant_partition(struct band_ctx *ctx, celt_norm *X,
864       int N, int b, int B, celt_norm *lowband,
865       int LM,
866       opus_val16 gain, int fill)
867 {
868    const unsigned char *cache;
869    int q;
870    int curr_bits;
871    int imid=0, iside=0;
872    int B0=B;
873    opus_val16 mid=0, side=0;
874    unsigned cm=0;
875 #ifdef RESYNTH
876    int resynth = 1;
877 #else
878    int resynth = !ctx->encode;
879 #endif
880    celt_norm *Y=NULL;
881    int encode;
882    const CELTMode *m;
883    int i;
884    int spread;
885    ec_ctx *ec;
886
887    encode = ctx->encode;
888    m = ctx->m;
889    i = ctx->i;
890    spread = ctx->spread;
891    ec = ctx->ec;
892
893    /* If we need 1.5 more bit than we can produce, split the band in two. */
894    cache = m->cache.bits + m->cache.index[(LM+1)*m->nbEBands+i];
895    if (LM != -1 && b > cache[cache[0]]+12 && N>2)
896    {
897       int mbits, sbits, delta;
898       int itheta;
899       int qalloc;
900       struct split_ctx sctx;
901       celt_norm *next_lowband2=NULL;
902       opus_int32 rebalance;
903
904       N >>= 1;
905       Y = X+N;
906       LM -= 1;
907       if (B==1)
908          fill = (fill&1)|(fill<<1);
909       B = (B+1)>>1;
910
911       compute_theta(ctx, &sctx, X, Y, N, &b, B, B0,
912             LM, 0, &fill);
913       imid = sctx.imid;
914       iside = sctx.iside;
915       delta = sctx.delta;
916       itheta = sctx.itheta;
917       qalloc = sctx.qalloc;
918 #ifdef FIXED_POINT
919       mid = imid;
920       side = iside;
921 #else
922       mid = (1.f/32768)*imid;
923       side = (1.f/32768)*iside;
924 #endif
925
926       /* Give more bits to low-energy MDCTs than they would otherwise deserve */
927       if (B0>1 && (itheta&0x3fff))
928       {
929          if (itheta > 8192)
930             /* Rough approximation for pre-echo masking */
931             delta -= delta>>(4-LM);
932          else
933             /* Corresponds to a forward-masking slope of 1.5 dB per 10 ms */
934             delta = IMIN(0, delta + (N<<BITRES>>(5-LM)));
935       }
936       mbits = IMAX(0, IMIN(b, (b-delta)/2));
937       sbits = b-mbits;
938       ctx->remaining_bits -= qalloc;
939
940       if (lowband)
941          next_lowband2 = lowband+N; /* >32-bit split case */
942
943       rebalance = ctx->remaining_bits;
944       if (mbits >= sbits)
945       {
946          cm = quant_partition(ctx, X, N, mbits, B,
947                lowband, LM,
948                MULT16_16_P15(gain,mid), fill);
949          rebalance = mbits - (rebalance-ctx->remaining_bits);
950          if (rebalance > 3<<BITRES && itheta!=0)
951             sbits += rebalance - (3<<BITRES);
952          cm |= quant_partition(ctx, Y, N, sbits, B,
953                next_lowband2, LM,
954                MULT16_16_P15(gain,side), fill>>B)<<(B0>>1);
955       } else {
956          cm = quant_partition(ctx, Y, N, sbits, B,
957                next_lowband2, LM,
958                MULT16_16_P15(gain,side), fill>>B)<<(B0>>1);
959          rebalance = sbits - (rebalance-ctx->remaining_bits);
960          if (rebalance > 3<<BITRES && itheta!=16384)
961             mbits += rebalance - (3<<BITRES);
962          cm |= quant_partition(ctx, X, N, mbits, B,
963                lowband, LM,
964                MULT16_16_P15(gain,mid), fill);
965       }
966    } else {
967       /* This is the basic no-split case */
968       q = bits2pulses(m, i, LM, b);
969       curr_bits = pulses2bits(m, i, LM, q);
970       ctx->remaining_bits -= curr_bits;
971
972       /* Ensures we can never bust the budget */
973       while (ctx->remaining_bits < 0 && q > 0)
974       {
975          ctx->remaining_bits += curr_bits;
976          q--;
977          curr_bits = pulses2bits(m, i, LM, q);
978          ctx->remaining_bits -= curr_bits;
979       }
980
981       if (q!=0)
982       {
983          int K = get_pulses(q);
984
985          /* Finally do the actual quantization */
986          if (encode)
987          {
988             cm = alg_quant(X, N, K, spread, B, ec
989 #ifdef RESYNTH
990                  , gain
991 #endif
992                  );
993          } else {
994             cm = alg_unquant(X, N, K, spread, B, ec, gain);
995          }
996       } else {
997          /* If there's no pulse, fill the band anyway */
998          int j;
999          if (resynth)
1000          {
1001             unsigned cm_mask;
1002             /* B can be as large as 16, so this shift might overflow an int on a
1003                16-bit platform; use a long to get defined behavior.*/
1004             cm_mask = (unsigned)(1UL<<B)-1;
1005             fill &= cm_mask;
1006             if (!fill)
1007             {
1008                for (j=0;j<N;j++)
1009                   X[j] = 0;
1010             } else {
1011                if (lowband == NULL)
1012                {
1013                   /* Noise */
1014                   for (j=0;j<N;j++)
1015                   {
1016                      ctx->seed = celt_lcg_rand(ctx->seed);
1017                      X[j] = (celt_norm)((opus_int32)ctx->seed>>20);
1018                   }
1019                   cm = cm_mask;
1020                } else {
1021                   /* Folded spectrum */
1022                   for (j=0;j<N;j++)
1023                   {
1024                      opus_val16 tmp;
1025                      ctx->seed = celt_lcg_rand(ctx->seed);
1026                      /* About 48 dB below the "normal" folding level */
1027                      tmp = QCONST16(1.0f/256, 10);
1028                      tmp = (ctx->seed)&0x8000 ? tmp : -tmp;
1029                      X[j] = lowband[j]+tmp;
1030                   }
1031                   cm = fill;
1032                }
1033                renormalise_vector(X, N, gain);
1034             }
1035          }
1036       }
1037    }
1038
1039    return cm;
1040 }
1041
1042
1043 /* This function is responsible for encoding and decoding a band for the mono case. */
1044 static unsigned quant_band(struct band_ctx *ctx, celt_norm *X,
1045       int N, int b, int B, celt_norm *lowband,
1046       int LM, celt_norm *lowband_out,
1047       opus_val16 gain, celt_norm *lowband_scratch, int fill)
1048 {
1049    int N0=N;
1050    int N_B=N;
1051    int N_B0;
1052    int B0=B;
1053    int time_divide=0;
1054    int recombine=0;
1055    int longBlocks;
1056    unsigned cm=0;
1057 #ifdef RESYNTH
1058    int resynth = 1;
1059 #else
1060    int resynth = !ctx->encode;
1061 #endif
1062    int k;
1063    int encode;
1064    int tf_change;
1065
1066    encode = ctx->encode;
1067    tf_change = ctx->tf_change;
1068
1069    longBlocks = B0==1;
1070
1071    N_B /= B;
1072
1073    /* Special case for one sample */
1074    if (N==1)
1075    {
1076       return quant_band_n1(ctx, X, NULL, b, lowband_out);
1077    }
1078
1079    if (tf_change>0)
1080       recombine = tf_change;
1081    /* Band recombining to increase frequency resolution */
1082
1083    if (lowband_scratch && lowband && (recombine || ((N_B&1) == 0 && tf_change<0) || B0>1))
1084    {
1085       int j;
1086       for (j=0;j<N;j++)
1087          lowband_scratch[j] = lowband[j];
1088       lowband = lowband_scratch;
1089    }
1090
1091    for (k=0;k<recombine;k++)
1092    {
1093       static const unsigned char bit_interleave_table[16]={
1094             0,1,1,1,2,3,3,3,2,3,3,3,2,3,3,3
1095       };
1096       if (encode)
1097          haar1(X, N>>k, 1<<k);
1098       if (lowband)
1099          haar1(lowband, N>>k, 1<<k);
1100       fill = bit_interleave_table[fill&0xF]|bit_interleave_table[fill>>4]<<2;
1101    }
1102    B>>=recombine;
1103    N_B<<=recombine;
1104
1105    /* Increasing the time resolution */
1106    while ((N_B&1) == 0 && tf_change<0)
1107    {
1108       if (encode)
1109          haar1(X, N_B, B);
1110       if (lowband)
1111          haar1(lowband, N_B, B);
1112       fill |= fill<<B;
1113       B <<= 1;
1114       N_B >>= 1;
1115       time_divide++;
1116       tf_change++;
1117    }
1118    B0=B;
1119    N_B0 = N_B;
1120
1121    /* Reorganize the samples in time order instead of frequency order */
1122    if (B0>1)
1123    {
1124       if (encode)
1125          deinterleave_hadamard(X, N_B>>recombine, B0<<recombine, longBlocks);
1126       if (lowband)
1127          deinterleave_hadamard(lowband, N_B>>recombine, B0<<recombine, longBlocks);
1128    }
1129
1130    cm = quant_partition(ctx, X, N, b, B, lowband,
1131          LM, gain, fill);
1132
1133    /* This code is used by the decoder and by the resynthesis-enabled encoder */
1134    if (resynth)
1135    {
1136       /* Undo the sample reorganization going from time order to frequency order */
1137       if (B0>1)
1138          interleave_hadamard(X, N_B>>recombine, B0<<recombine, longBlocks);
1139
1140       /* Undo time-freq changes that we did earlier */
1141       N_B = N_B0;
1142       B = B0;
1143       for (k=0;k<time_divide;k++)
1144       {
1145          B >>= 1;
1146          N_B <<= 1;
1147          cm |= cm>>B;
1148          haar1(X, N_B, B);
1149       }
1150
1151       for (k=0;k<recombine;k++)
1152       {
1153          static const unsigned char bit_deinterleave_table[16]={
1154                0x00,0x03,0x0C,0x0F,0x30,0x33,0x3C,0x3F,
1155                0xC0,0xC3,0xCC,0xCF,0xF0,0xF3,0xFC,0xFF
1156          };
1157          cm = bit_deinterleave_table[cm];
1158          haar1(X, N0>>k, 1<<k);
1159       }
1160       B<<=recombine;
1161
1162       /* Scale output for later folding */
1163       if (lowband_out)
1164       {
1165          int j;
1166          opus_val16 n;
1167          n = celt_sqrt(SHL32(EXTEND32(N0),22));
1168          for (j=0;j<N0;j++)
1169             lowband_out[j] = MULT16_16_Q15(n,X[j]);
1170       }
1171       cm &= (1<<B)-1;
1172    }
1173    return cm;
1174 }
1175
1176
1177 /* This function is responsible for encoding and decoding a band for the stereo case. */
1178 static unsigned quant_band_stereo(struct band_ctx *ctx, celt_norm *X, celt_norm *Y,
1179       int N, int b, int B, celt_norm *lowband,
1180       int LM, celt_norm *lowband_out,
1181       celt_norm *lowband_scratch, int fill)
1182 {
1183    int imid=0, iside=0;
1184    int inv = 0;
1185    opus_val16 mid=0, side=0;
1186    unsigned cm=0;
1187 #ifdef RESYNTH
1188    int resynth = 1;
1189 #else
1190    int resynth = !ctx->encode;
1191 #endif
1192    int mbits, sbits, delta;
1193    int itheta;
1194    int qalloc;
1195    struct split_ctx sctx;
1196    int orig_fill;
1197    int encode;
1198    ec_ctx *ec;
1199
1200    encode = ctx->encode;
1201    ec = ctx->ec;
1202
1203    /* Special case for one sample */
1204    if (N==1)
1205    {
1206       return quant_band_n1(ctx, X, Y, b, lowband_out);
1207    }
1208
1209    orig_fill = fill;
1210
1211    compute_theta(ctx, &sctx, X, Y, N, &b, B, B,
1212          LM, 1, &fill);
1213    inv = sctx.inv;
1214    imid = sctx.imid;
1215    iside = sctx.iside;
1216    delta = sctx.delta;
1217    itheta = sctx.itheta;
1218    qalloc = sctx.qalloc;
1219 #ifdef FIXED_POINT
1220    mid = imid;
1221    side = iside;
1222 #else
1223    mid = (1.f/32768)*imid;
1224    side = (1.f/32768)*iside;
1225 #endif
1226
1227    /* This is a special case for N=2 that only works for stereo and takes
1228       advantage of the fact that mid and side are orthogonal to encode
1229       the side with just one bit. */
1230    if (N==2)
1231    {
1232       int c;
1233       int sign=0;
1234       celt_norm *x2, *y2;
1235       mbits = b;
1236       sbits = 0;
1237       /* Only need one bit for the side. */
1238       if (itheta != 0 && itheta != 16384)
1239          sbits = 1<<BITRES;
1240       mbits -= sbits;
1241       c = itheta > 8192;
1242       ctx->remaining_bits -= qalloc+sbits;
1243
1244       x2 = c ? Y : X;
1245       y2 = c ? X : Y;
1246       if (sbits)
1247       {
1248          if (encode)
1249          {
1250             /* Here we only need to encode a sign for the side. */
1251             sign = x2[0]*y2[1] - x2[1]*y2[0] < 0;
1252             ec_enc_bits(ec, sign, 1);
1253          } else {
1254             sign = ec_dec_bits(ec, 1);
1255          }
1256       }
1257       sign = 1-2*sign;
1258       /* We use orig_fill here because we want to fold the side, but if
1259          itheta==16384, we'll have cleared the low bits of fill. */
1260       cm = quant_band(ctx, x2, N, mbits, B, lowband,
1261             LM, lowband_out, Q15ONE, lowband_scratch, orig_fill);
1262       /* We don't split N=2 bands, so cm is either 1 or 0 (for a fold-collapse),
1263          and there's no need to worry about mixing with the other channel. */
1264       y2[0] = -sign*x2[1];
1265       y2[1] = sign*x2[0];
1266       if (resynth)
1267       {
1268          celt_norm tmp;
1269          X[0] = MULT16_16_Q15(mid, X[0]);
1270          X[1] = MULT16_16_Q15(mid, X[1]);
1271          Y[0] = MULT16_16_Q15(side, Y[0]);
1272          Y[1] = MULT16_16_Q15(side, Y[1]);
1273          tmp = X[0];
1274          X[0] = SUB16(tmp,Y[0]);
1275          Y[0] = ADD16(tmp,Y[0]);
1276          tmp = X[1];
1277          X[1] = SUB16(tmp,Y[1]);
1278          Y[1] = ADD16(tmp,Y[1]);
1279       }
1280    } else {
1281       /* "Normal" split code */
1282       opus_int32 rebalance;
1283
1284       mbits = IMAX(0, IMIN(b, (b-delta)/2));
1285       sbits = b-mbits;
1286       ctx->remaining_bits -= qalloc;
1287
1288       rebalance = ctx->remaining_bits;
1289       if (mbits >= sbits)
1290       {
1291          /* In stereo mode, we do not apply a scaling to the mid because we need the normalized
1292             mid for folding later. */
1293          cm = quant_band(ctx, X, N, mbits, B,
1294                lowband, LM, lowband_out,
1295                Q15ONE, lowband_scratch, fill);
1296          rebalance = mbits - (rebalance-ctx->remaining_bits);
1297          if (rebalance > 3<<BITRES && itheta!=0)
1298             sbits += rebalance - (3<<BITRES);
1299
1300          /* For a stereo split, the high bits of fill are always zero, so no
1301             folding will be done to the side. */
1302          cm |= quant_band(ctx, Y, N, sbits, B,
1303                NULL, LM, NULL,
1304                side, NULL, fill>>B);
1305       } else {
1306          /* For a stereo split, the high bits of fill are always zero, so no
1307             folding will be done to the side. */
1308          cm = quant_band(ctx, Y, N, sbits, B,
1309                NULL, LM, NULL,
1310                side, NULL, fill>>B);
1311          rebalance = sbits - (rebalance-ctx->remaining_bits);
1312          if (rebalance > 3<<BITRES && itheta!=16384)
1313             mbits += rebalance - (3<<BITRES);
1314          /* In stereo mode, we do not apply a scaling to the mid because we need the normalized
1315             mid for folding later. */
1316          cm |= quant_band(ctx, X, N, mbits, B,
1317                lowband, LM, lowband_out,
1318                Q15ONE, lowband_scratch, fill);
1319       }
1320    }
1321
1322
1323    /* This code is used by the decoder and by the resynthesis-enabled encoder */
1324    if (resynth)
1325    {
1326       if (N!=2)
1327          stereo_merge(X, Y, mid, N);
1328       if (inv)
1329       {
1330          int j;
1331          for (j=0;j<N;j++)
1332             Y[j] = -Y[j];
1333       }
1334    }
1335    return cm;
1336 }
1337
1338
1339 void quant_all_bands(int encode, const CELTMode *m, int start, int end,
1340       celt_norm *X_, celt_norm *Y_, unsigned char *collapse_masks, const celt_ener *bandE, int *pulses,
1341       int shortBlocks, int spread, int dual_stereo, int intensity, int *tf_res,
1342       opus_int32 total_bits, opus_int32 balance, ec_ctx *ec, int LM, int codedBands, opus_uint32 *seed)
1343 {
1344    int i;
1345    opus_int32 remaining_bits;
1346    const opus_int16 * OPUS_RESTRICT eBands = m->eBands;
1347    celt_norm * OPUS_RESTRICT norm, * OPUS_RESTRICT norm2;
1348    VARDECL(celt_norm, _norm);
1349    celt_norm *lowband_scratch;
1350    int B;
1351    int M;
1352    int lowband_offset;
1353    int update_lowband = 1;
1354    int C = Y_ != NULL ? 2 : 1;
1355    int norm_offset;
1356 #ifdef RESYNTH
1357    int resynth = 1;
1358 #else
1359    int resynth = !encode;
1360 #endif
1361    struct band_ctx ctx;
1362    SAVE_STACK;
1363
1364    M = 1<<LM;
1365    B = shortBlocks ? M : 1;
1366    norm_offset = M*eBands[start];
1367    /* No need to allocate norm for the last band because we don't need an
1368       output in that band. */
1369    ALLOC(_norm, C*(M*eBands[m->nbEBands-1]-norm_offset), celt_norm);
1370    norm = _norm;
1371    norm2 = norm + M*eBands[m->nbEBands-1]-norm_offset;
1372    /* We can use the last band as scratch space because we don't need that
1373       scratch space for the last band. */
1374    lowband_scratch = X_+M*eBands[m->nbEBands-1];
1375
1376    lowband_offset = 0;
1377    ctx.bandE = bandE;
1378    ctx.ec = ec;
1379    ctx.encode = encode;
1380    ctx.intensity = intensity;
1381    ctx.m = m;
1382    ctx.seed = *seed;
1383    ctx.spread = spread;
1384    for (i=start;i<end;i++)
1385    {
1386       opus_int32 tell;
1387       int b;
1388       int N;
1389       opus_int32 curr_balance;
1390       int effective_lowband=-1;
1391       celt_norm * OPUS_RESTRICT X, * OPUS_RESTRICT Y;
1392       int tf_change=0;
1393       unsigned x_cm;
1394       unsigned y_cm;
1395       int last;
1396
1397       ctx.i = i;
1398       last = (i==end-1);
1399
1400       X = X_+M*eBands[i];
1401       if (Y_!=NULL)
1402          Y = Y_+M*eBands[i];
1403       else
1404          Y = NULL;
1405       N = M*eBands[i+1]-M*eBands[i];
1406       tell = ec_tell_frac(ec);
1407
1408       /* Compute how many bits we want to allocate to this band */
1409       if (i != start)
1410          balance -= tell;
1411       remaining_bits = total_bits-tell-1;
1412       ctx.remaining_bits = remaining_bits;
1413       if (i <= codedBands-1)
1414       {
1415          curr_balance = balance / IMIN(3, codedBands-i);
1416          b = IMAX(0, IMIN(16383, IMIN(remaining_bits+1,pulses[i]+curr_balance)));
1417       } else {
1418          b = 0;
1419       }
1420
1421       if (resynth && M*eBands[i]-N >= M*eBands[start] && (update_lowband || lowband_offset==0))
1422             lowband_offset = i;
1423
1424       tf_change = tf_res[i];
1425       ctx.tf_change = tf_change;
1426       if (i>=m->effEBands)
1427       {
1428          X=norm;
1429          if (Y_!=NULL)
1430             Y = norm;
1431          lowband_scratch = NULL;
1432       }
1433       if (i==end-1)
1434          lowband_scratch = NULL;
1435
1436       /* Get a conservative estimate of the collapse_mask's for the bands we're
1437          going to be folding from. */
1438       if (lowband_offset != 0 && (spread!=SPREAD_AGGRESSIVE || B>1 || tf_change<0))
1439       {
1440          int fold_start;
1441          int fold_end;
1442          int fold_i;
1443          /* This ensures we never repeat spectral content within one band */
1444          effective_lowband = IMAX(0, M*eBands[lowband_offset]-norm_offset-N);
1445          fold_start = lowband_offset;
1446          while(M*eBands[--fold_start] > effective_lowband+norm_offset);
1447          fold_end = lowband_offset-1;
1448          while(M*eBands[++fold_end] < effective_lowband+norm_offset+N);
1449          x_cm = y_cm = 0;
1450          fold_i = fold_start; do {
1451            x_cm |= collapse_masks[fold_i*C+0];
1452            y_cm |= collapse_masks[fold_i*C+C-1];
1453          } while (++fold_i<fold_end);
1454       }
1455       /* Otherwise, we'll be using the LCG to fold, so all blocks will (almost
1456          always) be non-zero. */
1457       else
1458          x_cm = y_cm = (1<<B)-1;
1459
1460       if (dual_stereo && i==intensity)
1461       {
1462          int j;
1463
1464          /* Switch off dual stereo to do intensity. */
1465          dual_stereo = 0;
1466          if (resynth)
1467             for (j=0;j<M*eBands[i]-norm_offset;j++)
1468                norm[j] = HALF32(norm[j]+norm2[j]);
1469       }
1470       if (dual_stereo)
1471       {
1472          x_cm = quant_band(&ctx, X, N, b/2, B,
1473                effective_lowband != -1 ? norm+effective_lowband : NULL, LM,
1474                last?NULL:norm+M*eBands[i]-norm_offset, Q15ONE, lowband_scratch, x_cm);
1475          y_cm = quant_band(&ctx, Y, N, b/2, B,
1476                effective_lowband != -1 ? norm2+effective_lowband : NULL, LM,
1477                last?NULL:norm2+M*eBands[i]-norm_offset, Q15ONE, lowband_scratch, y_cm);
1478       } else {
1479          if (Y!=NULL)
1480          {
1481             x_cm = quant_band_stereo(&ctx, X, Y, N, b, B,
1482                   effective_lowband != -1 ? norm+effective_lowband : NULL, LM,
1483                         last?NULL:norm+M*eBands[i]-norm_offset, lowband_scratch, x_cm|y_cm);
1484          } else {
1485             x_cm = quant_band(&ctx, X, N, b, B,
1486                   effective_lowband != -1 ? norm+effective_lowband : NULL, LM,
1487                         last?NULL:norm+M*eBands[i]-norm_offset, Q15ONE, lowband_scratch, x_cm|y_cm);
1488          }
1489          y_cm = x_cm;
1490       }
1491       collapse_masks[i*C+0] = (unsigned char)x_cm;
1492       collapse_masks[i*C+C-1] = (unsigned char)y_cm;
1493       balance += pulses[i] + tell;
1494
1495       /* Update the folding position only as long as we have 1 bit/sample depth. */
1496       update_lowband = b>(N<<BITRES);
1497    }
1498    *seed = ctx.seed;
1499
1500    RESTORE_STACK;
1501 }
1502