arm_bitreversal.c

00001 /* ----------------------------------------------------------------------    
00002 * Copyright (C) 2010-2014 ARM Limited. All rights reserved.    
00003 *    
00004 * $Date:        12. March 2014  
00005 * $Revision:    V1.4.3  
00006 *    
00007 * Project:      CMSIS DSP Library    
00008 * Title:        arm_bitreversal.c    
00009 *    
00010 * Description:  This file has common tables like Bitreverse, reciprocal etc which are used across different functions    
00011 *    
00012 * Target Processor: Cortex-M4/Cortex-M3/Cortex-M0
00013 *  
00014 * Redistribution and use in source and binary forms, with or without 
00015 * modification, are permitted provided that the following conditions
00016 * are met:
00017 *   - Redistributions of source code must retain the above copyright
00018 *     notice, this list of conditions and the following disclaimer.
00019 *   - Redistributions in binary form must reproduce the above copyright
00020 *     notice, this list of conditions and the following disclaimer in
00021 *     the documentation and/or other materials provided with the 
00022 *     distribution.
00023 *   - Neither the name of ARM LIMITED nor the names of its contributors
00024 *     may be used to endorse or promote products derived from this
00025 *     software without specific prior written permission.
00026 *
00027 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00028 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00029 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00030 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
00031 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00032 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00033 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00034 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00035 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00036 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00037 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00038 * POSSIBILITY OF SUCH DAMAGE.  
00039 * -------------------------------------------------------------------- */
00040 
00041 #include "arm_math.h"
00042 #include "arm_common_tables.h"
00043 
00044 /*    
00045 * @brief  In-place bit reversal function.   
00046 * @param[in, out] *pSrc        points to the in-place buffer of floating-point data type.   
00047 * @param[in]      fftSize      length of the FFT.   
00048 * @param[in]      bitRevFactor bit reversal modifier that supports different size FFTs with the same bit reversal table.   
00049 * @param[in]      *pBitRevTab  points to the bit reversal table.   
00050 * @return none.   
00051 */
00052 
00053 void arm_bitreversal_f32(
00054 float32_t * pSrc,
00055 uint16_t fftSize,
00056 uint16_t bitRevFactor,
00057 uint16_t * pBitRevTab)
00058 {
00059    uint16_t fftLenBy2, fftLenBy2p1;
00060    uint16_t i, j;
00061    float32_t in;
00062 
00063    /*  Initializations */
00064    j = 0u;
00065    fftLenBy2 = fftSize >> 1u;
00066    fftLenBy2p1 = (fftSize >> 1u) + 1u;
00067 
00068    /* Bit Reversal Implementation */
00069    for (i = 0u; i <= (fftLenBy2 - 2u); i += 2u)
00070    {
00071       if(i < j)
00072       {
00073          /*  pSrc[i] <-> pSrc[j]; */
00074          in = pSrc[2u * i];
00075          pSrc[2u * i] = pSrc[2u * j];
00076          pSrc[2u * j] = in;
00077 
00078          /*  pSrc[i+1u] <-> pSrc[j+1u] */
00079          in = pSrc[(2u * i) + 1u];
00080          pSrc[(2u * i) + 1u] = pSrc[(2u * j) + 1u];
00081          pSrc[(2u * j) + 1u] = in;
00082 
00083          /*  pSrc[i+fftLenBy2p1] <-> pSrc[j+fftLenBy2p1] */
00084          in = pSrc[2u * (i + fftLenBy2p1)];
00085          pSrc[2u * (i + fftLenBy2p1)] = pSrc[2u * (j + fftLenBy2p1)];
00086          pSrc[2u * (j + fftLenBy2p1)] = in;
00087 
00088          /*  pSrc[i+fftLenBy2p1+1u] <-> pSrc[j+fftLenBy2p1+1u] */
00089          in = pSrc[(2u * (i + fftLenBy2p1)) + 1u];
00090          pSrc[(2u * (i + fftLenBy2p1)) + 1u] =
00091          pSrc[(2u * (j + fftLenBy2p1)) + 1u];
00092          pSrc[(2u * (j + fftLenBy2p1)) + 1u] = in;
00093 
00094       }
00095 
00096       /*  pSrc[i+1u] <-> pSrc[j+1u] */
00097       in = pSrc[2u * (i + 1u)];
00098       pSrc[2u * (i + 1u)] = pSrc[2u * (j + fftLenBy2)];
00099       pSrc[2u * (j + fftLenBy2)] = in;
00100 
00101       /*  pSrc[i+2u] <-> pSrc[j+2u] */
00102       in = pSrc[(2u * (i + 1u)) + 1u];
00103       pSrc[(2u * (i + 1u)) + 1u] = pSrc[(2u * (j + fftLenBy2)) + 1u];
00104       pSrc[(2u * (j + fftLenBy2)) + 1u] = in;
00105 
00106       /*  Reading the index for the bit reversal */
00107       j = *pBitRevTab;
00108 
00109       /*  Updating the bit reversal index depending on the fft length  */
00110       pBitRevTab += bitRevFactor;
00111    }
00112 }
00113 
00114 
00115 
00116 /*    
00117 * @brief  In-place bit reversal function.   
00118 * @param[in, out] *pSrc        points to the in-place buffer of Q31 data type.   
00119 * @param[in]      fftLen       length of the FFT.   
00120 * @param[in]      bitRevFactor bit reversal modifier that supports different size FFTs with the same bit reversal table   
00121 * @param[in]      *pBitRevTab  points to bit reversal table.   
00122 * @return none.   
00123 */
00124 
00125 void arm_bitreversal_q31(
00126 q31_t * pSrc,
00127 uint32_t fftLen,
00128 uint16_t bitRevFactor,
00129 uint16_t * pBitRevTable)
00130 {
00131    uint32_t fftLenBy2, fftLenBy2p1, i, j;
00132    q31_t in;
00133 
00134    /*  Initializations      */
00135    j = 0u;
00136    fftLenBy2 = fftLen / 2u;
00137    fftLenBy2p1 = (fftLen / 2u) + 1u;
00138 
00139    /* Bit Reversal Implementation */
00140    for (i = 0u; i <= (fftLenBy2 - 2u); i += 2u)
00141    {
00142       if(i < j)
00143       {
00144          /*  pSrc[i] <-> pSrc[j]; */
00145          in = pSrc[2u * i];
00146          pSrc[2u * i] = pSrc[2u * j];
00147          pSrc[2u * j] = in;
00148 
00149          /*  pSrc[i+1u] <-> pSrc[j+1u] */
00150          in = pSrc[(2u * i) + 1u];
00151          pSrc[(2u * i) + 1u] = pSrc[(2u * j) + 1u];
00152          pSrc[(2u * j) + 1u] = in;
00153 
00154          /*  pSrc[i+fftLenBy2p1] <-> pSrc[j+fftLenBy2p1] */
00155          in = pSrc[2u * (i + fftLenBy2p1)];
00156          pSrc[2u * (i + fftLenBy2p1)] = pSrc[2u * (j + fftLenBy2p1)];
00157          pSrc[2u * (j + fftLenBy2p1)] = in;
00158 
00159          /*  pSrc[i+fftLenBy2p1+1u] <-> pSrc[j+fftLenBy2p1+1u] */
00160          in = pSrc[(2u * (i + fftLenBy2p1)) + 1u];
00161          pSrc[(2u * (i + fftLenBy2p1)) + 1u] =
00162          pSrc[(2u * (j + fftLenBy2p1)) + 1u];
00163          pSrc[(2u * (j + fftLenBy2p1)) + 1u] = in;
00164 
00165       }
00166 
00167       /*  pSrc[i+1u] <-> pSrc[j+1u] */
00168       in = pSrc[2u * (i + 1u)];
00169       pSrc[2u * (i + 1u)] = pSrc[2u * (j + fftLenBy2)];
00170       pSrc[2u * (j + fftLenBy2)] = in;
00171 
00172       /*  pSrc[i+2u] <-> pSrc[j+2u] */
00173       in = pSrc[(2u * (i + 1u)) + 1u];
00174       pSrc[(2u * (i + 1u)) + 1u] = pSrc[(2u * (j + fftLenBy2)) + 1u];
00175       pSrc[(2u * (j + fftLenBy2)) + 1u] = in;
00176 
00177       /*  Reading the index for the bit reversal */
00178       j = *pBitRevTable;
00179 
00180       /*  Updating the bit reversal index depending on the fft length */
00181       pBitRevTable += bitRevFactor;
00182    }
00183 }
00184 
00185 
00186 
00187 /*    
00188    * @brief  In-place bit reversal function.   
00189    * @param[in, out] *pSrc        points to the in-place buffer of Q15 data type.   
00190    * @param[in]      fftLen       length of the FFT.   
00191    * @param[in]      bitRevFactor bit reversal modifier that supports different size FFTs with the same bit reversal table   
00192    * @param[in]      *pBitRevTab  points to bit reversal table.   
00193    * @return none.   
00194 */
00195 
00196 void arm_bitreversal_q15(
00197 q15_t * pSrc16,
00198 uint32_t fftLen,
00199 uint16_t bitRevFactor,
00200 uint16_t * pBitRevTab)
00201 {
00202    q31_t *pSrc = (q31_t *) pSrc16;
00203    q31_t in;
00204    uint32_t fftLenBy2, fftLenBy2p1;
00205    uint32_t i, j;
00206 
00207    /*  Initializations */
00208    j = 0u;
00209    fftLenBy2 = fftLen / 2u;
00210    fftLenBy2p1 = (fftLen / 2u) + 1u;
00211 
00212    /* Bit Reversal Implementation */
00213    for (i = 0u; i <= (fftLenBy2 - 2u); i += 2u)
00214    {
00215       if(i < j)
00216       {
00217          /*  pSrc[i] <-> pSrc[j]; */
00218          /*  pSrc[i+1u] <-> pSrc[j+1u] */
00219          in = pSrc[i];
00220          pSrc[i] = pSrc[j];
00221          pSrc[j] = in;
00222 
00223          /*  pSrc[i + fftLenBy2p1] <-> pSrc[j + fftLenBy2p1];  */
00224          /*  pSrc[i + fftLenBy2p1+1u] <-> pSrc[j + fftLenBy2p1+1u] */
00225          in = pSrc[i + fftLenBy2p1];
00226          pSrc[i + fftLenBy2p1] = pSrc[j + fftLenBy2p1];
00227          pSrc[j + fftLenBy2p1] = in;
00228       }
00229 
00230       /*  pSrc[i+1u] <-> pSrc[j+fftLenBy2];         */
00231       /*  pSrc[i+2] <-> pSrc[j+fftLenBy2+1u]  */
00232       in = pSrc[i + 1u];
00233       pSrc[i + 1u] = pSrc[j + fftLenBy2];
00234       pSrc[j + fftLenBy2] = in;
00235 
00236       /*  Reading the index for the bit reversal */
00237       j = *pBitRevTab;
00238 
00239       /*  Updating the bit reversal index depending on the fft length  */
00240       pBitRevTab += bitRevFactor;
00241    }
00242 }