/* ------------------------------------------------------------------
 * Copyright (C) 1998-2009 PacketVideo
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
 * express or implied.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 * -------------------------------------------------------------------
 */
/*

 Pathname: ./src/fft_rx4_short.c
 Funtions: fft_rx4_short

------------------------------------------------------------------------------
 REVISION HISTORY

 Description:
            (1) Eliminated search for max in the main loop.
            (2) Simplified the function by eliminating different conditions
                for exp.
            (3) Reduced precision on w_64rx4 from Q15 to Q12, so now the
                input can be as high as 1.0 and saturation will not occurre
                because the accumulation times the new Q12 format will never
                exceed 31 bits.

 Description:
            (1) Added comment to explain max search elimination and
                Q format during multiplications
            (2) Increased down shift from 1 to 2, to ensure that 32-bit
                numbers will not overflow when 2 consecutive adds are done
                This was found during code review.

 Who:                                   Date:
 Description:

------------------------------------------------------------------------------
 INPUT AND OUTPUT DEFINITIONS

 Inputs:
    Data       =  Input complex vector, arranged in the following order:
                  real, imag, real, imag...
                  This is a complex vector whose elements (real and Imag) are
                  Int32.
                  type Int32 *

    peak_value =  Input,  peak value of the input vector
                  Output,  peak value of the resulting vector
                  type Int32 *

 Local Stores/Buffers/Pointers Needed:
    None

 Global Stores/Buffers/Pointers Needed:
    None

 Outputs:
    exponent returns a shift to compensate the scaling introduced by
    overflow protection

 Pointers and Buffers Modified:
    calculation are done in-place and returned in Data

 Local Stores Modified:
    None

 Global Stores Modified:
    None

------------------------------------------------------------------------------
 FUNCTION DESCRIPTION

    Fast Fourier Transform, radix 4 with Decimation in Frequency and block
    floating point arithmetic.
    The radix-4 FFT  simply divides the FFT into four smaller FFTs. Each of
    the smaller FFTs is then further divided into smaller ones and so on.
    It consists of log 4 N stages and each stage consists of N/4 dragonflies.

    An FFT is nothing but a bundle of multiplications and summations which
    may overflow during calculations.


    This routine uses a scheme to test and scale the result output from
    each FFT stage in order to fix the accumulation overflow.

    The Input Data should be in Q13 format to get the highest precision.
    At the end of each dragonfly calculation, a test for possible bit growth
    is made, if bit growth is possible the Data is scale down back to Q13.


------------------------------------------------------------------------------
 REQUIREMENTS

    This function should provide a fixed point FFT for an input array
    of size 64.

------------------------------------------------------------------------------
 REFERENCES

    [1] Advance Digital Signal Processing, J. Proakis, C. Rader, F. Ling,
        C. Nikias, Macmillan Pub. Co.

------------------------------------------------------------------------------
 PSEUDO-CODE


   MODIFY( x[] )
   RETURN( exponent )

------------------------------------------------------------------------------
 RESOURCES USED
   When the code is written for a specific target processor the
     the resources used should be documented below.

 STACK USAGE: [stack count for this module] + [variable to represent
          stack usage for each subroutine called]

     where: [stack usage variable] = stack usage for [subroutine
         name] (see [filename].ext)

 DATA MEMORY USED: x words

 PROGRAM MEMORY USED: x words

 CLOCK CYCLES: [cycle count equation for this module] + [variable
           used to represent cycle count for each subroutine
           called]

     where: [cycle count variable] = cycle count for [subroutine
        name] (see [filename].ext)

------------------------------------------------------------------------------
*/
/*----------------------------------------------------------------------------
; INCLUDES
----------------------------------------------------------------------------*/

#include "pv_audio_type_defs.h"
#include "fft_rx4.h"
#include "pv_normalize.h"
#include "fxp_mul32.h"

/*----------------------------------------------------------------------------
; MACROS
; Define module specific macros here
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
; DEFINES
; Include all pre-processor statements here. Include conditional
; compile variables also.
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
; LOCAL FUNCTION DEFINITIONS
; Function Prototype declaration
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
; LOCAL VARIABLE DEFINITIONS
; Variable declaration - defined here and used outside this module
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
; EXTERNAL FUNCTION REFERENCES
; Declare functions defined elsewhere and referenced in this module
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
; EXTERNAL VARIABLES REFERENCES
; Declare variables used in this module but defined elsewhere
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
; EXTERNAL GLOBAL STORE/BUFFER/POINTER REFERENCES
; Declare variables used in this module but defined elsewhere
----------------------------------------------------------------------------*/

/*----------------------------------------------------------------------------
; FUNCTION CODE
----------------------------------------------------------------------------*/

Int fft_rx4_short(
    Int32      Data[],
    Int32      *peak_value)

{
    Int		n1;
    Int		n2;
    Int		n3;
    Int		j;
    Int		k;
    Int		i;
    Int32  	exp_jw1;
    Int32  	exp_jw2;
    Int32  	exp_jw3;


    Int32  	t1;
    Int32  	t2;
    Int32  	r1;
    Int32  	r2;
    Int32  	r3;
    Int32  	s1;
    Int32  	s2;
    Int32  	s3;

    Int32   *pData1;
    Int32   *pData2;
    Int32   *pData3;
    Int32   *pData4;
    const Int32  *pw;
    Int32   temp1;
    Int32   temp2;
    Int32   temp3;
    Int32   temp4;
    Int32   max;
    Int     exp;
    Int     exponent = 0;
    Int     shift;


    max = *peak_value;
    exp = 0;

    if (max > 0x008000)
    {
        exp = 8 - pv_normalize(max);   /* use 24 bits  */

        exponent = exp;        /* keeps track of # of shifts */

    }

    n2 = FFT_RX4_SHORT;

    pw = W_64rx4;


    /* shift down to avoid possible overflow in first pass of the loop */
    shift = 2;

    for (k = FFT_RX4_SHORT; k > 4; k >>= 2)
    {

        n1 = n2;
        n2 >>= 2;
        n3 = n1 >> 1;

        exp -= 2;

        for (i = 0; i < FFT_RX4_SHORT; i += n1)
        {
            pData1 = &Data[ i<<1];
            pData3 = pData1 + n3;
            pData2 = pData1 + n1;
            pData4 = pData3 + n1;

            temp1   = *(pData1);
            temp2   = *(pData2);
            temp1   >>= shift;
            temp2   >>= shift;

            r1      = temp1 + temp2;
            r2      = temp1 - temp2;

            temp3   = *(pData3++);
            temp4   = *(pData4++);
            temp3   >>= shift;
            temp4   >>= shift;

            t1      = temp3 + temp4;
            t2      = temp3 - temp4;

            *(pData1++) = (r1 + t1) >> exp;
            *(pData2++) = (r1 - t1) >> exp;

            temp1   = *pData1;
            temp2   = *pData2;
            temp1   >>= shift;
            temp2   >>= shift;

            s1      = temp1 + temp2;
            s2      = temp1 - temp2;

            temp3   = *pData3;
            temp4   = *pData4;
            temp3   >>= shift;
            temp4   >>= shift;

            t1      = temp3 + temp4;
            r1      = temp3 - temp4;

            *pData1   = (s1 + t1) >> exp;
            *pData2   = (s1 - t1) >> exp;

            *pData4--    = (s2 + t2) >> exp;
            *pData4      = (r2 - r1) >> exp;

            *pData3--    = (s2 - t2) >> exp;
            *pData3      = (r2 + r1) >> exp;


        }  /* i */

        for (j = 1; j < n2; j++)
        {
            exp_jw1 = *pw++;
            exp_jw2 = *pw++;
            exp_jw3 = *pw++;


            for (i = j; i < FFT_RX4_SHORT; i += n1)
            {
                pData1 = &Data[ i<<1];
                pData3 = pData1 + n3;
                pData2 = pData1 + n1;
                pData4 = pData3 + n1;

                temp1   = *(pData1);
                temp2   = *(pData2++);
                temp1   >>= shift;
                temp2   >>= shift;

                r1      = temp1 + temp2;
                r2      = temp1 - temp2;
                temp3   = *(pData3++);
                temp4   = *(pData4++);
                temp3   >>= shift;
                temp4   >>= shift;

                t1      = temp3 + temp4;
                t2      = temp3 - temp4;

                *(pData1++) = (r1 + t1) >> exp;
                r1          = (r1 - t1) >> exp;

                temp1   = *pData1;
                temp2   = *pData2;
                temp1   >>= shift;
                temp2   >>= shift;

                s1      = temp1 + temp2;
                s2      = temp1 - temp2;

                s3      = (s2 + t2) >> exp;
                s2      = (s2 - t2) >> exp;

                temp3   = *pData3;
                temp4   = *pData4 ;
                temp3   >>= shift;
                temp4   >>= shift;

                t1      = temp3 + temp4;
                t2      = temp3 - temp4;

                *pData1  = (s1 + t1) >> exp;
                s1       = (s1 - t1) >> exp;


                *pData2--  = cmplx_mul32_by_16(s1, -r1, exp_jw2) << 1;
                *pData2    = cmplx_mul32_by_16(r1,  s1, exp_jw2) << 1;

                r3       = ((r2 - t2) >> exp);
                r2       = ((r2 + t2) >> exp);

                *pData3--  = cmplx_mul32_by_16(s2, -r2, exp_jw1) << 1;
                *pData3    = cmplx_mul32_by_16(r2,  s2, exp_jw1) << 1;

                *pData4--  = cmplx_mul32_by_16(s3, -r3, exp_jw3) << 1;
                *pData4    = cmplx_mul32_by_16(r3,  s3, exp_jw3) << 1;

            }  /* i */

        }  /*  j */

        /*
         *  this will reset exp and shift to zero for the second pass of the
         *  loop
         */
        exp   = 2;
        shift = 0;

    } /* k */


    max = 0;

    pData1 = Data - 7;

    for (i = ONE_FOURTH_FFT_RX4_SHORT; i != 0 ; i--)
    {
        pData1 += 7;

        pData3 = pData1 + 2;
        pData2 = pData1 + 4;
        pData4 = pData1 + 6;

        temp1   = *pData1;
        temp2   = *pData2++;

        r1      = temp1 + temp2;
        r2      = temp1 - temp2;

        temp1   = *pData3++;
        temp2   = *pData4++;

        t1      = temp1 + temp2;
        t2      = temp1 - temp2;

        temp1       = (r1 + t1);
        r1          = (r1 - t1);
        *(pData1++) = temp1;
        max        |= (temp1 >> 31) ^ temp1;


        temp1   = *pData1;
        temp2   = *pData2;

        s1      = temp1 + temp2;
        s2      = temp1 - temp2;

        s3      = (s2 + t2);
        s2      = (s2 - t2);

        temp1   = *pData3;
        temp2   = *pData4;

        t1      = temp1 + temp2;
        t2      = temp1 - temp2;

        temp1      = (s1 + t1);
        temp2      = (s1 - t1);
        *pData1    = temp1;
        *pData2--  = temp2;
        max       |= (temp1 >> 31) ^ temp1;
        max       |= (temp2 >> 31) ^ temp2;

        *pData2    = r1;
        *pData3--  = s2;
        *pData4--  = s3;
        max       |= (r1 >> 31) ^ r1;
        max       |= (s2 >> 31) ^ s2;
        max       |= (s3 >> 31) ^ s3;

        temp1      = (r2 - t2);
        temp2      = (r2 + t2);
        *pData4    = temp1;
        *pData3    = temp2;
        max       |= (temp1 >> 31) ^ temp1;
        max       |= (temp2 >> 31) ^ temp2;

    }  /* i */

    *peak_value = max;


    return (exponent);

}