]>
git.gir.st - tmk_keyboard.git/blob - tmk_core/tool/mbed/mbed-sdk/libraries/dsp/cmsis_dsp/FilteringFunctions/arm_correlate_fast_q31.c
1 /* ----------------------------------------------------------------------
2 * Copyright (C) 2010-2013 ARM Limited. All rights reserved.
4 * $Date: 17. January 2013
7 * Project: CMSIS DSP Library
8 * Title: arm_correlate_fast_q31.c
10 * Description: Fast Q31 Correlation.
12 * Target Processor: Cortex-M4/Cortex-M3
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions
17 * - Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 * - Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in
21 * the documentation and/or other materials provided with the
23 * - Neither the name of ARM LIMITED nor the names of its contributors
24 * may be used to endorse or promote products derived from this
25 * software without specific prior written permission.
27 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
29 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
30 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
31 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
32 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
33 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
34 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
35 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
37 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
38 * POSSIBILITY OF SUCH DAMAGE.
39 * -------------------------------------------------------------------- */
44 * @ingroup groupFilters
53 * @brief Correlation of Q31 sequences (fast version) for Cortex-M3 and Cortex-M4.
54 * @param[in] *pSrcA points to the first input sequence.
55 * @param[in] srcALen length of the first input sequence.
56 * @param[in] *pSrcB points to the second input sequence.
57 * @param[in] srcBLen length of the second input sequence.
58 * @param[out] *pDst points to the location where the output result is written. Length 2 * max(srcALen, srcBLen) - 1.
62 * <b>Scaling and Overflow Behavior:</b>
65 * This function is optimized for speed at the expense of fixed-point precision and overflow protection.
66 * The result of each 1.31 x 1.31 multiplication is truncated to 2.30 format.
67 * These intermediate results are accumulated in a 32-bit register in 2.30 format.
68 * Finally, the accumulator is saturated and converted to a 1.31 result.
71 * The fast version has the same overflow behavior as the standard version but provides less precision since it discards the low 32 bits of each multiplication result.
72 * In order to avoid overflows completely the input signals must be scaled down.
73 * The input signals should be scaled down to avoid intermediate overflows.
74 * Scale down one of the inputs by 1/min(srcALen, srcBLen)to avoid overflows since a
75 * maximum of min(srcALen, srcBLen) number of additions is carried internally.
78 * See <code>arm_correlate_q31()</code> for a slower implementation of this function which uses 64-bit accumulation to provide higher precision.
81 void arm_correlate_fast_q31 (
88 q31_t
* pIn1
; /* inputA pointer */
89 q31_t
* pIn2
; /* inputB pointer */
90 q31_t
* pOut
= pDst
; /* output pointer */
91 q31_t
* px
; /* Intermediate inputA pointer */
92 q31_t
* py
; /* Intermediate inputB pointer */
93 q31_t
* pSrc1
; /* Intermediate pointers */
94 q31_t sum
, acc0
, acc1
, acc2
, acc3
; /* Accumulators */
95 q31_t x0
, x1
, x2
, x3
, c0
; /* temporary variables for holding input and coefficient values */
96 uint32_t j
, k
= 0u , count
, blkCnt
, outBlockSize
, blockSize1
, blockSize2
, blockSize3
; /* loop counter */
97 int32_t inc
= 1 ; /* Destination address modifier */
100 /* The algorithm implementation is based on the lengths of the inputs. */
101 /* srcB is always made to slide across srcA. */
102 /* So srcBLen is always considered as shorter or equal to srcALen */
103 if ( srcALen
>= srcBLen
)
105 /* Initialization of inputA pointer */
108 /* Initialization of inputB pointer */
111 /* Number of output samples is calculated */
112 outBlockSize
= ( 2u * srcALen
) - 1u ;
114 /* When srcALen > srcBLen, zero padding is done to srcB
115 * to make their lengths equal.
116 * Instead, (outBlockSize - (srcALen + srcBLen - 1))
117 * number of output samples are made zero */
118 j
= outBlockSize
- ( srcALen
+ ( srcBLen
- 1u ));
120 /* Updating the pointer position to non zero value */
126 /* Initialization of inputA pointer */
129 /* Initialization of inputB pointer */
132 /* srcBLen is always considered as shorter or equal to srcALen */
137 /* CORR(x, y) = Reverse order(CORR(y, x)) */
138 /* Hence set the destination pointer to point to the last output sample */
139 pOut
= pDst
+ (( srcALen
+ srcBLen
) - 2u );
141 /* Destination address modifier is set to -1 */
146 /* The function is internally
147 * divided into three parts according to the number of multiplications that has to be
148 * taken place between inputA samples and inputB samples. In the first part of the
149 * algorithm, the multiplications increase by one for every iteration.
150 * In the second part of the algorithm, srcBLen number of multiplications are done.
151 * In the third part of the algorithm, the multiplications decrease by one
152 * for every iteration.*/
153 /* The algorithm is implemented in three stages.
154 * The loop counters of each stage is initiated here. */
155 blockSize1
= srcBLen
- 1u ;
156 blockSize2
= srcALen
- ( srcBLen
- 1u );
157 blockSize3
= blockSize1
;
159 /* --------------------------
160 * Initializations of stage1
161 * -------------------------*/
163 /* sum = x[0] * y[srcBlen - 1]
164 * sum = x[0] * y[srcBlen - 2] + x[1] * y[srcBlen - 1]
166 * sum = x[0] * y[0] + x[1] * y[1] +...+ x[srcBLen - 1] * y[srcBLen - 1]
169 /* In this stage the MAC operations are increased by 1 for every iteration.
170 The count variable holds the number of MAC operations performed */
173 /* Working pointer of inputA */
176 /* Working pointer of inputB */
177 pSrc1
= pIn2
+ ( srcBLen
- 1u );
180 /* ------------------------
182 * ----------------------*/
184 /* The first stage starts here */
185 while ( blockSize1
> 0u )
187 /* Accumulator is made zero for every iteration */
190 /* Apply loop unrolling and compute 4 MACs simultaneously. */
193 /* First part of the processing with loop unrolling. Compute 4 MACs at a time.
194 ** a second loop below computes MACs for the remaining 1 to 3 samples. */
197 /* x[0] * y[srcBLen - 4] */
198 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
199 (( q63_t
) * px
++ * (* py
++))) >> 32 );
200 /* x[1] * y[srcBLen - 3] */
201 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
202 (( q63_t
) * px
++ * (* py
++))) >> 32 );
203 /* x[2] * y[srcBLen - 2] */
204 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
205 (( q63_t
) * px
++ * (* py
++))) >> 32 );
206 /* x[3] * y[srcBLen - 1] */
207 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
208 (( q63_t
) * px
++ * (* py
++))) >> 32 );
210 /* Decrement the loop counter */
214 /* If the count is not a multiple of 4, compute any remaining MACs here.
215 ** No loop unrolling is used. */
220 /* Perform the multiply-accumulates */
221 /* x[0] * y[srcBLen - 1] */
222 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
223 (( q63_t
) * px
++ * (* py
++))) >> 32 );
225 /* Decrement the loop counter */
229 /* Store the result in the accumulator in the destination buffer. */
231 /* Destination pointer is updated according to the address modifier, inc */
234 /* Update the inputA and inputB pointers for next MAC calculation */
238 /* Increment the MAC count */
241 /* Decrement the loop counter */
245 /* --------------------------
246 * Initializations of stage2
247 * ------------------------*/
249 /* sum = x[0] * y[0] + x[1] * y[1] +...+ x[srcBLen-1] * y[srcBLen-1]
250 * sum = x[1] * y[0] + x[2] * y[1] +...+ x[srcBLen] * y[srcBLen-1]
252 * sum = x[srcALen-srcBLen-2] * y[0] + x[srcALen-srcBLen-1] * y[1] +...+ x[srcALen-1] * y[srcBLen-1]
255 /* Working pointer of inputA */
258 /* Working pointer of inputB */
261 /* count is index by which the pointer pIn1 to be incremented */
264 /* -------------------
266 * ------------------*/
268 /* Stage2 depends on srcBLen as in this stage srcBLen number of MACS are performed.
269 * So, to loop unroll over blockSize2,
270 * srcBLen should be greater than or equal to 4 */
273 /* Loop unroll over blockSize2, by 4 */
274 blkCnt
= blockSize2
>> 2u ;
278 /* Set all accumulators to zero */
284 /* read x[0], x[1], x[2] samples */
289 /* Apply loop unrolling and compute 4 MACs simultaneously. */
292 /* First part of the processing with loop unrolling. Compute 4 MACs at a time.
293 ** a second loop below computes MACs for the remaining 1 to 3 samples. */
296 /* Read y[0] sample */
299 /* Read x[3] sample */
302 /* Perform the multiply-accumulate */
303 /* acc0 += x[0] * y[0] */
304 acc0
= ( q31_t
) (((( q63_t
) acc0
<< 32 ) + (( q63_t
) x0
* c0
)) >> 32 );
305 /* acc1 += x[1] * y[0] */
306 acc1
= ( q31_t
) (((( q63_t
) acc1
<< 32 ) + (( q63_t
) x1
* c0
)) >> 32 );
307 /* acc2 += x[2] * y[0] */
308 acc2
= ( q31_t
) (((( q63_t
) acc2
<< 32 ) + (( q63_t
) x2
* c0
)) >> 32 );
309 /* acc3 += x[3] * y[0] */
310 acc3
= ( q31_t
) (((( q63_t
) acc3
<< 32 ) + (( q63_t
) x3
* c0
)) >> 32 );
312 /* Read y[1] sample */
315 /* Read x[4] sample */
318 /* Perform the multiply-accumulates */
319 /* acc0 += x[1] * y[1] */
320 acc0
= ( q31_t
) (((( q63_t
) acc0
<< 32 ) + (( q63_t
) x1
* c0
)) >> 32 );
321 /* acc1 += x[2] * y[1] */
322 acc1
= ( q31_t
) (((( q63_t
) acc1
<< 32 ) + (( q63_t
) x2
* c0
)) >> 32 );
323 /* acc2 += x[3] * y[1] */
324 acc2
= ( q31_t
) (((( q63_t
) acc2
<< 32 ) + (( q63_t
) x3
* c0
)) >> 32 );
325 /* acc3 += x[4] * y[1] */
326 acc3
= ( q31_t
) (((( q63_t
) acc3
<< 32 ) + (( q63_t
) x0
* c0
)) >> 32 );
328 /* Read y[2] sample */
331 /* Read x[5] sample */
334 /* Perform the multiply-accumulates */
335 /* acc0 += x[2] * y[2] */
336 acc0
= ( q31_t
) (((( q63_t
) acc0
<< 32 ) + (( q63_t
) x2
* c0
)) >> 32 );
337 /* acc1 += x[3] * y[2] */
338 acc1
= ( q31_t
) (((( q63_t
) acc1
<< 32 ) + (( q63_t
) x3
* c0
)) >> 32 );
339 /* acc2 += x[4] * y[2] */
340 acc2
= ( q31_t
) (((( q63_t
) acc2
<< 32 ) + (( q63_t
) x0
* c0
)) >> 32 );
341 /* acc3 += x[5] * y[2] */
342 acc3
= ( q31_t
) (((( q63_t
) acc3
<< 32 ) + (( q63_t
) x1
* c0
)) >> 32 );
344 /* Read y[3] sample */
347 /* Read x[6] sample */
350 /* Perform the multiply-accumulates */
351 /* acc0 += x[3] * y[3] */
352 acc0
= ( q31_t
) (((( q63_t
) acc0
<< 32 ) + (( q63_t
) x3
* c0
)) >> 32 );
353 /* acc1 += x[4] * y[3] */
354 acc1
= ( q31_t
) (((( q63_t
) acc1
<< 32 ) + (( q63_t
) x0
* c0
)) >> 32 );
355 /* acc2 += x[5] * y[3] */
356 acc2
= ( q31_t
) (((( q63_t
) acc2
<< 32 ) + (( q63_t
) x1
* c0
)) >> 32 );
357 /* acc3 += x[6] * y[3] */
358 acc3
= ( q31_t
) (((( q63_t
) acc3
<< 32 ) + (( q63_t
) x2
* c0
)) >> 32 );
363 /* If the srcBLen is not a multiple of 4, compute any remaining MACs here.
364 ** No loop unrolling is used. */
369 /* Read y[4] sample */
372 /* Read x[7] sample */
375 /* Perform the multiply-accumulates */
376 /* acc0 += x[4] * y[4] */
377 acc0
= ( q31_t
) (((( q63_t
) acc0
<< 32 ) + (( q63_t
) x0
* c0
)) >> 32 );
378 /* acc1 += x[5] * y[4] */
379 acc1
= ( q31_t
) (((( q63_t
) acc1
<< 32 ) + (( q63_t
) x1
* c0
)) >> 32 );
380 /* acc2 += x[6] * y[4] */
381 acc2
= ( q31_t
) (((( q63_t
) acc2
<< 32 ) + (( q63_t
) x2
* c0
)) >> 32 );
382 /* acc3 += x[7] * y[4] */
383 acc3
= ( q31_t
) (((( q63_t
) acc3
<< 32 ) + (( q63_t
) x3
* c0
)) >> 32 );
385 /* Reuse the present samples for the next MAC */
390 /* Decrement the loop counter */
394 /* Store the result in the accumulator in the destination buffer. */
395 * pOut
= ( q31_t
) ( acc0
<< 1 );
396 /* Destination pointer is updated according to the address modifier, inc */
399 * pOut
= ( q31_t
) ( acc1
<< 1 );
402 * pOut
= ( q31_t
) ( acc2
<< 1 );
405 * pOut
= ( q31_t
) ( acc3
<< 1 );
408 /* Increment the pointer pIn1 index, count by 4 */
411 /* Update the inputA and inputB pointers for next MAC calculation */
416 /* Decrement the loop counter */
420 /* If the blockSize2 is not a multiple of 4, compute any remaining output samples here.
421 ** No loop unrolling is used. */
422 blkCnt
= blockSize2
% 0x4 u
;
426 /* Accumulator is made zero for every iteration */
429 /* Apply loop unrolling and compute 4 MACs simultaneously. */
432 /* First part of the processing with loop unrolling. Compute 4 MACs at a time.
433 ** a second loop below computes MACs for the remaining 1 to 3 samples. */
436 /* Perform the multiply-accumulates */
437 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
438 (( q63_t
) * px
++ * (* py
++))) >> 32 );
439 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
440 (( q63_t
) * px
++ * (* py
++))) >> 32 );
441 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
442 (( q63_t
) * px
++ * (* py
++))) >> 32 );
443 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
444 (( q63_t
) * px
++ * (* py
++))) >> 32 );
446 /* Decrement the loop counter */
450 /* If the srcBLen is not a multiple of 4, compute any remaining MACs here.
451 ** No loop unrolling is used. */
456 /* Perform the multiply-accumulate */
457 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
458 (( q63_t
) * px
++ * (* py
++))) >> 32 );
460 /* Decrement the loop counter */
464 /* Store the result in the accumulator in the destination buffer. */
466 /* Destination pointer is updated according to the address modifier, inc */
469 /* Increment the MAC count */
472 /* Update the inputA and inputB pointers for next MAC calculation */
477 /* Decrement the loop counter */
483 /* If the srcBLen is not a multiple of 4,
484 * the blockSize2 loop cannot be unrolled by 4 */
489 /* Accumulator is made zero for every iteration */
492 /* Loop over srcBLen */
497 /* Perform the multiply-accumulate */
498 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
499 (( q63_t
) * px
++ * (* py
++))) >> 32 );
501 /* Decrement the loop counter */
505 /* Store the result in the accumulator in the destination buffer. */
507 /* Destination pointer is updated according to the address modifier, inc */
510 /* Increment the MAC count */
513 /* Update the inputA and inputB pointers for next MAC calculation */
517 /* Decrement the loop counter */
522 /* --------------------------
523 * Initializations of stage3
524 * -------------------------*/
526 /* sum += x[srcALen-srcBLen+1] * y[0] + x[srcALen-srcBLen+2] * y[1] +...+ x[srcALen-1] * y[srcBLen-1]
527 * sum += x[srcALen-srcBLen+2] * y[0] + x[srcALen-srcBLen+3] * y[1] +...+ x[srcALen-1] * y[srcBLen-1]
529 * sum += x[srcALen-2] * y[0] + x[srcALen-1] * y[1]
530 * sum += x[srcALen-1] * y[0]
533 /* In this stage the MAC operations are decreased by 1 for every iteration.
534 The count variable holds the number of MAC operations performed */
535 count
= srcBLen
- 1u ;
537 /* Working pointer of inputA */
538 pSrc1
= (( pIn1
+ srcALen
) - srcBLen
) + 1u ;
541 /* Working pointer of inputB */
544 /* -------------------
546 * ------------------*/
548 while ( blockSize3
> 0u )
550 /* Accumulator is made zero for every iteration */
553 /* Apply loop unrolling and compute 4 MACs simultaneously. */
556 /* First part of the processing with loop unrolling. Compute 4 MACs at a time.
557 ** a second loop below computes MACs for the remaining 1 to 3 samples. */
560 /* Perform the multiply-accumulates */
561 /* sum += x[srcALen - srcBLen + 4] * y[3] */
562 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
563 (( q63_t
) * px
++ * (* py
++))) >> 32 );
564 /* sum += x[srcALen - srcBLen + 3] * y[2] */
565 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
566 (( q63_t
) * px
++ * (* py
++))) >> 32 );
567 /* sum += x[srcALen - srcBLen + 2] * y[1] */
568 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
569 (( q63_t
) * px
++ * (* py
++))) >> 32 );
570 /* sum += x[srcALen - srcBLen + 1] * y[0] */
571 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
572 (( q63_t
) * px
++ * (* py
++))) >> 32 );
574 /* Decrement the loop counter */
578 /* If the count is not a multiple of 4, compute any remaining MACs here.
579 ** No loop unrolling is used. */
584 /* Perform the multiply-accumulates */
585 sum
= ( q31_t
) (((( q63_t
) sum
<< 32 ) +
586 (( q63_t
) * px
++ * (* py
++))) >> 32 );
588 /* Decrement the loop counter */
592 /* Store the result in the accumulator in the destination buffer. */
594 /* Destination pointer is updated according to the address modifier, inc */
597 /* Update the inputA and inputB pointers for next MAC calculation */
601 /* Decrement the MAC count */
604 /* Decrement the loop counter */
611 * @} end of Corr group