Tinkering with code and algorithms for fun
Public
Edited
Dec 11, 2022
6 stars
// Note: this function coverts the phase-
// encoded bits to a string of 1 and 0
// charactes, which works for demonstration
//purposes but obviously is rather inefficient.
//A real-world application of phase-in codes
//would place the actual bits into a stream of
//bytes of some sort.
function toBitString(value, totalValues) {
// First we have to find the number of bits
// required to fit totalValues. This tells
// us the power of two bigger or equal to
// totalValues (bet you've never seen
// Math.clz32() in JavaScript before, did
// you? It returns the number of leading zero
// bits in the 32-bit binary representation
// of a number. Yes, we could also use
// Math.ceil(Math.log2(totalValues-1)),
// but where's the fun in that?).
let length = 32 - Math.clz32(totalValues - 1);
const nextPow2 = (1 << length) >>> 0;
// Once we have this power of two we can
// determine the treshold value. Values
// below it will require one bit less.
const treshold = nextPow2 - totalValues;
let returnString = "";
if (value < treshold) {
length--;
} else {
value += treshold;
}
returnString = value.toString(2);
while (returnString.length < length) {
returnString = "0" + returnString;
}
return returnString;
}
function fromBitString(str, totalValues) {
const value = +("0b"+str);
const length = 32 - Math.clz32(totalValues-1);
const nextPow2 = (1<<length) >>> 0;
const treshold = nextPow2 - totalValues;
return value < treshold ? value : (value - treshold) >>> 0;
}
// Demonstration of a stream object that generates an array of bytes.
// Can be used in a variant of LZString, for example
class ByteStream {
constructor() {
this.stream = new CircularU8();
this.valOut = 0;
this.remainingOutBits = 8;
this.valInPos = 0;
this.valIn = 0;
this.remainingInBits = 0;
}
clear() {
this.stream = []; // use string as bitstream,
this.valOut = 0;
this.remainingOutBits = 8;
this.valInPos = -1;
this.valIn = 0;
this.remainingInBits = 0;
}
getNextVal() {
return this.stream.data[this.valInPos++];
}
/**
* @param {number} value
* @param {number} valueBits
*/
strOut(value, valueBits) {
// First handle all bits that fill up valOut and move to the next
// char in the stream until all the remaining value bits fit in valOut
if (valueBits > this.remainingOutBits) {
valueBits -= this.remainingOutBits;
let valueChunk = value >>> valueBits;
this.valOut = this.valOut | valueChunk;
this.stream.push(this.valOut);
// while there are more valueBits left than can be fit into
// a full charCode, stream bit by charCode sized chunks
while (valueBits >= 8) {
valueBits -= 8;
this.stream.push((value >>> valueBits) & 0xFF);
}
this.valOut = 0;
this.remainingOutBits = 8;
}
// At this point valueBits < remainingvalOutBits. If there are bits left
// to stream, put them into valOut
if (valueBits > 0) {
var valueMask = (1 << valueBits) - 1;
this.remainingOutBits -= valueBits;
this.valOut = this.valOut | ((value & valueMask) << this.remainingOutBits);
}
// if we filled up our valOut, stream it.
if (this.remainingOutBits === 0) {
this.stream.push(this.valOut);
this.valOut = 0;
this.remainingOutBits = 8;
}
}
flush() {
if (this.remainingOutBits < 8) {
this.stream.push(this.valOut);
this.valOut = 0;
this.remainingOutBits = 8;
}
}
/**
* @param {number} valueBits
*/
strIn(valueBits) {
// Move to next valIn value if this one is finished
if (this.remainingInBits === 0) {
this.remainingInBits = 8;
this.valIn = this.getNextVal();
}
// // only get a valIn if still inside data
// if (streamIdx >= this.stream.length) return null;
let value = 0;
// while more bits are asked than current valIn has remaining,
// put bit chunks into the output value and get new char values
if (valueBits > this.remainingInBits) {
let valueMask = (1 << this.remainingInBits) - 1;
valueBits -= this.remainingInBits;
this.remainingInBits = 8;
value = (this.valIn & valueMask) << valueBits;
while (valueBits > 8) {
valueBits -= 8;
value = value | (this.getNextVal() << valueBits);
}
this.valIn = this.getNextVal();
}
// If there are still required bits left, get them from valIn
// Note: valueBits < remainingBits is ensured due to above if+while section
if (valueBits > 0) {
let valueMask = (1 << valueBits) - 1;
this.remainingInBits -= valueBits;
value = value | ((this.valIn >>> this.remainingInBits) & valueMask);
}
return value;
}
/**
* @param {number} value
* @param {number} totalValues
*/
phaseOut(value, totalValues) {
value = totalValues - 1 - value;
let valueBits = 32 - Math.clz32(totalValues - 1);
const nextPow2 = (1 << valueBits) >>> 0;
// Once we have this power of two we can determine the treshold value.
// Any value below the treshold will require one fewer bit.
const treshold = nextPow2 - totalValues;
if (value < treshold) {
valueBits--;
}
else {
value += treshold;
}
this.strOut(value, valueBits);
}
/**
* @param {number} totalValues
*/
phaseIn(totalValues) {
const valueBits = 32 - Math.clz32(totalValues - 1);
const nextPow2 = (1 << valueBits) >>> 0;
const treshold = nextPow2 - totalValues;
let value = this.strIn(valueBits - 1);
if (value >= treshold)
value = ((value << 1) + this.strIn(1) - treshold) >>> 0;
return totalValues - 1 - value;
}
}
import {CircularU8} from "@jobleonard/circular-buffers"
// Not actually used
/*
function nextPow2(v) {
return v >= 0xFFFFFFFF ?
0x100000000 * (1<<(32-Math.clz32((v-1) * 2.3283064365386963e-10))) :
(1<<(32- Math.clz32(v-1))) >>> 0;
}
*/
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
