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 % 0x4u;
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