Create inline GIF favicons

favicon.js

/* Bill Ticehurst, 2020

Emits a minimal 16 x 16 gif suitable for use as an inline favicon

GIF spec at https://www.w3.org/Graphics/GIF/spec-gif89a.txt for the structure
Favicon formats supported at https://en.wikipedia.org/wiki/Favicon

For a transparent GIF (color_table = false, depend_on_background = true) this emits:

  <link rel="icon" href="data:image/gif;base64,R0lGODlhEAAQAAAAACwAAAAAAQABAAACASgAOw==">

Note that this is transparent as a browser favicon, but shows as a black square when opening as a file.
To be correct as a file, should set use_transparency = true also, which is slightly longer:

  <link rel="icon" href="data:image/gif;base64,R0lGODlhEAAQAAAAACH5BAEAAAAALAAAAAABAAEAAAIBKAA7">

For a default black square icon with the pixels specified (depend_on_background = false) this emits:

  <link rel="icon" href="data:image/gif;base64,R0lGODlhEAAQAAAAACwAAAAAEAAQAAACDvAxdbn9YZSTVntx1qcAADs=">

With an image color also specified (color_table = true) this emits:

  <link rel="icon" href="data:image/gif;base64,R0lGODlhEAAQAPAAAP9/PwAAACwAAAAAEAAQAAACDvAxdbn9YZSTVntx1qcAADs=">

With two_tone specified if will do top half color 0 and bottom half color 1, e.g. orange over blue is:

  <link rel="icon" href="data:image/gif;base64,R0lGODlhEAAQAPAAAP+AQECA/ywAAAAAEAAQAAACFPAxdbn9YZSTBXtx1pt3/8FQHLkCADs=">

*/

// @ts-check

// Use the system colors (index 0 is usually black)
const color_table = false;

// Use the background color for unspecified pixels
const depend_on_background = true;

// Specify to use the transparency extension
const use_transparency = true;

// Use the two colors for top/bottom halves of the image
const two_tone = false;

if (two_tone && depend_on_background) throw "Two tone doesn't work with background color";
if (two_tone && use_transparency) throw "Two tone and transparency makes no sense";

let expected_bytes = 28;
if (color_table) expected_bytes += 6;
if (!depend_on_background) expected_bytes += 13;
if (two_tone) expected_bytes += 6;
if (use_transparency) expected_bytes += 8;

// Even if using the background, a min 1 x 1 pixel image block is required
let pixel_count = (two_tone && depend_on_background) ? (8 * 16) : (depend_on_background ? 1 : 16 * 16);

// Specify the default index values prior to the LZW codes.
/** @type {Map<number, number[]>}> */
let dict = new Map([
  [0, [0]],
  [1, [1]],
  [2, [2]],
  [3, [3]]
]);

let code_size = 2;            // Bits needed per pixel
let bit_size = code_size + 1; // Initial size of codes in output
let clear_code = Math.pow(2, code_size);
let end_of_info_code = clear_code + 1;
let next_code = clear_code + 2;

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 */
function arr_equal(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;
  return arr1.every( (elem, idx) => arr2[idx] === elem);
}

/**
 * @param {number[]} arr
 */
function arr_clone(arr) {
  let result = [];
  arr.forEach(elem => result.push(elem));
  return result;
}

/**
 * @param {number[]} arr
 */
function find_code(arr) {
  for(const [key, value] of dict) {
    if (arr_equal(arr, value)) return key;
  }
  return undefined;
}

/** @type {number[]} */
let curr_input = [];
let pending_output = -1;

/** @type {number[]} */
let output = [];

for(let i = 0; i < pixel_count; ++i) {
  // Skip writing any pixel values if just using the background color
  let pix_color = (two_tone && i >= 0x80 ? 1 : 0);
  curr_input.push(pix_color);
  // console.log(`Writing index ${pix_color} to pixel ${i}`);

  // Do we have a code for it?
  let last_found = find_code(curr_input);

  if (last_found !== undefined) {
    pending_output = last_found;
    continue;
  }

  // Wasn't in the codes. Save this pattern
  dict.set(next_code++, arr_clone(curr_input));

  if (pending_output !== -1)
  {
    // Add the prior found pattern to the output stream
    // console.log("Pushing value: " + pending_output);
    output.push(pending_output);
    pending_output = -1;
  } else {
    // Can only get here with a length 2 input
    if (curr_input.length !== 2) throw "Invalid logic";
    // console.log("Pushing value " + curr_input[0]);
    output.push(curr_input[0]);
  }

  // Set the next input to be just the additional char not found
  curr_input = [curr_input.pop()];
}
// There's always either pending output code, or a char left to output
if (pending_output !== -1) {
  output.push(pending_output);
} else {
  if (curr_input.length) output.push(find_code(curr_input));
}
output.push(end_of_info_code);

let bits_needed = 0;
const start_bit_size = bit_size;
output.forEach(val => {
  // console.log(`Code: ${val}, bit_size: ${bit_size}`);
  bits_needed += bit_size;
  if (val + 1 === Math.pow(2, bit_size)) ++bit_size;
});
const bytes_needed = Math.ceil(bits_needed / 8);
bit_size = start_bit_size;

const buffer = new ArrayBuffer(expected_bytes);
const data_view = new DataView(buffer);
let buf_idx = 0;

// === Signature ===
for(let char of "GIF89a") {
  data_view.setUint8(buf_idx++, char.charCodeAt(0));
}

/* === Screen Descriptor ===
struct {
  uint16_t logical_width;   // 16
  uint16_t logical_height;  // 16
  byte     packed;          // 0
  byte     background_color_index;  // 0
  byte     pixel_aspect_ratio;      // 0 (no aspect ratio given)
} // 7 bytes

     <Packed Fields>  =      Global Color Table Flag       1 Bit
                             Color Resolution              3 Bits
                             Sort Flag                     1 Bit
                             Size of Global Color Table    3 Bits

*/

data_view.setUint16(buf_idx, 16, true); buf_idx += 2;
data_view.setUint16(buf_idx, 16, true); buf_idx += 2;

if (!color_table) {
  data_view.setInt8(buf_idx++, 0);
} else {
  data_view.setInt8(buf_idx++, 0xF0);
}
data_view.setInt8(buf_idx++, 0);
data_view.setInt8(buf_idx++, 0);

if (color_table) {
  // Write out the global color table. Min 2 entries needed.
  data_view.setInt8(buf_idx++, 0xFF);
  data_view.setInt8(buf_idx++, 0x80);
  data_view.setInt8(buf_idx++, 0x40);
  data_view.setInt8(buf_idx++, 0x40);
  data_view.setInt8(buf_idx++, 0x80);
  data_view.setInt8(buf_idx++, 0xFF);
}

/* === Control block for transparency
struct {
  byte extension;  // 0x21
  byte label;      // 0xF9
  byte block_size; // 0x04
  byte packed;     // 0x01
  uint16_t delay;  // 0x0000
  byte transparent_index; // 0x00
  byte terminator; // 0x00
} // 8 bytes
*/

if (use_transparency) {
  data_view.setInt8(buf_idx++, 0x21);
  data_view.setInt8(buf_idx++, 0xf9);
  data_view.setInt8(buf_idx++, 0x04);
  data_view.setInt8(buf_idx++, 0x01);
  data_view.setUint16(buf_idx, 0x00); buf_idx += 2;
  data_view.setInt8(buf_idx++, 0x00);
  data_view.setInt8(buf_idx++, 0x00);
}

/* === Image descriptor===
struct {
  byte     image_separator; // 0x2c
  uint16_t left_position;   // 0
  uint16_t top_position;    // 0
  uint16_t width;           // 16
  uint16_t height;          // 16
  byte     packed;          // 0
} // 10 bytes
*/

const width = (two_tone || !depend_on_background) ? 16 : 1;
const height = (two_tone && depend_on_background) ? 8 : (depend_on_background ? 1 : 16);
const top = (two_tone && depend_on_background) ? 8 : 0;
data_view.setInt8(buf_idx++, 0x2c);
data_view.setUint16(buf_idx, 0, true); buf_idx += 2;
data_view.setUint16(buf_idx, top, true); buf_idx += 2;
data_view.setUint16(buf_idx, width, true); buf_idx += 2;
data_view.setUint16(buf_idx, height, true); buf_idx += 2;
data_view.setInt8(buf_idx++, 0);

// Table-based data
data_view.setInt8(buf_idx++, code_size);

// Image block
data_view.setInt8(buf_idx++, bytes_needed); // Block size

// Write LZW bytes. See https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
let bit_idx = 0;
let bits = 0;

output.forEach( (val, idx) => {
  bits |= val << bit_idx;
  bit_idx += bit_size;

  if (val + 1 === Math.pow(2, bit_size)) ++bit_size;

  while (bit_idx >= 8) {
    data_view.setUint8(buf_idx++, bits & 0xFF);
    bits >>>= 8;
    bit_idx -= 8;
  }

  if (idx === output.length - 1 && bit_idx > 0) {
    // Last val and we have data to write
    data_view.setUint8(buf_idx++, bits & 0xFF);
  }
});

// Block terminator. Must follow the last block.
data_view.setInt8(buf_idx++, 0);

// Trailer. Required at end of file.
data_view.setInt8(buf_idx++, 0x3B);

if (buf_idx !== expected_bytes) throw "Unexpected length";

const fs = require("fs");
fs.writeFileSync("/temp/icon.gif", data_view);

const node_buf = Buffer.from(buffer);
console.log(`<link rel="icon" href="data:image/gif;base64,${node_buf.toString("base64")}">`);