1 /* 2 * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 /****************************************************************** 12 13 iLBC Speech Coder ANSI-C Source Code 14 15 WebRtcIlbcfix_CbSearch.c 16 17 ******************************************************************/ 18 19 #include "defines.h" 20 #include "gain_quant.h" 21 #include "filtered_cb_vecs.h" 22 #include "constants.h" 23 #include "cb_mem_energy.h" 24 #include "interpolate_samples.h" 25 #include "cb_mem_energy_augmentation.h" 26 #include "cb_search_core.h" 27 #include "energy_inverse.h" 28 #include "augmented_cb_corr.h" 29 #include "cb_update_best_index.h" 30 #include "create_augmented_vec.h" 31 32 /*----------------------------------------------------------------* 33 * Search routine for codebook encoding and gain quantization. 34 *----------------------------------------------------------------*/ 35 36 void WebRtcIlbcfix_CbSearch( 37 iLBC_Enc_Inst_t *iLBCenc_inst, 38 /* (i) the encoder state structure */ 39 int16_t *index, /* (o) Codebook indices */ 40 int16_t *gain_index, /* (o) Gain quantization indices */ 41 int16_t *intarget, /* (i) Target vector for encoding */ 42 int16_t *decResidual,/* (i) Decoded residual for codebook construction */ 43 int16_t lMem, /* (i) Length of buffer */ 44 int16_t lTarget, /* (i) Length of vector */ 45 int16_t *weightDenum,/* (i) weighting filter coefficients in Q12 */ 46 int16_t block /* (i) the subblock number */ 47 ) { 48 int16_t i, j, stage, range; 49 int16_t *pp, scale, tmp; 50 int16_t bits, temp1, temp2; 51 int16_t base_size; 52 int32_t codedEner, targetEner; 53 int16_t gains[CB_NSTAGES+1]; 54 int16_t *cb_vecPtr; 55 int16_t indexOffset, sInd, eInd; 56 int32_t CritMax=0; 57 int16_t shTotMax=WEBRTC_SPL_WORD16_MIN; 58 int16_t bestIndex=0; 59 int16_t bestGain=0; 60 int16_t indexNew, CritNewSh; 61 int32_t CritNew; 62 int32_t *cDotPtr; 63 int16_t noOfZeros; 64 int16_t *gainPtr; 65 int32_t t32, tmpW32; 66 int16_t *WebRtcIlbcfix_kGainSq5_ptr; 67 /* Stack based */ 68 int16_t CBbuf[CB_MEML+LPC_FILTERORDER+CB_HALFFILTERLEN]; 69 int32_t cDot[128]; 70 int32_t Crit[128]; 71 int16_t targetVec[SUBL+LPC_FILTERORDER]; 72 int16_t cbvectors[CB_MEML + 1]; /* Adding one extra position for 73 Coverity warnings. */ 74 int16_t codedVec[SUBL]; 75 int16_t interpSamples[20*4]; 76 int16_t interpSamplesFilt[20*4]; 77 int16_t energyW16[CB_EXPAND*128]; 78 int16_t energyShifts[CB_EXPAND*128]; 79 int16_t *inverseEnergy=energyW16; /* Reuse memory */ 80 int16_t *inverseEnergyShifts=energyShifts; /* Reuse memory */ 81 int16_t *buf = &CBbuf[LPC_FILTERORDER]; 82 int16_t *target = &targetVec[LPC_FILTERORDER]; 83 int16_t *aug_vec = (int16_t*)cDot; /* length [SUBL], reuse memory */ 84 85 /* Determine size of codebook sections */ 86 87 base_size=lMem-lTarget+1; 88 if (lTarget==SUBL) { 89 base_size=lMem-19; 90 } 91 92 /* weighting of the CB memory */ 93 noOfZeros=lMem-WebRtcIlbcfix_kFilterRange[block]; 94 WebRtcSpl_MemSetW16(&buf[-LPC_FILTERORDER], 0, noOfZeros+LPC_FILTERORDER); 95 WebRtcSpl_FilterARFastQ12( 96 decResidual+noOfZeros, buf+noOfZeros, 97 weightDenum, LPC_FILTERORDER+1, WebRtcIlbcfix_kFilterRange[block]); 98 99 /* weighting of the target vector */ 100 WEBRTC_SPL_MEMCPY_W16(&target[-LPC_FILTERORDER], buf+noOfZeros+WebRtcIlbcfix_kFilterRange[block]-LPC_FILTERORDER, LPC_FILTERORDER); 101 WebRtcSpl_FilterARFastQ12( 102 intarget, target, 103 weightDenum, LPC_FILTERORDER+1, lTarget); 104 105 /* Store target, towards the end codedVec is calculated as 106 the initial target minus the remaining target */ 107 WEBRTC_SPL_MEMCPY_W16(codedVec, target, lTarget); 108 109 /* Find the highest absolute value to calculate proper 110 vector scale factor (so that it uses 12 bits) */ 111 temp1 = WebRtcSpl_MaxAbsValueW16(buf, (int16_t)lMem); 112 temp2 = WebRtcSpl_MaxAbsValueW16(target, (int16_t)lTarget); 113 114 if ((temp1>0)&&(temp2>0)) { 115 temp1 = WEBRTC_SPL_MAX(temp1, temp2); 116 scale = WebRtcSpl_GetSizeInBits(WEBRTC_SPL_MUL_16_16(temp1, temp1)); 117 } else { 118 /* temp1 or temp2 is negative (maximum was -32768) */ 119 scale = 30; 120 } 121 122 /* Scale to so that a mul-add 40 times does not overflow */ 123 scale = scale - 25; 124 scale = WEBRTC_SPL_MAX(0, scale); 125 126 /* Compute energy of the original target */ 127 targetEner = WebRtcSpl_DotProductWithScale(target, target, lTarget, scale); 128 129 /* Prepare search over one more codebook section. This section 130 is created by filtering the original buffer with a filter. */ 131 WebRtcIlbcfix_FilteredCbVecs(cbvectors, buf, lMem, WebRtcIlbcfix_kFilterRange[block]); 132 133 range = WebRtcIlbcfix_kSearchRange[block][0]; 134 135 if(lTarget == SUBL) { 136 /* Create the interpolated samples and store them for use in all stages */ 137 138 /* First section, non-filtered half of the cb */ 139 WebRtcIlbcfix_InterpolateSamples(interpSamples, buf, lMem); 140 141 /* Second section, filtered half of the cb */ 142 WebRtcIlbcfix_InterpolateSamples(interpSamplesFilt, cbvectors, lMem); 143 144 /* Compute the CB vectors' energies for the first cb section (non-filtered) */ 145 WebRtcIlbcfix_CbMemEnergyAugmentation(interpSamples, buf, 146 scale, 20, energyW16, energyShifts); 147 148 /* Compute the CB vectors' energies for the second cb section (filtered cb) */ 149 WebRtcIlbcfix_CbMemEnergyAugmentation(interpSamplesFilt, cbvectors, 150 scale, (int16_t)(base_size+20), energyW16, energyShifts); 151 152 /* Compute the CB vectors' energies and store them in the vector 153 * energyW16. Also the corresponding shift values are stored. The 154 * energy values are used in all three stages. */ 155 WebRtcIlbcfix_CbMemEnergy(range, buf, cbvectors, lMem, 156 lTarget, energyW16+20, energyShifts+20, scale, base_size); 157 158 } else { 159 /* Compute the CB vectors' energies and store them in the vector 160 * energyW16. Also the corresponding shift values are stored. The 161 * energy values are used in all three stages. */ 162 WebRtcIlbcfix_CbMemEnergy(range, buf, cbvectors, lMem, 163 lTarget, energyW16, energyShifts, scale, base_size); 164 165 /* Set the energy positions 58-63 and 122-127 to zero 166 (otherwise they are uninitialized) */ 167 WebRtcSpl_MemSetW16(energyW16+range, 0, (base_size-range)); 168 WebRtcSpl_MemSetW16(energyW16+range+base_size, 0, (base_size-range)); 169 } 170 171 /* Calculate Inverse Energy (energyW16 is already normalized 172 and will contain the inverse energy in Q29 after this call */ 173 WebRtcIlbcfix_EnergyInverse(energyW16, base_size*CB_EXPAND); 174 175 /* The gain value computed in the previous stage is used 176 * as an upper limit to what the next stage gain value 177 * is allowed to be. In stage 0, 16384 (1.0 in Q14) is used as 178 * the upper limit. */ 179 gains[0] = 16384; 180 181 for (stage=0; stage<CB_NSTAGES; stage++) { 182 183 /* Set up memories */ 184 range = WebRtcIlbcfix_kSearchRange[block][stage]; 185 186 /* initialize search measures */ 187 CritMax=0; 188 shTotMax=-100; 189 bestIndex=0; 190 bestGain=0; 191 192 /* loop over lags 40+ in the first codebook section, full search */ 193 cb_vecPtr = buf+lMem-lTarget; 194 195 /* Calculate all the cross correlations (augmented part of CB) */ 196 if (lTarget==SUBL) { 197 WebRtcIlbcfix_AugmentedCbCorr(target, buf+lMem, 198 interpSamples, cDot, 199 20, 39, scale); 200 cDotPtr=&cDot[20]; 201 } else { 202 cDotPtr=cDot; 203 } 204 /* Calculate all the cross correlations (main part of CB) */ 205 WebRtcSpl_CrossCorrelation(cDotPtr, target, cb_vecPtr, lTarget, range, scale, -1); 206 207 /* Adjust the search range for the augmented vectors */ 208 if (lTarget==SUBL) { 209 range=WebRtcIlbcfix_kSearchRange[block][stage]+20; 210 } else { 211 range=WebRtcIlbcfix_kSearchRange[block][stage]; 212 } 213 214 indexOffset=0; 215 216 /* Search for best index in this part of the vector */ 217 WebRtcIlbcfix_CbSearchCore( 218 cDot, range, stage, inverseEnergy, 219 inverseEnergyShifts, Crit, 220 &indexNew, &CritNew, &CritNewSh); 221 222 /* Update the global best index and the corresponding gain */ 223 WebRtcIlbcfix_CbUpdateBestIndex( 224 CritNew, CritNewSh, (int16_t)(indexNew+indexOffset), cDot[indexNew+indexOffset], 225 inverseEnergy[indexNew+indexOffset], inverseEnergyShifts[indexNew+indexOffset], 226 &CritMax, &shTotMax, &bestIndex, &bestGain); 227 228 sInd=bestIndex-(int16_t)(CB_RESRANGE>>1); 229 eInd=sInd+CB_RESRANGE; 230 if (sInd<0) { 231 eInd-=sInd; 232 sInd=0; 233 } 234 if (eInd>=range) { 235 eInd=range-1; 236 sInd=eInd-CB_RESRANGE; 237 } 238 239 range = WebRtcIlbcfix_kSearchRange[block][stage]; 240 241 if (lTarget==SUBL) { 242 i=sInd; 243 if (sInd<20) { 244 WebRtcIlbcfix_AugmentedCbCorr(target, cbvectors+lMem, 245 interpSamplesFilt, cDot, 246 (int16_t)(sInd+20), (int16_t)(WEBRTC_SPL_MIN(39, (eInd+20))), scale); 247 i=20; 248 } 249 250 cDotPtr=&cDot[WEBRTC_SPL_MAX(0,(20-sInd))]; 251 cb_vecPtr = cbvectors+lMem-20-i; 252 253 /* Calculate the cross correlations (main part of the filtered CB) */ 254 WebRtcSpl_CrossCorrelation(cDotPtr, target, cb_vecPtr, lTarget, (int16_t)(eInd-i+1), scale, -1); 255 256 } else { 257 cDotPtr = cDot; 258 cb_vecPtr = cbvectors+lMem-lTarget-sInd; 259 260 /* Calculate the cross correlations (main part of the filtered CB) */ 261 WebRtcSpl_CrossCorrelation(cDotPtr, target, cb_vecPtr, lTarget, (int16_t)(eInd-sInd+1), scale, -1); 262 263 } 264 265 /* Adjust the search range for the augmented vectors */ 266 indexOffset=base_size+sInd; 267 268 /* Search for best index in this part of the vector */ 269 WebRtcIlbcfix_CbSearchCore( 270 cDot, (int16_t)(eInd-sInd+1), stage, inverseEnergy+indexOffset, 271 inverseEnergyShifts+indexOffset, Crit, 272 &indexNew, &CritNew, &CritNewSh); 273 274 /* Update the global best index and the corresponding gain */ 275 WebRtcIlbcfix_CbUpdateBestIndex( 276 CritNew, CritNewSh, (int16_t)(indexNew+indexOffset), cDot[indexNew], 277 inverseEnergy[indexNew+indexOffset], inverseEnergyShifts[indexNew+indexOffset], 278 &CritMax, &shTotMax, &bestIndex, &bestGain); 279 280 index[stage] = bestIndex; 281 282 283 bestGain = WebRtcIlbcfix_GainQuant(bestGain, 284 (int16_t)WEBRTC_SPL_ABS_W16(gains[stage]), stage, &gain_index[stage]); 285 286 /* Extract the best (according to measure) codebook vector 287 Also adjust the index, so that the augmented vectors are last. 288 Above these vectors were first... 289 */ 290 291 if(lTarget==(STATE_LEN-iLBCenc_inst->state_short_len)) { 292 293 if(index[stage]<base_size) { 294 pp=buf+lMem-lTarget-index[stage]; 295 } else { 296 pp=cbvectors+lMem-lTarget- 297 index[stage]+base_size; 298 } 299 300 } else { 301 302 if (index[stage]<base_size) { 303 if (index[stage]>=20) { 304 /* Adjust index and extract vector */ 305 index[stage]-=20; 306 pp=buf+lMem-lTarget-index[stage]; 307 } else { 308 /* Adjust index and extract vector */ 309 index[stage]+=(base_size-20); 310 311 WebRtcIlbcfix_CreateAugmentedVec((int16_t)(index[stage]-base_size+40), 312 buf+lMem, aug_vec); 313 pp = aug_vec; 314 315 } 316 } else { 317 318 if ((index[stage] - base_size) >= 20) { 319 /* Adjust index and extract vector */ 320 index[stage]-=20; 321 pp=cbvectors+lMem-lTarget- 322 index[stage]+base_size; 323 } else { 324 /* Adjust index and extract vector */ 325 index[stage]+=(base_size-20); 326 WebRtcIlbcfix_CreateAugmentedVec((int16_t)(index[stage]-2*base_size+40), 327 cbvectors+lMem, aug_vec); 328 pp = aug_vec; 329 } 330 } 331 } 332 333 /* Subtract the best codebook vector, according 334 to measure, from the target vector */ 335 336 WebRtcSpl_AddAffineVectorToVector(target, pp, (int16_t)(-bestGain), (int32_t)8192, (int16_t)14, (int)lTarget); 337 338 /* record quantized gain */ 339 gains[stage+1] = bestGain; 340 341 } /* end of Main Loop. for (stage=0;... */ 342 343 /* Calculte the coded vector (original target - what's left) */ 344 for (i=0;i<lTarget;i++) { 345 codedVec[i]-=target[i]; 346 } 347 348 /* Gain adjustment for energy matching */ 349 codedEner = WebRtcSpl_DotProductWithScale(codedVec, codedVec, lTarget, scale); 350 351 j=gain_index[0]; 352 353 temp1 = (int16_t)WebRtcSpl_NormW32(codedEner); 354 temp2 = (int16_t)WebRtcSpl_NormW32(targetEner); 355 356 if(temp1 < temp2) { 357 bits = 16 - temp1; 358 } else { 359 bits = 16 - temp2; 360 } 361 362 tmp = (int16_t) WEBRTC_SPL_MUL_16_16_RSFT(gains[1],gains[1], 14); 363 364 targetEner = WEBRTC_SPL_MUL_16_16( 365 WEBRTC_SPL_SHIFT_W32(targetEner, -bits), tmp); 366 367 tmpW32 = ((int32_t)(gains[1]-1))<<1; 368 369 /* Pointer to the table that contains 370 gain_sq5TblFIX * gain_sq5TblFIX in Q14 */ 371 gainPtr=(int16_t*)WebRtcIlbcfix_kGainSq5Sq+gain_index[0]; 372 temp1 = (int16_t)WEBRTC_SPL_SHIFT_W32(codedEner, -bits); 373 374 WebRtcIlbcfix_kGainSq5_ptr = (int16_t*)&WebRtcIlbcfix_kGainSq5[j]; 375 376 /* targetEner and codedEner are in Q(-2*scale) */ 377 for (i=gain_index[0];i<32;i++) { 378 379 /* Change the index if 380 (codedEnergy*gainTbl[i]*gainTbl[i])<(targetEn*gain[0]*gain[0]) AND 381 gainTbl[i] < 2*gain[0] 382 */ 383 384 t32 = WEBRTC_SPL_MUL_16_16(temp1, (*gainPtr)); 385 t32 = t32 - targetEner; 386 if (t32 < 0) { 387 if ((*WebRtcIlbcfix_kGainSq5_ptr) < tmpW32) { 388 j=i; 389 WebRtcIlbcfix_kGainSq5_ptr = (int16_t*)&WebRtcIlbcfix_kGainSq5[i]; 390 } 391 } 392 gainPtr++; 393 } 394 gain_index[0]=j; 395 396 return; 397 } 398