Adler-32
出典: フリー百科事典『ウィキペディア(Wikipedia)』
Adler-32 は、Mark Adler が考案したチェックサムアルゴリズム。同じ長さの巡回冗長検査と比較すると、信頼性と引き換えに高速性を追求している。その元となった Fletcher-16 に比較すると信頼性が高いが、Fletcher-32 に比較すると若干信頼性が劣る[1]。
目次 |
[編集] 歴史
Adler-32 はフレッチャーのチェックサムを修正したものである。
同じく Mark Adler が開発したzlib圧縮ライブラリの一部として使われている。Adler-32 に基づくローリングチェックサムが rsync で使われている。
[編集] アルゴリズム
Adler-32 チェックサムは、まず2つの16ビットのチェックサム A と B を計算し、それらを連結して32ビットの整数にする。Aは全てのバイトの総和に1を加えた値、B は A を計算している各ステップの値を累積した総和である。
初期状態では、A は 1 に初期化され、B は 0 に初期化される。これらの総和は modulo 65521 で保持される(65521 は 216 未満の最大の素数)。これらのバイトはネットワークオーダー(ビッグエンディアン)で格納され、B が最上位バイト側に位置する。
式で表すと、以下のようになる。
A = 1 + D1 + D2 + ... + Dn (mod 65521) B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521) = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521) Adler-32(D) = B × 65536 + A
ここで D はチェックサム計算対象のバイト列の各バイトを意味し、n はバイト数を意味する。
[編集] 例
ASCII文字列 "Wikipedia
" のAdler-32チェックサムは以下のように計算される。
ASCIIコード A B (基数10で示す) W: 87 1 + 87 = 88 0 + 88 = 88 i: 105 88 + 105 = 193 88 + 193 = 281 k: 107 193 + 107 = 300 281 + 300 = 581 i: 105 300 + 105 = 405 581 + 405 = 986 p: 112 405 + 112 = 517 986 + 517 = 1503 e: 101 517 + 101 = 618 1503 + 618 = 2121 d: 100 618 + 100 = 718 2121 + 718 = 2839 i: 105 718 + 105 = 823 2839 + 823 = 3662 a: 97 823 + 97 = 920 3662 + 920 = 4582 A = 920 = 398 hex (base 16) B = 4582 = 11E6 hex Output = 300286872 = 11E60398 hex
この例では、総和が65521を超えることがないため、modulo演算は特に意味がない。
[編集] フレッチャーのチェックサムとの比較
1つめの違いは、Adler-32では素数の modulo を使って計算している点で、フレッチャーの場合は使うビット数に応じて modulo 24-1, 28-1, 216-1 を採用している(これらは合成数である)。素数を使うことで、フレッチャーのチェックサムでは捉えられないバイト列の違いを捉えられることがある。
2つめの違いはアルゴリズムの高速性に関連するもので、Adler-32 では16ビットワード単位ではなく8ビットバイト単位で計算するため、ループ回数が2倍になる。このため16ビット境界に整列されたデータでは、フレッチャーのチェックサムの1.5倍から2倍の時間がかかる。ただし、バイト単位に整列されたデータでは、Adler-32 は普通に実装されたフレッチャーのチェックサムよりも高速である。
[編集] 実装例
C言語での最適化実装例を以下に示す。
#define MOD_ADLER 65521 uint32_t adler(uint8_t *data, size_t len) /* data: 対象データへのポインタ; len: バイト数 */ { uint32_t a = 1, b = 0; while (len > 0) { size_t tlen = len > 5550 ? 5550 : len; len -= tlen; do { a += *data++; b += a; } while (--tlen); a %= MOD_ADLER; b %= MOD_ADLER; } return (b << 16) | a; }
効率化のためにいくつかトリックが用いられている。
- 最も重要な点は、総和の一時格納変数として32ビット整数が使われている点で、これによって modulo 65521 を行う回数を減らしている。modulo 65521 は総和がオーバーフローする前に行う必要がある。
- マジックナンバー 5550 は
b
がオーバフローしない最大の反復(加算)回数である。これより小さい数でも大丈夫なので、場合によっては 4096 の方が便利である。a
の反復回数の上限は RFC によれば 5552 より若干小さい。5550 が安全であることの証明(5551 では安全ではないことの証明)は少々難解だが、内側のループに入るときのa
の最大値が0x1013a
であることを示すところから始まる。
[編集] 長所と短所
- CRC-32と同様、Adler-32チェックサムも容易に偽造できるため、改ざんに対するプロテクトとして用いるのは安全ではない。
- CRC に比較してソフトウェアで実装したとき高速である。
- 数百バイト程度の短いメッセージでは、チェックサムの32ビット全体を使うことがないため、Adler-32 は脆弱とされている。2001年に Jonathan Stone が指摘した。128バイトのメッセージでは A の最大値は 32640 であり、65521 を超えない。このため RFC 3309 ではSCTPでAdler-32の代わりにCRC-32を使うことを指示している。