Zenn
🎨

TypeScriptでGIF画像をデコードして描画する

2022/07/03に公開
JavaScript
TypeScript
#
gif
tech

先日、なんとなくGIF画像の仕組みが知りたくなって、GIFのフォーマットを調べながらTypeScriptでデコード処理を書いてみたが、自分で書いたコードでGIFアニメーションが再生すると結構感動したので、そのときの知見を共有したい。

GIFのフォーマット

GIFデータがGIFであるためには、データ先頭の3byteが "GIF" で、次の3byteにバージョンが入っていて…と明確にフォーマットが決まっており、フォーマットの詳細は下記のサイトが参考になる。

https://www.tohoho-web.com/wwwgif.htm

とにもかくにも、GIFをバイナリデータとして読み込まなければならないのでまずはそのやり方からスタートする。

バイナリデータとしての読み込み

const response = await fetch("xxx.gif");
const arrayBuffer = await response.arrayBuffer();
const buffer = new Uint8Array(arrayBuffer);

まず fetch() を使用してGIF画像を読み込む。読み込んだデータはバイナリデータとして扱いたいので Response#arrayBuffer() で ArrayBuffer に変換する。これらの関数は非同期処理で Promise が返ってくるので async/await 等を利用して受け取る必要がある。ArrayBuffer のままでは中のバイナリデータを参照することができないので、Uint8Array に変換する。Uint8Array はバイナリデータをByte単位で参照することができ、たとえば array[0] だとバイナリデータの先頭1byteを0～255の範囲で扱うことができる。

Uint8Arrayの操作

GIFデータの中には圧縮された画像データが入っているが、先頭からxxxByteの位置に格納、のように固定されているわけではなく、データ毎に可変の位置に存在するので、GIFの仕様に合わせて、前から順番にデータにアクセスする必要がある。そのための Uint8Array の操作方法例が下記になる。

let pos = 0;
const readByte = () => {
  return buffer[pos++];
};

まず Uint8Array の現在どこを指しているかを pos が管理する。そして readByte() を呼び出すと pos が指している位置のデータを1byte取り出し pos の位置を1つ先に進める。

const a = readByte();
const b = readByte();

こうするとデータを触るたびに pos の位置をいちいち手動で変更しなくてすむので非常に楽になる。ただし、実際には複数ByteやBit単位で読み込むところもあるので、もう少し読み込む関数を増やす必要がある。

let pos = 0;

// 1byte読み込む
const readByte = () => {
  return buffer[pos++];
};

// nbyte読み込む
const readBytes = (n: number) => {
  const ret: number[] = [];
  for (let i = 0; i < n; i++) {
    ret.push(readByte());
  }
  return ret;
};

// 3byte読み込んで色のデータ(RGB)として扱う
type Color = {
  r: number;
  g: number;
  b: number;
};
const readColor = (): Color => {
  const r = readByte();
  const g = readByte();
  const b = readByte();
  return { r, g, b };
};

// byteの右からpos番目からsizeビット取り出す
const readBit = (byte: number, pos: number, size: number) => {
  const v = byte >> (pos - size);
  const mask = 2 ** size - 1;

  return v & mask;
};

// 2byte取り出したものを反転して結合する
const readReversed2Byte = () => {
  const [a, b] = [readByte(), readByte()];
  return (b << 8) | a;
};

データの中で必要なものだけ取り出す

GIFデータにはGIFを構成するための複数の情報が格納されているが、今回その全てのデータが欲しいわけではなく、実際に必要なのは下記だけである。

  • GIF Header
    • 画像の幅
    • 画像の高さ
    • GlobalColorTable
  • ImageBlock
    • 左上位置、幅、高さ
    • LocalColorTable
    • 圧縮された画像データ
  • Graphic Control Extension
    • どの色を透明にするか？

GIFアニメーションでご存知の通り、GIFの中には複数の画像を入れることができ、それぞれの画像のことをImageBlockと呼ぶ。

このImageBlock毎に使用できる色は最大で256色で、ImageBlockで使用されている色全てはImageBlock内のLocalColorTableという領域に格納されている。

ただし、LocalColorTableの領域を用意するのは任意となっており、代わりにGIF画像の中にGlobalColorTableという領域が1つだけ用意されている。そこに入れることができる色はLocalと同じく256色である。これは名前の通り、ImageBlock共有のカラーパレットとして扱うことができ、このGlobalColorTableに色を収めることができるならばLocalColorTableの領域は不要になるのでGIFの容量を削減することができる。

後でも扱うが、ImageBlockとは別領域に、どの色（カラーパレットのインデックス）を透明にするかを決めることが出来る。

GIF Headerの読み込み

では実際に上記関数を利用してGIFデータをByte単位で読み込んでいく。先程挙げた必要なデータ以外は全て読み飛ばしたいので、そのような不必要な項目は readXXX() を呼んでも戻り値を受け取らないようにしている。

GIFデータの先頭にはGIF Headerというブロックが必ず存在し、その中で今必要なのは画像の幅・高さ、そして GlobalColorTable になる。

readString(3); // signature
readString(3); // version
const w = readReversed2Byte(); // 幅
const h = readReversed2Byte(); // 高さ
const v = readByte();
const globalColorTableFlag = readBit(v, 8, 1) === 1; // グローバルの色テーブルが存在するか？
readBit(v, 7, 3); // colorResolution
readBit(v, 4, 1); // sortFlag
const globalColorTableSize = readBit(v, 3, 3); // グローバルの色テーブルのサイズ
readByte(); // bgColorIndex
readByte(); // pixelAspectRatio

// グローバルの色テーブルが存在する場合、
// RGB3byteの並びが2^(globalColorTableSize+1)個配置されている
const globalColorTable: Color[] = [];
if (globalColorTableFlag) {
  for (let i = 0; i < 2 ** (globalColorTableSize + 1); i++) {
    globalColorTable.push(readColor());
  }
}

Blockの読み込み

GIF Headerの後はBlockという領域が1つ以上並んでいる。

ただしBlockには、

  • Image Block
  • Graphic Control Extension
  • Comment Extension
  • Plain Text Extension
  • Application Extension

という5つの種類があり、どれが先に来るかは分からないが、それぞれのブロックには先頭数Byteに固有の識別子が付いているので、それを見て処理を振り分ければ問題がない。

GIFデータの最後には 0x3b という値が入っているので、それがきたらGIFのデコード処理を終了させる。

const Exit = 0x3b;
const ImageBlock = 0x2c;
const ExtensionBlock = 0x21;
const GraphicControlExtension = 0xf9;
const CommentExtension = 0xfe;
const PlainTextExtension = 0x01;
const ApplicationExtension = 0xff;

while (true) {
  const type = readByte();
  if (type === Exit) {
    break;
  } else if (type === ImageBlock) {
    loadImageBlock();
  } else if (type === ExtensionBlock) {
    const label = readByte();
    switch (label) {
      case GraphicControlExtension:
        loadGraphicControlExtension();
        break;
      case CommentExtension:
        loadCommentExtension();
        break;
      case PlainTextExtension:
        loadPlainTextExtension();
        break;
      case ApplicationExtension:
        loadApplicationExtension();
        break;
      default:
        break;
    }
  }
}

ImageBlock/GraphicControlExtension以外のブロック

ImageBlock/GraphicControlExtension以外のブロック内の情報は今回必要がないので、仕様書通りに readXXX() で読み飛ばすことにする。

const loadCommentExtension = () => {
  while (true) {
    const blockSize = readByte();
    if (blockSize === 0) {
      break;
    }
    readBytes(blockSize); // commentData
  }
};

const loadPlainTextExtension = () => {
  readByte(); // blockSize
  readBytes(2); // textGridLeftPosition
  readBytes(2); // textGridTopPosition
  readBytes(2); // textGridWidth
  readBytes(2); // textGridHeight
  readByte(); // characterCellWidth
  readByte(); // characterCellHeight
  readByte(); // textForegroundColorIndex
  readByte(); // textBackgroundColorIndex
  while (true) {
    const blockSize = readByte();
    if (blockSize === 0) {
      break;
    }
    readBytes(blockSize); // plainTextData
  }
};

const loadApplicationExtension = () => {
  readByte(); // blockSize
  readBytes(8); // applicationIdentifier
  readBytes(3); // applicationAuthenticationCode
  while (true) {
    const blockSize = readByte();
    if (blockSize === 0) {
      break;
    }
    readBytes(blockSize); // applicationData
  }
};

GraphicControlExtension

const loadGraphicControlExtension = () => {
  readByte(); // blockSize
  const v = readByte();
  transparentColorFlag = readBit(v, 1, 1) === 1; // この後に出てくるImageBlockで透明にするところがあるか？
  readBytes(2); // delayTime
  transparentColorIndex = readByte(); // カラーテーブル内の透明にしたいインデックス
  readByte(); // blockTerminator
};

GraphicControlExtensionにはImageBlockの補足情報が入っており、基本的に該当のImageBlockの前にこのブロックが配置されている。

今欲しいのは transparentColorFlag と transparentColorIndex で、前者が 1 だと、この後に出てくるImageBlockの カラーテーブル[transparentColorIndex] を透明にさせる。

ImageBlock

const imageBlocks: ImageBlock[] = [];

const loadImageBlock = () => {
  const left = readReversed2Byte();
  const top = readReversed2Byte();
  const width = readReversed2Byte();
  const height = readReversed2Byte();
  const v = readByte();
  const localColorTableFlag = readBit(v, 8, 1) === 1;
  readBit(v, 7, 1); // interlaceFlag
  readBit(v, 6, 1); // sortFlag
  readBit(v, 5, 2); // reserved
  const localColorTableSize = readBit(v, 3, 3);
  const localColorTable: Color[] = [];
  if (localColorTableFlag) {
    for (let i = 0; i < 2 ** (localColorTableSize + 1); i++) {
      localColorTable.push(readColor());
    }
  }

  const lzwMinCodeSize = readByte();
  let imageData: number[] = [];
  while (true) {
    const blockSize = readByte();
    if (blockSize === 0) {
      break;
    }

    imageData = imageData.concat(readBytes(blockSize));
  }
  const decodedData = decodeLZW(lzwMinCodeSize, new Uint8Array(imageData), width * height);
  const colors: number[] = [];
  for (const d of decodedData) {
    const { r, g, b } = localColorTableFlag ? localColorTable[d] : globalColorTable[d];
    colors.push(r, g, b, 255);
  }
  imageBlocks.push({ left, top, width, height, colors });
};

left, top, width, height はこのブロックにおける領域を表す。なので、この情報がある以上、GIFアニメーションの一枚一枚の画像の左上位置は (0, 0) で無いケースが有りえる。というのも、GIFアニメーションの中には、部分的な範囲だけ変化するものがあり、その領域を含む最小の矩形範囲だけをImageBlockにすれば容量が大幅に削減されるからである。

LocalColorTableの扱いはGlobalColorTableと同じで、localColorTableFlag が 1 であれば、RGB3byteの並びが 2^(localColorTableSize+1) 個配置されている。

GIF内にある画像の一つ一つは、ピクセルから(Local/Global)ColorTableのインデックスに変換され、その値の列がLZWというアルゴリズムで圧縮されている。

lzwMinCodeSize にはこの後LZWデータを解凍する際に必要になる値が入っている。

lzwMinCodeSize の後にはLZWで圧縮されたデータが入っているが、255byteおきの細切れデータが格納されている。

具体的には、

  • 圧縮データ0のサイズ
  • 圧縮データ0
  • 圧縮データ1のサイズ
  • 圧縮データ1
  • 圧縮データ2のサイズ
  • 圧縮データ2
  • ...

という形で格納されている。

例えば600byteのデータだと、下記の形で格納されている。

  • 255
  • 255byteのデータ
  • 255
  • 255byteのデータ
  • 90
  • 90byteのデータ

これらの分割されたデータを結合してLZWを解凍する関数に渡す。

LZWの解凍

const decodeLZW = (minCodeSize: number, data: Uint8Array, pixelCount: number): number[] => {
  const maxStackSize = 2 ** 12;
  const nullCode = -1;
  const clearCode = 2 ** minCodeSize;
  const endCode = clearCode + 1;
  const ret = [];
  const prefix = [];
  const suffix = [];
  const pixelStack = [];

  let dataSize = minCodeSize;
  let available = clearCode + 2;
  let oldCode = nullCode;
  let codeSize = dataSize + 1;
  let codeMask = 2 ** codeSize - 1;
  let datum = 0;
  let bits = 0;
  let first = 0;
  let top = 0;
  let pi = 0;
  let bi = 0;

  for (let i = 0; i < clearCode; i++) {
    prefix[i] = 0;
    suffix[i] = i;
  }

  let i = 0;
  while (i < pixelCount) {
    if (top === 0) {
      if (bits < codeSize) {
        datum += data[bi++] << bits;
        bits += 8;
        continue;
      }

      let code = datum & codeMask;
      datum >>= codeSize;
      bits -= codeSize;

      if (code > available || code === endCode) {
        break;
      }

      if (code === clearCode) {
        codeSize = dataSize + 1;
        codeMask = 2 ** codeSize - 1;
        available = clearCode + 2;
        oldCode = nullCode;
        continue;
      }

      if (oldCode === nullCode) {
        pixelStack[top++] = suffix[code];
        oldCode = code;
        first = code;
        continue;
      }

      const inCode = code;

      if (code === available) {
        pixelStack[top++] = first;
        code = oldCode;
      }

      while (code > clearCode) {
        pixelStack[top++] = suffix[code];
        code = prefix[code];
      }

      first = suffix[code] & 0xff;
      pixelStack[top++] = first;

      if (available < maxStackSize) {
        prefix[available] = oldCode;
        suffix[available] = first;
        available++;

        if ((available & codeMask) === 0 && available < maxStackSize) {
          codeSize++;
          codeMask += available;
        }
      }

      oldCode = inCode;
    }

    top--;
    ret[pi++] = pixelStack[top];
    i++;
  }

  for (i = pi; i < pixelCount; i++) {
    ret[i] = 0;
  }

  return ret;
};

https://www.youtube.com/watch?v=KJBZyPPTwo0

LZWのアルゴリズムについては、上記動画がかなりわかりやすかったので参照してほしい。

再生

これで今回必要な情報が全て手に入ったので、LZWを解凍したカラーパレットインデックス列をもとに画面に描画させる。GIFアニメーションでなく単一の画像の場合は、ImageBlockが1つしかないという状態なのでアニメーションありなしで処理が変わることはない。

手元で幾つか画像の再生を試してみたが、毎フレーム CanvasRenderingContext2D#clearRect() などで画面の初期化をする必要はないと感じた。

import { parse } from "./gifparser/parse";

const gif = await parse("test.gif");
const canvas = document.getElementById("canvas") as HTMLCanvasElement;
canvas.width = gif.width;
canvas.height = gif.height;
const ctx = canvas.getContext("2d");
const scale = 1;
let frameIndex = 0;

const update = () => {
  if (ctx && frameIndex < gif.imageBlocks.length) {
    const block = gif.imageBlocks[frameIndex];
    frameIndex = (frameIndex + 1) % gif.imageBlocks.length;

    let i = 0;
    for (let y = block.top; y < block.top + block.height; y++) {
      for (let x = block.left; x < block.left + block.width; x++) {
        const r = block.colors[i];
        const g = block.colors[i + 1];
        const b = block.colors[i + 2];
        const a = block.colors[i + 3];
        ctx.fillStyle = `rgba(${r},${g},${b},${a})`;
        ctx.fillRect(x * scale, y * scale, scale, scale);
        i += 4;
      }
    }
  }

  requestAnimationFrame(update);
};
update();

実装例

https://github.com/BaroqueEngine/GIFParser

Discussion