134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)/* Copyright (C) 2002 Jean-Marc Valin 234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) File: vq.c 334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) Vector quantization 434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) Redistribution and use in source and binary forms, with or without 634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) modification, are permitted provided that the following conditions 734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) are met: 834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) - Redistributions of source code must retain the above copyright 1034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) notice, this list of conditions and the following disclaimer. 1134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 1234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) - Redistributions in binary form must reproduce the above copyright 1334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) notice, this list of conditions and the following disclaimer in the 1434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) documentation and/or other materials provided with the distribution. 1534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 1634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) - Neither the name of the Xiph.org Foundation nor the names of its 1734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) contributors may be used to endorse or promote products derived from 1834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) this software without specific prior written permission. 1934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 2034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR 2434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 2534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 2634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 2734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 2834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 2934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 3034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)*/ 3234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 3334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#ifdef HAVE_CONFIG_H 3434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include "config.h" 3534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#endif 3634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 3734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include "vq.h" 3834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include "stack_alloc.h" 3934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include "arch.h" 4034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 4134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#ifdef _USE_SSE 4234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include <xmmintrin.h> 4334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include "vq_sse.h" 4434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#elif defined(SHORTCUTS) && (defined(ARM4_ASM) || defined(ARM5E_ASM)) 4534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include "vq_arm4.h" 4634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#elif defined(BFIN_ASM) 4734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#include "vq_bfin.h" 4834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#endif 4934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 5034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 5134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)int scal_quant(spx_word16_t in, const spx_word16_t *boundary, int entries) 5234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles){ 5334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) int i=0; 5434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) while (i<entries-1 && in>boundary[0]) 5534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 5634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) boundary++; 5734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) i++; 5834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 5934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) return i; 6034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)} 6134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 6234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)int scal_quant32(spx_word32_t in, const spx_word32_t *boundary, int entries) 6334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles){ 6434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) int i=0; 6534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) while (i<entries-1 && in>boundary[0]) 6634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 6734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) boundary++; 6834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) i++; 6934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 7034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) return i; 7134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)} 7234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 7334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 7434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#ifndef OVERRIDE_VQ_NBEST 7534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)/*Finds the indices of the n-best entries in a codebook*/ 7634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)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) 7734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles){ 7834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) int i,j,k,used; 7934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) used = 0; 8034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) for (i=0;i<entries;i++) 8134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 8234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) spx_word32_t dist=0; 8334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) for (j=0;j<len;j++) 8434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) dist = MAC16_16(dist,in[j],*codebook++); 8534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#ifdef FIXED_POINT 8634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) dist=SUB32(SHR32(E[i],1),dist); 8734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#else 8834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) dist=.5f*E[i]-dist; 8934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#endif 9034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) if (i<N || dist<best_dist[N-1]) 9134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 9234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) for (k=N-1; (k >= 1) && (k > used || dist < best_dist[k-1]); k--) 9334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 9434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) best_dist[k]=best_dist[k-1]; 9534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) nbest[k] = nbest[k-1]; 9634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 9734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) best_dist[k]=dist; 9834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) nbest[k]=i; 9934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) used++; 10034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 10134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 10234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)} 10334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#endif 10434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 10534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 10634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 10734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) 10834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#ifndef OVERRIDE_VQ_NBEST_SIGN 10934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)/*Finds the indices of the n-best entries in a codebook with sign*/ 11034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)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) 11134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles){ 11234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) int i,j,k, sign, used; 11334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) used=0; 11434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) for (i=0;i<entries;i++) 11534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 11634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) spx_word32_t dist=0; 11734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) for (j=0;j<len;j++) 11834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) dist = MAC16_16(dist,in[j],*codebook++); 11934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) if (dist>0) 12034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 12134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) sign=0; 12234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) dist=-dist; 12334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } else 12434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 12534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) sign=1; 12634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 12734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#ifdef FIXED_POINT 12834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) dist = ADD32(dist,SHR32(E[i],1)); 12934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#else 13034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) dist = ADD32(dist,.5f*E[i]); 13134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#endif 13234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) if (i<N || dist<best_dist[N-1]) 13334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 13434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) for (k=N-1; (k >= 1) && (k > used || dist < best_dist[k-1]); k--) 13534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) { 13634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) best_dist[k]=best_dist[k-1]; 13734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) nbest[k] = nbest[k-1]; 13834680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 13934680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) best_dist[k]=dist; 14034680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) nbest[k]=i; 14134680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) used++; 14234680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) if (sign) 14334680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) nbest[k]+=entries; 14434680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 14534680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles) } 14634680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)} 14734680572440d7894ef8dafce81d8039ed80726a2Torne (Richard Coles)#endif 148