Fast Compression / Decompression Algorithms

microlz4.js

const { Buffer } = require("buffer");

/* ---------- helpers ---------- */
function writeV(buf: Uint8Array, off: number, v: number): number {
  let o = off;
  while (v >= 0x80) {
    buf[o++] = (v & 0x7f) | 0x80;
    v >>>= 7;
  }
  buf[o++] = v;
  return o - off;
}
function readV(buf: Uint8Array, off: number): { val: number; len: number } {
  let v = 0,
    s = 0,
    b: number;
  let o = off;
  do {
    b = buf[o++];
    v |= (b & 0x7f) << s;
    s += 7;
  } while (b & 0x80);
  return { val: v, len: o - off };
}

/* ---------- global pools ---------- */
let HT: Uint32Array | null = null;
const HT_SIZE = 1 << 15; // 128 KB hash table (Uint32)
function getHT(): Uint32Array {
  if (!HT) HT = new Uint32Array(HT_SIZE);
  return HT;
}

// Compressor scratch: worst-case 256 KB * 6 + 32 KB ≈ 1.6 MB
let CPOOL: Uint8Array | null = null;
function getCompressScratch(required: number): Uint8Array {
  if (!CPOOL || CPOOL.length < required)
    CPOOL = new Uint8Array(Math.max(required, 1600 * 1024));
  return CPOOL;
}

// Decompressor output: 256 KB max
let DPOOL: Uint8Array | null = null;
function getDecompressOut(len: number): Uint8Array {
  if (!DPOOL || DPOOL.length < len)
    DPOOL = new Uint8Array(Math.max(len, 256 * 1024));
  return DPOOL.subarray(0, len); // zero-copy view
}

/* ---------- compress ---------- */
export function compress(src: Buffer): Buffer {
  const n = src.length;
  if (n === 0) return Buffer.from([0]);

  const ht = getHT();
  ht.fill(0); // fast clear

  const needed = 5 + n * 6 + 32;
  const scratch = getCompressScratch(needed);
  let op = 0;

  op += writeV(scratch, op, n);

  const W = 1 << 15; // 32 KB window
  const minMatch = 4;
  const hashMask = HT_SIZE - 1;

  let anchor = 0;
  let ip = 0;

  while (ip < n - minMatch) {
    const h = ((src.readUInt32LE(ip) * 0x9e3779b9) >>> (32 - 15)) & hashMask;
    const ref = ht[h];
    ht[h] = ip;

    const dist = ip - ref;
    if (!ref || dist >= W || dist === 0) {
      ip++;
      continue;
    }
    if (
      !src.subarray(ip, ip + minMatch).equals(src.subarray(ref, ref + minMatch))
    ) {
      ip++;
      continue;
    }

    // literals
    if (ip > anchor) {
      const litLen = ip - anchor;
      op += writeV(scratch, op, litLen << 1);
      scratch.set(src.subarray(anchor, ip), op);
      op += litLen;
    }

    // match
    let matchLen = minMatch;
    while (ip + matchLen < n && src[ip + matchLen] === src[ref + matchLen])
      matchLen++;
    op += writeV(scratch, op, ((matchLen - minMatch) << 1) | 1);
    op += writeV(scratch, op, dist);
    ip += matchLen;
    anchor = ip;
  }

  if (anchor < n) {
    const litLen = n - anchor;
    op += writeV(scratch, op, litLen << 1);
    scratch.set(src.subarray(anchor, n), op);
    op += litLen;
  }

  // Convert Uint8Array view back to Node Buffer without copy
  return Buffer.from(scratch.buffer, scratch.byteOffset, op);
}

/* ---------- decompress ---------- */
export function decompress(src: Buffer): Buffer {
  if (src.length === 0) return Buffer.allocUnsafe(0);
  let ip = 0;
  const { val: n, len: l1 } = readV(src, ip);
  ip += l1;
  const out = getDecompressOut(n);
  let op = 0;

  while (ip < src.length) {
    const { val: token, len: l2 } = readV(src, ip);
    ip += l2;
    const isMatch = token & 1;
    const len = token >> 1;

    if (!isMatch) {
      out.set(src.subarray(ip, ip + len), op);
      op += len;
      ip += len;
    } else {
      const { val: dist, len: l3 } = readV(src, ip);
      ip += l3;
      const from = op - dist;
      for (let i = 0; i < len + 4; i++) out[op + i] = out[from + i];
      op += len + 4;
    }
  }
  return Buffer.from(out.buffer, out.byteOffset, n);
}

RLE.js

const { Buffer } = require("buffer");

// Run length encoding
// O(n) for both compression and decompression,  O(1) additional space during processing
// A,A,A,A,B,B,C,C,C,C,C => (A,4),(B,2),(C,5)
export function compressRLE(buffer: Buffer) {
  if (!buffer.length) return Buffer.alloc(0);

  const out = [];
  let val = buffer[0],
    cnt = 1;

  for (let i = 1; i < buffer.length; i++) {
    if (buffer[i] === val && cnt < 255) {
      cnt++;
    } else {
      out.push(val, cnt);
      val = buffer[i];
      cnt = 1;
    }
  }
  out.push(val, cnt);
  return Buffer.from(out);
}

export function decompressRLE(compressed: Buffer) {
  const out = [];
  for (let i = 0; i < compressed.length; i += 2) {
    const val = compressed[i];
    const cnt = compressed[i + 1];
    for (let j = 0; j < cnt; j++) out.push(val);
  }
  return Buffer.from(out);
}