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