logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Procedura dzielenia w asemblerze na AVR

marekdz 23 Mar 2009 12:13 4588 16
REKLAMA
  • #1 6320460
    marekdz
    Poziom 11  
    Witam.

    Czy ktoś z kolegów natknął się na procedury dzielenia dla AVR.
    Konkretnie chodzi mi o dzielenie liczby 24bit przez 16bit lub 32bit przez 16bit
    wynik liczba całkowita może być bez reszty no i warunek procedura nie może przekraczać 450cykli.

    Serdeczne dzięki za pomoc.
    Pozdrawiam
    Marek D.
  • REKLAMA
  • #2 6320527
    Freddie Chopin
    Specjalista - Mikrokontrolery
    marekdz napisał:
    procedura nie może przekraczać 450cykli

    Dostępne w avr-libc (avr-gcc) funkcje zajmują około 330 cykli (16/16=16) lub 730 cykli (32/16=16). Poniżej tego nie zejdziesz, nie widzę też sensu pisania własnych bibliotek, skoro można zastosować te gotowe.

    4\/3!!
  • #3 6320566
    marekdz
    Poziom 11  
    Witam.
    Posiadam w swoich zbiorach procedurę 32/16 i ta zajmuje 680 cykli.
    Znalazłem procedurę na PIC 24/16 podają iż zajmuje do 350cykli a 32/16 do 470cykli. A te procesory są głupsze od AVR.

    Pozdrawiam.
    Marek D.
  • #4 6321212
    Dr.Vee
    VIP Zasłużony dla elektroda
    Notę aplikacyjną AVR200 czytałeś?
    Tam są procedury 16/16 unsigned działające w 253/176 cyklach - implementacja mała/szybka.

    Dodanie kolejnych 8 bitów nie powinno zwiększyć czasu wykonania o więcej niż 50% :)

    Pozdrawiam,
    Dr.Vee
  • REKLAMA
  • #5 6321240
    marekdz
    Poziom 11  
    Czytałem.

    Ale nie mam pojęcia jak to rozszerzyć.
  • Pomocny post
    #6 6321873
    Dr.Vee
    VIP Zasłużony dla elektroda
    Mam dzisiaj chyba dzień dobroci...

    Tu masz procedurę dzielenia, przerobioną z noty AVR200. Wykona się +/- o 50% dłużej niż oryginalny kod 16/16 unsigned - jest 8 przebiegów pętli więcej i jedna instrukcja więcej w pętli, ale zoptymalizowałem jednego brancha więc cykli w przebiegu pętli wyjdzie tyle samo.

    Z tego wynika, że wszystko powinno zająć max 376 cykli.

    Oczywiście kod nie testowany itp itd.
    ;***************************************************************************
    ;*
    ;* "div24u" - 24/16 Bit Unsigned Division
    ;*
    ;* This subroutine divides the 24 by 16 bit numbers
    ;* "ddH:ddM:ddL" (dividend) and "dvH:dvL" (divisor). 
    ;* The result is placed in "resH:resM:resL" and the remainder in
    ;* "remH:remL".
    ;*  
    ;* Number of words      :??
    ;* Number of cycles     :??/?? (Min/Max)
    ;*
    ;***************************************************************************
    
    ;***** Subroutine Register Variables
    
    .def    remL=r14
    .def    remH=r15
    .def    resL=r16
    .def    resM=r17
    .def    resH=r18
    .def    ddL=r16
    .def    ddM=r17
    .def    ddH=r18
    .def    dvL=r19
    .def    dvH=r20
    .def    cnt=r21
    
    ;***** Code
    
    div24u: clr     remL            ;clear remainder Low byte
            sub     remH,remH       ;clear remainder High byte and carry
            ldi     cnt,25          ;init loop counter
    loop:   rol     ddL             ;shift left dividend
            rol     ddM
            rol     ddH
            dec     cnt             ;decrement counter
            breq    done            ;if done - return
            rol     remL            ;shift dividend into remainder
            rol     remH
            sub     remL,dvL        ;remainder = remainder - divisor
            sbc     remH,dvH        ;
            brcc    norest          ;if result negative
            add     remL,dvL        ;    restore remainder
            adc     remH,dvH
            clc                     ;    clear carry to be shifted into result
            rjmp    loop            ;else
    norest: sec                     ;    set carry to be shifted into result
            rjmp    loop
    done:   ret
    

    Pozdrawiam,
    Dr.Vee
  • REKLAMA
  • Pomocny post
    #7 6324279
    Jerzy_W
    Poziom 14  
    Witam!

    Kiedyś udało mi się "przyspieszyc" orginalne procedury dzielenia z noty AVR200.
    Oto to samo dzielenie 24/16 bitów troszkę szybciej:

    
    ;*************************************************************************** 
    ;* 
    ;* "div24u" - 24/16 Bit Unsigned Division 
    ;* 
    ;* This subroutine divides the 24 by 16 bit numbers 
    ;* "ddH:ddM:ddL" (dividend) and "dvH:dvL" (divisor). 
    ;* The result is placed in "resH:resM:resL" and the remainder in 
    ;* "remH:remL". 
    ;*  
    ;* Number of words      :?? 
    ;* Number of cycles     :283/355 (Min/Max) poprz. 352/376 
    ;* 
    ;*************************************************************************** 
    
    ;***** Subroutine Register Variables 
    
    .def    remL=r14 
    .def    remH=r15 
    .def    resL=r16 
    .def    resM=r17 
    .def    resH=r18 
    .def    ddL=r16 
    .def    ddM=r17 
    .def    ddH=r18 
    .def    dvL=r19 
    .def    dvH=r20 
    .def    cnt=r21 
    
    ;***** Code 
    
    div24u: clr     remL            ;clear remainder Low byte 
            sub     remH,remH       ;clear remainder High byte and carry 
            ldi     cnt,25          ;init loop counter 
    loop:   rol     ddL             ;shift left dividend 
            rol     ddM 
            rol     ddH 
            dec     cnt             ;decrement counter 
            breq    done            ;if done - return 
            rol     remL            ;shift dividend into remainder 
            rol     remH 
            sub     remL,dvL        ;remainder = remainder - divisor 
            sbc     remH,dvH        ; 
            brcc    loop          ;if result negative 
            add     remL,dvL        ;    restore remainder 
            adc     remH,dvH 
            rjmp    loop 
    done:   com	ddL
            com	ddM
            com	ddH
            ret
    


    pozdrawiam!
  • #8 6324384
    Dr.Vee
    VIP Zasłużony dla elektroda
    Faktycznie, dobry pomysł z komplementacją na końcu. Zastanawiałem się nad pierwszą rotacją (carry jest zawsze wyzerowane przed wejściem do pętli), ale rotacji jest 25 a bitów tylko 24, więc ten pierwszy bit i tak zostanie wysunięty z ilorazu przed zakończeniem funkcji.

    Dobra robota :)

    Pozdrawiam,
    Dr.Vee
  • #9 6324531
    marekdz
    Poziom 11  
    Witam.
    Serdeczne dzięki Panowie.

    Pozdrawiam
    Marek D.
  • #10 6339508
    marekdz
    Poziom 11  
    Witam.

    Sprawdziłem i niestety. Puki dzieli 16bit to jest ok. jak zaczyna dzielić 24bit. to są błędy.

    Pozdrawiam
    Marek D.
  • REKLAMA
  • Pomocny post
    #11 6339837
    Dar.El
    Poziom 41  
    Witam
    Moja przeróbka. Dzielenie 3B na 2B. Działa na pewno.

    ;dzielenie 3B/2B
    ;dzielna w r18,19,20
    ;dzielnik r16,r17
    ;wynik w r18,r19 i r20
    ;reszta w r12,13,14
    DIV32:
    		clr r15
    div16u:	clr	r12				;clear remainder Low byte
    		clr r13				;midle
    		sub	r14,r14			;clear remainder High byte and carry
    		ldi	r21,25			;init loop counter
    d16u_1:	rol	r18				;shift left dividend
    		rol	r19
    		rol r20
    
    		dec	r21				;decrement counter
    		brne d16u_2			;if done
    		ret					;return
    d16u_2:	rol	r12				;shift dividend into remainder
    		rol r13
    		rol	r14
    		sub	r12,r16			;remainder = remainder - divisor
    		sbc r13,r17
    		sbc	r14,r15			;
    		brcc d16u_3			;if result negative
    		add	r12,r16			;restore remainder
    		adc r13,r17
    		adc	r14,r15
    		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
  • #12 6340961
    Dr.Vee
    VIP Zasłużony dla elektroda
    Dar.El, tak szczerze to się zastanawiałem co Twoja modyfikacja wnosi... Rozszerzyłeś rejestr reszty z 16 do 24 bitów, ale reszta nie może być większa niż dzielnik.

    Aha! Jeśli dzielna ma więcej bitów niż dzielnik, to rejestr reszty może się przepełnić i porównanie da wtedy błędny wynik - tego nie uwzględniała moja modyfikacja ;)

    Jeśli wysunięty bit z reszty (carry) jest ustawiony, to na pewno reszta jest większa od dzielnika, więc trzeba wykonać odejmowanie:
    ;***************************************************************************
    ;*
    ;* "div24u" - 24/16 Bit Unsigned Division
    ;*
    ;* This subroutine divides the 24 by 16 bit numbers
    ;* "ddH:ddM:ddL" (dividend) and "dvH:dvL" (divisor).
    ;* The result is placed in "resH:resM:resL" and the remainder in
    ;* "remH:remL".
    ;* 
    ;* Number of words      :25
    ;* Number of cycles     :299/379 (Min/Max)
    ;*
    ;*************************************************************************** ;***** Subroutine Register Variables
    
    .def    remL=r14
    .def    remH=r15
    .def    resL=r16
    .def    resM=r17
    .def    resH=r18
    .def    ddL=r16
    .def    ddM=r17
    .def    ddH=r18
    .def    dvL=r19
    .def    dvH=r20
    .def    cnt=r21
    
    ;***** Code
    
    div24u: clr     remL            ;clear remainder Low byte
            sub     remH,remH       ;clear remainder High byte and carry
            ldi     cnt,25          ;init loop counter
    loop:   rol     ddL             ;shift left dividend
            rol     ddM
            rol     ddH
            dec     cnt             ;decrement counter
            breq    done            ;if done - return
            rol     remL            ;shift dividend into remainder
            rol     remH
            jc      overfl          ;check if we overflow the remainder
            cp      remL,dvL        ;check if remainder > divisor
            cpc     remH,dvH        ;
            brcs    loop            ;if remainder > divisor
            sub     remL,dvL        ;     remainder = remainder - divisor
            subc    remH,dvH        ; 
            rjmp    loop            ; here C=0
    overfl: sub     remL,dvL
            subc    remH,dvH        ; here C=1
            clc                     ; here C=0
            rjmp    loop
    done:   com   ddL
            com   ddM
            com   ddH
            ret


    Pozdrawiam,
    Dr.Vee
  • #13 6341125
    Dar.El
    Poziom 41  
    Nie rozszerzyłem tylko zwęziłem z 3B/3B na 3B/2B, bo tyle było mi potrzebne.
  • #14 6342238
    Jerzy_W
    Poziom 14  
    Cytat:
    Sprawdziłem i niestety. Puki dzieli 16bit to jest ok. jak zaczyna dzielić 24bit. to są błędy.


    :?:
    Napisałem tę procedurę dosyć dawno i już nie wiem w ilu ATMEGACH to pracuje.

    Na szybko napisałem programik do symulacji/testowania w AVR Studio.

    
    ;sprawdzanie procedury dzielenia 24/16
    	.include	"m162def.inc"
    
    	.equ	Dzielna=0xFFFFFF
    	.equ	Dzielnik=1
    
    	.org	0
    	ldi	R16,LOW(RAMEND)
    	out	SPL,R16
    	ldi	R16,HIGH(RAMEND)
    	out	SPH,R16
    	ldi	dzielna_B2,((Dzielna>>16) & 0xFF)
    	ldi	dzielna_B1,((Dzielna>>8) & 0xFF)
    	ldi	dzielna_B0,(Dzielna & 0xFF)
    	ldi	dzielnik_B1,((Dzielnik >> 8) & 0xFF)
    	ldi	dzielnik_B0,(Dzielnik & 0xFF)
    	rcall	div24U
    STOP:	rjmp	STOP
    
    .def    Reszta_B0=r14 
    .def    Reszta_B1=r15 
    ;.def    iloraz_B0=r16 - patrz dzielna 
    ;.def    iloraz_B1=r17 
    ;.def    iloraz_B2=r18 
    .def    Dzielna_B0=r16 
    .def    Dzielna_B1=r17 
    .def    Dzielna_B2=r18 
    .def    dzielnik_B0=r19 
    .def    dzielnik_B1=r20 
    .def    licznikP=r21 
    
    div24u: clr     reszta_B0            
            sub     reszta_B1,reszta_B1  
            ldi     LicznikP,25          
    loop:   rol     dzielna_B0
            rol     dzielna_B1 
            rol     dzielna_B2 
            dec     LicznikP
            breq    return
            rol     reszta_B0
            rol     reszta_B1 
            sub     reszta_B0,dzielnik_B0
            sbc     reszta_B1,dzielnik_B1
            brcc    loop
            add     reszta_B0,dzielnik_B0
            adc     reszta_B1,dzielnik_B1
            rjmp    loop 
    return: com	dzielna_B0
            com	dzielna_B1
            com	dzielna_B2
            ret
    


    Przetestowałem dla różnych wartości i na razie wygląda, że to działa.
    Czy możecie mi podać wartości dzielnej i dzielnika przy których jest błąd?

    P.S. Dzielenie przez zero iloraz=0xFFFFFF a reszta to dwa młodsze bajty dzielnej.
    0XFFFFFF to maksymalna warość liczby 3-bajtowej bez znaku - coś jak +niekończonośc- też sensowny wynik


    pozdrawiam
  • #15 6351977
    marekdz
    Poziom 11  
    Witam.
    Już przy tych wartościach jest błąd w dzieleniu
    Stała dzielna i zmieniający się dzielnik

    ldi dzielna_B2,((Dzielna>>16) & 0x69)
    ldi dzielna_B1,((Dzielna>>8) & 0x78)
    ldi dzielna_B0,(Dzielna & 0x00)
    ldi dzielnik_B1,((Dzielnik >> 8) & 0x8D)
    ldi dzielnik_B0,(Dzielnik & 0x00)

    otrzymany wynik z procedury to $85 a rzeczywisty $BF

    Pozdrawiam
    Marek D.
  • #16 6353270
    Jerzy_W
    Poziom 14  
    :cry:
    OOOPS!!!
    Na szczęście używałem tych procedur w wersji 16/16 i 32/32
    Widocznie nie da się tego algorytmu używać w wersji z 24/16 (nierówny wymiar dzielnej i dzielnika).

    Poniżej załączam programik do testowania dzielenia 3-bajtowego:

    
    
    ;sprawdzanie procedury dzielenia 24/24 
       .include   "m162def.inc" 
    
       .equ   Dzielna=0x697800
       .equ   Dzielnik=0x008D00
    
       .org   0 
       ldi   R16,LOW(RAMEND) 
       out   SPL,R16 
       ldi   R16,HIGH(RAMEND) 
       out   SPH,R16 
       ldi   dzielna_B2,((Dzielna>>16) & 0xFF) 
       ldi   dzielna_B1,((Dzielna>>8) & 0xFF) 
       ldi   dzielna_B0,(Dzielna & 0xFF)
       ldi   dzielnik_B2,((Dzielnik>>16) & 0xFF) 
       ldi   dzielnik_B1,((Dzielnik >> 8) & 0xFF) 
       ldi   dzielnik_B0,(Dzielnik & 0xFF)
       rcall   div24u 
    STOP:   rjmp   STOP 
    
    ;***** Subroutine Register Variables
    
    .def	Reszta_B0=r13
    .def	Reszta_B1=r14
    .def	Reszta_B2=r15
    .def	dres16uL=r16
    .def	dres16uH=r17
    .def	Dzielna_B0	=r16
    .def	Dzielna_B1	=r17
    .def	Dzielna_B2	=r18
    .def	Dzielnik_B0	=r19
    .def	Dzielnik_B1	=r20
    .def	Dzielnik_B2	=r21
    .def	dcnt16u		=r22
    
    ;***** Code
    
    div24u:	clr	Reszta_B0	;clear remainder Low byte
    	clr	Reszta_B1
    	sub	Reszta_B2,Reszta_B2;clear remainder High byte and carry
    	ldi	dcnt16u,25	;init loop counter
    d24u_1:	rol	Dzielna_B0		;shift left dividend
    	rol	Dzielna_B1
    	rol	Dzielna_B2
    	dec	dcnt16u		;decrement counter
    	brne	d24u_2		;if done
    	com	Dzielna_B0
    	com	Dzielna_B1
    	com	Dzielna_B2	
    	ret			;    return
    d24u_2:	rol	Reszta_B0	;shift dividend into remainder
    	rol	Reszta_B1
    	rol	Reszta_b2
    	sub	Reszta_B0,Dzielnik_B0	;remainder = remainder - divisor
    	sbc	Reszta_B1,Dzielnik_B1	;
    	sbc	Reszta_B2,Dzielnik_B2
    	brcc	d24u_1	
    	add	Reszta_B0,Dzielnik_B0	;    restore remainder
    	adc	Reszta_B1,Dzielnik_B1
    	adc	Reszta_B2,Dzielnik_B2
    	rjmp	d24u_1
    


    Aby ustawić dzielną lub dzielnik wpisz je tylko w tych liniach
    
    
       .equ   Dzielna=0x697800
       .equ   Dzielnik=0x008D00
    


    w liniach poniżej asembler wyłuskuje bajty dzielnej i dzielnika i wpisuje je do odpowiednich rejestrów. Nic tu zmieniać nie trzeba:
    
       ldi   dzielna_B2,((Dzielna>>16) & 0xFF) 
       ldi   dzielna_B1,((Dzielna>>8) & 0xFF) 
       ldi   dzielna_B0,(Dzielna & 0xFF)
       ldi   dzielnik_B2,((Dzielnik>>16) & 0xFF) 
       ldi   dzielnik_B1,((Dzielnik >> 8) & 0xFF) 
       ldi   dzielnik_B0,(Dzielnik & 0xFF)
    


    pozdrawiam
  • #17 6353342
    marekdz
    Poziom 11  
    Witam.

    Serdeczne dzięki kolegom za pomoc. Procedurki są świetne. Chyba wykorzystam procedurę kolegi Dr.Vee jest najszybsza i mogę jeszcze coś upakować.

    Pozdrawiam.
    Marek D.
REKLAMA