luni, 8 octombrie 2012

Realizarea construcţiilor algoritmice de bază: condiţii, selecţie multiplă, cicluri.


  Programarea în limbajul ASM (și nu numai în ASM) se reduce executarea condiționată sau necondiționată a unor instrucțiuni.
    Pentru executarea necondiționată vom avea asa numiții algoritmi seriali, care sunt compuși dintr-o serie de operații de transfer și prelucrare.

    Execuția condiționată presupune execuția unui set de instrucțiuni de transfer sau prelucrare în dependența de o condiție.

    Prin "set de instrucțiuni" vom avea în vedere de la nici o comandă până la secvențe complexe de program.

    Setul de comenzi pentru arhitectura AVR presupune două tipuri de comenzi condiționale: 
  • Comenzi de salt condiționat - BR_OP LABEL
  • Comenzi de ignorare a instrucțiunii imediat următoare  -  SB_OP




Implementarea algoritmilor cu comenzi de salt condiționat

    Comenzile de acest tip sunt comenzi care după testarea unei anumite condiții, presupuse de comanda, de obicei fiind un bit din registrul de stare SREG, execută un salt a execuției la o adresa fixă specificată de eticheta (label). În constext vom numi acest tip de comenzi ca BR_OP - operații de ramificare. Biții verificați din SREG pot fi gasiți în tabelul de comenzi a operațiilor de transfer al controlului, operații de salt condiționat.


    Pentru acest tip de comenzi putem face niște echivalări cu instrucțiunile condiționale din limbajele de nivel înalt cum ar fi Limbajul C.
  De ex:
    BREQ     if ==  daca este egalitate
    BRNE     if !=  daca este diferit
    BRSH     if >=  daca este mai mare sau egal
    BRLO     if <   daca este mai mic
    etc.

    O comanda de tip BR_OP de cele mai dese ori este precedată de o instrucțiune de comparație CP, CPI sau TEST. Comenzile de comparație sunt menite pentru a evalua relația între elementele participante la TEST având ca rezultat modificarea registrului de stare SREG. O instrucțiune de tip BR_OP poate să nu fie precedată de o operație comparație. Acest lucru este posibil în cazul în care operația de prelucrare de înaintea operației de ramificare configurează corect registrul SREG în starea dorită pentru ramificare. De exemplu după o decrementare până la ZERO în cicluri. De fapt în spatele comparației se execută o operație de scădere fără a salva rezultatul operației, iar ca urmare a operației de scădere se vor seta biții din registrul de stare SREG.

   

    Construcția algoritmică de ramificare în ulimbajul ASM poate fi implementată după cum urmează unde     etichetele L1, L2, L3 și L4 corespund punctelor cu același nume prezentate în figura de mai sus.

L1:             ; inceputul constructiei de ramificare
    cp R1,R2    ; operatia de comparare (R2 - R1)
    BR_OP L3    ; operatia de salt conditionat - ramificare
L2:             ; F - test FALSE
    ... 
    ...         ; OP1 - setul de instructiuni pentru ramura FALS
    ...
    rjmp L4     ; salt neconditionat la sfarsitul
                ; constructiei de ramificare
L3:             ; T - test TRUE
    ... 
    ...         ; OP2 - setul de instructiuni pentru ramura TRUE
    ...
    (rjmp L4)   ; poate fi omis
L4:             ; sfarsitul constructiei de ramificare



Implementarea ramificărilor cu comenzi de ignorare a următoarei comenzi.

Comenzile de acest tip presupun ignorarea execuției comenzii imediat care o urmează. Vom numi acest tip de comenzi în acest context ca comenzi tip SB_OP. Aceste comenzi de cele mai dese ori presupun verificarea unui bit dintr-un Registru de Uz General (din cei 32), Registru Periferic (din cei 64) sau registrul SREG. Bitul verificat se poate găsi din tabelul de comenzi pentru fiecare comandă în parte. Saltul condiționat pentru aceste comenzi va fi reprezentat prin saltul peste o comandă, și deci nu este nevoie de specificat adresa la care va avea loc saltul.
    Formatul instrucțiunii va arăta după cum urmează:

    • SB_OP TST_REG, N unde:
      • SB_OP - denumirea comenzii care va specifica o testare la bit setat sau resetat
      • TST_REG - numele registrului testat
      • N - numărul de ordine a bitului testat în registrul selectat
   Iar definiția comenzii va suna în felul următor: Salt peste o comandă (PC = PC+2) dacă bitul N din registrul TST_REG este setat/resetat. În caz contrar execută comanda următoare (PC=PC+1).



    Echivalările pentru limbajele de nivel înalt vor fi de tip 
     if(TST_REG[N]==0)
   sau
     if(TST_REG[N]==1)

     Aceste comenzi nu necesită operații de pre-comparare, ele execută comparația necesară și saltul în cadrul aceleiași instrucțiuni.
    Vom realiza mai jos construcția algoritmică de ramificare și  implementarea ei în ulimbajul ASM unde     etichetele L1, L2, L3 și L4 corespund punctelor cu același nume.
 



L1:             ; inceputul constructiei de ramificare
    SB_OP       ; operatia ignorare a comenzii ce urmeaza
    rjmp L3     ; salt la executia clauzei FALSE
   (rjmp L2)    ; salt la executia clauzei TRUE, poate fi omis
L2:             ; T - test TRUE
    ... 
    ...         ; OP1 - setul de instructiuni pentru ramura TRUE
    ...
    rjmp L4     ; salt neconditionat la sfarsitul
                ; constructiei de ramificare
L3:             ; F - test FALSE
    ... 
    ...         ; OP2 - setul de instructiuni pentru ramura FALSE
    ...
    (rjmp L4)   ; poate fi omis
L4:             ; sfarsitul constructiei de ramificare


Realizarea construcțiilor algoritmice complexe în baza ramificărilor
    După cum s-a putut observa construcțiile algoritmice discutate pana acum se refera in special implementării instructiunii if ... else a limbajelor de nivel înalt (cum ar fi C/C++).
    Majoritatea limbajelor de nivel inalt au un set de instrucțiuni specializate pentru implementarea construcțiilor algoritmice condiționale, selecție, și ciclice cum ar fi:
  • Condiționale
    • if ... else if
    • switch/case
  • Cicluri
    • while
    • do ... while
    • for
Vom analiza fiecare construcție în parte și von da o realizare în limbajul ASM a fiecărei din acestea.

Imlementarea instructiunilor if ... else if

    Realizarea instrucțiunilor de tip if ... else if coincide cu relizarea construcțiilor de ramificare expuse mai sus și deci tot ce s-a vorbit la acest capitol este aplicabil pentru acest tip de instrucțiuni. Vom adăuga doar faptul că clauza FALSE va conține încă o ramificare de același tip. În acest mod vom obține un lant de verificări de-a lungul clauzei FALSE. Ramificările se pot face cât cu instrucțiuni de tip BR_OP cât și cu SB_OP iar utilizarea unui anumit tip va impune respectarea regulilor de implementare descrise mai sus. Ramificările pot fi cu același tip de instrucțiuni sau mixate, utilizând ambele tipui de verificări.


   
Cazul cu SB_OP este identic cu cel prezentat mai sus, cu înlocuirea operațiilor de ramificare respective și respectarea regulilor de implementare pentru acest tip de instrucțiuni (SB_OP ).

Instrucțiunea de selectie switch/case

    Instrucțiunile de selecție switch/case reprezintă un caz particular al instrucțiunii if ... else if cu constrângerea ca se verifică aceiași variabilă/registru la egalitate cu diferite valori constante. Operația de verificare la egalitate va fi una de tip BR_OP și anume BREQ sau BRNE și deci implementarea instrucțiunii de selecție se va supune regulilor de implementare a acestui tip de instrucțiuni.

Instructiune de ciclu cu pre comparare while

    Această instrucțiune permite execuția unei secvențe de cod atîta timp cât o condiție este adevărată. Adică mai întâi se evaluează condiția și în cazul când condiția este satisfacută se execută un set de instrucțiuni după care are loc un salt spre o nouă comparație formând o buclă de execuție. În cazul în care condiția dă un rezultat FALSE instrucțiunile incluse în secvența ciclului nu se mai execuă și are loc un salt necondiționat la prima instrucțiune după ciclu. Construcția algoritmică pentru un asemenea ciclu va arăta în felul urmator:

Instrucțiune de ciclu cu post comparare do ... while

    Pentru această construcție algoritmică vom avea mai întîi execuția setului de instrucțiuni cuprinse în ciclu după care se va evalua comparația. În cazul când condiția se satisface vom avea un salt spre începutul blocului de instrucțiuni. În cazul în care nu se satisface condiția execuția continuă cu urmatoarea comandă după cea de comparație. Am putea organiza instrucțiunile în așa mod ca ultima instrucțiune din setul cuprins în corpul ciclului să seteze flagurile din SREG pentru a fi evaluate de către instrucțiunea de comparație BR_OP, și respectiv vom putea exclude din ciclu operația de comparație CP.

 

Instructiune de ciclu  for

    Această construcție poate fi implementată urmând principiul pentru instrucțiunea cu pre comparare while. Va conține o pre inițializare a contorului, verificare a condiției de ieșire din ciclu. Setul de instrucțiuni cuprins în corpul ciclului și la sfârșitul ciclului o operație de progresare a iteratorului. În calitate de iterator va servi un registru de uz general.

    unde  ~BR_OP vom spune ca este o comparație complementară, adică în loc de "<=" vom verifica ">".

Generalitați despre ciluri.

    Implementarea ciclurilor cu ramificări de tip SB_OP este identică cu cele implementate cu BR_OP înlocuind operațiile de ramificare respective și respectarea regulilor de implementare pentru acest tip de instrucțiuni (SB_OP ).
    Facînd o anliză generală despre cicluri  ca concluzie putem spune ca s-ar recomanda implementarea algoritmilor utilizînd construcții de tip do ... while fiind  mai optimale din punct de vedere a performanței.