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

[asm] zagadka z algorytmem mnożenia bitów

darkonel 11 Sty 2011 20:28 1712 2
REKLAMA
  • #1 8992322
    darkonel
    Poziom 19  
    Witam. Przeszukuję sieć w celu znalezienia skutecznego algorytmu mnożenia 16 bitów (16x16) z wynikiem 32 bitowym. Oto przykład z sieci (jakich wiele):
    
    mpy16u:
       clr   m16u3      ;clear 2 highest bytes of result
       clr   m16u2
       ldi   mcnt16u,16   ;init loop counter
       lsr   mp16uH
       ror   mp16uL
    m16u_1:
       brcc   noad8      ;if bit 0 of multiplier set
       add   m16u2,mc16uL   ;add multiplicand Low to byte 2 of res
       adc   m16u3,mc16uH   ;add multiplicand high to byte 3 of res
    noad8:   
       ror   m16u3      ;shift right result byte 3
       ror   m16u2      ;rotate right result byte 2
       ror   m16u1      ;rotate result byte 1 and multiplier High
       ror   m16u0      ;rotate result byte 0 and multiplier Low
       dec   mcnt16u      ;decrement loop counter
       brne   m16u_1      ;if not done, loop more     
        ret 
    

    Takich przykładów jest w sieci mnóstwo, ale o dziwo u mnie nie działają (zawsze wynik zerowy). Nawet dokument AVR200 Figure4-1 zawiera wg mnie błędny algorytm (z resztą zgodny z powyższym kodem). To o dziwo nie działa.

    Analizując temat doszedłem do wniosku, iż powrót jest w niewłaściwe miejsce, ponieważ jest to skok do , gdzie sprawdzana jest flaga C, ale skąd ta flaga? Wydaje mi się, że przed sprawdzeniem flagi C trzeba ją "wysunąć", a wg kodu (ostatni rozkaz przed sprawdzeniem C) wysuwane jest cały czas zero (przeanalizujcie kod a się przekonacie).
    Wpadłem na pomysł że wystarczy przenieść etykietę "m16u_1:" o dwie pozycje w górę w kodzie, wówczas flaga C będzie wysuwana zgodnie z zasadami mnożenia binarnego. No i tak zrobiłem:
    
    mpy16u:
       clr   m16u3      ;clear 2 highest bytes of result
       clr   m16u2
       ldi   mcnt16u,16   ;init loop counter
    m16u_1:
       lsr   mp16uH
       ror   mp16uL
       brcc   noad8      ;if bit 0 of multiplier set
       add   m16u2,mc16uL   ;add multiplicand Low to byte 2 of res
       adc   m16u3,mc16uH   ;add multiplicand high to byte 3 of res
    noad8:   
       ror   m16u3      ;shift right result byte 3
       ror   m16u2      ;rotate right result byte 2
       ror   m16u1      ;rotate result byte 1 and multiplier High
       ror   m16u0      ;rotate result byte 0 and multiplier Low
       dec   mcnt16u      ;decrement loop counter
       brne   m16u_1      ;if not done, loop more     
        ret 
    

    Teraz procedurka działa jak należy (sprawdziłem na wszelkie sposoby). No i mam nie lada zagadkę - czyżby w sieci krążyła błędna procedura (no i brak właściwej)?, czy jej nikt nie testował?, czy dokument Atmela także "kłamie"? Spotkał się juz ktoś z takim przypadkiem?
  • REKLAMA
  • #2 8993656
    asembler
    Poziom 32  
    Prawdopodobnie (bo jest późno) oryginalna proceura bedzie działać pod warunkiem że dobrze umieścisz dane wejściowe tzn ze wpiszesz jedną liczbe 16 bitową na początku do wyniku na mniej znaczących pozycjach.
    Wtedy po drodze przesuwając bity wyniku równiez przesuwamy jeden z czynniku iloczynu co czyni algorytm szybszym.
    A tak nawiasem mówiąc to można każdy algorytm "uwalić" nie podając pełnego kontekstu zdania czyli w tym wypadku deklaracji zmiennych bo podejrzewam ze zmienne mp16uh,l są zadeklarowane pod adresem zmiennych m16u0,1
    Z drugiej strony o ileż prościej by było używać standardowych nazw rejestrów zamiast deklarować nowe nazwy. Niby tak sie powinno robić ale bez przesady
    Ja bym napisał linijke komentarza przed procerurą umiesc jedna liczbe w r16,r17 druga w r20,r21 a wynik otrzymasz w r16..r19 a tak analizując kod musz latac do definicji rejestró i pamietać jakie rejestry są aktualnie używane.
  • #3 12341386
    darkonel
    Poziom 19  
    Temat nieaktualny, zamykam
REKLAMA