Mercurial > hg > js-dsp-test
changeset 32:ebc87a62321d
Add Nayuki fft.c compiled to JS
| author | Chris Cannam |
|---|---|
| date | Mon, 09 Nov 2015 11:46:47 +0000 |
| parents | 59a1ee198dca |
| children | bbf5d4e825eb |
| files | fft/index.html fft/nayukic/FFT.js fft/nayukic/Makefile.emscripten fft/nayukic/NayukiCFFT.js fft/nayukic/fft.c fft/nayukic/fft.h fft/nayukic/ffttest.c fft/test.js |
| diffstat | 8 files changed, 778 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- a/fft/index.html Mon Nov 09 11:46:35 2015 +0000 +++ b/fft/index.html Mon Nov 09 11:46:47 2015 +0000 @@ -12,6 +12,8 @@ <script src="nayuki/fft.js"></script> <script src="nayuki-obj/fft.js"></script> + <script src="nayukic/NayukiCFFT.js"></script> + <script src="nayukic/FFT.js"></script> <script src="fft.js/lib/complex.js"></script> <script src="jsfft/lib/complex_array.js"></script> <script src="jsfft/lib/fft.js"></script> @@ -38,6 +40,8 @@ <td>Nayuki</td><td id="nayuki-result"></td><td id="nayuki-1"></td><td id="nayuki-2"></td><td id="nayuki-itr"></td> </tr><tr> <td>Nayuki (obj)</td><td id="nayukiobj-result"></td><td id="nayukiobj-1"></td><td id="nayukiobj-2"></td><td id="nayukiobj-itr"></td> + </tr><tr> + <td>Nayuki (C)</td><td id="nayukic-result"></td><td id="nayukic-1"></td><td id="nayukic-2"></td><td id="nayukic-itr"></td> </tr><tr> <td>KissFFT</td><td id="kissfft-result"></td><td id="kissfft-1"></td><td id="kissfft-2"></td><td id="kissfft-itr"></td> </tr><tr> @@ -56,6 +60,7 @@ <ul> <li><b>Nayuki</b>: in-place single-precision complex-complex. Around 7kb.</li> <li><b>Nayuki (obj)</b>: Nayuki with the sin/cos tables pre-calculated on object construction. Around 4kb.</li> + <li><b>Nayuki (C)</b>: Nayuki C implementation compiled with Emscripten. Does not have pre-calculated sin/cos tables.</li> <li><b>Nockert</b>: double-precision real-complex. Around 25kb.</li> <li><b>Dntj</b>: double-precision complex-complex. Forward transform is scaled and I've scaled it back again here, which may
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fft/nayukic/FFT.js Mon Nov 09 11:46:47 2015 +0000 @@ -0,0 +1,39 @@ +"use strict"; + +var nayukiCModule = NayukiCModule({}); + +var nc_precalc = nayukiCModule.cwrap( + 'precalc', 'number', ['number'] +); + +var nc_dispose = nayukiCModule.cwrap( + 'dispose', 'void', ['number'] +); + +var nc_transform_radix2_precalc = nayukiCModule.cwrap( + 'transform_radix2_precalc', 'void', ['number', 'number', 'number', 'number'] +); + +function FFTNayukiC(n) { + + this.n = n; + this.rptr = nayukiCModule._malloc(n*8 + n*8); + this.iptr = this.rptr + n*8; + this.rarr = new Float64Array(nayukiCModule.HEAPU8.buffer, this.rptr, n); + this.iarr = new Float64Array(nayukiCModule.HEAPU8.buffer, this.iptr, n); + this.tables = nc_precalc(n); + + this.forward = function(real, imag) { + this.rarr.set(real); + this.iarr.set(imag); + nc_transform_radix2_precalc(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(this.tables); + } +} +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fft/nayukic/Makefile.emscripten Mon Nov 09 11:46:47 2015 +0000 @@ -0,0 +1,15 @@ + +NayukiCFFT.js: fft.c fft.h + emcc -O3 -I. \ + --memory-init-file 0 \ + -s NO_FILESYSTEM=1 \ + -s NO_BROWSER=1 \ + -s MODULARIZE=1 \ + -s EXPORT_NAME="'NayukiCModule'" \ + -s EXPORTED_FUNCTIONS="['_transform_radix2_precalc','_precalc','_dispose']" \ + -o NayukiCFFT.js \ + fft.c + +clean: + rm -f NayukiCFFT.js +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fft/nayukic/NayukiCFFT.js Mon Nov 09 11:46:47 2015 +0000 @@ -0,0 +1,22 @@ +var NayukiCModule = function(Module) { + Module = Module || {}; + +var Module;if(!Module)Module=(typeof NayukiCModule!=="undefined"?NayukiCModule:null)||{};var moduleOverrides={};for(var key in Module){if(Module.hasOwnProperty(key)){moduleOverrides[key]=Module[key]}}var ENVIRONMENT_IS_WEB=typeof window==="object";var ENVIRONMENT_IS_WORKER=typeof importScripts==="function";var ENVIRONMENT_IS_NODE=typeof process==="object"&&typeof require==="function"&&!ENVIRONMENT_IS_WEB&&!ENVIRONMENT_IS_WORKER;var ENVIRONMENT_IS_SHELL=!ENVIRONMENT_IS_WEB&&!ENVIRONMENT_IS_NODE&&!ENVIRONMENT_IS_WORKER;if(ENVIRONMENT_IS_NODE){if(!Module["print"])Module["print"]=function print(x){process["stdout"].write(x+"\n")};if(!Module["printErr"])Module["printErr"]=function printErr(x){process["stderr"].write(x+"\n")};var nodeFS=require("fs");var nodePath=require("path");Module["read"]=function read(filename,binary){filename=nodePath["normalize"](filename);var ret=nodeFS["readFileSync"](filename);if(!ret&&filename!=nodePath["resolve"](filename)){filename=path.join(__dirname,"..","src",filename);ret=nodeFS["readFileSync"](filename)}if(ret&&!binary)ret=ret.toString();return ret};Module["readBinary"]=function readBinary(filename){var ret=Module["read"](filename,true);if(!ret.buffer){ret=new Uint8Array(ret)}assert(ret.buffer);return ret};Module["load"]=function load(f){globalEval(read(f))};if(!Module["thisProgram"]){if(process["argv"].length>1){Module["thisProgram"]=process["argv"][1].replace(/\\/g,"/")}else{Module["thisProgram"]="unknown-program"}}Module["arguments"]=process["argv"].slice(2);if(typeof module!=="undefined"){module["exports"]=Module}process["on"]("uncaughtException",(function(ex){if(!(ex instanceof ExitStatus)){throw ex}}));Module["inspect"]=(function(){return"[Emscripten Module object]"})}else if(ENVIRONMENT_IS_SHELL){if(!Module["print"])Module["print"]=print;if(typeof printErr!="undefined")Module["printErr"]=printErr;if(typeof read!="undefined"){Module["read"]=read}else{Module["read"]=function read(){throw"no read() available (jsc?)"}}Module["readBinary"]=function readBinary(f){if(typeof readbuffer==="function"){return new Uint8Array(readbuffer(f))}var data=read(f,"binary");assert(typeof data==="object");return data};if(typeof scriptArgs!="undefined"){Module["arguments"]=scriptArgs}else if(typeof arguments!="undefined"){Module["arguments"]=arguments}}else if(ENVIRONMENT_IS_WEB||ENVIRONMENT_IS_WORKER){Module["read"]=function read(url){var xhr=new XMLHttpRequest;xhr.open("GET",url,false);xhr.send(null);return xhr.responseText};if(typeof arguments!="undefined"){Module["arguments"]=arguments}if(typeof console!=="undefined"){if(!Module["print"])Module["print"]=function print(x){console.log(x)};if(!Module["printErr"])Module["printErr"]=function printErr(x){console.log(x)}}else{var TRY_USE_DUMP=false;if(!Module["print"])Module["print"]=TRY_USE_DUMP&&typeof dump!=="undefined"?(function(x){dump(x)}):(function(x){})}if(ENVIRONMENT_IS_WORKER){Module["load"]=importScripts}if(typeof Module["setWindowTitle"]==="undefined"){Module["setWindowTitle"]=(function(title){document.title=title})}}else{throw"Unknown runtime environment. Where are we?"}function globalEval(x){eval.call(null,x)}if(!Module["load"]&&Module["read"]){Module["load"]=function load(f){globalEval(Module["read"](f))}}if(!Module["print"]){Module["print"]=(function(){})}if(!Module["printErr"]){Module["printErr"]=Module["print"]}if(!Module["arguments"]){Module["arguments"]=[]}if(!Module["thisProgram"]){Module["thisProgram"]="./this.program"}Module.print=Module["print"];Module.printErr=Module["printErr"];Module["preRun"]=[];Module["postRun"]=[];for(var key in moduleOverrides){if(moduleOverrides.hasOwnProperty(key)){Module[key]=moduleOverrides[key]}}var Runtime={setTempRet0:(function(value){tempRet0=value}),getTempRet0:(function(){return tempRet0}),stackSave:(function(){return STACKTOP}),stackRestore:(function(stackTop){STACKTOP=stackTop}),getNativeTypeSize:(function(type){switch(type){case"i1":case"i8":return 1;case"i16":return 2;case"i32":return 4;case"i64":return 8;case"float":return 4;case"double":return 8;default:{if(type[type.length-1]==="*"){return Runtime.QUANTUM_SIZE}else if(type[0]==="i"){var bits=parseInt(type.substr(1));assert(bits%8===0);return bits/8}else{return 0}}}}),getNativeFieldSize:(function(type){return Math.max(Runtime.getNativeTypeSize(type),Runtime.QUANTUM_SIZE)}),STACK_ALIGN:16,prepVararg:(function(ptr,type){if(type==="double"||type==="i64"){if(ptr&7){assert((ptr&7)===4);ptr+=4}}else{assert((ptr&3)===0)}return ptr}),getAlignSize:(function(type,size,vararg){if(!vararg&&(type=="i64"||type=="double"))return 8;if(!type)return Math.min(size,8);return Math.min(size||(type?Runtime.getNativeFieldSize(type):0),Runtime.QUANTUM_SIZE)}),dynCall:(function(sig,ptr,args){if(args&&args.length){if(!args.splice)args=Array.prototype.slice.call(args);args.splice(0,0,ptr);return Module["dynCall_"+sig].apply(null,args)}else{return Module["dynCall_"+sig].call(null,ptr)}}),functionPointers:[],addFunction:(function(func){for(var i=0;i<Runtime.functionPointers.length;i++){if(!Runtime.functionPointers[i]){Runtime.functionPointers[i]=func;return 2*(1+i)}}throw"Finished up all reserved function pointers. Use a higher value for RESERVED_FUNCTION_POINTERS."}),removeFunction:(function(index){Runtime.functionPointers[(index-2)/2]=null}),warnOnce:(function(text){if(!Runtime.warnOnce.shown)Runtime.warnOnce.shown={};if(!Runtime.warnOnce.shown[text]){Runtime.warnOnce.shown[text]=1;Module.printErr(text)}}),funcWrappers:{},getFuncWrapper:(function(func,sig){assert(sig);if(!Runtime.funcWrappers[sig]){Runtime.funcWrappers[sig]={}}var sigCache=Runtime.funcWrappers[sig];if(!sigCache[func]){sigCache[func]=function dynCall_wrapper(){return Runtime.dynCall(sig,func,arguments)}}return sigCache[func]}),getCompilerSetting:(function(name){throw"You must build with -s RETAIN_COMPILER_SETTINGS=1 for Runtime.getCompilerSetting or emscripten_get_compiler_setting to work"}),stackAlloc:(function(size){var ret=STACKTOP;STACKTOP=STACKTOP+size|0;STACKTOP=STACKTOP+15&-16;return ret}),staticAlloc:(function(size){var ret=STATICTOP;STATICTOP=STATICTOP+size|0;STATICTOP=STATICTOP+15&-16;return ret}),dynamicAlloc:(function(size){var ret=DYNAMICTOP;DYNAMICTOP=DYNAMICTOP+size|0;DYNAMICTOP=DYNAMICTOP+15&-16;if(DYNAMICTOP>=TOTAL_MEMORY){var success=enlargeMemory();if(!success){DYNAMICTOP=ret;return 0}}return ret}),alignMemory:(function(size,quantum){var ret=size=Math.ceil(size/(quantum?quantum:16))*(quantum?quantum:16);return ret}),makeBigInt:(function(low,high,unsigned){var ret=unsigned?+(low>>>0)+ +(high>>>0)*+4294967296:+(low>>>0)+ +(high|0)*+4294967296;return ret}),GLOBAL_BASE:8,QUANTUM_SIZE:4,__dummy__:0};Module["Runtime"]=Runtime;var __THREW__=0;var ABORT=false;var EXITSTATUS=0;var undef=0;var tempValue,tempInt,tempBigInt,tempInt2,tempBigInt2,tempPair,tempBigIntI,tempBigIntR,tempBigIntS,tempBigIntP,tempBigIntD,tempDouble,tempFloat;var tempI64,tempI64b;var tempRet0,tempRet1,tempRet2,tempRet3,tempRet4,tempRet5,tempRet6,tempRet7,tempRet8,tempRet9;function assert(condition,text){if(!condition){abort("Assertion failed: "+text)}}var globalScope=this;function getCFunc(ident){var func=Module["_"+ident];if(!func){try{func=eval("_"+ident)}catch(e){}}assert(func,"Cannot call unknown function "+ident+" (perhaps LLVM optimizations or closure removed it?)");return func}var cwrap,ccall;((function(){var JSfuncs={"stackSave":(function(){Runtime.stackSave()}),"stackRestore":(function(){Runtime.stackRestore()}),"arrayToC":(function(arr){var ret=Runtime.stackAlloc(arr.length);writeArrayToMemory(arr,ret);return ret}),"stringToC":(function(str){var ret=0;if(str!==null&&str!==undefined&&str!==0){ret=Runtime.stackAlloc((str.length<<2)+1);writeStringToMemory(str,ret)}return ret})};var toC={"string":JSfuncs["stringToC"],"array":JSfuncs["arrayToC"]};ccall=function ccallFunc(ident,returnType,argTypes,args,opts){var func=getCFunc(ident);var cArgs=[];var stack=0;if(args){for(var i=0;i<args.length;i++){var converter=toC[argTypes[i]];if(converter){if(stack===0)stack=Runtime.stackSave();cArgs[i]=converter(args[i])}else{cArgs[i]=args[i]}}}var ret=func.apply(null,cArgs);if(returnType==="string")ret=Pointer_stringify(ret);if(stack!==0){if(opts&&opts.async){EmterpreterAsync.asyncFinalizers.push((function(){Runtime.stackRestore(stack)}));return}Runtime.stackRestore(stack)}return ret};var sourceRegex=/^function\s*\(([^)]*)\)\s*{\s*([^*]*?)[\s;]*(?:return\s*(.*?)[;\s]*)?}$/;function parseJSFunc(jsfunc){var parsed=jsfunc.toString().match(sourceRegex).slice(1);return{arguments:parsed[0],body:parsed[1],returnValue:parsed[2]}}var JSsource={};for(var fun in JSfuncs){if(JSfuncs.hasOwnProperty(fun)){JSsource[fun]=parseJSFunc(JSfuncs[fun])}}cwrap=function cwrap(ident,returnType,argTypes){argTypes=argTypes||[];var cfunc=getCFunc(ident);var numericArgs=argTypes.every((function(type){return type==="number"}));var numericRet=returnType!=="string";if(numericRet&&numericArgs){return cfunc}var argNames=argTypes.map((function(x,i){return"$"+i}));var funcstr="(function("+argNames.join(",")+") {";var nargs=argTypes.length;if(!numericArgs){funcstr+="var stack = "+JSsource["stackSave"].body+";";for(var i=0;i<nargs;i++){var arg=argNames[i],type=argTypes[i];if(type==="number")continue;var convertCode=JSsource[type+"ToC"];funcstr+="var "+convertCode.arguments+" = "+arg+";";funcstr+=convertCode.body+";";funcstr+=arg+"="+convertCode.returnValue+";"}}var cfuncname=parseJSFunc((function(){return cfunc})).returnValue;funcstr+="var ret = "+cfuncname+"("+argNames.join(",")+");";if(!numericRet){var strgfy=parseJSFunc((function(){return Pointer_stringify})).returnValue;funcstr+="ret = "+strgfy+"(ret);"}if(!numericArgs){funcstr+=JSsource["stackRestore"].body.replace("()","(stack)")+";"}funcstr+="return ret})";return eval(funcstr)}}))();Module["ccall"]=ccall;Module["cwrap"]=cwrap;function setValue(ptr,value,type,noSafe){type=type||"i8";if(type.charAt(type.length-1)==="*")type="i32";switch(type){case"i1":HEAP8[ptr>>0]=value;break;case"i8":HEAP8[ptr>>0]=value;break;case"i16":HEAP16[ptr>>1]=value;break;case"i32":HEAP32[ptr>>2]=value;break;case"i64":tempI64=[value>>>0,(tempDouble=value,+Math_abs(tempDouble)>=+1?tempDouble>+0?(Math_min(+Math_floor(tempDouble/+4294967296),+4294967295)|0)>>>0:~~+Math_ceil((tempDouble- +(~~tempDouble>>>0))/+4294967296)>>>0:0)],HEAP32[ptr>>2]=tempI64[0],HEAP32[ptr+4>>2]=tempI64[1];break;case"float":HEAPF32[ptr>>2]=value;break;case"double":HEAPF64[ptr>>3]=value;break;default:abort("invalid type for setValue: "+type)}}Module["setValue"]=setValue;function getValue(ptr,type,noSafe){type=type||"i8";if(type.charAt(type.length-1)==="*")type="i32";switch(type){case"i1":return HEAP8[ptr>>0];case"i8":return HEAP8[ptr>>0];case"i16":return HEAP16[ptr>>1];case"i32":return HEAP32[ptr>>2];case"i64":return HEAP32[ptr>>2];case"float":return HEAPF32[ptr>>2];case"double":return HEAPF64[ptr>>3];default:abort("invalid type for setValue: "+type)}return null}Module["getValue"]=getValue;var ALLOC_NORMAL=0;var ALLOC_STACK=1;var ALLOC_STATIC=2;var ALLOC_DYNAMIC=3;var ALLOC_NONE=4;Module["ALLOC_NORMAL"]=ALLOC_NORMAL;Module["ALLOC_STACK"]=ALLOC_STACK;Module["ALLOC_STATIC"]=ALLOC_STATIC;Module["ALLOC_DYNAMIC"]=ALLOC_DYNAMIC;Module["ALLOC_NONE"]=ALLOC_NONE;function allocate(slab,types,allocator,ptr){var zeroinit,size;if(typeof slab==="number"){zeroinit=true;size=slab}else{zeroinit=false;size=slab.length}var singleType=typeof types==="string"?types:null;var ret;if(allocator==ALLOC_NONE){ret=ptr}else{ret=[_malloc,Runtime.stackAlloc,Runtime.staticAlloc,Runtime.dynamicAlloc][allocator===undefined?ALLOC_STATIC:allocator](Math.max(size,singleType?1:types.length))}if(zeroinit){var ptr=ret,stop;assert((ret&3)==0);stop=ret+(size&~3);for(;ptr<stop;ptr+=4){HEAP32[ptr>>2]=0}stop=ret+size;while(ptr<stop){HEAP8[ptr++>>0]=0}return ret}if(singleType==="i8"){if(slab.subarray||slab.slice){HEAPU8.set(slab,ret)}else{HEAPU8.set(new Uint8Array(slab),ret)}return ret}var i=0,type,typeSize,previousType;while(i<size){var curr=slab[i];if(typeof curr==="function"){curr=Runtime.getFunctionIndex(curr)}type=singleType||types[i];if(type===0){i++;continue}if(type=="i64")type="i32";setValue(ret+i,curr,type);if(previousType!==type){typeSize=Runtime.getNativeTypeSize(type);previousType=type}i+=typeSize}return ret}Module["allocate"]=allocate;function getMemory(size){if(!staticSealed)return Runtime.staticAlloc(size);if(typeof _sbrk!=="undefined"&&!_sbrk.called||!runtimeInitialized)return Runtime.dynamicAlloc(size);return _malloc(size)}Module["getMemory"]=getMemory;function Pointer_stringify(ptr,length){if(length===0||!ptr)return"";var hasUtf=0;var t;var i=0;while(1){t=HEAPU8[ptr+i>>0];hasUtf|=t;if(t==0&&!length)break;i++;if(length&&i==length)break}if(!length)length=i;var ret="";if(hasUtf<128){var MAX_CHUNK=1024;var curr;while(length>0){curr=String.fromCharCode.apply(String,HEAPU8.subarray(ptr,ptr+Math.min(length,MAX_CHUNK)));ret=ret?ret+curr:curr;ptr+=MAX_CHUNK;length-=MAX_CHUNK}return ret}return Module["UTF8ToString"](ptr)}Module["Pointer_stringify"]=Pointer_stringify;function AsciiToString(ptr){var str="";while(1){var ch=HEAP8[ptr++>>0];if(!ch)return str;str+=String.fromCharCode(ch)}}Module["AsciiToString"]=AsciiToString;function stringToAscii(str,outPtr){return writeAsciiToMemory(str,outPtr,false)}Module["stringToAscii"]=stringToAscii;function UTF8ArrayToString(u8Array,idx){var u0,u1,u2,u3,u4,u5;var str="";while(1){u0=u8Array[idx++];if(!u0)return str;if(!(u0&128)){str+=String.fromCharCode(u0);continue}u1=u8Array[idx++]&63;if((u0&224)==192){str+=String.fromCharCode((u0&31)<<6|u1);continue}u2=u8Array[idx++]&63;if((u0&240)==224){u0=(u0&15)<<12|u1<<6|u2}else{u3=u8Array[idx++]&63;if((u0&248)==240){u0=(u0&7)<<18|u1<<12|u2<<6|u3}else{u4=u8Array[idx++]&63;if((u0&252)==248){u0=(u0&3)<<24|u1<<18|u2<<12|u3<<6|u4}else{u5=u8Array[idx++]&63;u0=(u0&1)<<30|u1<<24|u2<<18|u3<<12|u4<<6|u5}}}if(u0<65536){str+=String.fromCharCode(u0)}else{var ch=u0-65536;str+=String.fromCharCode(55296|ch>>10,56320|ch&1023)}}}Module["UTF8ArrayToString"]=UTF8ArrayToString;function UTF8ToString(ptr){return UTF8ArrayToString(HEAPU8,ptr)}Module["UTF8ToString"]=UTF8ToString;function stringToUTF8Array(str,outU8Array,outIdx,maxBytesToWrite){if(!(maxBytesToWrite>0))return 0;var startIdx=outIdx;var endIdx=outIdx+maxBytesToWrite-1;for(var i=0;i<str.length;++i){var u=str.charCodeAt(i);if(u>=55296&&u<=57343)u=65536+((u&1023)<<10)|str.charCodeAt(++i)&1023;if(u<=127){if(outIdx>=endIdx)break;outU8Array[outIdx++]=u}else if(u<=2047){if(outIdx+1>=endIdx)break;outU8Array[outIdx++]=192|u>>6;outU8Array[outIdx++]=128|u&63}else if(u<=65535){if(outIdx+2>=endIdx)break;outU8Array[outIdx++]=224|u>>12;outU8Array[outIdx++]=128|u>>6&63;outU8Array[outIdx++]=128|u&63}else if(u<=2097151){if(outIdx+3>=endIdx)break;outU8Array[outIdx++]=240|u>>18;outU8Array[outIdx++]=128|u>>12&63;outU8Array[outIdx++]=128|u>>6&63;outU8Array[outIdx++]=128|u&63}else if(u<=67108863){if(outIdx+4>=endIdx)break;outU8Array[outIdx++]=248|u>>24;outU8Array[outIdx++]=128|u>>18&63;outU8Array[outIdx++]=128|u>>12&63;outU8Array[outIdx++]=128|u>>6&63;outU8Array[outIdx++]=128|u&63}else{if(outIdx+5>=endIdx)break;outU8Array[outIdx++]=252|u>>30;outU8Array[outIdx++]=128|u>>24&63;outU8Array[outIdx++]=128|u>>18&63;outU8Array[outIdx++]=128|u>>12&63;outU8Array[outIdx++]=128|u>>6&63;outU8Array[outIdx++]=128|u&63}}outU8Array[outIdx]=0;return outIdx-startIdx}Module["stringToUTF8Array"]=stringToUTF8Array;function stringToUTF8(str,outPtr,maxBytesToWrite){return stringToUTF8Array(str,HEAPU8,outPtr,maxBytesToWrite)}Module["stringToUTF8"]=stringToUTF8;function lengthBytesUTF8(str){var len=0;for(var i=0;i<str.length;++i){var u=str.charCodeAt(i);if(u>=55296&&u<=57343)u=65536+((u&1023)<<10)|str.charCodeAt(++i)&1023;if(u<=127){++len}else if(u<=2047){len+=2}else if(u<=65535){len+=3}else if(u<=2097151){len+=4}else if(u<=67108863){len+=5}else{len+=6}}return len}Module["lengthBytesUTF8"]=lengthBytesUTF8;function UTF16ToString(ptr){var i=0;var str="";while(1){var codeUnit=HEAP16[ptr+i*2>>1];if(codeUnit==0)return str;++i;str+=String.fromCharCode(codeUnit)}}Module["UTF16ToString"]=UTF16ToString;function stringToUTF16(str,outPtr,maxBytesToWrite){if(maxBytesToWrite===undefined){maxBytesToWrite=2147483647}if(maxBytesToWrite<2)return 0;maxBytesToWrite-=2;var startPtr=outPtr;var numCharsToWrite=maxBytesToWrite<str.length*2?maxBytesToWrite/2:str.length;for(var i=0;i<numCharsToWrite;++i){var codeUnit=str.charCodeAt(i);HEAP16[outPtr>>1]=codeUnit;outPtr+=2}HEAP16[outPtr>>1]=0;return outPtr-startPtr}Module["stringToUTF16"]=stringToUTF16;function lengthBytesUTF16(str){return str.length*2}Module["lengthBytesUTF16"]=lengthBytesUTF16;function UTF32ToString(ptr){var i=0;var str="";while(1){var utf32=HEAP32[ptr+i*4>>2];if(utf32==0)return str;++i;if(utf32>=65536){var ch=utf32-65536;str+=String.fromCharCode(55296|ch>>10,56320|ch&1023)}else{str+=String.fromCharCode(utf32)}}}Module["UTF32ToString"]=UTF32ToString;function stringToUTF32(str,outPtr,maxBytesToWrite){if(maxBytesToWrite===undefined){maxBytesToWrite=2147483647}if(maxBytesToWrite<4)return 0;var startPtr=outPtr;var endPtr=startPtr+maxBytesToWrite-4;for(var i=0;i<str.length;++i){var codeUnit=str.charCodeAt(i);if(codeUnit>=55296&&codeUnit<=57343){var trailSurrogate=str.charCodeAt(++i);codeUnit=65536+((codeUnit&1023)<<10)|trailSurrogate&1023}HEAP32[outPtr>>2]=codeUnit;outPtr+=4;if(outPtr+4>endPtr)break}HEAP32[outPtr>>2]=0;return outPtr-startPtr}Module["stringToUTF32"]=stringToUTF32;function lengthBytesUTF32(str){var len=0;for(var i=0;i<str.length;++i){var codeUnit=str.charCodeAt(i);if(codeUnit>=55296&&codeUnit<=57343)++i;len+=4}return len}Module["lengthBytesUTF32"]=lengthBytesUTF32;function demangle(func){var hasLibcxxabi=!!Module["___cxa_demangle"];if(hasLibcxxabi){try{var buf=_malloc(func.length);writeStringToMemory(func.substr(1),buf);var status=_malloc(4);var ret=Module["___cxa_demangle"](buf,0,0,status);if(getValue(status,"i32")===0&&ret){return Pointer_stringify(ret)}}catch(e){}finally{if(buf)_free(buf);if(status)_free(status);if(ret)_free(ret)}}var i=3;var basicTypes={"v":"void","b":"bool","c":"char","s":"short","i":"int","l":"long","f":"float","d":"double","w":"wchar_t","a":"signed char","h":"unsigned char","t":"unsigned short","j":"unsigned int","m":"unsigned long","x":"long long","y":"unsigned long long","z":"..."};var subs=[];var first=true;function dump(x){if(x)Module.print(x);Module.print(func);var pre="";for(var a=0;a<i;a++)pre+=" ";Module.print(pre+"^")}function parseNested(){i++;if(func[i]==="K")i++;var parts=[];while(func[i]!=="E"){if(func[i]==="S"){i++;var next=func.indexOf("_",i);var num=func.substring(i,next)||0;parts.push(subs[num]||"?");i=next+1;continue}if(func[i]==="C"){parts.push(parts[parts.length-1]);i+=2;continue}var size=parseInt(func.substr(i));var pre=size.toString().length;if(!size||!pre){i--;break}var curr=func.substr(i+pre,size);parts.push(curr);subs.push(curr);i+=pre+size}i++;return parts}function parse(rawList,limit,allowVoid){limit=limit||Infinity;var ret="",list=[];function flushList(){return"("+list.join(", ")+")"}var name;if(func[i]==="N"){name=parseNested().join("::");limit--;if(limit===0)return rawList?[name]:name}else{if(func[i]==="K"||first&&func[i]==="L")i++;var size=parseInt(func.substr(i));if(size){var pre=size.toString().length;name=func.substr(i+pre,size);i+=pre+size}}first=false;if(func[i]==="I"){i++;var iList=parse(true);var iRet=parse(true,1,true);ret+=iRet[0]+" "+name+"<"+iList.join(", ")+">"}else{ret=name}paramLoop:while(i<func.length&&limit-->0){var c=func[i++];if(c in basicTypes){list.push(basicTypes[c])}else{switch(c){case"P":list.push(parse(true,1,true)[0]+"*");break;case"R":list.push(parse(true,1,true)[0]+"&");break;case"L":{i++;var end=func.indexOf("E",i);var size=end-i;list.push(func.substr(i,size));i+=size+2;break};case"A":{var size=parseInt(func.substr(i));i+=size.toString().length;if(func[i]!=="_")throw"?";i++;list.push(parse(true,1,true)[0]+" ["+size+"]");break};case"E":break paramLoop;default:ret+="?"+c;break paramLoop}}}if(!allowVoid&&list.length===1&&list[0]==="void")list=[];if(rawList){if(ret){list.push(ret+"?")}return list}else{return ret+flushList()}}var parsed=func;try{if(func=="Object._main"||func=="_main"){return"main()"}if(typeof func==="number")func=Pointer_stringify(func);if(func[0]!=="_")return func;if(func[1]!=="_")return func;if(func[2]!=="Z")return func;switch(func[3]){case"n":return"operator new()";case"d":return"operator delete()"}parsed=parse()}catch(e){parsed+="?"}if(parsed.indexOf("?")>=0&&!hasLibcxxabi){Runtime.warnOnce("warning: a problem occurred in builtin C++ name demangling; build with -s DEMANGLE_SUPPORT=1 to link in libcxxabi demangling")}return parsed}function demangleAll(text){return text.replace(/__Z[\w\d_]+/g,(function(x){var y=demangle(x);return x===y?x:x+" ["+y+"]"}))}function jsStackTrace(){var err=new Error;if(!err.stack){try{throw new Error(0)}catch(e){err=e}if(!err.stack){return"(no stack trace available)"}}return err.stack.toString()}function stackTrace(){return demangleAll(jsStackTrace())}Module["stackTrace"]=stackTrace;var PAGE_SIZE=4096;function alignMemoryPage(x){if(x%4096>0){x+=4096-x%4096}return x}var HEAP;var HEAP8,HEAPU8,HEAP16,HEAPU16,HEAP32,HEAPU32,HEAPF32,HEAPF64;var STATIC_BASE=0,STATICTOP=0,staticSealed=false;var STACK_BASE=0,STACKTOP=0,STACK_MAX=0;var DYNAMIC_BASE=0,DYNAMICTOP=0;function abortOnCannotGrowMemory(){abort("Cannot enlarge memory arrays. Either (1) compile with -s TOTAL_MEMORY=X with X higher than the current value "+TOTAL_MEMORY+", (2) compile with -s ALLOW_MEMORY_GROWTH=1 which adjusts the size at runtime but prevents some optimizations, (3) set Module.TOTAL_MEMORY to a higher value before the program runs, or if you want malloc to return NULL (0) instead of this abort, compile with -s ABORTING_MALLOC=0 ")}function enlargeMemory(){abortOnCannotGrowMemory()}var TOTAL_STACK=Module["TOTAL_STACK"]||5242880;var TOTAL_MEMORY=Module["TOTAL_MEMORY"]||16777216;var totalMemory=64*1024;while(totalMemory<TOTAL_MEMORY||totalMemory<2*TOTAL_STACK){if(totalMemory<16*1024*1024){totalMemory*=2}else{totalMemory+=16*1024*1024}}if(totalMemory!==TOTAL_MEMORY){TOTAL_MEMORY=totalMemory}assert(typeof Int32Array!=="undefined"&&typeof Float64Array!=="undefined"&&!!(new Int32Array(1))["subarray"]&&!!(new Int32Array(1))["set"],"JS engine does not provide full typed array support");var buffer;buffer=new ArrayBuffer(TOTAL_MEMORY);HEAP8=new Int8Array(buffer);HEAP16=new Int16Array(buffer);HEAP32=new Int32Array(buffer);HEAPU8=new Uint8Array(buffer);HEAPU16=new Uint16Array(buffer);HEAPU32=new Uint32Array(buffer);HEAPF32=new Float32Array(buffer);HEAPF64=new Float64Array(buffer);HEAP32[0]=255;assert(HEAPU8[0]===255&&HEAPU8[3]===0,"Typed arrays 2 must be run on a little-endian system");Module["HEAP"]=HEAP;Module["buffer"]=buffer;Module["HEAP8"]=HEAP8;Module["HEAP16"]=HEAP16;Module["HEAP32"]=HEAP32;Module["HEAPU8"]=HEAPU8;Module["HEAPU16"]=HEAPU16;Module["HEAPU32"]=HEAPU32;Module["HEAPF32"]=HEAPF32;Module["HEAPF64"]=HEAPF64;function callRuntimeCallbacks(callbacks){while(callbacks.length>0){var callback=callbacks.shift();if(typeof callback=="function"){callback();continue}var func=callback.func;if(typeof func==="number"){if(callback.arg===undefined){Runtime.dynCall("v",func)}else{Runtime.dynCall("vi",func,[callback.arg])}}else{func(callback.arg===undefined?null:callback.arg)}}}var __ATPRERUN__=[];var __ATINIT__=[];var __ATMAIN__=[];var __ATEXIT__=[];var __ATPOSTRUN__=[];var runtimeInitialized=false;var runtimeExited=false;function preRun(){if(Module["preRun"]){if(typeof Module["preRun"]=="function")Module["preRun"]=[Module["preRun"]];while(Module["preRun"].length){addOnPreRun(Module["preRun"].shift())}}callRuntimeCallbacks(__ATPRERUN__)}function ensureInitRuntime(){if(runtimeInitialized)return;runtimeInitialized=true;callRuntimeCallbacks(__ATINIT__)}function preMain(){callRuntimeCallbacks(__ATMAIN__)}function exitRuntime(){callRuntimeCallbacks(__ATEXIT__);runtimeExited=true}function postRun(){if(Module["postRun"]){if(typeof Module["postRun"]=="function")Module["postRun"]=[Module["postRun"]];while(Module["postRun"].length){addOnPostRun(Module["postRun"].shift())}}callRuntimeCallbacks(__ATPOSTRUN__)}function addOnPreRun(cb){__ATPRERUN__.unshift(cb)}Module["addOnPreRun"]=addOnPreRun;function addOnInit(cb){__ATINIT__.unshift(cb)}Module["addOnInit"]=addOnInit;function addOnPreMain(cb){__ATMAIN__.unshift(cb)}Module["addOnPreMain"]=addOnPreMain;function addOnExit(cb){__ATEXIT__.unshift(cb)}Module["addOnExit"]=addOnExit;function addOnPostRun(cb){__ATPOSTRUN__.unshift(cb)}Module["addOnPostRun"]=addOnPostRun;function intArrayFromString(stringy,dontAddNull,length){var len=length>0?length:lengthBytesUTF8(stringy)+1;var u8array=new Array(len);var numBytesWritten=stringToUTF8Array(stringy,u8array,0,u8array.length);if(dontAddNull)u8array.length=numBytesWritten;return u8array}Module["intArrayFromString"]=intArrayFromString;function intArrayToString(array){var ret=[];for(var i=0;i<array.length;i++){var chr=array[i];if(chr>255){chr&=255}ret.push(String.fromCharCode(chr))}return ret.join("")}Module["intArrayToString"]=intArrayToString;function writeStringToMemory(string,buffer,dontAddNull){var array=intArrayFromString(string,dontAddNull);var i=0;while(i<array.length){var chr=array[i];HEAP8[buffer+i>>0]=chr;i=i+1}}Module["writeStringToMemory"]=writeStringToMemory;function writeArrayToMemory(array,buffer){for(var i=0;i<array.length;i++){HEAP8[buffer++>>0]=array[i]}}Module["writeArrayToMemory"]=writeArrayToMemory;function writeAsciiToMemory(str,buffer,dontAddNull){for(var i=0;i<str.length;++i){HEAP8[buffer++>>0]=str.charCodeAt(i)}if(!dontAddNull)HEAP8[buffer>>0]=0}Module["writeAsciiToMemory"]=writeAsciiToMemory;function unSign(value,bits,ignore){if(value>=0){return value}return bits<=32?2*Math.abs(1<<bits-1)+value:Math.pow(2,bits)+value}function reSign(value,bits,ignore){if(value<=0){return value}var half=bits<=32?Math.abs(1<<bits-1):Math.pow(2,bits-1);if(value>=half&&(bits<=32||value>half)){value=-2*half+value}return value}if(!Math["imul"]||Math["imul"](4294967295,5)!==-5)Math["imul"]=function imul(a,b){var ah=a>>>16;var al=a&65535;var bh=b>>>16;var bl=b&65535;return al*bl+(ah*bl+al*bh<<16)|0};Math.imul=Math["imul"];if(!Math["clz32"])Math["clz32"]=(function(x){x=x>>>0;for(var i=0;i<32;i++){if(x&1<<31-i)return i}return 32});Math.clz32=Math["clz32"];var Math_abs=Math.abs;var Math_cos=Math.cos;var Math_sin=Math.sin;var Math_tan=Math.tan;var Math_acos=Math.acos;var Math_asin=Math.asin;var Math_atan=Math.atan;var Math_atan2=Math.atan2;var Math_exp=Math.exp;var Math_log=Math.log;var Math_sqrt=Math.sqrt;var Math_ceil=Math.ceil;var Math_floor=Math.floor;var Math_pow=Math.pow;var Math_imul=Math.imul;var Math_fround=Math.fround;var Math_min=Math.min;var Math_clz32=Math.clz32;var runDependencies=0;var runDependencyWatcher=null;var dependenciesFulfilled=null;function getUniqueRunDependency(id){return id}function addRunDependency(id){runDependencies++;if(Module["monitorRunDependencies"]){Module["monitorRunDependencies"](runDependencies)}}Module["addRunDependency"]=addRunDependency;function removeRunDependency(id){runDependencies--;if(Module["monitorRunDependencies"]){Module["monitorRunDependencies"](runDependencies)}if(runDependencies==0){if(runDependencyWatcher!==null){clearInterval(runDependencyWatcher);runDependencyWatcher=null}if(dependenciesFulfilled){var callback=dependenciesFulfilled;dependenciesFulfilled=null;callback()}}}Module["removeRunDependency"]=removeRunDependency;Module["preloadedImages"]={};Module["preloadedAudios"]={};var memoryInitializer=null;var ASM_CONSTS=[];STATIC_BASE=8;STATICTOP=STATIC_BASE+560;__ATINIT__.push();allocate([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],"i8",ALLOC_NONE,Runtime.GLOBAL_BASE);var tempDoublePtr=Runtime.alignMemory(allocate(12,"i8",ALLOC_STATIC),8);assert(tempDoublePtr%8==0);function copyTempFloat(ptr){HEAP8[tempDoublePtr]=HEAP8[ptr];HEAP8[tempDoublePtr+1]=HEAP8[ptr+1];HEAP8[tempDoublePtr+2]=HEAP8[ptr+2];HEAP8[tempDoublePtr+3]=HEAP8[ptr+3]}function copyTempDouble(ptr){HEAP8[tempDoublePtr]=HEAP8[ptr];HEAP8[tempDoublePtr+1]=HEAP8[ptr+1];HEAP8[tempDoublePtr+2]=HEAP8[ptr+2];HEAP8[tempDoublePtr+3]=HEAP8[ptr+3];HEAP8[tempDoublePtr+4]=HEAP8[ptr+4];HEAP8[tempDoublePtr+5]=HEAP8[ptr+5];HEAP8[tempDoublePtr+6]=HEAP8[ptr+6];HEAP8[tempDoublePtr+7]=HEAP8[ptr+7]}var _cos=Math_cos;function _sbrk(bytes){var self=_sbrk;if(!self.called){DYNAMICTOP=alignMemoryPage(DYNAMICTOP);self.called=true;assert(Runtime.dynamicAlloc);self.alloc=Runtime.dynamicAlloc;Runtime.dynamicAlloc=(function(){abort("cannot dynamically allocate, sbrk now has control")})}var ret=DYNAMICTOP;if(bytes!=0){var success=self.alloc(bytes);if(!success)return-1>>>0}return ret}function ___setErrNo(value){if(Module["___errno_location"])HEAP32[Module["___errno_location"]()>>2]=value;return value}var ERRNO_CODES={EPERM:1,ENOENT:2,ESRCH:3,EINTR:4,EIO:5,ENXIO:6,E2BIG:7,ENOEXEC:8,EBADF:9,ECHILD:10,EAGAIN:11,EWOULDBLOCK:11,ENOMEM:12,EACCES:13,EFAULT:14,ENOTBLK:15,EBUSY:16,EEXIST:17,EXDEV:18,ENODEV:19,ENOTDIR:20,EISDIR:21,EINVAL:22,ENFILE:23,EMFILE:24,ENOTTY:25,ETXTBSY:26,EFBIG:27,ENOSPC:28,ESPIPE:29,EROFS:30,EMLINK:31,EPIPE:32,EDOM:33,ERANGE:34,ENOMSG:42,EIDRM:43,ECHRNG:44,EL2NSYNC:45,EL3HLT:46,EL3RST:47,ELNRNG:48,EUNATCH:49,ENOCSI:50,EL2HLT:51,EDEADLK:35,ENOLCK:37,EBADE:52,EBADR:53,EXFULL:54,ENOANO:55,EBADRQC:56,EBADSLT:57,EDEADLOCK:35,EBFONT:59,ENOSTR:60,ENODATA:61,ETIME:62,ENOSR:63,ENONET:64,ENOPKG:65,EREMOTE:66,ENOLINK:67,EADV:68,ESRMNT:69,ECOMM:70,EPROTO:71,EMULTIHOP:72,EDOTDOT:73,EBADMSG:74,ENOTUNIQ:76,EBADFD:77,EREMCHG:78,ELIBACC:79,ELIBBAD:80,ELIBSCN:81,ELIBMAX:82,ELIBEXEC:83,ENOSYS:38,ENOTEMPTY:39,ENAMETOOLONG:36,ELOOP:40,EOPNOTSUPP:95,EPFNOSUPPORT:96,ECONNRESET:104,ENOBUFS:105,EAFNOSUPPORT:97,EPROTOTYPE:91,ENOTSOCK:88,ENOPROTOOPT:92,ESHUTDOWN:108,ECONNREFUSED:111,EADDRINUSE:98,ECONNABORTED:103,ENETUNREACH:101,ENETDOWN:100,ETIMEDOUT:110,EHOSTDOWN:112,EHOSTUNREACH:113,EINPROGRESS:115,EALREADY:114,EDESTADDRREQ:89,EMSGSIZE:90,EPROTONOSUPPORT:93,ESOCKTNOSUPPORT:94,EADDRNOTAVAIL:99,ENETRESET:102,EISCONN:106,ENOTCONN:107,ETOOMANYREFS:109,EUSERS:87,EDQUOT:122,ESTALE:116,ENOTSUP:95,ENOMEDIUM:123,EILSEQ:84,EOVERFLOW:75,ECANCELED:125,ENOTRECOVERABLE:131,EOWNERDEAD:130,ESTRPIPE:86};function _sysconf(name){switch(name){case 30:return PAGE_SIZE;case 85:return totalMemory/PAGE_SIZE;case 132:case 133:case 12:case 137:case 138:case 15:case 235:case 16:case 17:case 18:case 19:case 20:case 149:case 13:case 10:case 236:case 153:case 9:case 21:case 22:case 159:case 154:case 14:case 77:case 78:case 139:case 80:case 81:case 82:case 68:case 67:case 164:case 11:case 29:case 47:case 48:case 95:case 52:case 51:case 46:return 200809;case 79:return 0;case 27:case 246:case 127:case 128:case 23:case 24:case 160:case 161:case 181:case 182:case 242:case 183:case 184:case 243:case 244:case 245:case 165:case 178:case 179:case 49:case 50:case 168:case 169:case 175:case 170:case 171:case 172:case 97:case 76:case 32:case 173:case 35:return-1;case 176:case 177:case 7:case 155:case 8:case 157:case 125:case 126:case 92:case 93:case 129:case 130:case 131:case 94:case 91:return 1;case 74:case 60:case 69:case 70:case 4:return 1024;case 31:case 42:case 72:return 32;case 87:case 26:case 33:return 2147483647;case 34:case 1:return 47839;case 38:case 36:return 99;case 43:case 37:return 2048;case 0:return 2097152;case 3:return 65536;case 28:return 32768;case 44:return 32767;case 75:return 16384;case 39:return 1e3;case 89:return 700;case 71:return 256;case 40:return 255;case 2:return 100;case 180:return 64;case 25:return 20;case 5:return 16;case 6:return 6;case 73:return 4;case 84:{if(typeof navigator==="object")return navigator["hardwareConcurrency"]||1;return 1}}___setErrNo(ERRNO_CODES.EINVAL);return-1}Module["_memset"]=_memset;function _emscripten_memcpy_big(dest,src,num){HEAPU8.set(HEAPU8.subarray(src,src+num),dest);return dest}Module["_memcpy"]=_memcpy;function _abort(){Module["abort"]()}function _time(ptr){var ret=Date.now()/1e3|0;if(ptr){HEAP32[ptr>>2]=ret}return ret}function _pthread_self(){return 0}var _sin=Math_sin;STACK_BASE=STACKTOP=Runtime.alignMemory(STATICTOP);staticSealed=true;STACK_MAX=STACK_BASE+TOTAL_STACK;DYNAMIC_BASE=DYNAMICTOP=Runtime.alignMemory(STACK_MAX);assert(DYNAMIC_BASE<TOTAL_MEMORY,"TOTAL_MEMORY not big enough for stack");Module.asmGlobalArg={"Math":Math,"Int8Array":Int8Array,"Int16Array":Int16Array,"Int32Array":Int32Array,"Uint8Array":Uint8Array,"Uint16Array":Uint16Array,"Uint32Array":Uint32Array,"Float32Array":Float32Array,"Float64Array":Float64Array,"NaN":NaN,"Infinity":Infinity};Module.asmLibraryArg={"abort":abort,"assert":assert,"_sin":_sin,"_cos":_cos,"_pthread_self":_pthread_self,"_abort":_abort,"___setErrNo":___setErrNo,"_sbrk":_sbrk,"_time":_time,"_emscripten_memcpy_big":_emscripten_memcpy_big,"_sysconf":_sysconf,"STACKTOP":STACKTOP,"STACK_MAX":STACK_MAX,"tempDoublePtr":tempDoublePtr,"ABORT":ABORT};// EMSCRIPTEN_START_ASM +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} + +// 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}}) + + +// 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() + + + + + + return Module; +};
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fft/nayukic/fft.c Mon Nov 09 11:46:47 2015 +0000 @@ -0,0 +1,374 @@ +/* + * Free FFT and convolution (C) + * + * Copyright (c) 2014 Project Nayuki + * http://www.nayuki.io/page/free-small-fft-in-multiple-languages + * + * (MIT License) + * Permission is hereby granted, free of charge, to any person obtaining a copy of + * this software and associated documentation files (the "Software"), to deal in + * the Software without restriction, including without limitation the rights to + * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of + * the Software, and to permit persons to whom the Software is furnished to do so, + * subject to the following conditions: + * - The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * - The Software is provided "as is", without warranty of any kind, express or + * implied, including but not limited to the warranties of merchantability, + * fitness for a particular purpose and noninfringement. In no event shall the + * authors or copyright holders be liable for any claim, damages or other + * liability, whether in an action of contract, tort or otherwise, arising from, + * out of or in connection with the Software or the use or other dealings in the + * Software. + */ + +#include <math.h> +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include "fft.h" + + +// Private function prototypes +static size_t reverse_bits(size_t x, unsigned int n); +static void *memdup(const void *src, size_t n); + +#define SIZE_MAX ((size_t)-1) + + +int transform(double real[], double imag[], size_t n) { + if (n == 0) + return 1; + else if ((n & (n - 1)) == 0) // Is power of 2 + return transform_radix2(real, imag, n); + else // More complicated algorithm for arbitrary sizes + return transform_bluestein(real, imag, n); +} + + +int inverse_transform(double real[], double imag[], size_t n) { + return transform(imag, real, n); +} + +tables *precalc(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(double) < n / 2) return 0; + tables *tables = malloc(sizeof(tables)); + if (!tables) return tables; + tables->levels = levels; + size_t size = (n / 2) * sizeof(double); + 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); + free(tables->sin); + free(tables); +} + +void transform_radix2_precalc(double real[], double imag[], int n, tables *tables) { + double *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) { + double 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) { + double tpre = real[j+halfsize] * cos_table[k] + imag[j+halfsize] * sin_table[k]; + double 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; + unsigned int levels; + double *cos_table, *sin_table; + size_t size; + size_t i; + + // 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 + } + + // Trignometric tables + if (SIZE_MAX / sizeof(double) < n / 2) + return 0; + size = (n / 2) * sizeof(double); + cos_table = malloc(size); + sin_table = malloc(size); + if (cos_table == NULL || sin_table == NULL) + goto cleanup; + for (i = 0; i < n / 2; i++) { + cos_table[i] = cos(2 * M_PI * i / n); + sin_table[i] = sin(2 * M_PI * i / n); + } + + // Bit-reversed addressing permutation + for (i = 0; i < n; i++) { + size_t j = reverse_bits(i, levels); + if (j > i) { + double 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) { + size_t halfsize = size / 2; + size_t tablestep = n / size; + for (i = 0; i < n; i += size) { + size_t j; + size_t k; + for (j = i, k = 0; j < i + halfsize; j++, k += tablestep) { + double tpre = real[j+halfsize] * cos_table[k] + imag[j+halfsize] * sin_table[k]; + double 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; + } + status = 1; + +cleanup: + free(sin_table); + free(cos_table); + return status; +} + + +int transform_bluestein(double real[], double imag[], size_t n) { + // Variables + int status = 0; + double *cos_table, *sin_table; + double *areal, *aimag; + double *breal, *bimag; + double *creal, *cimag; + size_t m; + size_t size_n, size_m; + size_t i; + + // Find a power-of-2 convolution length m such that m >= n * 2 + 1 + { + size_t target; + if (n > (SIZE_MAX - 1) / 2) + return 0; + target = n * 2 + 1; + for (m = 1; m < target; m *= 2) { + if (SIZE_MAX / 2 < m) + return 0; + } + } + + // Allocate memory + if (SIZE_MAX / sizeof(double) < n || SIZE_MAX / sizeof(double) < m) + return 0; + size_n = n * sizeof(double); + size_m = m * sizeof(double); + cos_table = malloc(size_n); + sin_table = malloc(size_n); + areal = calloc(m, sizeof(double)); + aimag = calloc(m, sizeof(double)); + breal = calloc(m, sizeof(double)); + bimag = calloc(m, sizeof(double)); + creal = malloc(size_m); + cimag = malloc(size_m); + if (cos_table == NULL || sin_table == NULL + || areal == NULL || aimag == NULL + || breal == NULL || bimag == NULL + || creal == NULL || cimag == NULL) + goto cleanup; + + // Trignometric tables + for (i = 0; i < n; i++) { + double temp = M_PI * (size_t)((unsigned long long)i * i % ((unsigned long long)n * 2)) / n; + // Less accurate version if long long is unavailable: double temp = M_PI * i * i / n; + cos_table[i] = cos(temp); + sin_table[i] = sin(temp); + } + + // Temporary vectors and preprocessing + for (i = 0; i < n; i++) { + areal[i] = real[i] * cos_table[i] + imag[i] * sin_table[i]; + aimag[i] = -real[i] * sin_table[i] + imag[i] * cos_table[i]; + } + breal[0] = cos_table[0]; + bimag[0] = sin_table[0]; + for (i = 1; i < n; i++) { + breal[i] = breal[m - i] = cos_table[i]; + bimag[i] = bimag[m - i] = sin_table[i]; + } + + // Convolution + if (!convolve_complex(areal, aimag, breal, bimag, creal, cimag, m)) + goto cleanup; + + // Postprocessing + for (i = 0; i < n; i++) { + real[i] = creal[i] * cos_table[i] + cimag[i] * sin_table[i]; + imag[i] = -creal[i] * sin_table[i] + cimag[i] * cos_table[i]; + } + status = 1; + + // Deallocation +cleanup: + free(cimag); + free(creal); + free(bimag); + free(breal); + free(aimag); + free(areal); + free(sin_table); + free(cos_table); + return status; +} + + +int convolve_real(const double x[], const double y[], double out[], size_t n) { + double *ximag, *yimag, *zimag; + int status = 0; + ximag = calloc(n, sizeof(double)); + yimag = calloc(n, sizeof(double)); + zimag = calloc(n, sizeof(double)); + if (ximag == NULL || yimag == NULL || zimag == NULL) + goto cleanup; + + status = convolve_complex(x, ximag, y, yimag, out, zimag, n); +cleanup: + free(zimag); + free(yimag); + free(ximag); + return status; +} + + +int convolve_complex(const double xreal[], const double ximag[], const double yreal[], const double yimag[], double outreal[], double outimag[], size_t n) { + int status = 0; + size_t size; + size_t i; + double *xr, *xi, *yr, *yi; + if (SIZE_MAX / sizeof(double) < n) + return 0; + size = n * sizeof(double); + xr = memdup(xreal, size); + xi = memdup(ximag, size); + yr = memdup(yreal, size); + yi = memdup(yimag, size); + if (xr == NULL || xi == NULL || yr == NULL || yi == NULL) + goto cleanup; + + if (!transform(xr, xi, n)) + goto cleanup; + if (!transform(yr, yi, n)) + goto cleanup; + for (i = 0; i < n; i++) { + double temp = xr[i] * yr[i] - xi[i] * yi[i]; + xi[i] = xi[i] * yr[i] + xr[i] * yi[i]; + xr[i] = temp; + } + if (!inverse_transform(xr, xi, n)) + goto cleanup; + for (i = 0; i < n; i++) { // Scaling (because this FFT implementation omits it) + outreal[i] = xr[i] / n; + outimag[i] = xi[i] / n; + } + status = 1; + +cleanup: + free(yi); + free(yr); + free(xi); + free(xr); + return status; +} + + +static size_t reverse_bits(size_t x, unsigned int n) { + size_t result = 0; + unsigned int i; + for (i = 0; i < n; i++, x >>= 1) + result = (result << 1) | (x & 1); + return result; +} + + +static void *memdup(const void *src, size_t n) { + void *dest = malloc(n); + if (dest != NULL) + memcpy(dest, src, n); + return dest; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fft/nayukic/fft.h Mon Nov 09 11:46:47 2015 +0000 @@ -0,0 +1,74 @@ +/* + * Free FFT and convolution (C) + * + * Copyright (c) 2014 Project Nayuki + * http://www.nayuki.io/page/free-small-fft-in-multiple-languages + * + * (MIT License) + * Permission is hereby granted, free of charge, to any person obtaining a copy of + * this software and associated documentation files (the "Software"), to deal in + * the Software without restriction, including without limitation the rights to + * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of + * the Software, and to permit persons to whom the Software is furnished to do so, + * subject to the following conditions: + * - The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * - The Software is provided "as is", without warranty of any kind, express or + * implied, including but not limited to the warranties of merchantability, + * fitness for a particular purpose and noninfringement. In no event shall the + * authors or copyright holders be liable for any claim, damages or other + * liability, whether in an action of contract, tort or otherwise, arising from, + * out of or in connection with the Software or the use or other dealings in the + * Software. + */ + + +/* + * 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 is a wrapper function. Returns 1 (true) if successful, 0 (false) otherwise (out of memory). + */ +int transform(double real[], double imag[], size_t n); + +/* + * Computes the inverse discrete Fourier transform (IDFT) of the given complex vector, storing the result back into the vector. + * The vector can have any length. This is a wrapper function. This transform does not perform scaling, so the inverse is not a true inverse. + * Returns 1 (true) if successful, 0 (false) otherwise (out of memory). + */ +int inverse_transform(double real[], double imag[], size_t n); + +/* + * Computes the discrete Fourier transform (DFT) of the given complex vector, storing the result back into the vector. + * The vector's length must be a power of 2. Uses the Cooley-Tukey decimation-in-time radix-2 algorithm. + * Returns 1 (true) if successful, 0 (false) otherwise (n is not a power of 2, or out of memory). + */ +int transform_radix2(double real[], double imag[], size_t n); + +typedef struct { + double *cos; + double *sin; + int levels; +} tables; + +tables *precalc(size_t n); +void dispose(tables *); +void transform_radix2_precalc(double real[], double imag[], int n, tables *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. + * Uses Bluestein's chirp z-transform algorithm. Returns 1 (true) if successful, 0 (false) otherwise (out of memory). + */ +int transform_bluestein(double real[], double imag[], size_t n); + +/* + * Computes the circular convolution of the given real vectors. Each vector's length must be the same. + * Returns 1 (true) if successful, 0 (false) otherwise (out of memory). + */ +int convolve_real(const double x[], const double y[], double out[], size_t n); + +/* + * Computes the circular convolution of the given complex vectors. Each vector's length must be the same. + * Returns 1 (true) if successful, 0 (false) otherwise (out of memory). + */ +int convolve_complex(const double xreal[], const double ximag[], const double yreal[], const double yimag[], double outreal[], double outimag[], size_t n); +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fft/nayukic/ffttest.c Mon Nov 09 11:46:47 2015 +0000 @@ -0,0 +1,218 @@ +/* + * FFT and convolution test (C) + * + * Copyright (c) 2014 Project Nayuki + * http://www.nayuki.io/page/free-small-fft-in-multiple-languages + * + * (MIT License) + * Permission is hereby granted, free of charge, to any person obtaining a copy of + * this software and associated documentation files (the "Software"), to deal in + * the Software without restriction, including without limitation the rights to + * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of + * the Software, and to permit persons to whom the Software is furnished to do so, + * subject to the following conditions: + * - The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * - The Software is provided "as is", without warranty of any kind, express or + * implied, including but not limited to the warranties of merchantability, + * fitness for a particular purpose and noninfringement. In no event shall the + * authors or copyright holders be liable for any claim, damages or other + * liability, whether in an action of contract, tort or otherwise, arising from, + * out of or in connection with the Software or the use or other dealings in the + * Software. + */ + +#include <math.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include "fft.h" + + +// Private function prototypes +static void test_fft(int n); +static void test_convolution(int n); +static void naive_dft(const double *inreal, const double *inimag, double *outreal, double *outimag, int inverse, int n); +static void naive_convolve(const double *xreal, const double *ximag, const double *yreal, const double *yimag, double *outreal, double *outimag, int n); +static double log10_rms_err(const double *xreal, const double *ximag, const double *yreal, const double *yimag, int n); +static double *random_reals(int n); +static void *memdup(const void *src, size_t n); + +static double max_log_error = -INFINITY; + + +/* Main and test functions */ + +int main(int argc, char **argv) { + int i; + int prev; + srand(time(NULL)); + + // Test power-of-2 size FFTs + for (i = 0; i <= 12; i++) + test_fft(1 << i); + + // Test small size FFTs + for (i = 0; i < 30; i++) + test_fft(i); + + // Test diverse size FFTs + prev = 0; + for (i = 0; i <= 100; i++) { + int n = (int)lround(pow(1500, i / 100.0)); + if (n > prev) { + test_fft(n); + prev = n; + } + } + + // Test power-of-2 size convolutions + for (i = 0; i <= 12; i++) + test_convolution(1 << i); + + // Test diverse size convolutions + prev = 0; + for (i = 0; i <= 100; i++) { + int n = (int)lround(pow(1500, i / 100.0)); + if (n > prev) { + test_convolution(n); + prev = n; + } + } + + printf("\n"); + printf("Max log err = %.1f\n", max_log_error); + printf("Test %s\n", max_log_error < -10 ? "passed" : "failed"); + return 0; +} + + +static void test_fft(int n) { + double *inputreal, *inputimag; + double *refoutreal, *refoutimag; + double *actualoutreal, *actualoutimag; + + inputreal = random_reals(n); + inputimag = random_reals(n); + + refoutreal = malloc(n * sizeof(double)); + refoutimag = malloc(n * sizeof(double)); + naive_dft(inputreal, inputimag, refoutreal, refoutimag, 0, n); + + actualoutreal = memdup(inputreal, n * sizeof(double)); + actualoutimag = memdup(inputimag, n * sizeof(double)); + transform(actualoutreal, actualoutimag, n); + + printf("fftsize=%4d logerr=%5.1f\n", n, log10_rms_err(refoutreal, refoutimag, actualoutreal, actualoutimag, n)); + + free(inputreal); + free(inputimag); + free(refoutreal); + free(refoutimag); + free(actualoutreal); + free(actualoutimag); +} + + +static void test_convolution(int n) { + double *input0real, *input0imag; + double *input1real, *input1imag; + double *refoutreal, *refoutimag; + double *actualoutreal, *actualoutimag; + + input0real = random_reals(n); + input0imag = random_reals(n); + input1real = random_reals(n); + input1imag = random_reals(n); + + refoutreal = malloc(n * sizeof(double)); + refoutimag = malloc(n * sizeof(double)); + naive_convolve(input0real, input0imag, input1real, input1imag, refoutreal, refoutimag, n); + + actualoutreal = malloc(n * sizeof(double)); + actualoutimag = malloc(n * sizeof(double)); + convolve_complex(input0real, input0imag, input1real, input1imag, actualoutreal, actualoutimag, n); + + printf("convsize=%4d logerr=%5.1f\n", n, log10_rms_err(refoutreal, refoutimag, actualoutreal, actualoutimag, n)); + + free(input0real); + free(input0imag); + free(input1real); + free(input1imag); + free(refoutreal); + free(refoutimag); + free(actualoutreal); + free(actualoutimag); +} + + +/* Naive reference computation functions */ + +static void naive_dft(const double *inreal, const double *inimag, double *outreal, double *outimag, int inverse, int n) { + double coef = (inverse ? 2 : -2) * M_PI; + int k; + for (k = 0; k < n; k++) { // For each output element + double sumreal = 0; + double sumimag = 0; + int t; + for (t = 0; t < n; t++) { // For each input element + double angle = coef * ((long long)t * k % n) / n; + sumreal += inreal[t]*cos(angle) - inimag[t]*sin(angle); + sumimag += inreal[t]*sin(angle) + inimag[t]*cos(angle); + } + outreal[k] = sumreal; + outimag[k] = sumimag; + } +} + + +static void naive_convolve(const double *xreal, const double *ximag, const double *yreal, const double *yimag, double *outreal, double *outimag, int n) { + int i; + for (i = 0; i < n; i++) { + double sumreal = 0; + double sumimag = 0; + int j; + for (j = 0; j < n; j++) { + int k = (i - j + n) % n; + sumreal += xreal[k] * yreal[j] - ximag[k] * yimag[j]; + sumimag += xreal[k] * yimag[j] + ximag[k] * yreal[j]; + } + outreal[i] = sumreal; + outimag[i] = sumimag; + } +} + + +/* Utility functions */ + +static double log10_rms_err(const double *xreal, const double *ximag, const double *yreal, const double *yimag, int n) { + double err = 0; + int i; + for (i = 0; i < n; i++) + err += (xreal[i] - yreal[i]) * (xreal[i] - yreal[i]) + (ximag[i] - yimag[i]) * (ximag[i] - yimag[i]); + + err /= n > 0 ? n : 1; + err = sqrt(err); // Now this is a root mean square (RMS) error + err = err > 0 ? log10(err) : -99.0; + if (err > max_log_error) + max_log_error = err; + return err; +} + + +static double *random_reals(int n) { + double *result = malloc(n * sizeof(double)); + int i; + for (i = 0; i < n; i++) + result[i] = (rand() / (RAND_MAX + 1.0)) * 2 - 1; + return result; +} + + +static void *memdup(const void *src, size_t n) { + void *dest = malloc(n); + if (dest != NULL) + memcpy(dest, src, n); + return dest; +}
--- a/fft/test.js Mon Nov 09 11:46:35 2015 +0000 +++ b/fft/test.js Mon Nov 09 11:46:47 2015 +0000 @@ -103,6 +103,35 @@ report("nayukiobj", start, middle, end, total); } +function testNayukiC(size) { + + var fft = new FFTNayukiC(size); + + var start = performance.now(); + var middle = start; + var end = start; + + total = 0.0; + + for (var i = 0; i < 2*iterations; ++i) { + if (i == iterations) { + middle = performance.now(); + } + var real = inputReals(size); + var imag = zeroReals(size); + fft.forward(real, imag); + for (var j = 0; j < size; ++j) { + total += Math.sqrt(real[j] * real[j] + imag[j] * imag[j]); + } + } + + var end = performance.now(); + + fft.dispose(); + + report("nayukic", start, middle, end, total); +} + function testNockert(size) { var fft = new FFT.complex(size, false); @@ -252,7 +281,8 @@ } var sizes = [ 512, 2048 ]; -var tests = [ testNayuki, testNayukiObj, testKissFFT, testCross, testFFTW, testNockert, testDntj ]; +var tests = [ testNayuki, testNayukiObj, testNayukiC, testKissFFT, + testCross, testFFTW, testNockert, testDntj ]; var nextTest = 0; var nextSize = 0; var interval;