Z80での１バイトのビット順反転処理

　今回はみんな大好き？な Z80 のマシン語ネタです。Twitter のタイムライン（以降、TLと記す）で 8bit データの MSB-LSB の順番を反転する処理についてのコメントを見かけました。
　この話題の発端は内藤さんのマニアックなブログ「Code Knowledge」の「Z80 超高速ビット左右反転」の記事です。因みに内藤さんのブログの「Z80 数値の加算と減算」の記事で拙作の「Z80での10の高速除算方法」の記事を紹介して頂いています。

　話をビット順の反転処理に戻すと 256 パターンのテーブルを作成し、テーブルから引っ張るのが最も高速ですが、メモリを大食いしてしまうので普通に考えると A-reg ともう一つのレジスタを使ってキャリーフラグ経由でローテートを８回実施する方法を直ぐに思い付きます。
　しかし、A-reg のローテートは４ステートですが A-reg 以外のローテートは８ステート必要でそれなりにコストが掛かります。

　改善案として下記の処理が上記の TL で提示されました。

reverse (original method)

Original: 47 ld b,a ; 76543210 4 E6 55 and 55h ; 7 4F ld c,a ; _6_4_2_0 4 78 ld a,b ; 4 E6 AA and 0aah ; 7_5_3_1_ 7 0F rrca ; 4 0F rrca ; 1_7_5_3_ 4 B1 or c ; 16745230 4 47 ld b,a ; 4 E6 99 and 99h ; 1__45__0 7 0F rrca ; 4 4F ld c,a ; 01__45__ 4 78 ld a,b ; 4 E6 66 and 66h ; _67__23_ 7 07 rlca ; 4 07 rlca ; 4 07 rlca ; __23__67 4 B1 or c ; 01234567 4 C9 ret ; 4+7+4+4+7+4+4+4+4+7+4+4+4+7+4+4+4+4 = 84

　最初の AND 命令の部分は C-reg を減算した方が効率がいいので下記の処理を提案してみました。

reverse (improvement method)
Improve: 47 LD B,A ; 76543210 4 E6 55 AND 55H ; _6_4_2_0 7 4F LD C,A ; 4 78 LD A,B ; 4 91 SUB C ; 7_5_3_1_ 4 0F RRCA ; 4 0F RRCA ; 1_7_5_3_ 4 B1 OR C ; 16745230 4 47 LD B,A ; 4 E6 66 AND 66H ; _67__23_ 7 07 RLCA ; 4 07 RLCA ; 4 07 RLCA ; 4 4F LD C,A ; __23__67 4 78 LD A,B ; 4 E6 99 AND 99H ; 1__45__0 7 0F RRCA ; 01__45__ 4 B1 OR C ; 01234567 4 C9 RET ; 4+7+4+4+4+4+4+4+4+7+4+4+4+4+4+7+4+4 = 81

　これに対して XOR により直前の LD も省略し、更には後半の 2bit ペアの処理にも同様の改善手法を適用した改善案が提示されました。素晴らしいですね。

reverse (further improvement method)
Fimprov: 47 ld b,a ; 76543210 4 E6 55 and 55h ; _6_4_2_0 7 4F ld c,a ; 4 A8 xor b ; 7_5_3_1_ 4 0F rrca ; 4 0F rrca ; 1_7_5_3_ 4 B1 or c ; 16745230 4 0F rrca ; 01674523 4 47 ld b,a ; 4 E6 CC and 0cch ; 01__45__ 7 4F ld c,a ; 4 A8 xor b ; __67__23 4 07 rlca ; 4 07 rlca ; 4 07 rlca ; 4 07 rlca ; __23__67 4 B1 or c ; 01234567 4 C9 ret ; 4+7+4+4+4+4+4+4+4+7+4+4+4+4+4+4+4 = 74

　上記の処理より高速な手法は中々見つかりません。1bit 毎と 2bit 毎の2回の順番入れ替えが必要なことはすぐに判るのですが（2bit 入れ替えの方から先にやってもいい、と言うか順番のリバース処理なので末尾処理から逆に実行してもリバースになる）、例えば次の例のように命令数は削減できても同じステート数になってしまいます。

reverse (sample method)
Sample: 47 LD B,A ; 76543210 4 E6 AA AND 0AAH ; 7_5_3_1_ 7 4F LD C,A ; 4 A8 XOR B ; _6_4_2_0 4 0F RRCA ; 0_6_4_2_ 4 CB 01 RLC C ; _5_3_1_7 8 B1 OR C ; 05634127 4 47 LD B,A ; 4 E6 99 AND 99H ; 0__34__7 7 4F LD C,A ; 4 A8 XOR B ; _56__12_ 4 0F RRCA ; 4 0F RRCA ; 4 0F RRCA ; 4 0F RRCA ; _12__56_ 4 B1 OR C ; 01234564 4 C9 RET ; 4+7+4+4+4+8+4+4+7+4+4+4+4+4+4+4 = 74

　ローテート処理だけでは限界が見えてきたので加減算処理をうまく利用できないか考えてみたところ・・・・若干ではありますが更に高速な手法に辿り着きました (^^)/

reverse (fastest method at the moment)
Fastest: 47 LD B,A ; 76543210 4 E6 55 AND 55H ; _6_4_2_0 7 4F LD C,A ; 4 80 ADD A,B ; 4 1F RRA ; 4 81 ADD A,C ; 67452301 4 47 LD B,A ; 4 E6 CC AND 0CCH ; 67__23__ 7 07 RLCA ; 4 07 RLCA ; __23__67 4 4F LD C,A ; 4 78 LD A,B ; 67452301 4 E6 33 AND 33H ; __45__01 7 0F RRCA ; 4 0F RRCA ; 01__45__ 4 B1 OR C ; 01234567 4 C9 RET ; 4+7+4+4+4+4+4+7+4+4+4+4+7+4+4+4 = 73

　前半の 1bit の入れ替え部分が若干トリッキーですが、256 通りの全ての入力パターンに対して従来の処理と同じ結果になることを確認しました。

　素晴らしい処理方法を直ぐに思いつけばいいのですがいろいろな組み合わせがあるので、処理手法については散歩中等の空き時間を利用してアイディアを考えて頭の中で思考実験し、行けそうであれば紙に書いて確認し（当然最終確認はプログラムですが）メモを残すというやり方をしています。

　メモと言っても下の写真のように汚く書き散らかしたようなものなのですが・・ｗ

手法を思考中のメモ

　もし更なる改善案を思い付いた場合にはコメント頂ければ嬉しいです。


★追記　2022/06/07
　twitterのリプライで教えて頂いたのですがNET上の Retro Programming に 66 ステートでリバース処理するコードがありました。素晴らしい!!
　XOR 演算による置き換えが秀逸ですね。

reverse (Fastest method on the net)
net: 6F ld l,a ; 76543210 4 07 rlca ; 4 07 rlca ; 54321076 4 AD xor l ; 4 E6 AA and 0aah ; 7 AD xor l ; 56341270 4 6F ld l,a ; 4 07 rlca ; 4 07 rlca ; 4 07 rlca ; 41270563 4 CB 0D rrc l ; 05634127 8 AD xor l ; 4 E6 66 and 66h ; 7 AD xor l ; 01234567 4 C9 ret ; 4+4+4+4+7+4+4+4+4+4+8+4+7+4 = 66

★追記　2022/07/07
　その後も時折考えていますが七夕でもあるので現状の改善案を追記しておきますｗ
　70 ステートで上記の NET 手法よりもまだ 4 ステート遅い状況です。

reverse (Current improving method)
idea3: 47 LD B,A ; 76543210 4 E6 55 AND 55H ; _6_4_2_0 7 4F LD C,A ; 4 80 ADD A,B ; 4 1F RRA ; 4 81 ADD A,C ; 67452301 4 47 LD B,A ; 4 07 RLCA ; 4 07 RLCA ; 45230167 4 A8 XOR B ; 4 E6 33 AND 33H ; 7 4F LD C,A ; 4 0F RRCA ; 4 0F RRCA ; 4 B1 OR C ; 4 A8 XOR B ; 01234567 4 C9 RET ; 4+7+4+4+4+4+4+4+4+4+7+4+4+4+4+4 = 70