The NIST Statistical Test Suite： 序列随机性测试工具

/* Notes from RFB: Looks like the user-level routines are: Real FFT void __ogg_fdrffti(int n, double *wsave, int *ifac) void __ogg_fdrfftf(int n, double *r, double *wsave, int *ifac) void __ogg_fdrfftb(int n, double *r, double *wsave, int *ifac) __ogg_fdrffti == initialization __ogg_fdrfftf == forward transform __ogg_fdrfftb == backward transform Parameters are n == length of sequence r == sequence to be transformed (input) == transformed sequence (output) wsave == work array of length 2n (allocated by caller) ifac == work array of length 15 (allocated by caller) Cosine quarter-wave FFT void __ogg_fdcosqi(int n, double *wsave, int *ifac) void __ogg_fdcosqf(int n, double *x, double *wsave, int *ifac) void __ogg_fdcosqb(int n, double *x, double *wsave, int *ifac) */ /******************************************************************** * * * THIS FILE IS PART OF THE OggSQUISH SOFTWARE CODEC SOURCE CODE. * * * ******************************************************************** file: fft.c function: Fast discrete Fourier and cosine transforms and inverses author: Monty <xiphmont@mit.edu> modifications by: Monty last modification date: Jul 1 1996 ********************************************************************/ /* These Fourier routines were originally based on the Fourier routines of the same names from the NETLIB bihar and fftpack fortran libraries developed by Paul N. Swarztrauber at the National Center for Atmospheric Research in Boulder, CO USA. They have been reimplemented in C and optimized in a few ways for OggSquish. */ /* As the original fortran libraries are public domain, the C Fourier routines in this file are hereby released to the public domain as well. The C routines here produce output exactly equivalent to the original fortran routines. Of particular interest are the facts that (like the original fortran), these routines can work on arbitrary length vectors that need not be powers of two in length. */ #include <math.h> #define STIN static static void drfti1(int n, double *wa, int *ifac) { static int ntryh[4] = { 4,2,3,5 }; static double tpi = 6.28318530717958647692528676655900577; double arg, argh, argld, fi; int ntry=0,i,j=-1; int k1, l1, l2, ib; int ld, ii, ip, is, nq, nr; int ido, ipm, nfm1; int nl=n; int nf=0; L101: j++; if ( j < 4 ) ntry = ntryh[j]; else ntry += 2; L104: nq = nl/ntry; nr = nl-ntry*nq; if ( nr != 0 ) goto L101; nf++; ifac[nf+1] = ntry; nl = nq; if ( ntry != 2 ) goto L107; if ( nf == 1 ) goto L107; for ( i=1; i<nf; i++ ) { ib = nf-i+1; ifac[ib+1] = ifac[ib]; } ifac[2] = 2; L107: if( nl != 1 ) goto L104; ifac[0] = n; ifac[1] = nf; argh = tpi/n; is = 0; nfm1 = nf-1; l1 = 1; if ( nfm1 == 0 ) return; for ( k1=0; k1<nfm1; k1++ ) { ip = ifac[k1+2]; ld = 0; l2 = l1*ip; ido = n/l2; ipm = ip-1; for ( j=0; j<ipm; j++ ) { ld += l1; i = is; argld = (double)ld*argh; fi = 0.0; for ( ii=2; ii<ido; ii+=2 ) { fi += 1.0; arg = fi*argld; wa[i++] = cos(arg); wa[i++] = sin(arg); } is += ido; } l1 = l2; } } void __ogg_fdrffti(int n, double *wsave, int *ifac) { if ( n == 1 ) return; drfti1(n, wsave+n, ifac); } #ifdef LBBBBBBBBBBBBB void __ogg_fdcosqi(int n, double *wsave, int *ifac) { static double pih = 1.57079632679489661923132169163975; static int k; static double fk, dt; dt = pih/n; fk = 0.0; for ( k=0; k<n; k++ ) { fk += 1.0; wsave[k] = cos(fk*dt); } __ogg_fdrffti(n, wsave+n,ifac); } #endif STIN void dradf2(int ido, int l1, double *cc, double *ch, double *wa1) { int i , k; double ti2 , tr2; int t0 , t1, t2, t3, t4, t5, t6; t1 = 0; t0 = (t2 = l1*ido); t3 = ido<<1; for ( k=0; k<l1; k++ ) { ch[t1<<1] = cc[t1]+cc[t2]; ch[(t1<<1)+t3-1] = cc[t1]-cc[t2]; t1 += ido; t2 += ido; } if ( ido < 2 ) return; if ( ido == 2 ) goto L105; t1 = 0; t2 = t0; for ( k=0; k<l1; k++ ) { t3 = t2; t4 = (t1<<1)+(ido<<1); t5 = t1; t6 = t1+t1; for ( i=2; i<ido; i+=2 ) { t3 += 2; t4 -= 2; t5 += 2; t6 += 2; tr2 = wa1[i-2]*cc[t3-1]+wa1[i-1]*cc[t3]; ti2 = wa1[i-2]*cc[t3]-wa1[i-1]*cc[t3-1]; ch[t6] = cc[t5]+ti2; ch[t4] = ti2-cc[t5]; ch[t6-1] = cc[t5-1]+tr2; ch[t4-1] = cc[t5-1]-tr2; } t1 += ido; t2 += ido; } if ( ido%2 == 1 ) return; L105: t3 = (t2 = (t1 = ido)-1); t2 += t0; for ( k=0; k<l1; k++ ) { ch[t1] = -cc[t2]; ch[t1-1] = cc[t3]; t1 += ido<<1; t2 += ido; t3 += ido; } } STIN void dradf4(int ido, int l1, double *cc, double *ch, double *wa1, double *wa2, double *wa3) { static double hsqt2 = .70710678118654752440084436210485; int i, k, t0, t1, t2, t3, t4, t5, t6; double ci2, ci3, ci4, cr2, cr3, cr4; double ti1, ti2, ti3, ti4, tr1, tr2, tr3, tr4; t0 = l1*ido; t1 = t0; t4 = t1<<1; t2 = t1+(t1<<1); t3 = 0; for ( k=0; k<l1; k++ ) { tr1 = cc[t1]+cc[t2]; tr2 = cc[t3]+cc[t4]; ch[t5 = t3<<2] = tr1+tr2; ch[(ido<<2)+t5-1] = tr2-tr1; ch[(t5 += (ido<<1))-1] = cc[t3]-cc[t4]; ch[t5] = cc[t2]-cc[t1]; t1 += ido; t2 += ido; t3 += ido; t4 += ido; } if ( ido < 2 ) return; if ( ido == 2 ) goto L105; t1 = 0; for ( k=0; k<l1; k++ ) { t2 = t1; t4 = t1<<2; t5 = (t6 = ido<<1)+t4; for ( i=2; i<ido; i+=2 ) { t3 = (t2 += 2); t4 += 2; t5 -= 2; t3 += t0; cr2 = wa1[i-2]*cc[t3-1]+wa1[i-1]*cc[t3]; ci2 = wa1[i-2]*cc[t3]-wa1[i-1]*cc[t3-1]; t3 += t0; cr3 = wa2[i-2]*cc[t3-1]+wa2[i-1]*cc[t3]; ci3 = wa2[i-2]*cc[t3]-wa2[i-1]*cc[t3-1]; t3 += t0; cr4 = wa3[i-2]*cc[t3-1]+wa3[i-1]*cc[t3]; ci4 = wa3[i-2]*cc[t3]-wa3[i-1]*cc[t3-1]; tr1 = cr2+cr4; tr4 = cr4-cr2; ti1 = ci2+ci4; ti4 = ci2-ci4; ti2 = cc[t2]+ci3; ti3 = cc[t2]-ci3; tr2 = cc[t2-1]+cr3; tr3 = cc[t2-1]-cr3; ch[t4-1] = tr1+tr2; ch[t4] = ti1+ti2; ch[t5-1] = tr3-ti4; ch[t5] = tr4-ti3; ch[t4+t6-1] = ti4+tr3; ch[t4+t6] = tr4+ti3; ch[t5+t6-1] = tr2-tr1; ch[t5+t6] = ti1-ti2; } t1 += ido; } if ( ido%2 == 1 ) return; L105: t2 = (t1 = t0+ido-1)+(t0<<1); t3 = ido<<2; t4 = ido; t5 = ido<<1; t6 = ido; for ( k=0; k<l1; k++ ) { ti1 = -hsqt2*(cc[t1]+cc[t2]); tr1 = hsqt2*(cc[t1]-cc[t2]); ch[t4-1] = tr1+cc[t6-1]; ch[t4+t5-1] = cc[t6-1]-tr1; ch[t4] = ti1-cc[t1+t0]; ch[t4+t5] = ti1+cc[t1+t0]; t1 += ido; t2 += ido; t4 += t3; t6 += ido; } } STIN void dradfg(int ido, int ip, int l1, int idl1, double *cc, double *c1, double *c2, double *ch, double *ch2, double *wa) { static double tpi = 6.28318530717958647692528676655900577; int idij, ipph, i, j, k, l, ic, ik, is; int t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10; double dc2, ai1, ai2, ar1, ar2, ds2; int nbd; double dcp, arg, dsp, ar1h, ar2h; int idp2, ipp2; arg = tpi/(double)ip; dcp = cos(arg); dsp = sin(arg); ipph = (ip+1)>>1; ipp2 = ip; idp2 = ido; nbd = (ido-1)>>1; t0 = l1*ido; t10 = ip*ido; if ( ido == 1 ) goto L119; for ( ik=0; ik<idl1; ik++ ) ch2[ik] = c2[ik]; t1 = 0; for ( j=1; j<ip; j++ ) { t1 += t0; t2 = t1; for ( k=0; k<l1; k++ ) { ch[t2] = c1[t2]; t2 += ido; } } is = -ido; t1 = 0; if ( nbd > l1 ) { for ( j=1; j<ip; j++ ) { t1 += t0; is += ido; t2 = -ido+t1; for ( k=0; k<l1; k++ ) { idij = is-1; t2 += ido; t3 = t2; for ( i=2; i<ido; i+=2 ) { idij += 2; t3 += 2; ch[t3-1] = wa[idij-1]*c1[t3-1]+wa[idij]*c1[t3]; ch[t3] = wa[idij-1]*c1[t3]-wa[idij]*c1[t3-1]; } } } } else { for ( j=1; j<ip; j++ ) { is += ido; idij = is-1; t1 += t0; t2 = t1; for ( i=2; i<ido; i+=2 ) { idij += 2; t2 += 2; t3 = t2; for ( k=0; k<l1; k++ ) { ch[t3-1] = wa[idij-1]*c1[t3-1]+wa[idij]*c1[t3]; ch[t3] = wa[idij-1]*c1[t3]-wa[idij]*c1[t3-1]; t3