1b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org/* 2b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. 3b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * 4b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * Use of this source code is governed by a BSD-style license 5b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * that can be found in the LICENSE file in the root of the source 6b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * tree. An additional intellectual property rights grant can be found 7b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * in the file PATENTS. All contributing project authors may 8b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * be found in the AUTHORS file in the root of the source tree. 9b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org */ 10b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 11b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org/* 12b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * fft.c 13b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * 14b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * Fast Fourier Transform 15b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org * 16b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org */ 17b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 18b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 19b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org#include "fft.h" 20b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 21fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.orgconst int16_t kSortTabFft[240] = { 22b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 0, 60, 120, 180, 20, 80, 140, 200, 40, 100, 160, 220, 23b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 4, 64, 124, 184, 24, 84, 144, 204, 44, 104, 164, 224, 24b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 8, 68, 128, 188, 28, 88, 148, 208, 48, 108, 168, 228, 25b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 12, 72, 132, 192, 32, 92, 152, 212, 52, 112, 172, 232, 26b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 16, 76, 136, 196, 36, 96, 156, 216, 56, 116, 176, 236, 27b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 1, 61, 121, 181, 21, 81, 141, 201, 41, 101, 161, 221, 28b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 5, 65, 125, 185, 25, 85, 145, 205, 45, 105, 165, 225, 29b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 9, 69, 129, 189, 29, 89, 149, 209, 49, 109, 169, 229, 30b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 13, 73, 133, 193, 33, 93, 153, 213, 53, 113, 173, 233, 31b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 17, 77, 137, 197, 37, 97, 157, 217, 57, 117, 177, 237, 32b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 2, 62, 122, 182, 22, 82, 142, 202, 42, 102, 162, 222, 33b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 6, 66, 126, 186, 26, 86, 146, 206, 46, 106, 166, 226, 34b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 10, 70, 130, 190, 30, 90, 150, 210, 50, 110, 170, 230, 35b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 14, 74, 134, 194, 34, 94, 154, 214, 54, 114, 174, 234, 36b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 18, 78, 138, 198, 38, 98, 158, 218, 58, 118, 178, 238, 37b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 3, 63, 123, 183, 23, 83, 143, 203, 43, 103, 163, 223, 38b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 7, 67, 127, 187, 27, 87, 147, 207, 47, 107, 167, 227, 39b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 11, 71, 131, 191, 31, 91, 151, 211, 51, 111, 171, 231, 40b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 15, 75, 135, 195, 35, 95, 155, 215, 55, 115, 175, 235, 41b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 19, 79, 139, 199, 39, 99, 159, 219, 59, 119, 179, 239 42b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org}; 43b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 44b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org/* Cosine table in Q14 */ 45fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.orgconst int16_t kCosTabFfftQ14[240] = { 46b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 16384, 16378, 16362, 16333, 16294, 16244, 16182, 16110, 16026, 15931, 15826, 15709, 47b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 15582, 15444, 15296, 15137, 14968, 14788, 14598, 14399, 14189, 13970, 13741, 13502, 48b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 13255, 12998, 12733, 12458, 12176, 11885, 11585, 11278, 10963, 10641, 10311, 9974, 49b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 9630, 9280, 8923, 8561, 8192, 7818, 7438, 7053, 6664, 6270, 5872, 5469, 50b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 5063, 4653, 4240, 3825, 3406, 2986, 2563, 2139, 1713, 1285, 857, 429, 51b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 0, -429, -857, -1285, -1713, -2139, -2563, -2986, -3406, -3825, -4240, -4653, 52b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -5063, -5469, -5872, -6270, -6664, -7053, -7438, -7818, -8192, -8561, -8923, -9280, 53b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -9630, -9974, -10311, -10641, -10963, -11278, -11585, -11885, -12176, -12458, -12733, -12998, 54b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -13255, -13502, -13741, -13970, -14189, -14399, -14598, -14788, -14968, -15137, -15296, -15444, 55b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -15582, -15709, -15826, -15931, -16026, -16110, -16182, -16244, -16294, -16333, -16362, -16378, 56b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -16384, -16378, -16362, -16333, -16294, -16244, -16182, -16110, -16026, -15931, -15826, -15709, 57b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -15582, -15444, -15296, -15137, -14968, -14788, -14598, -14399, -14189, -13970, -13741, -13502, 58b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -13255, -12998, -12733, -12458, -12176, -11885, -11585, -11278, -10963, -10641, -10311, -9974, 59b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -9630, -9280, -8923, -8561, -8192, -7818, -7438, -7053, -6664, -6270, -5872, -5469, 60b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org -5063, -4653, -4240, -3825, -3406, -2986, -2563, -2139, -1713, -1285, -857, -429, 61b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 0, 429, 857, 1285, 1713, 2139, 2563, 2986, 3406, 3825, 4240, 4653, 62b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 5063, 5469, 5872, 6270, 6664, 7053, 7438, 7818, 8192, 8561, 8923, 9280, 63b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 9630, 9974, 10311, 10641, 10963, 11278, 11585, 11885, 12176, 12458, 12733, 12998, 64b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 13255, 13502, 13741, 13970, 14189, 14399, 14598, 14788, 14968, 15137, 15296, 15444, 65b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 15582, 15709, 15826, 15931, 16026, 16110, 16182, 16244, 16294, 16333, 16362, 16378 66b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org}; 67b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 68b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 69b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 70b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org/* Uses 16x16 mul, without rounding, which is faster. Uses WEBRTC_SPL_MUL_16_16_RSFT */ 71fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.orgint16_t WebRtcIsacfix_FftRadix16Fastest(int16_t RexQx[], int16_t ImxQx[], int16_t iSign) { 72b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 73fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t dd, ee, ff, gg, hh, ii; 74fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t k0, k1, k2, k3, k4, kk; 75fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t tmp116, tmp216; 76b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 77fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t ccc1Q14, ccc2Q14, ccc3Q14, sss1Q14, sss2Q14, sss3Q14; 78fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t sss60Q14, ccc72Q14, sss72Q14; 79fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t aaQx, ajQx, akQx, ajmQx, ajpQx, akmQx, akpQx; 80fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t bbQx, bjQx, bkQx, bjmQx, bjpQx, bkmQx, bkpQx; 81b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 82fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org int16_t ReDATAQx[240], ImDATAQx[240]; 83b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 84b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss60Q14 = kCosTabFfftQ14[20]; 85b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ccc72Q14 = kCosTabFfftQ14[48]; 86b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss72Q14 = kCosTabFfftQ14[12]; 87b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 88b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (iSign < 0) { 89b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss72Q14 = -sss72Q14; 90b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss60Q14 = -sss60Q14; 91b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 92b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* Complexity is: 10 cycles */ 93b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 94b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* compute fourier transform */ 95b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 96b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // transform for factor of 4 97b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (kk=0; kk<60; kk++) { 98b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k0 = kk; 99b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k1 = k0 + 60; 100b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k2 = k1 + 60; 101b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k3 = k2 + 60; 102b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 103b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akpQx = RexQx[k0] + RexQx[k2]; 104b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akmQx = RexQx[k0] - RexQx[k2]; 105b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajpQx = RexQx[k1] + RexQx[k3]; 106b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajmQx = RexQx[k1] - RexQx[k3]; 107b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkpQx = ImxQx[k0] + ImxQx[k2]; 108b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkmQx = ImxQx[k0] - ImxQx[k2]; 109b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjpQx = ImxQx[k1] + ImxQx[k3]; 110b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjmQx = ImxQx[k1] - ImxQx[k3]; 111b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 112b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k0] = akpQx + ajpQx; 113b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k0] = bkpQx + bjpQx; 114b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajpQx = akpQx - ajpQx; 115b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjpQx = bkpQx - bjpQx; 116b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (iSign < 0) { 117b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akpQx = akmQx + bjmQx; 118b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkpQx = bkmQx - ajmQx; 119b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akmQx -= bjmQx; 120b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkmQx += ajmQx; 121b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } else { 122b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akpQx = akmQx - bjmQx; 123b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkpQx = bkmQx + ajmQx; 124b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akmQx += bjmQx; 125b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkmQx -= ajmQx; 126b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 127b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 128b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ccc1Q14 = kCosTabFfftQ14[kk]; 129b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ccc2Q14 = kCosTabFfftQ14[WEBRTC_SPL_MUL_16_16(2, kk)]; 130b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ccc3Q14 = kCosTabFfftQ14[WEBRTC_SPL_MUL_16_16(3, kk)]; 131b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss1Q14 = kCosTabFfftQ14[kk+60]; 132b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = kCosTabFfftQ14[WEBRTC_SPL_MUL_16_16(2, kk)+60]; 133b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss3Q14 = kCosTabFfftQ14[WEBRTC_SPL_MUL_16_16(3, kk)+60]; 134b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (iSign==1) { 135b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss1Q14 = -sss1Q14; 136b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = -sss2Q14; 137b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss3Q14 = -sss3Q14; 138b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 139b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 140b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org //Do several multiplications like Q14*Q16>>14 = Q16 141b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // RexQ16[k1] = akpQ16 * ccc1Q14 - bkpQ16 * sss1Q14; 142b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // RexQ16[k2] = ajpQ16 * ccc2Q14 - bjpQ16 * sss2Q14; 143b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // RexQ16[k3] = akmQ16 * ccc3Q14 - bkmQ16 * sss3Q14; 144b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // ImxQ16[k1] = akpQ16 * sss1Q14 + bkpQ16 * ccc1Q14; 145b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // ImxQ16[k2] = ajpQ16 * sss2Q14 + bjpQ16 * ccc2Q14; 146b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // ImxQ16[k3] = akmQ16 * sss3Q14 + bkmQ16 * ccc3Q14; 147b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 148fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org RexQx[k1] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc1Q14, akpQx, 14) - 149fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss1Q14, bkpQx, 14); // 6 non-mul + 2 mul cycles, i.e. 8 cycles (6+2*7=20 cycles if 16x32mul) 150fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org RexQx[k2] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, ajpQx, 14) - 151fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, bjpQx, 14); 152fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org RexQx[k3] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc3Q14, akmQx, 14) - 153fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss3Q14, bkmQx, 14); 154fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ImxQx[k1] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss1Q14, akpQx, 14) + 155fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc1Q14, bkpQx, 14); 156fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ImxQx[k2] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, ajpQx, 14) + 157fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, bjpQx, 14); 158fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ImxQx[k3] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss3Q14, akmQx, 14) + 159fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc3Q14, bkmQx, 14); 160b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org //This mul segment needs 6*8 = 48 cycles for 16x16 muls, but 6*20 = 120 cycles for 16x32 muls 161b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 162b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 163b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 164b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* Complexity is: 51+48 = 99 cycles for 16x16 muls, but 51+120 = 171 cycles for 16x32 muls*/ 165b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 166b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // transform for factor of 3 167b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk=0; 168b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k1=20; 169b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k2=40; 170b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 171b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (hh=0; hh<4; hh++) { 172b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (ii=0; ii<20; ii++) { 173b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akQx = RexQx[kk]; 174b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkQx = ImxQx[kk]; 175b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajQx = RexQx[k1] + RexQx[k2]; 176b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjQx = ImxQx[k1] + ImxQx[k2]; 177b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[kk] = akQx + ajQx; 178b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[kk] = bkQx + bjQx; 179b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org tmp116 = WEBRTC_SPL_RSHIFT_W16(ajQx, 1); 180b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org tmp216 = WEBRTC_SPL_RSHIFT_W16(bjQx, 1); 181b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akQx = akQx - tmp116; 182b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkQx = bkQx - tmp216; 183b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org tmp116 = RexQx[k1] - RexQx[k2]; 184b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org tmp216 = ImxQx[k1] - ImxQx[k2]; 185b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 186fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ajQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss60Q14, tmp116, 14); // Q14*Qx>>14 = Qx 187fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org bjQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss60Q14, tmp216, 14); // Q14*Qx>>14 = Qx 188b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k1] = akQx - bjQx; 189b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k2] = akQx + bjQx; 190b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k1] = bkQx + ajQx; 191b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k2] = bkQx - ajQx; 192b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 193b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk++; 194b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k1++; 195b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k2++; 196b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 197b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* Complexity : (31+6)*20 = 740 cycles for 16x16 muls, but (31+18)*20 = 980 cycles for 16x32 muls*/ 198b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk=kk+40; 199b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k1=k1+40; 200b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k2=k2+40; 201b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 202b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* Complexity : 4*(740+3) = 2972 cycles for 16x16 muls, but 4*(980+3) = 3932 cycles for 16x32 muls*/ 203b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 204b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* multiply by rotation factor for odd factor 3 or 5 (not for 4) 205b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org Same code (duplicated) for both ii=2 and ii=3 */ 206b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = 1; 207b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ee = 0; 208b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ff = 0; 209b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 210b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (gg=0; gg<19; gg++) { 211b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk += 20; 212b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ff = ff+4; 213b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (hh=0; hh<2; hh++) { 214fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ee = ff + (int16_t)WEBRTC_SPL_MUL_16_16(hh, ff); 215b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org dd = ee + 60; 216b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ccc2Q14 = kCosTabFfftQ14[ee]; 217b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = kCosTabFfftQ14[dd]; 218b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (iSign==1) { 219b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = -sss2Q14; 220b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 221b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (ii=0; ii<4; ii++) { 222b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akQx = RexQx[kk]; 223b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkQx = ImxQx[kk]; 224fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org RexQx[kk] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, akQx, 14) - // Q14*Qx>>14 = Qx 225fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, bkQx, 14); 226fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ImxQx[kk] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, akQx, 14) + // Q14*Qx>>14 = Qx 227fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, bkQx, 14); 228b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 229b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 230b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk += 60; 231b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 232b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = kk - 220; 233b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 234b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 2*(13+5+4*13+2) = 144 for 16x16 muls, but 2*(13+5+4*33+2) = 304 cycles for 16x32 muls 235b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = kk - 59; 236b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 237b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 19*144 = 2736 for 16x16 muls, but 19*304 = 5776 cycles for 16x32 muls 238b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 239b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // transform for factor of 5 240b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = 0; 241b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ccc2Q14 = kCosTabFfftQ14[96]; 242b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = kCosTabFfftQ14[84]; 243b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (iSign==1) { 244b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = -sss2Q14; 245b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 246b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 247b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (hh=0; hh<4; hh++) { 248b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (ii=0; ii<12; ii++) { 249b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k1 = kk + 4; 250b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k2 = k1 + 4; 251b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k3 = k2 + 4; 252b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k4 = k3 + 4; 253b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 254b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akpQx = RexQx[k1] + RexQx[k4]; 255b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akmQx = RexQx[k1] - RexQx[k4]; 256b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkpQx = ImxQx[k1] + ImxQx[k4]; 257b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkmQx = ImxQx[k1] - ImxQx[k4]; 258b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajpQx = RexQx[k2] + RexQx[k3]; 259b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajmQx = RexQx[k2] - RexQx[k3]; 260b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjpQx = ImxQx[k2] + ImxQx[k3]; 261b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjmQx = ImxQx[k2] - ImxQx[k3]; 262b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org aaQx = RexQx[kk]; 263b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bbQx = ImxQx[kk]; 264b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[kk] = aaQx + akpQx + ajpQx; 265b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[kk] = bbQx + bkpQx + bjpQx; 266b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 267fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org akQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc72Q14, akpQx, 14) + 268fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, ajpQx, 14) + aaQx; 269fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org bkQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc72Q14, bkpQx, 14) + 270fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, bjpQx, 14) + bbQx; 271fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ajQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss72Q14, akmQx, 14) + 272fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, ajmQx, 14); 273fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org bjQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss72Q14, bkmQx, 14) + 274fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, bjmQx, 14); 275b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // 32+4*8=64 or 32+4*20=112 276b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 277b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k1] = akQx - bjQx; 278b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k4] = akQx + bjQx; 279b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k1] = bkQx + ajQx; 280b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k4] = bkQx - ajQx; 281b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 282fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org akQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, akpQx, 14) + 283fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc72Q14, ajpQx, 14) + aaQx; 284fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org bkQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, bkpQx, 14) + 285fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc72Q14, bjpQx, 14) + bbQx; 286fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ajQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, akmQx, 14) - 287fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss72Q14, ajmQx, 14); 288fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org bjQx = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, bkmQx, 14) - 289fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss72Q14, bjmQx, 14); 290b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // 8+4*8=40 or 8+4*20=88 291b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 292b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k2] = akQx - bjQx; 293b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k3] = akQx + bjQx; 294b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k2] = bkQx + ajQx; 295b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k3] = bkQx - ajQx; 296b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 297b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = k4 + 4; 298b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 299b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 12*(64+40+10) = 1368 for 16x16 muls, but 12*(112+88+10) = 2520 cycles for 16x32 muls 300b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk -= 239; 301b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 302b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 4*1368 = 5472 for 16x16 muls, but 4*2520 = 10080 cycles for 16x32 muls 303b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 304b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* multiply by rotation factor for odd factor 3 or 5 (not for 4) 305b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org Same code (duplicated) for both ii=2 and ii=3 */ 306b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = 1; 307b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ee=0; 308b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 309b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (gg=0; gg<3; gg++) { 310b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk += 4; 311fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org dd = 12 + (int16_t)WEBRTC_SPL_MUL_16_16(12, gg); 312b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ff = 0; 313b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (hh=0; hh<4; hh++) { 314b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ff = ff+dd; 315b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ee = ff+60; 316b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (ii=0; ii<12; ii++) { 317b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akQx = RexQx[kk]; 318b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkQx = ImxQx[kk]; 319b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 320b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ccc2Q14 = kCosTabFfftQ14[ff]; 321b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = kCosTabFfftQ14[ee]; 322b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 323b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (iSign==1) { 324b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org sss2Q14 = -sss2Q14; 325b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 326b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 327fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org RexQx[kk] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, akQx, 14) - 328fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, bkQx, 14); 329fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org ImxQx[kk] = (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(sss2Q14, akQx, 14) + 330fbda0fcf2f9e82c82bcaac138f44d4e5144f6e0dpbos@webrtc.org (int16_t)WEBRTC_SPL_MUL_16_16_RSFT(ccc2Q14, bkQx, 14); 331b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 332b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk += 20; 333b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 334b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = kk - 236; 335b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 12*(12+12) = 288 for 16x16 muls, but 12*(12+32) = 528 cycles for 16x32 muls 336b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 337b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org kk = kk - 19; 338b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 4*288+6 for 16x16 muls, but 4*528+6 cycles for 16x32 muls 339b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 340b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 3*4*288+6 = 3462 for 16x16 muls, but 3*4*528+6 = 6342 cycles for 16x32 muls 341b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 342b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 343b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // last transform for factor of 4 */ 344b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (kk=0; kk<240; kk=kk+4) { 345b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k1 = kk + 1; 346b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k2 = k1 + 1; 347b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org k3 = k2 + 1; 348b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 349b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akpQx = RexQx[kk] + RexQx[k2]; 350b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akmQx = RexQx[kk] - RexQx[k2]; 351b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajpQx = RexQx[k1] + RexQx[k3]; 352b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajmQx = RexQx[k1] - RexQx[k3]; 353b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkpQx = ImxQx[kk] + ImxQx[k2]; 354b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkmQx = ImxQx[kk] - ImxQx[k2]; 355b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjpQx = ImxQx[k1] + ImxQx[k3]; 356b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjmQx = ImxQx[k1] - ImxQx[k3]; 357b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[kk] = akpQx + ajpQx; 358b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[kk] = bkpQx + bjpQx; 359b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ajpQx = akpQx - ajpQx; 360b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bjpQx = bkpQx - bjpQx; 361b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (iSign < 0) { 362b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akpQx = akmQx + bjmQx; 363b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkpQx = bkmQx - ajmQx; 364b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akmQx -= bjmQx; 365b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkmQx += ajmQx; 366b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } else { 367b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akpQx = akmQx - bjmQx; 368b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkpQx = bkmQx + ajmQx; 369b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org akmQx += bjmQx; 370b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bkmQx -= ajmQx; 371b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 372b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k1] = akpQx; 373b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k2] = ajpQx; 374b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[k3] = akmQx; 375b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k1] = bkpQx; 376b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k2] = bjpQx; 377b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[k3] = bkmQx; 378b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 379b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 60*45 = 2700 for 16x16 muls, but 60*45 = 2700 cycles for 16x32 muls 380b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 381b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org /* permute the results to normal order */ 382b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (ii=0; ii<240; ii++) { 383b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ReDATAQx[ii]=RexQx[ii]; 384b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImDATAQx[ii]=ImxQx[ii]; 385b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 386b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 240*2=480 cycles 387b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 388b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (ii=0; ii<240; ii++) { 389b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org RexQx[ii]=ReDATAQx[kSortTabFft[ii]]; 390b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ImxQx[ii]=ImDATAQx[kSortTabFft[ii]]; 391b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 392b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 240*2*2=960 cycles 393b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 394b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Total complexity: 395b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // 16x16 16x32 396b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 10 10 397b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 99 171 398b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 2972 3932 399b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 2736 5776 400b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 5472 10080 401b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 3462 6342 402b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 2700 2700 403b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 480 480 404b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Complexity: 960 960 405b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // ======================= 406b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // 18891 30451 407b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // 408b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // If this FFT is called 2 time each frame, i.e. 67 times per second, it will correspond to 409b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // a C54 complexity of 67*18891/1000000 = 1.27 MIPS with 16x16-muls, and 67*30451/1000000 = 410b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // = 2.04 MIPS with 16x32-muls. Note that this routine somtimes is called 6 times during the 411b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // encoding of a frame, i.e. the max complexity would be 7/2*1.27 = 4.4 MIPS for the 16x16 mul case. 412b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 413b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 414b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org return 0; 415b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org} 416