PixelMap compression contest submission

encode_web_safe_color.js

/* Pair of compress/decompress functions for hex-triplet encoded web safe 16x16 image.
 *
 * Uses max Brotli quality for max compression ratio, trading off computation
 * time. Assumes lower case image string input and produces lower case output.
 *
 * Uses the first byte to lookup the encoding/compression strategy.
 */

const base91 = require('node-base91')
const stream = require('stream') // needed for zlib
const zlib = require('zlib')

zlib.constants.BROTLI_PARAM_QUALITY = zlib.constants.BROTLI_MAX_QUALITY
zlib.constants.BROTLI_PARAM_SIZE_HINT = 256

const cartesian = (...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())))

const allowed_hex = ['0', '3', '6', '9', 'c', 'f']
const websafe_triplets = cartesian(allowed_hex, allowed_hex, allowed_hex).map(x => x.join(''))
const hex_to_code = Object.fromEntries([...websafe_triplets.entries()].map(x => x.reverse()))

function chunk_of_n(n, seq) {
  const chunks = []
  for (let i = 0; i < (seq.length / n); i++) {
    chunks.push(seq.slice(i * n, (i + 1) * n))
  }
  return chunks
}

function encode_web_safe(triplets) {
  return Buffer.from(triplets.map(x => hex_to_code[x]))
}

function decode_web_safe(buf) {
  return [...buf].map(x => websafe_triplets[x]).join('')
}

function encode_12bit(triplets) {
  return Buffer.concat(triplets.map(x => Buffer.from('0' + x, 'hex')))
}

function decode_12bit(buf) {
  return chunk_of_n(2, buf).map(
    byte2 => byte2.toString('hex').slice(1)
  ).join('')
}

WEBSAFE_PALETTE = 1
TWELVEB_PALETTE = 2

function compress(s) {
  assert.ok(s.length == 768)

  const triplets = chunk_of_n(3, s)
  let buf, buf_strat;

  // Dispatch encoding strategy based on content
  if (triplets.every(x => websafe_triplets.includes(x))) {
    buf = encode_web_safe(triplets)
    buf_strat = Buffer.from([WEBSAFE_PALETTE])
  } else {
    buf = encode_12bit(triplets)
    buf_strat = Buffer.from([TWELVEB_PALETTE])
  }

  return base91.encode(zlib.brotliCompressSync(Buffer.concat([buf_strat, buf])))
}

function decompress(s) {
  const buf = zlib.brotliDecompressSync(base91.decode(s))
  const buf_strat = buf[0]

  // Dispatch decoding strategy based on first byte
  if (buf_strat === WEBSAFE_PALETTE) {
    return decode_web_safe(buf.slice(1))
  } else if (buf_strat === TWELVEB_PALETTE) {
    return decode_12bit(buf.slice(1))
  }
}

This is an entry into the PixelMap Compression Contest.

Tests using node 14.15.4

Sample image from the contest announcement blog post.

const ss = [
  '390390390390390390390000000390390390390390390390',
  '390390390390390390000ff0ff0000390390390390390390',
  '390390390390390390000ff0ff0000390390390390390390',
  '390390390390390000ff0ff0ff0ff0000390390390390390',
  '000000000000000000ff0ff0ff0ff0000000000000000000',
  '000ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0000',
  '390000ff0ff0ff0ff0000ff0ff0000ff0ff0ff0ff0000390',
  '390390000ff0ff0ff0000ff0ff0000ff0ff0ff0000390390',
  '390390390000ff0ff0000ff0ff0000ff0ff0000390390390',
  '390390390000ff0ff0ff0ff0ff0ff0ff0ff0000390390390',
  '390390000ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0000390390',
  '390390000ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0000390390',
  '390000ff0ff0ff0ff0ff0000000ff0ff0ff0ff0ff0000390',
  '390000ff0ff0ff0000000390390000000ff0ff0ff0000390',
  '000ff0ff0000000390390390390390390000000ff0ff0000',
  '000000000390390390390390390390390390390000000000'
].join('')

console.log(encode(sample))
// -> fY/BDQAhCASnKvqvgYpUFoS7hxsSHNBFzEJgU7jz4I1VIBTcxxZ5N0JvaOaaK4a7z/an8GNhziXtT6bG126gT449YAE=

console.log(encode(sample).length)
// -> 92

console.log(decode(encode(ss)) == ss)
// -> true

Sample blank image.

const sample = [
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
  '000000000000000000000000000000000000000000000000',
].join('')


console.log(encode(sample))
// -> Y2AY2QAA

console.log(encode(sample).length)
// -> 8

console.log(decode(encode(sample)) == sample)
// -> true

Version 2

Base91 encoding/decoding is provided by node-base91. Get it with

npm install node-base91

This final submission supports dynamically dispatched encoding strategy between web safe color space and 12bit color space. This gets the best of both worlds between high space savings by restricting to web safe color palette, and the affordance of higher image quality for users who are happy to pay the higher gas fee.

Reserving the first byte as an encoding indicator save room for forward competability, which I see as a key requirement for on-chain data.

If a user is willing to sacrifice color quality for cheaper gas, they may first downgrade their image to web safe colors using the existing frontend code, before proceeding to uploading their image.

Tested using node 14.15.4

function test(s) {
  s_encoded = compress(s)

  console.log("--- Case ---")
  console.log("Length: (" + s_encoded.length + ") Payload: " + s_encoded)

  if (decompress(s_encoded) == s) {
    console.log('pass')
  } else {
    console.log('FAIL')
    console.log(s)
    console.log(decompress(s_encoded))
  }
}

test([
  '390390390390390390390000000390390390390390390390',
  '390390390390390390000ff0ff0000390390390390390390',
  '390390390390390390000ff0ff0000390390390390390390',
  '390390390390390000ff0ff0ff0ff0000390390390390390',
  '000000000000000000ff0ff0ff0ff0000000000000000000',
  '000ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0000',
  '390000ff0ff0ff0ff0000ff0ff0000ff0ff0ff0ff0000390',
  '390390000ff0ff0ff0000ff0ff0000ff0ff0ff0000390390',
  '390390390000ff0ff0000ff0ff0000ff0ff0000390390390',
  '390390390000ff0ff0ff0ff0ff0ff0ff0ff0000390390390',
  '390390000ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0000390390',
  '390390000ff0ff0ff0ff0ff0ff0ff0ff0ff0ff0000390390',
  '390000ff0ff0ff0ff0ff0000000ff0ff0ff0ff0ff0000390',
  '390000ff0ff0ff0000000390390000000ff0ff0ff0000390',
  '000ff0ff0000000390390390390390390000000ff0ff0000',
  '000000000390390390390390390390390390390000000000'
].join(''))

test(Array(768).fill('0').join(''))
test(Array(128).fill('000333').join(''))
test(Array(128).fill('000111').join(''))
test(Array(64).fill('000111222333').join(''))

Output

--- Case ---
Length: (87) Payload: bAG"cZ>UCZw)/#NA7yDBr#yV2k?@1*t7oXcF#C[JpZ+|6A#(eL%s0Wm:^Zqp3/AO#qJC^";v?^J;.kY@JQyq)(B
pass
--- Case ---
Length: (15) Payload: bAG"wd:C:a)WF%A
pass
--- Case ---
Length: (17) Payload: bAG"D0:CaaH#wA[RA
pass
--- Case ---
Length: (19) Payload: bAK"x::C!WpB"D*h:(B
pass
--- Case ---
Length: (25) Payload: bAK"EB9"ax@?"$M&]Jjf0dTUA
pass