Integer division¶
You’ve seen add, which takes the two operands to be added together
and puts the sum back into one of them (the first operand, also known as
the destination operand). You can use sub exactly the same way,
to subtract. However, multiplication and division are a little different.
When you add two \(n\) bit numbers, the result in general is an \(n + 1\) bit number. The answer can overflow, but if it does it’s still only by 1 bit being carried out with nowhere to go (there are ways to detect this situation and deal with it). However, when you multiply two \(n\) bit numbers, the result in general is a \(2\cdot n\) bit number—exactly twice as wide. So on the one hand, there’s no pesky odd bit out; we like powers of 2. But on the other hand, with addition we only need to remember whether there was overflow or not, while with multiplication, we need a whole other number to remember all that extra information.
The solution taken in this architecture is to put two registers
together so everything fits. The conjoined register is described
using a colon, i.e. rdx:rax is a 128-bit register where the
top (more significant) bits are from rdx and the bottom (less
significant) bits are from rax. To multiply, you first put one
of your multiplicands into rax, then you use the mul
instruction with (only) the other multiplicand and the answer gets put
into rdx:rax.
Division goes the other way. You put values into rdx and
rax first, so that rdx:rax is the dividend (unless
your dividend is huge, you probably just put it in rax and
set rdx to 0 with e.g. mov rdx, 0). Then you use
the div instruction with the divisor as its only explicit
operand. The quotient goes back into rax. Since we’re talking
about integer division, there will also be a remainder, which goes into
rdx. Sometimes you just want one or the other, and sometimes
you want both, but div always leaves the quotient in rax
and the remainder in rdx for you.
The example program for integer division shows this in practice. A lot of
the same features appear as in the integer division program, but it sets up
and uses div.
.intel_syntax noprefix
.text
.global main
main: push rbp
mov rbp, rsp
# put the dividend into rdx:rax
# (it must be rdx:rax since div uses those implicitly)
mov rdx, 0 # the top 64 bits should be 0
mov rax, [rip + b] # the bottom 64 bits come from the 'b' variable
# put the divisor into rcx from the 'a' register
# (I chose rcx, but it could be another register)
mov rcx, [rip + a]
# compute rdx:rax (implied) divided by rcx (the given operand)
div rcx
mov [rip + quotient], rax # div leaves the quotient in rax
mov [rip + remainder], rdx # div leaves the remainder in rdx
mov rax, 0
pop rbp
ret
# 'input' in initialized data segment
# you can change the inputs by hardcoding their values here
.data
a: .quad 123 # divisor
b: .quad 456 # dividend
# 'output' in uninitialized data segment
.bss
quotient:
.zero 8 # space for computed quotient to be saved into
remainder:
.zero 8 # space for computed remainder to be saved into
You can double-check that your variables exist and are in the right
places using objdump. The -t (‘table’) option
tells objdump to dump the symbol table, but that can be quite
long, so I typically combine it with the -j SECTION option,
e.g. -j .data, to only look at the symbols in a particular
section. In this program, the ‘input’ variables a and
b should be in the .data section, and the ‘output’
variables quotient and remainder should be in the
.bss section.
$ objdump -t -j .data divints
divints: file format elf64-x86-64
SYMBOL TABLE:
0000000000004000 l d .data 0000000000000000 .data
0000000000004018 l .data 0000000000000000 b
0000000000004010 l .data 0000000000000000 a
0000000000004000 w .data 0000000000000000 data_start
0000000000004020 g .data 0000000000000000 _edata
0000000000004000 g .data 0000000000000000 __data_start
0000000000004008 g O .data 0000000000000000 .hidden __dso_handle
0000000000004020 g O .data 0000000000000000 .hidden __TMC_END__
$ objdump -t -j .bss divints
divints: file format elf64-x86-64
SYMBOL TABLE:
0000000000004020 l d .bss 0000000000000000 .bss
0000000000004020 l O .bss 0000000000000001 completed.8061
0000000000004021 l .bss 0000000000000000 quotient
0000000000004029 l .bss 0000000000000000 remainder
0000000000004038 g .bss 0000000000000000 _end
0000000000004020 g .bss 0000000000000000 __bss_start
Everything seems to be in order on that front. The following screencast shows a gdb session that walks through this program step by step, looking at the memory locations and the registers to make sure everything seems right. We should see that \(456 / 123\) is 3 with a remainder of 87 (since \(123\cdot 3 + 87 = 456\)).
