Posted on 2025-12-11:: OS 低レイヤ

この記事は理情 Advent Calendar 2025 11日目の記事です。

はじめに

東京大学理学部情報科学科3年のLLUUIIGGEEと申します。今回はAdvent Calendarの記事として、授業の一環で作ったOSにGIF画像ファイルを描画する機能を実装した話をしたいと思います。

理学部情報科学科では、3Sセメスターに「システムプログラミング実験」（通称シスプロ）という実験が行われます。C言語での低レイヤのプログラムを書くことを通して、現代のコンピュータ技術を支えるOSやハードウェアを理解しようという授業です。

学期の前半ではシステムコールの仕組みやシェルの実装方法などを実装を通して学び、後半（OS演習）ではOSを実際に作ってみようということをします。もちろんいきなり一人では作れないので、TAの方が用意してくれた最低限の骨組みに、肉付けをしていく形でOSの機能を実装していきます。

OS演習では、以下のスケジュールで機能の追加をしていきました。

第1週画面への描画、出力関数(putchar, putsなど)、タイマ割り込み
第2週ページアロケータ
第3週 syscall、プロセススケジューリング
第4週ページング、fork
第5週プロセス間通信、排他処理
第6週ファイルシステム

最後の週の実装が終わり最低限必要な機能がそろったということで、夏休みを使ってこのOS（ISOSと呼ぼう）にGIF画像描画機能を追加しました。

なぜGIFなのか

世の中には様々な画像フォーマットがあります。広く使われているのは、JPEG、PNG、GIF、ベクター画像ではSVGではないでしょうか。その中でGIFは、メモリをあまり使わず、圧縮アルゴリズムが簡単すぎず複雑すぎないちょうどいいフォーマットだったので、GIFを選びました。またGIFはアニメーションにも対応しているので、将来的にはアニメーションを流したいという野望もありました。

GIFの描画

ここからが本題のGIF画像の描画についてです。GIFファイルのバイト列から画面に描画するまでの処理として、以下の3つがあります。

ファイルシステムからファイルを読み込み、ヘッダーからメタデータ（GIFのバージョンや解像度、カラーテーブルなど）を取得
圧縮ピクセルデータを展開
ピクセルデータを画面に描画

それぞれの処理を、簡単なものから紹介します。

3. ピクセルデータを画面に描画

第3段階の画面への描画ですが、これが一番簡単です。配列からピクセルを読み取っていって、フレームバッファに書き込んでいくだけです。

画面への描画は第1回で扱うのですが、実はピクセルデータを配列でプログラムに埋め込んでおけばもう画像の描画ができます。実際、そのあたりで既に絵を描いている人たちがいました。

1. ファイルのメタデータを取得

次に簡単なのが、第1段階のファイルフォーマットに従ってファイルをパースする部分です（というか、展開が面倒くさすぎる）。ちょうど、セキュリティキャンプの応募課題でext4イメージファイルのパースをさせられたので、ここではそれが活きました。

いきなりですが、GIFを読んでみましょう。 LLUUIIGGEE をhexdumpしてみると、以下のような出力が得られます。

00000000  47 49 46 38 37 61 10 00  10 00 81 00 00 ff ff ff  |GIF87a..........|
00000010  ff c8 af 00 ff ff 00 af  4b 2c 00 00 00 00 10 00  |........K,......|
00000020  10 00 40 08 68 00 05 08  1c 48 70 60 80 83 02 07  |..@.h....Hp`....|
00000030  28 54 08 60 61 c3 82 09  03 0c 38 28 f1 e0 42 01  |(T.`a.....8(..B.|
00000040  01 04 0c 00 c0 b1 a3 47  85 05 3d 8a 44 38 50 21  |.......G..=.D8P!|
00000050  45 89 0b 07 60 44 99 52  64 42 8d 0c 45 02 80 18  |E...`D.RdB..E...|
00000060  d2 a3 40 8a 05 17 5a cc  78 b1 24 4a 8a 13 2d 42  |..@...Z.x.$J..-B|
00000070  3c 09 b4 64 4a 86 0e 23  22 e4 b8 11 40 00 8e 4f  |<..dJ..#"...@..O|
00000080  41 c2 6c 2a b3 a1 4a 95  02 6c d2 0c 08 00 3b     |A.l*..J..l....;|
0000008f

冒頭にGIF87aという文字列があるので、これが87aというバージョンのGIFファイルであることが分かります。そのあとに10 00 10 00と続いていますが、2×2ビットで画像サイズを表しています。リトルエンディアンなので、16×16の画像であることが分かります。

このようにして、1バイトずつ読み取って画像のメタデータを取得していきます。Wikipediaの英語版記事にGIFファイルの例があったので、それを参考にして作りました。

2. 圧縮データの展開

圧縮されたデータを展開する処理です。これが最も重く、今回の記事で主に説明する部分になります。

GIF画像は、Lempel–Ziv–Welch(LZW)というアルゴリズムにより圧縮されています。LZWは辞書式圧縮に分類される圧縮アルゴリズムで、バイト列から圧縮コードへの辞書を作成し、その辞書をもとに圧縮を行います。Wikipediaの例のように、TOKYOTOKKYOKYOKAKYOKUという文字列を圧縮すると、最終的には以下のような辞書が作られます。

文字列	コード
`A`	`00000`
`B`	`00001`
...	...
`Z`	`11010`
`TO`	`11011`
`OK`	`11100`
`KY`	`11101`
`YO`	`11110`
`OT`	`11111`
`TOK`	`100000`
`KK`	`100001`
`KYO`	`100010`
`OKY`	`100011`
`YOK`	`100100`
`KA`	`100101`
`AK`	`100110`
`KYOK`	`100111`
`KU`	`101000`

圧縮コードは辞書を参照して出力されますが、ポイントなのが、出力がこの辞書を作成しながら行われるということです。先ほどの例で言うと、初期状態の辞書にはA～Zまでしか登録されていないので、最初のTOKはまだ辞書になく、Tに対応する10100が出力され、TOが辞書に登録されます。

なぜこのようなことをするのかというと、展開する側が、辞書を知らなくても正確に展開できるようにするためです。展開の際には、圧縮の際に使用した辞書を復元する必要がありますが、LZWでは辞書を添付しないので、圧縮コード列だけを見て辞書を復元しなければなりません。そこで、圧縮でも展開でもデータを読み取りながら辞書を作成するようにしようというのが、LZWのアイデアになります。辞書を送らないことで、ファイルサイズの削減を実現しています。

LZWの詳細なアルゴリズムについては、この記事では解説しません。興味がある方は、私が参考にしたサイトのリンクを置いておくので、ぜひ参考にしてください。

メモリアロケータ

ここからISOSに固有の話をしていきます。

展開に使う辞書は、圧縮に使う辞書と逆で、コードからバイト列への辞書となります。辞書のエントリ数は8～4096まで動的に変化します。また、辞書の値となるバイト列については長さに制限がなく、事前にどのくらいのメモリが必要かが分からないため、動的なメモリ管理が必要になります。

ところで、ISOSに実装されているメモリアロケータはページアロケータしかありません。ページとはOSがメモリを管理する単位であり、4KiB~2MiBの二冪のサイズしか確保することができません。高々長さ数百のバイト列を格納するためにいちいち4KiBのページを確保していたら内部断片化が甚だしいですよね。これは非効率的なので、小さいサイズのメモリアロケータが必要になります。

現在様々なメモリアロケータが考案されており、用途によって使い分けられています。その中で、私はbump allocatorというアロケータを実装しました。

bump allocator

bump allocatorは最もシンプルなメモリアロケータです。用意された領域の先頭から要求された分だけ領域を割り当てていき、割り当てたすべての領域が解放されてはじめて状態をリセットすることで再利用できるという仕組みで動きます。（参考：Writing an OS in Rust）

bump allocatorを採用した理由としては、手を抜きたかったからが一番なのですが、さらに手を抜いて、解放処理を一切行わないことにしました。

以下がbump allocatorの実装です。

struct BumpAllocator {
    void *(*alloc)(Allocator *, u64);       // 確保関数のポインタ
    void (*dealloc)(Allocator *, void *);   // 解放関数のポインタ
    int order;                              // 確保した領域のサイズ (1<<(order+12))
    void *area_top;                         // ページアロケータから確保した領域の先頭
    void *alloc_top;                        // 未割り当て領域の先頭
    u64 rest_size;                          // 未割り当てサイズ
};

Allocator* new_bump_allocator(int order) {
    struct BumpAllocator* allocator = (struct BumpAllocator*)alloc_pages(order); // ページアロケータから確保
    if (allocator == NULL) {
        return NULL;
    }
    allocator->alloc = (void* (*)(Allocator*, u64))alloc_from_bump;
    allocator->dealloc = (void (*)(Allocator*, void*))dealloc_from_bump;
    allocator->order = order;
    allocator->area_top = (void*)allocator + sizeof(struct BumpAllocator);
    allocator->alloc_top = allocator->area_top;
    allocator->rest_size =
        (1 << (12 + allocator->order)) - sizeof(struct BumpAllocator);

    return (Allocator*)allocator;
}

void delete_bump_allocator(Allocator* allocator) {
    struct BumpAllocator* ballocator = (struct BumpAllocator*)allocator;
    free_pages((void*)ballocator, ballocator->order); // 確保した領域を解放
}

void* alloc_from_bump(Allocator* allocator, u64 size) {
    struct BumpAllocator* ballocator = (struct BumpAllocator*)allocator;
    void* res = NULL;
    size = ((size - 1) / 8 + 1) * 8;
    if (size <= ballocator->rest_size) {
        res = ballocator->alloc_top;
        ballocator->alloc_top += size;
        ballocator->rest_size -= size;
    } else {
        puts("lack of area...\n");
    }

    return res;
}

void dealloc_from_bump(Allocator *allocator, void *buf) {} // 何もしない

ところで、これらの関数はstruct BumpAllocatorではなくAllocatorという型をやり取りしています。これは何でしょうか。

実装したbump allocatorはとても頭の悪いアロケータです。そこで、後々賢いメモリアロケータを実装した際にどのアロケータを使うか指定できるよう、GIFをパースするときに使うメモリアロケータを引数で渡せるようにしました。このときに使われる、メモリアロケータ全体を指す型がAllocatorです。

Allcatorの定義はこのようになっています。

typedef struct Allocator {
    void *(*alloc)(struct Allocator *, u64);
    void (*dealloc)(struct Allocator *, void *);
} Allocator;

Allocatorは要件として、要求されたサイズを確保するallocと、アロケータから確保した領域を解放するdeallocの二つのメソッドを持っていることが求められます。（つまり、AllocatorはRustでいうtraitになっているということですね、他の言語でいうとinterfaceでしょうか）

Allocatorのallocとdeallocを呼び出してくれるalloc関数とdealloc関数を作ったので、それに突っ込めば確保と解放をしてくれます。

void* alloc(Allocator* allocator, u64 size) {
    return allocator->alloc(allocator, size);
}
void* dealloc(Allocator* allocator, void* buf) {
    allocator->dealloc(allocator, buf);
}

// このように呼び出せる
Allocator *allocator = (Allocator *)new_hoge_allocator(...);
void *buf = alloc(allocator, size);
dealloc(allocator, buf);

（本当はallocator->alloc(size)のように呼び出したかったのですが、関数にallocator自身を渡さないと処理ができないため、しかたなく上のような形にしました）

辞書の表現

話がそれてしまいましたが、LZWの展開に話を戻します。

辞書自体や辞書の値のサイズが動的に変化するため、動的メモリ確保が必要という話でした。メモリアロケータを実装したので、そこから確保した領域を辞書とし、そこにバイト列のポインタを格納していけば辞書が表現できそうです。

しかし、実は辞書に入る値はバイト列だけではなく、値がないことを表す値や、辞書に関する特別な操作を指示する命令などが入ります。具体的に定義すると、

enum Entry {
    NODATA = 0,     // 値がない
    DATA = 1,       // バイト列
    CLR = 2,        // 辞書の初期化
    END = 3,        // コードの終端
};

の4つがあります。NODATAやDATAは分かりやすいと思いますが、CLRは辞書の初期化を指示し、ENDはコードがそこで終わりであることを表します。

配列を付随データとして持つのはDATAのみなので、なんとかうまくアドレスを埋め込みたいな～という気持ちになります。ここで、bump allocatorの返すアドレスが8の倍数であることを利用します。アドレスの下位3ビットは必ず0なので、このうち下位2ビットを使って辞書の値がEntryの中のどれに該当するかを格納します。

辞書の例を示すと以下のようになります。

code	value	Entry	(data address)
...	...	...	...
`255`	`0x4001`	DATA	`0x4000`
`256`	`0x2`	CLR	`------`
`257`	`0x3`	END	`------`
`258`	`0x4019`	DATA	`0x4018`
`259`	`0x0`	NODATA	`------`
...	...	...	...

このようにすると、Rustで表現すると

enum Entry {
    NODATA,
    DATA(Vec<u8>),
    CLR,
    END,
}

という型が表現できるようになります。

また、バイト列についても、アドレスが格納されているだけではその長さが分からないため、最初の2バイトでそのあとに続くバイト列の長さを表すようにしました。最初は1バイトで長さを表していましたが、大きなファイルだと長さが255を超えるようなバイト列が出現するため、2バイトに変更しました。

あとは展開アルゴリズムを頑張って実装すれば、ピクセルデータを得ることができます。

できたもの

使用した画像

アニメーション

しれっとルイージが走ってますが、そうです、アニメーションにも対応させました。動画も画像の集まりなので、一枚ずつ読み込んでいって速い速度で書き換えればアニメーションになります。

一枚だけの画像と変わる部分は、それぞれの画像に異なるカラーテーブルが割り当てられる可能性があること、前後で差分がある範囲だけ書き換える機能があることです。これらについても、GIFの仕様に従って処理すれば実装できます。

現在ISOSで行っている処理としては、すべての静止画を読み込んだ後にビジーループで描画するということをしています。アニメーション画像を描画すると描画関数から帰ってこないため、現状ではアニメーション画像は一枚しか描画できません。せっかくタイマ割り込みがあるので、描画対象画像をキューか何かで保持しておいて、定期的に画面の書き換えを行う、ということが実現できればな、という風に思っています。

`syscall_gifdraw`

この記事のリンクにも含まれていますが、GIFファイルをパースして画面に描画する処理をシステムコール化したので、ユーザーアプリからもGIF描画機能を呼び出すことができます。

int syscall_gifdraw(const char *path, unsigned long long left, unsigned long long top);

インターフェースはこのようになっていて、パスと座標を指定することで画像を表示してくれます。システムコール番号はもちろん0x91fです。

おわりに

ここまで読んでくださり、ありがとうございました。GIFを描画する話のはずですが、ほとんどメモリアロケータの話をしていたような気がします。まぁしかし、特に書きたかったのはその部分なので、大目に見てもらえると嬉しいです。賢いメモリアロケータを実装するなら、Glibcのmalloc/freeで使われているアルゴリズムのうち、tcache binsとunsorted binsを採用したものになるかなと思っています。

今回は授業で扱ったOSを改造したわけですが、授業の課題で作ったものまでだと、他の人とほとんど同じもので終わってしまいます。ですが、OSに独自の機能を追加していると、自分だけのOSをつくっているという全能感が感じられ、とても気持ちが良いです。

ISOSには、まだ遊ぶ余地が残っています。もっと大きいユーザープログラムを実行できるようにしたり、GUIやネットワーク機能を実装したり、など夢は広がります。

最後に、私の最大の夢は自分で作ったOSを自分で攻撃することです。弱い相手をボコしても面白くありません。夢を叶えるため、ツヨツヨOSとなるような機能を追加していきたいと思っています。