Help us understand the problem. What is going on with this article?

Gitはどうやってテキストファイルとバイナリファイルを自動識別しているのか?

More than 1 year has passed since last update.

tl;dr

先頭 8000 バイト以内に NUL が有ったらバイナリファイル。

Gitの実装

Gitの内蔵diffは FIRST_FEW_BYTES だけ検索するようになっている。

#define FIRST_FEW_BYTES 8000
int buffer_is_binary(const char *ptr, unsigned long size)
{
    if (FIRST_FEW_BYTES < size)
        size = FIRST_FEW_BYTES;
    return !!memchr(ptr, 0, size);
}

8000 ?

なんで8192とかじゃないんだろうか。この数値はGitが自前のdiffを備えた当初から8000に設定されている。

#define FIRST_FEW_BYTES 8000
static int mmfile_is_binary(mmfile_t *mf)
{
    long sz = mf->size;
    if (FIRST_FEW_BYTES < sz)
        sz = FIRST_FEW_BYTES;
    if (memchr(mf->ptr, 0, sz))
        return 1;
    return 0;
}

(前掲した現状のコードでは memchr の返値を !! でブール値にして返しているが、最初は return 1return 0 の分岐だったようだ。)

このコミットログでは、

  • Detect and punt binary diff like GNU does;

のように書かれていて、この手法がGNU diffに由来することがわかる。

GNU diff

GNU diffで現在の形のアルゴリズムが導入されたのは'92年に遡る。

-static int
-binary_file_p (buf, size)
-     char *buf;
-     int size;
-{
-  while (--size >= 0)
-    if (!textchar[*buf++ & 0377])
-      return 1;
-  return 0;
-}
+#define binary_file_p(buf, size) (memchr (buf, '\0', size) != 0)

それまではprintableな文字かどうかを気にした実装だったが、急にゼロを検索する現在の形に替えている。

ちなみに、直後にGNU創始者であるリチャード・ストールマンは標準準拠でない memchr 実装を気にしたのか size!=0 のチェックを追加しているが、 このコードは結局元に戻されていて現存しない のはちょっと面白い。

-#define binary_file_p(buf, size) (memchr (buf, '\0', size) != 0)
+#define binary_file_p(buf, size) (size != 0 && memchr (buf, '\0', size) != 0)

libgit2

ちなみにlibgit2も当初は以前のGNU diffのようなprintableな文字かどうかを気にした実装になっていたが、今はGit互換のアルゴリズムを採用している。

...そもそも何で最初は真面目にprintable判定をしたんだろうか。

妥当性

このアルゴリズムの問題は NUL が無いバイナリファイルを検出できない点となる。 ...そんなもん普通は無いだろうと言って良い気もする。そういうファイルを救おうとしてprintable判定を入れると、今度はUTF-8テキスト等をバイナリとして誤判別する可能性がある。

逆に、バイナリフォーマットを設計するときは意図的に NUL を入れるべきなのかもしれない。この目的で NUL を採用しているフォーマットはあんまり無い気もするが、例えば PNGは必ずIHDRチャンクから始まるためファイルの先頭にNUL文字が常に入る ことになる。同様に、executableの類もファイル内部に大抵ポインタの形で適当な数値を持っていてゼロに近い値が入るだろうし、圧縮ファイルであればランダムデータになるのでそれなりの確率でゼロが来ることが期待できる。

UTF-16とかは。。まぁ使わないで。。

okuoku
ゲーム会社だけどゲームは作ってない。
https://mjt.hatenadiary.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした