fork/rust-sdks

git clone https://git.julia.blue/fork/rust-sdks

Théo Monnomsoxr-sys (#438)2e4d385

livekit/livekit-ffi@0.13.0
36.5 KiB1346 linesraw
1/* Copyright Takuya OOURA, 1996-2001.
2
3You may use, copy, modify and distribute this code for any
4purpose (include commercial use) and without fee.  Please
5refer to this package when you modify this code.
6
7Package home:  http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html
8
9Fast Fourier/Cosine/Sine Transform
10    dimension   :one
11    data length :power of 2
12    decimation  :frequency
13    radix       :4, 2
14    data        :inplace
15    table       :use
16functions
17    cdft: Complex Discrete Fourier Transform
18    rdft: Real Discrete Fourier Transform
19    ddct: Discrete Cosine Transform
20    ddst: Discrete Sine Transform
21    dfct: Cosine Transform of RDFT (Real Symmetric DFT)
22    dfst: Sine Transform of RDFT (Real Anti-symmetric DFT)
23function prototypes
24    void cdft(int, int, double *, int *, double *);
25    void rdft(int, int, double *, int *, double *);
26    void ddct(int, int, double *, int *, double *);
27    void ddst(int, int, double *, int *, double *);
28    void dfct(int, double *, double *, int *, double *);
29    void dfst(int, double *, double *, int *, double *);
30
31
32-------- Complex DFT (Discrete Fourier Transform) --------
33    [definition]
34        <case1>
35            X[k] = sum_j=0^n-1 x[j]*exp(2*pi*i*j*k/n), 0<=k<n
36        <case2>
37            X[k] = sum_j=0^n-1 x[j]*exp(-2*pi*i*j*k/n), 0<=k<n
38        (notes: sum_j=0^n-1 is a summation from j=0 to n-1)
39    [usage]
40        <case1>
41            ip[0] = 0; // first time only
42            cdft(2*n, 1, a, ip, w);
43        <case2>
44            ip[0] = 0; // first time only
45            cdft(2*n, -1, a, ip, w);
46    [parameters]
47        2*n            :data length (int)
48                        n >= 1, n = power of 2
49        a[0...2*n-1]   :input/output data (double *)
50                        input data
51                            a[2*j] = Re(x[j]),
52                            a[2*j+1] = Im(x[j]), 0<=j<n
53                        output data
54                            a[2*k] = Re(X[k]),
55                            a[2*k+1] = Im(X[k]), 0<=k<n
56        ip[0...*]      :work area for bit reversal (int *)
57                        length of ip >= 2+sqrt(n)
58                        strictly,
59                        length of ip >=
60                            2+(1<<(int)(log(n+0.5)/log(2))/2).
61                        ip[0],ip[1] are pointers of the cos/sin table.
62        w[0...n/2-1]   :cos/sin table (double *)
63                        w[],ip[] are initialized if ip[0] == 0.
64    [remark]
65        Inverse of
66            cdft(2*n, -1, a, ip, w);
67        is
68            cdft(2*n, 1, a, ip, w);
69            for (j = 0; j <= 2 * n - 1; j++) {
70                a[j] *= 1.0 / n;
71            }
72        .
73
74
75-------- Real DFT / Inverse of Real DFT --------
76    [definition]
77        <case1> RDFT
78            R[k] = sum_j=0^n-1 a[j]*cos(2*pi*j*k/n), 0<=k<=n/2
79            I[k] = sum_j=0^n-1 a[j]*sin(2*pi*j*k/n), 0<k<n/2
80        <case2> IRDFT (excluding scale)
81            a[k] = (R[0] + R[n/2]*cos(pi*k))/2 +
82                   sum_j=1^n/2-1 R[j]*cos(2*pi*j*k/n) +
83                   sum_j=1^n/2-1 I[j]*sin(2*pi*j*k/n), 0<=k<n
84    [usage]
85        <case1>
86            ip[0] = 0; // first time only
87            rdft(n, 1, a, ip, w);
88        <case2>
89            ip[0] = 0; // first time only
90            rdft(n, -1, a, ip, w);
91    [parameters]
92        n              :data length (int)
93                        n >= 2, n = power of 2
94        a[0...n-1]     :input/output data (double *)
95                        <case1>
96                            output data
97                                a[2*k] = R[k], 0<=k<n/2
98                                a[2*k+1] = I[k], 0<k<n/2
99                                a[1] = R[n/2]
100                        <case2>
101                            input data
102                                a[2*j] = R[j], 0<=j<n/2
103                                a[2*j+1] = I[j], 0<j<n/2
104                                a[1] = R[n/2]
105        ip[0...*]      :work area for bit reversal (int *)
106                        length of ip >= 2+sqrt(n/2)
107                        strictly,
108                        length of ip >=
109                            2+(1<<(int)(log(n/2+0.5)/log(2))/2).
110                        ip[0],ip[1] are pointers of the cos/sin table.
111        w[0...n/2-1]   :cos/sin table (double *)
112                        w[],ip[] are initialized if ip[0] == 0.
113    [remark]
114        Inverse of
115            rdft(n, 1, a, ip, w);
116        is
117            rdft(n, -1, a, ip, w);
118            for (j = 0; j <= n - 1; j++) {
119                a[j] *= 2.0 / n;
120            }
121        .
122
123
124-------- DCT (Discrete Cosine Transform) / Inverse of DCT --------
125    [definition]
126        <case1> IDCT (excluding scale)
127            C[k] = sum_j=0^n-1 a[j]*cos(pi*j*(k+1/2)/n), 0<=k<n
128        <case2> DCT
129            C[k] = sum_j=0^n-1 a[j]*cos(pi*(j+1/2)*k/n), 0<=k<n
130    [usage]
131        <case1>
132            ip[0] = 0; // first time only
133            ddct(n, 1, a, ip, w);
134        <case2>
135            ip[0] = 0; // first time only
136            ddct(n, -1, a, ip, w);
137    [parameters]
138        n              :data length (int)
139                        n >= 2, n = power of 2
140        a[0...n-1]     :input/output data (double *)
141                        output data
142                            a[k] = C[k], 0<=k<n
143        ip[0...*]      :work area for bit reversal (int *)
144                        length of ip >= 2+sqrt(n/2)
145                        strictly,
146                        length of ip >=
147                            2+(1<<(int)(log(n/2+0.5)/log(2))/2).
148                        ip[0],ip[1] are pointers of the cos/sin table.
149        w[0...n*5/4-1] :cos/sin table (double *)
150                        w[],ip[] are initialized if ip[0] == 0.
151    [remark]
152        Inverse of
153            ddct(n, -1, a, ip, w);
154        is
155            a[0] *= 0.5;
156            ddct(n, 1, a, ip, w);
157            for (j = 0; j <= n - 1; j++) {
158                a[j] *= 2.0 / n;
159            }
160        .
161
162
163-------- DST (Discrete Sine Transform) / Inverse of DST --------
164    [definition]
165        <case1> IDST (excluding scale)
166            S[k] = sum_j=1^n A[j]*sin(pi*j*(k+1/2)/n), 0<=k<n
167        <case2> DST
168            S[k] = sum_j=0^n-1 a[j]*sin(pi*(j+1/2)*k/n), 0<k<=n
169    [usage]
170        <case1>
171            ip[0] = 0; // first time only
172            ddst(n, 1, a, ip, w);
173        <case2>
174            ip[0] = 0; // first time only
175            ddst(n, -1, a, ip, w);
176    [parameters]
177        n              :data length (int)
178                        n >= 2, n = power of 2
179        a[0...n-1]     :input/output data (double *)
180                        <case1>
181                            input data
182                                a[j] = A[j], 0<j<n
183                                a[0] = A[n]
184                            output data
185                                a[k] = S[k], 0<=k<n
186                        <case2>
187                            output data
188                                a[k] = S[k], 0<k<n
189                                a[0] = S[n]
190        ip[0...*]      :work area for bit reversal (int *)
191                        length of ip >= 2+sqrt(n/2)
192                        strictly,
193                        length of ip >=
194                            2+(1<<(int)(log(n/2+0.5)/log(2))/2).
195                        ip[0],ip[1] are pointers of the cos/sin table.
196        w[0...n*5/4-1] :cos/sin table (double *)
197                        w[],ip[] are initialized if ip[0] == 0.
198    [remark]
199        Inverse of
200            ddst(n, -1, a, ip, w);
201        is
202            a[0] *= 0.5;
203            ddst(n, 1, a, ip, w);
204            for (j = 0; j <= n - 1; j++) {
205                a[j] *= 2.0 / n;
206            }
207        .
208
209
210-------- Cosine Transform of RDFT (Real Symmetric DFT) --------
211    [definition]
212        C[k] = sum_j=0^n a[j]*cos(pi*j*k/n), 0<=k<=n
213    [usage]
214        ip[0] = 0; // first time only
215        dfct(n, a, t, ip, w);
216    [parameters]
217        n              :data length - 1 (int)
218                        n >= 2, n = power of 2
219        a[0...n]       :input/output data (double *)
220                        output data
221                            a[k] = C[k], 0<=k<=n
222        t[0...n/2]     :work area (double *)
223        ip[0...*]      :work area for bit reversal (int *)
224                        length of ip >= 2+sqrt(n/4)
225                        strictly,
226                        length of ip >=
227                            2+(1<<(int)(log(n/4+0.5)/log(2))/2).
228                        ip[0],ip[1] are pointers of the cos/sin table.
229        w[0...n*5/8-1] :cos/sin table (double *)
230                        w[],ip[] are initialized if ip[0] == 0.
231    [remark]
232        Inverse of
233            a[0] *= 0.5;
234            a[n] *= 0.5;
235            dfct(n, a, t, ip, w);
236        is
237            a[0] *= 0.5;
238            a[n] *= 0.5;
239            dfct(n, a, t, ip, w);
240            for (j = 0; j <= n; j++) {
241                a[j] *= 2.0 / n;
242            }
243        .
244
245
246-------- Sine Transform of RDFT (Real Anti-symmetric DFT) --------
247    [definition]
248        S[k] = sum_j=1^n-1 a[j]*sin(pi*j*k/n), 0<k<n
249    [usage]
250        ip[0] = 0; // first time only
251        dfst(n, a, t, ip, w);
252    [parameters]
253        n              :data length + 1 (int)
254                        n >= 2, n = power of 2
255        a[0...n-1]     :input/output data (double *)
256                        output data
257                            a[k] = S[k], 0<k<n
258                        (a[0] is used for work area)
259        t[0...n/2-1]   :work area (double *)
260        ip[0...*]      :work area for bit reversal (int *)
261                        length of ip >= 2+sqrt(n/4)
262                        strictly,
263                        length of ip >=
264                            2+(1<<(int)(log(n/4+0.5)/log(2))/2).
265                        ip[0],ip[1] are pointers of the cos/sin table.
266        w[0...n*5/8-1] :cos/sin table (double *)
267                        w[],ip[] are initialized if ip[0] == 0.
268    [remark]
269        Inverse of
270            dfst(n, a, t, ip, w);
271        is
272            dfst(n, a, t, ip, w);
273            for (j = 1; j <= n - 1; j++) {
274                a[j] *= 2.0 / n;
275            }
276        .
277
278
279Appendix :
280    The cos/sin table is recalculated when the larger table required.
281    w[] and ip[] are compatible with all routines.
282*/
283
284
285#include "math-wrap.h"
286#include "fft4g.h"
287
288#ifdef FFT4G_FLOAT
289  #define double float
290  #define one_half 0.5f
291
292  #define sin(x)   sinf(x)
293  #define cos(x)   cosf(x)
294  #define atan(x)  atanf(x)
295
296  #define cdft  lsx_cdft_f
297  #define rdft  lsx_rdft_f
298  #define ddct  lsx_ddct_f
299  #define ddst  lsx_ddst_f
300  #define dfct  lsx_dfct_f
301  #define dfst  lsx_dfst_f
302#else
303  #define one_half 0.5
304  #define cdft  lsx_cdft
305  #define rdft  lsx_rdft
306  #define ddct  lsx_ddct
307  #define ddst  lsx_ddst
308  #define dfct  lsx_dfct
309  #define dfst  lsx_dfst
310#endif
311
312static void bitrv2conj(int n, int *ip, double *a);
313static void bitrv2(int n, int *ip, double *a);
314static void cft1st(int n, double *a, double const *w);
315static void cftbsub(int n, double *a, double const *w);
316static void cftfsub(int n, double *a, double const *w);
317static void cftmdl(int n, int l, double *a, double const *w);
318static void dctsub(int n, double *a, int nc, double const *c);
319static void dstsub(int n, double *a, int nc, double const *c);
320static void makect(int nc, int *ip, double *c);
321static void makewt(int nw, int *ip, double *w);
322static void rftbsub(int n, double *a, int nc, double const *c);
323static void rftfsub(int n, double *a, int nc, double const *c);
324
325
326void cdft(int n, int isgn, double *a, int *ip, double *w)
327{
328    if (n > (ip[0] << 2)) {
329        makewt(n >> 2, ip, w);
330    }
331    if (n > 4) {
332        if (isgn >= 0) {
333            bitrv2(n, ip + 2, a);
334            cftfsub(n, a, w);
335        } else {
336            bitrv2conj(n, ip + 2, a);
337            cftbsub(n, a, w);
338        }
339    } else if (n == 4) {
340        cftfsub(n, a, w);
341    }
342}
343
344
345void rdft(int n, int isgn, double *a, int *ip, double *w)
346{
347    int nw, nc;
348    double xi;
349
350    nw = ip[0];
351    if (n > (nw << 2)) {
352        nw = n >> 2;
353        makewt(nw, ip, w);
354    }
355    nc = ip[1];
356    if (n > (nc << 2)) {
357        nc = n >> 2;
358        makect(nc, ip, w + nw);
359    }
360    if (isgn >= 0) {
361        if (n > 4) {
362            bitrv2(n, ip + 2, a);
363            cftfsub(n, a, w);
364            rftfsub(n, a, nc, w + nw);
365        } else if (n == 4) {
366            cftfsub(n, a, w);
367        }
368        xi = a[0] - a[1];
369        a[0] += a[1];
370        a[1] = xi;
371    } else {
372        a[1] = one_half * (a[0] - a[1]);
373        a[0] -= a[1];
374        if (n > 4) {
375            rftbsub(n, a, nc, w + nw);
376            bitrv2(n, ip + 2, a);
377            cftbsub(n, a, w);
378        } else if (n == 4) {
379            cftfsub(n, a, w);
380        }
381    }
382}
383
384
385void ddct(int n, int isgn, double *a, int *ip, double *w)
386{
387    int j, nw, nc;
388    double xr;
389
390    nw = ip[0];
391    if (n > (nw << 2)) {
392        nw = n >> 2;
393        makewt(nw, ip, w);
394    }
395    nc = ip[1];
396    if (n > nc) {
397        nc = n;
398        makect(nc, ip, w + nw);
399    }
400    if (isgn < 0) {
401        xr = a[n - 1];
402        for (j = n - 2; j >= 2; j -= 2) {
403            a[j + 1] = a[j] - a[j - 1];
404            a[j] += a[j - 1];
405        }
406        a[1] = a[0] - xr;
407        a[0] += xr;
408        if (n > 4) {
409            rftbsub(n, a, nc, w + nw);
410            bitrv2(n, ip + 2, a);
411            cftbsub(n, a, w);
412        } else if (n == 4) {
413            cftfsub(n, a, w);
414        }
415    }
416    dctsub(n, a, nc, w + nw);
417    if (isgn >= 0) {
418        if (n > 4) {
419            bitrv2(n, ip + 2, a);
420            cftfsub(n, a, w);
421            rftfsub(n, a, nc, w + nw);
422        } else if (n == 4) {
423            cftfsub(n, a, w);
424        }
425        xr = a[0] - a[1];
426        a[0] += a[1];
427        for (j = 2; j < n; j += 2) {
428            a[j - 1] = a[j] - a[j + 1];
429            a[j] += a[j + 1];
430        }
431        a[n - 1] = xr;
432    }
433}
434
435
436void ddst(int n, int isgn, double *a, int *ip, double *w)
437{
438    int j, nw, nc;
439    double xr;
440
441    nw = ip[0];
442    if (n > (nw << 2)) {
443        nw = n >> 2;
444        makewt(nw, ip, w);
445    }
446    nc = ip[1];
447    if (n > nc) {
448        nc = n;
449        makect(nc, ip, w + nw);
450    }
451    if (isgn < 0) {
452        xr = a[n - 1];
453        for (j = n - 2; j >= 2; j -= 2) {
454            a[j + 1] = -a[j] - a[j - 1];
455            a[j] -= a[j - 1];
456        }
457        a[1] = a[0] + xr;
458        a[0] -= xr;
459        if (n > 4) {
460            rftbsub(n, a, nc, w + nw);
461            bitrv2(n, ip + 2, a);
462            cftbsub(n, a, w);
463        } else if (n == 4) {
464            cftfsub(n, a, w);
465        }
466    }
467    dstsub(n, a, nc, w + nw);
468    if (isgn >= 0) {
469        if (n > 4) {
470            bitrv2(n, ip + 2, a);
471            cftfsub(n, a, w);
472            rftfsub(n, a, nc, w + nw);
473        } else if (n == 4) {
474            cftfsub(n, a, w);
475        }
476        xr = a[0] - a[1];
477        a[0] += a[1];
478        for (j = 2; j < n; j += 2) {
479            a[j - 1] = -a[j] - a[j + 1];
480            a[j] -= a[j + 1];
481        }
482        a[n - 1] = -xr;
483    }
484}
485
486
487void dfct(int n, double *a, double *t, int *ip, double *w)
488{
489    int j, k, l, m, mh, nw, nc;
490    double xr, xi, yr, yi;
491
492    nw = ip[0];
493    if (n > (nw << 3)) {
494        nw = n >> 3;
495        makewt(nw, ip, w);
496    }
497    nc = ip[1];
498    if (n > (nc << 1)) {
499        nc = n >> 1;
500        makect(nc, ip, w + nw);
501    }
502    m = n >> 1;
503    yi = a[m];
504    xi = a[0] + a[n];
505    a[0] -= a[n];
506    t[0] = xi - yi;
507    t[m] = xi + yi;
508    if (n > 2) {
509        mh = m >> 1;
510        for (j = 1; j < mh; j++) {
511            k = m - j;
512            xr = a[j] - a[n - j];
513            xi = a[j] + a[n - j];
514            yr = a[k] - a[n - k];
515            yi = a[k] + a[n - k];
516            a[j] = xr;
517            a[k] = yr;
518            t[j] = xi - yi;
519            t[k] = xi + yi;
520        }
521        t[mh] = a[mh] + a[n - mh];
522        a[mh] -= a[n - mh];
523        dctsub(m, a, nc, w + nw);
524        if (m > 4) {
525            bitrv2(m, ip + 2, a);
526            cftfsub(m, a, w);
527            rftfsub(m, a, nc, w + nw);
528        } else if (m == 4) {
529            cftfsub(m, a, w);
530        }
531        a[n - 1] = a[0] - a[1];
532        a[1] = a[0] + a[1];
533        for (j = m - 2; j >= 2; j -= 2) {
534            a[2 * j + 1] = a[j] + a[j + 1];
535            a[2 * j - 1] = a[j] - a[j + 1];
536        }
537        l = 2;
538        m = mh;
539        while (m >= 2) {
540            dctsub(m, t, nc, w + nw);
541            if (m > 4) {
542                bitrv2(m, ip + 2, t);
543                cftfsub(m, t, w);
544                rftfsub(m, t, nc, w + nw);
545            } else if (m == 4) {
546                cftfsub(m, t, w);
547            }
548            a[n - l] = t[0] - t[1];
549            a[l] = t[0] + t[1];
550            k = 0;
551            for (j = 2; j < m; j += 2) {
552                k += l << 2;
553                a[k - l] = t[j] - t[j + 1];
554                a[k + l] = t[j] + t[j + 1];
555            }
556            l <<= 1;
557            mh = m >> 1;
558            for (j = 0; j < mh; j++) {
559                k = m - j;
560                t[j] = t[m + k] - t[m + j];
561                t[k] = t[m + k] + t[m + j];
562            }
563            t[mh] = t[m + mh];
564            m = mh;
565        }
566        a[l] = t[0];
567        a[n] = t[2] - t[1];
568        a[0] = t[2] + t[1];
569    } else {
570        a[1] = a[0];
571        a[2] = t[0];
572        a[0] = t[1];
573    }
574}
575
576
577void dfst(int n, double *a, double *t, int *ip, double *w)
578{
579    int j, k, l, m, mh, nw, nc;
580    double xr, xi, yr, yi;
581
582    nw = ip[0];
583    if (n > (nw << 3)) {
584        nw = n >> 3;
585        makewt(nw, ip, w);
586    }
587    nc = ip[1];
588    if (n > (nc << 1)) {
589        nc = n >> 1;
590        makect(nc, ip, w + nw);
591    }
592    if (n > 2) {
593        m = n >> 1;
594        mh = m >> 1;
595        for (j = 1; j < mh; j++) {
596            k = m - j;
597            xr = a[j] + a[n - j];
598            xi = a[j] - a[n - j];
599            yr = a[k] + a[n - k];
600            yi = a[k] - a[n - k];
601            a[j] = xr;
602            a[k] = yr;
603            t[j] = xi + yi;
604            t[k] = xi - yi;
605        }
606        t[0] = a[mh] - a[n - mh];
607        a[mh] += a[n - mh];
608        a[0] = a[m];
609        dstsub(m, a, nc, w + nw);
610        if (m > 4) {
611            bitrv2(m, ip + 2, a);
612            cftfsub(m, a, w);
613            rftfsub(m, a, nc, w + nw);
614        } else if (m == 4) {
615            cftfsub(m, a, w);
616        }
617        a[n - 1] = a[1] - a[0];
618        a[1] = a[0] + a[1];
619        for (j = m - 2; j >= 2; j -= 2) {
620            a[2 * j + 1] = a[j] - a[j + 1];
621            a[2 * j - 1] = -a[j] - a[j + 1];
622        }
623        l = 2;
624        m = mh;
625        while (m >= 2) {
626            dstsub(m, t, nc, w + nw);
627            if (m > 4) {
628                bitrv2(m, ip + 2, t);
629                cftfsub(m, t, w);
630                rftfsub(m, t, nc, w + nw);
631            } else if (m == 4) {
632                cftfsub(m, t, w);
633            }
634            a[n - l] = t[1] - t[0];
635            a[l] = t[0] + t[1];
636            k = 0;
637            for (j = 2; j < m; j += 2) {
638                k += l << 2;
639                a[k - l] = -t[j] - t[j + 1];
640                a[k + l] = t[j] - t[j + 1];
641            }
642            l <<= 1;
643            mh = m >> 1;
644            for (j = 1; j < mh; j++) {
645                k = m - j;
646                t[j] = t[m + k] + t[m + j];
647                t[k] = t[m + k] - t[m + j];
648            }
649            t[0] = t[m + mh];
650            m = mh;
651        }
652        a[l] = t[0];
653    }
654    a[0] = 0;
655}
656
657
658/* -------- initializing routines -------- */
659
660
661static void makewt(int nw, int *ip, double *w)
662{
663    int j, nwh;
664    double delta, x, y;
665
666    ip[0] = nw;
667    ip[1] = 1;
668    if (nw > 2) {
669        nwh = nw >> 1;
670        delta = atan(1.0) / (double)nwh;
671        w[0] = 1;
672        w[1] = 0;
673        w[nwh] = cos(delta * (double)nwh);
674        w[nwh + 1] = w[nwh];
675        if (nwh > 2) {
676            for (j = 2; j < nwh; j += 2) {
677                x = cos(delta * (double)j);
678                y = sin(delta * (double)j);
679                w[j] = x;
680                w[j + 1] = y;
681                w[nw - j] = y;
682                w[nw - j + 1] = x;
683            }
684            bitrv2(nw, ip + 2, w);
685        }
686    }
687}
688
689
690static void makect(int nc, int *ip, double *c)
691{
692    int j, nch;
693    double delta;
694
695    ip[1] = nc;
696    if (nc > 1) {
697        nch = nc >> 1;
698        delta = atan(1.0) / (double)nch;
699        c[0] = cos(delta * (double)nch);
700        c[nch] = one_half * c[0];
701        for (j = 1; j < nch; j++) {
702            c[j] = one_half * cos(delta * (double)j);
703            c[nc - j] = one_half * sin(delta * (double)j);
704        }
705    }
706}
707
708
709/* -------- child routines -------- */
710
711
712static void bitrv2(int n, int *ip0, double *a)
713{
714    int j, j1, k, k1, l, m, m2, ip[1024];
715    double xr, xi, yr, yi;
716
717    (void)ip0;
718    ip[0] = 0;
719    l = n;
720    m = 1;
721    while ((m << 3) < l) {
722        l >>= 1;
723        for (j = 0; j < m; j++) {
724            ip[m + j] = ip[j] + l;
725        }
726        m <<= 1;
727    }
728    m2 = 2 * m;
729    if ((m << 3) == l) {
730        for (k = 0; k < m; k++) {
731            for (j = 0; j < k; j++) {
732                j1 = 2 * j + ip[k];
733                k1 = 2 * k + ip[j];
734                xr = a[j1];
735                xi = a[j1 + 1];
736                yr = a[k1];
737                yi = a[k1 + 1];
738                a[j1] = yr;
739                a[j1 + 1] = yi;
740                a[k1] = xr;
741                a[k1 + 1] = xi;
742                j1 += m2;
743                k1 += 2 * m2;
744                xr = a[j1];
745                xi = a[j1 + 1];
746                yr = a[k1];
747                yi = a[k1 + 1];
748                a[j1] = yr;
749                a[j1 + 1] = yi;
750                a[k1] = xr;
751                a[k1 + 1] = xi;
752                j1 += m2;
753                k1 -= m2;
754                xr = a[j1];
755                xi = a[j1 + 1];
756                yr = a[k1];
757                yi = a[k1 + 1];
758                a[j1] = yr;
759                a[j1 + 1] = yi;
760                a[k1] = xr;
761                a[k1 + 1] = xi;
762                j1 += m2;
763                k1 += 2 * m2;
764                xr = a[j1];
765                xi = a[j1 + 1];
766                yr = a[k1];
767                yi = a[k1 + 1];
768                a[j1] = yr;
769                a[j1 + 1] = yi;
770                a[k1] = xr;
771                a[k1 + 1] = xi;
772            }
773            j1 = 2 * k + m2 + ip[k];
774            k1 = j1 + m2;
775            xr = a[j1];
776            xi = a[j1 + 1];
777            yr = a[k1];
778            yi = a[k1 + 1];
779            a[j1] = yr;
780            a[j1 + 1] = yi;
781            a[k1] = xr;
782            a[k1 + 1] = xi;
783        }
784    } else {
785        for (k = 1; k < m; k++) {
786            for (j = 0; j < k; j++) {
787                j1 = 2 * j + ip[k];
788                k1 = 2 * k + ip[j];
789                xr = a[j1];
790                xi = a[j1 + 1];
791                yr = a[k1];
792                yi = a[k1 + 1];
793                a[j1] = yr;
794                a[j1 + 1] = yi;
795                a[k1] = xr;
796                a[k1 + 1] = xi;
797                j1 += m2;
798                k1 += m2;
799                xr = a[j1];
800                xi = a[j1 + 1];
801                yr = a[k1];
802                yi = a[k1 + 1];
803                a[j1] = yr;
804                a[j1 + 1] = yi;
805                a[k1] = xr;
806                a[k1 + 1] = xi;
807            }
808        }
809    }
810}
811
812
813static void bitrv2conj(int n, int *ip0, double *a)
814{
815    int j, j1, k, k1, l, m, m2, ip[512];
816    double xr, xi, yr, yi;
817
818    (void)ip0;
819    ip[0] = 0;
820    l = n;
821    m = 1;
822    while ((m << 3) < l) {
823        l >>= 1;
824        for (j = 0; j < m; j++) {
825            ip[m + j] = ip[j] + l;
826        }
827        m <<= 1;
828    }
829    m2 = 2 * m;
830    if ((m << 3) == l) {
831        for (k = 0; k < m; k++) {
832            for (j = 0; j < k; j++) {
833                j1 = 2 * j + ip[k];
834                k1 = 2 * k + ip[j];
835                xr = a[j1];
836                xi = -a[j1 + 1];
837                yr = a[k1];
838                yi = -a[k1 + 1];
839                a[j1] = yr;
840                a[j1 + 1] = yi;
841                a[k1] = xr;
842                a[k1 + 1] = xi;
843                j1 += m2;
844                k1 += 2 * m2;
845                xr = a[j1];
846                xi = -a[j1 + 1];
847                yr = a[k1];
848                yi = -a[k1 + 1];
849                a[j1] = yr;
850                a[j1 + 1] = yi;
851                a[k1] = xr;
852                a[k1 + 1] = xi;
853                j1 += m2;
854                k1 -= m2;
855                xr = a[j1];
856                xi = -a[j1 + 1];
857                yr = a[k1];
858                yi = -a[k1 + 1];
859                a[j1] = yr;
860                a[j1 + 1] = yi;
861                a[k1] = xr;
862                a[k1 + 1] = xi;
863                j1 += m2;
864                k1 += 2 * m2;
865                xr = a[j1];
866                xi = -a[j1 + 1];
867                yr = a[k1];
868                yi = -a[k1 + 1];
869                a[j1] = yr;
870                a[j1 + 1] = yi;
871                a[k1] = xr;
872                a[k1 + 1] = xi;
873            }
874            k1 = 2 * k + ip[k];
875            a[k1 + 1] = -a[k1 + 1];
876            j1 = k1 + m2;
877            k1 = j1 + m2;
878            xr = a[j1];
879            xi = -a[j1 + 1];
880            yr = a[k1];
881            yi = -a[k1 + 1];
882            a[j1] = yr;
883            a[j1 + 1] = yi;
884            a[k1] = xr;
885            a[k1 + 1] = xi;
886            k1 += m2;
887            a[k1 + 1] = -a[k1 + 1];
888        }
889    } else {
890        a[1] = -a[1];
891        a[m2 + 1] = -a[m2 + 1];
892        for (k = 1; k < m; k++) {
893            for (j = 0; j < k; j++) {
894                j1 = 2 * j + ip[k];
895                k1 = 2 * k + ip[j];
896                xr = a[j1];
897                xi = -a[j1 + 1];
898                yr = a[k1];
899                yi = -a[k1 + 1];
900                a[j1] = yr;
901                a[j1 + 1] = yi;
902                a[k1] = xr;
903                a[k1 + 1] = xi;
904                j1 += m2;
905                k1 += m2;
906                xr = a[j1];
907                xi = -a[j1 + 1];
908                yr = a[k1];
909                yi = -a[k1 + 1];
910                a[j1] = yr;
911                a[j1 + 1] = yi;
912                a[k1] = xr;
913                a[k1 + 1] = xi;
914            }
915            k1 = 2 * k + ip[k];
916            a[k1 + 1] = -a[k1 + 1];
917            a[k1 + m2 + 1] = -a[k1 + m2 + 1];
918        }
919    }
920}
921
922
923static void cftfsub(int n, double *a, double const *w)
924{
925    int j, j1, j2, j3, l;
926    double x0r, x0i, x1r, x1i, x2r, x2i, x3r, x3i;
927
928    l = 2;
929    if (n > 8) {
930        cft1st(n, a, w);
931        l = 8;
932        while ((l << 2) < n) {
933            cftmdl(n, l, a, w);
934            l <<= 2;
935        }
936    }
937    if ((l << 2) == n) {
938        for (j = 0; j < l; j += 2) {
939            j1 = j + l;
940            j2 = j1 + l;
941            j3 = j2 + l;
942            x0r = a[j] + a[j1];
943            x0i = a[j + 1] + a[j1 + 1];
944            x1r = a[j] - a[j1];
945            x1i = a[j + 1] - a[j1 + 1];
946            x2r = a[j2] + a[j3];
947            x2i = a[j2 + 1] + a[j3 + 1];
948            x3r = a[j2] - a[j3];
949            x3i = a[j2 + 1] - a[j3 + 1];
950            a[j] = x0r + x2r;
951            a[j + 1] = x0i + x2i;
952            a[j2] = x0r - x2r;
953            a[j2 + 1] = x0i - x2i;
954            a[j1] = x1r - x3i;
955            a[j1 + 1] = x1i + x3r;
956            a[j3] = x1r + x3i;
957            a[j3 + 1] = x1i - x3r;
958        }
959    } else {
960        for (j = 0; j < l; j += 2) {
961            j1 = j + l;
962            x0r = a[j] - a[j1];
963            x0i = a[j + 1] - a[j1 + 1];
964            a[j] += a[j1];
965            a[j + 1] += a[j1 + 1];
966            a[j1] = x0r;
967            a[j1 + 1] = x0i;
968        }
969    }
970}
971
972
973static void cftbsub(int n, double *a, double const *w)
974{
975    int j, j1, j2, j3, l;
976    double x0r, x0i, x1r, x1i, x2r, x2i, x3r, x3i;
977
978    l = 2;
979    if (n > 8) {
980        cft1st(n, a, w);
981        l = 8;
982        while ((l << 2) < n) {
983            cftmdl(n, l, a, w);
984            l <<= 2;
985        }
986    }
987    if ((l << 2) == n) {
988        for (j = 0; j < l; j += 2) {
989            j1 = j + l;
990            j2 = j1 + l;
991            j3 = j2 + l;
992            x0r = a[j] + a[j1];
993            x0i = -a[j + 1] - a[j1 + 1];
994            x1r = a[j] - a[j1];
995            x1i = -a[j + 1] + a[j1 + 1];
996            x2r = a[j2] + a[j3];
997            x2i = a[j2 + 1] + a[j3 + 1];
998            x3r = a[j2] - a[j3];
999            x3i = a[j2 + 1] - a[j3 + 1];
1000            a[j] = x0r + x2r;
1001            a[j + 1] = x0i - x2i;
1002            a[j2] = x0r - x2r;
1003            a[j2 + 1] = x0i + x2i;
1004            a[j1] = x1r - x3i;
1005            a[j1 + 1] = x1i - x3r;
1006            a[j3] = x1r + x3i;
1007            a[j3 + 1] = x1i + x3r;
1008        }
1009    } else {
1010        for (j = 0; j < l; j += 2) {
1011            j1 = j + l;
1012            x0r = a[j] - a[j1];
1013            x0i = -a[j + 1] + a[j1 + 1];
1014            a[j] += a[j1];
1015            a[j + 1] = -a[j + 1] - a[j1 + 1];
1016            a[j1] = x0r;
1017            a[j1 + 1] = x0i;
1018        }
1019    }
1020}
1021
1022
1023static void cft1st(int n, double *a, double const *w)
1024{
1025    int j, k1, k2;
1026    double wk1r, wk1i, wk2r, wk2i, wk3r, wk3i;
1027    double x0r, x0i, x1r, x1i, x2r, x2i, x3r, x3i;
1028
1029    x0r = a[0] + a[2];
1030    x0i = a[1] + a[3];
1031    x1r = a[0] - a[2];
1032    x1i = a[1] - a[3];
1033    x2r = a[4] + a[6];
1034    x2i = a[5] + a[7];
1035    x3r = a[4] - a[6];
1036    x3i = a[5] - a[7];
1037    a[0] = x0r + x2r;
1038    a[1] = x0i + x2i;
1039    a[4] = x0r - x2r;
1040    a[5] = x0i - x2i;
1041    a[2] = x1r - x3i;
1042    a[3] = x1i + x3r;
1043    a[6] = x1r + x3i;
1044    a[7] = x1i - x3r;
1045    wk1r = w[2];
1046    x0r = a[8] + a[10];
1047    x0i = a[9] + a[11];
1048    x1r = a[8] - a[10];
1049    x1i = a[9] - a[11];
1050    x2r = a[12] + a[14];
1051    x2i = a[13] + a[15];
1052    x3r = a[12] - a[14];
1053    x3i = a[13] - a[15];
1054    a[8] = x0r + x2r;
1055    a[9] = x0i + x2i;
1056    a[12] = x2i - x0i;
1057    a[13] = x0r - x2r;
1058    x0r = x1r - x3i;
1059    x0i = x1i + x3r;
1060    a[10] = wk1r * (x0r - x0i);
1061    a[11] = wk1r * (x0r + x0i);
1062    x0r = x3i + x1r;
1063    x0i = x3r - x1i;
1064    a[14] = wk1r * (x0i - x0r);
1065    a[15] = wk1r * (x0i + x0r);
1066    k1 = 0;
1067    for (j = 16; j < n; j += 16) {
1068        k1 += 2;
1069        k2 = 2 * k1;
1070        wk2r = w[k1];
1071        wk2i = w[k1 + 1];
1072        wk1r = w[k2];
1073        wk1i = w[k2 + 1];
1074        wk3r = wk1r - 2 * wk2i * wk1i;
1075        wk3i = 2 * wk2i * wk1r - wk1i;
1076        x0r = a[j] + a[j + 2];
1077        x0i = a[j + 1] + a[j + 3];
1078        x1r = a[j] - a[j + 2];
1079        x1i = a[j + 1] - a[j + 3];
1080        x2r = a[j + 4] + a[j + 6];
1081        x2i = a[j + 5] + a[j + 7];
1082        x3r = a[j + 4] - a[j + 6];
1083        x3i = a[j + 5] - a[j + 7];
1084        a[j] = x0r + x2r;
1085        a[j + 1] = x0i + x2i;
1086        x0r -= x2r;
1087        x0i -= x2i;
1088        a[j + 4] = wk2r * x0r - wk2i * x0i;
1089        a[j + 5] = wk2r * x0i + wk2i * x0r;
1090        x0r = x1r - x3i;
1091        x0i = x1i + x3r;
1092        a[j + 2] = wk1r * x0r - wk1i * x0i;
1093        a[j + 3] = wk1r * x0i + wk1i * x0r;
1094        x0r = x1r + x3i;
1095        x0i = x1i - x3r;
1096        a[j + 6] = wk3r * x0r - wk3i * x0i;
1097        a[j + 7] = wk3r * x0i + wk3i * x0r;
1098        wk1r = w[k2 + 2];
1099        wk1i = w[k2 + 3];
1100        wk3r = wk1r - 2 * wk2r * wk1i;
1101        wk3i = 2 * wk2r * wk1r - wk1i;
1102        x0r = a[j + 8] + a[j + 10];
1103        x0i = a[j + 9] + a[j + 11];
1104        x1r = a[j + 8] - a[j + 10];
1105        x1i = a[j + 9] - a[j + 11];
1106        x2r = a[j + 12] + a[j + 14];
1107        x2i = a[j + 13] + a[j + 15];
1108        x3r = a[j + 12] - a[j + 14];
1109        x3i = a[j + 13] - a[j + 15];
1110        a[j + 8] = x0r + x2r;
1111        a[j + 9] = x0i + x2i;
1112        x0r -= x2r;
1113        x0i -= x2i;
1114        a[j + 12] = -wk2i * x0r - wk2r * x0i;
1115        a[j + 13] = -wk2i * x0i + wk2r * x0r;
1116        x0r = x1r - x3i;
1117        x0i = x1i + x3r;
1118        a[j + 10] = wk1r * x0r - wk1i * x0i;
1119        a[j + 11] = wk1r * x0i + wk1i * x0r;
1120        x0r = x1r + x3i;
1121        x0i = x1i - x3r;
1122        a[j + 14] = wk3r * x0r - wk3i * x0i;
1123        a[j + 15] = wk3r * x0i + wk3i * x0r;
1124    }
1125}
1126
1127
1128static void cftmdl(int n, int l, double *a, double const *w)
1129{
1130    int j, j1, j2, j3, k, k1, k2, m, m2;
1131    double wk1r, wk1i, wk2r, wk2i, wk3r, wk3i;
1132    double x0r, x0i, x1r, x1i, x2r, x2i, x3r, x3i;
1133
1134    m = l << 2;
1135    for (j = 0; j < l; j += 2) {
1136        j1 = j + l;
1137        j2 = j1 + l;
1138        j3 = j2 + l;
1139        x0r = a[j] + a[j1];
1140        x0i = a[j + 1] + a[j1 + 1];
1141        x1r = a[j] - a[j1];
1142        x1i = a[j + 1] - a[j1 + 1];
1143        x2r = a[j2] + a[j3];
1144        x2i = a[j2 + 1] + a[j3 + 1];
1145        x3r = a[j2] - a[j3];
1146        x3i = a[j2 + 1] - a[j3 + 1];
1147        a[j] = x0r + x2r;
1148        a[j + 1] = x0i + x2i;
1149        a[j2] = x0r - x2r;
1150        a[j2 + 1] = x0i - x2i;
1151        a[j1] = x1r - x3i;
1152        a[j1 + 1] = x1i + x3r;
1153        a[j3] = x1r + x3i;
1154        a[j3 + 1] = x1i - x3r;
1155    }
1156    wk1r = w[2];
1157    for (j = m; j < l + m; j += 2) {
1158        j1 = j + l;
1159        j2 = j1 + l;
1160        j3 = j2 + l;
1161        x0r = a[j] + a[j1];
1162        x0i = a[j + 1] + a[j1 + 1];
1163        x1r = a[j] - a[j1];
1164        x1i = a[j + 1] - a[j1 + 1];
1165        x2r = a[j2] + a[j3];
1166        x2i = a[j2 + 1] + a[j3 + 1];
1167        x3r = a[j2] - a[j3];
1168        x3i = a[j2 + 1] - a[j3 + 1];
1169        a[j] = x0r + x2r;
1170        a[j + 1] = x0i + x2i;
1171        a[j2] = x2i - x0i;
1172        a[j2 + 1] = x0r - x2r;
1173        x0r = x1r - x3i;
1174        x0i = x1i + x3r;
1175        a[j1] = wk1r * (x0r - x0i);
1176        a[j1 + 1] = wk1r * (x0r + x0i);
1177        x0r = x3i + x1r;
1178        x0i = x3r - x1i;
1179        a[j3] = wk1r * (x0i - x0r);
1180        a[j3 + 1] = wk1r * (x0i + x0r);
1181    }
1182    k1 = 0;
1183    m2 = 2 * m;
1184    for (k = m2; k < n; k += m2) {
1185        k1 += 2;
1186        k2 = 2 * k1;
1187        wk2r = w[k1];
1188        wk2i = w[k1 + 1];
1189        wk1r = w[k2];
1190        wk1i = w[k2 + 1];
1191        wk3r = wk1r - 2 * wk2i * wk1i;
1192        wk3i = 2 * wk2i * wk1r - wk1i;
1193        for (j = k; j < l + k; j += 2) {
1194            j1 = j + l;
1195            j2 = j1 + l;
1196            j3 = j2 + l;
1197            x0r = a[j] + a[j1];
1198            x0i = a[j + 1] + a[j1 + 1];
1199            x1r = a[j] - a[j1];
1200            x1i = a[j + 1] - a[j1 + 1];
1201            x2r = a[j2] + a[j3];
1202            x2i = a[j2 + 1] + a[j3 + 1];
1203            x3r = a[j2] - a[j3];
1204            x3i = a[j2 + 1] - a[j3 + 1];
1205            a[j] = x0r + x2r;
1206            a[j + 1] = x0i + x2i;
1207            x0r -= x2r;
1208            x0i -= x2i;
1209            a[j2] = wk2r * x0r - wk2i * x0i;
1210            a[j2 + 1] = wk2r * x0i + wk2i * x0r;
1211            x0r = x1r - x3i;
1212            x0i = x1i + x3r;
1213            a[j1] = wk1r * x0r - wk1i * x0i;
1214            a[j1 + 1] = wk1r * x0i + wk1i * x0r;
1215            x0r = x1r + x3i;
1216            x0i = x1i - x3r;
1217            a[j3] = wk3r * x0r - wk3i * x0i;
1218            a[j3 + 1] = wk3r * x0i + wk3i * x0r;
1219        }
1220        wk1r = w[k2 + 2];
1221        wk1i = w[k2 + 3];
1222        wk3r = wk1r - 2 * wk2r * wk1i;
1223        wk3i = 2 * wk2r * wk1r - wk1i;
1224        for (j = k + m; j < l + (k + m); j += 2) {
1225            j1 = j + l;
1226            j2 = j1 + l;
1227            j3 = j2 + l;
1228            x0r = a[j] + a[j1];
1229            x0i = a[j + 1] + a[j1 + 1];
1230            x1r = a[j] - a[j1];
1231            x1i = a[j + 1] - a[j1 + 1];
1232            x2r = a[j2] + a[j3];
1233            x2i = a[j2 + 1] + a[j3 + 1];
1234            x3r = a[j2] - a[j3];
1235            x3i = a[j2 + 1] - a[j3 + 1];
1236            a[j] = x0r + x2r;
1237            a[j + 1] = x0i + x2i;
1238            x0r -= x2r;
1239            x0i -= x2i;
1240            a[j2] = -wk2i * x0r - wk2r * x0i;
1241            a[j2 + 1] = -wk2i * x0i + wk2r * x0r;
1242            x0r = x1r - x3i;
1243            x0i = x1i + x3r;
1244            a[j1] = wk1r * x0r - wk1i * x0i;
1245            a[j1 + 1] = wk1r * x0i + wk1i * x0r;
1246            x0r = x1r + x3i;
1247            x0i = x1i - x3r;
1248            a[j3] = wk3r * x0r - wk3i * x0i;
1249            a[j3 + 1] = wk3r * x0i + wk3i * x0r;
1250        }
1251    }
1252}
1253
1254
1255static void rftfsub(int n, double *a, int nc, double const *c)
1256{
1257    int j, k, kk, ks, m;
1258    double wkr, wki, xr, xi, yr, yi;
1259
1260    m = n >> 1;
1261    ks = 2 * nc / m;
1262    kk = 0;
1263    for (j = 2; j < m; j += 2) {
1264        k = n - j;
1265        kk += ks;
1266        wkr = one_half - c[nc - kk];
1267        wki = c[kk];
1268        xr = a[j] - a[k];
1269        xi = a[j + 1] + a[k + 1];
1270        yr = wkr * xr - wki * xi;
1271        yi = wkr * xi + wki * xr;
1272        a[j] -= yr;
1273        a[j + 1] -= yi;
1274        a[k] += yr;
1275        a[k + 1] -= yi;
1276    }
1277}
1278
1279
1280static void rftbsub(int n, double *a, int nc, double const *c)
1281{
1282    int j, k, kk, ks, m;
1283    double wkr, wki, xr, xi, yr, yi;
1284
1285    a[1] = -a[1];
1286    m = n >> 1;
1287    ks = 2 * nc / m;
1288    kk = 0;
1289    for (j = 2; j < m; j += 2) {
1290        k = n - j;
1291        kk += ks;
1292        wkr = one_half - c[nc - kk];
1293        wki = c[kk];
1294        xr = a[j] - a[k];
1295        xi = a[j + 1] + a[k + 1];
1296        yr = wkr * xr + wki * xi;
1297        yi = wkr * xi - wki * xr;
1298        a[j] -= yr;
1299        a[j + 1] = yi - a[j + 1];
1300        a[k] += yr;
1301        a[k + 1] = yi - a[k + 1];
1302    }
1303    a[m + 1] = -a[m + 1];
1304}
1305
1306
1307static void dctsub(int n, double *a, int nc, double const *c)
1308{
1309    int j, k, kk, ks, m;
1310    double wkr, wki, xr;
1311
1312    m = n >> 1;
1313    ks = nc / n;
1314    kk = 0;
1315    for (j = 1; j < m; j++) {
1316        k = n - j;
1317        kk += ks;
1318        wkr = c[kk] - c[nc - kk];
1319        wki = c[kk] + c[nc - kk];
1320        xr = wki * a[j] - wkr * a[k];
1321        a[j] = wkr * a[j] + wki * a[k];
1322        a[k] = xr;
1323    }
1324    a[m] *= c[0];
1325}
1326
1327
1328static void dstsub(int n, double *a, int nc, double const *c)
1329{
1330    int j, k, kk, ks, m;
1331    double wkr, wki, xr;
1332
1333    m = n >> 1;
1334    ks = nc / n;
1335    kk = 0;
1336    for (j = 1; j < m; j++) {
1337        k = n - j;
1338        kk += ks;
1339        wkr = c[kk] - c[nc - kk];
1340        wki = c[kk] + c[nc - kk];
1341        xr = wki * a[k] - wkr * a[j];
1342        a[k] = wkr * a[k] + wki * a[j];
1343        a[j] = xr;
1344    }
1345    a[m] *= c[0];
1346}