2

I have this problem where I am asked to multiply BX by 42 without using any mul or div instructions, presumably by using shl or shr. It is also required to do it in 5 lines.

How do you do such a thing ?

I didn't try anything, but the above requirement was to multiply BX by 32 in 1 line, so I just used SHL BX, 5.

Sep Roland
  • 33,889
  • 7
  • 43
  • 76
wabulu
  • 25
  • 3
  • 3
    This problem is too hard for you; you need to [find a simpler problem](https://ericlippert.com/2014/03/21/find-a-simpler-problem/). You said you can multiply by 32, can you multiply by 10? – Corvus Nov 12 '22 at 14:36
  • 1
    Note that in 8086 it is not possible to do `shl bx, 5` in one line because [shl with immediate byte](https://pushbx.org/ecm/doc/insref.htm#insSHL) is an 186-level instruction. For a true 8086 you would have to set up `mov cl, 5` then `shl bx, cl` – ecm Nov 12 '22 at 17:05
  • 2
    if you're using 16-bit mode but could use 386 instructions and addressing modes, https://godbolt.org/z/3K78d9ja3 shows how to do it in 2 LEAs and an ADD, since 386 allows multiply by 5 with `lea ax, [ebx + ebx*4]`, and [How to multiply a register by 37 using only 2 consecutive leal instructions in x86?](https://stackoverflow.com/q/46480579) shows tricks like mixing and matching which temporaries you scale and add. But this isn't an answer to this question, since emu8086 effectively allows most 186 instructions but not later. On a modern x86 in 16-bit mode, you'd use `imul ax, bx, 42` – Peter Cordes Nov 12 '22 at 23:01

3 Answers3

3

Factor 42 (decimal) equals 00101010 (binary), and orders of 1s in this notation are 1, 3, 5, hence the result will be
21 * N + 23 * N + 25 * N = 42 * N.

The code assumes CPU Intel 186 or better and the factor N loaded in BX; product is returned in BX, too.
Unfortunately, it needs six instructions, I didn't manage to spare a line.

SHL BX,1   ; BX=2*N
MOV AX,BX  ; AX=2*N
SHL BX,2   ; BX=8*N
ADD AX,BX  ; AX=2*N + 8*N
SHL BX,2   ; BX=32*N
ADD BX,AX  ; BX=2*N + 8*N + 32*N = 42*N
vitsoft
  • 5,515
  • 1
  • 18
  • 31
  • It's real hard to do it in 5 lines. I have been at it quite some time now and hope that someone will soon come up with a 5-line solution... – Sep Roland Nov 12 '22 at 22:41
  • 1
    And this uses `shl reg, imm`, new in 186, not 8086. But emu8086 allows it in the asm source. I forget if it expands it like a pseudo-instruction or actually uses the 186 opcode. – Peter Cordes Nov 12 '22 at 22:54
  • 2
    @PeterCordes : EMU8086 emits a series of single bit shift instructions to achieve the desired effect. When you use the EMU8086 debugger you will see each individual shift instruction. – Michael Petch Nov 12 '22 at 23:40
  • @MichaelPetch: Thanks. Good thing the question says "5 lines" (of source code), not "5 instructions", then :P I don't suppose EMU8086 has a way to put multiple instructions one one line, like GAS `;` statement separator. Or define a macro and use it? – Peter Cordes Nov 13 '22 at 03:54
  • 2
    @SepRoland: I used [the Stoke superoptimizer](https://github.com/StanfordPL/stoke) to try to find a better sequence. It didn't find one. But that's not conclusive since it was allowed to use LEA but didn't find what GCC `-m32 -mtune=pentium` does. (https://godbolt.org/z/3K78d9ja3). It only works for x86-64, but it has whitelist / blacklist options. I had it trying to beat a 32-bit version of this code, since that's more natural for x86-64, and presumably the best strategy won't involve 8-bit halves. So I could tell it not to use byte or word versions of anything, and no `.*mul.*` etc. – Peter Cordes Nov 13 '22 at 08:01
3

A trio of solutions that have 6 lines and can run on emu8086 because that emulator does allow shifting by an immediate count, contrary to what a real 8086 CPU would allow!

On input BX = N

shl bx, 1   ; BX = N * 2 
mov ax, bx  ; AX = N * 2
shl bx, 2   ; BX = N * 8
add bx, ax  ; BX = N * 10
shl bx, 2   ; BX = N * 40
add bx, ax  ; BX = N * 42

mov ax, bx  ; AX = N
shl bx, 2   ; BX = N * 4
add ax, bx  ; AX = N * 5
shl bx, 2   ; BX = N * 16
add bx, ax  ; BX = N * 21
shl bx, 1   ; BX = N * 42

but the above requirement was to multiply BX by 32 in 1 line

mov ax, bx  ; AX = N
shl bx, 5   ; BX = N * 32
shl ax, 1   ; AX = N * 2 
add bx, ax  ; BX = N * 34
shl ax, 2   ; AX = N * 8
add bx, ax  ; BX = N * 42

Related assembly 8086 multiply 41 without using MUL

Sep Roland
  • 33,889
  • 7
  • 43
  • 76
3

An out of the box solution with 4 lines only would be

   xor ax,ax
   mov cx,42
a: add ax,bx
   loop a

Otherwise, the common approaches include shift and add using the binary representation of the constant 42 = 0b101010, as well as the Booth's encoding (turning a sequence of ones e.g. 0b11110 to one shift and one subtraction 0b100000 * A - 0b10 * A). Additionally one can factor out the constant 42 = 2*3*7, which would lead to 7A*6, which could be done as (A<<3 - A)*6, however that too needs 6 instructions.

One could possibly exploit the AAD instruction with undefined behaviour, which can be used to multiply an 8-bit value by another 8-bit value coded as the immediate.

Aki Suihkonen
  • 19,144
  • 1
  • 36
  • 57
  • Intel's current manual (https://www.felixcloutier.com/x86/aad) documents `AAD imm8` as allowing any multiplier for `AH*imm8 + AL`. In the early days some non-Intel CPUs apparently ignored the immediate for AAM / AAD and used a fixed `10`, and Intel says some assemblers don't support `aad 42` source syntax. But the problem is that it's non-widening, `AX= (AH*imm8+AL) & 0xFF` i.e. producing an 8-bit result in AL and zero-extending. Even a widening 8x8 => 16-bit multiply would need 2 multiplies and an add to do BX * 42 (low and high halves), plus mov and/or xchg – Peter Cordes Nov 13 '22 at 23:26