MPEG2 TSのCRC32を計算する

PegasysのTMPGEnc MPEG Editor 3。いろいろショボい点は多いのだけど，他によい選択肢がないので，未だに使い続けている。

今を遡ること約2年半前，「WOWOW2のTS」という記事を書いた。標準画質のWOWOW2を録画したTSファイルを，「TMPGEnc MPEG Editor 3」(TME3)で読み込めない問題について調査した結果をまとめたものだ。この記事の最後で，CRCの計算方法についての記事を後日書くとしているのだが，すっかり忘れていて，書いていなかった。実は，これと同じように，続編を書くつもりでいて忘れている記事はいくつかあるのだ。完結していないのは，個人的にも気持ちが悪いのだが，時間の経過とともに何をどうしたのかも忘れてしまうので，思い出しながら書くのはかなり骨である。それで，自分で気が付いても，ついついほったらかしにしてしまう。そのうち，自分で必要になった時に考えればいいか，という調子だ。しかし最近，コメントで問い合わせを受けたので，重い腰を上げて再調査することにした。

件の記事では，TME3で読み込めるようにするため，最終的にTSファイルを書き換えるプログラムを作成した。その時に問題となったのが「CRC」。CRCというのは，"Cyclic Redundancy Check"の略で，日本語だと「巡回冗長検査」とかいうらしい。対象となるデータ全体から，あるアルゴリズムで算出される値で，通信路などでデータが化けてしまっていないかをチェックするのに利用される。TSファイルのデータ構造の単位である「セクション」には，CRC32という32ビットのCRC値が含まれているため，セクションのデータを書き換えたら，CRC値もそれに合わせて書き換えなければいけない。となると，どうやって計算すれば良いかを調べる必要がある。しかし，「トラ技2008年11月号」にも，「CRC32」と書かれているだけで，詳しいことは載っていない。

CRCなんて所詮チェックサムだろう，なんて高をくくって，セクションのデータを4バイトずつに分割して，全部足してみたりしたのだが，全く一致しない。CRC値と足して0になる訳でもない。もしかしてとんでもない勘違いをしている?

でWebを検索してみると，Wikipediaになにやら難しいことが書いてある。CRC32といってもいくつか種類があるようだが，MPEG2と書かれているのはこちら。

CRC-32-IEEE 802.3

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

0x04C11DB7 / 0xEDB88320 (0x82608EDB)

何この変な多項式は。そして，「0x04C11DB7」という16進数との関係は? ちょっと考えて，この多項式が，「0x4C11DB7」で「1」が立っているビット位置を表しているらしいことが分かった。でも，x³²に対応するビットが立っていないし。はて。

分かってきたのは，CRCが，対象のデータをある定数で割った余りなのだということ。その定数を表しているのが多項式。定数は，CRCのビット数より1つ大きいビット数のもので，最上位ビットは必ず1になる。そうでないと有効ビット数が小さくなってしまうからだ。32ビットのCRCの場合は33ビット。16進数で表すと「0x104C11DB7」になるのだが，最上位ビットは常に1になるので，省略するらしい(あとで考えると，計算上不要だからという理由もあるのだろう)。

ということで，要はセクションのデータ全体を巨大な整数値だと考えて，「0x104C11DB7」で割った余りを求めれば，それがCRC値ということのようだ。では，どうやって割り算を実行するのかというと，Wikipediaによれば，10進数の割り算を筆算で求める要領でやるらしい。ただし，2進数のレベルで，「2を法として」計算するというのがポイント。

筆算の割り算を言葉で説明するのは面倒(HTMLで絵を描くのも難しいが)だが，およそ次のような手順になるだろう。まず，割られる数(被除数)の上位の桁から，割る数(除数)以上になるように何桁かを取って，それを除数で割って，1から9の答と余りを求める。余りは被除数の残りの部分と連結し，これを新たな被除数として割り算を繰り返す。最後，被除数が除数より小さくなったら終了。それが全体の計算の余りとなる。

これを2進数で考えると，途中の割り算の答は0か1しかない。さらに，「2を法とする」ということは，「0-1=-1=1」になることを意味している。つまり，ふつうだと，「1010」は「1111」より小さいので引けない(答が負になる)が，2を法とする場合は引くことが出来て，正の値，「0101」が答になる。すなわち，2を法とする2進数の割り算では，桁数が同じ2進数の場合，その大小に関わらず答は必ず1となる。そしてその余りは，被除数から除数を引いたものになる。桁単位の引き算の組み合わせは4通りで，

被減数	減数	答
0	0	0
0	1	1
1	0	1
1	1	0

となる。これはビット単位で排他的論理和(XOR)を実行した時と同じ結果だ。つまり，2を法とする2進数の引き算は，XOR演算で代用できることが分かる。

以上をまとめると，2を法とする2進数の割り算の筆算は，被除数の1となる最上位の桁に合わせて，下に除数を書き，桁毎にXORした結果(余り)と，被除数の残りの桁を連結して新たな被除数にする，という計算を繰り返せばよいことになる。このやり方なら，CRC計算の対象となるデータの先頭から，1バイトずつ取り出してきて計算することができるので，便利だ。

で，当時これをプログラムとして実装したはずなのだが，手元にあるのは以下のコード。

#define MPEG2TS_POLYNOMIAL	0x04c11db7

typedef unsigned char byte;
typedef unsigned long dword;

dword crcTable[256];

void makeCRCTable( void)
{
    for( dword i=0; i<256; i++){
        dword crc = i << 24;
        for( int j=0; j<8; j++){
            crc = ( crc << 1)
                    ^ ( ( crc & 0x80000000) ? MPEG2TS_POLYNOMIAL : 0);
        }
        crcTable[i] = crc;
    }
}

dword calcCRC( byte *buf, int len)
{
    dword crc = 0xffffffff;
    for( int i=0; i<len; i++){
        crc = ( crc << 8)
                ^ crcTable[ ( ( crc >> 24) ^ buf[i]) & 0xff];
    }
    return crc;
}

う～む。さっき説明したアルゴリズムを，どうやったらこのコードになるのか。いくら考えてもさっぱり分からない。日頃若いエンジニアに，特殊なアルゴリズムを使った場合は，コメントに説明を書くか，参考文献を載せておくように，と指導しているのに，自分でこんなことしてたらいけませんな。

さすがに分からないままにしておく訳にもいかないので，Webでさんざん調べた挙げ句，よいページを見つけた。「KONE's D-Station」というHP内の，「気まぐれな戯れ言の部屋」というコーナーのバック・ナンバーのページ。CRCについて疑問に思っていたことが，ほどよい難易度で説明されている上，上記のプログラムのアルゴリズムも解説されている! 当時はこのページを参考にした訳ではないのだが，代表的なアルゴリズムのひとつなのだろう。

具体的に言えば，「ファイルのCRC編-その3」という記事の最初のセクション，「アルゴリズムの最適化」で解説されているのが，まさに上記のプログラムである。若干難解なところもあるが，「その1」の記事からじっくり読んで考えていけば，なぜこのプログラムでよいのか理解できるはず. 他人任せで申し訳ないが，興味のある人は一読をお勧めする。著者の方には，この場を借りて感謝したい。

この解説と唯一異なる点は，calcCRC関数の最初の行で，変数crcに0xffffffffを代入しているところ。これもどこからの情報を元にしたのか，今となっては不明だが，ちょっと調べてみたところ，"RFC4236"の4.6節に，「CRC32 アキュミュレータ・レジスタを0xffffffffで初期化する」と書かれているので，MPEG2ではそういう仕様なのだろう。

MPEG2 TSのセクションのCRCを計算する場合は，calcCRC関数に，セクションの先頭(テーブルID)からCRC32領域の直前までのデータをすべて渡せば，適切な値が得られるはず。Big Endianなので，これを上位バイトからCRC32領域に詰めればOK。

という訳で，2年半前の宿題がようやく片付いたという感じ。当時ちゃんと書いていれば，こんな苦労は...とも思うが，これだけ調べても何も思い出さないところをみると，当時もこのアルゴリズムを完全に理解できていたかは，大いに疑問である。それだから続編を書けなかっただけなのかもね。

コメント 1

0xffffffffで初期化するのは、データの先頭に0のビットが続いたときに、その長さで結果がかわるようにするため。
0xffffffffで初期化しないと、データの先頭の0が無視される仕様になり、先頭の0の数だけが違うデータでも同じCRC値になってしまいます。
by 博文 (2012-02-15 11:29)