Continue to Site

# ASM01 – Fast AVR Code for Dividing 16-Bit Register by 8-Bit Register (0 to 255) with Rounding

Status
Not open for further replies.

#### KerimF

I hope the comments of the code below are clear.

Kerim

Code:
;======================================================
; Division of 16-bit register {A} by 8-bit register {N}
;======================================================

; {R}={A}/{N} = r17:r16 / {N} = r17:r16 * {Kd} /256 /256 then rounding

; {A} dividend in r17:r16 [0 to 65535]
; {N} constant divisor in r22 [N=0 to 255], see Note_1, Note_2 below
; {R} result in r21:r20 , {A}/{N} rounded
; {Kd} = round(256*256/{N},0), the division constant [from KdTable:]
; {Kr} = INT[ (1-{N})/2 ]    , the rounding constant
; Used registers: ZH,ZL,r19,r18,r14,r13,r1,r0
; 49, 59 or 60 cycles = 42c|52c|53c code + 4c RET + 3c RCALL

D16var8:
TST   r22                   ;1abc
BREQ  DOoverF               ;1abc

CPI   r22, 1                ;1abc
BREQ  DO_same               ;1abc

LDI   ZH, high(KdTable)     ;1abc, address in words, 0x??00
MOV   ZL, r22               ;1abc
LSL   ZL                    ;1abc
ROL   ZH                    ;1abc
LPM   r13, Z+               ;3abc
LPM   r14, Z                ;3abc, 14abc
; r14:r13 = reg_Kd

; multiplicand in r17:r16 = {A}
; multiplier   in r14:r13 = {Kd}
; mul. result  in r21:r20:r19:r18
; valid result in r21:r20
MUL   r17, r14              ;2abc
MOVW  r21:r20, r1:r0        ;1abc
MUL   r16, r13              ;2abc
MOVW  r19:r18, r1:r0        ;1abc
MUL   r17, r13              ;2abc
CLR   r13                   ;1abc
MUL   r14, r16              ;2abc
ADC   r21, r13              ;1abc +17abc= 31abc
; {B} = r21:r20 = r17:r16 * r14:r13 /256/256 = {A}*{Kd}/256/256
; {R} = {B} or {B}+1

; for rounding
MOV   r13, r22              ;1abc
; r13 = {N}

MUL   r20, r13              ;2abc
MOVW  r19:r18, r1:r0        ;1abc
MUL   r21, r13              ;2abc
ADD   r19, r0               ;1abc, +7abc= 38abc
; {C} = r19:r18 = {B}*{N} = r21:r20 * r13

; the following conditions were deduced empirically
; if( Carry_1=0, {R}={B}, if({D2}>0, {R}={B}, {R}={B}+1 ) )

SUB   r18, r16              ;1abc
SBC   r19, r17              ;1abc
; {D1} = r19:r18 = {C} - {A} = r19:r18 - r17:r16

BRCC  DIV_ret               ;2a|1bc +4a=[42a]
; if Carry_1=0, {R}={B}

DEC   r13                   ;1bc
LSR   r13                   ;1bc
; r13 = - reg_Kr

CLR   r13                   ;1bc
; {D2} = r19:r18 = {D1} + {-Kr} = r19:r18 + {-Kr}

BRPL  DIV_ret               ;2b|1c, +10b=[52b]
; if {D2} positive, {R}={B}

SUBI  r20,  low(-1)         ;1c
SBCI  r21, high(-1)         ;1c, +11c=[53c]
; {R}={B}+1

DIV_ret:
RET                         ;4
; {R} = r21:r20 = {B} or {B}+1 [ {A}/{N} rounded ]

DOoverF:
SER   r20
SER   r21
RET
; {R} = r21:r20 = 0xFFFF

DO_same:
MOV   r20, r16
MOV   r21, r17
RET

;====================================

.org 0x??00

KdTable:
.dw   0,0,32768,21845,16384,13107,10923,9362
.dw   8192,7282,6554,5958,5461,5041,4681,4369
.dw   4096,3855,3641,3449,3277,3121,2979,2849
.dw   2731,2621,2521,2427,2341,2260,2185,2114
.dw   2048,1986,1928,1872,1820,1771,1725,1680
.dw   1638,1598,1560,1524,1489,1456,1425,1394
.dw   1365,1337,1311,1285,1260,1237,1214,1192
.dw   1170,1150,1130,1111,1092,1074,1057,1040
.dw   1024,1008,993,978,964,950,936,923
.dw   910,898,886,874,862,851,840,830
.dw   819,809,799,790,780,771,762,753
.dw   745,736,728,720,712,705,697,690
.dw   683,676,669,662,655,649,643,636
.dw   630,624,618,612,607,601,596,590
.dw   585,580,575,570,565,560,555,551
.dw   546,542,537,533,529,524,520,516
.dw   512,508,504,500,496,493,489,485
.dw   482,478,475,471,468,465,462,458
.dw   455,452,449,446,443,440,437,434
.dw   431,428,426,423,420,417,415,412
.dw   410,407,405,402,400,397,395,392
.dw   390,388,386,383,381,379,377,374
.dw   372,370,368,366,364,362,360,358
.dw   356,354,352,350,349,347,345,343
.dw   341,340,338,336,334,333,331,329
.dw   328,326,324,323,321,320,318,317
.dw   315,314,312,311,309,308,306,305
.dw   303,302,301,299,298,297,295,294
.dw   293,291,290,289,287,286,285,284
.dw   282,281,280,279,278,277,275,274
.dw   273,272,271,270,269,267,266,265
.dw   264,263,262,261,260,259,258,257

/*
Note_1:
If N=0, the returned result [r21:r20] is 65535 [the highest possible number for it]. But this could be replaced by setting an overflow flag for example.

Note_2:
In case reg_N [r22] won’t be 0 or 1 for sure, testing r22 at the beginning of the code could be removed, also the code of DOoverF: and DO_same:
*

Hi,

I see no question.
Why did you post the code?

Klaus

Hi,

I see no question.
Why did you post the code?

Klaus
Hi,

Sorry, I just liked sharing this code with others.

For instance, would you please help me know where I had to post something which could be new and useful to some others without having a question? Thank you.

By the way, I wonder if you heard already of this fast division (or the like). I was told it is new, but this may not be so to all programmers.

Kerim

Status
Not open for further replies.