この記事はEEIC2022 Advent Calender2021第23日目の記事として書かれました。

はじめに

はじめまして、EEIC2022のゆーちゃんです。学科のアドカレをくらげくんが作ってくれたので折角ならということで参加してみました。某H君には自転車でズッコケて救急車で運ばれた話をアドカレにしろと言われてたのですが、折角なので、EEICっぽい記事を残そうと思います。
ちなみに自転車でズッコケて救急車で運ばれた話はnoteに書きました。

この記事の目次

基本的には、僕がGIF画像を作ろうと思ったキッカケを話したあとはひたすらGIF画像の作り方について説明するつもりです。
なお、僕はGIF画像作成がかなりの茨の道であることを知らずに突っ込んだため、それなりに重症を負いました。

タイトル	内容
ライフゲームについて	ライフゲームについて軽い説明と動機
そもそもGIF画像って何	GIF画像のバイナリ構造について解説
LZW圧縮ってなんやねん	GIFの圧縮方式について解説
LZW圧縮をC言語で実装しよう	LZW圧縮をC言語で実装します。ついでに画像に適した形に変形までします。
ライフゲームの場合	ライフゲームをGIF化する際の注意事項だけです。あとソースコードへのリンク
感想	感想
参考文献	参考文献

1. ライフゲームについて

ライフゲームって知ってますか？

ライフゲーム (Conway's Game of Life[1]) は1970年にイギリスの数学者ジョン・ホートン・コンウェイ (John Horton Conway) が考案した生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲームである。単純なルールでその模様の変化を楽しめるため、パズルの要素を持っている。

生物集団においては、過疎でも過密でも個体の生存に適さないという個体群生態学的な側面を背景に持つ。セル・オートマトンのもっともよく知られた例でもある。

まぁ、簡単な話が、シミュレーションゲームです。以下のルールに従って細胞が生まれたり死んだりします（いずれもwikipediaより）

誕生
　　死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
生存
　　生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
過疎
　　生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
過密
　　生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

という4つのルールに従って細胞が誕生したり、死滅したりします。条件分岐と配列のみでプログラムが書けることから、プログラミングの入門にはよく使われるようなイメージがありますね。実際東大ではアルゴリズム入門という授業で取り上げた（こっちはPython）と思ったら、ソフトウェア2というEEICの授業でも（こっちはC言語）扱われました。

Pythonの場合はその有り余るライブラリのパワーを存分に使って、比較的簡単にビジュアライズ出来るのですが、C言語の場合はそんな便利なものは存在しません¹。基本的にはこんな感じで、ターミナルにライフゲームのボードを出力して眺めることになります。

これはこれでありなんですが、2021年ともなれば、やっぱり画像か動画の形で見たくなるのが男の性[^2]。 **じゃあC言語でGIF画像作っちゃおうぜ！**というのが、この記事の主題になります。

2. そもそもGIF画像って何

GIF画像を作るとなれば、まずはGIF画像って何？ってところから調べないといけませんでした。GIF画像って何？って言われたらそれはまぁ「動かせる画像」なんですが、そうではなく、中身の話ですね。基本的に画像や動画といったファイルはバイナリデータ²の形で表されるのは知っていたので、fp = fopen(filename,"wb")みたいなことをしないといけないんだろうなぁ、みたいなことはわかってたのですが、バイナリデータとして何を書き込めばよいのかは全く知らなかったので、まずはそこからでした。文献リストは記事の最後に載せますが、大体10箇所くらいサイトをグルグル回りつつ、GIFのバイナリ構造についての知見を集めていきました。その結果、まぁ大体（アニメーションGIFの場合）こんな感じなんだなと言うことがわかりました。

大きなブロック名	コンテンツ	大きさ
GIF Header	Signature="GIF"	3byte
	Version = "89a"	3byte
	Logical Screen Width = 画像の横幅リトルエンディアン	2byte
	Logical Screen Height = 画像の縦幅リトルエンディアン	2byte
	色関連情報共通パレット存在フラグ:1bit 1画素のビット数:3bit 色のパレットがソートされているか:1bit 色の数:3bit	1byte
	背景色のインデックス	1byte
	ピクセルの縦横比（基本的には0）	1byte
	共通色パレットデータ	3byte*色数
Application Extensiton	ブロックであることを示す識別子＝ 0x21	1byte
	アプリケーション拡張ブロックであることを示す識別子 = 0xFF	1byte
	ブロック全体の大きさ = 11byte	1byte
	アプリケーションの識別名 = "NETSCAPE"	8byte
	アプリケーションのバージョン = "2.0"	3byte
	アプリケーションデータの大きさ = 3byte	1byte
	サブブロックのインデックス = 1	1byte
	繰り返し回数	2byte
	終了コード = 0	1byte
Graphic Control Extension	ブロックであることを示す識別子 = 0x21	1byte
	グラフィック拡張ブロックであることを示す識別子 = 0xf9	1byte
	ブロックサイズ = 4	4byte
	更新時動作予約部分 = 000 : 3bit 次のイメージを重ねるときの処理 = 3 : 3bit ユーザー入力を受けるか = 0 : 1bit 透過処理をするか = 0 : 1bit	1byte
	画像表示までの待ち時間	2byte
	透過色のインデックス = 0	1byte
	終了コード = 0	1byte
ImageBlock	ブロック識別子 = 0x21	1byte
	イメージブロック識別子 = 0xf9	1byte
	幅方向の始点座標 = 0	2byte
	高さ方向の始点座標 = 0	2byte
	画像幅リトルエンディアン	2byte
	画像高さリトルエンディアン	2byte
	色関連データ = 0 固有パレットがある場合は別ですが、今回は考えません。	1byte
	LZW最小コードのサイズ(詳しくは後ほど)-1	1byte
	ブロックサイズ = 画像データサイズ(1-255)	1byte
	LZW圧縮した画像データ	上で述べたサイズ分
	ブロック終了コード = 0	1byte
	以下、ブロックサイズと画像データを、画像データがすべて書けるまで続ける	...
以下、アニメーションにしたい画像分、Graphic Control ExtensionとImageBlockのペアを続ける
画像終了コード	0x3B	1byte

上から順に、ヘッダー部分でGIF画像であることを宣言し、画像全体に関連する画像サイズや、色の数、色の種類などについて取り上げます。その次に今回はアニメーションGIFにしたいので、拡張ブロックで、アプリケーションを定義し、グラフィックコントロールで、アニメーション時の動作について書きます。あとはイメージブロックで実際の画像データについて書いていけば終わりです。

色関連情報と、更新時動作については、上から順にビット列を並べて、1byteのサイズにしたものを入れてあげてください。あとは自分の作りたい画像データについて、各自で画像をこの形で文字列にして、バイナリに書き込めばGIF画像が生成されます。
とりあえずやってみたいんだ！って人は、これを実行してみてください。

giftest.c

#include <stdio.h>
#include <stdlib.h>

int main() {
  char width = 3, height = 3;
  char num = 4;
  unsigned char gifdata[70000] = {
      'G',  'I',  'F',   '8',  '9',    'a',  width, 0x00, height, 0x00, 0x91,
      0x00, 0x00, 0xb0,  0xc4, 0xde,   0xFF, 0xFF,  0xFF, 0xff,   0xc0, 0xcb,
      0xff, 0xff, 0xff,  0x21, 0xFF,   11,   'N',   'E',  'T',    'S',  'C',
      'A',  'P',  'E',   '2',  '.',    '0',  3,     1,    0,      0,    0,
      0x21, 0xF9, 4,     4,    10,     0,    0,     0,    0x2C,   0,    0,
      0,    0,    width, 0,    height, 0,    0x00,  2,    4,      0x84, 0x03,
      0x81, 0x51, 0x00,  0x2C, 0,      0,    0,     0,    width,  0,    height,
      0,    0x00, 2,     4,    0x44,   0x74, 0x09,  0x03, 0,      0x3B};
  FILE* fp;
  fp = fopen("my1stgif.gif", "wb");
  fwrite(gifdata, sizeof(unsigned char), sizeof(gifdata) / sizeof(gifdata[0]), fp);
  fclose(fp);
  return 0;
}

これを実行するとmy1stgif.gifが生成されて、こんな2枚の画像からなるGIF画像が見えるはずです。（画像サイズが小さいので、VSCodeなどで拡大して見ることをお勧めします。）

これで曲がりなりにもGIFの構造についてはなんとなくわかった…？

3. LZW圧縮ってなんやねん

ところがどっこい、さっきの説明でもわからない部分があります。それはLZW圧縮についてです。こんなふうになっていた部分が先のコードのGIFdataの中にあったと思います。

2, 4, 0x84, 0x03,0x81, 0x51

最初から順に最小lzwサイズ、サイズ、画像データ×4なのですが、そもそもlzwがわからんのでなんのこっちゃという話になります。

結論から言うと、LZWはGIFに用いられている圧縮方式です。昔は特許だったから勝手に使ったら怒られたらしいんですが、今は特許が切れて誰でも使えるようになっています。

どんな圧縮方式か、はこちらの記事が馬鹿みたいにわかりやすいので、僕が紹介するまでもないと思うのですが、ざっくり説明します。

まずLZW圧縮は、辞書データを用いた圧縮方式です。画像は各ピクセルごとに色を持つと思いますが、画像データはそのピクセルが何色か、を表します。
例えばこんな画像とカラーパレットがあったとしましょう。

インデックス	色
0	白 = #ffffff
1	黒 = #000000

画像

白白黒
黒白黒
黒黒白

この場合、画像データはこんなふうになります。

0 0 1
1 0 1
1 1 0

そして、これをまっすぐ一直線にしたデータ001101110が画像データです。
次に、辞書データを作成します。最初の辞書データは、こんな感じになります。ダミーが入っているのは、辞書データサイズはbitで定義され、順次拡張されていくのですが、0,1のみしか必要ない場合だとすぐに辞書データサイズを拡張することになるため、はじめから3bitの辞書で始めようというものです。ただし、開始コード・終了コードはGIF画像の圧縮時特有です。

値	キー
0	0
1	1
2	2 (ダミー)
3	3 （ダミー）
4	4（開始コード）
5	5（終了コード）
6
7

あとは圧縮データを前から順に見ていきます。存在していれば、辞書データの値を書き込みます。最長一致するキーを検索してください。もし、キーが存在しなくなった場合は、辞書データに追加します。
今回の場合

0→00（存在しないので00をキーとして登録する(7)、データは0で辞書データは3bit）
0→01（存在しないので01をキーとして登録する(8)、データは0で辞書データは3bit）
1→11（存在しないので11をキーとして登録する(9)、データは1で辞書データは4bit）
1→10（存在しないので10をキーとして登録する(10)、データは1で辞書データは4bit）
0→01→011（存在しないので011をキーとして登録する(11)、データは7で辞書データは4bit）
1→11→110（存在しないので110をキーとして登録する(12)、データは8で辞書データは4bit）
0(終わりなので0)

となって開始コードと終了コードを前後に足して、圧縮データは400117805となります。
次にこれらを、bit列に変換します。ただしこのときbitサイズは、その時点での辞書データサイズに依存します。つまりこんな感じです。

そして、上から順にbyte列に詰めていきます。ただしこのとき右詰めになることに注意してください。

00000100 -> 0x04
00100010 -> 0x22
00001110 -> 0x0b
10100001 -> 0xa1
00000000(最後は0埋めする) -> 0x00

あとはこれを順に書いていけば画像データの作成は完了します。

4. LZW圧縮をC言語で実装しよう

次に任意の数字列からLZW圧縮した結果を返すようなプログラムを作りましょう。僕は頭がそんなに良くないので愚直な方法をまずは実装します。
流れはこうです。

数字列を前から見る。
辞書にない数字列になったらそれを辞書に登録する
完成したら前後に開始コードと終了コードをつける
ビット列に変換
ビット列をバイト列に右詰めで変換
バイト列を16進数に変換

C++見たくmapがあれば辞書の検索や登録はすぐなんですがC言語にはありません。ここは検索のオーダーがO(N)になってしまいますが、ただのリストを作ることにしました。本当はmapを作りたかったんですが、赤黒木やらなんやらで課題の提出に間に合わせるためには妥協も必要と判断しました。

typedef struct node {
  char c[10];
  bool registerd;
} Node;

Node node_init(const char c[]) {
  Node node;
  strcpy(node.c, c);
  node.registerd = true;
  return node;
}

int node_find(Node* node, size_t size, char* value) {
  for (int i = 0; i < size; i++) {
    printf("%s == %s\n",node[i].c,value);
    if (strcmp(node[i].c, value) == 0) {
      return i;
    }
  }
  return -1;
}

void node_append(Node* node, size_t* size, char* value) {
  if (node_find(node, *size, value) == -1) {
    if (*(size)+1 >= MAX_NODE) {
      fprintf(stderr, "要素数が増えすぎました\n");
      return;
    }
    strcpy(node[*size].c, value);
    node[(int)*size].registerd = true;
    *(size) += 1;
  }
}

いっちょ前にnodeとかいう構造体作ってるけど、別にいらないんですよね。まぁそれに伴う関数がうまい感じに作れたのでヨシとしますが…
テストはこんな感じにしてやってみました。辞書に現れなくなるまで文字列を見ていき、現れなくなったら辞書に登録、最後を空文字にして、そのインデックスをデータに登録。みたいな流れです。無駄が多いですが、愚直に行くと決めたのでこれでﾖｼ。文字列の最後に行ったときだけ少しややこしいですね。

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX_NODE 70000
#define CODE_SIZE 100

int main(int argc, char* argv[]) {
  Node n[2000];
  n[0] = node_init("0");
  n[1] = node_init("1");
  n[2] = node_init("2");
  n[3] = node_init("3");
  n[4] = node_init("4");
  n[5] = node_init("5");
  size_t size = 6;
  char code[CODE_SIZE] = "000000000";//圧縮する文字列
  int ans[CODE_SIZE + 2];
  size_t anssize = 0;
  ans[0] = 4;
  for (int i = 0; i < strlen(code); i++) {
    char s[1000000];
    for (int i = 0; i < 1000000; i++) {
      s[i] = '\0';
    }

    int j = 0;
    s[0] = code[i];
    while (node_find(n, size, s) != -1) {//見つからなくなるまで探す
      if (i + j == strlen(code)) {
        break;
      }
      s[j] = code[i + j];
      j++;
    }
    if (i + j == strlen(code) && node_find(n, size, s) != -1) {//文字列の最後だったときの処理
      ans[anssize + 1] = node_find(n, size, s);
      ans[anssize + 2] = 5;
      anssize++;
      break;
    } else {
      i += strlen(s) - 2;
      node_append(n, &size, s);
      s[j - 1] = '\0';
      ans[anssize + 1] = node_find(n, size, s);
      anssize++;
    }
  }
  for (int i = 0; i < anssize + 2; i++) {
    printf("%d,", ans[i]);
  }
  printf("\n");
  return EXIT_SUCCESS;
}

ただ、これだとbit列に変換するときの辞書サイズがどこにも載っていないので、困ります。そこでこんな感じに改良します。

int node_find(Node *node, size_t size, char *value) {
  for (int i = 0; i < size; i++) {
    if (strcmp(node[i].c, value) == 0) {
      return i;
    }
  }
  return -1;
}

void node_append(Node *node, size_t *size, char *value) {
  if (node_find(node, *size, value) == -1) {
    if (*(size) + 1 >= MAX_NODE) {
      fprintf(stderr, "要素数が増えすぎました\n");
      return;
    }
    strcpy(node[*size].c, value);
    node[(int)*size].registerd = true;
    *(size) += 1;//サイズを常に追いかける
  }
}

  unsigned char bitsize[CODE_SIZE + 2];
  int bitlength = 3;
  bitsize[0] = bitlength;
  int ans[CODE_SIZE + 2];
  size_t anssize = 0;
  ans[0] = 4;
  for (int i = 0; i < strlen(code); i++) {
    char s[1000000];
    for (int j = 0; j < 1000000; j++) {
      s[j] = '\0';
    }
    int j = 0;
    s[0] = code[i];
    while (node_find(n, size, s) != -1) {
      if (i + j == strlen(code)) {
        break;
      }
      s[j] = code[i + j];
      j++;
    }
    if (i + j == strlen(code) && node_find(n, size, s) != -1) {
      ans[anssize + 1] = node_find(n, size, s);
      bitsize[anssize + 1] = bitsize[anssize + 2] = bitlength;
      ans[anssize + 2] = 5;
      anssize++;
      break;
    } else {
      i += strlen(s) - 2;
      node_append(n, &size, s);
      s[j - 1] = '\0';
      ans[anssize + 1] = node_find(n, size, s);
      bitsize[anssize + 1] = bitlength;
      if (size - 1 >= 1 << bitlength) {
        bitlength++; //辞書に登録後に、辞書サイズがビットサイズを超えていたらビット長を増やす。
      }
      anssize++;
    }
  }

これで圧縮後の数列のインデックスについてbitsizeの同じインデックスを見れば、その時の辞書サイズが分かるようになります。
あとは、これにあわせて更にビット列への変換、バイト列への変換、10進数への変換をやっていきます。

int returnnum(char buf[]) {//2進数文字データから十進数に変換
  int num = 0;
  for (int i = 0; i < 8; i++) {
    num += buf[i] * 1 << (7 - i);
  }
  return num;
}

char buf[8];
  int bufindex = 7;
  int imageboard[500];
  int imageindex = 0;
//まずbitに変換
  for (int i = 0; i < anssize + 2; i++) {
    int x = ans[i];
    char y[bitsize[i]];//辞書サイズ分の列を作る
    for (int j = 0; j < bitsize[i]; j++) {
      if (x & 1 << (bitsize[i] - 1 - j)) {
        y[j] = 1;
      } else {
        y[j] = 0;
      }
    }
    for (int j = 0; j < bitsize[i]; j++) {
      if (bufindex < 0) {  // bufが満杯
        imageboard[imageindex] = return0xnum(buf); //imageboardへの登録
        ++imageindex;
        bufindex = 7;
      }
      buf[bufindex] = y[bitsize[i] - 1 - j];//yからバイト列に右詰めで埋めていく。
      bufindex--;
    }
    if (i == anssize + 1) {
      for (int j = 0; j <= bufindex; j++) {
        buf[j] = 0; //0が必要な時用
      }
      imageboard[imageindex] = returnnum(buf);
      imageindex++;
    }
  }
  int num = imageindex;

これでimageboardには、必要な数列が入ります。imageindexをわざわざ取っているのは、lzw圧縮した後のバイト数をGIFにする際に残しておかないといけないからです。
これで、理論上2色のGIF画像ならなんでも作れるはずです。（ちなみに例で扱った極小GIF画像は4色です。）

あとはこれらを組み合わせてライフゲームなり、なんなりご自分の好きなデータをGIF化しちゃいましょう。

#5. ライフゲームの場合
ライフゲームの場合、盤面サイズが大体40×70とかなので、盤面情報をそのまま画像にすると、40×70のちっちゃいGIFアニメになります。なので、もっと大きな盤面でやるか、ないしは拡大の処理が必要です。拡大はある点に生き物がいたらそこを起点として縦横nマスの画像データを生きている判定にするみたいなことをやれば画像サイズはn倍になります。そこらへんはまぁ、ご自由にという感じですね。
で、最終的に出来上がったのがこちらになります（授業課題そのまんまだから間違い見つかると恥ずかしいね）。
https://github.com/yutyan0119/soft2-lifegame

#6. 感想
PhotoShopすげえが第一の感想
第二の感想はバイナリは沼だなぁです。
僕のLZW圧縮方式はまだまだ改善の余地はあるし、(mapの実装やbit変換など)もっと素早く出来ると思うんですが、時間制約上こんな感じになっちゃいますね。
同期のみんなはこれからこの記事を参考に面白いGIF画像を量産してくれることを期待しています。その時はこの記事へのリンクをREADME.mdによろしくね！

#7. 参考文献

他にツールを使えば別ですが。 ↩
人間に読むことは難しいただの数値データ。計算機が読み取るための0と1のみのデータだと思ってください ↩