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

[KerimF]

I hope the comments of the code below are clear.

Kerim

;======================================================
; 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
; *2 [from word address to byte address]
    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
    ADD   r19, r0               ;1abc
    ADC   r20, r1               ;1abc
    ADC   r21, r13              ;1abc
    MUL   r14, r16              ;2abc
    ADD   r19, r0               ;1abc
    ADC   r20, r1               ;1abc
    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

    ADD   r18,  r13             ;1bc
    CLR   r13                   ;1bc
    ADC   r19,  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:
*

 

[KlausST]

Hi,

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

Klaus

 

[KerimF]

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