1/* 2 * Copyright (c) 2014 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 * 10 */ 11 12#include <stdint.h> 13 14#include "dl/api/omxtypes.h" 15#include "dl/sp/api/omxSP.h" 16#include "dl/sp/api/mipsSP.h" 17 18static OMX_U16 SplitRadixPermutation(int i, int size, int inverse) { 19 int m; 20 if (size <= 2) 21 return (i & 1); 22 m = size >> 1; 23 if (!(i & m)) 24 return SplitRadixPermutation(i, m, inverse) * 2; 25 m >>= 1; 26 if (inverse == !(i & m)) 27 return SplitRadixPermutation(i, m, inverse) * 4 + 1; 28 29 return SplitRadixPermutation(i, m, inverse) * 4 - 1; 30} 31 32static void InitFFTOffsetsLUT(OMX_U16* offset_table, 33 int offset, 34 int size, 35 OMX_U32* index) { 36 if (size < 16) { 37 offset_table[*index] = (OMX_U16)(offset >> 2); 38 (*index)++; 39 } else { 40 InitFFTOffsetsLUT(offset_table, offset, size >> 1, index); 41 InitFFTOffsetsLUT(offset_table, offset + (size >> 1), size >> 2, index); 42 InitFFTOffsetsLUT(offset_table, offset + 3 * (size >> 2), size >> 2, index); 43 } 44} 45 46OMXResult omxSP_FFTInit_R_F32(OMXFFTSpec_R_F32* pFFTSpec, OMX_INT order) { 47 OMX_U32 n; 48 uint32_t fft_size; 49 OMX_U16* p_bit_rev; 50 OMX_U16* p_bit_rev_inv; 51 OMX_U16* p_offset; 52 OMX_F32* p_twiddle; 53 OMX_F32* p_buf; 54 OMX_U32 tmp; 55 MIPSFFTSpec_R_FC32* pFFTStruct = (MIPSFFTSpec_R_FC32*)pFFTSpec; 56 57 if (!pFFTSpec || (order < 1) || (order > TWIDDLE_TABLE_ORDER)) 58 return OMX_Sts_BadArgErr; 59 60 /* For order larger than 4, compute Real FFT as Complex FFT of (order - 1). */ 61 if (order > 4) 62 fft_size = 1 << (order - 1); 63 else 64 fft_size = 1 << order; 65 66 p_bit_rev = (OMX_U16*)((OMX_S8*)pFFTSpec + sizeof(MIPSFFTSpec_R_FC32)); 67 /* Align to 32 byte boundary. */ 68 tmp = ((uintptr_t)p_bit_rev) & 31; 69 if (tmp) 70 p_bit_rev = (OMX_U16*)((OMX_S8*)p_bit_rev + (32 - tmp)); 71 72 p_bit_rev_inv = (OMX_U16*)((OMX_S8*)p_bit_rev + fft_size * sizeof(OMX_U16)); 73 /* Align to 32 byte boundary. */ 74 tmp = ((uintptr_t)p_bit_rev_inv) & 31; 75 if (tmp) 76 p_bit_rev_inv = (OMX_U16*)((OMX_S8*)p_bit_rev_inv + (32 - tmp)); 77 78 p_offset = (OMX_U16*)((OMX_S8*)p_bit_rev_inv + fft_size * sizeof(OMX_U16)); 79 /* Align to 32 byte boundary. */ 80 tmp = ((uintptr_t)p_offset) & 31; 81 if (tmp) 82 p_offset = (OMX_U16*)((OMX_S8*)p_offset + (32 - tmp)); 83 84 if (order < 5) { 85 p_twiddle = (OMX_F32*)((OMX_S8*)p_offset + 86 ((SUBTRANSFORM_CONST >> (16 - order)) | 1) * 87 sizeof(OMX_U16)); 88 } else { 89 p_twiddle = (OMX_F32*)((OMX_S8*)p_offset + 90 ((SUBTRANSFORM_CONST >> (17 - order)) | 1) * 91 sizeof(OMX_U16)); 92 } 93 94 /* Align to 32 byte boundary. */ 95 tmp = ((uintptr_t)p_twiddle) & 31; 96 if (tmp) 97 p_twiddle = (OMX_F32*)((OMX_S8*)p_twiddle + (32 - tmp)); 98 99 if (order > 3) 100 p_buf = 101 (OMX_F32*)((OMX_S8*)p_twiddle + (1 << (order - 2)) * sizeof(OMX_F32)); 102 else 103 p_buf = (OMX_F32*)((OMX_S8*)p_twiddle + sizeof(OMX_F32)); 104 105 /* Align to 32 byte boundary. */ 106 tmp = ((uintptr_t)p_buf) & 31; 107 if (tmp) 108 p_buf = (OMX_F32*)((OMX_S8*)p_buf + (32 - tmp)); 109 110 /* Calculate BitRevInv indexes. */ 111 for (uint32_t i = 0; i < fft_size; ++i) 112 p_bit_rev_inv[-SplitRadixPermutation(i, fft_size, 0) & (fft_size - 1)] = i; 113 114 /* Calculate BitRev indexes. */ 115 for (uint32_t i = 0; i < fft_size; ++i) 116 p_bit_rev[p_bit_rev_inv[i]] = i; 117 118 /* Calculate Offsets. */ 119 n = 0; 120 if (order < 5) 121 InitFFTOffsetsLUT(p_offset, 0, 1 << order, &n); 122 else 123 InitFFTOffsetsLUT(p_offset, 0, 1 << (order - 1), &n); 124 125 /* Fill the twiddle table */ 126 if (order > 3) { 127 tmp = 1 << (TWIDDLE_TABLE_ORDER - order); 128 for (n = 0; n < (1 << (order - 2)); ++n) { 129 p_twiddle[n] = mipsSP_FFT_F32TwiddleTable[n * tmp]; 130 } 131 } 132 133 /* 134 * Double-check if the offset tables are initialized correctly. 135 * Note: the bit-reverse tables and the initialization algorithm for 136 * pFFTStruct->pOffset table are thoroughly tested, so this check is 137 * probabaly redundant. However, keeping this just to make sure the offsets 138 * will not exceed the buffer boundaries. 139 */ 140 if (order > 1) { 141 /* 142 * In the case of order = 1 there is no table accesses, so there is no need 143 * for any boundary checks. 144 */ 145 if (order == 2) { 146 /* Only check the offsets for the p_bit_rev_inv table. */ 147 for (uint32_t i = 0; i < fft_size; ++i) { 148 if (p_bit_rev_inv[i] >= fft_size) 149 return OMX_Sts_BadArgErr; 150 } 151 } else if (order < 5) { 152 /* Check for p_offset table. */ 153 int shift = 2; 154 int over = 4; 155 int num_transforms = (SUBTRANSFORM_CONST >> (16 - order)) | 1; 156 for (uint32_t i = 2; i < order; ++i) { 157 for (uint32_t j = 0; j < num_transforms; ++j) { 158 if (((p_offset[j] << shift) + over - 1) >= fft_size) 159 return OMX_Sts_BadArgErr; 160 } 161 shift++; 162 over <<= 1; 163 num_transforms = (num_transforms >> 1) | 1; 164 } 165 /* Check for bit-reverse tables. */ 166 for (uint32_t i = 0; i < fft_size; ++i) { 167 if ((p_bit_rev[i] >= fft_size) || (p_bit_rev_inv[i] >= fft_size)) 168 return OMX_Sts_BadArgErr; 169 } 170 } else { 171 /* Check for p_offset table. */ 172 int shift = 2; 173 int over = 4; 174 int num_transforms = (SUBTRANSFORM_CONST >> (17 - order)) | 1; 175 for (uint32_t i = 2; i < order; ++i) { 176 for (uint32_t j = 0; j < num_transforms; ++j) { 177 if (((p_offset[j] << shift) + over - 1) >= fft_size) 178 return OMX_Sts_BadArgErr; 179 } 180 shift++; 181 over <<= 1; 182 num_transforms = (num_transforms >> 1) | 1; 183 } 184 /* Check for bit-reverse tables. */ 185 for (uint32_t i = 0; i < fft_size; ++i) { 186 if ((p_bit_rev[i] >= fft_size) || (p_bit_rev_inv[i] >= fft_size)) 187 return OMX_Sts_BadArgErr; 188 } 189 } 190 } 191 192 pFFTStruct->order = order; 193 pFFTStruct->pBitRev = p_bit_rev; 194 pFFTStruct->pBitRevInv = p_bit_rev_inv; 195 pFFTStruct->pOffset = (const OMX_U16*)p_offset; 196 pFFTStruct->pTwiddle = (const OMX_F32*)p_twiddle; 197 pFFTStruct->pBuf = p_buf; 198 199 return OMX_Sts_NoErr; 200} 201