二進化十進表現（BCD）は、何かと組み込みプログラミングに付いて回ります。値を液晶に表示するときなんかは、内部的にBCD変換をすることになるはずです（C言語ならばprintfとかを使えばプログラマーが意識することはなくなるかもしれませんが）。
他にも、RTCなんかはカレンダー機能を内蔵していて、データのやり取りにはBCD形式を用いているものも結構ありますし、PIC24Fシリーズが持っているRTCCもBCDです。
さて、このBCDですが、このように組み込みプログラミング上で使おうとすると、マイコン内部の値、すなわちただの2進数との変換が必要になってきます。私の中ではこれは案外コストがかかるものであるという認識がありました。
というのも、BCD変換は要するに10進数の桁の抽出ですから、変数を10で除したり、その剰余を計算する必要があります。マイコンのような貧弱なCPUでは除算命令を持っていないことが多く、内部的にはループ等で除算が実装されていると思われます。また、C言語では除算演算子と剰余演算子が別個なので、同じ除数、被除数の場合はループならば本来は同時に商と剰余が産出されますが、C言語で記述する場合は、コンパイラが最適化してくれない限り、商と剰余で2回除算が必要になります。
もちろん自分でループを実装すればその手間は省けますが、それでもあまりスマートな気はしませんよね。
というわけで、こういうのって絶対すごいアルゴリズムあるよね～ってググっていたら見つけました。
BCD変換ルーチンについて
2020/5/4追記： 上記サイトリンク切れにつき、当ブログにてアルゴリズムを詳しく紹介する記事を書きました。アルゴリズムについてはこちらを参照ください。）1度読んだだけではどういう意味かよく分かりませんでしたが（ついでに<SUB>タグなどが上手く仕事していなくてとても読みにくいですが）、何度か読むと意味がわかってきました。シフト演算で値をコピーするときにBCD変換しようという発想で、基本的にはコピー先の各桁が10以上になったら6を足して繰り上げしてあげるってことみたいです。ただ、シフト演算は要するに2倍するということですので、2倍後の各桁は最大で18になりえます。ですが、それは4ビット値の最大値(15)を超えて不都合なので、シフト演算で2倍する前に5以上かを判別し、繰り上げ処理(2倍する前なので6の半分の3を足す)をやってあげるということのようです。これによって、BCD変換前の値のビット数だけのループ回数と、あとはシフト演算や簡単な比較、足し算だけでBCD変換ができてしまいます。なんと低コストなのでしょう。PICにはディジットキャリービットがありますから、下位4bitが桁あふれをしたかを判別することができるので、4bitごとの演算はとてもやりやすく、さらに計算の低コスト化ができるでしょう。コンパイラの頭の良さを試しどころです。
というわけで、PICを意識したC言語でこのアルゴリズムを実装してみました。
typedef union {
uint24_t value;
struct _tagField {
unsigned binary : 8;
unsigned BCD_1 : 4;
unsigned BCD_10 : 4;
unsigned BCD_100 : 4;
} field;
} BYTE_BCD_CONVERTER_UNION;
uint16_t ByteToBCD(uint8_t val)
{
BYTE_BCD_CONVERTER_UNION conv;
conv.value = 0;
conv.field.binary = val;
for(uint8_t i = 0; i < 8; i++) {
if(conv.field.BCD_1 >= 5)
conv.field.BCD_1 += 3;
if(conv.field.BCD_10 >= 5)
conv.field.BCD_10 += 3;
if(conv.field.BCD_100 >= 5)
conv.field.BCD_100 += 3;
conv.value <<= 1;
}
return (uint16_t)(conv.value >> 8);
}
ためしに、BCDの1の位と10の位が5以上かを見て処理する部分の逆アセンブル結果を見てみましょう。ちなみに、コンパイラはXC8 v1.35の無料版で、ターゲットはPIC16F1823です。
22: if(conv.field.BCD_1 >= 5) 0279 087A MOVF i, W 027A 390F ANDLW 0xF 027B 00F4 MOVWF multiplicand 027C 3005 MOVLW 0x5 027D 0274 SUBWF multiplicand, W 027E 1C03 BTFSS STATUS, 0x0 027F 2A8A GOTO 0x28A 23: conv.field.BCD_1 += 3; 0280 087A MOVF i, W 0281 390F ANDLW 0xF 0282 00F4 MOVWF multiplicand 0283 3003 MOVLW 0x3 0284 07F4 ADDWF multiplicand, F 0285 087A MOVF i, W 0286 0674 XORWF multiplicand, W 0287 39F0 ANDLW 0xF0 0288 0674 XORWF multiplicand, W 0289 00FA MOVWF i 24: if(conv.field.BCD_10 >= 5) 028A 0E7A SWAPF i, W 028B 390F ANDLW 0xF 028C 00F4 MOVWF multiplicand 028D 3005 MOVLW 0x5 028E 0274 SUBWF multiplicand, W 028F 1C03 BTFSS STATUS, 0x0 0290 2A9C GOTO 0x29C 25: conv.field.BCD_10 += 3; 0291 0E7A SWAPF i, W 0292 390F ANDLW 0xF 0293 00F4 MOVWF multiplicand 0294 3003 MOVLW 0x3 0295 07F4 ADDWF multiplicand, F 0296 0EF4 SWAPF multiplicand, F 0297 087A MOVF i, W 0298 0674 XORWF multiplicand, W 0299 390F ANDLW 0xF 029A 0674 XORWF multiplicand, W 029B 00FA MOVWF i
実際、自分でアセンブリで書くのならば、1の位はそのままマスクせずに0x05を引いてからSTATUSレジスタのディジットボロービットを見ることになりそうですし、0x03を足してもその4bit値としては桁あふれは絶対起こさないということはわかっているので、XOR→AND→XORなんていう回りくどい処理は省くでしょう。また、10の位はSWAPFなんてせずに、0x50を引いて上位4bitが5以上かを見ればよいですし、ここで足し算をするときもSWAP→マスク→3を足す→SWAP→XOR→AND→XORなんていう回りくどいことをせず、0x30を足せば良いでしょう。
…と考えると、このバイナリもまだまだ相当ステップ省略できそうですね。「桁あふれしないことはわかっている」っていうのはかなりハードな最適化なのでコンパイラができなくても仕方ないかなと思いますが、SWAPをして3を足す代わりにそのまま0x30を足す、くらいの芸当はやってほしかったですね。まあ、無料版だから仕方ないか。C言語でそう書けばいいんでしょうけどね…。
0 件のコメント:
コメントを投稿