Implement constant-latency branchless multiplication efficiently

Question

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.

Goal

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 c and d, after which the result will be stored in registers a and b, a storing the lower bits and b storing the higher bits. You don't have to preserve the input in c and d.

Spec

The machine has 26 8-bit registers from a to 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.

Score

The total sum of latency cycles plus the number of registers used will be your score, the lower the better.

Available Instructions

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 mov, swp, setX, and 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 r0 to 1 if the specified flag was set, and 0 otherwise ; z -> ZF, nz -> not ZF, c -> CF, nc -> not CF
• mskz/msknz/mskc/msknc r0 (1) : set r0 to 0xff if the specified flag was set, and 0 otherwise
• 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 a to o, and you have to write shr a, 1 instead of shr a etc. because of NASM syntax.

This is a scoring program written by @tsh. It is also a full featured tester. I'd like to explain how to use it if I know Javascript, but unfortunately I don't. Feel free to edit this post if you can add an explanation.

Answer 1

Score: 94 92

Reduced score by 1 thanks to @xiver77.

rol c
mskc a
and a, d
shl a
setc b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0
shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0

Explanation:

rol c
mskc a
and a, d

Multiply the MSB of c by d.

shl a
rcl b
rol c
mskc e
and e, d
add a, e
adc b, 0

For each of the remaining seven bits, double ba and add d multiplied by the bit (setc b is used instead of rcl b for the first bit since it scores 1 fewer).

Answer 2

87 82 80, destroying c

shl c
mskc a
and a, d

shl a
rcl c
mskc e
and e, d
add a, e
setc b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

shl a
rcl c
mskc e
and e, d
add a, e
rcl b

add b, c
  

82 preserving c is trivial from 80 destroying it

Didn't notice that mul from most significant is faster

104

1 reg a # output low
1 reg b # output high
1 reg c # input 
1 reg d # input
1 reg e # cur
1 reg f # back
0 # bit 0
1 ror d
1 msk a, C # mskc a by OP
2 and a, c
1 mov b, a
0 # bit 1
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 254
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 252
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 248
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 240
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 224
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 192
2 add a, e
3 adc b, f
1 rol c
1 ror d
1 msk e, C
2 and e, c
1 mov f, e
2 and e, 128
2 add a, e
3 adc b, f
0 # fix b
2 sub b, a

Writing set a, C feel better and align friendly than setc a