*===============================================================================
*
* TEXAS INSTRUMENTS, INC.
*
* Copyright � Texas Instruments Incorporated 1998
*
* TI retains all right, title and interest in this code and authorizes its
* use solely and exclusively with digital signal processing devices
* manufactured by or for TI. This code is intended to provide an
* understanding of the benefits of using TI digital signal processing devices.
* It is provided "AS IS". TI disclaims all warranties and representations,
* including but not limited to, any warranty of merchantability or fitness
* for a particular purpose. This code may contain irregularities not found
* in commercial software and is not intended to be used in production
* applications. You agree that prior to using or incorporating this code
* into any commercial product you will thoroughly test that product and the
* functionality of the code in that product and will be solely responsible
* for any problems or failures.
*
* TI retains all rights not granted herein.
*
*
* Linear Time, Small Lookup Table: Bit Reversal
*
* Revision Date: 5/12/98
*
* USAGE This routine is C Callable and can be called as:
*
* void bitrev(float *x, short *index, int n){
*
* x = Input Array to be Bit-Reversed
* n = Number of points in array must be a power of 2)
* index = Array of ~sqrt(n) created by the routine
* digitrev_index found below to allow the fast
* implementation of the bit-reversal
*
* If routine is not to be used as a C callable function
* then all instructions relating to stack should be removed.
* Refer to comments of individual instructions. You will also
* need to initialize values for all of the values passed as these
* are assumed to be in registers as defined by the calling
* convention of the compiler, (refer to the C compiler reference
* guide).
*
* C Code This is the C equivalent of the Assembly Code without
* restrictions. Note that the assembly code is hand optimized
* and restrictions may apply
*
* TI retains all rights, title and interest in this code and only
* authorizes the use of this code on TI TMS320 DSPs manufactured by TI.
*
* void bitrev(float *xs, short *index, int n){
* int i;
* short i0, i1, i2, i3;
* short j0, j1, j2, j3;
* double xi0, xi1, xi2, xi3;
* double xj0, xj1, xj2, xj3;
* short t;
* int a, b, ia, ib, ibs;
* int mask;
* int nbits, nbot, ntop, ndiff, n2, halfn;
* double *x ;
* x = (double *)xs ;
*
* nbits = 0;
* i = n;
* while (i > 1)
* {
* i = i >> 1;
* nbits++;
* }
*
* nbot = nbits >> 1;
* ndiff = nbits & 1;
* ntop = nbot + ndiff;
* n2 = 1 << ntop;
* mask = n2 - 1;
* halfn = n >> 1;
*
* for (i0 = 0; i0 < halfn; i0 += 2)
* {
* b = i0 & mask;
* a = i0 >> nbot;
* if (!b) ia = index[a];
* ib = index[b];
* ibs = ib << nbot;
*
* j0 = ibs + ia;
* t = i0 < j0;
* xi0 = x[i0];
* xj0 = x[j0];
*
* if (t)
* {
* x[i0] = xj0;
* x[j0] = xi0;
* }
*
* i1 = i0 + 1;
* j1 = j0 + halfn;
* xi1 = x[i1];
* xj1 = x[j1];
* x[i1] = xj1;
* x[j1] = xi1;
*
* i3 = i1 + halfn;
* j3 = j1 + 1;
* xi3 = x[i3];
* xj3 = x[j3];
* if (t)
* {
* x[i3] = xj3;
* x[j3] = xi3;
* }
* }
* }
*
* DESCRIPTION
* This routine performs the bit-reversal of the input array x[].
* where x[] is an array of length n 32-bit complex pairs of data.
* This requires the index array provided by the program below.
* This index should be generated at compile time not by the DSP.
*
* ASSUMPTIONS
* n is a power of 2
*
* NOTE: If n <= 4K one can use the char (8-bit) data type for
* the "index" variable. This would require changing the LDH when
* loading index values in the assembly routine to LDB. This would
* further reduce the size of the Index Table by half its size.
*
* CYCLES (n/4)*11 + 9
*
* MEMORY NOTE
* There are NO memory bank hits regarless of array alignment
*
*******************************************************************************
* Use This Routine To Generate the Index Table for
* Bit/Digit Reversing of Radix-2 and Radix-4 Routines
*******************************************************************************
* This routine calculates the index for digitrev of length n
* (length of index is 2^(radix*ceil(k/radix)) where n = 2^k
* in otherwords
* Either:sqrt(n) when n=2^even# Or: sqrt(2)*sqrt(n) when n=2^odd# [radix 2]
* sqrt(n) when n=4^even# Or: sqrt(4)*sqrt(n) when n=4^odd# [radix 4]
* Note: the variable "radix" is 2 for radix-2 and 4 for radix-4
*******************************************************************************
*
* void digitrev_index(short *index, int n, int radix){
*
* int i,j,k;
* short nbits, nbot, ntop, ndiff, n2, raddiv2;
*
* nbits = 0;
* i = n;
* while (i > 1){
* i = i >> 1;
* nbits++;
* }
*
* raddiv2 = radix >> 1;
* nbot = nbits >> raddiv2;
* nbot = nbot << raddiv2 - 1;
* ndiff = nbits & raddiv2;
* ntop = nbot + ndiff;
* n2 = 1 << ntop;
*
* index[0] = 0;
* for ( i = 1, j = n2/radix + 1; i < n2 - 1; i++){
* index[i] = j - 1;
* for (k = n2/radix; k*(radix-1) < j; k /= radix)
* j -= k*(radix-1);
* j += k;
* }
* index[n2 - 1] = n2 - 1;
* }
*
* TECHNIQUES
*
* 1. The following registers are sharead to reduce register pressure
* A8 (between) xi2, xi4, n2, nbits
* A9 (between) xj2, xj4, tmp, ndiff
* A10 (between) xi0, cnst
* A11 (between) xj0, ntop
* B4 (between) index, ptr_i1
* B6 (between) xi1, xi3
* B7 (between) xj1, xj3
* 2. The first set of indices ia and ib are loaded before
* loop kernel
* 3. Three load pointers are used to decouple 3 load/stores
* 4. Memory bank hits are eliminated by loading odd/even
* index pair in one cycle
*
*******************************************************************************
.global _bitrev
.text
_bitrev:
STW .D2T2 B14,*B15--(48)
STW .D2T2 B3,*+B15(4)
STW .D2T1 A10,*+B15(8)
STW .D2T1 A11,*+B15(12)
STW .D2T1 A12,*+B15(16)
STW .D2T1 A13,*+B15(20)
STW .D2T1 A14,*+B15(24)
STW .D2T1 A15,*+B15(28)
STW .D2T2 B10,*+B15(32)
STW .D2T2 B11,*+B15(36)
STW .D2T2 B12,*+B15(40)
STW .D2T2 B13,*+B15(44)
; Begin Benchmark Timing
LDH .D2T1 *B4, A13 ; ib = *index
|| SHR .S2X A6, 2, B1 ; icntr = n >> 2
|| MVK .S1 31, A10 ; cnst = 31
|| LMBD .L1 1, A6, A9 ; tmp = lmbd(1, n)
|| ZERO .L2 B13 ; i0 = 0
SHR .S2X A6, 1, B5 ; halfn = n >> 1
|| SHL .S1 A6, 2, A12 ; halfnbytes = n << 2
|| LDH .D2 *B4, B3 ; ia = *index
|| SUB .L1 A10, A9, A8 ; nbits = cnst - tmp
SHR .S1 A8, 1, A14 ; nbot1 = nbits >> 1
|| AND .L1 A8, 1, A9 ; ndiff = nbits & 1
ADD .L1 A14, A9, A11 ; ntop = nbot1 + ndiff
|| MVK .S1 1, A9 ; tmp = 1
SHL .S1 A9, A11, A8 ; n2 = tmp << ntop
|| ADD .S2 B13,2,B2 ; aa = i0 + 2
|| ADD .L1X B13,2,A1 ; bb = i0 + 2
|| MV .L2X A14, B14 ; nbot = nbot1
SHL .S1 A13, A14, A13 ; ib = ib << nbot1
|| SUB .D1 A8, 1, A15 ; mask = n2 - 1
ADD .L1X A13, B3, A0 ; j0 = ib + ia
|| SHR .S1 A6, 1, A6 ; n = n >> 1
SHL .S1 A0,3,A3 ; ptr_y0 = j0 << 3
|| MV .L1X B4, A7 ; ptr_i0 = index
MV .L2X A4,B11 ; ptr_y1 = x
|| ADD .L1 A4,A3,A3 ; ptr_y0 = x + ptr_y0
|| AND .S1 A1, A15, A1 ; bb = bb & mask
|| SHR .S2 B2, B14, B2 ; aa = aa >> nbot
LOOP:
LDDW .D2T1 *++B11[1], A9:A8 ; xj2:xi2 = *++ptr_y1[1]
|| LDDW .D1T2 *++A3[A6], B7:B6 ; xj3:xi3 = *++ptr_y0[n]
|| ADD .S2 B11,8,B12 ; ptr_z1 = ptr_y1 + 8
|| ADD .L1 A3,A12,A5 ; ptr_z0 = ptr_y0 + halfnbytes
|| CMPLT .L2X B13, A0, B0 ; if (i0 < j0) {t=1} else {t=0}
LDH .D1 *+A7[A1], A13 ; ib = *+ptr_i0[bb]
|| MV .L1 A4, A2 ; ptr_x0 = x
|| MV .L2X A4, B10 ; ptr_x1 = x
[B0] LDDW .D2T1 *++B10[B13], A11:A10 ; if (t) xj0:xi0 = *++ptr_x1[i0]
||[B0] LDDW .D1T2 *++A5[1], B9:B8 ; if (t) xj5:xi5 = *++ptr_z0[1]
|| ADD .L2 B13, 2, B13 ; i0 = i0 + 2
[!A1] LDH .D2 *+B4[B2], B3 ; if (!bb) ia = *+ptr_i1[aa]
[B0] LDDW .D1T2 *++A2[A0], B7:B6 ; if (t) xj1:xi1 = *++ptr_x0[j0]
||[B0] LDDW .D2T1 *++B12[B5], A9:A8 ; if (t)xj4:xi4=*++ptr_z1[halfn]
||[B1] SUB .S2 B1, 1, B1 ; if (icntr) icntr -=1
|| ADD .L2 B13,2,B2 ; aa = i0 + 2
|| ADD .L1X B13,2,A1 ; bb = i0 + 2
STW .D1T1 A8, *A3++[1] ; *ptr_y0++[1] = xi2
|| STW .D2T2 B7, *++B11[1] ; *++ptr_y1[1] = xj3
||[B1] B .S2 LOOP
STW .D1T1 A9, *A3--[1] ; *ptr_y0--[1] = xj2
|| STW .D2T2 B6, *--B11[1] ; *--ptr_y1[1] = xi3
|| SHL .S1 A13, A14, A13 ; ib = ib << nbot1
[B0] STW .D1T1 A10, *A2++[1] ; if (t) *ptr_x0++[1] = xi0
||[B0] STW .D2T2 B9, *++B12[1] ; if (t) *++ptr_z1[1] = xj5
|| AND .S1 A1, A15, A1 ; bb = bb & mask
|| SHR .S2 B2, B14, B2 ; aa = aa >> nbot
[B0] STW .D1T1 A11, *A2--[1] ; if (t) *ptr_x0--[1] = xj0
||[B0] STW .D2T2 B8, *--B12[1] ; if (t) *--ptr_z1[1] = xi5
|| ADD .L1X A13, B3, A0 ; j0 = ib + ia
[B0] STW .D2T2 B7, *++B10[1] ; if (t) *++ptr_x1[1] = xj1
||[B0] STW .D1T1 A8, *A5++[1] ; if (t) *ptr_z0++[1] = xi4
|| SHL .S1 A0,3,A3 ; ptr_y0 = j0 << 3
|| SHL .S2 B13,3,B11 ; ptr_y1 = i0 << 3
[B0] STW .D2T2 B6, *--B10[1] ; if (t) *--ptr_x1[1] = xi1
||[B0] STW .D1T1 A9, *A5--[1] ; if (t) *ptr_z0--[1] = xj4
|| ADD .L2X A4,B11,B11 ; ptr_y1 = x + ptr_y1
|| ADD .L1 A4,A3,A3 ; ptr_y0 = x + ptr_y0
;---------------------------------------------------------------------------
; End Benchmark Timing
LDW .D2 *+B15(4),B3 ; pop return address
LDDW .D2T1 *+B15(8),A11:A10
LDDW .D2T1 *+B15(16),A13:A12
LDDW .D2T1 *+B15(24),A15:A14
LDDW .D2T2 *+B15(32),B11:B10
LDDW .D2T2 *+B15(40),B13:B12
|| B .S2 B3 ; Return to calling function
LDW .D2T2 *++B15(48),B14
NOP 4