Modern hardware can perform multiplication very fast in a constant latency of 3~4 cycles. But some tiny chips for embedded environments sometimes lack hardware multiplication, which has to be emulated by a series of instructions.
You are given a primitive CPU with a set of basic operations. Your job is to implement unsigned multiplication of two 8-bit numbers, each in register
d, after which the result will be stored in registers
a storing the lower bits and
b storing the higher bits. You don't have to preserve the input in
The machine has 26 8-bit registers from
z, whose initial value is
0. You are allowed to use all of them freely to implement this operation.
There are no "jumps" or branching instructions, but there are flags conditionally set according to the last operation.
- ZF : zero flag; set if the result is zero
- CF : carry flag; set if the result is "wrapped" for addition/subtraction; set if a bit was "carried out" for shift/rotation
There is no memory access.
The total sum of latency cycles plus the number of registers used will be your score, the lower the better.
instr r0 r1/imm (2) means
instr takes two register operands, of which the second one can be an 8-bit immediate operand, and this instruction takes 2 cycles to complete.
All operations except
mskX sets the zero flag accordingly.
mov r0 r1/imm (1):
r0 = r1
swp r0 r1 (2):
r0 = r1,
r1 = r0
sswp r0 (2): swap the low 4 bits and the high 4 bits
setz/setnz/setc/setnc r0 (1): set
1if the specified flag was set, and
z -> ZF, nz -> not ZF, c -> CF, nc -> not CF
mskz/msknz/mskc/msknc r0 (1): set
0xffif the specified flag was set, and
add r0 r1/imm (2):
r0 = r0 + r1; CF affected
sub r0 r1/imm (2):
r0 = r0 - r1; CF affected
adc r0 r1/imm (3):
r0 = r0 + r1 + CF; CF affected
sbb r0 r1/imm (3):
r0 = r0 - r1 - CF; CF affected
and r0 r1/imm (2):
r0 = r0 & r1
or r0 r1/imm (2):
r0 = r0 | r1
xor r0 r1/imm (2):
r0 = r0 ^ r1
shr r0 (1): bitshift right once shifting in a zero; CF is the old least significant bit (LSB)
shl r0 (1): bitshift left once shifting in a zero; CF is the old most significant bit (MSB)
ror r0 (1): rotate right; bitshift right once shifting in the LSB; CF is the old LSB
rol r0 (1): rotate left; bitshift left once shifting in the MSB; CF is the old MSB
rcr r0 (2): rotate right with carry; bitshift right once shifting in the CF; the new CF is the old LSB
rcl r0 (2): rotate left with carry; bitshift left once shifting in the CF; the new CF is the old MSB
not r0 (2): bitwise not
neg r0 (2): two's complement negation; same as
not r0; add r0 1;
CF = not ZF
Here, you can test your code that is translated to x86 assembly. Write your code below the label
mulb:. I also added a working implementation ported from the work of @l4m2.
The tester has some limitations, though. It only supports 15 registers from
o, and you have to write
shr a, 1 instead of
shr a etc. because of NASM syntax.