Tajemnice Atari - nieoficjalne elektroniczne archiwum

Tajemnice ATARI

MulDiv

    Po początkowym zainteresowaniu różnego rodzaju grami komputerowymi przychodzi czas na napisanie pierwszego programu. Początkujący programiści zaczynają zazwyczaj od poznania języka BASIC. Pomimo swych wielu wad posiada on niewątpliwą zaletę, jaką jest stała obecność w pamięci komputera, w związku z czym nie trzeba go wczytywać z dysku lub, co gorsza, z kasety. Język ten, bądź co bądź przestarzały i wyrabiający nie najlepsze nawyki, nie sprawia większych problemów w realizowaniu najprostszych pomysłów. Po pewnym jednak czasie jego możliwości stają się niewystarczające. Wielu programistów zdenerwowanych powolnością BASIC-a sięga wtedy po wygodniejsze i szybsze narzędzia, jakimi są np. TURBO BASIC XL lub Action!. Są jednak i tacy, którzy postanawiają zgłębić tajniki sztuki, jaką jest programowanie komputerów, sięgając po język niższego rzędu - Assembler.

    Powszechnie wiadomo, że jest to język bardzo szybki. Niestety, jego zwinność okupiona została niewielką liczbą operacji dostępnych dla użytkownika. Należą do nich między innymi proste operacje logiczne, porównania, skoki, a także działania arytmetyczne na liczbach binarnych i w tzw. kodzie BCD. Projektanci 6502 zapomnieli niestety o bardzo wygodnych rozkazach mnożenia i dzielenia, w które są wyposażone inne, tak popularne procesory, jak np. INTEL 8086.

    Kiedy więc programista, piszący dawniej w BASIC-u, zechce przeprowadzić tak prostą z jego punktu widzenia operację, jaką jest

MNOŻENIE.

często staje ze smutnie opuszczoną głową, lub też miota się z kąta w kąt, nadaremnie szukając sposobu rozwiązania owego problemu. Pierwszą metodą, która wtedy przychodzi do głowy jest mnożenie przez wielokrotne dodawanie.

Tok postępowania jest prosty: aby otrzymać wynik mnożenia liczb A przez B, należy liczbę A dodać do siebie B razy.

Poniższy program doskonale to obrazuje:

__mul ldy __b
      beq __don ;skok gdy B=0
      clc
__lop adc __a   ;dodanie A
      bcc __dec
      inx       ;zwiększenie MSB wyniku
      clc
__dec dey       ;zmniejszenie B o 1
      bne __lop ;skok gdy B<>0
__don rts

Przed skokiem do podprogramu należy do rejestrów .A i .X w kolejności LSB, MSB wpisać liczbę, do której ma zostać dodany wynik mnożenia (jest to bardzo wygodne przy wielokrotnym sumowaniu iloczynów różnych liczb), a w komórkach __A i __B umieścić wartości czynników mnożenia. Dla potrzeb programu należy zdefiniować jeszcze dwie komórki pomocnicze:

__a   dta b(0)
__b   dta b(0)

    Rezultat operacji uzyskamy w rejestrach .A i .Y procesora w kolejności LSB, MSB. Widzimy tutaj, że czas trwania procedury zależy od liczby wpisanej do __B. Im jest ona większa, tym dłużej będzie przebiegać cała operacja. Tak więc osobom, którym zależy przede wszystkim na czasie, w związku z czym powyższa procedura może dla ich potrzeb okazać się niewystarczająca, proponuję dokładną analizę kolejnej metody, opierającej się również na wielokrotnym dodawaniu. Jak wiadomo z trzeciej klasy szkoły podstawowej, każdy iloczyn dwóch liczb można rozpisać jako iloczyn jednego z czynników mnożenia i sumy dowolnych liczb, dających w wyniku drugi czynnik owego działania, np.:

2*20=2*(10+5+3+2)

lub

2*20=(1+1)*20.

    Zgodnie z powyższym możemy dowolne mnożenie rozpisać jako iloczyn pierwszego z czynników mnożenia i sumę kolejnych, nie powtarzających się potęg liczby dwa, dających w wyniku drugi czynnik działania, np.:

3*28=3*(16+8+4)=3*(2⁴+2³+2²)= 3*(1*2⁴+1*2³+1*2²+0*2¹+0*2⁰).

    Wynik mnożenia uzyskamy, sumując poszczególne iloczyny pierwszego czynnika mnożenia przez odpowiednie potęgi liczby dwa. Niejeden Czytelnik w tym momencie mógłby się zdziwić i powiedzieć: "Przecież procesor 6502 nie posiada na swojej liście rozkazów mnożenia, co czyni niemożliwym wykonanie także i potęgowania!". Niewątpliwie miałby on rację, lecz procesor 6502 posiada polecenia ASL i ROL, które przesuwają poszczególne bity w lewo, powodując proste mnożenie przez dwa. Poprzez wielokrotną rotację dowolnej liczby w lewo otrzymamy więc iloczyn tejże liczby i poszczególnych potęg liczby "dwa", np.:

3*2 = 3*2¹ - przesunięcie jednokrotne
3*2*2 = 3*2² - przesunięcie dwukrotne
3*2*2*2=3*2³ - przesunięcie trzykrotne.

    Program obliczający iloczyn dwóch liczb i opierający się na powyższych założeniach wygląda tak:

__mul eor #%1lllllll ;modyfikacja
      sta __bta   ;pierwszego czynnika

      stx __btb   ;przygotowanie
      ldx #0      ;drugiego czynnika
      stx   __btb+2

      ldx #8      ;długość słowa


__lop lsr __bta  ;sprawdzenie aktualnej
      bcs __nxt   ;potęgi dwójki

      lda __btb   ;dodanie __BTB
      adc __rsl   ;pomnożonego przez 2
      sta __rsl   ;2 do potęgi 8-.X do
      lda __btb+1 ;wyniku
      adc __rsl+1
      sta __rsl+1

__nxt asl __btb   ;pomnożenie __BTB
      rol __btb+1 ;przez kolejną potęgę
                  ;liczby 2

      dex
      bne __lop
      rts

Do prawidłowego działania procedury należy jeszcze zarezerwować komórki, gdzie będą umieszczone wartości czynników mnożenia i wynik.

__bta org *+1
__btb org *+2
__rsl org *+2

    Moment zastanowienia mogłaby wywołać rezerwacja dwóch bajtów dla __BTB. Jest to celowe, gdyż np. liczba 128 pomnożona już przez pierwszą potęgę liczby 2 daje w wyniku 256, a więc liczbę, nie mieszczącą się w ośmiu bitach.

    Przed użyciem procedury należy umieścić liczbę, która będzie dodana do iloczynu w komórkach __RSL oraz __RSL+1 w kolejności LSB i MSB, a w .A i .X wpisać czynniki mnożenia. Powyższy podprogram powoduje pomnożenie przez siebie dwóch liczb ośmiobitowych, wpisując szesnastobitowy wynik do komórek __RSL i __RSL+1 w wiadomej kolejności. Warto zauważyć, ze w przeciwieństwie do poprzedniego, czas wykonywania tego podprogramu jest dla różnych danych mniej więcej taki sam.

    Niemniej wygodnym, co spędzającym sen z powiek utrapieniem jest

DZIELENIE.

Najprostszy iloraz liczby szesnastobitowej przez ośmiobitową realizowany jest przez wielokrotne odejmowanie dzielnika od dzielnej:

__div ldy #0    ;przygotowanie .Y

__lop lda __a   ;odejmowanie dzielnika 
      sbc __b   ;od dzielnej
      tax 
      lda __a+1
      sbc #0
      bcc __don ;skok gdy __A<__B

      stx __a   ;zapis reszty
      sta __a+1
      iny       ;zwiększenie wyniku o 1
      bne __lop
      ldy #$ff  ;dzielenie przez liczbę
don__ rts       ;dającą wynik>255

Przed uruchomieniem procedury należy umieścić dzielną i dzielnik we wcześniej zarezerwowanych komórkach.

__a   org *+2
__b   org *+1

    Po powrocie z podprogramu .Y zawiera ośmiobitowy wynik (w przypadku dzielenia przez zero umieszczana jest tam wartość 255), a komórka __A resztę z dzielenia __A przez __B. Zawartość dzielnika nie jest kasowana. W tym przypadku czas działania procedury zależy od wielkości dzielnej i wartości dzielnika (im mniejszy dzielnik i większa dzielna, tym dłuższy czas).

    Niżej przedstawiona procedura dzielenia jest dokładną odwrotnością, opisywanego przeze mnie, drugiego ze sposobów mnożenia liczb ośmiobitowych. Polega ona na odejmowaniu od dzielnej iloczynów dzielnika i poszczególnych potęg liczby dwa w kolejności od najstarszej do najmłodszej.

    Tok postępowania:

1. Jeśli dzielna jest większa lub równa iloczynowi dzielnika i 2^N oznacza to, że dzielnik mieści się w dzielnej 2^N razy, np.:

128=8*2⁴ - dzielnik (8) mieści się w dzielnej (128) 2⁴ razy.

2. Jeśli relacja ta jest prawdziwa, dodajemy do wyniku 2^N i odejmujemy od dzielnej iloczyn tegoż właśnie 2^N i dzielnika.

3. Zmniejszamy numer potęgi (N) liczby 2, przez którą mnożymy dzielnik i jeśli N=0, to powtarzamy wszystkie operacje.

    Po zakończeniu działania reszta z dzielenia znajduje się w dzielnej.

    Oto przykładowy przebieg ośmiobitowego dzielenia liczby 120 przez 11:

B=11, W=(A=B*2^N) ;0 - fałsz, 1 - prawda

N=7, A=120, W=0

N=6, A=120, W=0

N=5, A=120, W=0

N=4, A=120, W=0

N=3, A=120, W=1, B*2^N=88

N=2, A=32, W=0

N=1, A=32, W=1,B*2^N=22

N=0, A=10, W=0
wynik: 00001010 bin = 10 dec, reszta: 10 dec.

Opis metody odbiega nieco od treści procedury (zamiast nieporęcznych operacji dodawania 2^N do wyniku, użyłem rotacji bitów), jednakże jej istota nie została przez to zmieniona.

__div sta __bta   ;przygotowanie 
      stx __bta+1 ;danych 
      ldx #0
      stx __btb
      sty __btb+1 ;dzielnik*2^8

      ldx #8      ;długość słowa

__lop lsr __btb   ;dzielnik*2(.X-1)
      ror __btb+1

      lda __bta   ;dzielna-dzielnik
      sbc __btb   ;a zarazem porównanie
      tay
      lda __bta+1
      sbc __btb+1
      bcc __nxt   ;skok gdy __BTA<__BTB

      sty __bta   ;dzielna=dzielna+
      sta __bta+1 ; -dzielnik*2(.X-1)

__nxt rol __rsl   ;"wciągnięcie" potęgi
      dex         ;.X-1 do wyniku
      bne __lop
      rts

Procedura ta, jak i poprzednie, także wymaga rezerwacji pamięci dla swych danych.

__bta org *+2 
__btb org *+2
__rsl org *+1

    Wykorzystanie procedury sprowadza się do umieszczenia dzielnej w .A i .X w formacie LSB i MSB, oraz dzielnika w .Y i wywołania __div. Po powrocie z podprogramu w komórce __RSL znajduje się wynik a w __BTA reszta z dzielenia. Analogicznie, jak w przypadku drugiej procedury mnożącej dwa bajty, czas obliczeń powyższej procedury nie zależy od wartości danych.

    Uwaga! Zawartości komórek od __BTA do __RSL włącznie ulegają zmianie w trakcie działania podprogramu.

    Wszystkie opublikowane procedury można w prosty sposób uzdatnić do obliczeń o dowolnej precyzji. W jaki sposób? Ten problem pozostawiam Czytelnikowi.

(jk)

P.S. Procedury zostały napisane pod QA w konwencji programów firmowych. Użyte w tekście skróty LSB i MSB oznaczają rzecz jasna "least significant byte" - mniej znaczący bajt i "most significant byte" - bardziej znaczący bajt.

Powrót na start | Powrót do spisu treści | Powrót na stronę główną