When and why do we sign extend and use cdq with mul/div?
Solution 1:
Use cdq
/ idiv
for signed 32-bit / 32-bit => 32 bit division,xor edx,edx
/ div
for unsigned.
With the dividend in EAX to start with, and the divisor specified as an operand to DIV or IDIV.
mov eax, 1234
mov ecx, 17
cdq ; EDX = signbit(EAX)
idiv ecx ; EAX = 1234/17 EDX = 1234%17
If you zero EDX/RDX instead of sign-extending into EDX:EAX before idiv
, you can get a large positive result for -5 / 2, for example.
Using the "full power" of 64 / 32-bit => 32-bit division is possible, but not safe unless you know the divisor is large enough so the quotient doesn't overflow. (i.e. you can't in general implement (a*b) / c
with just mul
/ div
and a 64-bit temporary in EDX:EAX.)
Division raises an exception (#DE) on overflow of the quotient. On Unix/Linux, the kernel delivers SIGFPE for arithmetic exceptions including divide errors. With normal sign or zero-extended divide, overflow is only possible with idiv
of INT_MIN / -1
(i.e. the 2's complement special case of the most negative number.)
As you can see from the insn ref manual (link in the x86 tag wiki):
- one-operand
mul
/imul
:edx:eax = eax * src
- two-operand
imul
:dst *= src
. e.g.imul ecx, esi
doesn't read or write eax or edx.
-
div
/idiv
: dividesedx:eax
by the src. quotient ineax
, remainder inedx
. There's no form ofdiv
/idiv
that ignoresedx
in the input. -
cdq
sign-extendseax
intoedx:eax
, i.e. broadcasts the sign bit ofeax
into every bit ofedx
. Not to be confused withcdqe
, the 64-bit instruction that is a more compact form ofmovsxd rax, eax
.Originally (8086), there was just
cbw
(ax = sign_extend(al)
) andcwd
(dx:ax = sign_extend(ax)
). The extensions of x86 to 32bit and 64bit have made the mnemonics slightly ambiguous (but remember, other thancbw
, the within-eax versions always end with ane
for Extend). There is no dl=sign_bit(al) instruction because 8bit mul and div are special, and useax
instead ofdl:al
.
Since the inputs to [i]mul
are single registers, you never need to do anything with edx
before a multiply.
If your input is signed, you sign-extend it to fill the register you're using as an input to the multiply e.g. with movsx
or cwde
(eax = sign_extend(ax)
). If your input is unsigned, you zero extend. (With the exception that if you only need the low 16 bits of the multiply result, for example, it doesn't matter if the upper 16 bits of either or both inputs contain garbage.)
For a divide, you always need to zero or sign extend eax into edx. Zero-extending is the same as just unconditionally zeroing edx, so there's no special instruction for it. Just xor edx,edx
.
cdq
exists because it's a lot shorter than mov edx, eax
/ sar edx, 31
to broadcast the sign bit of eax to every bit in edx. Also, shifts with immediate count > 1 didn't exist until 186 and were still 1 cycle per count, so on 8086 you'd have to do something even worse (like branch, or rotate the sign bit to the bottom and isolate + neg
it). So cwd
in 8086 saved a lot of time/space when it was needed.
In 64bit mode, sign and zero extending 32bit values to 64bit is common. The ABI allows garbage in the high 32bits of a 64bit register holding a 32bit value, so if your function is only supposed to look at the low 32bits of edi
, you can't just use [array + rdi]
to index the array.
So you see a lot of movsx rdi, edi
(sign extend), or mov eax, edi
(zero-extend, and yes it's more efficient to use a different target register, because Intel mov-elimination doesn't work with mov same,same
)