Update SILK code using the CELT range coder
[opus.git] / src_FLP / SKP_Silk_NLSF_MSVQ_encode_FLP.c
1 /***********************************************************************\r
2 Copyright (c) 2006-2010, Skype Limited. All rights reserved. \r
3 Redistribution and use in source and binary forms, with or without \r
4 modification, (subject to the limitations in the disclaimer below) \r
5 are permitted provided that the following conditions are met:\r
6 - Redistributions of source code must retain the above copyright notice,\r
7 this list of conditions and the following disclaimer.\r
8 - Redistributions in binary form must reproduce the above copyright \r
9 notice, this list of conditions and the following disclaimer in the \r
10 documentation and/or other materials provided with the distribution.\r
11 - Neither the name of Skype Limited, nor the names of specific \r
12 contributors, may be used to endorse or promote products derived from \r
13 this software without specific prior written permission.\r
14 NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE GRANTED \r
15 BY THIS LICENSE. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND \r
16 CONTRIBUTORS ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,\r
17 BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND \r
18 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE \r
19 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, \r
20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF \r
22 USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON \r
23 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT \r
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE \r
25 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
26 ***********************************************************************/\r
27 \r
28 #include "SKP_Silk_main_FLP.h"\r
29 \r
30 /***********************/\r
31 /* NLSF vector encoder */\r
32 /***********************/\r
33 void SKP_Silk_NLSF_MSVQ_encode_FLP(\r
34           SKP_int                   *NLSFIndices,       /* O    Codebook path vector [ CB_STAGES ]      */\r
35           SKP_float                 *pNLSF,             /* I/O  Quantized NLSF vector [ LPC_ORDER ]     */\r
36     const SKP_Silk_NLSF_CB_FLP      *psNLSF_CB_FLP,     /* I    Codebook object                         */\r
37     const SKP_float                 *pNLSF_q_prev,      /* I    Prev. quantized NLSF vector [LPC_ORDER] */\r
38     const SKP_float                 *pW,                /* I    NLSF weight vector [ LPC_ORDER ]        */\r
39     const SKP_float                 NLSF_mu,            /* I    Rate weight for the RD optimization     */\r
40     const SKP_float                 NLSF_mu_fluc_red,   /* I    Fluctuation reduction error weight      */\r
41     const SKP_int                   NLSF_MSVQ_Survivors,/* I    Max survivors from each stage           */\r
42     const SKP_int                   LPC_order,          /* I    LPC order                               */\r
43     const SKP_int                   deactivate_fluc_red /* I    Deactivate fluctuation reduction        */\r
44 )\r
45 {\r
46     SKP_int     i, s, k, cur_survivors, prev_survivors, input_index, cb_index, bestIndex;\r
47     SKP_float   se, wsse, rateDistThreshold, bestRateDist;\r
48     SKP_float   pNLSF_in[ MAX_LPC_ORDER ];\r
49 \r
50 #if( LOW_COMPLEXITY_ONLY == 1 )\r
51     SKP_float   pRateDist[      NLSF_MSVQ_TREE_SEARCH_MAX_VECTORS_EVALUATED_LC_MODE ];\r
52     SKP_float   pRate[          MAX_NLSF_MSVQ_SURVIVORS_LC_MODE ];\r
53     SKP_float   pRate_new[      MAX_NLSF_MSVQ_SURVIVORS_LC_MODE ];\r
54     SKP_int     pTempIndices[   MAX_NLSF_MSVQ_SURVIVORS_LC_MODE ];\r
55     SKP_int     pPath[          MAX_NLSF_MSVQ_SURVIVORS_LC_MODE * NLSF_MSVQ_MAX_CB_STAGES ];\r
56     SKP_int     pPath_new[      MAX_NLSF_MSVQ_SURVIVORS_LC_MODE * NLSF_MSVQ_MAX_CB_STAGES ];\r
57     SKP_float   pRes[           MAX_NLSF_MSVQ_SURVIVORS_LC_MODE * MAX_LPC_ORDER ];\r
58     SKP_float   pRes_new[       MAX_NLSF_MSVQ_SURVIVORS_LC_MODE * MAX_LPC_ORDER ];\r
59 #else\r
60     SKP_float   pRateDist[      NLSF_MSVQ_TREE_SEARCH_MAX_VECTORS_EVALUATED ];\r
61     SKP_float   pRate[          MAX_NLSF_MSVQ_SURVIVORS ];\r
62     SKP_float   pRate_new[      MAX_NLSF_MSVQ_SURVIVORS ];\r
63     SKP_int     pTempIndices[   MAX_NLSF_MSVQ_SURVIVORS ];\r
64     SKP_int     pPath[          MAX_NLSF_MSVQ_SURVIVORS * NLSF_MSVQ_MAX_CB_STAGES ];\r
65     SKP_int     pPath_new[      MAX_NLSF_MSVQ_SURVIVORS * NLSF_MSVQ_MAX_CB_STAGES ];\r
66     SKP_float   pRes[           MAX_NLSF_MSVQ_SURVIVORS * MAX_LPC_ORDER ];\r
67     SKP_float   pRes_new[       MAX_NLSF_MSVQ_SURVIVORS * MAX_LPC_ORDER ];\r
68 #endif\r
69 \r
70     const SKP_float *pConstFloat;\r
71           SKP_float *pFloat;\r
72     const SKP_int   *pConstInt;\r
73           SKP_int   *pInt;\r
74     const SKP_float *pCB_element;\r
75     const SKP_Silk_NLSF_CBS_FLP *pCurrentCBStage;\r
76 \r
77     SKP_assert( NLSF_MSVQ_Survivors <= MAX_NLSF_MSVQ_SURVIVORS );\r
78     SKP_assert( ( LOW_COMPLEXITY_ONLY == 0 ) || ( NLSF_MSVQ_Survivors <= MAX_NLSF_MSVQ_SURVIVORS_LC_MODE ) );\r
79 \r
80     cur_survivors = NLSF_MSVQ_Survivors;\r
81 \r
82 \r
83 \r
84     /* Copy the input vector */\r
85     SKP_memcpy( pNLSF_in, pNLSF, LPC_order * sizeof(SKP_float) );\r
86 \r
87     /****************************************************/\r
88     /* Tree search for the multi-stage vector quantizer */\r
89     /****************************************************/\r
90 \r
91     /* Clear accumulated rates */\r
92     SKP_memset( pRate, 0, NLSF_MSVQ_Survivors * sizeof( SKP_float ) );\r
93     \r
94     /* Copy NLSFs into residual signal vector */\r
95     SKP_memcpy( pRes, pNLSF, LPC_order * sizeof( SKP_float ) );\r
96 \r
97     /* Set first stage values */\r
98     prev_survivors = 1;\r
99 \r
100     /* Loop over all stages */\r
101     for( s = 0; s < psNLSF_CB_FLP->nStages; s++ ) {\r
102 \r
103         /* Set a pointer to the current stage codebook */\r
104         pCurrentCBStage = &psNLSF_CB_FLP->CBStages[ s ];\r
105 \r
106         /* Calculate the number of survivors in the current stage */\r
107         cur_survivors = SKP_min_32( NLSF_MSVQ_Survivors, prev_survivors * pCurrentCBStage->nVectors );\r
108 \r
109 #if( NLSF_MSVQ_FLUCTUATION_REDUCTION == 0 )\r
110         /* Find a single best survivor in the last stage, if we */\r
111         /* do not need candidates for fluctuation reduction     */\r
112         if( s == psNLSF_CB_FLP->nStages - 1 ) {\r
113             cur_survivors = 1;\r
114         }\r
115 #endif\r
116         /* Nearest neighbor clustering for multiple input data vectors */\r
117         SKP_Silk_NLSF_VQ_rate_distortion_FLP( pRateDist, pCurrentCBStage, pRes, pW, pRate, NLSF_mu, prev_survivors, LPC_order );\r
118 \r
119         /* Sort the rate-distortion errors */\r
120         SKP_Silk_insertion_sort_increasing_FLP( pRateDist, pTempIndices, prev_survivors * pCurrentCBStage->nVectors, cur_survivors );\r
121 \r
122         /* Discard survivors with rate-distortion values too far above the best one */\r
123         rateDistThreshold = NLSF_MSVQ_SURV_MAX_REL_RD * pRateDist[ 0 ];\r
124         while( pRateDist[ cur_survivors - 1 ] > rateDistThreshold && cur_survivors > 1 ) {\r
125             cur_survivors--;\r
126         }\r
127 \r
128         /* Update accumulated codebook contributions for the 'cur_survivors' best codebook indices */\r
129         for( k = 0; k < cur_survivors; k++ ) { \r
130             if( s > 0 ) {\r
131                 /* Find the indices of the input and the codebook vector */\r
132                 if( pCurrentCBStage->nVectors == 8 ) {\r
133                     input_index = SKP_RSHIFT( pTempIndices[ k ], 3 );\r
134                     cb_index    = pTempIndices[ k ] & 7;\r
135                 } else {\r
136                     input_index = pTempIndices[ k ] / pCurrentCBStage->nVectors;  \r
137                     cb_index    = pTempIndices[ k ] - input_index * pCurrentCBStage->nVectors;\r
138                 }\r
139             } else {\r
140                 /* Find the indices of the input and the codebook vector */\r
141                 input_index = 0;\r
142                 cb_index    = pTempIndices[ k ];\r
143             }\r
144 \r
145             /* Subtract new contribution from the previous residual vector for each of 'cur_survivors' */\r
146             pConstFloat = &pRes[ input_index * LPC_order ];\r
147             pCB_element = &pCurrentCBStage->CB[ cb_index * LPC_order ];\r
148             pFloat      = &pRes_new[ k * LPC_order ];\r
149             for( i = 0; i < LPC_order; i++ ) {\r
150                 pFloat[ i ] = pConstFloat[ i ] - pCB_element[ i ];\r
151             }\r
152 \r
153             /* Update accumulated rate for stage 1 to the current */\r
154             pRate_new[ k ] = pRate[ input_index ] + pCurrentCBStage->Rates[ cb_index ];\r
155 \r
156             /* Copy paths from previous matrix, starting with the best path */\r
157             pConstInt = &pPath[ input_index * psNLSF_CB_FLP->nStages ];\r
158             pInt      = &pPath_new[       k * psNLSF_CB_FLP->nStages ];\r
159             for( i = 0; i < s; i++ ) {\r
160                 pInt[ i ] = pConstInt[ i ];\r
161             }\r
162             /* Write the current stage indices for the 'cur_survivors' to the best path matrix */\r
163             pInt[ s ] = cb_index;\r
164         }\r
165 \r
166         if( s < psNLSF_CB_FLP->nStages - 1 ) {\r
167             /* Copy NLSF residual matrix for next stage */\r
168             SKP_memcpy(pRes, pRes_new, cur_survivors * LPC_order * sizeof( SKP_float ) );\r
169 \r
170             /* Copy rate vector for next stage */\r
171             SKP_memcpy(pRate, pRate_new, cur_survivors * sizeof( SKP_float ) );\r
172 \r
173             /* Copy best path matrix for next stage */\r
174             SKP_memcpy(pPath, pPath_new, cur_survivors * psNLSF_CB_FLP->nStages * sizeof( SKP_int ) );\r
175         }\r
176 \r
177         prev_survivors = cur_survivors;\r
178     }\r
179 \r
180     /* (Preliminary) index of the best survivor, later to be decoded */\r
181     bestIndex = 0;\r
182 \r
183 #if( NLSF_MSVQ_FLUCTUATION_REDUCTION == 1 )\r
184     /******************************/\r
185     /* NLSF fluctuation reduction */\r
186     /******************************/\r
187     if( deactivate_fluc_red != 1 ) {\r
188     \r
189         /* Search among all survivors, now taking also weighted fluctuation errors into account */\r
190         bestRateDist = SKP_float_MAX;\r
191         for( s = 0; s < cur_survivors; s++ ) {\r
192             /* Decode survivor to compare with previous quantized NLSF vector */\r
193             SKP_Silk_NLSF_MSVQ_decode_FLP( pNLSF, psNLSF_CB_FLP, &pPath_new[ s * psNLSF_CB_FLP->nStages ], LPC_order );\r
194 \r
195             /* Compare decoded NLSF vector with the previously quantized vector */ \r
196             wsse = 0;\r
197             for( i = 0; i < LPC_order; i += 2 ) {\r
198                 /* Compute weighted squared quantization error for index i */\r
199                 se = pNLSF[ i ] - pNLSF_q_prev[ i ];\r
200                 wsse += pW[ i ] * se * se;\r
201 \r
202                 /* Compute weighted squared quantization error for index i + 1 */\r
203                 se = pNLSF[ i + 1 ] - pNLSF_q_prev[ i + 1 ];\r
204                 wsse += pW[ i + 1 ] * se * se;\r
205             }\r
206 \r
207             /* Add the fluctuation reduction penalty to the rate distortion error */\r
208             wsse = pRateDist[s] + wsse * NLSF_mu_fluc_red;\r
209 \r
210             /* Keep index of best survivor */\r
211             if( wsse < bestRateDist ) {\r
212                 bestRateDist = wsse;\r
213                 bestIndex = s;\r
214             }\r
215         }\r
216     }\r
217 #endif\r
218 \r
219     /* Copy best path to output argument */\r
220     SKP_memcpy( NLSFIndices, &pPath_new[ bestIndex * psNLSF_CB_FLP->nStages ], psNLSF_CB_FLP->nStages * sizeof( SKP_int ) );\r
221 \r
222     /* Decode and stabilize the best survivor */\r
223     SKP_Silk_NLSF_MSVQ_decode_FLP( pNLSF, psNLSF_CB_FLP, NLSFIndices, LPC_order );\r
224 \r
225 }\r