Gitはsha1の計算をどのようにやっているのか

2013/10/06

echo 'hello' > hello.txt
git add hello.txt

こうすると、hello.txtの中身が圧縮されて

.git/objects/ce/013625030ba8dba906f756967f9e9ca394464a
というファイル名でレポジトリに保存されます。

この"ce013625030ba8dba906f756967f9e9ca394464a"という40文字の文字列がhello.txtに対するsha1ハッシュ値です。

sha1ハッシュ値の計算方法

一言でいうと「ヘッダとデータをつなげたバイト列をハッシュ関数によってハッシュする」です。

ここで「データ」というのは実際のファイルの中身のことです。このケースでは"hello\n"というバイト列です。

ヘッダというのは「<オブジェクト型><半角スペース><データサイズ>」からなる文字列です。
オブジェクト型には"blob","tree","commit"などがあり、上記のケースでは"blob"型になります。
データサイズは"hello\n"というバイト列のバイトサイズなので"6"となります。
よって、ヘッダ部は"blob 6"となります。

ヘッダ部とデータ部は"\0"で連結されますので、「ヘッダとデータをつなげたバイト列」は

"blob 6\0hello\n"

というものになります。
このバイト列をハッシュ関数にわたすことでsha1ハッシュ値が計算されます。

手動でsha1を計算して確かめる

Linuxで下記のようにすれば、実際にsha1を計算することができます。

$ echo -n "blob 6\0hello\n"  | openssl sha1
(stdin)= ce013625030ba8dba906f756967f9e9ca394464a

ごらんのとおり、git addが生成したのと同じsha1ハッシュ値を得ることができました。

ハッシュ値の計算はどこで行われているのか？

ソースコードを見て確かめてみましょう。
sha1ハッシュ値の計算はsha1_file.cのwrite_sha1_file_prepare関数で行われています。
https://github.com/git/git/blob/v1.8.4/sha1_file.c#L2672

static void write_sha1_file_prepare(const void *buf, unsigned long len,
                                    const char *type, unsigned char *sha1,
                                    char *hdr, int *hdrlen)
{
	git_SHA_CTX c;

	/* Generate the header */
	*hdrlen = sprintf(hdr, "%s %lu", type, len)+1;

	/* Sha1.. */
	git_SHA1_Init(&c);
	git_SHA1_Update(&c, hdr, *hdrlen);
	git_SHA1_Update(&c, buf, len);
	git_SHA1_Final(sha1, &c);
}

hdrがヘッダーを表すバイト列(おそらくheaderの略)、bufがデータ部を表すバイト列です。
git_SHA1_Final()を呼び出すとsha1変数にハッシュ値がセットされます。

git_SHA1_*系の関数の中身は、OpenSSLのライブラリを単に呼び出しているにすぎないようです。
続きはこちら
Gitのsha1ハッシュ値計算をC言語で実装してみた

参考

Gitのハッシュ値計算とコンテンツ管理の仕様についてはこちらの本に詳しく書いてあるのでオススメです。
Gitの開発者ご本人が書かれた本なので内部構造について詳しい解説があります。

カテゴリ: Git