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_1

With 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 carry

Next, 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				;    return

Then, 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	drem16uH

As 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	dd16uH

Otherwise, 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	dd16uH

This 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/1000

The 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
	ret

This 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_3

The 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)

<< Prev

Next >>