USBのCRC：回路とCソース #crc

概要

USBのパケットに付加するCRCの計算方法について、CRC-5とCRC-16のそれぞれの回路とC言語のソースで解説します。

動機

USBキーボードを組み込み機器に接続する必要があって、最初はMAX3421を使っていたのですが、1個当たりの値段が高い（Digikeyで50個の時、1個あたり883.96円）のです。キーボードしかつながないので、安いマイクロコントローラでコントロールできないか調べてみたら、USBのCRCがちょっと特殊で、ちゃんと動作するソースがすぐに見つからない事がわかりました。
USBのCRCは、USBホストコントローラが自動で生成・チェックしてくれるので、今まで直接扱ったことがなかったのです。
そこで、USBのCRC5、CRC16について、ちゃんと正面から戦ってみました。

CRCの特徴

CRCは Cyclic Redundancy Check の略で、日本語では巡回冗長検査と言います。データ通信のノイズでビット落ちやビット反転・取りこぼしなどが発生しやすい時に、データのエラーチェックに使います。
CRCの特徴は、一定のビットのうち、一部が化けている事を検出しやすい事にあります。また、長いビット列の一部が変わった場合、CRCの計算結果は大きく変わるように出来ています。一部が変わった時に計算結果が大きく違うので、データの一部とCRCの一部が変わって、偶然計算結果が一致するような事が確率的に非常に少なくなります。

CRCのアルゴリズムは剰余を求める方法に似ていますが、実際に割り算をする代わりにXORを使います。
2進数の割り算を調べると判りますが、割り算は割られる数の上位桁から順に引けるかどうかを見て、引ける場合は引いて下の桁に移る、を繰り返します。CRCの場合は、上位桁から順に除数でXORを取るかどうかを見て必要ならXORを取って下の桁に移る、を繰り返します。
ここでいう「割られる数」がエラーチェックをするデータ、「除数」はCRCのアルゴリズム毎に決められた定数です。

CRCは主に除数の違いで色々な種類があります。詳しくは検索してみてください。
USBのCRC16は x¹⁶+x¹⁵+x²+x⁰ を除数としています。
CRC-16-IBMと言われるものがこの除数です（アルゴリズムが若干違うので、IBMとUSBでは計算結果は違います）。
USBのCRCは割られる数と除数のビットのXORを使います（XORの結果を別のXORに入れます）。
例によってLogisimの回路を用意しました。

回路

USBのCRC回路です（USB.circ　XMLなので、右クリックで）。
CRC-5を例に説明します。USBのCRC-5は除数が x⁵+x²+x⁰ です。二進数で100101です（ビット5,2,0が1です）。
CRC-5は結果は5ビットですが、基本的に剰余なので除数は6ビット目が1です。6ビット目が1なら、その下の桁が幾つであっても、余りが5ビットの範囲に散らばりますから。でも、除数の最上位の1はCRCの計算結果に影響が無い(6ビット目は1と決まっている)ので回路では省略してあります。

５つ並んだD-FlipFlopが、CRCの結果を保存しています。右側が最上位ビットです。除数はビット0とビット2が1です。この除数でXORを取るのですから、回路でもビット0の入力とビット2の入力にXORが入っています（回路右下はUSBのバスに先に出て行くビットが左になるように、ビットを上下入れ替えてあります）。
2つのXORのうち左は、割られる数（実際はエラーチェックをする入力データです）の最上位のビットとCRCの最上位のビットのXORです。
回路全体はCLKの立ち上がりで右側にシフトして行きます。
Logisimの都合で割られる数（入力データ）は、上位が右から出て行くようになっています。この場合の上位とは、先に送信するビットです¹。

CRCの最上位と入力データの最上位ビットが同じなら0、違っているなら1が次の（CLKの立ち上がりで確定する）CRCのビット0になります。同時に、CRCの次のビット2が反転するかどうかが、次のビット0と現在のビット1（という事は次のビット2になる予定）のXNORで決まります。XNORですから、次のビット0が0の場合は現在のビット1の反転が次のビット2です。
シフトと反転を同時にやるのでわかりにくいですが、LogisimでCLKをつついてみると解ると思います。

Cソース

Cのソースです。USB用なのでCRC5の入力データは11ビット固定です。

CRC-5-USB

USB_crc5.c

// CRC-5 USB

#define CRC5POLY 0x25   //  x^5 + x^2 + x^0

/*
    11bit -> crc5
    dataは先に送信するビットを左（上位ビット）とします。
    戻り値のCRCもやはり先に送信するビットが左です。
*/
unsigned short crc5(unsigned short data){
    unsigned short crc=0 ;

    for(int i=0 ; i<11 ; i++){
        crc=(crc << 1) | 1 ;    //  左側にシフト。変数crcの初期値を0にしたので最下位には1を入れる

        //  crcをシフトしてあふれたビット（6ビット目）とデータの最上位ビットを比較
        if(((data >> 5) & 0x20) == (crc & 0x20)){   //  ==で比較して
            crc ^= CRC5POLY ;   //  同じなら除数でXOR
        }
        data <<= 1 ;    //  データをシフト
    }

    return crc & 0x1f ;
}

CRC-16-USB

USB_crc16.c

//  CRC-16 USB

#define CRC16POLY 0x18005 // x^16+x^15+x^2+x^0

unsigned short crc16(unsigned char* buff, int len){
    unsigned int crc=0 ;    //  crcは17bit以上必要

    for(int n=0 ; n<len ; n++){
        unsigned char data=buff[n] ;

        for(int i=0 ; i<8 ; i++){
            crc=(crc << 1) | 1 ;
            if(((data >> 7) & 1) == ((crc >> 16) & 1)){
                crc ^= CRC16POLY ;
            }
            data <<= 1 ;
        }
    }

    return crc & 0xffff ;
}

テストコード

USB_crc.c

/*
gcc USB_crc.c USB_crc5.c USB_crc16.c -o crc
*/

#include <stdio.h>

unsigned short crc5(unsigned short data) ;
unsigned short crc16(unsigned char* buff, int len) ;


//  整数から2進文字列へ
char *int_to_binstr(int bin, int len)
{
    int i;
    static char buff[32];

    for (i = 0; i < len; i++) {
        if (bin & (1UL << (len - i - 1))) {
            buff[i] = '1';
        }
        else {
            buff[i] = '0';
        }
    }
    buff[i] = 0;

    return buff;
}


void test_crc5(unsigned short data){
    unsigned short crc ;
    printf("crc5  0x%03X -> ", data) ;
    crc=crc5(data) ;
    printf("0x%02X(%s)\n", crc, int_to_binstr((int)crc, 5)) ;
}


void test_crc16(unsigned char* buff, int len){
    unsigned short crc ;

    printf("crc16 0x") ;
    for(int i=0 ; i<len ; i++){
        printf("%02X ", buff[i]) ;
    }
    printf("-> ") ;

    crc=crc16(buff, len) ;
    printf("0x%04X(%s)\n", crc, int_to_binstr((int)crc, 16)) ;
}


unsigned char test_data[2][4]={
    {0x00, 0x80, 0x40, 0xc0},   //  00 01 02 03
    {0xc4, 0xa2, 0xe6, 0x91}    //  23 45 67 89
} ;

int main(void){
    test_crc5(0) ;
    test_crc5(0x547) ; // setup addr 15 endp e
    test_crc5(0x2e5) ; // out addr 3a endp a
    test_crc5(0x072) ; // in addr 70 endp 4
    test_crc5(0x400) ; // sof timestamp 001
    printf("\n") ;
    test_crc16(test_data[0], 4) ;
    test_crc16(test_data[1], 4) ;
}

実行結果

nic@nina-u:/mnt/pub/USB/USB-CRC$ gcc USB_crc.c USB_crc5.c USB_crc16.c -o crc
nic@nina-u:/mnt/pub/USB/USB-CRC$ ./crc
crc5  0x000 -> 0x08(01000)
crc5  0x547 -> 0x17(10111)
crc5  0x2E5 -> 0x1C(11100)
crc5  0x072 -> 0x0E(01110)
crc5  0x400 -> 0x17(10111)

crc16 0x00 80 40 C0 -> 0xF75E(1111011101011110)
crc16 0xC4 A2 E6 91 -> 0x7038(0111000000111000)

USBはLSBを先に送信します。例えば、8ビットの0x0fを送信する時は、最初に送信するビットは1です。 ↩