Z80での高速な乗算処理（その２）最適化

　Z80 での unsigned 8bit の新たな乗算方式を提案した前回の記事「Z80での高速な乗算処理」は予想以上に多くの閲覧があり、驚きました。

　前回の記事で書いたようにコードの最適化をあまりしていなかったので今回は最適化について書いてみたいと思います。Z80 アセンブラは直行性の要素が少ない反面、パズルを解くような面白さがあるので方式検討とコーディング（最適化）で二度楽しめます ^^

★追記　2023/02/19　{
　Z80 のアセンブラ経験者の方であれば前回の記事の最適化前のソースの高速化を少し考えてから本記事を読むと本記事の内容がより面白いものになるかと思います。
}

1. Twitter での反響
   　ブログの閲覧もそうですが地味なメッセージであったにもかかわらず Twitter でも予想以上の反響を頂きました。
   　具体的なコードを示された方もあり、私がタイムラインで確認できた中で最も高速だったのは、私のメッセージに対して最初（約４時間後）にコードを提示されたメッセージのものです。
   　下記にコードを引用させて頂きます（Twitter 上の実際のコードには判り易いコメントを付けられています）。
   　未検証とのことでしたが、当方で検証した結果、問題ありませんでした。平均ステート数は 141.5 でメチャ高速です。
   
   

   タイムライン上の最速コード（Z80アセンブラ）

   ; unsigned 8 bits fast multi(my method) 24lines ; fastest code in Twitter time line ; x*y = (x^2 + y^2 - (x-y)^2)/2 ; E <- data0 ; L <- data1 ; HL -> data0 * data1 0188 7B TwMul: LD A,E ; 4 0189 95 SUB L ; 4 018A 30 03 JR NC,TwMu10 ; 12/7 018C ED 44 NEG ; 8 018E EB EX DE,HL ; 4 018F 26 03 TwMu10: LD H,HIGH MULTBL+1 ; 7 0191 46 LD B,(HL) ; 7 0192 25 DEC H ; 4 0193 4E LD C,(HL) ; 7 0194 6F LD L,A ; 4 0195 54 LD D,H ; 4 0196 1A LD A,(DE) ; 7 0197 96 SUB (HL) ; 7 0198 14 INC D ; 4 0199 24 INC H ; 4 019A 66 LD H,(HL) ; 7 019B 6F LD L,A ; 4 019C 1A LD A,(DE) ; 7 019D 9C SBC A,H ; 4 019E 67 LD H,A ; 4 019F 09 ADD HL,BC ; 11 01A0 CB 1C RR H ; 8 01A2 CB 1D RR L ; 8 01A4 C9 RET ; 10 ; Max 145 = 4+4+(7+8+4)+7+7+4+7+4+4+7+7+4+4+7+4+7+4+4+11+8+8+10  ; Min 138 = 4+4+(12)+7+7+4+7+4+4+7+7+4+4+7+4+7+4+4+11+8+8+10 ; Ave 141.5

   
   
   　私も Z80 の最適化には自信を持ってはいるのですが、上記のコードは処理の流れに淀みが無く、洗練されたコードで流石だと思いました。僭越ではありますが、気になったのは次の２点です。
   
   
   • "NEG" 後の "EX DE,HL" は必要なのか？
     　最初に気になったのは DE と HL の交換は必要ないのではないかと言うことです。ディバッガで追ってみて交換が必要である理由が判りました。この交換の必要性を机上で判ったのであればすごいですね。
     
     
   • 最後の二つのシフト命令
     　A-reg 以外のシフト命令は遅い（ 8 ステート）ので使用をなるべく避けたいところです。しかし、処理の流れ上これより速い方法は思い付きませんでした。
     
   
   　もっと速いコードを模索しましたが、これ以上のものは難しいと思います（少なくとも私は諦めました）。短時間でこのコードを作られた作者の方には流石と言う他ありません。
   
   
   
2. 更なる高速化
   　今回使った乗算方式の発案者としてはこのままではあれなのでコーディング上の高速化が難しいことから方式に戻って検討を行いました。
   　具体的には前項で二つ目に書いたシフト命令部分について考えてみました。最後に 1/2 するのであれば、最初からテーブル内の値を 1/2 にすればいいのではないかと言う発想です。そのためには LSB 分の計算（桁上り）を別ロジックで計算する必要があります。
   
   　それでは LSB からの桁上りが発生する条件について見てみましょう。今回の乗算方式（マイナス二乗法）は乗算を求めるために下記の式を用いています。
   
   

   x*y = (x^2 + y^2 - (x - y)^2) / 2

   
   　x,y の偶数／奇数の組合せでの各項の偶数／奇数及び桁上りの発生有無は下表のようになります（０：偶数（桁上り無し））、１：奇数（桁上り有り））。
   　"(x-y)^2" はマイナス項なので x,y が両者とも奇数の場合のみ桁上り（＋１）すればいいことになります。
   
   

   No.	x	y	x^2	y^2	(x - y)^2	carry
   1	0	0	0	0	0	0
   2	0	1	0	1	1	0
   3	1	0	1	0	1	0
   4	1	1	1	1	0	1

   
   　また、前項の 1 番目の DE,HL の交換の必要性の確認で判ったことですが、15 ビットの計算になるので副次的な効果として計算の順番を気にする必要も無くなります。
   
   
   
3. 最適化の結果
   　上記の処理をコーディングした結果を末尾に示します。平均ステート数は 140.5 となり、前項の最速コードより辛うじて速くなりました。
   　前回の最適化前のものも含めたステート数の一覧が下表になります。
   
   

   No.	Method	Max	Min	Average	ratio
   1	Normal method	363	315	339.0	1.00
   2	Minus square method	154	151	152.5	2.22
   3	Minus square method   (optimized)	142	139	140.5	2.41

   
   　コードは下記の通りで二乗計算のためのテーブル内の値を 1/2 にしています。
   
   

   最適化したコード（Z80アセンブラ）

   ; unsigned 8 bits fast multi(Minus square method) 27 lines ; x*y = (x^2 + y^2 - (x-y)^2)/2 ; E <- data0 ; L <- data1 ; HL -> data0 * data1 016A 7B FFMu8: LD A,E ; 4 016B A5 AND L ; 4 016C 1F RRA ; 4 016D 26 04 LD H,HIGH(MULTB2) ; 7 016F 54 LD D,H ; 4 0170 1A LD A,(DE) ; 7 0171 8E ADC A,(HL) ; 7 0172 4F LD C,A ; 4 0173 14 INC D ; 4 0174 24 INC H ; 4 0175 1A LD A,(DE) ; 7 0176 8E ADC A,(HL) ; 7 0177 57 LD D,A ; 4 0178 7B LD A,E ; 4 0179 95 SUB L ; 4 017A 30 02 JR NC,FFMu10 ; 12/7 017C ED 44 NEG ; 8 017E 6F FFMU10: LD L,A ; 4 017F 5E LD E,(HL) ; 7 0180 25 DEC H ; 4 0181 79 LD A,C ; 4 0182 96 SUB (HL) ; 7 0183 6F LD L,A ; 4 0184 7A LD A,D ; 4 0185 9B SBC A,E ; 4 0186 67 LD H,A ; 4 0187 C9 RET ; 10 ; Max 142 = 4+4+4+7+4+7+7+4+4+4+7+7+4+4+4+(7+8)+4+7+4+4+7+4+4+4+4+10  ; Min 139 = 4+4+4+7+4+7+7+4+4+4+7+7+4+4+4+(12)+4+7+4+4+7+4+4+4+4+10 ; Ave 140.5 ORG ($ + 255) AND 0FF00H ; (8bit ^ 2) / 2 table 0400 00 00 02 04 MULTB2: DB 000H,000H,002H,004H,008H,00CH,012H,018H ; low byte 0404 08 0C 12 18 0408 20 28 32 3C DB 020H,028H,032H,03CH,048H,054H,062H,070H 040C 48 54 62 70 0410 80 90 A2 B4 DB 080H,090H,0A2H,0B4H,0C8H,0DCH,0F2H,008H 0414 C8 DC F2 08 0418 20 38 52 6C DB 020H,038H,052H,06CH,088H,0A4H,0C2H,0E0H 041C 88 A4 C2 E0 0420 00 20 42 64 DB 000H,020H,042H,064H,088H,0ACH,0D2H,0F8H 0424 88 AC D2 F8 0428 20 48 72 9C DB 020H,048H,072H,09CH,0C8H,0F4H,022H,050H 042C C8 F4 22 50 0430 80 B0 E2 14 DB 080H,0B0H,0E2H,014H,048H,07CH,0B2H,0E8H 0434 48 7C B2 E8 0438 20 58 92 CC DB 020H,058H,092H,0CCH,008H,044H,082H,0C0H 043C 08 44 82 C0 0440 00 40 82 C4 DB 000H,040H,082H,0C4H,008H,04CH,092H,0D8H 0444 08 4C 92 D8 0448 20 68 B2 FC DB 020H,068H,0B2H,0FCH,048H,094H,0E2H,030H 044C 48 94 E2 30 0450 80 D0 22 74 DB 080H,0D0H,022H,074H,0C8H,01CH,072H,0C8H 0454 C8 1C 72 C8 0458 20 78 D2 2C DB 020H,078H,0D2H,02CH,088H,0E4H,042H,0A0H 045C 88 E4 42 A0 0460 00 60 C2 24 DB 000H,060H,0C2H,024H,088H,0ECH,052H,0B8H 0464 88 EC 52 B8 0468 20 88 F2 5C DB 020H,088H,0F2H,05CH,0C8H,034H,0A2H,010H 046C C8 34 A2 10 0470 80 F0 62 D4 DB 080H,0F0H,062H,0D4H,048H,0BCH,032H,0A8H 0474 48 BC 32 A8 0478 20 98 12 8C DB 020H,098H,012H,08CH,008H,084H,002H,080H 047C 08 84 02 80 0480 00 80 02 84 DB 000H,080H,002H,084H,008H,08CH,012H,098H 0484 08 8C 12 98 0488 20 A8 32 BC DB 020H,0A8H,032H,0BCH,048H,0D4H,062H,0F0H 048C 48 D4 62 F0 0490 80 10 A2 34 DB 080H,010H,0A2H,034H,0C8H,05CH,0F2H,088H 0494 C8 5C F2 88 0498 20 B8 52 EC DB 020H,0B8H,052H,0ECH,088H,024H,0C2H,060H 049C 88 24 C2 60 04A0 00 A0 42 E4 DB 000H,0A0H,042H,0E4H,088H,02CH,0D2H,078H 04A4 88 2C D2 78 04A8 20 C8 72 1C DB 020H,0C8H,072H,01CH,0C8H,074H,022H,0D0H 04AC C8 74 22 D0 04B0 80 30 E2 94 DB 080H,030H,0E2H,094H,048H,0FCH,0B2H,068H 04B4 48 FC B2 68 04B8 20 D8 92 4C DB 020H,0D8H,092H,04CH,008H,0C4H,082H,040H 04BC 08 C4 82 40 04C0 00 C0 82 44 DB 000H,0C0H,082H,044H,008H,0CCH,092H,058H 04C4 08 CC 92 58 04C8 20 E8 B2 7C DB 020H,0E8H,0B2H,07CH,048H,014H,0E2H,0B0H 04CC 48 14 E2 B0 04D0 80 50 22 F4 DB 080H,050H,022H,0F4H,0C8H,09CH,072H,048H 04D4 C8 9C 72 48 04D8 20 F8 D2 AC DB 020H,0F8H,0D2H,0ACH,088H,064H,042H,020H 04DC 88 64 42 20 04E0 00 E0 C2 A4 DB 000H,0E0H,0C2H,0A4H,088H,06CH,052H,038H 04E4 88 6C 52 38 04E8 20 08 F2 DC DB 020H,008H,0F2H,0DCH,0C8H,0B4H,0A2H,090H 04EC C8 B4 A2 90 04F0 80 70 62 54 DB 080H,070H,062H,054H,048H,03CH,032H,028H 04F4 48 3C 32 28 04F8 20 18 12 0C DB 020H,018H,012H,00CH,008H,004H,002H,000H 04FC 08 04 02 00 0500 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H ; high byte 0504 00 00 00 00 0508 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H 050C 00 00 00 00 0510 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,001H 0514 00 00 00 01 0518 01 01 01 01 DB 001H,001H,001H,001H,001H,001H,001H,001H 051C 01 01 01 01 0520 02 02 02 02 DB 002H,002H,002H,002H,002H,002H,002H,002H 0524 02 02 02 02 0528 03 03 03 03 DB 003H,003H,003H,003H,003H,003H,004H,004H 052C 03 03 04 04 0530 04 04 04 05 DB 004H,004H,004H,005H,005H,005H,005H,005H 0534 05 05 05 05 0538 06 06 06 06 DB 006H,006H,006H,006H,007H,007H,007H,007H 053C 07 07 07 07 0540 08 08 08 08 DB 008H,008H,008H,008H,009H,009H,009H,009H 0544 09 09 09 09 0548 0A 0A 0A 0A DB 00AH,00AH,00AH,00AH,00BH,00BH,00BH,00CH 054C 0B 0B 0B 0C 0550 0C 0C 0D 0D DB 00CH,00CH,00DH,00DH,00DH,00EH,00EH,00EH 0554 0D 0E 0E 0E 0558 0F 0F 0F 10 DB 00FH,00FH,00FH,010H,010H,010H,011H,011H 055C 10 10 11 11 0560 12 12 12 13 DB 012H,012H,012H,013H,013H,013H,014H,014H 0564 13 13 14 14 0568 15 15 15 16 DB 015H,015H,015H,016H,016H,017H,017H,018H 056C 16 17 17 18 0570 18 18 19 19 DB 018H,018H,019H,019H,01AH,01AH,01BH,01BH 0574 1A 1A 1B 1B 0578 1C 1C 1D 1D DB 01CH,01CH,01DH,01DH,01EH,01EH,01FH,01FH 057C 1E 1E 1F 1F 0580 20 20 21 21 DB 020H,020H,021H,021H,022H,022H,023H,023H 0584 22 22 23 23 0588 24 24 25 25 DB 024H,024H,025H,025H,026H,026H,027H,027H 058C 26 26 27 27 0590 28 29 29 2A DB 028H,029H,029H,02AH,02AH,02BH,02BH,02CH 0594 2A 2B 2B 2C 0598 2D 2D 2E 2E DB 02DH,02DH,02EH,02EH,02FH,030H,030H,031H 059C 2F 30 30 31 05A0 32 32 33 33 DB 032H,032H,033H,033H,034H,035H,035H,036H 05A4 34 35 35 36 05A8 37 37 38 39 DB 037H,037H,038H,039H,039H,03AH,03BH,03BH 05AC 39 3A 3B 3B 05B0 3C 3D 3D 3E DB 03CH,03DH,03DH,03EH,03FH,03FH,040H,041H 05B4 3F 3F 40 41 05B8 42 42 43 44 DB 042H,042H,043H,044H,045H,045H,046H,047H 05BC 45 45 46 47 05C0 48 48 49 4A DB 048H,048H,049H,04AH,04BH,04BH,04CH,04DH 05C4 4B 4B 4C 4D 05C8 4E 4E 4F 50 DB 04EH,04EH,04FH,050H,051H,052H,052H,053H 05CC 51 52 52 53 05D0 54 55 56 56 DB 054H,055H,056H,056H,057H,058H,059H,05AH 05D4 57 58 59 5A 05D8 5B 5B 5C 5D DB 05BH,05BH,05CH,05DH,05EH,05FH,060H,061H 05DC 5E 5F 60 61 05E0 62 62 63 64 DB 062H,062H,063H,064H,065H,066H,067H,068H 05E4 65 66 67 68 05E8 69 6A 6A 6B DB 069H,06AH,06AH,06BH,06CH,06DH,06EH,06FH 05EC 6C 6D 6E 6F 05F0 70 71 72 73 DB 070H,071H,072H,073H,074H,075H,076H,077H 05F4 74 75 76 77 05F8 78 79 7A 7B DB 078H,079H,07AH,07BH,07CH,07DH,07EH,07FH 05FC 7C 7D 7E 7F

　以上、最適化について書きましたが個人的には中々面白い結果になったのではないかと思います。


★追記　2023/06/23
　「Z80での高速な乗算処理（その３）２バイト乗算への適用検討」の記事に２バイト乗算への適用検討について記載しました。


[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]

タグ：Minus square method マイナス二乗法 高速乗算 符号なし8ビット Multiplication 乗算 Z80

Z80での高速な乗算処理

　Twitter のタイムラインで見かけた

(x+y)^2 - (x-y)^2 = 4*x*y     ⇒　x*y = ((x+y)^2 - (x-y)^2) / 4

の等式を利用し、テーブルを使って二乗計算を速く行うことで乗算処理を高速にできる・・と言うことがずっと頭の片隅に残っていました。
　時間もあるので少し検討してみたいと思います。以降上記の手法をプラマイ二乗法と記します。

1. プラマイ二乗法の検討
   　8bit の二乗は最大で 16bit になるので二乗の結果を収めた 512 バイトのテーブルが必要になります。上位バイトと下位バイトを必ずペアでアクセスするので上位アドレスの使い回しができるように下位バイトのテーブルと上位バイトのテーブルに分けました。
   　コードを考える上で問題となるのが (x + y) が最大 9 ビットになることです。9 ビットになった場合、MSBとそれ以外の 8 ビットを分離して処理しようとすると
   
   

   (2^8 + x)^2     = 2^16 + 2^8*2*x + x*x     = 2^16 + 2^9*x + x*x

   
   となり、x の二乗を求めた後に 9 bit シフトして加算する必要があり、その後 4 で割るので 18 ビットの演算が必要になります。
   　場合分けしてもできそうですが、面倒になる根源は x+y という項があることです。そこで　加算の二乗を使わない方法を考えてみました。
   
   
   
2. マイナス二乗法
   
　上記のようにプラスの項が処理を面倒にする原因なので下記のようにマイナスの二乗のみを使ってみることにしました。二乗の回数が1つ増えますが二乗計算はテーブル引きなので低コストで処理出来ます。この手法をマイナス二乗法と呼ぶことにします。



(x - y)^2 = x^2 -2*x*y + y^2     ⇒　x*y = (x^2 + y^2 - (x - y)^2) / 2


　アセンブラで書いたソースが下記になります。それほど最適化していないのでまだのりしろがあると思います。



今回考案したマイナス二乗法での乗算処理（Z80アセンブラ）

; unsigned 8 bits fast multi(my method) ; x*y = (x^2 + y^2 - (x-y)^2)/2 ; E <- data0 ; L <- data1 ; HL -> data0 * data1 016C 7D FMul8: LD A,L ; 4 016D BB CP E ; 4 016E 30 02 JR NC,FMul10 ; 12/7 0170 EB EX DE,HL ; 4 0171 7D LD A,L ; 4 0172 26 03 FMul10: LD H,HIGH MULTBL+1 ; 7 0174 46 LD B,(HL) ; 7 0175 25 DEC H ; 4 0176 4E LD C,(HL) ; 7 0177 93 SUB E ; 4 0178 6F LD L,A ; 4 0179 79 LD A,C ; 4 017A 96 SUB (HL) ; 7 017B 4F LD C,A ; 4 017C 24 INC H ; 4 017D 78 LD A,B ; 4 017E 9E SBC A,(HL) ; 7 017F 47 LD B,A ; 4 0180 6B LD L,E ; 4 0181 56 LD D,(HL) ; 7 0182 25 DEC H ; 4 0183 7E LD A,(HL) ; 7 0184 81 ADD A,C ; 4 0185 6F LD L,A ; 4 0186 78 LD A,B ; 4 0187 8A ADC A,D ; 4 0188 1F RRA ; 4 0189 67 LD H,A ; 4 018A CB 1D RR L ; 8 018C C9 RET ; 10 ; Max 154 = 4+4+(7+4+4)+7+7+4+7+4+4+4+7+4+4+4+7+4+4+7+4+7+4+4+4+4+4+4+8+10  ; Min 151 = 4+4+(12)+7+7+4+7+4+4+4+7+4+4+4+7+4+4+7+4+7+4+4+4+4+4+4+8+10 ; Ave 152.5 ORG ($ + 255) AND 0FF00H ; 8bit ^ 2 table 0200 MULTBL: 0200 00 01 04 09 DB 000H,001H,004H,009H,010H,019H,024H,031H ; low byte 0204 10 19 24 31 0208 40 51 64 79 DB 040H,051H,064H,079H,090H,0A9H,0C4H,0E1H 020C 90 A9 C4 E1 0210 00 21 44 69 DB 000H,021H,044H,069H,090H,0B9H,0E4H,011H 0214 90 B9 E4 11 0218 40 71 A4 D9 DB 040H,071H,0A4H,0D9H,010H,049H,084H,0C1H 021C 10 49 84 C1 0220 00 41 84 C9 DB 000H,041H,084H,0C9H,010H,059H,0A4H,0F1H 0224 10 59 A4 F1 0228 40 91 E4 39 DB 040H,091H,0E4H,039H,090H,0E9H,044H,0A1H 022C 90 E9 44 A1 0230 00 61 C4 29 DB 000H,061H,0C4H,029H,090H,0F9H,064H,0D1H 0234 90 F9 64 D1 0238 40 B1 24 99 DB 040H,0B1H,024H,099H,010H,089H,004H,081H 023C 10 89 04 81 0240 00 81 04 89 DB 000H,081H,004H,089H,010H,099H,024H,0B1H 0244 10 99 24 B1 0248 40 D1 64 F9 DB 040H,0D1H,064H,0F9H,090H,029H,0C4H,061H 024C 90 29 C4 61 0250 00 A1 44 E9 DB 000H,0A1H,044H,0E9H,090H,039H,0E4H,091H 0254 90 39 E4 91 0258 40 F1 A4 59 DB 040H,0F1H,0A4H,059H,010H,0C9H,084H,041H 025C 10 C9 84 41 0260 00 C1 84 49 DB 000H,0C1H,084H,049H,010H,0D9H,0A4H,071H 0264 10 D9 A4 71 0268 40 11 E4 B9 DB 040H,011H,0E4H,0B9H,090H,069H,044H,021H 026C 90 69 44 21 0270 00 E1 C4 A9 DB 000H,0E1H,0C4H,0A9H,090H,079H,064H,051H 0274 90 79 64 51 0278 40 31 24 19 DB 040H,031H,024H,019H,010H,009H,004H,001H 027C 10 09 04 01 0280 00 01 04 09 DB 000H,001H,004H,009H,010H,019H,024H,031H 0284 10 19 24 31 0288 40 51 64 79 DB 040H,051H,064H,079H,090H,0A9H,0C4H,0E1H 028C 90 A9 C4 E1 0290 00 21 44 69 DB 000H,021H,044H,069H,090H,0B9H,0E4H,011H 0294 90 B9 E4 11 0298 40 71 A4 D9 DB 040H,071H,0A4H,0D9H,010H,049H,084H,0C1H 029C 10 49 84 C1 02A0 00 41 84 C9 DB 000H,041H,084H,0C9H,010H,059H,0A4H,0F1H 02A4 10 59 A4 F1 02A8 40 91 E4 39 DB 040H,091H,0E4H,039H,090H,0E9H,044H,0A1H 02AC 90 E9 44 A1 02B0 00 61 C4 29 DB 000H,061H,0C4H,029H,090H,0F9H,064H,0D1H 02B4 90 F9 64 D1 02B8 40 B1 24 99 DB 040H,0B1H,024H,099H,010H,089H,004H,081H 02BC 10 89 04 81 02C0 00 81 04 89 DB 000H,081H,004H,089H,010H,099H,024H,0B1H 02C4 10 99 24 B1 02C8 40 D1 64 F9 DB 040H,0D1H,064H,0F9H,090H,029H,0C4H,061H 02CC 90 29 C4 61 02D0 00 A1 44 E9 DB 000H,0A1H,044H,0E9H,090H,039H,0E4H,091H 02D4 90 39 E4 91 02D8 40 F1 A4 59 DB 040H,0F1H,0A4H,059H,010H,0C9H,084H,041H 02DC 10 C9 84 41 02E0 00 C1 84 49 DB 000H,0C1H,084H,049H,010H,0D9H,0A4H,071H 02E4 10 D9 A4 71 02E8 40 11 E4 B9 DB 040H,011H,0E4H,0B9H,090H,069H,044H,021H 02EC 90 69 44 21 02F0 00 E1 C4 A9 DB 000H,0E1H,0C4H,0A9H,090H,079H,064H,051H 02F4 90 79 64 51 02F8 40 31 24 19 DB 040H,031H,024H,019H,010H,009H,004H,001H 02FC 10 09 04 01 0300 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H ; high byte 0304 00 00 00 00 0308 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H 030C 00 00 00 00 0310 01 01 01 01 DB 001H,001H,001H,001H,001H,001H,001H,002H 0314 01 01 01 02 0318 02 02 02 02 DB 002H,002H,002H,002H,003H,003H,003H,003H 031C 03 03 03 03 0320 04 04 04 04 DB 004H,004H,004H,004H,005H,005H,005H,005H 0324 05 05 05 05 0328 06 06 06 07 DB 006H,006H,006H,007H,007H,007H,008H,008H 032C 07 07 08 08 0330 09 09 09 0A DB 009H,009H,009H,00AH,00AH,00AH,00BH,00BH 0334 0A 0A 0B 0B 0338 0C 0C 0D 0D DB 00CH,00CH,00DH,00DH,00EH,00EH,00FH,00FH 033C 0E 0E 0F 0F 0340 10 10 11 11 DB 010H,010H,011H,011H,012H,012H,013H,013H 0344 12 12 13 13 0348 14 14 15 15 DB 014H,014H,015H,015H,016H,017H,017H,018H 034C 16 17 17 18 0350 19 19 1A 1A DB 019H,019H,01AH,01AH,01BH,01CH,01CH,01DH 0354 1B 1C 1C 1D 0358 1E 1E 1F 20 DB 01EH,01EH,01FH,020H,021H,021H,022H,023H 035C 21 21 22 23 0360 24 24 25 26 DB 024H,024H,025H,026H,027H,027H,028H,029H 0364 27 27 28 29 0368 2A 2B 2B 2C DB 02AH,02BH,02BH,02CH,02DH,02EH,02FH,030H 036C 2D 2E 2F 30 0370 31 31 32 33 DB 031H,031H,032H,033H,034H,035H,036H,037H 0374 34 35 36 37 0378 38 39 3A 3B DB 038H,039H,03AH,03BH,03CH,03DH,03EH,03FH 037C 3C 3D 3E 3F 0380 40 41 42 43 DB 040H,041H,042H,043H,044H,045H,046H,047H 0384 44 45 46 47 0388 48 49 4A 4B DB 048H,049H,04AH,04BH,04CH,04DH,04EH,04FH 038C 4C 4D 4E 4F 0390 51 52 53 54 DB 051H,052H,053H,054H,055H,056H,057H,059H 0394 55 56 57 59 0398 5A 5B 5C 5D DB 05AH,05BH,05CH,05DH,05FH,060H,061H,062H 039C 5F 60 61 62 03A0 64 65 66 67 DB 064H,065H,066H,067H,069H,06AH,06BH,06CH 03A4 69 6A 6B 6C 03A8 6E 6F 70 72 DB 06EH,06FH,070H,072H,073H,074H,076H,077H 03AC 73 74 76 77 03B0 79 7A 7B 7D DB 079H,07AH,07BH,07DH,07EH,07FH,081H,082H 03B4 7E 7F 81 82 03B8 84 85 87 88 DB 084H,085H,087H,088H,08AH,08BH,08DH,08EH 03BC 8A 8B 8D 8E 03C0 90 91 93 94 DB 090H,091H,093H,094H,096H,097H,099H,09AH 03C4 96 97 99 9A 03C8 9C 9D 9F A0 DB 09CH,09DH,09FH,0A0H,0A2H,0A4H,0A5H,0A7H 03CC A2 A4 A5 A7 03D0 A9 AA AC AD DB 0A9H,0AAH,0ACH,0ADH,0AFH,0B1H,0B2H,0B4H 03D4 AF B1 B2 B4 03D8 B6 B7 B9 BB DB 0B6H,0B7H,0B9H,0BBH,0BDH,0BEH,0C0H,0C2H 03DC BD BE C0 C2 03E0 C4 C5 C7 C9 DB 0C4H,0C5H,0C7H,0C9H,0CBH,0CCH,0CEH,0D0H 03E4 CB CC CE D0 03E8 D2 D4 D5 D7 DB 0D2H,0D4H,0D5H,0D7H,0D9H,0DBH,0DDH,0DFH 03EC D9 DB DD DF 03F0 E1 E2 E4 E6 DB 0E1H,0E2H,0E4H,0E6H,0E8H,0EAH,0ECH,0EEH 03F4 E8 EA EC EE 03F8 F0 F2 F4 F6 DB 0F0H,0F2H,0F4H,0F6H,0F8H,0FAH,0FCH,0FEH 03FC F8 FA FC FE


　参考として、テーブルを使わない一般的な乗算処理は下記のようになるのではないかと思います。



一般的な unsigned 8 ビットの乗算処理（Z80アセンブラ）

; unsigned 8 bits normal multi(normal method) ; E <- data0 ; L <- data1 ; HL -> data0 * data1 018D 65 NMul: LD H,L ; 4 018E 2E 00 LD L,0 ; 7 0190 55 LD D,L ; 4 0191 06 08 LD B,8 ; 7 0193 29 NMul10: ADD HL,HL ; 11 0194 30 01 JR NC,NMul20 ; 12/7 0196 19 ADD HL,DE ; 11 0197 10 FA NMul20: DJNZ NMul10 ; 13/8 0199 C9 RET ; 10 ; Max 363 = 4+7+4+7+((11+(7+11)+13)*8-13+8)+10 ; Max 315 = 4+7+4+7+((11+(12)+13)*8-13+8)+10 ; Ave 339




3. 各方式の比較
   　冒頭で紹介した Twitter メッセージには URL も書いてあったのでプラマイ二乗法の処理を確認して見ました。
   　二乗テーブルの持ち方は前項で書いたマイナス二乗法と同じですね。x+y が 9 bit になった場合の対処として偶数と奇数の場合に場合分けして処理していました。処理のステート数については「CPC Cycles: 136-172 (154 on average)」と書いてあります。
   　三つの方式のステート数の一覧が下表になります。
   
   

   No.	Method	Max	Min	Average
   1	Normal method	363	315	339.0
   2	Minus square method	154	151	152.5
   3	Plamai square method	172	136	154.0

   ★変更　2023/02/13 Normal method のステート数を修正
   　今回作ったマイナス二乗法はノーマル処理の約２倍の速さと言うことになります。
   　ネットにあったプラマイ二乗法の処理を下に示しますが、ステート数を数えると Max:158, Min:129, Ave:143.5 になります。
   　下記のソースでは引数とリターン値を入れるレジスタのアサインを不自然に感じますが、本来の処理は引数とリターン値を入れるレジスタがリーズナブルな物であり、その分のステート数を加えたものが上記の表内の数値になるのかもしれません（マイナス二乗法でもリターン値をHLに揃えなくてもよければそれだけで数ステート短くなります）。
   
   ★追記　202/02/19　{
   　プラマイ二乗法が CPCWiKi に追加される際の議論を見つけました。この中でシフト命令等を変更してより高速化されています。最終ソースのステート数が異なるのはこの為かも知れません。
   }
   
   

   ネットで公開されていた高速乗算処理（Z80アセンブラ）

   ; Web version finded in Internet ; A,B <- data0,data1 ; A:E -> data0*data1 019A B8 IMul: cp b ; 4 019B 30 03 jr nc,l1 ; 12/7 019D 5F ld e,a ; 4 019E 78 ld a,b ; 4 019F 43 ld b,e ; 4 01A0 4F l1: ld c,a ; 4 01A1 90 sub b ; 4 01A2 1F rra ; 4 01A3 57 ld d,a ; 4 01A4 79 ld a,c ; 4 01A5 80 add a,b ; 4 01A6 1F rra ; 4 01A7 6F ld l,a ; 4 01A8 26 02 ld h,high(MULTBL) ; 7 01AA 7E ld a,(hl) ; 7 01AB 5D ld e,l ; 4 01AC 6A ld l,d ; 4 01AD 30 0F jr nc,l2 ; 12/7 01AF 96 sub (hl) ; 7 odd 01B0 6B ld l,e ; 4 01B1 5F ld e,a ; 4 01B2 24 inc h ; 4 loads high(sqrhi) 01B3 7E ld a,(hl) ; 7 01B4 6A ld l,d ; 4 01B5 9E sbc a,(hl) ; 7 01B6 57 ld d,a ; 4 01B7 7B ld a,e ; 4 01B8 80 add a,b ; 4 01B9 5F ld e,a ; 4 01BA 7A ld a,d ; 4 01BB CE 00 adc a,0 ; 7 01BD C9 ret ; 10 01BE 96 l2: sub (hl) ; 7 even 01BF 6B ld l,e ; 4 01C0 5F ld e,a ; 4 01C1 24 inc h ; 4 01C2 7E ld a,(hl) ; 7 01C3 6A ld l,d ; 4 01C4 9E sbc a,(hl) ; 7 01C5 C9 ret ; 10 ; Max 158 = 4+(7+4+4+4)+4+4+4+4+4+4+4+4+7+7+4+4+(7+7+4+4+4+7+4+7+4+4+4+4+4+7+10) ; Min 129 = 4+(12)+4+4+4+4+4+4+4+4+7+7+4+4+(12+7+4+4+4+7+4+7+10) ; Ave 143.5

   
   
   
4. 応用編
   　8 ビットの高速な乗算処理ができたので「ＧＡＭＥ言語での ASCIIART の高速化」の記事で書いた ASCIIART に適用してみました。
   　先の記事では 16 ビットの固定小数点の乗算処理を作って高速化しましたが、今回は手抜きをして次の方法で 8 ビット乗算で 16 ビット乗算を作ってみました。
   
   

   (256*x1 + x0)*(256*y1 + y0)   = 2^16*x1y1 + 2^8*(x0*y1 + x1*y0) + x0*y0

   
   　従来のアセンブラで書いた ASCIIART（asciiar2）を実行後に、今回の乗算処理を組み込んだ ASCIIART（fasciiar）を実行した画面が、下図になります。実行環境は Z80 が 12MHz で動作している環境です。
   
   　TeraTerm のマクロで実行時間を計測した結果も表示されていますが、それを見ると実行時間はほぼ同じ（寧ろ若干遅くなっている）ですね。16 ビット化するための上記の展開式の処理のオーバーヘッドが元々の 2 倍速を食いつぶしてしまったようです。
   
   ★追記　2023/02/17　{
   　上記で使用した固定小数点演算では 2byte x 2byte の結果の 4byte の中央の 2byte のみ必要なため、内部では 24 bit の計算をしているので通常のオーバーフロー無しの乗算処理（結果が 32 bit）よりは速いものです。
   }
   
   　それにしても意外だったのは新乗算処理を組み込んだ後、一発で ASCIIART が表示されたことです。気分のいいところでそろそろ筆を置きたいと思います。
   
   

   ASCIIART 実行結果

★追記　2023/02/15
　「Z80での高速な乗算処理（その２）最適化」の記事に最適化して更に高速化したことについて記載しました。


[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]

タグ：マイナス二乗法 Minus square method Z80 乗算 Multiplication 符号なし8ビット 高速乗算

超小型Z80マイコン（その１２）PCBへの部品実装

　前回の記事でプリント基板のパターン設計について書きましたが、製造依頼していたプリント基板が届いたので、今回は部品実装と動作確認について書いてみます（写真が多めです）。

　いつもの様にコンパクト化のために表面実装部品を両面に実装しています。まずはトップ面ですが、SRAM と USB コネクタ等を実装しています。SMD 部品実装後の写真が下図になります。

トップ面への SMD 部品の実装

　下図は SMD 部品実装後のボトム面でPIC（PIC18F14K50）や TF カードコネクタ等を実装しています。PIC は SSOP パッケージにしようかとも思いましたが、設計当初、秋月さんで品切れだったことと SOP よりも高かったので SOP パッケージのタイプにしました。

ボトム面への SMD 部品の実装

　Z80 用の 40 ピンソケット実装後のトップ面が下の写真です。ソケットのピン位置が基板の淵ギリギリになるまで攻め込んでいますｗ

40 ピンソケット実装後のトップ面

　ソケット実装後のボトム面が下の写真です。TF カードコネクタとソケットのピンとの隙間が殆ど無いのでコネクタ側をカプトンテープで絶遠しました。

40 ピンソケット実装後のボトム面

　Z80 実装後のトップ面が下の写真です。基板幅が Z80 とほぼ同じですねｗ

Z80 実装後のトップ面

　部品実装後に簡易的な導通試験を行い、電源を入れてみましたが USB は認識しているようですが TeraTerm の画面には何も表示されませんorz

　コンパクト化した基板の調査は大変です・・・

　Z80 の信号をロジアナで観測し易くするためにピンヘッダとピンソケットを使って下駄を作成してみました。細ピンヘッダを使用しましたが、丸ピンソケットを取り付け可能という40 ピンの ZIF ソケットには太すぎて取付けられませんでした^^;
　気を取り直して普通の ZIF ソケットに取付け、ZIF ソケットには平ピンソケットを付けて基板上の丸ピンソケットに差し込みました。

Z80 信号測定用の下駄

　Z80 周りの信号が観測可能になれば、動作原理が判っているので問題究明は割合簡単です。SMD 部品の半田付け NG 部分を２カ所修復して無事動作するようになりました^^

　改めてウレタン線で手配線した開発用のものと今回組み上げたプリント基板のものを並べてみました。かなりコンパクトになっていますね^^

開発用基板とプリント基板のサイズ比較

　ん～　想定通りのコンパクトさです^^
　DIP40 ピンの Z80 を使用して CP/M が動く基板をこれ以上小さく作るのは難しいのではないでしょうか？

完成した Z80PicCompact

　Twitter に投稿した動画付きメッセージを貼っておきます。

20ピンのPICを使用した3チップ構成小型Z80ボードが動きました^^/
Z80とほぼ同サイズでUSBケーブルを接続するだけでCP/Mが動きます（CP/Mの自動起動も可能）
40ピンのZ80を使用しCP/Mが動くワンボードをこれより小さく作れるだろうか？https://t.co/MS93rro48R#Z80PicCompact #Z80 #CPM #PIC18F14K50 https://t.co/0z7EbalNZh pic.twitter.com/Cn1SrwBnxd

— skyriver (@wcinp) February 8, 2023

★追記　2022/02/09
　Twitter の動画に基板の写真等を追加して YouTube で公開しましたので貼っておきます。

★追記　2023/03/13
　回路とプリント基板のパターンの設計に使った Design Spark PCB から３Ｄデータを Design Spark Mechanical に引き継いでケースを設計しました。

ＰＣＢ設計の３Ｄデータでケース設計

　下図は設計が完了した状態でのスケルトン表示です。

設計完了状態のスケルトン表示

　透明の PETG フィラメントで出力したケースに入れた状態が下の写真になります。

ケースに入れた　Z80PicCompact

★追記　2023/05/16　{
　「超小型Z80マイコン（その１４）開発機のケース製作」の最後の方で書いた２液式エポキシ接着剤と溶剤を使ったコーティングを Z80PicCompact のケースに行ってみました。
　写真では少し判り辛いですが、ケースの透明度が結構増しました。

　トップ面が下の写真になります。Ｚ８０のチップサイズとほぼ同じなのでＺ８０のチップ自体はまだ見え辛いのですがチップのリードも見えるようになりました。

コーティング後の Z80PicCompact ケース（トップ面）

　下の写真はボトム面です。TFカードコネクタ等もはっきり見えますね。

コーティング後の Z80PicCompact ケース（ボトム面）

}


[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]

タグ：BlogZ80PicCompact PIC18F14K50 Z80PicCompact Twitter CP/M YouTube DesignSparkMechanical ケース作成

ポケコン（G850）用拡張基板（その１０）コンパクト化（その２）

　前回の記事ではポケコン （PC-G850V）用のシステムバスに接続するメモリ＆TFカードを実装したメモリ拡張ボード（Eborsy）のコンパクト化（Eborsy Compact）のパターン設計について書きましたが、製造依頼した基板が届いたので部品を実装してみました。

　PC-G850V のシステムバス端子用のコネクタは aitendo さんで販売していて品切れ状態が続いていましたが、また復活したようなので少し前に購入しました。

　しかし基板に実装しようとするとうまく入りません。開発用 Eborsy を作ったころに購入したコネクタも残っていたので並べてみたものが下の写真です。左側が古いものです。パッと見は同じですがよく見てみると千鳥状に曲げてあるピンの曲げ方が逆になっていますorz
　尚、写真では側面の溝の幅も違いますがこれはＺ軸に180°回転すると同じ溝幅になります（成形の型は同じものの様です）。今回は取り合えず１個しか残っていない古い方のコネクタを使用しました。

システムバス用コネクタ（左：旧タイプ、右：新タイプ）

　部品実装後、最初は動かなかったのですが、基板を調べてみると SPI インターフェースの部分で使っているショットキーバリアダイオードのシルクが逆なため、実装も逆になっていました。回路を確認したところ問題ありませんでしたが、パターン設計画面でショットキーのデータをアップデートしたところ正常になりました。この部品のフットプリントはネットからダウンロードしたもので編集はしていないはずですがどうして逆になってしまったのか謎です。

　部品実装後の Eborsy Compact と開発用の Eborsy を並べて撮った写真も貼っておきます。今回作成した Compact の方は名前通りかなりコンパクトになっていますね＾＾

Eborsy Compact（左）と開発用 Eborsy（右）

　下の写真はトップ面の写真です。最初は上手く動かず半田ごてで追半田したので見た目があまり綺麗じゃないですね ^^;

Eborsy Compact（トップ面）

　下の写真がボトム面です。GAL は PLCC パッケージのものを直付けしています。

Eborsy Compact（ボトム面）

　CP/M が無事に立上り、BDS C でコンパイルもでき、 MBASIC で ASCIIART も動きました。
　しかし、PC-850V は最後の 16KB 部分のメモリを外部 RAM に切り替えることが出来ないようなので、動作しているのは 46KB CP/M であり HI-TECH C はメモリ不足で動作しませんでした。


　twitter に投稿した動画付きメッセージも貼っておきます。

ポケコン（PC-G850V）のシステムバス端子用の自作ボードの基板が届き無事動作しました^^
PLCCパッケージのGALを直付けしていますが問題ありませんでした
aitendoさんでコネクタの在庫が復活していますが以前のものとピンの曲げ方が逆だったorzhttps://t.co/8ZepGIcVXj#G850 #CPM #EborsyCompact https://t.co/V4i2RojwAt pic.twitter.com/TkFpB8kGXX

— skyriver (@wcinp) February 5, 2023

[TOP] [ 前へ ] 連載記事 [ 次へ ]

タグ：G850 PC-G850V CP/M システムバス ポケコン TFカード メモリ増設 EborsyCompact Eborsy