momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Generarea unui orar fără ferestre, sau cu cel mult câte una

GNU as
2015 jan

Presupunem formulată o schemă de repartizare a orelor pe zilele săptămânii (v. [1]) şi extragem orele unei zile - fie ca prim exemplu de lucru, sub-schema (v. şi [2]):

vb@Home:~/_ORAR$ pr -3 -t  schema_1.txt
Ailioaei    AD		Cocuz	    BDbf	Solomon	    BFbe
Badea	    BDEce	Ianul	    ef		Sirbu	    ABCFae
Bojescu	    BCabd	Iovu	    EF		Tudorache   Ed
Busuioc	    Ccdf	Lupu	    AAcd	Tanase	    Db
Butnaru	    Cabc	Neagu	    acd		Taune	    bf
Ceru	    C		Prelipcean  ABFde	Ungureanu   DEFa
Ciubotaru   Ff		Racovita    AEcf	Vatamanu    CEae

Printr-un program ca orar_zi.cpp din [2] - am obţinut fişierul binar 'schema.bin', care pe de o parte reprezintă datele schemei (indexul profesorului şi rangurile claselor la care are ore în ziua respectivă), iar pe de altă parte rezervă pentru fiecare profesor anumite câmpuri de octeţi - pregătind terenul pe care urmează să se desfăşoare un program "low-level" care să aşeze orele respective într-un orar. Dar faţă de [2] - am modificat ordinea şi dimensiunile câmpurilor preconizate:

struct bin_prof { // 36 octeţi (cu aliniere modulo 4 a adreselor câmpurilor)
    uint8_t id_cls[8] = {0,0,0,0,0,0,0,0}; // rangurile claselor (până la 0xFF)
    uint8_t id_ora[8] = {0,0,0,0,0,0,0,0}; // rangul orei, pentru fiecare clasă
    uint8_t ocup[4] = {0,0,0,0}; // şablonul binar al orelor puse (primul octet)    
    uint8_t sab_opt[4] = {0x7F,0,0,0}; // şablonul opţiunilor orare (primul octet);
    uint8_t nr_ore[4] = {0,0,0,0}; // maximum 7 (pe primul octet)
    uint8_t rang[4] = {0,0,0,0}; // rangul alfabetic al profesorului (primul octet)
    uint32_t kls = 0; // şablonul binar al claselor (rang_bit = rang_clasă)
};

Având de accesat pentru fiecare profesor clasele acestuia (pentru a le plasa pe rând într-o oră sau alta a zilei) - am fixat tabelul claselor chiar la început şi am separat iklo[16] din [2] în tablourile alăturate 'id_cls[8]' şi 'id_ora[8]'. Am supradimensionat câmpurile 'ocup' etc. la patru octeţi, dintre care numai primul este semnificativ; astfel, respectăm o regulă de optimizare a accesului la memorie încă valabilă - datele din memoria internă sunt accesate mai rapid dacă adresele lor sunt multipli de puteri ale lui 2 (v. Limbaje şi Calculator (de la nivel-înalt, la microprocesor - "Alinierea cuvintelor în memorie").

Prin urmare 'schema.bin' conţine câte 36 de octeţi pentru fiecare profesor, organizaţi pe 7 câmpuri pe care în limbaj de asamblare le vom putea adresa astfel:

Registrul %EDI va păstra adresa de bază a înregistrării curente.
0(%EDI): id_cls[8] - rangurile claselor (până la octetul 0xFF)
8(%EDI): id_ora[8] - rangul orei (indexul bitului 1), pentru fiecare clasă
16(%EDI): octetul 'ocup' - şablonul orelor puse (OR între părţile "id_ora")
20(%EDI): octetul 'sab_opt' (0x7F) - şablonul opţiunilor de plasare a orelor
24(%EDI): octetul 'nr_ore' (câte ore are, în ziua respectivă)
28(%EDI): octetul 'rang' (numărul de ordine în lista alfabetică a profesorilor)
32(%EDI): 32 biţi 'kls' - şablonul claselor (indexul bitului = rangul clasei)

Vizăm asamblorul GNU as. '%EDI' indică un registru al microprocesorului ('EDI' ar desemna o anumită variabilă a programului); '8(%EDI)' vizează al 8-lea octet al zonei indicate de %EDI.

Clasele vor fi vizate succesiv prin %ESI; iniţial, %ESI = %EDI (prin instrucţiunea movl %edi, %esi), iar pe parcurs %ESI va fi incrementat pentru a trece la clasa următoare, sau decrementat pentru a reveni la clasa precedentă. Clasa curentă va fi scoasă în %BL - prin movb (%esi), %bl.

Observăm că astfel, încălcăm regula alinierii datelor la adrese pare (%ESI va conţine şi adrese impare); am putea "corecta" folosind adresarea indexată: movb (%ESI, %ECX), %BL, prin care se transferă în %BL ("într-un singur pas"), conţinutul locaţiei de la adresa (%EDX + %ECX) - unde %ECX este iniţializat cu 0 şi apoi este incrementat. Dar este de văzut dacă merită să sacrificăm un registru (%ECX) - probabil că da, fiindcă n-am mai avea nevoie de %ESI (indexând direct de la %EDI)

Rangul orei din zi la care căutăm plasarea clasei de rang %BL va fi indicat prin %CL - iniţializat cu 1 şi apoi, deplasat spre stânga cu un bit (prin shlb $1, %CL), indicând mereu prin poziţia bitului 1 rangul curent al orei. La profesorul indicat de %EDI, se va putea plasa clasa %BL pe ora indicată de %CL, în următoarele trei condiţii:

ora %CL se încadrează intervalului orar specificat pentru clasa %BL
Programul orar_zi.cpp ne-a furnizat şi fişierul binar 'nobkls.bin', care specifică pentru fiecare clasă (anume, la indexul %BL) intervalul orar corespunzător. De exemplu, în fişierul iniţial "schema_1.txt" redat mai sus, clasa indicată prin 'D' apare de 5 ori; aceste 5 ore trebuie să constituie un subinterval al orelor zilei, începând sau de la prima oră din zi, sau de la a doua. Specificăm acest subinterval prin biţi 0 consecutivi (indexul bitului corespunzând rangului în cadrul zilei al orei); de exemplu, pentru clasa 'D' valoarea 0xE0 =11100000 specifică primele 5 ore din zi.

Cele mai fireşti subintervale orare ale claselor sunt cele care încep la prima oră din zi; dar vom putea forţa lucrurile, după caz: rolb $1, nobkls(%EBX) va deplasa mai jos, subintervalul respectiv - de exemplu, 0xE0 va deveni 0xC1 = 11000001 (5 ore, începând de la a doua din zi).

testb %CL, nobkls(%EBX) va seta bitul "Zf" (flagul zero) din registrul de "flaguri", dacă ora %CL face parte din intervalul specificat la indexul %EBX în zona de date nobkls; cu jnz ("jump if not zero") vom putea trimite la secvenţa de tratare a neîndeplinirii condiţiei noastre.

clasa %BL este liberă în ora indicată de %CL
În secţiunea de date vom menţine pe parcurs o listă orekls, marcând pentru fiecare clasă ce ore s-au plasat deja acesteia - prin setarea bitului de index corespunzător rangului 0..6 al orei plasate.
testb %CL, orekls(%EBX) va seta Zf dacă ora indicată de %CL este încă liberă, la clasa %BL.

profesorul este liber în ora indicată de %CL
Pe câmpul 'ocup' de la adresa 16(%EDX) se înregistrează pe parcurs orele setate profesorului şi testb %CL, 16(%EDX) va seta Zf dacă profesorul este liber în ora %CL.

Aceste trei condiţii sunt obligatorii, pentru a obţine un orar. Dar vizând maximum posibil, trebuie să avem în vedere încă două condiţii - legate de opţiunile unora dintre profesori în privinţa poziţionării orelor proprii şi respectiv, de acceptarea sau nu a unor ferestre.

Octetul 'sab_opt' de la adresa 20(%EDI) ne specifică opţiunile orare ale profesorului - valoarea standard fiind 0x7F, acoperind toate cele 7 ore posibile (nu există doleanţe speciale); testb %CL, 20(%EDI) va seta Zf dacă ora %CL este în afara opţiunilor orare ale profesorului.

Avem de ales între a accepta ca profesorul curent (indicat de %EDI) să aibă o fereastră, sau să evităm complet orice fereastră; este totuşi de bănuit că nu totdeauna este posibil un orar cu zero ferestre (pe o schemă de repartizare fixată) - vom vedea mai jos că pe schema redată la început (schema_1.txt) nu se poate obţine un orar fără ferestre (decât - poate - deplasând subintervalul orar al clasei 'D').

Avem două posibilităţi (dacă nu vede cineva încă vreuna): fie testăm dacă apare o fereastră chiar după verificarea celor trei condiţii obligatorii specificate mai sus pentru clasa curentă %BL şi ora curentă %CL (dacă "da", atunci încercăm altă valoare %CL pentru acea clasă), fie investigăm existenţa vreunei ferestre abia după ce vom fi realizat plasarea orelor la toate clasele profesorului curent. Am folosit şi prima posibilitate (în programul pentru DOS din 2002 - v. [1], [2]) şi pe a doua (în programul de faţă) - dar n-am reuşit să-mi dau seama dacă una este mai bună decât cealaltă.

Prima oră din orarul curent al profesorului este indicată în octetul 'ocup' de la adresa 16(%EDI) de către cel mai puţin semnificativ bit 1 al acestuia, iar ultima oră - de bitul 1 cel mai semnificativ; cu bsfw 16(%EDI), %CX obţinem în %CL rangul primei ore, iar bsrw 16(%EDI), %AX ne dă în %AL rangul ultimei ore; de exemplu, dacă ocup = 00110100 atunci "bit scan forward" ne va da 2, iar "bit scan reverse" ne va da 5.

Obţinem distanţa dintre prima şi ultima oră prin subb %CL, %AL şi o comparăm cu valoarea de pe câmpul 'nr_ore': cmpb 24(%EDI), %AL; flagul Zf va fi setat dacă valorile comparate sunt egale - iar în acest caz 'ocup' conţine o singură fereastră; altfel (distanţa este mai mică decât 'nr_ore') - va fi setat Cf ("Carry flag") - indicând că "descăzutul" %AL este mai mic decât "scăzătorul" - iar în acest caz, 'ocup' nu conţine ferestre.

Pentru ramificarea execuţiei în urma acestei comparaţii, am avea mai multe variante de lucru; deocamdată am optat pentru cea mai clară, vizând separat cele două posibilităţi: dacă sau flagul Zf este setat, sau flagul Cf este setat atunci avansăm la următorul profesor (acceptând eventuala fereastră la profesorul curent) - testul respectiv fiind asigurat de jbe ("jump if below or equal"); iar pentru a obţine totuşi un orar cu zero ferestre - înlocuim pur şi simplu "jbe" cu jc ("jump if carry). Sensul acestei separări este dat de faptul că obţinem mult mai rapid un orar în care fiecare profesor are sau zero ferestre sau una singură, decât unul în care există în total, zero ferestre.

Având ca bază logica redată mai sus (plus observaţiile din [2] referitoare la trecerea de la un profesor P1 la unul P2, după cum P1 şi P2 au sau nu clase comune) - am ajuns la următorul program 'orar.s':

.data  # secţiunea de date
    schema:  # 36 octeţi de date pentru fiecare profesor
        .incbin "schema.bin"  
    _schema: .byte 0xFF  # marchează sfârşitul înregistrărilor
    .align 4
    .set sz_sch, _schema - schema  # lungimea listei (vom "afişa" orarul final)

    nobkls:  # şablon binar pentru subintervalul orar alocat fiecărei clase
        .incbin "nobkls.bin"

    .align 4
    orekls:  # şablon binar al orelor curent plasate clasei
        .rept 32
        .byte 0  # iniţial, toţi biţii sunt 0
        .endr

.text  # secţiunea de cod 
    .global _start
_start:
    movl $schema, %EDI  # EDI va referi profesorul curent.
A:    
    movl %EDI, %ESI  # ESI referă clasa; 8(%ESI) referă şablonul binar al orei.
B:
    movb (%ESI), %BL  # BL = rangul clasei; orekls(%EBX) = şablonul orar al clasei
    cmpb $0xFF, %BL   # Dacă s-au amplasat toate clasele profesorul curent,
    jz E              # trece la 'E' (testează existenţa ferestrelor).
    movb $1, %CL      # Încearcă plasarea clasei BL pe ora I-a (bit_0) din zi.
C:
    testb %CL, nobkls(%EBX) # Ora este în intervalul orar permis clasei?   
    jnz F
    testb %CL, orekls(%EBX) # Clasa este liberă în ora CL? 
    jnz F
    testb %CL, 20(%EDI)     # Ora este în intervalul opţiunilor profesorului?
    jz F
    testb %CL, 16(%EDI)     # Profesorul este liber în ora CL?
    jnz F
    orb %CL, orekls(%EBX)  # Înscrie clasei BL ora CL. 
    movb %CL, 8(%ESI)  # Înscrie ora CL la clasa BL în orarul profesorului.
    orb %CL, 16(%EDI)  # Înregistrează ora CL pe câmpul 'ocup' al orelor puse.
    incl %ESI          # Referă următoarea clasă a profesorului şi reia. 
    jmp B
F:    
    orb %CL, %CL  # ...pentru eventualitatea că se ajunge aici cu CL==0...
    jz Q    
    shlb $1, %CL  # CL = ora următoare celeia a cărei setare nu a reuşit.
    jmp C
E:  # există ferestre?
    bsfw 16(%EDI), %CX  # CL = rangul primei ore de lucru a profesorului.
    bsrw 16(%EDI), %AX  # AL = rangul ultimei ore
    subb %CL, %AL  # AL = diferenţa dintre rangurile biţilor 1 extremi din 'ocup'.
    cmpb 24(%EDI), %AL
    jc EE  # AL < 'nr_ore' ==> NU există ferestre
    #jbe EE  # AL <= 'nr_ore' ==> există o fereastră (una singură!)

Q:  # (toate încercările de plasare au eşuat, pentru clasa BL)
    decl %ESI
    cmpl %EDI, %ESI   # Se încearcă reamplasarea clasei precedente.
    jc G              # Dar se trece la 'G', dacă nu mai există o clasă precedentă.
    movb (%ESI), %BL  # BL = clasa precedentă.
    movb 8(%ESI), %CL # CL = şablonul orei puse anterior clasei BL.
    movb %CL, %AL           
    notb %AL                # "Şterge" ora pusă anterior clasei BL,
    andb %AL, orekls(%EBX)  # atât în 'orekls'
    andb %AL, 16(%EDI)   # cât şi în 'ocup', încercând de la 'F' mutarea acelei ore.
    jmp    F

EE:
    addl $36, %EDI      # Avansează la următorul profesor.
    cmpb $0xFF, (%EDI)  # Dacă s-au parcurs toate înregistrările, trece la 'L' -
    jnz    A            # altfel, reia de la 'A'.
    jmp    L

G:  # Amplasarea/reamplasarea claselor profesorului curent au eşuat.
    cmpl $schema, %EDI   # Dacă nu există profesori anteriori celui curent P1 - încheie
    jz LL                # (NU poate fi construit un orar cu ZERO ferestre).
    movl 32(%EDI), %EAX  # EAX = şablonul binar al claselor lui P1 (câmpul 'kls').
    subl $36, %EDI       # EDI referă acum profesorul anterior P2.
    testl 32(%EDI), %EAX # Trece la 'J' dacă P1 şi P2 au clase comune.
    jnz J
H:    
    movl %EDI, %ESI     # Dacă P2 nu are clase comune cu P1 -
    movb 24(%EDI), %CL  # şterge orele celor 'nr_ore' clase ale lui P2.
    xorb %CH, %CH
I:    
    movb (%ESI), %BL        # BL = rangul clasei curente.
    movb 8(%ESI), %AH       # AH = şablonul orei puse clasei BL.
    notb %AH                # Inversează AH, pentru a
    andb %AH, orekls(%EBX)  # şterge bitul respectiv în şablonul orelor plasate clasei BL.
    incl %ESI               # Referă următoarea clasă (dintre cele 'nr_ore') şi repetă.
    loop    I
    movb $0, 16(%EDI)  # Reiniţializează 'ocup' (şterge orele plasate anterior lui P2).
    jmp G

J:  # P1 şi P2 au clase comune: reamplasează clasele profesorului P2.   
    movl %EDI, %ESI 
    movb 24(%EDI), %CL
    xorb %CH, %CH
    addl %ECX, %ESI         
    movb (%ESI), %BL        # BL = rangul ultimei clase a lui P2.
    movb 8(%ESI), %CL       # CL = şablonul orei puse ultimei clase a lui P2.
    movb %CL, %AL           
    notb %AL
    andb %AL, orekls(%EBX)  # Şterge ora pusă clasei BL.
    andb %AL, 16(%EDI)      
    jmp F                   # Încearcă de la 'F', modificarea orei respective.

L:  # invocă write(); având date binare, ieşirea trebuie redirectată pe un fişier 'orar.bin'
    movl $4, %eax  
    movl $1, %ebx
    movl $schema, %ecx
    movl $sz_sch, %edx
    int $0x80
LL:
    movl $1, %eax  # invocă exit()
    movl $0, %ebx
    int $0x80

Obţinem fişierul executabil 'orar' invocând asamblorul as şi apoi link-editorul ld:

vb@Home:~/_ORAR$ as --32 -o orar.o orar.s
vb@Home:~/_ORAR$ ld -m elf_i386 -o orar32 orar.o

Eliminând opţiunile --32 şi respectiv, -m elf_i386 obţineam un executabil pentru x86_64 (şi nu pentru IA-32, ca în cazul prezenţei acestor opţiuni); este însă perfect suficient executabilul obţinut pentru "--32" (cel pentru "--64" nu este cu nimic superior) - posibil de obţinut tocmai pentru că nu am folosit (şi chiar nu am avut nevoie să folosim) regiştrii de 64 biţi, sau instrucţiuni specifice x86-64.

În treacăt fie spus - programul-sursă redat mai sus - deşi poate părea lung - are numai 78 de instrucţiuni în limbaj de asamblare, codificate împreună pe un total de 231 octeţi.

Executăm pentru exemplul considerat la început, în cazul jbe EE (admitem câte cel mult o fereastră) - având grijă să redirectăm ieşirea către un fişier:

vb@Home:~/_ORAR$ time ./orar32  > orar.bin
real	0m0.094s
user	0m0.090s
sys	0m0.004s

Rezultatul s-a obţinut instantaneu şi îl redăm printr-un program analog cu 'orar_zi.cpp':

vb@Home:~/_ORAR$ ./oraz32  schema_1.txt  orar.bin
Ailioaei    . . . . D A .   # ora a 5-a şi a 6-a, la clasele 'D' şi respectiv 'A'
Badea       B D E c e . . 
Bojescu     d a . C B b .   # fereastră în ora a 3-a
Busuioc     . C . d f c . 
Butnaru     . . b a c C . 
Ceru        C . . . . . . 
Ciubotaru   f F . . . . . 
Cocuz       . . D B b f . 
Ianul       e . f . . . . 
Iovu        . E F . . . . 
Lupu        c . A A d . . 
Neagu       a c d . . . . 
Prelipcean  F A B e . d . 
Racovita    . . c f A E . 
Solomon     . e . b F B . 
Sirbu       A B C F a e . 
Tudorache   E d . . . . . 
Tanase      D b . . . . . 
Taune       b f . . . . . 
Ungureanu   . . a D E F . 
Vatamanu    . . e E C a . 

Avem în total 5 ferestre de câte o oră; una poate fi "reparată" imediat: la 'Busuioc', mutăm ora 'c' din poziţia 6 în prima poziţie şi la 'Lupu' mutăm 'c' din prima poziţie pe a 6-a (astfel, am eliminat fereastra lui 'Lupu'). Putem reduce şi alte ferestre - dar în cazul de faţă nu pe toate!

Reasamblăm programul folosind acum jc EE (pentru a obţine un orar cu zero ferestre) şi-l executăm redirectând ieşirea pe un alt fişier, 'orar_1.bin'; execuţia durează enorm faţă de primul caz (cam o oră) iar fişierul 'orar_1.bin' este vid - însemnând că nu s-a mai executat secvenţa write() de la adresa 'L' ci doar secvenţa exit() de la adresa LL, la care se trimite din secvenţa 'G' în cazul epuizării tuturor posibilităţilor de plasare / reamplasare a orelor. Cu alte cuvinte - schema dată iniţial nu admite un orar cu zero ferestre.

Pentru încă un exemplu, considerăm următoarea schemă:

vb@Home:~/_ORAR$ pr -4 -t schema_2.txt
 Andries   BC	       Cozma   DEcd 	Mircea	 BFHd 	 Popescu   A
   Baciu   defg      Diaconu   Cg     Musteata	 DGce 	  Pruncu   af
   Bazon   AAab     Dosoftei   FGG     Nicolae	 a    	    Stan   DEFH
   Bogos   BC	  Dumitrescu   BEc  	Nitica	 Dad  	   Stroe   ADH
 Braescu   FI	     Ghergut   cf      Pantiru	 Gbg  	Vasilica   EFGI
Calancea   CHe     Hotoleanu   BCIa 	 Peptu	 G     Virlanuta   DIa
    Carp   Ad	    Iticescu   Hb   	  Popa	 BEc  	Zarnescu   Hbc
   Coman   beg

Obţinem fişierele binare 'schema.bin' şi 'nobkls.bin' folosind programul 'orar_zi.cpp' şi apoi executăm (în varianta cu 'jc EE'):

vb@Home:~/_ORAR$ time ./orar32 > orar_2.bin
real	3m25.454s

obţinând (în 3 - 4 minute) un orar cu zero ferestre (afişat aici pe 3 coloane):

vb@Home:~/_ORAR$  ./oraz32  schema_2.txt  orar_2.bin | pr -3 -t
Andries	  . . C B . .   Dosoftei    . . . G F G   Peptu	    G . . . . .
Baciu	  e d f g . .   Dumitrescu  . . E c B .   Popa	    B E c . . .
Bazon	  . A a A b .   Ghergut	    . . . . f c   Popescu   A . . . . .
Bogos	  . . . . C B   Hotoleanu   I C B f a b   Pruncu    a f . . . .
Braescu	  F I . . . .   Iticescu    H b . . . .   Stan	    . . D F E H
Calancea  . . e C H .   Mircea	    d B F H g .   Stroe	    D H A . . .
Carp	  . . . d A .   Musteata    c e G D . .   Vasilica  E F I e G .
Coman	  . . g b e .   Nicolae	    . a . . . .   Virlanuta . . . I D a
Cozma	  f D d E c .   Nitica	    . . . a d D   Zarnescu  b c H . . .
Diaconu	  C g . . . .   Pantiru	    g G b . . . 

Programul 'oraz32' invocat mai sus provine dintr-un program C++11 analog cu 'orar_zi.cpp' din [2]; primeşte ca parametri numele fişierului în care avem schema iniţială şi numele fişierului binar care conţine orarul (produs prin execuţia subrutinei 'orar32') şi converteşte datele binare, legându-le de numele profesorilor şi ale claselor - producând în final afişarea orarului respectiv.

vezi Cărţile mele (de programare)

docerpro | Prev | Next