8年ぐらい前に、雑誌付録のSHマイコンに、SDカードをSPI接続して遊んでいた。MMC用のコードを使っていたので、当然SDHCやSDXCは利用できない。
先日PCを整理している時に、そのコードが出てきた。マイコンボードも出てきたので、SDカードのSPIモード用ドライバを作って遊ぼうと、作業を始めた。
コードを見直すと、コマンドトークンのCRC7の計算が、1bitずつ計算するお手本のようなわかりやすいコードだった。
一日30分の作業の繰り返しで、TRONやFATファイルシステムドライバまで作るとなると、出来る限り不具合の入らないコードで、プログラムを構成するのが良い。とにかく全体を実装して、実際に使えるようにすることを最優先にすると、どうしてもそのようなコードになる。
以下のような、コードだった。
CRC7計算をそのまま実装したような、わかりやすい動作の素直なコードだ。uint8_t calcCRC7(const uint8_t *buff, int len ) { uint8_t crc = 0; while( len-- ) { uint8_t byte = *buff++; int bits = 8; while( bits-- ) { crc <<= 1; if( (crc ^ byte) & 0x80 ) { crc ^= 0x89; } byte <<= 1; } } return( crc ); }
素直なのは良いが遅い。とはいえ、コマンドトークンは5バイトなので、遅くてもほとんど影響はない。
速いほうが良いが、貴重な時間を使ってまでやる必要は無い。というわけで、放置していた。
今回は、一応それなりに動くものがすでにある。SDHC対応、すなわち強化を行うのだ。
ついでに、多少寄り道して、CRC7をテーブル演算で実装してみる。
話は前後するが、CRCの処理について簡単に言えば、ビット列を端から順番に見ていって、'1'になっているビットがあるときに、生成多項式をXORしていくというものだ。
詳しくは、Wikipediaでも参照してもらいたい。
それを踏まえて、上記コードを見てみる。
2重のwhileループのうち、外側のループはバイト単位のループで、内側のループはビット単位のループである。
内側のループの内側に注目すると、
左ビット(最上位ビット)から処理するようにしているのがわかる。CRCは左回りと右回りがある。SD cardのCRC7は、左回りで計算する。SPIは上位ビットから入出力されるものなので、それが自然だろう。crc <<= 1; if( (crc ^ byte) & 0x80 ) { crc ^= 0x89; } byte <<= 1;
変数crc と 変数byte をXORして、その最上位ビットを見ている。
このビットが'1'の場合、crcに0x89(生成多項式)をXORしている。上の行に示されているように、if文の条件式の中で crc は byte とXORされているので、結果的にbyteにXORされることになる。
実際にはbyteのビットは変化しないのだが。
また、よく見るとcrcとbyteは、1ビットずつ左シフトしている。左のビットから順番に処理するためだ。
それぞれ1bitずつ左シフトしているので、最初にcrcにbyteをXORしておけば、途中でXORする必要がなくなり単純になる。
しかし、左シフトするタイミングが違っている。crcはif文の前、byteはif文の後ろだ。
なぜ2つに分かれているのか?
- byteの左シフトが上にあると、判定の前に最上位ビットがシフトアウトしてしまう。 最上位ビットから判定する必要があるので、これではダメだ。
- crcの左シフトが下にあると、終了時、余計に1bit左にシフトした結果になってしまう。 そのため、判定前に左シフトする。
そのため、判定後に左シフトする。
bit位置を合わせたいなら、最後に1bit右シフトして戻せばいい。最後に戻すなら、crcの左シフトを下に移動できる。
すなわち、以下のようになる。
このコードをよく見ると、crc と byte の XORを ループの外に移動して、1つの変数にできることがわかるだろう。if( (crc ^ byte) & 0x80 ) { crc ^= 0x89; } crc <<= 1; byte <<= 1;
1つの変数ならば、ビットシフトも1つで良くなり、単純になる。
これらを踏まえて整理すると、以下のようなコードになる。
ループ内のビットシフトが2つから1つになり、if文の条件式内のXORもなくなった。uint8_t calcCRC7(const uint8_t *buff, int len ) { uint8_t crc = 0; while( len-- ) { int bits = 8; crc ^= *buff++; // 最初にXORしておく while( bits-- ) { if( crc & 0x80 ) { // 最上位ビットを見て1ならば、 crc ^= 0x89; // 生成多項式とXORする。 } crc <<= 1; // ビットシフト } } return( crc >> 1 ); // 元の結果と同じになるように1bit戻す。 }
かなりすっきりした。
ここで、もう一度内側のループに注目してみよう。
このループをよく見ると、入力がcrcで、出力もcrcの演算処理と見ることができる。while( bits-- ) { if( crc & 0x80 ) { // 最上位ビットを見て1ならば、 crc ^= 0x89; // 生成多項式とXORする。 } crc <<= 1; // ビットシフト }
すなわち、内側のループ全体を関数X()として書き直すと、
ここまでまとまれば、テーブル化は簡単だ。uint8_t X( uint8_t crc ) { int bits = 8; while( bits-- ) { if( crc & 0x80 ) { // 最上位ビットを見て1ならば、 crc ^= 0x89; // 生成多項式とXORする。 } crc <<= 1; // ビットシフト } return( crc ); } uint8_t calcCRC7(const uint8_t *buff, int len ) { uint8_t crc = 0; while( len-- ) { crc ^= *buff++; // 最初にXORしておく crc = X( crc ); // 関数化された演算処理 } return( crc >> 1 ); // 元の結果と同じになるように1bit戻す。 }
変数crcは8bit変数だ。すなわち、0〜255までの256個の値しかとらない。
256個のルックアップテーブルを作って、テーブル解決すればいい。
(2017/11/17 makeTable()に使わない引数があった。修正した。)static uint8_t Table[256]; void makeTable( void ) { int i; for( i=0; i<256; i++ ) { uint8_t crc = i; int bits = 8; while( bits-- ) { if( crc & 0x80 ) { crc ^= 0x89; } crc <<= 1; } Table[i] = crc; } } uint8_t calcCRC7(const uint8_t *buff, int len ) { uint8_t crc = 0; while( len-- ) { crc ^= *buff++; // 最初にXORしておく crc = Table[ crc ]; // テーブル化された演算処理 } return( crc >> 1 ); // 元の結果と同じになるように1bit戻す。 }
テーブルを動的に生成するなら、上記のようなコードかな。
私は、コンパイル時に決定してしまうのが好きなので、テーブルの値を事前に計算して、ソースコードに埋め込んだ。
さらにもう少し。static const uint8_t Table[] = { 0x00,0x12,0x24,0x36,0x48,0x5A,0x6C,0x7E,0x90,0x82,0xB4,0xA6,0xD8,0xCA,0xFC,0xEE, 0x32,0x20,0x16,0x04,0x7A,0x68,0x5E,0x4C,0xA2,0xB0,0x86,0x94,0xEA,0xF8,0xCE,0xDC, 0x64,0x76,0x40,0x52,0x2C,0x3E,0x08,0x1A,0xF4,0xE6,0xD0,0xC2,0xBC,0xAE,0x98,0x8A, 0x56,0x44,0x72,0x60,0x1E,0x0C,0x3A,0x28,0xC6,0xD4,0xE2,0xF0,0x8E,0x9C,0xAA,0xB8, 0xC8,0xDA,0xEC,0xFE,0x80,0x92,0xA4,0xB6,0x58,0x4A,0x7C,0x6E,0x10,0x02,0x34,0x26, 0xFA,0xE8,0xDE,0xCC,0xB2,0xA0,0x96,0x84,0x6A,0x78,0x4E,0x5C,0x22,0x30,0x06,0x14, 0xAC,0xBE,0x88,0x9A,0xE4,0xF6,0xC0,0xD2,0x3C,0x2E,0x18,0x0A,0x74,0x66,0x50,0x42, 0x9E,0x8C,0xBA,0xA8,0xD6,0xC4,0xF2,0xE0,0x0E,0x1C,0x2A,0x38,0x46,0x54,0x62,0x70, 0x82,0x90,0xA6,0xB4,0xCA,0xD8,0xEE,0xFC,0x12,0x00,0x36,0x24,0x5A,0x48,0x7E,0x6C, 0xB0,0xA2,0x94,0x86,0xF8,0xEA,0xDC,0xCE,0x20,0x32,0x04,0x16,0x68,0x7A,0x4C,0x5E, 0xE6,0xF4,0xC2,0xD0,0xAE,0xBC,0x8A,0x98,0x76,0x64,0x52,0x40,0x3E,0x2C,0x1A,0x08, 0xD4,0xC6,0xF0,0xE2,0x9C,0x8E,0xB8,0xAA,0x44,0x56,0x60,0x72,0x0C,0x1E,0x28,0x3A, 0x4A,0x58,0x6E,0x7C,0x02,0x10,0x26,0x34,0xDA,0xC8,0xFE,0xEC,0x92,0x80,0xB6,0xA4, 0x78,0x6A,0x5C,0x4E,0x30,0x22,0x14,0x06,0xE8,0xFA,0xCC,0xDE,0xA0,0xB2,0x84,0x96, 0x2E,0x3C,0x0A,0x18,0x66,0x74,0x42,0x50,0xBE,0xAC,0x9A,0x88,0xF6,0xE4,0xD2,0xC0, 0x1C,0x0E,0x38,0x2A,0x54,0x46,0x70,0x62,0x8C,0x9E,0xA8,0xBA,0xC4,0xD6,0xE0,0xF2 };
よく考えてみればわかるが、SD cardのコマンドトークンのCRC7は、8bit内の上位7bitに格納されている。
そのため、SD card用なら、最後の右シフトは要らない。
それを除去してしまおう。
最初のcalcCRC7()よりも処理速度は10倍ぐらい高速化されているだろう。uint8_t calcCRC7(const uint8_t *buff, int len ) { uint8_t crc = 0; while( len-- ) { crc ^= *buff++; // 最初にXORしておく crc = Table[ crc ]; // テーブル化された演算処理 } return( crc ); // 8bit中、上7bitがCRC7 }
しかし、SDカードアクセス処理全体では、コマンドトークンのCRC7の計算量はわずかだ(たった 5 byte)。
そのため、全体での性能向上も大したことはない。
あまり期待すると、残念な思いをするだろう。
うっかり間違えて、下書きに戻していた。
公開し直した。
2017/11/12 サンプルコードやテーブルをスクロールするようにした。一部解りにくい表現を直した。