14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/*---------------------------------------------------------------------------* 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * sp_fft.c * 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Copyright 2007, 2008 Nuance Communciations, Inc. * 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the 'License'); * 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * you may not use this file except in compliance with the License. * 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * You may obtain a copy of the License at * 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 * 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Unless required by applicable law or agreed to in writing, software * 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * distributed under the License is distributed on an 'AS IS' BASIS, * 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * See the License for the specific language governing permissions and * 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * limitations under the License. * 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * * 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *---------------------------------------------------------------------------*/ 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project**************************************************************************** 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** FILE: sp_fft.cpp 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** CREATED: 11-September-99 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** DESCRIPTION: Split-Radix FFT 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** MODIFICATIONS: 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** Revision history log 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** VSS revision history. Do not edit by hand. 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** $NoKeywords: $ 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project** 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project*/ 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef _RTT 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <stdio.h> 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <math.h> 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <assert.h> 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "front.h" 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "portable.h" 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "sp_fft.h" 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "himul32.h" 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/*extern "C" asr_int32_t himul32(asr_int32_t factor1, asr_int32_t factor2);*/ 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* >>>> Fixed Point, Floting Point, and Machine Specific Methods <<<< 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project We will localize all fixed point, floating point, and machine specific 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project operations into the following methods so that in the main body of the code 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project we would not need to worry these issues. 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project*/ 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* convert trigonomy function data to its required representation*/ 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic trigonomydata 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectto_trigonomydata(double a) 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned scale = (unsigned int)(1 << (8 * sizeof(trigonomydata) - 1)); 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (trigonomydata)(a * scale); 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* Do a sign-extending right shift of x by i bits, and 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * round the result based on the leftmost bit shifted out. 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Must have 1 <= i < 32. 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Note that C doesn't define whether right shift of signed 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * ints sign-extends or zero-fills. 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * On platforms that do sign-extend, use the native right shift. 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * Else use a short branch-free sequence that forces in copies 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project * of the sign bit. 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PINLINE asr_int32_t rshift(asr_int32_t x, int i) 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project asr_int32_t xshift = x >> i; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(i >= 1 && i < 32); 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#if -1 >> 31 != -1 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project asr_int32_t signbit = (asr_int32_t)(((asr_uint32_t)x & 0x80000000U) >> i); 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project xshift |= -signbit; 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project xshift += (x >> (i - 1)) & 1; 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return xshift; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* compute (a + jb)*(c + jd) = a*c - b*d + j(ad + bc) */ 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PINLINE void complex_multiplier(trigonomydata a, trigonomydata b, 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata c, fftdata d, 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata* real, fftdata* imag) 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project himul32(factor1, factor2) = floor( (factor1 * factor2) / 2**32 ) 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project we need floor( (factor1 * factor2) / 2**31 ) 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project retain one more bit of accuracy by left shifting first. 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project c <<= 1; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project d <<= 1; 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *real = himul32(a, c) - himul32(b, d); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *imag = himul32(a, d) + himul32(b, c); 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* determine the maximum number of bits required to represent the data */ 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PINLINE int data_bits(const int length, fftdata data[]) 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project asr_uint32_t bits = 0; 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int d = 0; 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int i; 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(sizeof(data[0]) == 4); 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < length; i++) 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project d = data[i]; 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bits |= (d > 0) ? d : -d; 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project d = 0; 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (bits > 0) 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bits >>= 1; 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project d++; 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return d; 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* >>>> Fixed Point, Floting Point, and Machine Independent Methods <<<< */ 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* constructor */ 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectsrfft* new_srfft(unsigned logLength) 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project srfft* pthis; 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* cannot do smaller than 4 point FFT */ 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(logLength >= 2); 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis = (srfft*) CALLOC(1, sizeof(srfft), "srfft"); 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_logLength = logLength; 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_length = 1 << logLength; 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project allocate_bitreverse_tbl(pthis); 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project allocate_butterfly_tbl(pthis); 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project allocate_trigonomy_tbl(pthis); 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return pthis; 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* destructor */ 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid delete_srfft(srfft* pSrfft) 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_sin3Tbl); 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_cos3Tbl); 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_sin2Tbl); 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_cos2Tbl); 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_sin1Tbl); 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_cos1Tbl); 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_butterflyIndexTbl); 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft->m_bitreverseTbl); 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)pSrfft); 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project allocate L shaped butterfly index lookup table 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project*/ 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid allocate_butterfly_tbl(srfft* pthis) 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned butterflyLength, butterflies, *butterflyIndex; 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned m, n, n2, i, j, i0, is, id, ii, ib; 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* compute total number of L shaped butterflies */ 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project m = pthis->m_logLength; 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyLength = 0; 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflies = 0; 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < m; i++) 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflies = (i % 2) ? butterflyLength : butterflyLength + 1; 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyLength += butterflies; 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Allocate m more spaces to store size information */ 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyLength += m; 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyIndex = (unsigned*) CALLOC(butterflyLength, sizeof(unsigned), "srfft.butterflyIndex"); 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Compute and store L shaped butterfly indexes at each stage */ 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n = pthis->m_length; 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n2 = n << 1; 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyLength = 0; 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ib = 0; 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < m; i++) 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflies = (i % 2) ? butterflyLength : butterflyLength + 1; 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyLength += butterflies; 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Store number of L butterflies at stage m-i*/ 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyIndex[ib++] = butterflies; 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Compute Sorensen, Heideman, and Burrus indexes for L shaped butterfiles */ 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project id = n2; 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project is = 0; 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n2 = n2 >> 1; 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (is < n) 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i0 = is; i0 < n; i0 += id) 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyIndex[ib] = i0; 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (i0 != 0) 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* sort bufferfly index in increasing order to simplify look up */ 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii = ib; 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (butterflyIndex[ii] < butterflyIndex[ii-1]) 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project j = butterflyIndex[ii]; 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyIndex[ii] = butterflyIndex[ii-1]; 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyIndex[--ii] = j; 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ib++; 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project is = 2 * id - n2; 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project id = id << 2; 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_butterflyIndexTbl = butterflyIndex; 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* move to stage 2 buffer index table */ 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < m - 2; i++) 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflies = *butterflyIndex; 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyIndex += (butterflies + 1); 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Since we want to compute four point butterflies directly, 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project when we compute two point butterflieswe at the last stage 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project we must bypass those two point butterflies that are decomposed 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project from previous stage's four point butterflies . 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflies = *butterflyIndex++; /* number of four point butterflies */ 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii = butterflies + 1; /* index to the two point butterflies*/ 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < butterflies; i++) 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project j = butterflyIndex[i]; 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project find those two point butterflies that are 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project decomposed from the four point butterflies 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (butterflyIndex[ii] != j) /* look up is sure so do not need worry over bound*/ 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii++; 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterflyIndex[ii++] = 0; 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(ii <= butterflyLength + m); 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Allocate trigonoy function lookup tables 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project*/ 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid allocate_trigonomy_tbl(srfft* pthis) 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trigonomydata *pcos1, *psin1, *pcos2, *psin2, *pcos3, *psin3; 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned m, n, n2, n4, i, j, ii, nt; 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project double e, radias, radias3; 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project m = pthis->m_logLength; 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n = pthis->m_length; 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project nt = (n >> 1) - 1; 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pcos1 = (trigonomydata*) CALLOC(nt, sizeof(trigonomydata), "srfft.trigonomydata"); 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project psin1 = (trigonomydata*) CALLOC(nt, sizeof(trigonomydata), "srfft.trigonomydata"); 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pcos2 = (trigonomydata*) CALLOC(nt, sizeof(trigonomydata), "srfft.trigonomydata"); 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project psin2 = (trigonomydata*) CALLOC(nt, sizeof(trigonomydata), "srfft.trigonomydata"); 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pcos3 = (trigonomydata*) CALLOC(nt, sizeof(trigonomydata), "srfft.trigonomydata"); 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project psin3 = (trigonomydata*) CALLOC(nt, sizeof(trigonomydata), "srfft.trigonomydata"); 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii = 0; 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n2 = n << 1; 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < m - 1; i++) 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n2 = n2 >> 1; 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n4 = n2 >> 2; 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project e = 6.283185307179586 / n2; 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (j = 0; j < n4; j++) 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (j != 0) /* there is no need for radias zero trigonomy tables */ 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project radias = j * e; 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project radias3 = 3.0 * radias; 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pcos1[ii] = to_trigonomydata(cos(radias)); 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project psin1[ii] = to_trigonomydata(sin(radias)); 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pcos3[ii] = to_trigonomydata(cos(radias3)); 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project psin3[ii] = to_trigonomydata(sin(radias3)); 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii++; 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < nt; i++) 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project radias = 3.141592653589793 * (i + 1) / n; 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pcos2[i] = to_trigonomydata(cos(radias)); 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project psin2[i] = to_trigonomydata(sin(radias)); 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_cos1Tbl = pcos1; 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_sin1Tbl = psin1; 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_cos2Tbl = pcos2; 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_sin2Tbl = psin2; 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_cos3Tbl = pcos3; 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_sin3Tbl = psin3; 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Allocate bit reverse tables 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project*/ 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid allocate_bitreverse_tbl(srfft* pthis) 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned forward, reverse, *tbl; 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned m, n, i, j; 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n = pthis->m_length; 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tbl = (unsigned*) CALLOC(n, sizeof(unsigned), "srfft.bitreverseTbl"); 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (j = 0; j < n; j++) tbl[j] = 0; 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project m = pthis->m_logLength; 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project forward = 1; 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project reverse = n >> 1; 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < m; i++) 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (j = 0; j < n; j++) 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (forward & j) tbl[j] |= reverse; 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project reverse >>= 1; 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project forward <<= 1; 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pthis->m_bitreverseTbl = tbl; 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Compute a four point FFT that requires no multiplications 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project*/ 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PINLINE void four_point_fft1(fftdata* data) 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata r0, r1, r2; 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[0]; 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[4]; 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[0] = r0 + r1; 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[4] = r0 - r1; 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[2]; 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[6]; 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[2] = r0 + r1; 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[6] = r0 - r1; 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[1]; 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[5]; 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[1] = r0 + r1; 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[5] = r0 - r1; 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[3]; 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[7]; 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[3] = r0 + r1; 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[7] = r0 - r1; 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[0]; 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[2]; 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[0] = r0 + r1; 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[2] = r0 - r1; 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[1]; 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[3]; 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[1] = r0 + r1; 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[3] = r0 - r1; 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[4]; 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[7]; 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r2 = data[6]; 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[4] = r0 + r1; 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[6] = r0 - r1; 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[5]; 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[5] = r0 - r2; 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[7] = r0 + r2; 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/* 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Compute a two point FFT that requires no multiplications 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project*/ 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PINLINE void two_point_fft1(fftdata* data) 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata r0, r1; 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[0]; 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[2]; 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[0] = r0 + r1; 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[2] = r0 - r1; 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[1]; 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[3]; 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[1] = r0 + r1; 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[3] = r0 - r1; 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic PINLINE void comp_L_butterfly1(unsigned butteflyIndex, unsigned quarterLength, 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trigonomydata cc1, trigonomydata ss1, 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trigonomydata cc3, trigonomydata ss3, 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata* data) 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned k1, k2, k3; 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata r0, r1, r2, r3, i0, i1, i2, i3; 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project quarterLength <<= 1; 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k1 = quarterLength; 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k2 = k1 + quarterLength; 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k3 = k2 + quarterLength; 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 = data[0]; 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 = data[k1]; 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r2 = data[k2]; 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r3 = data[k3]; 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i0 = data[1]; 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i1 = data[k1+1]; 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i2 = data[k2+1]; 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i3 = data[k3+1]; 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* compute the radix-2 butterfly */ 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[0] = r0 + r2; 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k1] = r1 + r3; 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[1] = i0 + i2; 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k1+1] = i1 + i3; 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* compute two radix-4 butterflies with twiddle factors */ 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r0 -= r2; 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r1 -= r3; 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i0 -= i2; 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i1 -= i3; 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r2 = r0 + i1; 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i2 = r1 - i0; 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project r3 = r0 - i1; 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i3 = r1 + i0; 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project optimize the butterfly computation for zero's power twiddle factor 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project that does not need multimplications 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (butteflyIndex == 0) 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k2] = r2; 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k2+1] = -i2; 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k3] = r3; 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k3+1] = i3; 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project complex_multiplier(cc1, -ss1, r2, -i2, data + k2, data + k2 + 1); 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project complex_multiplier(cc3, -ss3, r3, i3, data + k3, data + k3 + 1); 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/**********************************************************************/ 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid do_fft1(srfft* pthis, unsigned length2, fftdata* data) 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned *indexTbl, indexLength; 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trigonomydata *cos1, *sin1, *cos3, *sin3; 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trigonomydata cc1, ss1, cc3, ss3; 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned n, m, n4, i, j, k, ii, k0; 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata temp; 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Load butterfly index table */ 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexTbl = pthis->m_butterflyIndexTbl; 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexLength = 0; 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Load cosine and sine tables */ 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cos1 = pthis->m_cos1Tbl; 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sin1 = pthis->m_sin1Tbl; 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cos3 = pthis->m_cos3Tbl; 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sin3 = pthis->m_sin3Tbl; 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* stages of butterfly computation*/ 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n = pthis->m_length; 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project m = pthis->m_logLength; 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project compute L shaped butterfies util only 4 and 2 point 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project butterfiles are left 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n4 = n >> 1; 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii = 0; 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < m - 2; i++) 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n4 >>= 1; 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* read the number of L shaped butterfly nodes at the stage */ 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexLength = *indexTbl++; 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project compute one L shaped butterflies at each stage 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project j (time) and k (frequency) loops are reversed to minimize 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trigonomy table lookups 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (j = 0; j < n4; j++) 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cc1 = cos1[ii]; 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ss1 = sin1[ii]; 5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cc3 = cos3[ii]; 5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ss3 = sin3[ii++]; 5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (k = 0; k < indexLength; k++) 5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k0 = indexTbl[k] + j; 5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k0 <<= 1; 5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project comp_L_butterfly1(j, n4, cc1, ss1, cc3, ss3, data + k0); 5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Move to the butterfly index table of the next stage*/ 5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexTbl += indexLength; 5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Compute 4 point butterflies at stage 2 */ 5414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexLength = *indexTbl++; 5424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (k = 0; k < indexLength; k++) 5434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k0 = indexTbl[k]; 5454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k0 <<= 1; 5464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project four_point_fft1(data + k0); 5474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexTbl += indexLength; 5494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Compute 2 point butterflies of the last stage */ 5514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexLength = *indexTbl++; 5524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (k = 0; k < indexLength; k++) 5534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k0 = indexTbl[k]; 5554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k0 <<= 1; 5564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* k0 = 0 implies these nodes have been computed */ 5584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (k0 != 0) 5594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project two_point_fft1(data + k0); 5614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* Bit reverse the data array */ 5654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project indexTbl = pthis->m_bitreverseTbl; 5664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < n; i++) 5674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii = indexTbl[i]; 5694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (i < ii) 5704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 5714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project j = i << 1; 5724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k = ii << 1; 5734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project temp = data[j]; 5744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[j] = data[k]; 5754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k] = temp; 5764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project j++; 5784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project k++; 5794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project temp = data[j]; 5804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[j] = data[k]; 5814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[k] = temp; 5824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 5854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid do_real_fft(srfft* pthis, unsigned n, fftdata* data) 5874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 5884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned n2; 5894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned i, i1, i2, i3, i4; 5904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata h1r, h1i, h2r, h2i, tr, ti; 5914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trigonomydata *cos2, *sin2; 5924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project cos2 = pthis->m_cos2Tbl; 5944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project sin2 = pthis->m_sin2Tbl; 5954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* do a complex FFT of half size using the even indexed data 5974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** as real component and odd indexed data as imaginary data components 5984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 5994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project do_fft1(pthis, n, data); 6014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 6034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** queeze the real valued first and last component of 6044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** the complex transform as elements data[0] and data[1] 6054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 6064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tr = data[0]; 6074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ti = data[1]; 6084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[0] = (tr + ti); 6094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[1] = (tr - ti); 6104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* do the rest of elements*/ 6124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n2 = n >> 2; 6134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 1; i < n2; i++) 6144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 6154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i1 = i << 1; 6164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i2 = i1 + 1; 6174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i3 = n - i1; 6184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i4 = i3 + 1; 6194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project h1r = (data[i1] + data[i3]) / 2; 6214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project h1i = (data[i2] - data[i4]) / 2; 6224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project h2r = (data[i2] + data[i4]) / 2; 6234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project h2i = -(data[i1] - data[i3]) / 2; 6244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project complex_multiplier(cos2[i-1], -sin2[i-1], h2r, h2i, &tr, &ti); 6264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i1] = h1r + tr; 6284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i2] = h1i + ti; 6294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i3] = h1r - tr; 6304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i4] = -h1i + ti; 6314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* center one needs no multiplication, but has to reverse sign */ 6334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i = (n >> 1); 6344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i+1] = -data[i+1]; 6354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 6374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/*****************************************************************************/ 6394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectint do_real_fft_magsq(srfft* pthis, unsigned n, fftdata* data) 6414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 6424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata tr, ti, last; 6434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned i, ii, n1; 6444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int scale = 0; 6454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int s = 0; 6464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned maxval = 0; 6474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 6504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** Windowed fftdata has an unknown data length - determine this using 6514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** data_bits(), a maximum of: 6524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** fixed data = windowedData * 2**HAMMING_DATA_BITS 6544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** FFT will grow data log2Length. In order to avoid data overflow, 6564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** we can scale data by a factor 6574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** scale = 8*sizeof(fftdata) - data_bits() - log2Length 6594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** In other words, we now have 6614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** fixed data = windowedData * 2**HAMMING_DATA_BITS * 2**scale 6634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 6654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scale = 8 * sizeof(fftdata) - 2 - pthis->m_logLength; 6684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scale -= data_bits(n, data); 6694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < n; i++) 6714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 6724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (scale < 0) 6734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 6744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i] = rshift(data[i], -scale); 6754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 6774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 6784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i] <<= scale; 6794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* compute the real input fft, the real valued first and last component of 6834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** the complex transform is stored as elements data[0] and data[1] 6844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 6854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project do_real_fft(pthis, n, data); 6874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* After fft, we now have the data, 6894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** fixed data = fftdata * 2**HAMMING_DATA_BITS * 2**scale 6914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** to get fft data, we then need to reverse-shift the fixed data by the 6934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** scale constant; 6944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** However, since our purpose is to compute magnitude, we can combine 6964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** this step into the magnitude computation. Notice that 6974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 6984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** fixed data = fftdata * 2**(8*sizeof(fftdata) - DATA_BITS - log2Length) 6994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 7004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** if we use himul32 to compute the magnitude, which gives us, 7014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 7024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** fixed magnitude = fftdata magnitude * 2**(2*(32 - 16 - log2Length)) - 2**32) 7034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** = fftdata magnitude * 2**(-2*log2Length) 7044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 7054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** to get the fixed magnitude = fftdata magnitude * 2**(-log2Length-1) 7064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** = fftdata magnitude/FFT length 7074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** we need to upscale fftdata to cancel out the log2Lenght-1 factor in 7084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** the fixed magnitude 7094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 7104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** Notice that upshift scale log2Lenght-1 is not a constant, but a 7114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** function of FFT length. 7124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** Funthermore, even and odd log2Length-1 must be handled differently. 7134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** 7144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 7154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 7174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** This bit is a lot simpler now, we just aim to get the pre-magsqu 7184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** values in a 30-bit range + sign. 7194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** This is the max val if we want r*r+i*i guarenteed < signed int64 range. 7204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** So shift the data up until it is ==30 bits (FFTDATA_SIZE-2) 7214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 7224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project s = (FFTDATA_SIZE - 2) - data_bits(n, data); 7244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* n is twice the size, so this */ 7254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 0; i < n; i++) 7284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 7294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s < 0) 7304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 7314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i] = rshift(data[i], -s); 7324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 7344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 7354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i] <<= s; 7364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scale += s; 7404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 7424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** OK, now we are in the 30bit range, we can do a magsq. 7434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** This magsq output must be less that 60bit plus sign. 7444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 7454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 7474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** Special at start as DC and Nyquist freqs are in data[0] and data[1] 7484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** respectively. 7494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 7504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tr = data[0]; 7524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[0] = himul32(tr, tr); 7534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project maxval |= data[0]; 7544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tr = data[1]; 7564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project last = himul32(tr, tr); 7574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project maxval |= last; 7584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project n1 = n >> 1; 7604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (i = 1; i < n1; i++) 7614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 7624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ii = i << 1; 7634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project tr = data[ii]; 7644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i] = himul32(tr, tr); 7654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ti = data[++ii]; 7674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[i] += himul32(ti, ti); 7684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project maxval |= data[i]; 7704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 7714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project data[n1] = last; /* now the Nyquist freq can be put in place */ 7734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 7754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** computing magnitude _squared_ means the scale is effectively 7764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** applied twice 7774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 7784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scale *= 2; 7804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 7824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** account for inherent scale of fft - we have do to this here as each 7834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** stage scales by sqrt(2), and we couldn't add this to scale until 7844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** after it had been multiplied by two (??) 7854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** TODO: The truth is we got here by trial and error 7864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** This should be checked. 7874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 7884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scale += pthis->m_logLength + 1; 7904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* 7924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ** doing the himul32() shift results in shifting down by 32(FFTDATA_SIZE) bits. 7934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project */ 7944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project scale -= 32; 7964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 7974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(maxval >= 0); 7984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(!(maxval & 0xC0000000)); 7994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* we've done something wrong if */ 8004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* either of the top two bits */ 8014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* get used! */ 8024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return(-scale); /* return the amount we have shifted the */ 8044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /* data _down_ by */ 8054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 8074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project/*****************************************************************************/ 8104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid configure_fft(fft_info *fft, int size) 8124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 8134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned int log2Length, length; 8144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project log2Length = 0; 8164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project length = size / 2; 8174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (length > 1) 8184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 8194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project length = length >> 1; 8204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project log2Length++; 8214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 8224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(size == 1 << (log2Length + 1)); 8244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fft->size2 = size; 8254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fft->size = size / 2; 8264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fft->m_srfft = new_srfft(log2Length); 8284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fft->real = (fftdata*) CALLOC(size + 2, sizeof(fftdata), "srfft.fft_data"); 8294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fft->imag = fft->real + size / 2 + 1; 8304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 8314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectint fft_perform_and_magsq(fft_info *fft) 8334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 8344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project unsigned n = fft->size2; 8354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fftdata *real = fft->real; 8364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project srfft *pSrfft = fft->m_srfft; 8374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ; 8384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return do_real_fft_magsq(pSrfft, n, real); 8404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 8414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid unconfigure_fft(fft_info *fft) 8434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 8444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(fft); 8454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete_srfft(fft->m_srfft); 8464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FREE((char*)fft->real); 8474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 8484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectint place_sample_data(fft_info *fft, fftdata *seq, fftdata *smooth, int num) 8514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project{ 8524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int ii, size2; 8534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project srfft * pSrfft; 8544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pSrfft = fft->m_srfft; 8564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(fft); 8584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(seq); 8594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(smooth); 8604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ASSERT(num <= (int)fft->size2); 8614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size2 = fft->size2; 8624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ii = 0; ii < num; ii++) 8644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 8654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fft->real[ii] = (fftdata)(seq[ii] * smooth[ii]); 8664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 8674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (; ii < size2; ii++) 8694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project { 8704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fft->real[ii] = 0; 8714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 8724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 8734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return(-(HALF_FFTDATA_SIZE - 1)); 8744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 8754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 876