CMSIS DSP library
Dependents: performance_timer Surfboard_ gps2rtty Capstone ... more
Legacy Warning
This is an mbed 2 library. To learn more about mbed OS 5, visit the docs.
Diff: cmsis_dsp/TransformFunctions/arm_cfft_radix2_q31.c
- Revision:
- 3:7a284390b0ce
- Parent:
- 2:da51fb522205
- Child:
- 5:3762170b6d4d
--- a/cmsis_dsp/TransformFunctions/arm_cfft_radix2_q31.c Thu May 30 17:10:11 2013 +0100 +++ b/cmsis_dsp/TransformFunctions/arm_cfft_radix2_q31.c Fri Nov 08 13:45:10 2013 +0000 @@ -1,8 +1,8 @@ /* ---------------------------------------------------------------------- -* Copyright (C) 2010 ARM Limited. All rights reserved. +* Copyright (C) 2010-2013 ARM Limited. All rights reserved. * -* $Date: 15. February 2012 -* $Revision: V1.1.0 +* $Date: 17. January 2013 +* $Revision: V1.4.1 * * Project: CMSIS DSP Library * Title: arm_cfft_radix2_q31.c @@ -12,299 +12,339 @@ * * Target Processor: Cortex-M4/Cortex-M3/Cortex-M0 * -* Version 1.1.0 2012/02/15 -* Updated with more optimizations, bug fixes and minor API changes. -* -* Version 0.0.3 2010/03/10 -* Initial version +* Redistribution and use in source and binary forms, with or without +* modification, are permitted provided that the following conditions +* are met: +* - Redistributions of source code must retain the above copyright +* notice, this list of conditions and the following disclaimer. +* - Redistributions in binary form must reproduce the above copyright +* notice, this list of conditions and the following disclaimer in +* the documentation and/or other materials provided with the +* distribution. +* - Neither the name of ARM LIMITED nor the names of its contributors +* may be used to endorse or promote products derived from this +* software without specific prior written permission. +* +* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS +* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE +* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, +* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, +* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN +* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +* POSSIBILITY OF SUCH DAMAGE. * -------------------------------------------------------------------- */ #include "arm_math.h" -/** - * @ingroup groupTransforms - */ - -/** - * @defgroup Radix2_CFFT_CIFFT Radix-2 Complex FFT Functions - * - * \par - * Complex Fast Fourier Transform(CFFT) and Complex Inverse Fast Fourier Transform(CIFFT) is an efficient algorithm to compute Discrete Fourier Transform(DFT) and Inverse Discrete Fourier Transform(IDFT). - * Computational complexity of CFFT reduces drastically when compared to DFT. - */ - - -/** - * @addtogroup Radix2_CFFT_CIFFT - * @{ - */ - -/** - * @details - * @brief Processing function for the fixed-point CFFT/CIFFT. - * @param[in] *S points to an instance of the fixed-point CFFT/CIFFT structure. - * @param[in, out] *pSrc points to the complex data buffer of size <code>2*fftLen</code>. Processing occurs in-place. - * @return none. - */ - -void arm_cfft_radix2_q31( - const arm_cfft_radix2_instance_q31 * S, - q31_t * pSrc) -{ - - if(S->ifftFlag == 1u) - { - arm_radix2_butterfly_inverse_q31(pSrc, S->fftLen, - S->pTwiddle, S->twidCoefModifier); - } - else - { - arm_radix2_butterfly_q31(pSrc, S->fftLen, - S->pTwiddle, S->twidCoefModifier); - } - - arm_bitreversal_q31(pSrc, S->fftLen, S->bitRevFactor, S->pBitRevTable); -} - -/** - * @} end of Radix2_CFFT_CIFFT group - */ - void arm_radix2_butterfly_q31( q31_t * pSrc, uint32_t fftLen, q31_t * pCoef, - uint16_t twidCoefModifier) + uint16_t twidCoefModifier); + +void arm_radix2_butterfly_inverse_q31( + q31_t * pSrc, + uint32_t fftLen, + q31_t * pCoef, + uint16_t twidCoefModifier); + +void arm_bitreversal_q31( + q31_t * pSrc, + uint32_t fftLen, + uint16_t bitRevFactor, + uint16_t * pBitRevTab); + +/** +* @ingroup groupTransforms +*/ + +/** +* @addtogroup ComplexFFT +* @{ +*/ + +/** +* @details +* @brief Processing function for the fixed-point CFFT/CIFFT. +* @param[in] *S points to an instance of the fixed-point CFFT/CIFFT structure. +* @param[in, out] *pSrc points to the complex data buffer of size <code>2*fftLen</code>. Processing occurs in-place. +* @return none. +*/ + +void arm_cfft_radix2_q31( +const arm_cfft_radix2_instance_q31 * S, +q31_t * pSrc) { - int i, j, k, l; - int n1, n2, ia; - q31_t xt, yt, cosVal, sinVal; - - //N = fftLen; - n2 = fftLen; - - n1 = n2; - n2 = n2 >> 1; - ia = 0; + if(S->ifftFlag == 1u) + { + arm_radix2_butterfly_inverse_q31(pSrc, S->fftLen, + S->pTwiddle, S->twidCoefModifier); + } + else + { + arm_radix2_butterfly_q31(pSrc, S->fftLen, + S->pTwiddle, S->twidCoefModifier); + } - // loop for groups - for (i = 0; i < n2; i++) - { - cosVal = pCoef[ia * 2]; - sinVal = pCoef[(ia * 2) + 1]; - ia = ia + twidCoefModifier; + arm_bitreversal_q31(pSrc, S->fftLen, S->bitRevFactor, S->pBitRevTable); +} - l = i + n2; - xt = (pSrc[2 * i] >> 2u) - (pSrc[2 * l] >> 2u); - pSrc[2 * i] = ((pSrc[2 * i] >> 2u) + (pSrc[2 * l] >> 2u)) >> 1u; +/** +* @} end of ComplexFFT group +*/ - yt = (pSrc[2 * i + 1] >> 2u) - (pSrc[2 * l + 1] >> 2u); - pSrc[2 * i + 1] = - ((pSrc[2 * l + 1] >> 2u) + (pSrc[2 * i + 1] >> 2u)) >> 1u; - - pSrc[2u * l] = (((int32_t) (((q63_t) xt * cosVal) >> 32)) + - ((int32_t) (((q63_t) yt * sinVal) >> 32))); - - pSrc[2u * l + 1u] = (((int32_t) (((q63_t) yt * cosVal) >> 32)) - - ((int32_t) (((q63_t) xt * sinVal) >> 32))); - - } // groups loop end +void arm_radix2_butterfly_q31( +q31_t * pSrc, +uint32_t fftLen, +q31_t * pCoef, +uint16_t twidCoefModifier) +{ - twidCoefModifier = twidCoefModifier << 1u; + unsigned i, j, k, l, m; + unsigned n1, n2, ia; + q31_t xt, yt, cosVal, sinVal; + q31_t p0, p1; + + //N = fftLen; + n2 = fftLen; - // loop for stage - for (k = fftLen / 2; k > 2; k = k >> 1) - { - n1 = n2; - n2 = n2 >> 1; - ia = 0; + n1 = n2; + n2 = n2 >> 1; + ia = 0; - // loop for groups - for (j = 0; j < n2; j++) - { + // loop for groups + for (i = 0; i < n2; i++) + { cosVal = pCoef[ia * 2]; sinVal = pCoef[(ia * 2) + 1]; ia = ia + twidCoefModifier; - // loop for butterfly - for (i = j; i < fftLen; i += n1) - { - l = i + n2; - xt = pSrc[2 * i] - pSrc[2 * l]; - pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]) >> 1u; + l = i + n2; + xt = (pSrc[2 * i] >> 2u) - (pSrc[2 * l] >> 2u); + pSrc[2 * i] = ((pSrc[2 * i] >> 2u) + (pSrc[2 * l] >> 2u)) >> 1u; + + yt = (pSrc[2 * i + 1] >> 2u) - (pSrc[2 * l + 1] >> 2u); + pSrc[2 * i + 1] = + ((pSrc[2 * l + 1] >> 2u) + (pSrc[2 * i + 1] >> 2u)) >> 1u; - yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; - pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]) >> 1u; + mult_32x32_keep32_R(p0, xt, cosVal); + mult_32x32_keep32_R(p1, yt, cosVal); + multAcc_32x32_keep32_R(p0, yt, sinVal); + multSub_32x32_keep32_R(p1, xt, sinVal); + + pSrc[2u * l] = p0; + pSrc[2u * l + 1u] = p1; - pSrc[2u * l] = (((int32_t) (((q63_t) xt * cosVal) >> 32)) + - ((int32_t) (((q63_t) yt * sinVal) >> 32))); + } // groups loop end + + twidCoefModifier <<= 1u; - pSrc[2u * l + 1u] = (((int32_t) (((q63_t) yt * cosVal) >> 32)) - - ((int32_t) (((q63_t) xt * sinVal) >> 32))); - - } // butterfly loop end - - } // groups loop end + // loop for stage + for (k = fftLen / 2; k > 2; k = k >> 1) + { + n1 = n2; + n2 = n2 >> 1; + ia = 0; - twidCoefModifier = twidCoefModifier << 1u; - } // stages loop end + // loop for groups + for (j = 0; j < n2; j++) + { + cosVal = pCoef[ia * 2]; + sinVal = pCoef[(ia * 2) + 1]; + ia = ia + twidCoefModifier; - n1 = n2; - n2 = n2 >> 1; - ia = 0; + // loop for butterfly + i = j; + m = fftLen / n1; + do + { + l = i + n2; + xt = pSrc[2 * i] - pSrc[2 * l]; + pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]) >> 1u; + + yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; + pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]) >> 1u; - cosVal = pCoef[ia * 2]; - sinVal = pCoef[(ia * 2) + 1]; - ia = ia + twidCoefModifier; + mult_32x32_keep32_R(p0, xt, cosVal); + mult_32x32_keep32_R(p1, yt, cosVal); + multAcc_32x32_keep32_R(p0, yt, sinVal); + multSub_32x32_keep32_R(p1, xt, sinVal); + + pSrc[2u * l] = p0; + pSrc[2u * l + 1u] = p1; + i += n1; + m--; + } while( m > 0); // butterfly loop end - // loop for butterfly - for (i = 0; i < fftLen; i += n1) - { - l = i + n2; - xt = pSrc[2 * i] - pSrc[2 * l]; - pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); + } // groups loop end + + twidCoefModifier <<= 1u; + } // stages loop end - yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; - pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); + n1 = n2; + n2 = n2 >> 1; + ia = 0; - pSrc[2u * l] = xt; + cosVal = pCoef[ia * 2]; + sinVal = pCoef[(ia * 2) + 1]; + ia = ia + twidCoefModifier; - pSrc[2u * l + 1u] = yt; + // loop for butterfly + for (i = 0; i < fftLen; i += n1) + { + l = i + n2; + xt = pSrc[2 * i] - pSrc[2 * l]; + pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); - i += n1; - l = i + n2; + yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; + pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); - xt = pSrc[2 * i] - pSrc[2 * l]; - pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); + pSrc[2u * l] = xt; + + pSrc[2u * l + 1u] = yt; - yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; - pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); + i += n1; + l = i + n2; + + xt = pSrc[2 * i] - pSrc[2 * l]; + pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); - pSrc[2u * l] = xt; + yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; + pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); - pSrc[2u * l + 1u] = yt; + pSrc[2u * l] = xt; - } // butterfly loop end + pSrc[2u * l + 1u] = yt; + + } // butterfly loop end } void arm_radix2_butterfly_inverse_q31( - q31_t * pSrc, - uint32_t fftLen, - q31_t * pCoef, - uint16_t twidCoefModifier) +q31_t * pSrc, +uint32_t fftLen, +q31_t * pCoef, +uint16_t twidCoefModifier) { - int i, j, k, l; - int n1, n2, ia; - q31_t xt, yt, cosVal, sinVal; - - //N = fftLen; - n2 = fftLen; - - n1 = n2; - n2 = n2 >> 1; - ia = 0; + unsigned i, j, k, l; + unsigned n1, n2, ia; + q31_t xt, yt, cosVal, sinVal; + q31_t p0, p1; - // loop for groups - for (i = 0; i < n2; i++) - { - cosVal = pCoef[ia * 2]; - sinVal = pCoef[(ia * 2) + 1]; - ia = ia + twidCoefModifier; - - l = i + n2; - xt = (pSrc[2 * i] >> 2u) - (pSrc[2 * l] >> 2u); - pSrc[2 * i] = ((pSrc[2 * i] >> 2u) + (pSrc[2 * l] >> 2u)) >> 1u; + //N = fftLen; + n2 = fftLen; - yt = (pSrc[2 * i + 1] >> 2u) - (pSrc[2 * l + 1] >> 2u); - pSrc[2 * i + 1] = - ((pSrc[2 * l + 1] >> 2u) + (pSrc[2 * i + 1] >> 2u)) >> 1u; - - pSrc[2u * l] = (((int32_t) (((q63_t) xt * cosVal) >> 32)) - - ((int32_t) (((q63_t) yt * sinVal) >> 32))); - - pSrc[2u * l + 1u] = (((int32_t) (((q63_t) yt * cosVal) >> 32)) + - ((int32_t) (((q63_t) xt * sinVal) >> 32))); - - } // groups loop end + n1 = n2; + n2 = n2 >> 1; + ia = 0; - twidCoefModifier = twidCoefModifier << 1u; - - // loop for stage - for (k = fftLen / 2; k > 2; k = k >> 1) - { - n1 = n2; - n2 = n2 >> 1; - ia = 0; - - // loop for groups - for (j = 0; j < n2; j++) - { + // loop for groups + for (i = 0; i < n2; i++) + { cosVal = pCoef[ia * 2]; sinVal = pCoef[(ia * 2) + 1]; ia = ia + twidCoefModifier; - // loop for butterfly - for (i = j; i < fftLen; i += n1) - { - l = i + n2; - xt = pSrc[2 * i] - pSrc[2 * l]; - pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]) >> 1u; + l = i + n2; + xt = (pSrc[2 * i] >> 2u) - (pSrc[2 * l] >> 2u); + pSrc[2 * i] = ((pSrc[2 * i] >> 2u) + (pSrc[2 * l] >> 2u)) >> 1u; + + yt = (pSrc[2 * i + 1] >> 2u) - (pSrc[2 * l + 1] >> 2u); + pSrc[2 * i + 1] = + ((pSrc[2 * l + 1] >> 2u) + (pSrc[2 * i + 1] >> 2u)) >> 1u; - yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; - pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]) >> 1u; + mult_32x32_keep32_R(p0, xt, cosVal); + mult_32x32_keep32_R(p1, yt, cosVal); + multSub_32x32_keep32_R(p0, yt, sinVal); + multAcc_32x32_keep32_R(p1, xt, sinVal); + + pSrc[2u * l] = p0; + pSrc[2u * l + 1u] = p1; + } // groups loop end - pSrc[2u * l] = (((int32_t) (((q63_t) xt * cosVal) >> 32)) - - ((int32_t) (((q63_t) yt * sinVal) >> 32))); + twidCoefModifier = twidCoefModifier << 1u; - pSrc[2u * l + 1u] = (((int32_t) (((q63_t) yt * cosVal) >> 32)) + - ((int32_t) (((q63_t) xt * sinVal) >> 32))); - - } // butterfly loop end - - } // groups loop end + // loop for stage + for (k = fftLen / 2; k > 2; k = k >> 1) + { + n1 = n2; + n2 = n2 >> 1; + ia = 0; - twidCoefModifier = twidCoefModifier << 1u; - } // stages loop end + // loop for groups + for (j = 0; j < n2; j++) + { + cosVal = pCoef[ia * 2]; + sinVal = pCoef[(ia * 2) + 1]; + ia = ia + twidCoefModifier; - n1 = n2; - n2 = n2 >> 1; - ia = 0; + // loop for butterfly + for (i = j; i < fftLen; i += n1) + { + l = i + n2; + xt = pSrc[2 * i] - pSrc[2 * l]; + pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]) >> 1u; + + yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; + pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]) >> 1u; - cosVal = pCoef[ia * 2]; - sinVal = pCoef[(ia * 2) + 1]; - ia = ia + twidCoefModifier; + mult_32x32_keep32_R(p0, xt, cosVal); + mult_32x32_keep32_R(p1, yt, cosVal); + multSub_32x32_keep32_R(p0, yt, sinVal); + multAcc_32x32_keep32_R(p1, xt, sinVal); + + pSrc[2u * l] = p0; + pSrc[2u * l + 1u] = p1; + } // butterfly loop end + + } // groups loop end - // loop for butterfly - for (i = 0; i < fftLen; i += n1) - { - l = i + n2; - xt = pSrc[2 * i] - pSrc[2 * l]; - pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); + twidCoefModifier = twidCoefModifier << 1u; + } // stages loop end - yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; - pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); + n1 = n2; + n2 = n2 >> 1; + ia = 0; - pSrc[2u * l] = xt; + cosVal = pCoef[ia * 2]; + sinVal = pCoef[(ia * 2) + 1]; + ia = ia + twidCoefModifier; - pSrc[2u * l + 1u] = yt; + // loop for butterfly + for (i = 0; i < fftLen; i += n1) + { + l = i + n2; + xt = pSrc[2 * i] - pSrc[2 * l]; + pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); - i += n1; - l = i + n2; + yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; + pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); - xt = pSrc[2 * i] - pSrc[2 * l]; - pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); + pSrc[2u * l] = xt; + + pSrc[2u * l + 1u] = yt; - yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; - pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); + i += n1; + l = i + n2; + + xt = pSrc[2 * i] - pSrc[2 * l]; + pSrc[2 * i] = (pSrc[2 * i] + pSrc[2 * l]); - pSrc[2u * l] = xt; + yt = pSrc[2 * i + 1] - pSrc[2 * l + 1]; + pSrc[2 * i + 1] = (pSrc[2 * l + 1] + pSrc[2 * i + 1]); - pSrc[2u * l + 1u] = yt; + pSrc[2u * l] = xt; - } // butterfly loop end + pSrc[2u * l + 1u] = yt; + + } // butterfly loop end }