Mercurial > hg > js-dsp-test
changeset 33:bbf5d4e825eb
Hack in an alternative float-only version (no faster)
| author | Chris Cannam |
|---|---|
| date | Mon, 09 Nov 2015 12:22:00 +0000 |
| parents | ebc87a62321d |
| children | c795fab4c4be |
| files | fft/nayukic/FFT.js fft/nayukic/Makefile.emscripten fft/nayukic/NayukiCFFT.js fft/nayukic/fft.c fft/nayukic/fft.h fft/test.js |
| diffstat | 6 files changed, 140 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/fft/nayukic/FFT.js Mon Nov 09 11:46:47 2015 +0000 +++ b/fft/nayukic/FFT.js Mon Nov 09 12:22:00 2015 +0000 @@ -14,6 +14,18 @@ 'transform_radix2_precalc', 'void', ['number', 'number', 'number', 'number'] ); +var nc_precalc_f = nayukiCModule.cwrap( + 'precalc_f', 'number', ['number'] +); + +var nc_dispose_f = nayukiCModule.cwrap( + 'dispose_f', 'void', ['number'] +); + +var nc_transform_radix2_precalc_f = nayukiCModule.cwrap( + 'transform_radix2_precalc_f', 'void', ['number', 'number', 'number', 'number'] +); + function FFTNayukiC(n) { this.n = n; @@ -37,3 +49,26 @@ } } +function FFTNayukiCFloat(n) { + + this.n = n; + this.rptr = nayukiCModule._malloc(n*4 + n*4); + this.iptr = this.rptr + n*4; + this.rarr = new Float32Array(nayukiCModule.HEAPU8.buffer, this.rptr, n); + this.iarr = new Float32Array(nayukiCModule.HEAPU8.buffer, this.iptr, n); + this.tables = nc_precalc_f(n); + + this.forward = function(real, imag) { + this.rarr.set(real); + this.iarr.set(imag); + nc_transform_radix2_precalc_f(this.rptr, this.iptr, this.n, this.tables); + real.set(this.rarr); + imag.set(this.iarr); + }; + + this.dispose = function() { + nayukiCModule._free(this.rptr); + nc_dispose_f(this.tables); + } +} +
--- a/fft/nayukic/Makefile.emscripten Mon Nov 09 11:46:47 2015 +0000 +++ b/fft/nayukic/Makefile.emscripten Mon Nov 09 12:22:00 2015 +0000 @@ -6,7 +6,7 @@ -s NO_BROWSER=1 \ -s MODULARIZE=1 \ -s EXPORT_NAME="'NayukiCModule'" \ - -s EXPORTED_FUNCTIONS="['_transform_radix2_precalc','_precalc','_dispose']" \ + -s EXPORTED_FUNCTIONS="['_transform_radix2_precalc','_precalc','_dispose','_transform_radix2_precalc_f','_precalc_f','_dispose_f']" \ -o NayukiCFFT.js \ fft.c
--- a/fft/nayukic/NayukiCFFT.js Mon Nov 09 11:46:47 2015 +0000 +++ b/fft/nayukic/NayukiCFFT.js Mon Nov 09 12:22:00 2015 +0000 @@ -5,14 +5,14 @@ var asm=(function(global,env,buffer) { "use asm";var a=new global.Int8Array(buffer);var b=new global.Int16Array(buffer);var c=new global.Int32Array(buffer);var d=new global.Uint8Array(buffer);var e=new global.Uint16Array(buffer);var f=new global.Uint32Array(buffer);var g=new global.Float32Array(buffer);var h=new global.Float64Array(buffer);var i=env.STACKTOP|0;var j=env.STACK_MAX|0;var k=env.tempDoublePtr|0;var l=env.ABORT|0;var m=0;var n=0;var o=0;var p=0;var q=global.NaN,r=global.Infinity;var s=0,t=0,u=0,v=0,w=0.0,x=0,y=0,z=0,A=0.0;var B=0;var C=0;var D=0;var E=0;var F=0;var G=0;var H=0;var I=0;var J=0;var K=0;var L=global.Math.floor;var M=global.Math.abs;var N=global.Math.sqrt;var O=global.Math.pow;var P=global.Math.cos;var Q=global.Math.sin;var R=global.Math.tan;var S=global.Math.acos;var T=global.Math.asin;var U=global.Math.atan;var V=global.Math.atan2;var W=global.Math.exp;var X=global.Math.log;var Y=global.Math.ceil;var Z=global.Math.imul;var _=global.Math.min;var $=global.Math.clz32;var aa=env.abort;var ba=env.assert;var ca=env._sin;var da=env._cos;var ea=env._pthread_self;var fa=env._abort;var ga=env.___setErrNo;var ha=env._sbrk;var ia=env._time;var ja=env._emscripten_memcpy_big;var ka=env._sysconf;var la=0.0; // EMSCRIPTEN_START_FUNCS -function ma(a){a=a|0;var b=0;b=i;i=i+a|0;i=i+15&-16;return b|0}function na(){return i|0}function oa(a){a=a|0;i=a}function pa(a,b){a=a|0;b=b|0;i=a;j=b}function qa(a,b){a=a|0;b=b|0;if(!m){m=a;n=b}}function ra(b){b=b|0;a[k>>0]=a[b>>0];a[k+1>>0]=a[b+1>>0];a[k+2>>0]=a[b+2>>0];a[k+3>>0]=a[b+3>>0]}function sa(b){b=b|0;a[k>>0]=a[b>>0];a[k+1>>0]=a[b+1>>0];a[k+2>>0]=a[b+2>>0];a[k+3>>0]=a[b+3>>0];a[k+4>>0]=a[b+4>>0];a[k+5>>0]=a[b+5>>0];a[k+6>>0]=a[b+6>>0];a[k+7>>0]=a[b+7>>0]}function ta(a){a=a|0;B=a}function ua(){return B|0}function va(a){a=a|0;var b=0,d=0,e=0.0,f=0,g=0,i=0,j=0.0;if(a>>>0>1){b=0;d=a;while(1){b=b+1|0;if(d>>>0>3)d=d>>>1;else{d=b;break}}}else d=0;if((1<<d|0)!=(a|0)){a=0;return a|0}i=a>>>1;if(a>>>0>1073741823){a=0;return a|0}b=za(4)|0;if(!b){a=b;return a|0}c[b+8>>2]=d;d=i<<3;g=za(d)|0;c[b>>2]=g;if(!g){Aa(b);a=0;return a|0}f=za(d)|0;c[b+4>>2]=f;if(!f){Aa(g);Aa(b);a=0;return a|0}if(!i){a=b;return a|0}e=+(a>>>0);d=0;do{j=+(d|0)*6.283185307179586/e;h[g+(d<<3)>>3]=+P(+j);h[f+(d<<3)>>3]=+Q(+j);d=d+1|0}while((d|0)!=(i|0));return b|0}function wa(a){a=a|0;if(!a)return;Aa(c[a>>2]|0);Aa(c[a+4>>2]|0);Aa(a);return}function xa(a,b,d,e){a=a|0;b=b|0;d=d|0;e=e|0;var f=0,g=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,p=0.0,q=0,r=0,s=0.0,t=0,u=0.0,v=0.0,w=0.0;n=c[e>>2]|0;o=c[e+4>>2]|0;if((d|0)<=0)return;i=c[e+8>>2]|0;if(!i){e=0;do e=e+1|0;while((e|0)!=(d|0))}else{j=0;do{f=j;g=0;e=0;while(1){e=f&1|e<<1;g=g+1|0;if((g|0)==(i|0))break;else f=f>>>1}if((e|0)>(j|0)){m=a+(j<<3)|0;p=+h[m>>3];l=a+(e<<3)|0;h[m>>3]=+h[l>>3];h[l>>3]=p;l=b+(j<<3)|0;p=+h[l>>3];m=b+(e<<3)|0;h[l>>3]=+h[m>>3];h[m>>3]=p}j=j+1|0}while((j|0)!=(d|0))}if((d|0)<2)return;else m=2;do{e=(m|0)/2|0;f=(d|0)/(m|0)|0;i=(m|0)>1;j=0;do{g=j+e|0;if(i){k=j;l=0;while(1){t=k+e|0;q=a+(t<<3)|0;u=+h[q>>3];w=+h[n+(l<<3)>>3];t=b+(t<<3)|0;v=+h[t>>3];p=+h[o+(l<<3)>>3];s=u*w+v*p;p=w*v-u*p;r=a+(k<<3)|0;h[q>>3]=+h[r>>3]-s;q=b+(k<<3)|0;h[t>>3]=+h[q>>3]-p;h[r>>3]=s+ +h[r>>3];h[q>>3]=p+ +h[q>>3];k=k+1|0;if((k|0)>=(g|0))break;else l=l+f|0}}j=j+m|0}while((j|0)<(d|0));t=m;m=m<<1}while(!((t|0)==(d|0)|(m|0)>(d|0)));return}function ya(){var a=0;if(!(c[2]|0))a=52;else a=c[(ea()|0)+60>>2]|0;return a|0}function za(a){a=a|0;var b=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,p=0,q=0,r=0,s=0,t=0,u=0,v=0,w=0,x=0,y=0,z=0,A=0,B=0,C=0,D=0,E=0,F=0,G=0,H=0,I=0,J=0,K=0,L=0;do if(a>>>0<245){o=a>>>0<11?16:a+11&-8;a=o>>>3;j=c[14]|0;b=j>>>a;if(b&3){b=(b&1^1)+a|0;d=96+(b<<1<<2)|0;e=d+8|0;f=c[e>>2]|0;g=f+8|0;h=c[g>>2]|0;do if((d|0)!=(h|0)){if(h>>>0<(c[18]|0)>>>0)fa();a=h+12|0;if((c[a>>2]|0)==(f|0)){c[a>>2]=d;c[e>>2]=h;break}else fa()}else c[14]=j&~(1<<b);while(0);L=b<<3;c[f+4>>2]=L|3;L=f+L+4|0;c[L>>2]=c[L>>2]|1;L=g;return L|0}h=c[16]|0;if(o>>>0>h>>>0){if(b){d=2<<a;d=b<<a&(d|0-d);d=(d&0-d)+-1|0;i=d>>>12&16;d=d>>>i;f=d>>>5&8;d=d>>>f;g=d>>>2&4;d=d>>>g;e=d>>>1&2;d=d>>>e;b=d>>>1&1;b=(f|i|g|e|b)+(d>>>b)|0;d=96+(b<<1<<2)|0;e=d+8|0;g=c[e>>2]|0;i=g+8|0;f=c[i>>2]|0;do if((d|0)!=(f|0)){if(f>>>0<(c[18]|0)>>>0)fa();a=f+12|0;if((c[a>>2]|0)==(g|0)){c[a>>2]=d;c[e>>2]=f;k=c[16]|0;break}else fa()}else{c[14]=j&~(1<<b);k=h}while(0);h=(b<<3)-o|0;c[g+4>>2]=o|3;e=g+o|0;c[e+4>>2]=h|1;c[e+h>>2]=h;if(k){f=c[19]|0;b=k>>>3;d=96+(b<<1<<2)|0;a=c[14]|0;b=1<<b;if(a&b){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{l=a;m=b}}else{c[14]=a|b;l=d+8|0;m=d}c[l>>2]=f;c[m+12>>2]=f;c[f+8>>2]=m;c[f+12>>2]=d}c[16]=h;c[19]=e;L=i;return L|0}a=c[15]|0;if(a){d=(a&0-a)+-1|0;K=d>>>12&16;d=d>>>K;J=d>>>5&8;d=d>>>J;L=d>>>2&4;d=d>>>L;b=d>>>1&2;d=d>>>b;e=d>>>1&1;e=c[360+((J|K|L|b|e)+(d>>>e)<<2)>>2]|0;d=(c[e+4>>2]&-8)-o|0;b=e;while(1){a=c[b+16>>2]|0;if(!a){a=c[b+20>>2]|0;if(!a){j=e;break}}b=(c[a+4>>2]&-8)-o|0;L=b>>>0<d>>>0;d=L?b:d;b=a;e=L?a:e}g=c[18]|0;if(j>>>0<g>>>0)fa();i=j+o|0;if(j>>>0>=i>>>0)fa();h=c[j+24>>2]|0;e=c[j+12>>2]|0;do if((e|0)==(j|0)){b=j+20|0;a=c[b>>2]|0;if(!a){b=j+16|0;a=c[b>>2]|0;if(!a){n=0;break}}while(1){e=a+20|0;f=c[e>>2]|0;if(f){a=f;b=e;continue}e=a+16|0;f=c[e>>2]|0;if(!f)break;else{a=f;b=e}}if(b>>>0<g>>>0)fa();else{c[b>>2]=0;n=a;break}}else{f=c[j+8>>2]|0;if(f>>>0<g>>>0)fa();a=f+12|0;if((c[a>>2]|0)!=(j|0))fa();b=e+8|0;if((c[b>>2]|0)==(j|0)){c[a>>2]=e;c[b>>2]=f;n=e;break}else fa()}while(0);do if(h){a=c[j+28>>2]|0;b=360+(a<<2)|0;if((j|0)==(c[b>>2]|0)){c[b>>2]=n;if(!n){c[15]=c[15]&~(1<<a);break}}else{if(h>>>0<(c[18]|0)>>>0)fa();a=h+16|0;if((c[a>>2]|0)==(j|0))c[a>>2]=n;else c[h+20>>2]=n;if(!n)break}b=c[18]|0;if(n>>>0<b>>>0)fa();c[n+24>>2]=h;a=c[j+16>>2]|0;do if(a)if(a>>>0<b>>>0)fa();else{c[n+16>>2]=a;c[a+24>>2]=n;break}while(0);a=c[j+20>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[n+20>>2]=a;c[a+24>>2]=n;break}}while(0);if(d>>>0<16){L=d+o|0;c[j+4>>2]=L|3;L=j+L+4|0;c[L>>2]=c[L>>2]|1}else{c[j+4>>2]=o|3;c[i+4>>2]=d|1;c[i+d>>2]=d;a=c[16]|0;if(a){f=c[19]|0;b=a>>>3;e=96+(b<<1<<2)|0;a=c[14]|0;b=1<<b;if(a&b){a=e+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{p=a;q=b}}else{c[14]=a|b;p=e+8|0;q=e}c[p>>2]=f;c[q+12>>2]=f;c[f+8>>2]=q;c[f+12>>2]=e}c[16]=d;c[19]=i}L=j+8|0;return L|0}}}else if(a>>>0<=4294967231){a=a+11|0;o=a&-8;j=c[15]|0;if(j){d=0-o|0;a=a>>>8;if(a)if(o>>>0>16777215)i=31;else{q=(a+1048320|0)>>>16&8;E=a<<q;p=(E+520192|0)>>>16&4;E=E<<p;i=(E+245760|0)>>>16&2;i=14-(p|q|i)+(E<<i>>>15)|0;i=o>>>(i+7|0)&1|i<<1}else i=0;b=c[360+(i<<2)>>2]|0;a:do if(!b){a=0;b=0;E=86}else{f=d;a=0;g=o<<((i|0)==31?0:25-(i>>>1)|0);h=b;b=0;while(1){e=c[h+4>>2]&-8;d=e-o|0;if(d>>>0<f>>>0)if((e|0)==(o|0)){a=h;b=h;E=90;break a}else b=h;else d=f;e=c[h+20>>2]|0;h=c[h+16+(g>>>31<<2)>>2]|0;a=(e|0)==0|(e|0)==(h|0)?a:e;e=(h|0)==0;if(e){E=86;break}else{f=d;g=g<<(e&1^1)}}}while(0);if((E|0)==86){if((a|0)==0&(b|0)==0){a=2<<i;a=j&(a|0-a);if(!a)break;q=(a&0-a)+-1|0;m=q>>>12&16;q=q>>>m;l=q>>>5&8;q=q>>>l;n=q>>>2&4;q=q>>>n;p=q>>>1&2;q=q>>>p;a=q>>>1&1;a=c[360+((l|m|n|p|a)+(q>>>a)<<2)>>2]|0}if(!a){i=d;j=b}else E=90}if((E|0)==90)while(1){E=0;q=(c[a+4>>2]&-8)-o|0;e=q>>>0<d>>>0;d=e?q:d;b=e?a:b;e=c[a+16>>2]|0;if(e){a=e;E=90;continue}a=c[a+20>>2]|0;if(!a){i=d;j=b;break}else E=90}if((j|0)!=0?i>>>0<((c[16]|0)-o|0)>>>0:0){f=c[18]|0;if(j>>>0<f>>>0)fa();h=j+o|0;if(j>>>0>=h>>>0)fa();g=c[j+24>>2]|0;d=c[j+12>>2]|0;do if((d|0)==(j|0)){b=j+20|0;a=c[b>>2]|0;if(!a){b=j+16|0;a=c[b>>2]|0;if(!a){s=0;break}}while(1){d=a+20|0;e=c[d>>2]|0;if(e){a=e;b=d;continue}d=a+16|0;e=c[d>>2]|0;if(!e)break;else{a=e;b=d}}if(b>>>0<f>>>0)fa();else{c[b>>2]=0;s=a;break}}else{e=c[j+8>>2]|0;if(e>>>0<f>>>0)fa();a=e+12|0;if((c[a>>2]|0)!=(j|0))fa();b=d+8|0;if((c[b>>2]|0)==(j|0)){c[a>>2]=d;c[b>>2]=e;s=d;break}else fa()}while(0);do if(g){a=c[j+28>>2]|0;b=360+(a<<2)|0;if((j|0)==(c[b>>2]|0)){c[b>>2]=s;if(!s){c[15]=c[15]&~(1<<a);break}}else{if(g>>>0<(c[18]|0)>>>0)fa();a=g+16|0;if((c[a>>2]|0)==(j|0))c[a>>2]=s;else c[g+20>>2]=s;if(!s)break}b=c[18]|0;if(s>>>0<b>>>0)fa();c[s+24>>2]=g;a=c[j+16>>2]|0;do if(a)if(a>>>0<b>>>0)fa();else{c[s+16>>2]=a;c[a+24>>2]=s;break}while(0);a=c[j+20>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[s+20>>2]=a;c[a+24>>2]=s;break}}while(0);do if(i>>>0>=16){c[j+4>>2]=o|3;c[h+4>>2]=i|1;c[h+i>>2]=i;a=i>>>3;if(i>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;if(b&a){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{u=a;v=b}}else{c[14]=b|a;u=d+8|0;v=d}c[u>>2]=h;c[v+12>>2]=h;c[h+8>>2]=v;c[h+12>>2]=d;break}a=i>>>8;if(a)if(i>>>0>16777215)d=31;else{K=(a+1048320|0)>>>16&8;L=a<<K;J=(L+520192|0)>>>16&4;L=L<<J;d=(L+245760|0)>>>16&2;d=14-(J|K|d)+(L<<d>>>15)|0;d=i>>>(d+7|0)&1|d<<1}else d=0;e=360+(d<<2)|0;c[h+28>>2]=d;a=h+16|0;c[a+4>>2]=0;c[a>>2]=0;a=c[15]|0;b=1<<d;if(!(a&b)){c[15]=a|b;c[e>>2]=h;c[h+24>>2]=e;c[h+12>>2]=h;c[h+8>>2]=h;break}f=i<<((d|0)==31?0:25-(d>>>1)|0);a=c[e>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(i|0)){d=a;E=148;break}b=a+16+(f>>>31<<2)|0;d=c[b>>2]|0;if(!d){E=145;break}else{f=f<<1;a=d}}if((E|0)==145)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=h;c[h+24>>2]=a;c[h+12>>2]=h;c[h+8>>2]=h;break}else if((E|0)==148){a=d+8|0;b=c[a>>2]|0;L=c[18]|0;if(b>>>0>=L>>>0&d>>>0>=L>>>0){c[b+12>>2]=h;c[a>>2]=h;c[h+8>>2]=b;c[h+12>>2]=d;c[h+24>>2]=0;break}else fa()}}else{L=i+o|0;c[j+4>>2]=L|3;L=j+L+4|0;c[L>>2]=c[L>>2]|1}while(0);L=j+8|0;return L|0}}}else o=-1;while(0);d=c[16]|0;if(d>>>0>=o>>>0){a=d-o|0;b=c[19]|0;if(a>>>0>15){L=b+o|0;c[19]=L;c[16]=a;c[L+4>>2]=a|1;c[L+a>>2]=a;c[b+4>>2]=o|3}else{c[16]=0;c[19]=0;c[b+4>>2]=d|3;L=b+d+4|0;c[L>>2]=c[L>>2]|1}L=b+8|0;return L|0}a=c[17]|0;if(a>>>0>o>>>0){J=a-o|0;c[17]=J;L=c[20]|0;K=L+o|0;c[20]=K;c[K+4>>2]=J|1;c[L+4>>2]=o|3;L=L+8|0;return L|0}do if(!(c[132]|0)){a=ka(30)|0;if(!(a+-1&a)){c[134]=a;c[133]=a;c[135]=-1;c[136]=-1;c[137]=0;c[125]=0;c[132]=(ia(0)|0)&-16^1431655768;break}else fa()}while(0);h=o+48|0;g=c[134]|0;i=o+47|0;f=g+i|0;g=0-g|0;j=f&g;if(j>>>0<=o>>>0){L=0;return L|0}a=c[124]|0;if((a|0)!=0?(u=c[122]|0,v=u+j|0,v>>>0<=u>>>0|v>>>0>a>>>0):0){L=0;return L|0}b:do if(!(c[125]&4)){a=c[20]|0;c:do if(a){d=504;while(1){b=c[d>>2]|0;if(b>>>0<=a>>>0?(r=d+4|0,(b+(c[r>>2]|0)|0)>>>0>a>>>0):0){e=d;d=r;break}d=c[d+8>>2]|0;if(!d){E=173;break c}}a=f-(c[17]|0)&g;if(a>>>0<2147483647){b=ha(a|0)|0;if((b|0)==((c[e>>2]|0)+(c[d>>2]|0)|0)){if((b|0)!=(-1|0)){h=b;f=a;E=193;break b}}else E=183}}else E=173;while(0);do if((E|0)==173?(t=ha(0)|0,(t|0)!=(-1|0)):0){a=t;b=c[133]|0;d=b+-1|0;if(!(d&a))a=j;else a=j-a+(d+a&0-b)|0;b=c[122]|0;d=b+a|0;if(a>>>0>o>>>0&a>>>0<2147483647){v=c[124]|0;if((v|0)!=0?d>>>0<=b>>>0|d>>>0>v>>>0:0)break;b=ha(a|0)|0;if((b|0)==(t|0)){h=t;f=a;E=193;break b}else E=183}}while(0);d:do if((E|0)==183){d=0-a|0;do if(h>>>0>a>>>0&(a>>>0<2147483647&(b|0)!=(-1|0))?(w=c[134]|0,w=i-a+w&0-w,w>>>0<2147483647):0)if((ha(w|0)|0)==(-1|0)){ha(d|0)|0;break d}else{a=w+a|0;break}while(0);if((b|0)!=(-1|0)){h=b;f=a;E=193;break b}}while(0);c[125]=c[125]|4;E=190}else E=190;while(0);if((((E|0)==190?j>>>0<2147483647:0)?(x=ha(j|0)|0,y=ha(0)|0,x>>>0<y>>>0&((x|0)!=(-1|0)&(y|0)!=(-1|0))):0)?(z=y-x|0,z>>>0>(o+40|0)>>>0):0){h=x;f=z;E=193}if((E|0)==193){a=(c[122]|0)+f|0;c[122]=a;if(a>>>0>(c[123]|0)>>>0)c[123]=a;i=c[20]|0;do if(i){e=504;do{a=c[e>>2]|0;b=e+4|0;d=c[b>>2]|0;if((h|0)==(a+d|0)){A=a;B=b;C=d;D=e;E=203;break}e=c[e+8>>2]|0}while((e|0)!=0);if(((E|0)==203?(c[D+12>>2]&8|0)==0:0)?i>>>0<h>>>0&i>>>0>=A>>>0:0){c[B>>2]=C+f;L=i+8|0;L=(L&7|0)==0?0:0-L&7;K=i+L|0;L=f-L+(c[17]|0)|0;c[20]=K;c[17]=L;c[K+4>>2]=L|1;c[K+L+4>>2]=40;c[21]=c[136];break}a=c[18]|0;if(h>>>0<a>>>0){c[18]=h;j=h}else j=a;d=h+f|0;a=504;while(1){if((c[a>>2]|0)==(d|0)){b=a;E=211;break}a=c[a+8>>2]|0;if(!a){b=504;break}}if((E|0)==211)if(!(c[a+12>>2]&8)){c[b>>2]=h;l=a+4|0;c[l>>2]=(c[l>>2]|0)+f;l=h+8|0;l=h+((l&7|0)==0?0:0-l&7)|0;a=d+8|0;a=d+((a&7|0)==0?0:0-a&7)|0;k=l+o|0;g=a-l-o|0;c[l+4>>2]=o|3;do if((a|0)!=(i|0)){if((a|0)==(c[19]|0)){L=(c[16]|0)+g|0;c[16]=L;c[19]=k;c[k+4>>2]=L|1;c[k+L>>2]=L;break}b=c[a+4>>2]|0;if((b&3|0)==1){i=b&-8;f=b>>>3;e:do if(b>>>0>=256){h=c[a+24>>2]|0;e=c[a+12>>2]|0;do if((e|0)==(a|0)){d=a+16|0;e=d+4|0;b=c[e>>2]|0;if(!b){b=c[d>>2]|0;if(!b){J=0;break}}else d=e;while(1){e=b+20|0;f=c[e>>2]|0;if(f){b=f;d=e;continue}e=b+16|0;f=c[e>>2]|0;if(!f)break;else{b=f;d=e}}if(d>>>0<j>>>0)fa();else{c[d>>2]=0;J=b;break}}else{f=c[a+8>>2]|0;if(f>>>0<j>>>0)fa();b=f+12|0;if((c[b>>2]|0)!=(a|0))fa();d=e+8|0;if((c[d>>2]|0)==(a|0)){c[b>>2]=e;c[d>>2]=f;J=e;break}else fa()}while(0);if(!h)break;b=c[a+28>>2]|0;d=360+(b<<2)|0;do if((a|0)!=(c[d>>2]|0)){if(h>>>0<(c[18]|0)>>>0)fa();b=h+16|0;if((c[b>>2]|0)==(a|0))c[b>>2]=J;else c[h+20>>2]=J;if(!J)break e}else{c[d>>2]=J;if(J)break;c[15]=c[15]&~(1<<b);break e}while(0);e=c[18]|0;if(J>>>0<e>>>0)fa();c[J+24>>2]=h;b=a+16|0;d=c[b>>2]|0;do if(d)if(d>>>0<e>>>0)fa();else{c[J+16>>2]=d;c[d+24>>2]=J;break}while(0);b=c[b+4>>2]|0;if(!b)break;if(b>>>0<(c[18]|0)>>>0)fa();else{c[J+20>>2]=b;c[b+24>>2]=J;break}}else{d=c[a+8>>2]|0;e=c[a+12>>2]|0;b=96+(f<<1<<2)|0;do if((d|0)!=(b|0)){if(d>>>0<j>>>0)fa();if((c[d+12>>2]|0)==(a|0))break;fa()}while(0);if((e|0)==(d|0)){c[14]=c[14]&~(1<<f);break}do if((e|0)==(b|0))G=e+8|0;else{if(e>>>0<j>>>0)fa();b=e+8|0;if((c[b>>2]|0)==(a|0)){G=b;break}fa()}while(0);c[d+12>>2]=e;c[G>>2]=d}while(0);a=a+i|0;g=i+g|0}a=a+4|0;c[a>>2]=c[a>>2]&-2;c[k+4>>2]=g|1;c[k+g>>2]=g;a=g>>>3;if(g>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;do if(!(b&a)){c[14]=b|a;K=d+8|0;L=d}else{a=d+8|0;b=c[a>>2]|0;if(b>>>0>=(c[18]|0)>>>0){K=a;L=b;break}fa()}while(0);c[K>>2]=k;c[L+12>>2]=k;c[k+8>>2]=L;c[k+12>>2]=d;break}a=g>>>8;do if(!a)d=0;else{if(g>>>0>16777215){d=31;break}K=(a+1048320|0)>>>16&8;L=a<<K;J=(L+520192|0)>>>16&4;L=L<<J;d=(L+245760|0)>>>16&2;d=14-(J|K|d)+(L<<d>>>15)|0;d=g>>>(d+7|0)&1|d<<1}while(0);e=360+(d<<2)|0;c[k+28>>2]=d;a=k+16|0;c[a+4>>2]=0;c[a>>2]=0;a=c[15]|0;b=1<<d;if(!(a&b)){c[15]=a|b;c[e>>2]=k;c[k+24>>2]=e;c[k+12>>2]=k;c[k+8>>2]=k;break}f=g<<((d|0)==31?0:25-(d>>>1)|0);a=c[e>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(g|0)){d=a;E=281;break}b=a+16+(f>>>31<<2)|0;d=c[b>>2]|0;if(!d){E=278;break}else{f=f<<1;a=d}}if((E|0)==278)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=k;c[k+24>>2]=a;c[k+12>>2]=k;c[k+8>>2]=k;break}else if((E|0)==281){a=d+8|0;b=c[a>>2]|0;L=c[18]|0;if(b>>>0>=L>>>0&d>>>0>=L>>>0){c[b+12>>2]=k;c[a>>2]=k;c[k+8>>2]=b;c[k+12>>2]=d;c[k+24>>2]=0;break}else fa()}}else{L=(c[17]|0)+g|0;c[17]=L;c[20]=k;c[k+4>>2]=L|1}while(0);L=l+8|0;return L|0}else b=504;while(1){a=c[b>>2]|0;if(a>>>0<=i>>>0?(F=a+(c[b+4>>2]|0)|0,F>>>0>i>>>0):0){b=F;break}b=c[b+8>>2]|0}g=b+-47|0;d=g+8|0;d=g+((d&7|0)==0?0:0-d&7)|0;g=i+16|0;d=d>>>0<g>>>0?i:d;a=d+8|0;e=h+8|0;e=(e&7|0)==0?0:0-e&7;L=h+e|0;e=f+-40-e|0;c[20]=L;c[17]=e;c[L+4>>2]=e|1;c[L+e+4>>2]=40;c[21]=c[136];e=d+4|0;c[e>>2]=27;c[a>>2]=c[126];c[a+4>>2]=c[127];c[a+8>>2]=c[128];c[a+12>>2]=c[129];c[126]=h;c[127]=f;c[129]=0;c[128]=a;a=d+24|0;do{a=a+4|0;c[a>>2]=7}while((a+4|0)>>>0<b>>>0);if((d|0)!=(i|0)){h=d-i|0;c[e>>2]=c[e>>2]&-2;c[i+4>>2]=h|1;c[d>>2]=h;a=h>>>3;if(h>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;if(b&a){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{H=a;I=b}}else{c[14]=b|a;H=d+8|0;I=d}c[H>>2]=i;c[I+12>>2]=i;c[i+8>>2]=I;c[i+12>>2]=d;break}a=h>>>8;if(a)if(h>>>0>16777215)d=31;else{K=(a+1048320|0)>>>16&8;L=a<<K;J=(L+520192|0)>>>16&4;L=L<<J;d=(L+245760|0)>>>16&2;d=14-(J|K|d)+(L<<d>>>15)|0;d=h>>>(d+7|0)&1|d<<1}else d=0;f=360+(d<<2)|0;c[i+28>>2]=d;c[i+20>>2]=0;c[g>>2]=0;a=c[15]|0;b=1<<d;if(!(a&b)){c[15]=a|b;c[f>>2]=i;c[i+24>>2]=f;c[i+12>>2]=i;c[i+8>>2]=i;break}e=h<<((d|0)==31?0:25-(d>>>1)|0);a=c[f>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(h|0)){d=a;E=307;break}b=a+16+(e>>>31<<2)|0;d=c[b>>2]|0;if(!d){E=304;break}else{e=e<<1;a=d}}if((E|0)==304)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=i;c[i+24>>2]=a;c[i+12>>2]=i;c[i+8>>2]=i;break}else if((E|0)==307){a=d+8|0;b=c[a>>2]|0;L=c[18]|0;if(b>>>0>=L>>>0&d>>>0>=L>>>0){c[b+12>>2]=i;c[a>>2]=i;c[i+8>>2]=b;c[i+12>>2]=d;c[i+24>>2]=0;break}else fa()}}}else{L=c[18]|0;if((L|0)==0|h>>>0<L>>>0)c[18]=h;c[126]=h;c[127]=f;c[129]=0;c[23]=c[132];c[22]=-1;a=0;do{L=96+(a<<1<<2)|0;c[L+12>>2]=L;c[L+8>>2]=L;a=a+1|0}while((a|0)!=32);L=h+8|0;L=(L&7|0)==0?0:0-L&7;K=h+L|0;L=f+-40-L|0;c[20]=K;c[17]=L;c[K+4>>2]=L|1;c[K+L+4>>2]=40;c[21]=c[136]}while(0);a=c[17]|0;if(a>>>0>o>>>0){J=a-o|0;c[17]=J;L=c[20]|0;K=L+o|0;c[20]=K;c[K+4>>2]=J|1;c[L+4>>2]=o|3;L=L+8|0;return L|0}}c[(ya()|0)>>2]=12;L=0;return L|0}function Aa(a){a=a|0;var b=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,p=0,q=0;if(!a)return;d=a+-8|0;h=c[18]|0;if(d>>>0<h>>>0)fa();a=c[a+-4>>2]|0;b=a&3;if((b|0)==1)fa();e=a&-8;m=d+e|0;do if(!(a&1)){a=c[d>>2]|0;if(!b)return;k=d+(0-a)|0;j=a+e|0;if(k>>>0<h>>>0)fa();if((k|0)==(c[19]|0)){a=m+4|0;b=c[a>>2]|0;if((b&3|0)!=3){q=k;g=j;break}c[16]=j;c[a>>2]=b&-2;c[k+4>>2]=j|1;c[k+j>>2]=j;return}e=a>>>3;if(a>>>0<256){b=c[k+8>>2]|0;d=c[k+12>>2]|0;a=96+(e<<1<<2)|0;if((b|0)!=(a|0)){if(b>>>0<h>>>0)fa();if((c[b+12>>2]|0)!=(k|0))fa()}if((d|0)==(b|0)){c[14]=c[14]&~(1<<e);q=k;g=j;break}if((d|0)!=(a|0)){if(d>>>0<h>>>0)fa();a=d+8|0;if((c[a>>2]|0)==(k|0))f=a;else fa()}else f=d+8|0;c[b+12>>2]=d;c[f>>2]=b;q=k;g=j;break}f=c[k+24>>2]|0;d=c[k+12>>2]|0;do if((d|0)==(k|0)){b=k+16|0;d=b+4|0;a=c[d>>2]|0;if(!a){a=c[b>>2]|0;if(!a){i=0;break}}else b=d;while(1){d=a+20|0;e=c[d>>2]|0;if(e){a=e;b=d;continue}d=a+16|0;e=c[d>>2]|0;if(!e)break;else{a=e;b=d}}if(b>>>0<h>>>0)fa();else{c[b>>2]=0;i=a;break}}else{e=c[k+8>>2]|0;if(e>>>0<h>>>0)fa();a=e+12|0;if((c[a>>2]|0)!=(k|0))fa();b=d+8|0;if((c[b>>2]|0)==(k|0)){c[a>>2]=d;c[b>>2]=e;i=d;break}else fa()}while(0);if(f){a=c[k+28>>2]|0;b=360+(a<<2)|0;if((k|0)==(c[b>>2]|0)){c[b>>2]=i;if(!i){c[15]=c[15]&~(1<<a);q=k;g=j;break}}else{if(f>>>0<(c[18]|0)>>>0)fa();a=f+16|0;if((c[a>>2]|0)==(k|0))c[a>>2]=i;else c[f+20>>2]=i;if(!i){q=k;g=j;break}}d=c[18]|0;if(i>>>0<d>>>0)fa();c[i+24>>2]=f;a=k+16|0;b=c[a>>2]|0;do if(b)if(b>>>0<d>>>0)fa();else{c[i+16>>2]=b;c[b+24>>2]=i;break}while(0);a=c[a+4>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[i+20>>2]=a;c[a+24>>2]=i;q=k;g=j;break}else{q=k;g=j}}else{q=k;g=j}}else{q=d;g=e}while(0);if(q>>>0>=m>>>0)fa();a=m+4|0;b=c[a>>2]|0;if(!(b&1))fa();if(!(b&2)){if((m|0)==(c[20]|0)){p=(c[17]|0)+g|0;c[17]=p;c[20]=q;c[q+4>>2]=p|1;if((q|0)!=(c[19]|0))return;c[19]=0;c[16]=0;return}if((m|0)==(c[19]|0)){p=(c[16]|0)+g|0;c[16]=p;c[19]=q;c[q+4>>2]=p|1;c[q+p>>2]=p;return}g=(b&-8)+g|0;e=b>>>3;do if(b>>>0>=256){f=c[m+24>>2]|0;a=c[m+12>>2]|0;do if((a|0)==(m|0)){b=m+16|0;d=b+4|0;a=c[d>>2]|0;if(!a){a=c[b>>2]|0;if(!a){n=0;break}}else b=d;while(1){d=a+20|0;e=c[d>>2]|0;if(e){a=e;b=d;continue}d=a+16|0;e=c[d>>2]|0;if(!e)break;else{a=e;b=d}}if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=0;n=a;break}}else{b=c[m+8>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();d=b+12|0;if((c[d>>2]|0)!=(m|0))fa();e=a+8|0;if((c[e>>2]|0)==(m|0)){c[d>>2]=a;c[e>>2]=b;n=a;break}else fa()}while(0);if(f){a=c[m+28>>2]|0;b=360+(a<<2)|0;if((m|0)==(c[b>>2]|0)){c[b>>2]=n;if(!n){c[15]=c[15]&~(1<<a);break}}else{if(f>>>0<(c[18]|0)>>>0)fa();a=f+16|0;if((c[a>>2]|0)==(m|0))c[a>>2]=n;else c[f+20>>2]=n;if(!n)break}d=c[18]|0;if(n>>>0<d>>>0)fa();c[n+24>>2]=f;a=m+16|0;b=c[a>>2]|0;do if(b)if(b>>>0<d>>>0)fa();else{c[n+16>>2]=b;c[b+24>>2]=n;break}while(0);a=c[a+4>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[n+20>>2]=a;c[a+24>>2]=n;break}}}else{b=c[m+8>>2]|0;d=c[m+12>>2]|0;a=96+(e<<1<<2)|0;if((b|0)!=(a|0)){if(b>>>0<(c[18]|0)>>>0)fa();if((c[b+12>>2]|0)!=(m|0))fa()}if((d|0)==(b|0)){c[14]=c[14]&~(1<<e);break}if((d|0)!=(a|0)){if(d>>>0<(c[18]|0)>>>0)fa();a=d+8|0;if((c[a>>2]|0)==(m|0))l=a;else fa()}else l=d+8|0;c[b+12>>2]=d;c[l>>2]=b}while(0);c[q+4>>2]=g|1;c[q+g>>2]=g;if((q|0)==(c[19]|0)){c[16]=g;return}}else{c[a>>2]=b&-2;c[q+4>>2]=g|1;c[q+g>>2]=g}a=g>>>3;if(g>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;if(b&a){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{o=a;p=b}}else{c[14]=b|a;o=d+8|0;p=d}c[o>>2]=q;c[p+12>>2]=q;c[q+8>>2]=p;c[q+12>>2]=d;return}a=g>>>8;if(a)if(g>>>0>16777215)d=31;else{o=(a+1048320|0)>>>16&8;p=a<<o;n=(p+520192|0)>>>16&4;p=p<<n;d=(p+245760|0)>>>16&2;d=14-(n|o|d)+(p<<d>>>15)|0;d=g>>>(d+7|0)&1|d<<1}else d=0;e=360+(d<<2)|0;c[q+28>>2]=d;c[q+20>>2]=0;c[q+16>>2]=0;a=c[15]|0;b=1<<d;do if(a&b){f=g<<((d|0)==31?0:25-(d>>>1)|0);a=c[e>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(g|0)){d=a;e=130;break}b=a+16+(f>>>31<<2)|0;d=c[b>>2]|0;if(!d){e=127;break}else{f=f<<1;a=d}}if((e|0)==127)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=q;c[q+24>>2]=a;c[q+12>>2]=q;c[q+8>>2]=q;break}else if((e|0)==130){a=d+8|0;b=c[a>>2]|0;p=c[18]|0;if(b>>>0>=p>>>0&d>>>0>=p>>>0){c[b+12>>2]=q;c[a>>2]=q;c[q+8>>2]=b;c[q+12>>2]=d;c[q+24>>2]=0;break}else fa()}}else{c[15]=a|b;c[e>>2]=q;c[q+24>>2]=e;c[q+12>>2]=q;c[q+8>>2]=q}while(0);q=(c[22]|0)+-1|0;c[22]=q;if(!q)a=512;else return;while(1){a=c[a>>2]|0;if(!a)break;else a=a+8|0}c[22]=-1;return}function Ba(){}function Ca(b,d,e){b=b|0;d=d|0;e=e|0;var f=0,g=0,h=0,i=0;f=b+e|0;if((e|0)>=20){d=d&255;h=b&3;i=d|d<<8|d<<16|d<<24;g=f&~3;if(h){h=b+4-h|0;while((b|0)<(h|0)){a[b>>0]=d;b=b+1|0}}while((b|0)<(g|0)){c[b>>2]=i;b=b+4|0}}while((b|0)<(f|0)){a[b>>0]=d;b=b+1|0}return b-e|0}function Da(b,d,e){b=b|0;d=d|0;e=e|0;var f=0;if((e|0)>=4096)return ja(b|0,d|0,e|0)|0;f=b|0;if((b&3)==(d&3)){while(b&3){if(!e)return f|0;a[b>>0]=a[d>>0]|0;b=b+1|0;d=d+1|0;e=e-1|0}while((e|0)>=4){c[b>>2]=c[d>>2];b=b+4|0;d=d+4|0;e=e-4|0}}while((e|0)>0){a[b>>0]=a[d>>0]|0;b=b+1|0;d=d+1|0;e=e-1|0}return f|0} +function ma(a){a=a|0;var b=0;b=i;i=i+a|0;i=i+15&-16;return b|0}function na(){return i|0}function oa(a){a=a|0;i=a}function pa(a,b){a=a|0;b=b|0;i=a;j=b}function qa(a,b){a=a|0;b=b|0;if(!m){m=a;n=b}}function ra(b){b=b|0;a[k>>0]=a[b>>0];a[k+1>>0]=a[b+1>>0];a[k+2>>0]=a[b+2>>0];a[k+3>>0]=a[b+3>>0]}function sa(b){b=b|0;a[k>>0]=a[b>>0];a[k+1>>0]=a[b+1>>0];a[k+2>>0]=a[b+2>>0];a[k+3>>0]=a[b+3>>0];a[k+4>>0]=a[b+4>>0];a[k+5>>0]=a[b+5>>0];a[k+6>>0]=a[b+6>>0];a[k+7>>0]=a[b+7>>0]}function ta(a){a=a|0;B=a}function ua(){return B|0}function va(a){a=a|0;var b=0,d=0,e=0.0,f=0,g=0,i=0,j=0.0;if(a>>>0>1){b=0;d=a;while(1){b=b+1|0;if(d>>>0>3)d=d>>>1;else{d=b;break}}}else d=0;if((1<<d|0)!=(a|0)){a=0;return a|0}i=a>>>1;if(a>>>0>1073741823){a=0;return a|0}b=Ca(4)|0;if(!b){a=b;return a|0}c[b+8>>2]=d;d=i<<3;g=Ca(d)|0;c[b>>2]=g;if(!g){Da(b);a=0;return a|0}f=Ca(d)|0;c[b+4>>2]=f;if(!f){Da(g);Da(b);a=0;return a|0}if(!i){a=b;return a|0}e=+(a>>>0);d=0;do{j=+(d|0)*6.283185307179586/e;h[g+(d<<3)>>3]=+P(+j);h[f+(d<<3)>>3]=+Q(+j);d=d+1|0}while((d|0)!=(i|0));return b|0}function wa(a){a=a|0;var b=0,d=0,e=0.0,f=0,h=0,i=0,j=0.0;if(a>>>0>1){b=0;d=a;while(1){b=b+1|0;if(d>>>0>3)d=d>>>1;else{d=b;break}}}else d=0;if((1<<d|0)!=(a|0)){a=0;return a|0}i=a>>>1;if((a|0)<0){a=0;return a|0}b=Ca(12)|0;if(!b){a=b;return a|0}c[b+8>>2]=d;d=i<<2;h=Ca(d)|0;c[b>>2]=h;if(!h){Da(b);a=0;return a|0}f=Ca(d)|0;c[b+4>>2]=f;if(!f){Da(h);Da(b);a=0;return a|0}if(!i){a=b;return a|0}e=+(a>>>0);d=0;do{j=+(d|0)*6.283185307179586/e;g[h+(d<<2)>>2]=+P(+j);g[f+(d<<2)>>2]=+Q(+j);d=d+1|0}while((d|0)!=(i|0));return b|0}function xa(a){a=a|0;if(!a)return;Da(c[a>>2]|0);Da(c[a+4>>2]|0);Da(a);return}function ya(a){a=a|0;if(!a)return;Da(c[a>>2]|0);Da(c[a+4>>2]|0);Da(a);return}function za(a,b,d,e){a=a|0;b=b|0;d=d|0;e=e|0;var f=0,g=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,p=0.0,q=0,r=0,s=0.0,t=0,u=0.0,v=0.0,w=0.0;n=c[e>>2]|0;o=c[e+4>>2]|0;if((d|0)<=0)return;i=c[e+8>>2]|0;if(!i){e=0;do e=e+1|0;while((e|0)!=(d|0))}else{j=0;do{f=j;g=0;e=0;while(1){e=f&1|e<<1;g=g+1|0;if((g|0)==(i|0))break;else f=f>>>1}if((e|0)>(j|0)){m=a+(j<<3)|0;p=+h[m>>3];l=a+(e<<3)|0;h[m>>3]=+h[l>>3];h[l>>3]=p;l=b+(j<<3)|0;p=+h[l>>3];m=b+(e<<3)|0;h[l>>3]=+h[m>>3];h[m>>3]=p}j=j+1|0}while((j|0)!=(d|0))}if((d|0)<2)return;else m=2;do{e=(m|0)/2|0;f=(d|0)/(m|0)|0;i=(m|0)>1;j=0;do{g=j+e|0;if(i){k=j;l=0;while(1){t=k+e|0;q=a+(t<<3)|0;u=+h[q>>3];w=+h[n+(l<<3)>>3];t=b+(t<<3)|0;v=+h[t>>3];p=+h[o+(l<<3)>>3];s=u*w+v*p;p=w*v-u*p;r=a+(k<<3)|0;h[q>>3]=+h[r>>3]-s;q=b+(k<<3)|0;h[t>>3]=+h[q>>3]-p;h[r>>3]=s+ +h[r>>3];h[q>>3]=p+ +h[q>>3];k=k+1|0;if((k|0)>=(g|0))break;else l=l+f|0}}j=j+m|0}while((j|0)<(d|0));t=m;m=m<<1}while(!((t|0)==(d|0)|(m|0)>(d|0)));return}function Aa(a,b,d,e){a=a|0;b=b|0;d=d|0;e=e|0;var f=0,h=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,p=0,q=0.0,r=0,s=0.0,t=0,u=0.0,v=0.0,w=0.0;n=c[e>>2]|0;o=c[e+4>>2]|0;if((d|0)<=0)return;i=c[e+8>>2]|0;if(!i){e=0;do e=e+1|0;while((e|0)!=(d|0))}else{j=0;do{f=j;h=0;e=0;while(1){e=f&1|e<<1;h=h+1|0;if((h|0)==(i|0))break;else f=f>>>1}if((e|0)>(j|0)){m=a+(j<<2)|0;l=c[m>>2]|0;k=a+(e<<2)|0;c[m>>2]=c[k>>2];c[k>>2]=l;k=b+(j<<2)|0;l=c[k>>2]|0;m=b+(e<<2)|0;c[k>>2]=c[m>>2];c[m>>2]=l}j=j+1|0}while((j|0)!=(d|0))}if((d|0)<2)return;else m=2;do{e=(m|0)/2|0;f=(d|0)/(m|0)|0;i=(m|0)>1;j=0;do{h=j+e|0;if(i){k=j;l=0;while(1){t=k+e|0;p=a+(t<<2)|0;u=+g[p>>2];w=+g[n+(l<<2)>>2];t=b+(t<<2)|0;v=+g[t>>2];q=+g[o+(l<<2)>>2];s=u*w+v*q;q=w*v-u*q;r=a+(k<<2)|0;g[p>>2]=+g[r>>2]-s;p=b+(k<<2)|0;g[t>>2]=+g[p>>2]-q;g[r>>2]=s+ +g[r>>2];g[p>>2]=q+ +g[p>>2];k=k+1|0;if((k|0)>=(h|0))break;else l=l+f|0}}j=j+m|0}while((j|0)<(d|0));t=m;m=m<<1}while(!((t|0)==(d|0)|(m|0)>(d|0)));return}function Ba(){var a=0;if(!(c[2]|0))a=52;else a=c[(ea()|0)+60>>2]|0;return a|0}function Ca(a){a=a|0;var b=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,p=0,q=0,r=0,s=0,t=0,u=0,v=0,w=0,x=0,y=0,z=0,A=0,B=0,C=0,D=0,E=0,F=0,G=0,H=0,I=0,J=0,K=0,L=0;do if(a>>>0<245){o=a>>>0<11?16:a+11&-8;a=o>>>3;j=c[14]|0;b=j>>>a;if(b&3){b=(b&1^1)+a|0;d=96+(b<<1<<2)|0;e=d+8|0;f=c[e>>2]|0;g=f+8|0;h=c[g>>2]|0;do if((d|0)!=(h|0)){if(h>>>0<(c[18]|0)>>>0)fa();a=h+12|0;if((c[a>>2]|0)==(f|0)){c[a>>2]=d;c[e>>2]=h;break}else fa()}else c[14]=j&~(1<<b);while(0);L=b<<3;c[f+4>>2]=L|3;L=f+L+4|0;c[L>>2]=c[L>>2]|1;L=g;return L|0}h=c[16]|0;if(o>>>0>h>>>0){if(b){d=2<<a;d=b<<a&(d|0-d);d=(d&0-d)+-1|0;i=d>>>12&16;d=d>>>i;f=d>>>5&8;d=d>>>f;g=d>>>2&4;d=d>>>g;e=d>>>1&2;d=d>>>e;b=d>>>1&1;b=(f|i|g|e|b)+(d>>>b)|0;d=96+(b<<1<<2)|0;e=d+8|0;g=c[e>>2]|0;i=g+8|0;f=c[i>>2]|0;do if((d|0)!=(f|0)){if(f>>>0<(c[18]|0)>>>0)fa();a=f+12|0;if((c[a>>2]|0)==(g|0)){c[a>>2]=d;c[e>>2]=f;k=c[16]|0;break}else fa()}else{c[14]=j&~(1<<b);k=h}while(0);h=(b<<3)-o|0;c[g+4>>2]=o|3;e=g+o|0;c[e+4>>2]=h|1;c[e+h>>2]=h;if(k){f=c[19]|0;b=k>>>3;d=96+(b<<1<<2)|0;a=c[14]|0;b=1<<b;if(a&b){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{l=a;m=b}}else{c[14]=a|b;l=d+8|0;m=d}c[l>>2]=f;c[m+12>>2]=f;c[f+8>>2]=m;c[f+12>>2]=d}c[16]=h;c[19]=e;L=i;return L|0}a=c[15]|0;if(a){d=(a&0-a)+-1|0;K=d>>>12&16;d=d>>>K;J=d>>>5&8;d=d>>>J;L=d>>>2&4;d=d>>>L;b=d>>>1&2;d=d>>>b;e=d>>>1&1;e=c[360+((J|K|L|b|e)+(d>>>e)<<2)>>2]|0;d=(c[e+4>>2]&-8)-o|0;b=e;while(1){a=c[b+16>>2]|0;if(!a){a=c[b+20>>2]|0;if(!a){j=e;break}}b=(c[a+4>>2]&-8)-o|0;L=b>>>0<d>>>0;d=L?b:d;b=a;e=L?a:e}g=c[18]|0;if(j>>>0<g>>>0)fa();i=j+o|0;if(j>>>0>=i>>>0)fa();h=c[j+24>>2]|0;e=c[j+12>>2]|0;do if((e|0)==(j|0)){b=j+20|0;a=c[b>>2]|0;if(!a){b=j+16|0;a=c[b>>2]|0;if(!a){n=0;break}}while(1){e=a+20|0;f=c[e>>2]|0;if(f){a=f;b=e;continue}e=a+16|0;f=c[e>>2]|0;if(!f)break;else{a=f;b=e}}if(b>>>0<g>>>0)fa();else{c[b>>2]=0;n=a;break}}else{f=c[j+8>>2]|0;if(f>>>0<g>>>0)fa();a=f+12|0;if((c[a>>2]|0)!=(j|0))fa();b=e+8|0;if((c[b>>2]|0)==(j|0)){c[a>>2]=e;c[b>>2]=f;n=e;break}else fa()}while(0);do if(h){a=c[j+28>>2]|0;b=360+(a<<2)|0;if((j|0)==(c[b>>2]|0)){c[b>>2]=n;if(!n){c[15]=c[15]&~(1<<a);break}}else{if(h>>>0<(c[18]|0)>>>0)fa();a=h+16|0;if((c[a>>2]|0)==(j|0))c[a>>2]=n;else c[h+20>>2]=n;if(!n)break}b=c[18]|0;if(n>>>0<b>>>0)fa();c[n+24>>2]=h;a=c[j+16>>2]|0;do if(a)if(a>>>0<b>>>0)fa();else{c[n+16>>2]=a;c[a+24>>2]=n;break}while(0);a=c[j+20>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[n+20>>2]=a;c[a+24>>2]=n;break}}while(0);if(d>>>0<16){L=d+o|0;c[j+4>>2]=L|3;L=j+L+4|0;c[L>>2]=c[L>>2]|1}else{c[j+4>>2]=o|3;c[i+4>>2]=d|1;c[i+d>>2]=d;a=c[16]|0;if(a){f=c[19]|0;b=a>>>3;e=96+(b<<1<<2)|0;a=c[14]|0;b=1<<b;if(a&b){a=e+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{p=a;q=b}}else{c[14]=a|b;p=e+8|0;q=e}c[p>>2]=f;c[q+12>>2]=f;c[f+8>>2]=q;c[f+12>>2]=e}c[16]=d;c[19]=i}L=j+8|0;return L|0}}}else if(a>>>0<=4294967231){a=a+11|0;o=a&-8;j=c[15]|0;if(j){d=0-o|0;a=a>>>8;if(a)if(o>>>0>16777215)i=31;else{q=(a+1048320|0)>>>16&8;E=a<<q;p=(E+520192|0)>>>16&4;E=E<<p;i=(E+245760|0)>>>16&2;i=14-(p|q|i)+(E<<i>>>15)|0;i=o>>>(i+7|0)&1|i<<1}else i=0;b=c[360+(i<<2)>>2]|0;a:do if(!b){a=0;b=0;E=86}else{f=d;a=0;g=o<<((i|0)==31?0:25-(i>>>1)|0);h=b;b=0;while(1){e=c[h+4>>2]&-8;d=e-o|0;if(d>>>0<f>>>0)if((e|0)==(o|0)){a=h;b=h;E=90;break a}else b=h;else d=f;e=c[h+20>>2]|0;h=c[h+16+(g>>>31<<2)>>2]|0;a=(e|0)==0|(e|0)==(h|0)?a:e;e=(h|0)==0;if(e){E=86;break}else{f=d;g=g<<(e&1^1)}}}while(0);if((E|0)==86){if((a|0)==0&(b|0)==0){a=2<<i;a=j&(a|0-a);if(!a)break;q=(a&0-a)+-1|0;m=q>>>12&16;q=q>>>m;l=q>>>5&8;q=q>>>l;n=q>>>2&4;q=q>>>n;p=q>>>1&2;q=q>>>p;a=q>>>1&1;a=c[360+((l|m|n|p|a)+(q>>>a)<<2)>>2]|0}if(!a){i=d;j=b}else E=90}if((E|0)==90)while(1){E=0;q=(c[a+4>>2]&-8)-o|0;e=q>>>0<d>>>0;d=e?q:d;b=e?a:b;e=c[a+16>>2]|0;if(e){a=e;E=90;continue}a=c[a+20>>2]|0;if(!a){i=d;j=b;break}else E=90}if((j|0)!=0?i>>>0<((c[16]|0)-o|0)>>>0:0){f=c[18]|0;if(j>>>0<f>>>0)fa();h=j+o|0;if(j>>>0>=h>>>0)fa();g=c[j+24>>2]|0;d=c[j+12>>2]|0;do if((d|0)==(j|0)){b=j+20|0;a=c[b>>2]|0;if(!a){b=j+16|0;a=c[b>>2]|0;if(!a){s=0;break}}while(1){d=a+20|0;e=c[d>>2]|0;if(e){a=e;b=d;continue}d=a+16|0;e=c[d>>2]|0;if(!e)break;else{a=e;b=d}}if(b>>>0<f>>>0)fa();else{c[b>>2]=0;s=a;break}}else{e=c[j+8>>2]|0;if(e>>>0<f>>>0)fa();a=e+12|0;if((c[a>>2]|0)!=(j|0))fa();b=d+8|0;if((c[b>>2]|0)==(j|0)){c[a>>2]=d;c[b>>2]=e;s=d;break}else fa()}while(0);do if(g){a=c[j+28>>2]|0;b=360+(a<<2)|0;if((j|0)==(c[b>>2]|0)){c[b>>2]=s;if(!s){c[15]=c[15]&~(1<<a);break}}else{if(g>>>0<(c[18]|0)>>>0)fa();a=g+16|0;if((c[a>>2]|0)==(j|0))c[a>>2]=s;else c[g+20>>2]=s;if(!s)break}b=c[18]|0;if(s>>>0<b>>>0)fa();c[s+24>>2]=g;a=c[j+16>>2]|0;do if(a)if(a>>>0<b>>>0)fa();else{c[s+16>>2]=a;c[a+24>>2]=s;break}while(0);a=c[j+20>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[s+20>>2]=a;c[a+24>>2]=s;break}}while(0);do if(i>>>0>=16){c[j+4>>2]=o|3;c[h+4>>2]=i|1;c[h+i>>2]=i;a=i>>>3;if(i>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;if(b&a){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{u=a;v=b}}else{c[14]=b|a;u=d+8|0;v=d}c[u>>2]=h;c[v+12>>2]=h;c[h+8>>2]=v;c[h+12>>2]=d;break}a=i>>>8;if(a)if(i>>>0>16777215)d=31;else{K=(a+1048320|0)>>>16&8;L=a<<K;J=(L+520192|0)>>>16&4;L=L<<J;d=(L+245760|0)>>>16&2;d=14-(J|K|d)+(L<<d>>>15)|0;d=i>>>(d+7|0)&1|d<<1}else d=0;e=360+(d<<2)|0;c[h+28>>2]=d;a=h+16|0;c[a+4>>2]=0;c[a>>2]=0;a=c[15]|0;b=1<<d;if(!(a&b)){c[15]=a|b;c[e>>2]=h;c[h+24>>2]=e;c[h+12>>2]=h;c[h+8>>2]=h;break}f=i<<((d|0)==31?0:25-(d>>>1)|0);a=c[e>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(i|0)){d=a;E=148;break}b=a+16+(f>>>31<<2)|0;d=c[b>>2]|0;if(!d){E=145;break}else{f=f<<1;a=d}}if((E|0)==145)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=h;c[h+24>>2]=a;c[h+12>>2]=h;c[h+8>>2]=h;break}else if((E|0)==148){a=d+8|0;b=c[a>>2]|0;L=c[18]|0;if(b>>>0>=L>>>0&d>>>0>=L>>>0){c[b+12>>2]=h;c[a>>2]=h;c[h+8>>2]=b;c[h+12>>2]=d;c[h+24>>2]=0;break}else fa()}}else{L=i+o|0;c[j+4>>2]=L|3;L=j+L+4|0;c[L>>2]=c[L>>2]|1}while(0);L=j+8|0;return L|0}}}else o=-1;while(0);d=c[16]|0;if(d>>>0>=o>>>0){a=d-o|0;b=c[19]|0;if(a>>>0>15){L=b+o|0;c[19]=L;c[16]=a;c[L+4>>2]=a|1;c[L+a>>2]=a;c[b+4>>2]=o|3}else{c[16]=0;c[19]=0;c[b+4>>2]=d|3;L=b+d+4|0;c[L>>2]=c[L>>2]|1}L=b+8|0;return L|0}a=c[17]|0;if(a>>>0>o>>>0){J=a-o|0;c[17]=J;L=c[20]|0;K=L+o|0;c[20]=K;c[K+4>>2]=J|1;c[L+4>>2]=o|3;L=L+8|0;return L|0}do if(!(c[132]|0)){a=ka(30)|0;if(!(a+-1&a)){c[134]=a;c[133]=a;c[135]=-1;c[136]=-1;c[137]=0;c[125]=0;c[132]=(ia(0)|0)&-16^1431655768;break}else fa()}while(0);h=o+48|0;g=c[134]|0;i=o+47|0;f=g+i|0;g=0-g|0;j=f&g;if(j>>>0<=o>>>0){L=0;return L|0}a=c[124]|0;if((a|0)!=0?(u=c[122]|0,v=u+j|0,v>>>0<=u>>>0|v>>>0>a>>>0):0){L=0;return L|0}b:do if(!(c[125]&4)){a=c[20]|0;c:do if(a){d=504;while(1){b=c[d>>2]|0;if(b>>>0<=a>>>0?(r=d+4|0,(b+(c[r>>2]|0)|0)>>>0>a>>>0):0){e=d;d=r;break}d=c[d+8>>2]|0;if(!d){E=173;break c}}a=f-(c[17]|0)&g;if(a>>>0<2147483647){b=ha(a|0)|0;if((b|0)==((c[e>>2]|0)+(c[d>>2]|0)|0)){if((b|0)!=(-1|0)){h=b;f=a;E=193;break b}}else E=183}}else E=173;while(0);do if((E|0)==173?(t=ha(0)|0,(t|0)!=(-1|0)):0){a=t;b=c[133]|0;d=b+-1|0;if(!(d&a))a=j;else a=j-a+(d+a&0-b)|0;b=c[122]|0;d=b+a|0;if(a>>>0>o>>>0&a>>>0<2147483647){v=c[124]|0;if((v|0)!=0?d>>>0<=b>>>0|d>>>0>v>>>0:0)break;b=ha(a|0)|0;if((b|0)==(t|0)){h=t;f=a;E=193;break b}else E=183}}while(0);d:do if((E|0)==183){d=0-a|0;do if(h>>>0>a>>>0&(a>>>0<2147483647&(b|0)!=(-1|0))?(w=c[134]|0,w=i-a+w&0-w,w>>>0<2147483647):0)if((ha(w|0)|0)==(-1|0)){ha(d|0)|0;break d}else{a=w+a|0;break}while(0);if((b|0)!=(-1|0)){h=b;f=a;E=193;break b}}while(0);c[125]=c[125]|4;E=190}else E=190;while(0);if((((E|0)==190?j>>>0<2147483647:0)?(x=ha(j|0)|0,y=ha(0)|0,x>>>0<y>>>0&((x|0)!=(-1|0)&(y|0)!=(-1|0))):0)?(z=y-x|0,z>>>0>(o+40|0)>>>0):0){h=x;f=z;E=193}if((E|0)==193){a=(c[122]|0)+f|0;c[122]=a;if(a>>>0>(c[123]|0)>>>0)c[123]=a;i=c[20]|0;do if(i){e=504;do{a=c[e>>2]|0;b=e+4|0;d=c[b>>2]|0;if((h|0)==(a+d|0)){A=a;B=b;C=d;D=e;E=203;break}e=c[e+8>>2]|0}while((e|0)!=0);if(((E|0)==203?(c[D+12>>2]&8|0)==0:0)?i>>>0<h>>>0&i>>>0>=A>>>0:0){c[B>>2]=C+f;L=i+8|0;L=(L&7|0)==0?0:0-L&7;K=i+L|0;L=f-L+(c[17]|0)|0;c[20]=K;c[17]=L;c[K+4>>2]=L|1;c[K+L+4>>2]=40;c[21]=c[136];break}a=c[18]|0;if(h>>>0<a>>>0){c[18]=h;j=h}else j=a;d=h+f|0;a=504;while(1){if((c[a>>2]|0)==(d|0)){b=a;E=211;break}a=c[a+8>>2]|0;if(!a){b=504;break}}if((E|0)==211)if(!(c[a+12>>2]&8)){c[b>>2]=h;l=a+4|0;c[l>>2]=(c[l>>2]|0)+f;l=h+8|0;l=h+((l&7|0)==0?0:0-l&7)|0;a=d+8|0;a=d+((a&7|0)==0?0:0-a&7)|0;k=l+o|0;g=a-l-o|0;c[l+4>>2]=o|3;do if((a|0)!=(i|0)){if((a|0)==(c[19]|0)){L=(c[16]|0)+g|0;c[16]=L;c[19]=k;c[k+4>>2]=L|1;c[k+L>>2]=L;break}b=c[a+4>>2]|0;if((b&3|0)==1){i=b&-8;f=b>>>3;e:do if(b>>>0>=256){h=c[a+24>>2]|0;e=c[a+12>>2]|0;do if((e|0)==(a|0)){d=a+16|0;e=d+4|0;b=c[e>>2]|0;if(!b){b=c[d>>2]|0;if(!b){J=0;break}}else d=e;while(1){e=b+20|0;f=c[e>>2]|0;if(f){b=f;d=e;continue}e=b+16|0;f=c[e>>2]|0;if(!f)break;else{b=f;d=e}}if(d>>>0<j>>>0)fa();else{c[d>>2]=0;J=b;break}}else{f=c[a+8>>2]|0;if(f>>>0<j>>>0)fa();b=f+12|0;if((c[b>>2]|0)!=(a|0))fa();d=e+8|0;if((c[d>>2]|0)==(a|0)){c[b>>2]=e;c[d>>2]=f;J=e;break}else fa()}while(0);if(!h)break;b=c[a+28>>2]|0;d=360+(b<<2)|0;do if((a|0)!=(c[d>>2]|0)){if(h>>>0<(c[18]|0)>>>0)fa();b=h+16|0;if((c[b>>2]|0)==(a|0))c[b>>2]=J;else c[h+20>>2]=J;if(!J)break e}else{c[d>>2]=J;if(J)break;c[15]=c[15]&~(1<<b);break e}while(0);e=c[18]|0;if(J>>>0<e>>>0)fa();c[J+24>>2]=h;b=a+16|0;d=c[b>>2]|0;do if(d)if(d>>>0<e>>>0)fa();else{c[J+16>>2]=d;c[d+24>>2]=J;break}while(0);b=c[b+4>>2]|0;if(!b)break;if(b>>>0<(c[18]|0)>>>0)fa();else{c[J+20>>2]=b;c[b+24>>2]=J;break}}else{d=c[a+8>>2]|0;e=c[a+12>>2]|0;b=96+(f<<1<<2)|0;do if((d|0)!=(b|0)){if(d>>>0<j>>>0)fa();if((c[d+12>>2]|0)==(a|0))break;fa()}while(0);if((e|0)==(d|0)){c[14]=c[14]&~(1<<f);break}do if((e|0)==(b|0))G=e+8|0;else{if(e>>>0<j>>>0)fa();b=e+8|0;if((c[b>>2]|0)==(a|0)){G=b;break}fa()}while(0);c[d+12>>2]=e;c[G>>2]=d}while(0);a=a+i|0;g=i+g|0}a=a+4|0;c[a>>2]=c[a>>2]&-2;c[k+4>>2]=g|1;c[k+g>>2]=g;a=g>>>3;if(g>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;do if(!(b&a)){c[14]=b|a;K=d+8|0;L=d}else{a=d+8|0;b=c[a>>2]|0;if(b>>>0>=(c[18]|0)>>>0){K=a;L=b;break}fa()}while(0);c[K>>2]=k;c[L+12>>2]=k;c[k+8>>2]=L;c[k+12>>2]=d;break}a=g>>>8;do if(!a)d=0;else{if(g>>>0>16777215){d=31;break}K=(a+1048320|0)>>>16&8;L=a<<K;J=(L+520192|0)>>>16&4;L=L<<J;d=(L+245760|0)>>>16&2;d=14-(J|K|d)+(L<<d>>>15)|0;d=g>>>(d+7|0)&1|d<<1}while(0);e=360+(d<<2)|0;c[k+28>>2]=d;a=k+16|0;c[a+4>>2]=0;c[a>>2]=0;a=c[15]|0;b=1<<d;if(!(a&b)){c[15]=a|b;c[e>>2]=k;c[k+24>>2]=e;c[k+12>>2]=k;c[k+8>>2]=k;break}f=g<<((d|0)==31?0:25-(d>>>1)|0);a=c[e>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(g|0)){d=a;E=281;break}b=a+16+(f>>>31<<2)|0;d=c[b>>2]|0;if(!d){E=278;break}else{f=f<<1;a=d}}if((E|0)==278)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=k;c[k+24>>2]=a;c[k+12>>2]=k;c[k+8>>2]=k;break}else if((E|0)==281){a=d+8|0;b=c[a>>2]|0;L=c[18]|0;if(b>>>0>=L>>>0&d>>>0>=L>>>0){c[b+12>>2]=k;c[a>>2]=k;c[k+8>>2]=b;c[k+12>>2]=d;c[k+24>>2]=0;break}else fa()}}else{L=(c[17]|0)+g|0;c[17]=L;c[20]=k;c[k+4>>2]=L|1}while(0);L=l+8|0;return L|0}else b=504;while(1){a=c[b>>2]|0;if(a>>>0<=i>>>0?(F=a+(c[b+4>>2]|0)|0,F>>>0>i>>>0):0){b=F;break}b=c[b+8>>2]|0}g=b+-47|0;d=g+8|0;d=g+((d&7|0)==0?0:0-d&7)|0;g=i+16|0;d=d>>>0<g>>>0?i:d;a=d+8|0;e=h+8|0;e=(e&7|0)==0?0:0-e&7;L=h+e|0;e=f+-40-e|0;c[20]=L;c[17]=e;c[L+4>>2]=e|1;c[L+e+4>>2]=40;c[21]=c[136];e=d+4|0;c[e>>2]=27;c[a>>2]=c[126];c[a+4>>2]=c[127];c[a+8>>2]=c[128];c[a+12>>2]=c[129];c[126]=h;c[127]=f;c[129]=0;c[128]=a;a=d+24|0;do{a=a+4|0;c[a>>2]=7}while((a+4|0)>>>0<b>>>0);if((d|0)!=(i|0)){h=d-i|0;c[e>>2]=c[e>>2]&-2;c[i+4>>2]=h|1;c[d>>2]=h;a=h>>>3;if(h>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;if(b&a){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{H=a;I=b}}else{c[14]=b|a;H=d+8|0;I=d}c[H>>2]=i;c[I+12>>2]=i;c[i+8>>2]=I;c[i+12>>2]=d;break}a=h>>>8;if(a)if(h>>>0>16777215)d=31;else{K=(a+1048320|0)>>>16&8;L=a<<K;J=(L+520192|0)>>>16&4;L=L<<J;d=(L+245760|0)>>>16&2;d=14-(J|K|d)+(L<<d>>>15)|0;d=h>>>(d+7|0)&1|d<<1}else d=0;f=360+(d<<2)|0;c[i+28>>2]=d;c[i+20>>2]=0;c[g>>2]=0;a=c[15]|0;b=1<<d;if(!(a&b)){c[15]=a|b;c[f>>2]=i;c[i+24>>2]=f;c[i+12>>2]=i;c[i+8>>2]=i;break}e=h<<((d|0)==31?0:25-(d>>>1)|0);a=c[f>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(h|0)){d=a;E=307;break}b=a+16+(e>>>31<<2)|0;d=c[b>>2]|0;if(!d){E=304;break}else{e=e<<1;a=d}}if((E|0)==304)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=i;c[i+24>>2]=a;c[i+12>>2]=i;c[i+8>>2]=i;break}else if((E|0)==307){a=d+8|0;b=c[a>>2]|0;L=c[18]|0;if(b>>>0>=L>>>0&d>>>0>=L>>>0){c[b+12>>2]=i;c[a>>2]=i;c[i+8>>2]=b;c[i+12>>2]=d;c[i+24>>2]=0;break}else fa()}}}else{L=c[18]|0;if((L|0)==0|h>>>0<L>>>0)c[18]=h;c[126]=h;c[127]=f;c[129]=0;c[23]=c[132];c[22]=-1;a=0;do{L=96+(a<<1<<2)|0;c[L+12>>2]=L;c[L+8>>2]=L;a=a+1|0}while((a|0)!=32);L=h+8|0;L=(L&7|0)==0?0:0-L&7;K=h+L|0;L=f+-40-L|0;c[20]=K;c[17]=L;c[K+4>>2]=L|1;c[K+L+4>>2]=40;c[21]=c[136]}while(0);a=c[17]|0;if(a>>>0>o>>>0){J=a-o|0;c[17]=J;L=c[20]|0;K=L+o|0;c[20]=K;c[K+4>>2]=J|1;c[L+4>>2]=o|3;L=L+8|0;return L|0}}c[(Ba()|0)>>2]=12;L=0;return L|0}function Da(a){a=a|0;var b=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,p=0,q=0;if(!a)return;d=a+-8|0;h=c[18]|0;if(d>>>0<h>>>0)fa();a=c[a+-4>>2]|0;b=a&3;if((b|0)==1)fa();e=a&-8;m=d+e|0;do if(!(a&1)){a=c[d>>2]|0;if(!b)return;k=d+(0-a)|0;j=a+e|0;if(k>>>0<h>>>0)fa();if((k|0)==(c[19]|0)){a=m+4|0;b=c[a>>2]|0;if((b&3|0)!=3){q=k;g=j;break}c[16]=j;c[a>>2]=b&-2;c[k+4>>2]=j|1;c[k+j>>2]=j;return}e=a>>>3;if(a>>>0<256){b=c[k+8>>2]|0;d=c[k+12>>2]|0;a=96+(e<<1<<2)|0;if((b|0)!=(a|0)){if(b>>>0<h>>>0)fa();if((c[b+12>>2]|0)!=(k|0))fa()}if((d|0)==(b|0)){c[14]=c[14]&~(1<<e);q=k;g=j;break}if((d|0)!=(a|0)){if(d>>>0<h>>>0)fa();a=d+8|0;if((c[a>>2]|0)==(k|0))f=a;else fa()}else f=d+8|0;c[b+12>>2]=d;c[f>>2]=b;q=k;g=j;break}f=c[k+24>>2]|0;d=c[k+12>>2]|0;do if((d|0)==(k|0)){b=k+16|0;d=b+4|0;a=c[d>>2]|0;if(!a){a=c[b>>2]|0;if(!a){i=0;break}}else b=d;while(1){d=a+20|0;e=c[d>>2]|0;if(e){a=e;b=d;continue}d=a+16|0;e=c[d>>2]|0;if(!e)break;else{a=e;b=d}}if(b>>>0<h>>>0)fa();else{c[b>>2]=0;i=a;break}}else{e=c[k+8>>2]|0;if(e>>>0<h>>>0)fa();a=e+12|0;if((c[a>>2]|0)!=(k|0))fa();b=d+8|0;if((c[b>>2]|0)==(k|0)){c[a>>2]=d;c[b>>2]=e;i=d;break}else fa()}while(0);if(f){a=c[k+28>>2]|0;b=360+(a<<2)|0;if((k|0)==(c[b>>2]|0)){c[b>>2]=i;if(!i){c[15]=c[15]&~(1<<a);q=k;g=j;break}}else{if(f>>>0<(c[18]|0)>>>0)fa();a=f+16|0;if((c[a>>2]|0)==(k|0))c[a>>2]=i;else c[f+20>>2]=i;if(!i){q=k;g=j;break}}d=c[18]|0;if(i>>>0<d>>>0)fa();c[i+24>>2]=f;a=k+16|0;b=c[a>>2]|0;do if(b)if(b>>>0<d>>>0)fa();else{c[i+16>>2]=b;c[b+24>>2]=i;break}while(0);a=c[a+4>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[i+20>>2]=a;c[a+24>>2]=i;q=k;g=j;break}else{q=k;g=j}}else{q=k;g=j}}else{q=d;g=e}while(0);if(q>>>0>=m>>>0)fa();a=m+4|0;b=c[a>>2]|0;if(!(b&1))fa();if(!(b&2)){if((m|0)==(c[20]|0)){p=(c[17]|0)+g|0;c[17]=p;c[20]=q;c[q+4>>2]=p|1;if((q|0)!=(c[19]|0))return;c[19]=0;c[16]=0;return}if((m|0)==(c[19]|0)){p=(c[16]|0)+g|0;c[16]=p;c[19]=q;c[q+4>>2]=p|1;c[q+p>>2]=p;return}g=(b&-8)+g|0;e=b>>>3;do if(b>>>0>=256){f=c[m+24>>2]|0;a=c[m+12>>2]|0;do if((a|0)==(m|0)){b=m+16|0;d=b+4|0;a=c[d>>2]|0;if(!a){a=c[b>>2]|0;if(!a){n=0;break}}else b=d;while(1){d=a+20|0;e=c[d>>2]|0;if(e){a=e;b=d;continue}d=a+16|0;e=c[d>>2]|0;if(!e)break;else{a=e;b=d}}if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=0;n=a;break}}else{b=c[m+8>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();d=b+12|0;if((c[d>>2]|0)!=(m|0))fa();e=a+8|0;if((c[e>>2]|0)==(m|0)){c[d>>2]=a;c[e>>2]=b;n=a;break}else fa()}while(0);if(f){a=c[m+28>>2]|0;b=360+(a<<2)|0;if((m|0)==(c[b>>2]|0)){c[b>>2]=n;if(!n){c[15]=c[15]&~(1<<a);break}}else{if(f>>>0<(c[18]|0)>>>0)fa();a=f+16|0;if((c[a>>2]|0)==(m|0))c[a>>2]=n;else c[f+20>>2]=n;if(!n)break}d=c[18]|0;if(n>>>0<d>>>0)fa();c[n+24>>2]=f;a=m+16|0;b=c[a>>2]|0;do if(b)if(b>>>0<d>>>0)fa();else{c[n+16>>2]=b;c[b+24>>2]=n;break}while(0);a=c[a+4>>2]|0;if(a)if(a>>>0<(c[18]|0)>>>0)fa();else{c[n+20>>2]=a;c[a+24>>2]=n;break}}}else{b=c[m+8>>2]|0;d=c[m+12>>2]|0;a=96+(e<<1<<2)|0;if((b|0)!=(a|0)){if(b>>>0<(c[18]|0)>>>0)fa();if((c[b+12>>2]|0)!=(m|0))fa()}if((d|0)==(b|0)){c[14]=c[14]&~(1<<e);break}if((d|0)!=(a|0)){if(d>>>0<(c[18]|0)>>>0)fa();a=d+8|0;if((c[a>>2]|0)==(m|0))l=a;else fa()}else l=d+8|0;c[b+12>>2]=d;c[l>>2]=b}while(0);c[q+4>>2]=g|1;c[q+g>>2]=g;if((q|0)==(c[19]|0)){c[16]=g;return}}else{c[a>>2]=b&-2;c[q+4>>2]=g|1;c[q+g>>2]=g}a=g>>>3;if(g>>>0<256){d=96+(a<<1<<2)|0;b=c[14]|0;a=1<<a;if(b&a){a=d+8|0;b=c[a>>2]|0;if(b>>>0<(c[18]|0)>>>0)fa();else{o=a;p=b}}else{c[14]=b|a;o=d+8|0;p=d}c[o>>2]=q;c[p+12>>2]=q;c[q+8>>2]=p;c[q+12>>2]=d;return}a=g>>>8;if(a)if(g>>>0>16777215)d=31;else{o=(a+1048320|0)>>>16&8;p=a<<o;n=(p+520192|0)>>>16&4;p=p<<n;d=(p+245760|0)>>>16&2;d=14-(n|o|d)+(p<<d>>>15)|0;d=g>>>(d+7|0)&1|d<<1}else d=0;e=360+(d<<2)|0;c[q+28>>2]=d;c[q+20>>2]=0;c[q+16>>2]=0;a=c[15]|0;b=1<<d;do if(a&b){f=g<<((d|0)==31?0:25-(d>>>1)|0);a=c[e>>2]|0;while(1){if((c[a+4>>2]&-8|0)==(g|0)){d=a;e=130;break}b=a+16+(f>>>31<<2)|0;d=c[b>>2]|0;if(!d){e=127;break}else{f=f<<1;a=d}}if((e|0)==127)if(b>>>0<(c[18]|0)>>>0)fa();else{c[b>>2]=q;c[q+24>>2]=a;c[q+12>>2]=q;c[q+8>>2]=q;break}else if((e|0)==130){a=d+8|0;b=c[a>>2]|0;p=c[18]|0;if(b>>>0>=p>>>0&d>>>0>=p>>>0){c[b+12>>2]=q;c[a>>2]=q;c[q+8>>2]=b;c[q+12>>2]=d;c[q+24>>2]=0;break}else fa()}}else{c[15]=a|b;c[e>>2]=q;c[q+24>>2]=e;c[q+12>>2]=q;c[q+8>>2]=q}while(0);q=(c[22]|0)+-1|0;c[22]=q;if(!q)a=512;else return;while(1){a=c[a>>2]|0;if(!a)break;else a=a+8|0}c[22]=-1;return}function Ea(){}function Fa(b,d,e){b=b|0;d=d|0;e=e|0;var f=0,g=0,h=0,i=0;f=b+e|0;if((e|0)>=20){d=d&255;h=b&3;i=d|d<<8|d<<16|d<<24;g=f&~3;if(h){h=b+4-h|0;while((b|0)<(h|0)){a[b>>0]=d;b=b+1|0}}while((b|0)<(g|0)){c[b>>2]=i;b=b+4|0}}while((b|0)<(f|0)){a[b>>0]=d;b=b+1|0}return b-e|0}function Ga(b,d,e){b=b|0;d=d|0;e=e|0;var f=0;if((e|0)>=4096)return ja(b|0,d|0,e|0)|0;f=b|0;if((b&3)==(d&3)){while(b&3){if(!e)return f|0;a[b>>0]=a[d>>0]|0;b=b+1|0;d=d+1|0;e=e-1|0}while((e|0)>=4){c[b>>2]=c[d>>2];b=b+4|0;d=d+4|0;e=e-4|0}}while((e|0)>0){a[b>>0]=a[d>>0]|0;b=b+1|0;d=d+1|0;e=e-1|0}return f|0} // EMSCRIPTEN_END_FUNCS -return{_free:Aa,_memset:Ca,_malloc:za,_precalc:va,_dispose:wa,_memcpy:Da,_transform_radix2_precalc:xa,runPostSets:Ba,stackAlloc:ma,stackSave:na,stackRestore:oa,establishStackSpace:pa,setThrew:qa,setTempRet0:ta,getTempRet0:ua}}) +return{_malloc:Ca,_free:Da,_transform_radix2_precalc_f:Aa,_memset:Fa,_precalc_f:wa,_precalc:va,_dispose:xa,_memcpy:Ga,_transform_radix2_precalc:za,_dispose_f:ya,runPostSets:Ea,stackAlloc:ma,stackSave:na,stackRestore:oa,establishStackSpace:pa,setThrew:qa,setTempRet0:ta,getTempRet0:ua}}) // EMSCRIPTEN_END_ASM -(Module.asmGlobalArg,Module.asmLibraryArg,buffer);var _free=Module["_free"]=asm["_free"];var runPostSets=Module["runPostSets"]=asm["runPostSets"];var _memset=Module["_memset"]=asm["_memset"];var _malloc=Module["_malloc"]=asm["_malloc"];var _precalc=Module["_precalc"]=asm["_precalc"];var _dispose=Module["_dispose"]=asm["_dispose"];var _memcpy=Module["_memcpy"]=asm["_memcpy"];var _transform_radix2_precalc=Module["_transform_radix2_precalc"]=asm["_transform_radix2_precalc"];Runtime.stackAlloc=asm["stackAlloc"];Runtime.stackSave=asm["stackSave"];Runtime.stackRestore=asm["stackRestore"];Runtime.establishStackSpace=asm["establishStackSpace"];Runtime.setTempRet0=asm["setTempRet0"];Runtime.getTempRet0=asm["getTempRet0"];function ExitStatus(status){this.name="ExitStatus";this.message="Program terminated with exit("+status+")";this.status=status}ExitStatus.prototype=new Error;ExitStatus.prototype.constructor=ExitStatus;var initialStackTop;var preloadStartTime=null;var calledMain=false;dependenciesFulfilled=function runCaller(){if(!Module["calledRun"])run();if(!Module["calledRun"])dependenciesFulfilled=runCaller};Module["callMain"]=Module.callMain=function callMain(args){assert(runDependencies==0,"cannot call main when async dependencies remain! (listen on __ATMAIN__)");assert(__ATPRERUN__.length==0,"cannot call main when preRun functions remain to be called");args=args||[];ensureInitRuntime();var argc=args.length+1;function pad(){for(var i=0;i<4-1;i++){argv.push(0)}}var argv=[allocate(intArrayFromString(Module["thisProgram"]),"i8",ALLOC_NORMAL)];pad();for(var i=0;i<argc-1;i=i+1){argv.push(allocate(intArrayFromString(args[i]),"i8",ALLOC_NORMAL));pad()}argv.push(0);argv=allocate(argv,"i32",ALLOC_NORMAL);try{var ret=Module["_main"](argc,argv,0);exit(ret,true)}catch(e){if(e instanceof ExitStatus){return}else if(e=="SimulateInfiniteLoop"){Module["noExitRuntime"]=true;return}else{if(e&&typeof e==="object"&&e.stack)Module.printErr("exception thrown: "+[e,e.stack]);throw e}}finally{calledMain=true}};function run(args){args=args||Module["arguments"];if(preloadStartTime===null)preloadStartTime=Date.now();if(runDependencies>0){return}preRun();if(runDependencies>0)return;if(Module["calledRun"])return;function doRun(){if(Module["calledRun"])return;Module["calledRun"]=true;if(ABORT)return;ensureInitRuntime();preMain();if(Module["onRuntimeInitialized"])Module["onRuntimeInitialized"]();if(Module["_main"]&&shouldRunNow)Module["callMain"](args);postRun()}if(Module["setStatus"]){Module["setStatus"]("Running...");setTimeout((function(){setTimeout((function(){Module["setStatus"]("")}),1);doRun()}),1)}else{doRun()}}Module["run"]=Module.run=run;function exit(status,implicit){if(implicit&&Module["noExitRuntime"]){return}if(Module["noExitRuntime"]){}else{ABORT=true;EXITSTATUS=status;STACKTOP=initialStackTop;exitRuntime();if(Module["onExit"])Module["onExit"](status)}if(ENVIRONMENT_IS_NODE){process["stdout"]["once"]("drain",(function(){process["exit"](status)}));console.log(" ");setTimeout((function(){process["exit"](status)}),500)}else if(ENVIRONMENT_IS_SHELL&&typeof quit==="function"){quit(status)}throw new ExitStatus(status)}Module["exit"]=Module.exit=exit;var abortDecorators=[];function abort(what){if(what!==undefined){Module.print(what);Module.printErr(what);what=JSON.stringify(what)}else{what=""}ABORT=true;EXITSTATUS=1;var extra="\nIf this abort() is unexpected, build with -s ASSERTIONS=1 which can give more information.";var output="abort("+what+") at "+stackTrace()+extra;if(abortDecorators){abortDecorators.forEach((function(decorator){output=decorator(output,what)}))}throw output}Module["abort"]=Module.abort=abort;if(Module["preInit"]){if(typeof Module["preInit"]=="function")Module["preInit"]=[Module["preInit"]];while(Module["preInit"].length>0){Module["preInit"].pop()()}}var shouldRunNow=true;if(Module["noInitialRun"]){shouldRunNow=false}run() +(Module.asmGlobalArg,Module.asmLibraryArg,buffer);var _precalc_f=Module["_precalc_f"]=asm["_precalc_f"];var _free=Module["_free"]=asm["_free"];var runPostSets=Module["runPostSets"]=asm["runPostSets"];var _transform_radix2_precalc_f=Module["_transform_radix2_precalc_f"]=asm["_transform_radix2_precalc_f"];var _memset=Module["_memset"]=asm["_memset"];var _malloc=Module["_malloc"]=asm["_malloc"];var _precalc=Module["_precalc"]=asm["_precalc"];var _dispose=Module["_dispose"]=asm["_dispose"];var _memcpy=Module["_memcpy"]=asm["_memcpy"];var _transform_radix2_precalc=Module["_transform_radix2_precalc"]=asm["_transform_radix2_precalc"];var _dispose_f=Module["_dispose_f"]=asm["_dispose_f"];Runtime.stackAlloc=asm["stackAlloc"];Runtime.stackSave=asm["stackSave"];Runtime.stackRestore=asm["stackRestore"];Runtime.establishStackSpace=asm["establishStackSpace"];Runtime.setTempRet0=asm["setTempRet0"];Runtime.getTempRet0=asm["getTempRet0"];function ExitStatus(status){this.name="ExitStatus";this.message="Program terminated with exit("+status+")";this.status=status}ExitStatus.prototype=new Error;ExitStatus.prototype.constructor=ExitStatus;var initialStackTop;var preloadStartTime=null;var calledMain=false;dependenciesFulfilled=function runCaller(){if(!Module["calledRun"])run();if(!Module["calledRun"])dependenciesFulfilled=runCaller};Module["callMain"]=Module.callMain=function callMain(args){assert(runDependencies==0,"cannot call main when async dependencies remain! (listen on __ATMAIN__)");assert(__ATPRERUN__.length==0,"cannot call main when preRun functions remain to be called");args=args||[];ensureInitRuntime();var argc=args.length+1;function pad(){for(var i=0;i<4-1;i++){argv.push(0)}}var argv=[allocate(intArrayFromString(Module["thisProgram"]),"i8",ALLOC_NORMAL)];pad();for(var i=0;i<argc-1;i=i+1){argv.push(allocate(intArrayFromString(args[i]),"i8",ALLOC_NORMAL));pad()}argv.push(0);argv=allocate(argv,"i32",ALLOC_NORMAL);try{var ret=Module["_main"](argc,argv,0);exit(ret,true)}catch(e){if(e instanceof ExitStatus){return}else if(e=="SimulateInfiniteLoop"){Module["noExitRuntime"]=true;return}else{if(e&&typeof e==="object"&&e.stack)Module.printErr("exception thrown: "+[e,e.stack]);throw e}}finally{calledMain=true}};function run(args){args=args||Module["arguments"];if(preloadStartTime===null)preloadStartTime=Date.now();if(runDependencies>0){return}preRun();if(runDependencies>0)return;if(Module["calledRun"])return;function doRun(){if(Module["calledRun"])return;Module["calledRun"]=true;if(ABORT)return;ensureInitRuntime();preMain();if(Module["onRuntimeInitialized"])Module["onRuntimeInitialized"]();if(Module["_main"]&&shouldRunNow)Module["callMain"](args);postRun()}if(Module["setStatus"]){Module["setStatus"]("Running...");setTimeout((function(){setTimeout((function(){Module["setStatus"]("")}),1);doRun()}),1)}else{doRun()}}Module["run"]=Module.run=run;function exit(status,implicit){if(implicit&&Module["noExitRuntime"]){return}if(Module["noExitRuntime"]){}else{ABORT=true;EXITSTATUS=status;STACKTOP=initialStackTop;exitRuntime();if(Module["onExit"])Module["onExit"](status)}if(ENVIRONMENT_IS_NODE){process["stdout"]["once"]("drain",(function(){process["exit"](status)}));console.log(" ");setTimeout((function(){process["exit"](status)}),500)}else if(ENVIRONMENT_IS_SHELL&&typeof quit==="function"){quit(status)}throw new ExitStatus(status)}Module["exit"]=Module.exit=exit;var abortDecorators=[];function abort(what){if(what!==undefined){Module.print(what);Module.printErr(what);what=JSON.stringify(what)}else{what=""}ABORT=true;EXITSTATUS=1;var extra="\nIf this abort() is unexpected, build with -s ASSERTIONS=1 which can give more information.";var output="abort("+what+") at "+stackTrace()+extra;if(abortDecorators){abortDecorators.forEach((function(decorator){output=decorator(output,what)}))}throw output}Module["abort"]=Module.abort=abort;if(Module["preInit"]){if(typeof Module["preInit"]=="function")Module["preInit"]=[Module["preInit"]];while(Module["preInit"].length>0){Module["preInit"].pop()()}}var shouldRunNow=true;if(Module["noInitialRun"]){shouldRunNow=false}run()
--- a/fft/nayukic/fft.c Mon Nov 09 11:46:47 2015 +0000 +++ b/fft/nayukic/fft.c Mon Nov 09 12:22:00 2015 +0000 @@ -87,6 +87,43 @@ return tables; } +tables_f *precalc_f(size_t n) { + unsigned int levels; + // Compute levels = floor(log2(n)) + { + size_t temp = n; + levels = 0; + while (temp > 1) { + levels++; + temp >>= 1; + } + if (1u << levels != n) + return 0; // n is not a power of 2 + } + if (SIZE_MAX / sizeof(float) < n / 2) return 0; + tables_f *tables = malloc(sizeof(tables_f)); + if (!tables) return tables; + tables->levels = levels; + size_t size = (n / 2) * sizeof(float); + tables->cos = malloc(size); + if (!tables->cos) { + free(tables); + return 0; + } + tables->sin = malloc(size); + if (!tables->sin) { + free(tables->cos); + free(tables); + return 0; + } + int i; + for (i = 0; i < n / 2; i++) { + tables->cos[i] = cos(2 * M_PI * i / n); + tables->sin[i] = sin(2 * M_PI * i / n); + } + return tables; +} + void dispose(tables *tables) { if (!tables) return; free(tables->cos); @@ -94,6 +131,13 @@ free(tables); } +void dispose_f(tables_f *tables) { + if (!tables) return; + free(tables->cos); + free(tables->sin); + free(tables); +} + void transform_radix2_precalc(double real[], double imag[], int n, tables *tables) { double *cos_table, *sin_table; int size; @@ -137,6 +181,49 @@ } } +void transform_radix2_precalc_f(float real[], float imag[], int n, tables_f *tables) { + float *cos_table, *sin_table; + int size; + int i; + + // Trignometric tables + cos_table = tables->cos; + sin_table = tables->sin; + + // Bit-reversed addressing permutation + for (i = 0; i < n; i++) { + int j = reverse_bits(i, tables->levels); + if (j > i) { + float temp = real[i]; + real[i] = real[j]; + real[j] = temp; + temp = imag[i]; + imag[i] = imag[j]; + imag[j] = temp; + } + } + + // Cooley-Tukey decimation-in-time radix-2 FFT + for (size = 2; size <= n; size *= 2) { + int halfsize = size / 2; + int tablestep = n / size; + for (i = 0; i < n; i += size) { + int j; + int k; + for (j = i, k = 0; j < i + halfsize; j++, k += tablestep) { + float tpre = real[j+halfsize] * cos_table[k] + imag[j+halfsize] * sin_table[k]; + float tpim = -real[j+halfsize] * sin_table[k] + imag[j+halfsize] * cos_table[k]; + real[j + halfsize] = real[j] - tpre; + imag[j + halfsize] = imag[j] - tpim; + real[j] += tpre; + imag[j] += tpim; + } + } + if (size == n) // Prevent overflow in 'size *= 2' + break; + } +} + int transform_radix2(double real[], double imag[], size_t n) { // Variables int status = 0;
--- a/fft/nayukic/fft.h Mon Nov 09 11:46:47 2015 +0000 +++ b/fft/nayukic/fft.h Mon Nov 09 12:22:00 2015 +0000 @@ -43,6 +43,8 @@ */ int transform_radix2(double real[], double imag[], size_t n); +/* Test versions with precalculated structures -- this API is + absolutely not for production use! */ typedef struct { double *cos; double *sin; @@ -53,6 +55,16 @@ void dispose(tables *); void transform_radix2_precalc(double real[], double imag[], int n, tables *tables); +typedef struct { + float *cos; + float *sin; + int levels; +} tables_f; + +tables_f *precalc_f(size_t n); +void dispose_f(tables_f *); +void transform_radix2_precalc_f(float real[], float imag[], int n, tables_f *tables); + /* * Computes the discrete Fourier transform (DFT) of the given complex vector, storing the result back into the vector. * The vector can have any length. This requires the convolution function, which in turn requires the radix-2 FFT function.
--- a/fft/test.js Mon Nov 09 11:46:47 2015 +0000 +++ b/fft/test.js Mon Nov 09 12:22:00 2015 +0000 @@ -117,8 +117,8 @@ if (i == iterations) { middle = performance.now(); } - var real = inputReals(size); - var imag = zeroReals(size); + var real = inputReal64s(size); + var imag = zeroReal64s(size); fft.forward(real, imag); for (var j = 0; j < size; ++j) { total += Math.sqrt(real[j] * real[j] + imag[j] * imag[j]);