しばらく何も記事を書いていなかったので、なんか書くことにした。
8年ぐらい前に、雑誌付録のSHマイコンに、SDカードをSPI接続して遊んでいた。MMC用のコードを使っていたので、当然SDHCやSDXCは利用できない。
先日PCを整理している時に、そのコードが出てきた。マイコンボードも出てきたので、SDカードのSPIモード用ドライバを作って遊ぼうと、作業を始めた。
コードを見直すと、コマンドトークンのCRC7の計算が、1bitずつ計算するお手本のようなわかりやすいコードだった。
一日30分の作業の繰り返しで、TRONやFATファイルシステムドライバまで作るとなると、出来る限り不具合の入らないコードで、プログラムを構成するのが良い。とにかく全体を実装して、実際に使えるようにすることを最優先にすると、どうしてもそのようなコードになる。
以下のような、コードだった。
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 );
}
CRC7計算をそのまま実装したような、わかりやすい動作の素直なコードだ。
素直なのは良いが遅い。とはいえ、コマンドトークンは5バイトなので、遅くてもほとんど影響はない。
速いほうが良いが、貴重な時間を使ってまでやる必要は無い。というわけで、放置していた。
今回は、一応それなりに動くものがすでにある。SDHC対応、すなわち強化を行うのだ。
ついでに、多少寄り道して、CRC7をテーブル演算で実装してみる。
話は前後するが、CRCの処理について簡単に言えば、ビット列を端から順番に見ていって、'1'になっているビットがあるときに、生成多項式をXORしていくというものだ。
詳しくは、Wikipediaでも参照してもらいたい。
それを踏まえて、上記コードを見てみる。
２重のwhileループのうち、外側のループはバイト単位のループで、内側のループはビット単位のループである。
内側のループの内側に注目すると、
crc <<= 1;
if( (crc ^ byte) & 0x80 ) {
crc ^= 0x89;
}
byte <<= 1;
左ビット(最上位ビット)から処理するようにしているのがわかる。CRCは左回りと右回りがある。SD cardのCRC7は、左回りで計算する。SPIは上位ビットから入出力されるものなので、それが自然だろう。
変数crc と 変数byte をXORして、その最上位ビットを見ている。
このビットが'1'の場合、crcに0x89(生成多項式)をXORしている。上の行に示されているように、if文の条件式の中で crc は byte とXORされているので、結果的にbyteにXORされることになる。
実際にはbyteのビットは変化しないのだが。
また、よく見るとcrcとbyteは、１ビットずつ左シフトしている。左のビットから順番に処理するためだ。
それぞれ1bitずつ左シフトしているので、最初にcrcにbyteをXORしておけば、途中でXORする必要がなくなり単純になる。
しかし、左シフトするタイミングが違っている。crcはif文の前、byteはif文の後ろだ。
なぜ２つに分かれているのか？
- byteの左シフトが上にあると、判定の前に最上位ビットがシフトアウトしてしまう。
最上位ビットから判定する必要があるので、これではダメだ。
そのため、判定後に左シフトする。
- crcの左シフトが下にあると、終了時、余計に1bit左にシフトした結果になってしまう。
そのため、判定前に左シフトする。
よく考えてみよう。結果が1bit余計にシフトされていても、変数crcは8bitで構成されており、CRC7は7bitなので、必要な情報は何も失われていない。
bit位置を合わせたいなら、最後に1bit右シフトして戻せばいい。最後に戻すなら、crcの左シフトを下に移動できる。
すなわち、以下のようになる。
if( (crc ^ byte) & 0x80 ) {
crc ^= 0x89;
}
crc <<= 1;
byte <<= 1;
このコードをよく見ると、crc と byte の XORを ループの外に移動して、１つの変数にできることがわかるだろう。
1つの変数ならば、ビットシフトも１つで良くなり、単純になる。
これらを踏まえて整理すると、以下のようなコードになる。
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 ) { // 最上位ビットを見て１ならば、
crc ^= 0x89; // 生成多項式とXORする。
}
crc <<= 1; // ビットシフト
}
}
return( crc >> 1 ); // 元の結果と同じになるように1bit戻す。
}
ループ内のビットシフトが２つから１つになり、if文の条件式内のXORもなくなった。
かなりすっきりした。
ここで、もう一度内側のループに注目してみよう。
while( bits-- ) {
if( crc & 0x80 ) { // 最上位ビットを見て１ならば、
crc ^= 0x89; // 生成多項式とXORする。
}
crc <<= 1; // ビットシフト
}
このループをよく見ると、入力がcrcで、出力もcrcの演算処理と見ることができる。
すなわち、内側のループ全体を関数X()として書き直すと、
uint8_t X( uint8_t crc )
{
int bits = 8;
while( bits-- ) {
if( crc & 0x80 ) { // 最上位ビットを見て１ならば、
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個のルックアップテーブルを作って、テーブル解決すればいい。
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戻す。
}
(2017/11/17 makeTable()に使わない引数があった。修正した。)
テーブルを動的に生成するなら、上記のようなコードかな。
私は、コンパイル時に決定してしまうのが好きなので、テーブルの値を事前に計算して、ソースコードに埋め込んだ。
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用なら、最後の右シフトは要らない。
それを除去してしまおう。
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
}
最初のcalcCRC7()よりも処理速度は10倍ぐらい高速化されているだろう。
しかし、SDカードアクセス処理全体では、コマンドトークンのCRC7の計算量はわずかだ(たった 5 byte)。
そのため、全体での性能向上も大したことはない。
あまり期待すると、残念な思いをするだろう。
うっかり間違えて、下書きに戻していた。
公開し直した。
2017/11/12 サンプルコードやテーブルをスクロールするようにした。一部解りにくい表現を直した。
