base128

Benchmark created on October 16, 2023

Setup

const U8Bits = {
  encode: (bytes) => {
    const bits = new Uint8Array(bytes.length * 8);
    for (let cursor = 0, i = 0, l = bytes.length; i < l; i++) {
      const byte = bytes[i];
      for (let bit_idx = 7; bit_idx >= 0; bit_idx--) {
        bits[cursor++] = byte >> bit_idx & 1;
      }
    }
    return bits;
  },
  decode: (bits) => {
    const bytes = new Uint8Array(Math.ceil(bits.length / 8));
    for (let cursor = 0, i = 0; i < bits.length; i += 8) {
      for (let bit_idx = 0; bit_idx < 8; bit_idx++) {
        bytes[cursor] |= (bits[i + bit_idx] | 0) << 7 - bit_idx;
      }
      cursor++;
    }
    return bytes;
  }
};
const U7Bits = {
  encode: (bytes) => {
    const bits = new Uint8Array(bytes.length * 7);
    for (let cursor = 0, i = 0, l = bytes.length; i < l; i++) {
      const byte = bytes[i];
      for (let bit_idx = 6; bit_idx >= 0; bit_idx--) {
        bits[cursor++] = byte >> bit_idx & 1;
      }
    }
    return bits;
  },
  decode: (bits) => {
    const bytes = new Uint8Array(Math.ceil(bits.length / 7));
    for (let cursor = 0, i = 0; i < bits.length; i += 7) {
      for (let bit_idx = 0; bit_idx < 7; bit_idx++) {
        bytes[cursor] |= (bits[i + bit_idx] | 0) << 6 - bit_idx;
      }
      cursor++;
    }
    return bytes;
  }
};
const BitByBitBase128 = {
  encode: (octets) => {
    const u8_bits = U8Bits.encode(octets);
    const encoded = U7Bits.decode(u8_bits);
    const n_padding = 7 - (u8_bits.length % 7 || 7);
    const with_n_padding = new Uint8Array(encoded.length + 1);
    with_n_padding.set(encoded, 0);
    with_n_padding[encoded.length] = n_padding;
    return with_n_padding;
  },
  decode: (bytes) => {
    const without_n_padding = bytes.slice(0, bytes.length - 1);
    return U8Bits.decode(U7Bits.encode(without_n_padding));
  }
};





// Encodes the given buffer of size bufferSize into a base128 encoded string.
// Returns a pointer to the encoded string, or NULL on error.
function base128Encode(buffer, bufferSize) {
  // Check if the buffer size is 0.
  if (bufferSize === 0) {
    return null;
  }

  // Calculate the size of the encoded string.
  // How many `uint7`s are required to store `bufferSize` `uint8`s?
  const size = Math.ceil(bufferSize * 8 / 7);

  // Allocate memory for the encoded string.
  const encoded = new Uint8Array(size);

  // Initialize the left shift and right shift variables.
  let left_shift = 0;
  let right_shift = 7;

  // Initialize the carry variable.
  let carry = 0;

  // Initialize the next character variable.
  let nc = 0;

  // Iterate over the buffer, encoding each byte.
  for (let input_idx = 0, t = 0; input_idx < bufferSize + 1; t++, input_idx++) {
    // If the left shift is greater than 7, use the previous iteration's input, shift the left index back and reset the right shift.
    if (left_shift > 7) {
      input_idx--;
      left_shift = 0;
      right_shift = 7;
    }

    // If the index is greater than or equal to the buffer size, set the next character to 0.
    // Otherwise, set the next character to the current byte in the buffer.
    nc = (input_idx >= bufferSize) ? 0 : buffer[input_idx];

    // Save the next character.
    const nc_for_carry = nc;

    // Shift the next character left by the left shift amount.
    nc <<= left_shift;

    // OR the next character with the previous carry bits.
    nc &= 0x7f;
    nc |= carry;

    // Shift the saved next character right by the right shift amount and save the carry bits.
    carry = (nc_for_carry >> right_shift) & 0x7f;

    // Increment the left shift and decrement the right shift
    // by 8 - 7 = 1
    left_shift++;
    right_shift--;

    // Set the current character in the encoded string to the ASCII value of the next character.
    encoded[t] = nc;
  }

  // Return a pointer to the encoded string.
  return encoded;
}

// Decodes the given base128 encoded string into a buffer.
// Returns a pointer to the buffer, or NULL on error.
function base128Decode(buffer) {
  // Check if the buffer size is 0.
  if (buffer.length === 0) {
    return null;
  }

  // Calculate the size of the decoded string.
  // How many `uint8`s are required to store `bufferSize` `uint7`s?
  const size = Math.ceil(buffer.length * 7 / 8);

  // Allocate memory for the decoded buffer.
  const decoded = new Uint8Array(size);

  // Set the decoded buffer size.
  decodedSize = size;

  // Initialize the right shift and left shift variables.
  let rs = 8;
  let ls = 7;

  // Initialize the carry variable.
  let r = 0;

  // Initialize the next character variable.
  let nc = 0;

  // Initialize the saved next character variable.
  let r1 = 0;

  // Initialize the index variable.
  let t = 0;

  // Iterate over the buffer, decoding each character.
  for (let inx = 0; inx < buffer.length; inx++) {
    nc = buffer[inx];

    // If the right shift is greater than 7, shift it back and reset the left shift.
    if (rs > 7) {
      rs = 1;
      ls = 7;
      r = nc;
      continue;
    }

    // Save the next character.
    r1 = nc;

    // Shift the next character left by the left shift amount and mask it with 0xFF.
    nc = (nc << ls) & 0xFF;

    // OR the next character with the carry bits.
    nc |= r;

    // Shift the saved next character right by the right shift amount.
    r = r1 >> rs;

    // Increment the right shift and decrement the left shift.
    rs++;
    ls--;

    // Set the current character in the decoded buffer to the next character.
    decoded[t++] = nc;
  }

  // Return a pointer to the decoded buffer.
  return decoded;
}


const buffer = new Uint8Array([
  0b00000001,
  0b00000010,
  0b00000011,
  0b00000100,
  0b00000101,
  0b00000110,
  0b00000111,
  0b00001000,
  0b00001001,
  0b00001010,
  0b00001011,
]);

function isEqualArray(a, b) {
  if (a.length != b.length) return false;
  for (let i = 0; i < a.length; i++) {
    if (a[i] != b[i]) return false;
  }
  return true;
}

function assert(condition, message) {
    if (!condition) {
        throw new Error(message || "Assertion failed");
    }
}

Test runner

const decodedBuffer = base128Decode(base128Encode(buffer, buffer.byteLength));
//assert(isEqualArray(decodedBuffer.slice(0, decodedBuffer.length - 1), buffer));

const decodedBuffer = BitByBitBase128.decode(BitByBitBase128.encode(buffer));
//assert(isEqualArray(decodedBuffer.slice(0, decodedBuffer.length - 1), buffer));

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on October 16, 2023