add noglobals API support to speexdec.c
[speexdsp.git] / libspeex / vq.c
1 /* Copyright (C) 2002 Jean-Marc Valin
2    File: vq.c
3    Vector quantization
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 "vq.h"
38 #include "stack_alloc.h"
39
40 int scal_quant(spx_word16_t in, const spx_word16_t *boundary, int entries)
41 {
42    int i=0;
43    while (i<entries-1 && in>boundary[0])
44    {
45       boundary++;
46       i++;
47    }
48    return i;
49 }
50
51 int scal_quant32(spx_word32_t in, const spx_word32_t *boundary, int entries)
52 {
53    int i=0;
54    while (i<entries-1 && in>boundary[0])
55    {
56       boundary++;
57       i++;
58    }
59    return i;
60 }
61
62 /*Finds the index of the entry in a codebook that best matches the input*/
63 int vq_index(float *in, const float *codebook, int len, int entries)
64 {
65    int i,j;
66    float min_dist=0;
67    int best_index=0;
68    for (i=0;i<entries;i++)
69    {
70       float dist=0;
71       for (j=0;j<len;j++)
72       {
73          float tmp = in[j]-*codebook++;
74          dist += tmp*tmp;
75       }
76       if (i==0 || dist<min_dist)
77       {
78          min_dist=dist;
79          best_index=i;
80       }
81    }
82    return best_index;
83 }
84
85 #ifdef _USE_SSE
86 #include <xmmintrin.h>
87 #include "misc.h"
88 void vq_nbest(spx_word16_t *_in, const __m128 *codebook, int len, int entries, __m128 *E, int N, int *nbest, spx_word32_t *best_dist, char *stack)
89 {
90    int i,j,k,used;
91    float *dist;
92    __m128 *in;
93    __m128 half;
94    used = 0;
95    dist = PUSH(stack, entries, float);
96    half = _mm_set_ps1(.5f);
97    in = PUSH(stack, len, __m128);
98    for (i=0;i<len;i++)
99       in[i] = _mm_set_ps1(_in[i]);
100    for (i=0;i<entries>>2;i++)
101    {
102       __m128 d = _mm_mul_ps(E[i], half);
103       for (j=0;j<len;j++)
104          d = _mm_sub_ps(d, _mm_mul_ps(in[j], *codebook++));
105       _mm_storeu_ps(dist+4*i, d);
106    }
107    for (i=0;i<entries;i++)
108    {
109       if (i<N || dist[i]<best_dist[N-1])
110       {
111          for (k=N-1; (k >= 1) && (k > used || dist[i] < best_dist[k-1]); k--)
112          {
113             best_dist[k]=best_dist[k-1];
114             nbest[k] = nbest[k-1];
115          }
116          best_dist[k]=dist[i];
117          nbest[k]=i;
118          used++;
119       }
120    }
121 }
122
123
124 #else
125
126 /*Finds the indices of the n-best entries in a codebook*/
127 void vq_nbest(spx_word16_t *in, const spx_word16_t *codebook, int len, int entries, spx_word32_t *E, int N, int *nbest, spx_word32_t *best_dist, char *stack)
128 {
129    int i,j,k,used;
130    used = 0;
131    for (i=0;i<entries;i++)
132    {
133       spx_word32_t dist=0;
134       for (j=0;j<len;j++)
135          dist = MAC16_16(dist,in[j],*codebook++);
136 #ifdef FIXED_POINT
137       dist=SUB32(SHR(E[i],1),dist);
138 #else
139       dist=.5f*E[i]-dist;
140 #endif
141       if (i<N || dist<best_dist[N-1])
142       {
143          for (k=N-1; (k >= 1) && (k > used || dist < best_dist[k-1]); k--)
144          {
145             best_dist[k]=best_dist[k-1];
146             nbest[k] = nbest[k-1];
147          }
148          best_dist[k]=dist;
149          nbest[k]=i;
150          used++;
151       }
152    }
153 }
154
155 #endif
156
157
158
159 #ifdef _USE_SSE
160
161 void vq_nbest_sign(spx_word16_t *_in, const __m128 *codebook, int len, int entries, __m128 *E, int N, int *nbest, spx_word32_t *best_dist, char *stack)
162 {
163    int i,j,k,used;
164    float *dist;
165    __m128 *in;
166    __m128 half;
167    used = 0;
168    dist = PUSH(stack, entries, float);
169    half = _mm_set_ps1(.5f);
170    in = PUSH(stack, len, __m128);
171    for (i=0;i<len;i++)
172       in[i] = _mm_set_ps1(_in[i]);
173    for (i=0;i<entries>>2;i++)
174    {
175       __m128 d = _mm_setzero_ps();
176       for (j=0;j<len;j++)
177          d = _mm_add_ps(d, _mm_mul_ps(in[j], *codebook++));
178       _mm_storeu_ps(dist+4*i, d);
179    }
180    for (i=0;i<entries;i++)
181    {
182       int sign;
183       if (dist[i]>0)
184       {
185          sign=0;
186          dist[i]=-dist[i];
187       } else
188       {
189          sign=1;
190       }
191       dist[i] += .5f*((float*)E)[i];
192       if (i<N || dist[i]<best_dist[N-1])
193       {
194          for (k=N-1; (k >= 1) && (k > used || dist[i] < best_dist[k-1]); k--)
195          {
196             best_dist[k]=best_dist[k-1];
197             nbest[k] = nbest[k-1];
198          }
199          best_dist[k]=dist[i];
200          nbest[k]=i;
201          used++;
202          if (sign)
203             nbest[k]+=entries;
204       }
205    }
206 }
207
208 #else
209
210 /*Finds the indices of the n-best entries in a codebook with sign*/
211 void vq_nbest_sign(spx_word16_t *in, const spx_word16_t *codebook, int len, int entries, spx_word32_t *E, int N, int *nbest, spx_word32_t *best_dist, char *stack)
212 {
213    int i,j,k, sign, used;
214    used=0;
215    for (i=0;i<entries;i++)
216    {
217       spx_word32_t dist=0;
218       for (j=0;j<len;j++)
219          dist = MAC16_16(dist,in[j],*codebook++);
220       if (dist>0)
221       {
222          sign=0;
223          dist=-dist;
224       } else
225       {
226          sign=1;
227       }
228 #ifdef FIXED_POINT
229       dist = ADD32(dist,SHR(E[i],1));
230 #else
231       dist = ADD32(dist,.5f*E[i]);
232 #endif
233       if (i<N || dist<best_dist[N-1])
234       {
235          for (k=N-1; (k >= 1) && (k > used || dist < best_dist[k-1]); k--)
236          {
237             best_dist[k]=best_dist[k-1];
238             nbest[k] = nbest[k-1];
239          }
240          best_dist[k]=dist;
241          nbest[k]=i;
242          used++;
243          if (sign)
244             nbest[k]+=entries;
245       }
246    }
247 }
248 #endif