1885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/* Copyright (c) 2009-2010 Xiph.Org Foundation
2885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   Written by Jean-Marc Valin */
3885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org/*
4885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   Redistribution and use in source and binary forms, with or without
5885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   modification, are permitted provided that the following conditions
6885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   are met:
7885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
8885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   - Redistributions of source code must retain the above copyright
9885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   notice, this list of conditions and the following disclaimer.
10885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
11885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   - Redistributions in binary form must reproduce the above copyright
12885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   notice, this list of conditions and the following disclaimer in the
13885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   documentation and/or other materials provided with the distribution.
14885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
15885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
19885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org*/
27885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
28885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef HAVE_CONFIG_H
29885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "config.h"
30885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif
31885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
32885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "celt_lpc.h"
33885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "stack_alloc.h"
34885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#include "mathops.h"
35e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#include "pitch.h"
36885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
37885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgvoid _celt_lpc(
38885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      opus_val16       *_lpc, /* out: [0...p-1] LPC coefficients      */
39885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgconst opus_val32 *ac,  /* in:  [0...p] autocorrelation values  */
40885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.orgint          p
41885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org)
42885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{
43885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   int i, j;
44885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   opus_val32 r;
45885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   opus_val32 error = ac[0];
46885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef FIXED_POINT
47885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   opus_val32 lpc[LPC_ORDER];
48885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#else
49885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   float *lpc = _lpc;
50885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif
51885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
52885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   for (i = 0; i < p; i++)
53885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      lpc[i] = 0;
54885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   if (ac[0] != 0)
55885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   {
56885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      for (i = 0; i < p; i++) {
57885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         /* Sum up this iteration's reflection coefficient */
58885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         opus_val32 rr = 0;
59885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         for (j = 0; j < i; j++)
60885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            rr += MULT32_32_Q31(lpc[j],ac[i - j]);
61885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         rr += SHR32(ac[i + 1],3);
62885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         r = -frac_div32(SHL32(rr,3), error);
63885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         /*  Update LPC coefficients and total error */
64885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         lpc[i] = SHR32(r,3);
65885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         for (j = 0; j < (i+1)>>1; j++)
66885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         {
67885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            opus_val32 tmp1, tmp2;
68885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            tmp1 = lpc[j];
69885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            tmp2 = lpc[i-1-j];
70885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            lpc[j]     = tmp1 + MULT32_32_Q31(r,tmp2);
71885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            lpc[i-1-j] = tmp2 + MULT32_32_Q31(r,tmp1);
72885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         }
73885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
74885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         error = error - MULT32_32_Q31(MULT32_32_Q31(r,r),error);
75885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         /* Bail out once we get 30 dB gain */
76885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef FIXED_POINT
77885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         if (error<SHR32(ac[0],10))
78885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            break;
79885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#else
80885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         if (error<.001f*ac[0])
81885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org            break;
82885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif
83885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      }
84885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   }
85885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef FIXED_POINT
86885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   for (i=0;i<p;i++)
87885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      _lpc[i] = ROUND16(lpc[i],16);
88885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif
89885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org}
90885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
91e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.orgvoid celt_fir(const opus_val16 *_x,
92885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         const opus_val16 *num,
93e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         opus_val16 *_y,
94885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         int N,
95885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         int ord,
96885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         opus_val16 *mem)
97885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{
98885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   int i,j;
99e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   VARDECL(opus_val16, rnum);
100e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   VARDECL(opus_val16, x);
101e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   SAVE_STACK;
102885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
103e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   ALLOC(rnum, ord, opus_val16);
104e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   ALLOC(x, N+ord, opus_val16);
105e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for(i=0;i<ord;i++)
106e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      rnum[i] = num[ord-i-1];
107e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for(i=0;i<ord;i++)
108e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      x[i] = mem[ord-i-1];
109e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for (i=0;i<N;i++)
110e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      x[i+ord]=_x[i];
111e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for(i=0;i<ord;i++)
112e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      mem[i] = _x[N-i-1];
113e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#ifdef SMALL_FOOTPRINT
114885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   for (i=0;i<N;i++)
115885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   {
116e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      opus_val32 sum = SHL32(EXTEND32(_x[i]), SIG_SHIFT);
117885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      for (j=0;j<ord;j++)
118885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      {
119e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         sum = MAC16_16(sum,rnum[j],x[i+j]);
120885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      }
121e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i] = SATURATE16(PSHR32(sum, SIG_SHIFT));
122885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   }
123e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#else
124e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for (i=0;i<N-3;i+=4)
125e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   {
126e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      opus_val32 sum[4]={0,0,0,0};
127e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      xcorr_kernel(rnum, x+i, sum, ord);
128e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i  ] = SATURATE16(ADD32(EXTEND32(_x[i  ]), PSHR32(sum[0], SIG_SHIFT)));
129e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i+1] = SATURATE16(ADD32(EXTEND32(_x[i+1]), PSHR32(sum[1], SIG_SHIFT)));
130e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i+2] = SATURATE16(ADD32(EXTEND32(_x[i+2]), PSHR32(sum[2], SIG_SHIFT)));
131e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i+3] = SATURATE16(ADD32(EXTEND32(_x[i+3]), PSHR32(sum[3], SIG_SHIFT)));
132e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   }
133e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for (;i<N;i++)
134e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   {
135e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      opus_val32 sum = 0;
136e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for (j=0;j<ord;j++)
137e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         sum = MAC16_16(sum,rnum[j],x[i+j]);
138e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i] = SATURATE16(ADD32(EXTEND32(_x[i]), PSHR32(sum, SIG_SHIFT)));
139e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   }
140e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#endif
141e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   RESTORE_STACK;
142885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org}
143885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
144e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.orgvoid celt_iir(const opus_val32 *_x,
145885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         const opus_val16 *den,
146e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         opus_val32 *_y,
147885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         int N,
148885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         int ord,
149885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         opus_val16 *mem)
150885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{
151e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#ifdef SMALL_FOOTPRINT
152885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   int i,j;
153885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   for (i=0;i<N;i++)
154885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   {
155e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      opus_val32 sum = _x[i];
156885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      for (j=0;j<ord;j++)
157885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      {
158885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         sum -= MULT16_16(den[j],mem[j]);
159885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      }
160885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      for (j=ord-1;j>=1;j--)
161885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      {
162885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org         mem[j]=mem[j-1];
163885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      }
164885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      mem[0] = ROUND16(sum,SIG_SHIFT);
165e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i] = sum;
166885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   }
167e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#else
168e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   int i,j;
169e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   VARDECL(opus_val16, rden);
170e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   VARDECL(opus_val16, y);
171e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   SAVE_STACK;
172e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org
173e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   celt_assert((ord&3)==0);
174e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   ALLOC(rden, ord, opus_val16);
175e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   ALLOC(y, N+ord, opus_val16);
176e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for(i=0;i<ord;i++)
177e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      rden[i] = den[ord-i-1];
178e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for(i=0;i<ord;i++)
179e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      y[i] = -mem[ord-i-1];
180e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for(;i<N+ord;i++)
181e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      y[i]=0;
182e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for (i=0;i<N-3;i+=4)
183e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   {
184e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      /* Unroll by 4 as if it were an FIR filter */
185e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      opus_val32 sum[4];
186e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[0]=_x[i];
187e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[1]=_x[i+1];
188e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[2]=_x[i+2];
189e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[3]=_x[i+3];
190e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      xcorr_kernel(rden, y+i, sum, ord);
191e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org
192e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      /* Patch up the result to compensate for the fact that this is an IIR */
193e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      y[i+ord  ] = -ROUND16(sum[0],SIG_SHIFT);
194e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i  ] = sum[0];
195e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[1] = MAC16_16(sum[1], y[i+ord  ], den[0]);
196e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      y[i+ord+1] = -ROUND16(sum[1],SIG_SHIFT);
197e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i+1] = sum[1];
198e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[2] = MAC16_16(sum[2], y[i+ord+1], den[0]);
199e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[2] = MAC16_16(sum[2], y[i+ord  ], den[1]);
200e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      y[i+ord+2] = -ROUND16(sum[2],SIG_SHIFT);
201e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i+2] = sum[2];
202e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org
203e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[3] = MAC16_16(sum[3], y[i+ord+2], den[0]);
204e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[3] = MAC16_16(sum[3], y[i+ord+1], den[1]);
205e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      sum[3] = MAC16_16(sum[3], y[i+ord  ], den[2]);
206e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      y[i+ord+3] = -ROUND16(sum[3],SIG_SHIFT);
207e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i+3] = sum[3];
208e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   }
209e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for (;i<N;i++)
210e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   {
211e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      opus_val32 sum = _x[i];
212e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for (j=0;j<ord;j++)
213e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         sum -= MULT16_16(rden[j],y[i+j]);
214e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      y[i+ord] = ROUND16(sum,SIG_SHIFT);
215e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      _y[i] = sum;
216e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   }
217e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for(i=0;i<ord;i++)
218e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      mem[i] = _y[N-i-1];
219e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   RESTORE_STACK;
220e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#endif
221885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org}
222885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
223e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.orgint _celt_autocorr(
224885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org                   const opus_val16 *x,   /*  in: [0...n-1] samples x   */
225885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org                   opus_val32       *ac,  /* out: [0...lag-1] ac values */
226885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org                   const opus_val16       *window,
227885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org                   int          overlap,
228885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org                   int          lag,
2293c3902f0ac13428394f14f78f0fab05ef3468d69tlegrand@google.com                   int          n,
2303c3902f0ac13428394f14f78f0fab05ef3468d69tlegrand@google.com                   int          arch
231885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org                  )
232885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org{
233885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   opus_val32 d;
234e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   int i, k;
235e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   int fastN=n-lag;
236e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   int shift;
237e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   const opus_val16 *xptr;
238885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   VARDECL(opus_val16, xx);
239885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   SAVE_STACK;
240885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   ALLOC(xx, n, opus_val16);
241885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   celt_assert(n>0);
242885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   celt_assert(overlap>=0);
243e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   if (overlap == 0)
244885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   {
245e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      xptr = x;
246e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   } else {
247e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for (i=0;i<n;i++)
248e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         xx[i] = x[i];
249e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for (i=0;i<overlap;i++)
250e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      {
251e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         xx[i] = MULT16_16_Q15(x[i],window[i]);
252e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         xx[n-i-1] = MULT16_16_Q15(x[n-i-1],window[i]);
253e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      }
254e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      xptr = xx;
255885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   }
256e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   shift=0;
257885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#ifdef FIXED_POINT
258885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   {
259e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      opus_val32 ac0;
260e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      ac0 = 1+(n<<7);
261e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      if (n&1) ac0 += SHR32(MULT16_16(xptr[0],xptr[0]),9);
262e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for(i=(n&1);i<n;i+=2)
263e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      {
264e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         ac0 += SHR32(MULT16_16(xptr[i],xptr[i]),9);
265e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         ac0 += SHR32(MULT16_16(xptr[i+1],xptr[i+1]),9);
266e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      }
267885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
268885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org      shift = celt_ilog2(ac0)-30+10;
269e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      shift = (shift)/2;
270e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      if (shift>0)
271e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      {
272e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         for(i=0;i<n;i++)
273e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org            xx[i] = PSHR32(xptr[i], shift);
274e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         xptr = xx;
275e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      } else
276e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         shift = 0;
277885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   }
278885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org#endif
2793c3902f0ac13428394f14f78f0fab05ef3468d69tlegrand@google.com   celt_pitch_xcorr(xptr, xptr, ac, fastN, lag+1, arch);
280e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   for (k=0;k<=lag;k++)
281885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   {
282e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for (i = k+fastN, d = 0; i < n; i++)
283e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         d = MAC16_16(d, xptr[i], xptr[i-k]);
284e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      ac[k] += d;
285885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   }
286e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#ifdef FIXED_POINT
287e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   shift = 2*shift;
288e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   if (shift<=0)
289e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      ac[0] += SHL32((opus_int32)1, -shift);
290e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   if (ac[0] < 268435456)
291e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   {
292e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      int shift2 = 29 - EC_ILOG(ac[0]);
293e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for (i=0;i<=lag;i++)
294e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         ac[i] = SHL32(ac[i], shift2);
295e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      shift -= shift2;
296e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   } else if (ac[0] >= 536870912)
297e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   {
298e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      int shift2=1;
299e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      if (ac[0] >= 1073741824)
300e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         shift2++;
301e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      for (i=0;i<=lag;i++)
302e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org         ac[i] = SHR32(ac[i], shift2);
303e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org      shift += shift2;
304e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   }
305e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org#endif
306885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org
307885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org   RESTORE_STACK;
308e3ea049fcaee2247e45f0ce793d4313babb4ef69tlegrand@chromium.org   return shift;
309885f2ff5a7a7d6a73432d26a6c0ae9147e6b452sergeyu@chromium.org}
310