var v232 = 2n ** 32n;
function clz32(n) {
return Math.clz32(n | 0);
}
// https://stackoverflow.com/questions/61442006/whats-the-most-efficient-way-of-getting-position-of-least-significant-bit-of-a
function ctz32(n) {
n |= 0;
return n ? 31 - Math.clz32(n & -n) : 0;
}
function clz64(bn) {
let result = clz32(Number(bn / v232) | 0);
if (result === 32) {
result += clz32(Number(bn % v232) | 0);
}
return result;
}
function arrayBufferToBase64(arrayBuffer) {
return btoa(String.fromCharCode(...new Uint8Array(arrayBuffer)));
}
function base64ToArrayBuffer(base64) {
let s = atob(base64);
let arrayBuffer = new ArrayBuffer(s.length);
var bufferView = new Uint8Array(arrayBuffer);
for (let i = 0; i < s.length; i++) {
bufferView[i] = s.charCodeAt(i);
}
return arrayBuffer;
}
async function compile(fn, preCompiled) {
let wasmBuffer;
if (preCompiled) {
wasmBuffer = base64ToArrayBuffer(preCompiled);
} else {
let response = await fetch(fn);
wasmBuffer = await response.arrayBuffer();
console.log(arrayBufferToBase64(wasmBuffer));
}
return await WebAssembly.instantiate(wasmBuffer);
}
async function runTest() {
let wasm64v32 = await compile('./lz64v32.wasm', 'AGFzbQEAAAABBwFgAn9/AX8DAgEABwYBAmx6AAAKEAEOACABrUIghiAArXx5pwsAGQRuYW1lAQUBAAJsegILAQACAAJsbwECaGk=');
let wasm64 = await compile('./lz64.wasm', 'AGFzbQEAAAABBgFgAX4BfgMCAQAHCAEEbHo2NAAACgcBBQAgAHkLABgEbmFtZQEHAQAEbHo2NAIIAQABAAN2YWw=');
let v232 = 2n ** 32n;
let randomBigInts = new Array(10000000);
console.log(`Building ${randomBigInts.length.toLocaleString()} BigInts...\n\n`);
for (let i = 0; i < randomBigInts.length; i++) {
randomBigInts[i] = 2n ** BigInt(Math.round(Math.random() * 64));
}
console.log(`Math.clz32 MSB start check on ${randomBigInts.length.toLocaleString()} BigInts.`);
randomBigInts.forEach(v=>{
64 - clz64(v);
});
console.log('Done');
let v = randomBigInts[0];
console.log(`Math.clz32 test of msb ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${64 - clz64(v)}\n\n`);
console.log(`WASM MSB start check on ${randomBigInts.length.toLocaleString()} BigInts via WASM, splitting 64 bit BigInt into 2 x i32 parameters.`);
let lzf = wasm64v32.instance.exports.lz
randomBigInts.forEach(v=>{
64 - lzf(Number(v % v232), Number(v / v232));
});
console.log('Done');
console.log(`WASM test of leading zeros ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${64 - lzf(Number(v % v232), Number(v / v232))}\n\n`);
console.log(`WASM MSB start check on ${randomBigInts.length.toLocaleString()} BigInts via WASM using i64 parameter.`);
let lzf64 = wasm64.instance.exports.lz64
randomBigInts.forEach(v=>{
64n - lzf64(v);
});
console.log('Done');
console.log(`WASM test of leading zeros ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${64n - lzf64(v)}\n\n`);
console.log(`DeBruijn MSB start check on ${randomBigInts.length.toLocaleString()} BigInts via deBruijn.`);
randomBigInts.forEach(v=>{
msb(v);
});
console.log('Done');
console.log(`DeBruijn test of leading zeros ${('0'.repeat(64) + v.toString(2)).slice(-64)} is ${msb(v)}\n\n`);
}
const deBruijn = [0, 48, -1, -1, 31, -1, 15, 51, -1, 63, 5, -1, -1, -1, 19, -1, 23, 28, -1, -1, -1, 40, 36, 46, -1, 13, -1, -1, -1, 34, -1, 58, -1, 60, 2, 43, 55, -1, -1, -1, 50, 62, 4, -1, 18, 27, -1, 39, 45, -1, -1, 33, 57, -1, 1, 54, -1, 49, -1, 17, -1, -1, 32, -1, 53, -1, 16, -1, -1, 52, -1, -1, -1, 64, 6, 7, 8, -1, 9, -1, -1, -1, 20, 10, -1, -1, 24, -1, 29, -1, -1, 21, -1, 11, -1, -1, 41, -1, 25, 37, -1, 47, -1, 30, 14, -1, -1, -1, -1, 22, -1, -1, 35, 12, -1, -1, -1, 59, 42, -1, -1, 61, 3, 26, 38, 44, -1, 56];
const multiplicator = BigInt("0x6c04f118e9966f6b");
const b1 = BigInt(1)
, b2 = BigInt(2)
, b4 = BigInt(4)
, b8 = BigInt(8)
, b16 = BigInt(16)
, b32 = BigInt(32)
, b57 = BigInt(57);
function msb(v) {
v |= v >> b1;
v |= v >> b2;
v |= v >> b4;
v |= v >> b8;
v |= v >> b16;
v |= v >> b32;
return deBruijn[BigInt.asUintN(64, (BigInt.asUintN(64, (v * multiplicator))) >> b57)];
}
function lsb(v) {
v = -v | v;
return deBruijn[BigInt.asUintN(64, (BigInt.asUintN(64, (~(v) * multiplicator))) >> b57)];
}
runTest();
