since 2007.8 by K-ichi

まるさら受け売りなのだが、自分なりに考えたところを忘れないようにメモしておく。

シリアル接続環境ができたので、PICであれこれデータを取って、CSV形式でばーーーっと転送して……などと考えていたのだが、表計算に16進数CSVを食わすには難儀するらしい。
10進表記に変換したいが、PC上でひと手間かけるのもスマートでないし、マイコン側でやるのも大変。世間ではどうしているのかと検索してみると、頭のいい人はいるものだ。

たとえば8bitバイナリを10進表記に直すなら、さんすう頭では、100で割って商が100の位、剰余を10で割って10の位、余りが1の位、と考える。ただ、PICなどで割り算をやるのは非常にコストが高い。100を引けるだけ引く、的な力技で済ますことも多い。
ところがこの変換が、ビット数分のシフト&加減算だけでできるという。

なお、この変換の「10進表記」には、BCD(Binary Coded Decimal:二進化十進数)という形を使う。4bitを1塊として扱い、10進数の1桁を表現する。(参考:Wikipedia
文字コードに変換するには、4bitずつにバラして30hを足すだけなので扱いやすい。

8bitの変換は以下のようにする。

1.バイナリ8bitの上位に12bit(8bitの最大値が255なので、BCD3桁分)を追加する。
2.BCD部の各桁が5以上なら3を足し、全体を左シフト。
3.バイナリのビット数分、2.を繰り返す。

以上。
これで、上位12bitに変換された値ができあがる。

BCDというのは、10進数とみなしているものの実体は2進数。そのため諸演算の結果、10進数ではありえない「ひと桁で10~15」という数ができることがある。桁上がりも考慮すれば、19までとりうる。もし10以上の数ができてしまったら、6を足して0~9の範囲を表すように補正する。
Z80などには専用の命令があり、DAA(Decimal Adjust Accumulator)という命令を使うとその補正ができる。しかしPICには無い。DAA機能をそのままコーディングしてもいいが、効率よくこなすためにちょっと捻ったのが上記の手順になる。

2進数では、左シフトは値を2倍することと同義。BCDも実体は2進数なので同様。よって、シフト前なら、「10以上なら6を足す」の半分で済むことになる。
これはプログラム上で都合がよく、5以上に3を足すと8以上、つまり4bit塊の最上位ビットが立つ数値範囲にちょうど合致する。逆にいえば、その後の左シフトで桁上がりを要する数値だから、そのためのビットが立っている、とも見れる。

上位ビットから順繰りにBCD部に入っていき、最終的にはビット数分シフトされる。最上位ビット(27)は128倍され、次のビット(26)は64倍され……最下位ビット(20)は1倍されて、正しく重み付けされた状態でBCD側に入ることになる。
シフト演算(=自身と下位ビットの加算)の度に補正をかけてやることで、うまいことBCDに変換できる……らしい。


だいたい理解できたつもりになったので、実証してみる。
いくつかの数値で計算し、表にまとめてみた。透明背景の行がシフト後(または初期値)、グレー背景の行が補正処理後で、上から順に処理が進むイメージ。
青文字は実際に補正された箇所。xは任意だが、便宜上0とみなす。

0x80(128)の場合。

BCD BIN BCD BIN
000000000000100000000 0 08 0
000000000000100000000 0 08 0
0000000000010000000x0 0 10 0
0000000000010000000x0 0 10 0
000000000010000000xx0 0 20 0
000000000010000000xx0 0 20 0
00000000010000000xxx0 0 40 0
00000000010000000xxx0 0 40 0
0000000010000000xxxx0 0 80 0
0000000010110000xxxx0 0 B0 0
000000010110000xxxxx0 1 60 0
000000011001000xxxxx0 1 90 0
00000011001000xxxxxx0 3 20 0
00000011001000xxxxxx0 3 20 0
0000011001000xxxxxxx0 6 40 0
0000100101000xxxxxxx0 9 40 0
000100101000xxxxxxxx1 2 80 0

0xFF(255)の場合。

BCD BIN BCD BIN
000000000000111111110 0 0F F
000000000000111111110 0 0F F
0000000000011111111x0 0 1F E
0000000000011111111x0 0 1F E
000000000011111111xx0 0 3F C
000000000011111111xx0 0 3F C
00000000011111111xxx0 0 7F 8
00000000101011111xxx0 0 AF 8
0000000101011111xxxx0 1 5F 0
0000000110001111xxxx0 1 8F 0
000000110001111xxxxx0 3 1E 0
000000110001111xxxxx0 3 1E 0
00000110001111xxxxxx0 6 3C 0
00001001001111xxxxxx0 9 3C 0
0001001001111xxxxxxx1 2 78 0
0001001010101xxxxxxx1 2 A8 0
001001010101xxxxxxxx2 5 50 0

0xAA(170)の場合。

BCD BIN BCD BIN
000000000000101010100 0 0A A
000000000000101010100 0 0A A
0000000000010101010x0 0 15 5
0000000000010101010x0 0 15 5
000000000010101010xx0 0 2A 8
000000000010101010xx0 0 2A 8
00000000010101010xxx0 0 55 0
00000000100001010xxx0 0 85 0
0000000100001010xxxx0 1 0A 0
0000000100001010xxxx0 1 0A 0
000000100001010xxxxx0 2 14 0
000000100001010xxxxx0 2 14 0
00000100001010xxxxxx0 4 28 0
00000100001010xxxxxx0 4 28 0
0000100001010xxxxxxx0 8 50 0
0000101110000xxxxxxx0 B 80 0
000101110000xxxxxxxx1 7 00 0

なるほど。正しそう。

この処理をミッドレンジPICに実装すると、こんな感じになる。

最初の3bit分は、補正処理なくシフトできるので、ループ回数を減らしている。
5以上かを調べるのではなく、3を足して8以上になるか、で判断している。
100の位は最大でも2なので、補正処理はしていない。

「test value」値が、DH:DLの2バイトにまたがったBCDで返る。MPLABのシミュレーション機能で動作確認済み。

BI	equ	0x20
DL	equ	0x21
DH	equ	0x22
CNT	equ	0x23

	movlw	255	;test value
	movwf	BI
	clrf	DL
	clrf	DH

	rlf	BI,f
	rlf	DL,f
	rlf	BI,f
	rlf	DL,f
	rlf	BI,f
	rlf	DL,f
	movlw	5
	movwf	CNT
loop:
	movlw	0x33
	addwf	DL,f
	btfsc	DL,3
	addlw	-0x03
	btfsc	DL,7
	addlw	-0x30
	subwf	DL,f
	rlf	BI,f
	rlf	DL,f
	rlf	DH,f
	decfsz	CNT,f
	goto	loop

ついでなので、MSXなどに使われていたZ80用にも書いてみた。環境が整ってないので、動作確認はしていない。
PICと比べると、ビットテストや分岐はコスト高。同じアルゴリズムでは書きづらい。DAAという補正命令があるので、そちらを使うこととする。
DAAは、Aレジスタの演算結果のほか、HLレジスタペアの結果にも適用できる。補正に必要なC、Hフラグの変化は、Hレジスタが対象になっている。

ちなみにDAAについては、「daa命令の技」という、なかなか深いページがある。なるほどなぁ、という感じ。

「test value」値が、C:HレジスタにBCDで返る(はず)。

2016/10/24 追記、訂正。
CP/M互換環境のCPM.EXE(タイムスタンプ:1994/10/29 23:18)、MSX-DOS1互換環境のMSX.EXE(1998/7/30 0:08)、およびMSX1相当のWebMSXページにて動作確認。バグ修正済み。
前者2つの互換環境では、16bit演算におけるHフラグの動きが正しくシミュレートされていない。add hl,hlを8bitにバラして、Aレジスタで演算させれば動作する。ちなみにこれら互換環境は、Win7 64bitではエラーを吐いて動作せず。XPモード上で作業を行った。
WebMSXでは正常に動く。Hフラグの反応も、「Z80ファミリ・ハンドブック」の記載と同じなので、こちらが正しいと思われる。ちなみにこのWebMSXページは、IE11ではファイルの読み書きができないので、まともに使えない。Google Chrome 53.0.2785.143 mでは問題なく使えた。

	ld	l,255	;test value
	ld	h,0
	add	hl,hl
	add	hl,hl
	add	hl,hl
	ld	bc,0500h
loop:
	add	hl,hl
	ld	a,h
	daa
	ld	h,a
	ld	a,c
	adc	a,a
	ld	c,a
	djnz	loop

0 件のコメント:

コメントを投稿

.

関連記事


この記事へのリンク by 関連記事、被リンク記事をリストアップする」記事

ブログ アーカイブ