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