Efficient and Concise Multiplication in CHIP-8 I've entertained how to nicely express a decent many algorithms in CHIP-8 but hadn't thought my such thoughts warranted an article. I recently read of someone doing something similar, and this changed my mind. This other wrote a program to unintelligently and inefficiently find instruction listings. My approach targets multiplication and uses simple logic to get, I think, a nicer result; in mulling possible instructions, it's clear which are applicable; if the machine can or can't perform the task in one instruction it's clear if, say, two are found to suffice they form an answer and upper bound. Binary shifts give powers of two a clear advantage, and an important aspect of intelligently hacking machine code is to consider global optimizations; this simple routine is optimal for all such shifts and it could be optimized further through more indirection to handle register management. The first shift is unnecessary; it ultimately clears the register. These are placed at no particular address: 400-401 1024-1025 ^ ___ 800E 32782 *256 V0 <- V0 * 2; VF <- MSB 402-403 1026-1027 ^ ___ 800E 32782 *128 V0 <- V0 * 2; VF <- MSB 404-405 1028-1029 ^ ___ 800E 32782 *64 V0 <- V0 * 2; VF <- MSB 406-407 1030-1031 ^ ___ 800E 32782 *32 V0 <- V0 * 2; VF <- MSB 408-409 1032-1033 ^ ___ 800E 32782 *16 V0 <- V0 * 2; VF <- MSB 40A-40B 1034-1035 ^ ___ 800E 32782 *8 V0 <- V0 * 2; VF <- MSB 40C-40D 1036-1037 ^ ___ 800E 32782 *4 V0 <- V0 * 2; VF <- MSB 40E-40F 1038-1039 ^ ___ 800E 32782 *2 V0 <- V0 * 2; VF <- MSB 410-411 1040-1041 ___ ___ 00EE 00238 Return Addition of a register with itself or a lone shift instruction are both suitable for a doubling, but the latter has the significant advantage of selecting a destination register rather than clobbering. A simple multiplication by three uses a second register, forming this trivial pair: 200-201 0512-0513 ^ ___^ 810E 33038 V1 <- V0 * 2; VF <- MSB 202-203 0514-0515 ^ _ ^ 8104 33028 V1 <- V1 + V0; VF <- overflow A multiplication by five is opportunity to use part of the routine and is a mere instruction larger: 200-201 0512-0513 ^ ^ 8100 33024 V1 <- V0 202-203 0514-0515 ^ _# 240C 09228 Call *4 204-205 0516-0517 ^ _ ^ 8104 33028 V1 <- V1 + V0; VF <- overflow Multiplying by seven is close enough to a power of two for this alternative approach to be pleasant: 200-201 0512-0513 ^ ^ 8100 33024 V1 <- V0 202-203 0514-0515 ^ _^_ 240A 09226 Call *8 204-205 0516-0517 ^ _ _ _ 8015 32789 V0 <- V0 - V1; VF <- borrow Multiplying by larger numbers well uses fragmentation; this takes twenty-four as eight plus sixteen: 200-201 0512-0513 ^ _ 8010 32784 V0 <- V1 202-203 0514-0515 ^ _^_ 240A 09226 Call *8 204-205 0516-0517 ^ ^ 8200 33280 V2 <- V0 206-207 0518-0519 ^ _ 8010 32784 V0 <- V1 208-209 0520-0521 ^ _^ 2408 09224 Call *16 20A-20B 0522-0523 ^ _ _ 8024 32804 V0 <- V0 + V2; VF <- overflow That's no comparison to the much nicer method of splitting twenty-four as eight times three, though: 200-201 0512-0513 ^ ____ 801E 32798 V0 <- V1 * 2; VF <- MSB 202-203 0514-0515 ^ _ _ 8014 32788 V0 <- V0 + V1; VF <- overflow 204-205 0516-0517 ^ _^_ 240A 09226 Call *8 The number forty-three, resulting by adding or subtracting powers of two, should suit as a bad case: 200-201 0512-0513 ^ _ 8010 32784 V0 <- V1 202-203 0514-0515 ^ #_ 2406 09222 Call *32 204-205 0516-0517 ^ ^ 8200 33280 V2 <- V0 206-207 0518-0519 ^ _ 8010 32784 V0 <- V1 208-209 0520-0521 ^ _^_ 240A 09226 Call *8 20A-20B 0522-0523 ^ _ _ 8024 32804 V0 <- V0 + V2; VF <- overflow 20C-20D 0524-0525 ^ _ _ 8014 32788 V0 <- V0 + V1; VF <- overflow 20E-20F 0526-0527 ^ _ _ 8014 32788 V0 <- V0 + V1; VF <- overflow 210-211 0528-0529 ^ _ _ 8014 32788 V0 <- V0 + V1; VF <- overflow Notice three additions is cost just large enough to make other approaches infeasible; multiplication by four, followed by a subtraction, is one instruction larger, due to the extra register management; replacing the three additions with one and a shifting results in the same count, and so isn't shown: 200-201 0512-0513 ^ _ 8010 32784 V0 <- V1 202-203 0514-0515 ^ #_ 2406 09222 Call *32 204-205 0516-0517 ^ ^ 8200 33280 V2 <- V0 206-207 0518-0519 ^ _ 8010 32784 V0 <- V1 208-209 0520-0521 ^ _^_ 240A 09226 Call *8 20A-20B 0522-0523 ^ _^ 8204 33284 V2 <- V2 + V0; VF <- overflow 20C-20D 0524-0525 ^ _ 8010 32784 V0 <- V1 20E-20F 0526-0527 ^ _# 240C 09228 Call *4 210-211 0528-0529 ^ _ _ 8024 32804 V0 <- V0 + V2; VF <- overflow 212-213 0530-0531 ^ _ _ _ 8015 32789 V0 <- V0 - V1; VF <- borrow Loop adding forty-three would be concise, but inefficient; a table is a good solution yet changes I: 200-201 0512-0513 ^ ^ _ ^ A208 41480 I <- forty three 202-203 0514-0515 ^^^#___ F01E 61470 I <- I + V0 204-205 0516-0517 ^##^ _ _ F065 61541 Load V0->V0; I <- I + 01 206-207 0518-0519 ___ ___ 00EE 00238 Return 208 0520 00 000 forty three 209 0521 # # ## 2B 043 20A 0522 # # ## 56 086 20B 0523 # # 81 129 20C 0524 # # ## AC 172 20D 0525 ## # ### D7 215 Know the lower registers are rather poor choices for practical routines here, and zero in particular due to its use by BXXX. I will provide no general rule for determining efficient multiplication, as this can easily be done by a human at a whim. An easy way to get good multiplication chooses a good number to multiply by. Making a routine unnecessary is much better than making such more efficient. .