]>
git.gir.st - tmk_keyboard.git/blob - tmk_core/tool/mbed/mbed-sdk/libraries/dsp/cmsis_dsp/FilteringFunctions/arm_correlate_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_q31.c
10 * Description: Correlation of Q31 sequences.
12 * Target Processor: Cortex-M4/Cortex-M3/Cortex-M0
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.
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 * The function is implemented using an internal 64-bit accumulator.
66 * The accumulator has a 2.62 format and maintains full precision of the intermediate multiplication results but provides only a single guard bit.
67 * There is no saturation on intermediate additions.
68 * Thus, if the accumulator overflows it wraps around and distorts the result.
69 * The input signals should be scaled down to avoid intermediate overflows.
70 * Scale down one of the inputs by 1/min(srcALen, srcBLen)to avoid overflows since a
71 * maximum of min(srcALen, srcBLen) number of additions is carried internally.
72 * The 2.62 accumulator is right shifted by 31 bits and saturated to 1.31 format to yield the final result.
75 * See <code>arm_correlate_fast_q31()</code> for a faster but less precise implementation of this function for Cortex-M3 and Cortex-M4.
78 void arm_correlate_q31(
86 #ifndef ARM_MATH_CM0_FAMILY
88 /* Run the below code for Cortex-M4 and Cortex-M3 */
90 q31_t
*pIn1
; /* inputA pointer */
91 q31_t
*pIn2
; /* inputB pointer */
92 q31_t
*pOut
= pDst
; /* output pointer */
93 q31_t
*px
; /* Intermediate inputA pointer */
94 q31_t
*py
; /* Intermediate inputB pointer */
95 q31_t
*pSrc1
; /* Intermediate pointers */
96 q63_t sum
, acc0
, acc1
, acc2
; /* Accumulators */
97 q31_t x0
, x1
, x2
, c0
; /* temporary variables for holding input and coefficient values */
98 uint32_t j
, k
= 0u, count
, blkCnt
, outBlockSize
, blockSize1
, blockSize2
, blockSize3
; /* loop counter */
99 int32_t inc
= 1; /* Destination address modifier */
102 /* The algorithm implementation is based on the lengths of the inputs. */
103 /* srcB is always made to slide across srcA. */
104 /* So srcBLen is always considered as shorter or equal to srcALen */
105 /* But CORR(x, y) is reverse of CORR(y, x) */
106 /* So, when srcBLen > srcALen, output pointer is made to point to the end of the output buffer */
107 /* and the destination pointer modifier, inc is set to -1 */
108 /* If srcALen > srcBLen, zero pad has to be done to srcB to make the two inputs of same length */
109 /* But to improve the performance,
110 * we include zeroes in the output instead of zero padding either of the the inputs*/
111 /* If srcALen > srcBLen,
112 * (srcALen - srcBLen) zeroes has to included in the starting of the output buffer */
113 /* If srcALen < srcBLen,
114 * (srcALen - srcBLen) zeroes has to included in the ending of the output buffer */
115 if(srcALen
>= srcBLen
)
117 /* Initialization of inputA pointer */
120 /* Initialization of inputB pointer */
123 /* Number of output samples is calculated */
124 outBlockSize
= (2u * srcALen
) - 1u;
126 /* When srcALen > srcBLen, zero padding is done to srcB
127 * to make their lengths equal.
128 * Instead, (outBlockSize - (srcALen + srcBLen - 1))
129 * number of output samples are made zero */
130 j
= outBlockSize
- (srcALen
+ (srcBLen
- 1u));
132 /* Updating the pointer position to non zero value */
138 /* Initialization of inputA pointer */
141 /* Initialization of inputB pointer */
144 /* srcBLen is always considered as shorter or equal to srcALen */
149 /* CORR(x, y) = Reverse order(CORR(y, x)) */
150 /* Hence set the destination pointer to point to the last output sample */
151 pOut
= pDst
+ ((srcALen
+ srcBLen
) - 2u);
153 /* Destination address modifier is set to -1 */
158 /* The function is internally
159 * divided into three parts according to the number of multiplications that has to be
160 * taken place between inputA samples and inputB samples. In the first part of the
161 * algorithm, the multiplications increase by one for every iteration.
162 * In the second part of the algorithm, srcBLen number of multiplications are done.
163 * In the third part of the algorithm, the multiplications decrease by one
164 * for every iteration.*/
165 /* The algorithm is implemented in three stages.
166 * The loop counters of each stage is initiated here. */
167 blockSize1
= srcBLen
- 1u;
168 blockSize2
= srcALen
- (srcBLen
- 1u);
169 blockSize3
= blockSize1
;
171 /* --------------------------
172 * Initializations of stage1
173 * -------------------------*/
175 /* sum = x[0] * y[srcBlen - 1]
176 * sum = x[0] * y[srcBlen - 2] + x[1] * y[srcBlen - 1]
178 * sum = x[0] * y[0] + x[1] * y[1] +...+ x[srcBLen - 1] * y[srcBLen - 1]
181 /* In this stage the MAC operations are increased by 1 for every iteration.
182 The count variable holds the number of MAC operations performed */
185 /* Working pointer of inputA */
188 /* Working pointer of inputB */
189 pSrc1
= pIn2
+ (srcBLen
- 1u);
192 /* ------------------------
194 * ----------------------*/
196 /* The first stage starts here */
197 while(blockSize1
> 0u)
199 /* Accumulator is made zero for every iteration */
202 /* Apply loop unrolling and compute 4 MACs simultaneously. */
205 /* First part of the processing with loop unrolling. Compute 4 MACs at a time.
206 ** a second loop below computes MACs for the remaining 1 to 3 samples. */
209 /* x[0] * y[srcBLen - 4] */
210 sum
+= (q63_t
) * px
++ * (*py
++);
211 /* x[1] * y[srcBLen - 3] */
212 sum
+= (q63_t
) * px
++ * (*py
++);
213 /* x[2] * y[srcBLen - 2] */
214 sum
+= (q63_t
) * px
++ * (*py
++);
215 /* x[3] * y[srcBLen - 1] */
216 sum
+= (q63_t
) * px
++ * (*py
++);
218 /* Decrement the loop counter */
222 /* If the count is not a multiple of 4, compute any remaining MACs here.
223 ** No loop unrolling is used. */
228 /* Perform the multiply-accumulates */
229 /* x[0] * y[srcBLen - 1] */
230 sum
+= (q63_t
) * px
++ * (*py
++);
232 /* Decrement the loop counter */
236 /* Store the result in the accumulator in the destination buffer. */
237 *pOut
= (q31_t
) (sum
>> 31);
238 /* Destination pointer is updated according to the address modifier, inc */
241 /* Update the inputA and inputB pointers for next MAC calculation */
245 /* Increment the MAC count */
248 /* Decrement the loop counter */
252 /* --------------------------
253 * Initializations of stage2
254 * ------------------------*/
256 /* sum = x[0] * y[0] + x[1] * y[1] +...+ x[srcBLen-1] * y[srcBLen-1]
257 * sum = x[1] * y[0] + x[2] * y[1] +...+ x[srcBLen] * y[srcBLen-1]
259 * sum = x[srcALen-srcBLen-2] * y[0] + x[srcALen-srcBLen-1] * y[1] +...+ x[srcALen-1] * y[srcBLen-1]
262 /* Working pointer of inputA */
265 /* Working pointer of inputB */
268 /* count is index by which the pointer pIn1 to be incremented */
271 /* -------------------
273 * ------------------*/
275 /* Stage2 depends on srcBLen as in this stage srcBLen number of MACS are performed.
276 * So, to loop unroll over blockSize2,
277 * srcBLen should be greater than or equal to 4 */
280 /* Loop unroll by 3 */
281 blkCnt
= blockSize2
/ 3;
285 /* Set all accumulators to zero */
290 /* read x[0], x[1] samples */
294 /* Apply loop unrolling and compute 3 MACs simultaneously. */
297 /* First part of the processing with loop unrolling. Compute 3 MACs at a time.
298 ** a second loop below computes MACs for the remaining 1 to 2 samples. */
301 /* Read y[0] sample */
304 /* Read x[2] sample */
307 /* Perform the multiply-accumulate */
308 /* acc0 += x[0] * y[0] */
309 acc0
+= ((q63_t
) x0
* c0
);
310 /* acc1 += x[1] * y[0] */
311 acc1
+= ((q63_t
) x1
* c0
);
312 /* acc2 += x[2] * y[0] */
313 acc2
+= ((q63_t
) x2
* c0
);
315 /* Read y[1] sample */
318 /* Read x[3] sample */
321 /* Perform the multiply-accumulates */
322 /* acc0 += x[1] * y[1] */
323 acc0
+= ((q63_t
) x1
* c0
);
324 /* acc1 += x[2] * y[1] */
325 acc1
+= ((q63_t
) x2
* c0
);
326 /* acc2 += x[3] * y[1] */
327 acc2
+= ((q63_t
) x0
* c0
);
329 /* Read y[2] sample */
332 /* Read x[4] sample */
335 /* Perform the multiply-accumulates */
336 /* acc0 += x[2] * y[2] */
337 acc0
+= ((q63_t
) x2
* c0
);
338 /* acc1 += x[3] * y[2] */
339 acc1
+= ((q63_t
) x0
* c0
);
340 /* acc2 += x[4] * y[2] */
341 acc2
+= ((q63_t
) x1
* c0
);
343 /* update scratch pointers */
349 /* If the srcBLen is not a multiple of 3, compute any remaining MACs here.
350 ** No loop unrolling is used. */
351 k
= srcBLen
- (3 * (srcBLen
/ 3));
355 /* Read y[4] sample */
358 /* Read x[7] sample */
361 /* Perform the multiply-accumulates */
362 /* acc0 += x[4] * y[4] */
363 acc0
+= ((q63_t
) x0
* c0
);
364 /* acc1 += x[5] * y[4] */
365 acc1
+= ((q63_t
) x1
* c0
);
366 /* acc2 += x[6] * y[4] */
367 acc2
+= ((q63_t
) x2
* c0
);
369 /* Reuse the present samples for the next MAC */
373 /* Decrement the loop counter */
377 /* Store the result in the accumulator in the destination buffer. */
378 *pOut
= (q31_t
) (acc0
>> 31);
379 /* Destination pointer is updated according to the address modifier, inc */
382 *pOut
= (q31_t
) (acc1
>> 31);
385 *pOut
= (q31_t
) (acc2
>> 31);
388 /* Increment the pointer pIn1 index, count by 3 */
391 /* Update the inputA and inputB pointers for next MAC calculation */
396 /* Decrement the loop counter */
400 /* If the blockSize2 is not a multiple of 3, compute any remaining output samples here.
401 ** No loop unrolling is used. */
402 blkCnt
= blockSize2
- 3 * (blockSize2
/ 3);
406 /* Accumulator is made zero for every iteration */
409 /* Apply loop unrolling and compute 4 MACs simultaneously. */
412 /* First part of the processing with loop unrolling. Compute 4 MACs at a time.
413 ** a second loop below computes MACs for the remaining 1 to 3 samples. */
416 /* Perform the multiply-accumulates */
417 sum
+= (q63_t
) * px
++ * (*py
++);
418 sum
+= (q63_t
) * px
++ * (*py
++);
419 sum
+= (q63_t
) * px
++ * (*py
++);
420 sum
+= (q63_t
) * px
++ * (*py
++);
422 /* Decrement the loop counter */
426 /* If the srcBLen is not a multiple of 4, compute any remaining MACs here.
427 ** No loop unrolling is used. */
432 /* Perform the multiply-accumulate */
433 sum
+= (q63_t
) * px
++ * (*py
++);
435 /* Decrement the loop counter */
439 /* Store the result in the accumulator in the destination buffer. */
440 *pOut
= (q31_t
) (sum
>> 31);
441 /* Destination pointer is updated according to the address modifier, inc */
444 /* Increment the MAC count */
447 /* Update the inputA and inputB pointers for next MAC calculation */
451 /* Decrement the loop counter */
457 /* If the srcBLen is not a multiple of 4,
458 * the blockSize2 loop cannot be unrolled by 4 */
463 /* Accumulator is made zero for every iteration */
466 /* Loop over srcBLen */
471 /* Perform the multiply-accumulate */
472 sum
+= (q63_t
) * px
++ * (*py
++);
474 /* Decrement the loop counter */
478 /* Store the result in the accumulator in the destination buffer. */
479 *pOut
= (q31_t
) (sum
>> 31);
480 /* Destination pointer is updated according to the address modifier, inc */
483 /* Increment the MAC count */
486 /* Update the inputA and inputB pointers for next MAC calculation */
490 /* Decrement the loop counter */
495 /* --------------------------
496 * Initializations of stage3
497 * -------------------------*/
499 /* sum += x[srcALen-srcBLen+1] * y[0] + x[srcALen-srcBLen+2] * y[1] +...+ x[srcALen-1] * y[srcBLen-1]
500 * sum += x[srcALen-srcBLen+2] * y[0] + x[srcALen-srcBLen+3] * y[1] +...+ x[srcALen-1] * y[srcBLen-1]
502 * sum += x[srcALen-2] * y[0] + x[srcALen-1] * y[1]
503 * sum += x[srcALen-1] * y[0]
506 /* In this stage the MAC operations are decreased by 1 for every iteration.
507 The count variable holds the number of MAC operations performed */
508 count
= srcBLen
- 1u;
510 /* Working pointer of inputA */
511 pSrc1
= pIn1
+ (srcALen
- (srcBLen
- 1u));
514 /* Working pointer of inputB */
517 /* -------------------
519 * ------------------*/
521 while(blockSize3
> 0u)
523 /* Accumulator is made zero for every iteration */
526 /* Apply loop unrolling and compute 4 MACs simultaneously. */
529 /* First part of the processing with loop unrolling. Compute 4 MACs at a time.
530 ** a second loop below computes MACs for the remaining 1 to 3 samples. */
533 /* Perform the multiply-accumulates */
534 /* sum += x[srcALen - srcBLen + 4] * y[3] */
535 sum
+= (q63_t
) * px
++ * (*py
++);
536 /* sum += x[srcALen - srcBLen + 3] * y[2] */
537 sum
+= (q63_t
) * px
++ * (*py
++);
538 /* sum += x[srcALen - srcBLen + 2] * y[1] */
539 sum
+= (q63_t
) * px
++ * (*py
++);
540 /* sum += x[srcALen - srcBLen + 1] * y[0] */
541 sum
+= (q63_t
) * px
++ * (*py
++);
543 /* Decrement the loop counter */
547 /* If the count is not a multiple of 4, compute any remaining MACs here.
548 ** No loop unrolling is used. */
553 /* Perform the multiply-accumulates */
554 sum
+= (q63_t
) * px
++ * (*py
++);
556 /* Decrement the loop counter */
560 /* Store the result in the accumulator in the destination buffer. */
561 *pOut
= (q31_t
) (sum
>> 31);
562 /* Destination pointer is updated according to the address modifier, inc */
565 /* Update the inputA and inputB pointers for next MAC calculation */
569 /* Decrement the MAC count */
572 /* Decrement the loop counter */
578 /* Run the below code for Cortex-M0 */
580 q31_t
*pIn1
= pSrcA
; /* inputA pointer */
581 q31_t
*pIn2
= pSrcB
+ (srcBLen
- 1u); /* inputB pointer */
582 q63_t sum
; /* Accumulators */
583 uint32_t i
= 0u, j
; /* loop counters */
584 uint32_t inv
= 0u; /* Reverse order flag */
585 uint32_t tot
= 0u; /* Length */
587 /* The algorithm implementation is based on the lengths of the inputs. */
588 /* srcB is always made to slide across srcA. */
589 /* So srcBLen is always considered as shorter or equal to srcALen */
590 /* But CORR(x, y) is reverse of CORR(y, x) */
591 /* So, when srcBLen > srcALen, output pointer is made to point to the end of the output buffer */
592 /* and a varaible, inv is set to 1 */
593 /* If lengths are not equal then zero pad has to be done to make the two
594 * inputs of same length. But to improve the performance, we include zeroes
595 * in the output instead of zero padding either of the the inputs*/
596 /* If srcALen > srcBLen, (srcALen - srcBLen) zeroes has to included in the
597 * starting of the output buffer */
598 /* If srcALen < srcBLen, (srcALen - srcBLen) zeroes has to included in the
599 * ending of the output buffer */
600 /* Once the zero padding is done the remaining of the output is calcualted
601 * using correlation but with the shorter signal time shifted. */
603 /* Calculate the length of the remaining sequence */
604 tot
= ((srcALen
+ srcBLen
) - 2u);
606 if(srcALen
> srcBLen
)
608 /* Calculating the number of zeros to be padded to the output */
609 j
= srcALen
- srcBLen
;
611 /* Initialise the pointer after zero padding */
615 else if(srcALen
< srcBLen
)
617 /* Initialization to inputB pointer */
620 /* Initialization to the end of inputA pointer */
621 pIn2
= pSrcA
+ (srcALen
- 1u);
623 /* Initialisation of the pointer after zero padding */
626 /* Swapping the lengths */
631 /* Setting the reverse flag */
636 /* Loop to calculate correlation for output length number of times */
637 for (i
= 0u; i
<= tot
; i
++)
639 /* Initialize sum with zero to carry on MAC operations */
642 /* Loop to perform MAC operations according to correlation equation */
643 for (j
= 0u; j
<= i
; j
++)
645 /* Check the array limitations */
646 if((((i
- j
) < srcBLen
) && (j
< srcALen
)))
648 /* z[i] += x[i-j] * y[j] */
649 sum
+= ((q63_t
) pIn1
[j
] * pIn2
[-((int32_t) i
- j
)]);
652 /* Store the output in the destination buffer */
654 *pDst
-- = (q31_t
) (sum
>> 31u);
656 *pDst
++ = (q31_t
) (sum
>> 31u);
659 #endif /* #ifndef ARM_MATH_CM0_FAMILY */
664 * @} end of Corr group