16-Bit Division
Now that we've seen 8-bit division, extending to 16-bit is quite simple. Again, we will take a look at the division routines offered by Atmel in the AVR200 Application Note.
16-Bit Unsigned Division
Atmel's 16-bit unsigned division subroutine is shown below
;***************************************************************************
;*
;* "div16u" - 16/16 Bit Unsigned Division
;*
;* This subroutine divides the two 16-bit numbers
;* "dd8uH:dd8uL" (dividend) and "dv16uH:dv16uL" (divisor).
;* The result is placed in "dres16uH:dres16uL" and the remainder in
;* "drem16uH:drem16uL".
;*
;* Number of words :19
;* Number of cycles :235/251 (Min/Max)
;* Low registers used :2 (drem16uL,drem16uH)
;* High registers used :5 (dres16uL/dd16uL,dres16uH/dd16uH,dv16uL,dv16uH,
;* dcnt16u)
;*
;***************************************************************************
;***** Subroutine Register Variables
.def drem16uL=r14
.def drem16uH=r15
.def dres16uL=r16
.def dres16uH=r17
.def dd16uL =r16
.def dd16uH =r17
.def dv16uL =r18
.def dv16uH =r19
.def dcnt16u =r20
;***** Code
div16u: clr drem16uL ;clear remainder Low byte
sub drem16uH,drem16uH ;clear remainder High byte and carry
ldi dcnt16u,17 ;init loop counter
d16u_1: rol dd16uL ;shift left dividend
rol dd16uH
dec dcnt16u ;decrement counter
brne d16u_2 ;if done
ret ; return
d16u_2: rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_3 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_1 ;else
d16u_3: sec ; set carry to be shifted into result
rjmp d16u_1With this subroutine, the high and low bytes if the dividend are stored in dd16u (r17:r16) and the high and low bytes of the divisor are stored in dv16u (r19:r18). When the subroutine is finished, the high and low byes of the result are stored in dres16u (r17:r16) and the high and low bytes of the remainder are stored in drem16u (r15:r14).
Looking at this line by line you will see that it is not much different than 8-bit division - there are just a few instructions that must be doubled up since we need two registers to hold our values instead of one.
In the first line, the remainder register drem16u is cleared. Since it is 16-bits, this is done in two steps - first by clearing the lower byte with clr and then the higher byte with sub. As we saw before, using sub in this manner clears both the register and the Carry Flag.
div16u: clr drem16uL ;clear remainder Low byte
sub drem16uH,drem16uH ;clear remainder High byte and carryNext, a For Loop is setup to iterate through all 16-bits of the dividend.
ldi dcnt16u,17 ;init loop counter
...
dec dcnt16u ;decrement counter
brne d16u_2 ;if done
ret ; returnThen, we shift a bit out of the dividend into the remainder. Since these are 16-bit values, two rol instructions must be used.
d16u_1: rol dd16uL ;shift left dividend
rol dd16uH
...
d16u_2: rol drem16uL ;shift dividend into remainder
rol drem16uHAs before, we subtract our divisor from the remainder, only this time with two steps using sub and sbc. If the result is negative (carry set), we need to restore the value in the remainder and shift a zero into the result.
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
...
add drem16uL,dv16uL ;restore remainder
adc drem16uH,dv16uH
clc ;clear carry to be shifted into result
↓
rol dd16uL ;shift zero into result
rol dd16uHOtherwise, the divisor goes into the remainder, so we need to shift a one into the result.
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
...
sec ;set carry to be shifted into result
↓
rol dd16uL ;shift one into result
rol dd16uHThis process is repeated until dcnt16u reaches zero at which point the subroutine will return.
Calling this subroutine can be done as follows
ldi r16,LOW(10100) ; load r17:r16
ldi r17,HIGH(10100) ; with 10100
ldi r18,LOW(1000) ; load r19:r18
ldi r19,HIGH(1000) ; with 1000
rcall div16u ; compute 10100/1000The result 10 will be stored in r17:r16 when the subroutine finishes and a remainder of 100 will be stored in r15:r14.
Optimizing For Speed
Once again, we can choose to optimize the above routine for speed rather than code size by using a straight through sequence rather than loops. This (much longer) version is shown below.
;***************************************************************************
;*
;* "div16u" - 16/16 Bit Unsigned Division
;*
;* This subroutine divides the two 16-bit numbers
;* "dd8uH:dd8uL" (dividend) and "dv16uH:dv16uL" (divisor).
;* The result is placed in "dres16uH:dres16uL" and the remainder in
;* "drem16uH:drem16uL".
;*
;* Number of words :196 + return
;* Number of cycles :148/173/196 (Min/Avg/Max)
;* Low registers used :2 (drem16uL,drem16uH)
;* High registers used :4 (dres16uL/dd16uL,dres16uH/dd16uH,dv16uL,dv16uH)
;*
;***************************************************************************
;***** Subroutine Register Variables
.def drem16uL=r14
.def drem16uH=r15
.def dres16uL=r16
.def dres16uH=r17
.def dd16uL =r16
.def dd16uH =r17
.def dv16uL =r18
.def dv16uH =r19
;***** Code
div16u: clr drem16uL ;clear remainder Low byte
sub drem16uH,drem16uH ;clear remainder High byte and carry
rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_1 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_2 ;else
d16u_1: sec ; set carry to be shifted into result
d16u_2: rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_3 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_4 ;else
d16u_3: sec ; set carry to be shifted into result
d16u_4: rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_5 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_6 ;else
d16u_5: sec ; set carry to be shifted into result
d16u_6: rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_7 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_8 ;else
d16u_7: sec ; set carry to be shifted into result
d16u_8: rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_9 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_10 ;else
d16u_9: sec ; set carry to be shifted into result
d16u_10:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_11 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_12 ;else
d16u_11:sec ; set carry to be shifted into result
d16u_12:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_13 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_14 ;else
d16u_13:sec ; set carry to be shifted into result
d16u_14:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_15 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_16 ;else
d16u_15:sec ; set carry to be shifted into result
d16u_16:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_17 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_18 ;else
d16u_17: sec ; set carry to be shifted into result
d16u_18:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_19 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_20 ;else
d16u_19:sec ; set carry to be shifted into result
d16u_20:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_21 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_22 ;else
d16u_21:sec ; set carry to be shifted into result
d16u_22:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_23 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_24 ;else
d16u_23:sec ; set carry to be shifted into result
d16u_24:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_25 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_26 ;else
d16u_25:sec ; set carry to be shifted into result
d16u_26:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_27 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_28 ;else
d16u_27:sec ; set carry to be shifted into result
d16u_28:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_29 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_30 ;else
d16u_29:sec ; set carry to be shifted into result
d16u_30:rol dd16uL ;shift left dividend
rol dd16uH
rol drem16uL ;shift dividend into remainder
rol drem16uH
sub drem16uL,dv16uL ;remainder = remainder - divisor
sbc drem16uH,dv16uH ;
brcc d16u_31 ;if result negative
add drem16uL,dv16uL ; restore remainder
adc drem16uH,dv16uH
clc ; clear carry to be shifted into result
rjmp d16u_32 ;else
d16u_31:sec ; set carry to be shifted into result
d16u_32:rol dd16uL ;shift left dividend
rol dd16uH
retThis subroutine takes a whopping 196 words compared to 19 for the size optimized version. However, it executes in just 173 cycles as opposed to 243. Once again, it is up to you to decide what is best for your application - speed or size.
16-Bit Signed Division
As we saw in the 8-bit example, signed division can be done by converting any negative inputs to their unsigned magnitude and then computing unsigned division. If the dividend or divisor is negative (but not both), the result must be negative so it is converted back to a signed value at the end. Atmel's 16-bit signed division subroutine is shown below.
;***************************************************************************
;*
;* "div16s" - 16/16 Bit Signed Division
;*
;* This subroutine divides signed the two 16 bit numbers
;* "dd16sH:dd16sL" (dividend) and "dv16sH:dv16sL" (divisor).
;* The result is placed in "dres16sH:dres16sL" and the remainder in
;* "drem16sH:drem16sL".
;*
;* Number of words :39
;* Number of cycles :247/263 (Min/Max)
;* Low registers used :3 (d16s,drem16sL,drem16sH)
;* High registers used :7 (dres16sL/dd16sL,dres16sH/dd16sH,dv16sL,dv16sH,
;* dcnt16sH)
;*
;***************************************************************************
;***** Subroutine Register Variables
.def d16s =r13 ;sign register
.def drem16sL=r14 ;remainder low byte
.def drem16sH=r15 ;remainder high byte
.def dres16sL=r16 ;result low byte
.def dres16sH=r17 ;result high byte
.def dd16sL =r16 ;dividend low byte
.def dd16sH =r17 ;dividend high byte
.def dv16sL =r18 ;divisor low byte
.def dv16sH =r19 ;divisor high byte
.def dcnt16s =r20 ;loop counter
;***** Code
div16s: mov d16s,dd16sH ;move dividend High to sign register
eor d16s,dv16sH ;xor divisor High with sign register
sbrs dd16sH,7 ;if MSB in dividend set
rjmp d16s_1
com dd16sH ; change sign of dividend
com dd16sL
subi dd16sL,low(-1)
sbci dd16sL,high(-1)
d16s_1: sbrs dv16sH,7 ;if MSB in divisor set
rjmp d16s_2
com dv16sH ; change sign of divisor
com dv16sL
subi dv16sL,low(-1)
sbci dv16sH,high(-1)
d16s_2: clr drem16sL ;clear remainder Low byte
sub drem16sH,drem16sH ;clear remainder High byte and carry
ldi dcnt16s,17 ;init loop counter
d16s_3: rol dd16sL ;shift left dividend
rol dd16sH
dec dcnt16s ;decrement counter
brne d16s_5 ;if done
sbrs d16s,7 ; if MSB in sign register set
rjmp d16s_4
com dres16sH ; change sign of result
com dres16sL
subi dres16sL,low(-1)
sbci dres16sH,high(-1)
d16s_4: ret ; return
d16s_5: rol drem16sL ;shift dividend into remainder
rol drem16sH
sub drem16sL,dv16sL ;remainder = remainder - divisor
sbc drem16sH,dv16sH ;
brcc d16s_6 ;if result negative
add drem16sL,dv16sL ; restore remainder
adc drem16sH,dv16sH
clc ; clear carry to be shifted into result
rjmp d16s_3 ;else
d16s_6: sec ; set carry to be shifted into result
rjmp d16s_3The main difference between this routine and the 8-bit version is the way in which negative inputs are converted to an unsigned magnitude. Whereas before the neg instruction was used, we must get a little more creative for 16-bit numbers.
The trick is really quite simple - any negative number can be converted from a Two's Complement form to an unsigned magnitude by inverting all of its bits (i.e. changing all zeros to ones and all ones to zeros) and then adding one to the result. A great explanation of why this works can be found here.
This is shown below for the dividend. The instruction com is used to invert the bits of the high and low byte. Since there is no add immediate instruction, subi and sbci are used to do an immediate subtraction of -1 (which is the same as adding 1)
sbrs dd16sH,7 ;if MSB in dividend set
...
com dd16sH ; change sign of dividend
com dd16sL
subi dd16sL,low(-1)
sbci dd16sL,high(-1)The same is done for the divisor
sbrs dv16sH,7 ;if MSB in divisor set
...
com dv16sH ; change sign of divisor
com dv16sL
subi dv16sL,low(-1)
sbci dv16sH,high(-1)And at the end, if the result must be negated
sbrs d16s,7 ; if MSB in sign register set
...
com dres16sH ; change sign of result
com dres16sL
subi dres16sL,low(-1)
sbci dres16sH,high(-1)
Post a Comment