Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
PojavLauncherTeam
GitHub Repository: PojavLauncherTeam/mobile
 Path: blob/master/src/java.desktop/share/classes/com/sun/media/sound/FFT.java
41161 views
1
/*

2
 * Copyright (c) 2007, 2013, Oracle and/or its affiliates. All rights reserved.

3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

4
 *

5
 * This code is free software; you can redistribute it and/or modify it

6
 * under the terms of the GNU General Public License version 2 only, as

7
 * published by the Free Software Foundation.  Oracle designates this

8
 * particular file as subject to the "Classpath" exception as provided

9
 * by Oracle in the LICENSE file that accompanied this code.

10
 *

11
 * This code is distributed in the hope that it will be useful, but WITHOUT

12
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

13
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

14
 * version 2 for more details (a copy is included in the LICENSE file that

15
 * accompanied this code).

16
 *

17
 * You should have received a copy of the GNU General Public License version

18
 * 2 along with this work; if not, write to the Free Software Foundation,

19
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

20
 *

21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

22
 * or visit www.oracle.com if you need additional information or have any

23
 * questions.

24
 */

25


26
package com.sun.media.sound;

27


28
/**

29
 * Fast Fourier Transformer.

30
 *

31
 * @author Karl Helgason

32
 */

33
public final class FFT {

34


35
    private final double[] w;

36
    private final int fftFrameSize;

37
    private final int sign;

38
    private final int[] bitm_array;

39
    private final int fftFrameSize2;

40


41
    // Sign = -1 is FFT, 1 is IFFT (inverse FFT)

42
    // Data = Interlaced double array to be transformed.

43
    // The order is: real (sin), complex (cos)

44
    // Framesize must be power of 2

45
    public FFT(int fftFrameSize, int sign) {

46
        w = computeTwiddleFactors(fftFrameSize, sign);

47


48
        this.fftFrameSize = fftFrameSize;

49
        this.sign = sign;

50
        fftFrameSize2 = fftFrameSize << 1;

51


52
        // Pre-process Bit-Reversal

53
        bitm_array = new int[fftFrameSize2];

54
        for (int i = 2; i < fftFrameSize2; i += 2) {

55
            int j;

56
            int bitm;

57
            for (bitm = 2, j = 0; bitm < fftFrameSize2; bitm <<= 1) {

58
                if ((i & bitm) != 0)

59
                    j++;

60
                j <<= 1;

61
            }

62
            bitm_array[i] = j;

63
        }

64


65
    }

66


67
    public void transform(double[] data) {

68
        bitreversal(data);

69
        calc(fftFrameSize, data, sign, w);

70
    }

71


72
    private static double[] computeTwiddleFactors(int fftFrameSize,

73
            int sign) {

74


75
        int imax = (int) (Math.log(fftFrameSize) / Math.log(2.));

76


77
        double[] warray = new double[(fftFrameSize - 1) * 4];

78
        int w_index = 0;

79


80
        for (int i = 0,  nstep = 2; i < imax; i++) {

81
            int jmax = nstep;

82
            nstep <<= 1;

83


84
            double wr = 1.0;

85
            double wi = 0.0;

86


87
            double arg = Math.PI / (jmax >> 1);

88
            double wfr = Math.cos(arg);

89
            double wfi = sign * Math.sin(arg);

90


91
            for (int j = 0; j < jmax; j += 2) {

92
                warray[w_index++] = wr;

93
                warray[w_index++] = wi;

94


95
                double tempr = wr;

96
                wr = tempr * wfr - wi * wfi;

97
                wi = tempr * wfi + wi * wfr;

98
            }

99
        }

100


101
        // PRECOMPUTATION of wwr1, wwi1 for factor 4 Decomposition (3 * complex

102
        // operators and 8 +/- complex operators)

103
        {

104
            w_index = 0;

105
            int w_index2 = warray.length >> 1;

106
            for (int i = 0,  nstep = 2; i < (imax - 1); i++) {

107
                int jmax = nstep;

108
                nstep *= 2;

109


110
                int ii = w_index + jmax;

111
                for (int j = 0; j < jmax; j += 2) {

112
                    double wr = warray[w_index++];

113
                    double wi = warray[w_index++];

114
                    double wr1 = warray[ii++];

115
                    double wi1 = warray[ii++];

116
                    warray[w_index2++] = wr * wr1 - wi * wi1;

117
                    warray[w_index2++] = wr * wi1 + wi * wr1;

118
                }

119
            }

120


121
        }

122


123
        return warray;

124
    }

125


126
    private static void calc(int fftFrameSize, double[] data, int sign,

127
            double[] w) {

128


129
        final int fftFrameSize2 = fftFrameSize << 1;

130


131
        int nstep = 2;

132


133
        if (nstep >= fftFrameSize2)

134
            return;

135
        int i = nstep - 2;

136
        if (sign == -1)

137
            calcF4F(fftFrameSize, data, i, nstep, w);

138
        else

139
            calcF4I(fftFrameSize, data, i, nstep, w);

140


141
    }

142


143
    private static void calcF2E(int fftFrameSize, double[] data, int i,

144
            int nstep, double[] w) {

145
        int jmax = nstep;

146
        for (int n = 0; n < jmax; n += 2) {

147
            double wr = w[i++];

148
            double wi = w[i++];

149
            int m = n + jmax;

150
            double datam_r = data[m];

151
            double datam_i = data[m + 1];

152
            double datan_r = data[n];

153
            double datan_i = data[n + 1];

154
            double tempr = datam_r * wr - datam_i * wi;

155
            double tempi = datam_r * wi + datam_i * wr;

156
            data[m] = datan_r - tempr;

157
            data[m + 1] = datan_i - tempi;

158
            data[n] = datan_r + tempr;

159
            data[n + 1] = datan_i + tempi;

160
        }

161
        return;

162


163
    }

164


165
    // Perform Factor-4 Decomposition with 3 * complex operators and 8 +/-

166
    // complex operators

167
    private static void calcF4F(int fftFrameSize, double[] data, int i,

168
            int nstep, double[] w) {

169
        final int fftFrameSize2 = fftFrameSize << 1; // 2*fftFrameSize;

170
        // Factor-4 Decomposition

171


172
        int w_len = w.length >> 1;

173
        while (nstep < fftFrameSize2) {

174


175
            if (nstep << 2 == fftFrameSize2) {

176
                // Goto Factor-4 Final Decomposition

177
                // calcF4E(data, i, nstep, -1, w);

178
                calcF4FE(fftFrameSize, data, i, nstep, w);

179
                return;

180
            }

181
            int jmax = nstep;

182
            int nnstep = nstep << 1;

183
            if (nnstep == fftFrameSize2) {

184
                // Factor-4 Decomposition not possible

185
                calcF2E(fftFrameSize, data, i, nstep, w);

186
                return;

187
            }

188
            nstep <<= 2;

189
            int ii = i + jmax;

190
            int iii = i + w_len;

191


192
            {

193
                i += 2;

194
                ii += 2;

195
                iii += 2;

196


197
                for (int n = 0; n < fftFrameSize2; n += nstep) {

198
                    int m = n + jmax;

199


200
                    double datam1_r = data[m];

201
                    double datam1_i = data[m + 1];

202
                    double datan1_r = data[n];

203
                    double datan1_i = data[n + 1];

204


205
                    n += nnstep;

206
                    m += nnstep;

207
                    double datam2_r = data[m];

208
                    double datam2_i = data[m + 1];

209
                    double datan2_r = data[n];

210
                    double datan2_i = data[n + 1];

211


212
                    double tempr = datam1_r;

213
                    double tempi = datam1_i;

214


215
                    datam1_r = datan1_r - tempr;

216
                    datam1_i = datan1_i - tempi;

217
                    datan1_r = datan1_r + tempr;

218
                    datan1_i = datan1_i + tempi;

219


220
                    double n2w1r = datan2_r;

221
                    double n2w1i = datan2_i;

222
                    double m2ww1r = datam2_r;

223
                    double m2ww1i = datam2_i;

224


225
                    tempr = m2ww1r - n2w1r;

226
                    tempi = m2ww1i - n2w1i;

227


228
                    datam2_r = datam1_r + tempi;

229
                    datam2_i = datam1_i - tempr;

230
                    datam1_r = datam1_r - tempi;

231
                    datam1_i = datam1_i + tempr;

232


233
                    tempr = n2w1r + m2ww1r;

234
                    tempi = n2w1i + m2ww1i;

235


236
                    datan2_r = datan1_r - tempr;

237
                    datan2_i = datan1_i - tempi;

238
                    datan1_r = datan1_r + tempr;

239
                    datan1_i = datan1_i + tempi;

240


241
                    data[m] = datam2_r;

242
                    data[m + 1] = datam2_i;

243
                    data[n] = datan2_r;

244
                    data[n + 1] = datan2_i;

245


246
                    n -= nnstep;

247
                    m -= nnstep;

248
                    data[m] = datam1_r;

249
                    data[m + 1] = datam1_i;

250
                    data[n] = datan1_r;

251
                    data[n + 1] = datan1_i;

252


253
                }

254
            }

255


256
            for (int j = 2; j < jmax; j += 2) {

257
                double wr = w[i++];

258
                double wi = w[i++];

259
                double wr1 = w[ii++];

260
                double wi1 = w[ii++];

261
                double wwr1 = w[iii++];

262
                double wwi1 = w[iii++];

263
                // double wwr1 = wr * wr1 - wi * wi1; // these numbers can be

264
                // precomputed!!!

265
                // double wwi1 = wr * wi1 + wi * wr1;

266


267
                for (int n = j; n < fftFrameSize2; n += nstep) {

268
                    int m = n + jmax;

269


270
                    double datam1_r = data[m];

271
                    double datam1_i = data[m + 1];

272
                    double datan1_r = data[n];

273
                    double datan1_i = data[n + 1];

274


275
                    n += nnstep;

276
                    m += nnstep;

277
                    double datam2_r = data[m];

278
                    double datam2_i = data[m + 1];

279
                    double datan2_r = data[n];

280
                    double datan2_i = data[n + 1];

281


282
                    double tempr = datam1_r * wr - datam1_i * wi;

283
                    double tempi = datam1_r * wi + datam1_i * wr;

284


285
                    datam1_r = datan1_r - tempr;

286
                    datam1_i = datan1_i - tempi;

287
                    datan1_r = datan1_r + tempr;

288
                    datan1_i = datan1_i + tempi;

289


290
                    double n2w1r = datan2_r * wr1 - datan2_i * wi1;

291
                    double n2w1i = datan2_r * wi1 + datan2_i * wr1;

292
                    double m2ww1r = datam2_r * wwr1 - datam2_i * wwi1;

293
                    double m2ww1i = datam2_r * wwi1 + datam2_i * wwr1;

294


295
                    tempr = m2ww1r - n2w1r;

296
                    tempi = m2ww1i - n2w1i;

297


298
                    datam2_r = datam1_r + tempi;

299
                    datam2_i = datam1_i - tempr;

300
                    datam1_r = datam1_r - tempi;

301
                    datam1_i = datam1_i + tempr;

302


303
                    tempr = n2w1r + m2ww1r;

304
                    tempi = n2w1i + m2ww1i;

305


306
                    datan2_r = datan1_r - tempr;

307
                    datan2_i = datan1_i - tempi;

308
                    datan1_r = datan1_r + tempr;

309
                    datan1_i = datan1_i + tempi;

310


311
                    data[m] = datam2_r;

312
                    data[m + 1] = datam2_i;

313
                    data[n] = datan2_r;

314
                    data[n + 1] = datan2_i;

315


316
                    n -= nnstep;

317
                    m -= nnstep;

318
                    data[m] = datam1_r;

319
                    data[m + 1] = datam1_i;

320
                    data[n] = datan1_r;

321
                    data[n + 1] = datan1_i;

322
                }

323
            }

324


325
            i += jmax << 1;

326


327
        }

328


329
        calcF2E(fftFrameSize, data, i, nstep, w);

330


331
    }

332


333
    // Perform Factor-4 Decomposition with 3 * complex operators and 8 +/-

334
    // complex operators

335
    private static void calcF4I(int fftFrameSize, double[] data, int i,

336
            int nstep, double[] w) {

337
        final int fftFrameSize2 = fftFrameSize << 1; // 2*fftFrameSize;

338
        // Factor-4 Decomposition

339


340
        int w_len = w.length >> 1;

341
        while (nstep < fftFrameSize2) {

342


343
            if (nstep << 2 == fftFrameSize2) {

344
                // Goto Factor-4 Final Decomposition

345
                // calcF4E(data, i, nstep, 1, w);

346
                calcF4IE(fftFrameSize, data, i, nstep, w);

347
                return;

348
            }

349
            int jmax = nstep;

350
            int nnstep = nstep << 1;

351
            if (nnstep == fftFrameSize2) {

352
                // Factor-4 Decomposition not possible

353
                calcF2E(fftFrameSize, data, i, nstep, w);

354
                return;

355
            }

356
            nstep <<= 2;

357
            int ii = i + jmax;

358
            int iii = i + w_len;

359
            {

360
                i += 2;

361
                ii += 2;

362
                iii += 2;

363


364
                for (int n = 0; n < fftFrameSize2; n += nstep) {

365
                    int m = n + jmax;

366


367
                    double datam1_r = data[m];

368
                    double datam1_i = data[m + 1];

369
                    double datan1_r = data[n];

370
                    double datan1_i = data[n + 1];

371


372
                    n += nnstep;

373
                    m += nnstep;

374
                    double datam2_r = data[m];

375
                    double datam2_i = data[m + 1];

376
                    double datan2_r = data[n];

377
                    double datan2_i = data[n + 1];

378


379
                    double tempr = datam1_r;

380
                    double tempi = datam1_i;

381


382
                    datam1_r = datan1_r - tempr;

383
                    datam1_i = datan1_i - tempi;

384
                    datan1_r = datan1_r + tempr;

385
                    datan1_i = datan1_i + tempi;

386


387
                    double n2w1r = datan2_r;

388
                    double n2w1i = datan2_i;

389
                    double m2ww1r = datam2_r;

390
                    double m2ww1i = datam2_i;

391


392
                    tempr = n2w1r - m2ww1r;

393
                    tempi = n2w1i - m2ww1i;

394


395
                    datam2_r = datam1_r + tempi;

396
                    datam2_i = datam1_i - tempr;

397
                    datam1_r = datam1_r - tempi;

398
                    datam1_i = datam1_i + tempr;

399


400
                    tempr = n2w1r + m2ww1r;

401
                    tempi = n2w1i + m2ww1i;

402


403
                    datan2_r = datan1_r - tempr;

404
                    datan2_i = datan1_i - tempi;

405
                    datan1_r = datan1_r + tempr;

406
                    datan1_i = datan1_i + tempi;

407


408
                    data[m] = datam2_r;

409
                    data[m + 1] = datam2_i;

410
                    data[n] = datan2_r;

411
                    data[n + 1] = datan2_i;

412


413
                    n -= nnstep;

414
                    m -= nnstep;

415
                    data[m] = datam1_r;

416
                    data[m + 1] = datam1_i;

417
                    data[n] = datan1_r;

418
                    data[n + 1] = datan1_i;

419


420
                }

421


422
            }

423
            for (int j = 2; j < jmax; j += 2) {

424
                double wr = w[i++];

425
                double wi = w[i++];

426
                double wr1 = w[ii++];

427
                double wi1 = w[ii++];

428
                double wwr1 = w[iii++];

429
                double wwi1 = w[iii++];

430
                // double wwr1 = wr * wr1 - wi * wi1; // these numbers can be

431
                // precomputed!!!

432
                // double wwi1 = wr * wi1 + wi * wr1;

433


434
                for (int n = j; n < fftFrameSize2; n += nstep) {

435
                    int m = n + jmax;

436


437
                    double datam1_r = data[m];

438
                    double datam1_i = data[m + 1];

439
                    double datan1_r = data[n];

440
                    double datan1_i = data[n + 1];

441


442
                    n += nnstep;

443
                    m += nnstep;

444
                    double datam2_r = data[m];

445
                    double datam2_i = data[m + 1];

446
                    double datan2_r = data[n];

447
                    double datan2_i = data[n + 1];

448


449
                    double tempr = datam1_r * wr - datam1_i * wi;

450
                    double tempi = datam1_r * wi + datam1_i * wr;

451


452
                    datam1_r = datan1_r - tempr;

453
                    datam1_i = datan1_i - tempi;

454
                    datan1_r = datan1_r + tempr;

455
                    datan1_i = datan1_i + tempi;

456


457
                    double n2w1r = datan2_r * wr1 - datan2_i * wi1;

458
                    double n2w1i = datan2_r * wi1 + datan2_i * wr1;

459
                    double m2ww1r = datam2_r * wwr1 - datam2_i * wwi1;

460
                    double m2ww1i = datam2_r * wwi1 + datam2_i * wwr1;

461


462
                    tempr = n2w1r - m2ww1r;

463
                    tempi = n2w1i - m2ww1i;

464


465
                    datam2_r = datam1_r + tempi;

466
                    datam2_i = datam1_i - tempr;

467
                    datam1_r = datam1_r - tempi;

468
                    datam1_i = datam1_i + tempr;

469


470
                    tempr = n2w1r + m2ww1r;

471
                    tempi = n2w1i + m2ww1i;

472


473
                    datan2_r = datan1_r - tempr;

474
                    datan2_i = datan1_i - tempi;

475
                    datan1_r = datan1_r + tempr;

476
                    datan1_i = datan1_i + tempi;

477


478
                    data[m] = datam2_r;

479
                    data[m + 1] = datam2_i;

480
                    data[n] = datan2_r;

481
                    data[n + 1] = datan2_i;

482


483
                    n -= nnstep;

484
                    m -= nnstep;

485
                    data[m] = datam1_r;

486
                    data[m + 1] = datam1_i;

487
                    data[n] = datan1_r;

488
                    data[n + 1] = datan1_i;

489


490
                }

491
            }

492


493
            i += jmax << 1;

494


495
        }

496


497
        calcF2E(fftFrameSize, data, i, nstep, w);

498


499
    }

500


501
    // Perform Factor-4 Decomposition with 3 * complex operators and 8 +/-

502
    // complex operators

503
    private static void calcF4FE(int fftFrameSize, double[] data, int i,

504
            int nstep, double[] w) {

505
        final int fftFrameSize2 = fftFrameSize << 1; // 2*fftFrameSize;

506
        // Factor-4 Decomposition

507


508
        int w_len = w.length >> 1;

509
        while (nstep < fftFrameSize2) {

510


511
            int jmax = nstep;

512
            int nnstep = nstep << 1;

513
            if (nnstep == fftFrameSize2) {

514
                // Factor-4 Decomposition not possible

515
                calcF2E(fftFrameSize, data, i, nstep, w);

516
                return;

517
            }

518
            nstep <<= 2;

519
            int ii = i + jmax;

520
            int iii = i + w_len;

521
            for (int n = 0; n < jmax; n += 2) {

522
                double wr = w[i++];

523
                double wi = w[i++];

524
                double wr1 = w[ii++];

525
                double wi1 = w[ii++];

526
                double wwr1 = w[iii++];

527
                double wwi1 = w[iii++];

528
                // double wwr1 = wr * wr1 - wi * wi1; // these numbers can be

529
                // precomputed!!!

530
                // double wwi1 = wr * wi1 + wi * wr1;

531


532
                int m = n + jmax;

533


534
                double datam1_r = data[m];

535
                double datam1_i = data[m + 1];

536
                double datan1_r = data[n];

537
                double datan1_i = data[n + 1];

538


539
                n += nnstep;

540
                m += nnstep;

541
                double datam2_r = data[m];

542
                double datam2_i = data[m + 1];

543
                double datan2_r = data[n];

544
                double datan2_i = data[n + 1];

545


546
                double tempr = datam1_r * wr - datam1_i * wi;

547
                double tempi = datam1_r * wi + datam1_i * wr;

548


549
                datam1_r = datan1_r - tempr;

550
                datam1_i = datan1_i - tempi;

551
                datan1_r = datan1_r + tempr;

552
                datan1_i = datan1_i + tempi;

553


554
                double n2w1r = datan2_r * wr1 - datan2_i * wi1;

555
                double n2w1i = datan2_r * wi1 + datan2_i * wr1;

556
                double m2ww1r = datam2_r * wwr1 - datam2_i * wwi1;

557
                double m2ww1i = datam2_r * wwi1 + datam2_i * wwr1;

558


559
                tempr = m2ww1r - n2w1r;

560
                tempi = m2ww1i - n2w1i;

561


562
                datam2_r = datam1_r + tempi;

563
                datam2_i = datam1_i - tempr;

564
                datam1_r = datam1_r - tempi;

565
                datam1_i = datam1_i + tempr;

566


567
                tempr = n2w1r + m2ww1r;

568
                tempi = n2w1i + m2ww1i;

569


570
                datan2_r = datan1_r - tempr;

571
                datan2_i = datan1_i - tempi;

572
                datan1_r = datan1_r + tempr;

573
                datan1_i = datan1_i + tempi;

574


575
                data[m] = datam2_r;

576
                data[m + 1] = datam2_i;

577
                data[n] = datan2_r;

578
                data[n + 1] = datan2_i;

579


580
                n -= nnstep;

581
                m -= nnstep;

582
                data[m] = datam1_r;

583
                data[m + 1] = datam1_i;

584
                data[n] = datan1_r;

585
                data[n + 1] = datan1_i;

586


587
            }

588


589
            i += jmax << 1;

590


591
        }

592
    }

593


594
    // Perform Factor-4 Decomposition with 3 * complex operators and 8 +/-

595
    // complex operators

596
    private static void calcF4IE(int fftFrameSize, double[] data, int i,

597
            int nstep, double[] w) {

598
        final int fftFrameSize2 = fftFrameSize << 1; // 2*fftFrameSize;

599
        // Factor-4 Decomposition

600


601
        int w_len = w.length >> 1;

602
        while (nstep < fftFrameSize2) {

603


604
            int jmax = nstep;

605
            int nnstep = nstep << 1;

606
            if (nnstep == fftFrameSize2) {

607
                // Factor-4 Decomposition not possible

608
                calcF2E(fftFrameSize, data, i, nstep, w);

609
                return;

610
            }

611
            nstep <<= 2;

612
            int ii = i + jmax;

613
            int iii = i + w_len;

614
            for (int n = 0; n < jmax; n += 2) {

615
                double wr = w[i++];

616
                double wi = w[i++];

617
                double wr1 = w[ii++];

618
                double wi1 = w[ii++];

619
                double wwr1 = w[iii++];

620
                double wwi1 = w[iii++];

621
                // double wwr1 = wr * wr1 - wi * wi1; // these numbers can be

622
                // precomputed!!!

623
                // double wwi1 = wr * wi1 + wi * wr1;

624


625
                int m = n + jmax;

626


627
                double datam1_r = data[m];

628
                double datam1_i = data[m + 1];

629
                double datan1_r = data[n];

630
                double datan1_i = data[n + 1];

631


632
                n += nnstep;

633
                m += nnstep;

634
                double datam2_r = data[m];

635
                double datam2_i = data[m + 1];

636
                double datan2_r = data[n];

637
                double datan2_i = data[n + 1];

638


639
                double tempr = datam1_r * wr - datam1_i * wi;

640
                double tempi = datam1_r * wi + datam1_i * wr;

641


642
                datam1_r = datan1_r - tempr;

643
                datam1_i = datan1_i - tempi;

644
                datan1_r = datan1_r + tempr;

645
                datan1_i = datan1_i + tempi;

646


647
                double n2w1r = datan2_r * wr1 - datan2_i * wi1;

648
                double n2w1i = datan2_r * wi1 + datan2_i * wr1;

649
                double m2ww1r = datam2_r * wwr1 - datam2_i * wwi1;

650
                double m2ww1i = datam2_r * wwi1 + datam2_i * wwr1;

651


652
                tempr = n2w1r - m2ww1r;

653
                tempi = n2w1i - m2ww1i;

654


655
                datam2_r = datam1_r + tempi;

656
                datam2_i = datam1_i - tempr;

657
                datam1_r = datam1_r - tempi;

658
                datam1_i = datam1_i + tempr;

659


660
                tempr = n2w1r + m2ww1r;

661
                tempi = n2w1i + m2ww1i;

662


663
                datan2_r = datan1_r - tempr;

664
                datan2_i = datan1_i - tempi;

665
                datan1_r = datan1_r + tempr;

666
                datan1_i = datan1_i + tempi;

667


668
                data[m] = datam2_r;

669
                data[m + 1] = datam2_i;

670
                data[n] = datan2_r;

671
                data[n + 1] = datan2_i;

672


673
                n -= nnstep;

674
                m -= nnstep;

675
                data[m] = datam1_r;

676
                data[m + 1] = datam1_i;

677
                data[n] = datan1_r;

678
                data[n + 1] = datan1_i;

679


680
            }

681


682
            i += jmax << 1;

683


684
        }

685
    }

686


687
    private void bitreversal(double[] data) {

688
        if (fftFrameSize < 4)

689
            return;

690


691
        int inverse = fftFrameSize2 - 2;

692
        for (int i = 0; i < fftFrameSize; i += 4) {

693
            int j = bitm_array[i];

694


695
            // Performing Bit-Reversal, even v.s. even, O(2N)

696
            if (i < j) {

697


698
                int n = i;

699
                int m = j;

700


701
                // COMPLEX: SWAP(data[n], data[m])

702
                // Real Part

703
                double tempr = data[n];

704
                data[n] = data[m];

705
                data[m] = tempr;

706
                // Imagery Part

707
                n++;

708
                m++;

709
                double tempi = data[n];

710
                data[n] = data[m];

711
                data[m] = tempi;

712


713
                n = inverse - i;

714
                m = inverse - j;

715


716
                // COMPLEX: SWAP(data[n], data[m])

717
                // Real Part

718
                tempr = data[n];

719
                data[n] = data[m];

720
                data[m] = tempr;

721
                // Imagery Part

722
                n++;

723
                m++;

724
                tempi = data[n];

725
                data[n] = data[m];

726
                data[m] = tempi;

727
            }

728


729
            // Performing Bit-Reversal, odd v.s. even, O(N)

730


731
            int m = j + fftFrameSize; // bitm_array[i+2];

732
            // COMPLEX: SWAP(data[n], data[m])

733
            // Real Part

734
            int n = i + 2;

735
            double tempr = data[n];

736
            data[n] = data[m];

737
            data[m] = tempr;

738
            // Imagery Part

739
            n++;

740
            m++;

741
            double tempi = data[n];

742
            data[n] = data[m];

743
            data[m] = tempi;

744
        }

745
    }

746
}

747


748