C言語でGIF画像を作る（ライフゲームを強引にビジュアライズした話）

この記事は[EEIC2022 Advent Calender2021](https://adventar.org/calendars/6319)第23日目の記事として書かれました。:tada:
# はじめに
はじめまして、EEIC2022の[ゆーちゃん](https://twitter.com/yutyan_ut)です。学科のアドカレを[くらげくん](https://twitter.com/jellyfishrumble)が作ってくれたので折角ならということで参加してみました。 [某H君](https://twitter.com/decfrr)には自転車でズッコケて救急車で運ばれた話をアドカレにしろと言われてたのですが、折角なので、EEICっぽい記事を残そうと思います。
ちなみに自転車でズッコケて救急車で運ばれた話は[note](https://note.com)に書きました。
# この記事の目次
基本的には、僕がGIF画像を作ろうと思ったキッカケを話したあとはひたすらGIF画像の作り方について説明するつもりです。
なお、僕はGIF画像作成がかなりの茨の道であることを知らずに突っ込んだため、それなりに重症を負いました。
![lifegame.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597848/e92488a8-4063-aa2a-5d79-b57612bbc343.gif)
![readme1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597848/66e608fa-cf58-84b3-4640-48be26771b40.gif)

| タイトル| 内容|
|:-----------:|:------------:|
| [ライフゲームについて](#1-ライフゲームについて)|ライフゲームについて軽い説明と動機|
| [そもそもGIF画像って何](#2-そもそもgif画像って何)| GIF画像のバイナリ構造について解説|
| [LZW圧縮ってなんやねん](#3-lzw圧縮ってなんやねん)      |GIFの圧縮方式について解説        |
|[LZW圧縮をC言語で実装しよう](#4-lzw圧縮をc言語で実装しよう)        | LZW圧縮をC言語で実装します。ついでに画像に適した形に変形までします。          |
|[ライフゲームの場合](#5-ライフゲームの場合)| ライフゲームをGIF化する際の注意事項だけです。あとソースコードへのリンク|
|[感想](#6-感想)|感想|
|[参考文献](#7-参考文献)|参考文献|
# 1. ライフゲームについて
[ライフゲーム](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0)って知ってますか？
>ライフゲーム (Conway's Game of Life[1]) は1970年にイギリスの数学者ジョン・ホートン・コンウェイ (John Horton Conway) が考案した生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲームである。単純なルールでその模様の変化を楽しめるため、パズルの要素を持っている。
>
生物集団においては、過疎でも過密でも個体の生存に適さないという個体群生態学的な側面を背景に持つ。セル・オートマトンのもっともよく知られた例でもある。

まぁ、簡単な話が、シミュレーションゲームです。以下のルールに従って細胞が生まれたり死んだりします（いずれもwikipediaより）
>誕生
　　死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
生存
　　生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
過疎
　　生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
過密
　　生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

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

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

<img width="300" alt="lifegame.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597848/ee808e94-2be2-5784-4e6b-2072a9bccdc6.png">
これはこれでありなんですが、2021年ともなれば、やっぱり画像か動画の形で見たくなるのが男の性[^2]。
**じゃあC言語でGIF画像作っちゃおうぜ！**というのが、この記事の主題になります。

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

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

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

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

```c: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などで拡大して見ることをお勧めします。）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597848/f16eefc5-2231-f507-8a9d-c5ef9e53a73c.png)![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597848/7e29670c-8887-f2ba-f932-08468122f626.png)
これで曲がりなりにもGIFの構造についてはなんとなくわかった…？

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

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

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

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

どんな圧縮方式か、は[こちらの記事](https://www.petitmonte.com/math_algorithm/lzw_gif.html)が馬鹿みたいにわかりやすいので、僕が紹介するまでもないと思うのですが、ざっくり説明します。

まず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サイズは、その時点での辞書データサイズに依存します。つまりこんな感じです。

```
4 → 100
0 → 000
0 → 000
1 → 0001
1 → 0001
7 → 0111
8 → 1000
0 → 0000
5 → 0101
```
そして、上から順にbyte列に詰めていきます。ただしこのとき右詰めになることに注意してください。

```
00000100 -> 0x04
00100010 -> 0x22
00001110 -> 0x0b
10100001 -> 0xa1
00000000(最後は0埋めする) -> 0x00
```
あとはこれを順に書いていけば画像データの作成は完了します。

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

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

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

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

```c
#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列に変換するときの辞書サイズがどこにも載っていないので、困ります。そこでこんな感じに改良します。

```c
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進数への変換をやっていきます。

```c
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
![lifegame.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597848/e92488a8-4063-aa2a-5d79-b57612bbc343.gif)
![readme1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597848/66e608fa-cf58-84b3-4640-48be26771b40.gif)

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

#7. 参考文献

- [GIF公式document](https://www.w3.org/Graphics/GIF/spec-gif89a.txt)
- [GIFのバイナリを読んでみた from Qiita](https://qiita.com/7shi/items/33117c6c369d37dc6cdd)
- [GIF画像ファイルフォーマット from 略して仮](http://menyukko.ifdef.jp/cauldron/dtgifformat.html)
- [LZW圧縮アルゴリズム\[実践的なGIFファイルの作成\] from プチモンテ](https://www.petitmonte.com/math_algorithm/lzw_gif.html)
- [GIF from wikipedia (英語版)](https://en.wikipedia.org/wiki/GIF#File_format)
- [GIFフォーマットの詳細 from とほほのWWW入門](https://www.tohoho-web.com/wwwgif.htm#ApplicationExtension)


[^1]: 他にツールを使えば別ですが。
[^2]: ここでの男の性は別に男がどうとか決めてかかってるわけじゃないからね
[^3]: 人間に読むことは難しいただの数値データ。計算機が読み取るための0と1のみのデータだと思ってください