Operaţii la nivel de biţi - recapitulare

Operatorii pe biţi sunt:

~ negare, operator unar ~x (inverseză fiecare bit al lui x)& Şi a&b (face şi între biţii lui a şi ai lui b)| Sau a|b (face sau între biţii lui a şi ai lui b)^ sau exclusiv a^b (face sau exclusiv între biţii lui a şi ai lui b)>> deplasare dreapta a>>nr<< deplasare stânga a<<nr

Pentru a accesa anumiţi biţi din cadrul unui octet, putem folosi măştile: pe primele 3 poziţii ale lui nr reţinem un nr, pe următoarele 5 alt numar; mai jos este scris codul pentru a accesa (scrie, afisa) valoarea stocată pe primii 3 biţi.

unsigned short nr = (4 << 5) + 7; // pp nr are 2 octeti unsigned short primii3biti_siftati, primii3biti; printf("%hu\n", nr); // nr initial primii3biti = nr & 0xE0; // 1110 000 in hexa este E 0 // primii 3 biti au ramas pe valoarea lor (1 sau 0), ceilalti // sunt 0 primii3biti_siftati = primii3biti >> 5; // (8 total - cei 3 // biti) printf("%hu\n", primii3biti_siftati); nr = nr & ~0xE0; // setam pe 0 primii 3 biti printf("%hu\n", nr); // nr cu primii 3 biti pe 0

Structuri cu câmpuri pe biţi

Să considerăm o structură pentru memorarea unei date calendaristice:

struct data{

int zi;int luna;int an;

};

În această formă structura ocupă în memorie 12 octeţi (3 câmpuri de tip int înseamnă 3x4=12 octeţi).

Dacă analizăm mai atent lucrurile, observăm că fiecare din cele trei câmpuri ar putea fi memorat pe mai puţin de patru octeţi. Spre exemplu câmpul zi va lua valori între 1 şi 31, deci ar putea fi memorat pe 5 biţi (cea mai mică putere a lui 2 mai mare decât 31 este 32=2^5). Câmpul luna va lua valori între 1 şi 12, deci ar putea fi memorat pe 4 biţi (cea mai mică putere a lui 2 mai mare decât 12 este 16=2^4). Iar câmpul an să presupunem că va lua valori între -9999 şi 9999, deci poate fi reprezentat pe 15 biţi (avem din start un bit de semn deoarece vrem să putem reţine şi numere negative, iar cea mai mică putere a lui 2 mai mare decât 9999 este 16384=2^14; rezultă în total 15 biţi). Vedem că cele trei câmpuri împreună ar necesita de fapt doar 5+4+15=24 biţi, adică 3 octeţi. Cu alte cuvinte folosim un spaţiu de memorie de patru ori mai mare decât ar fi necesar.

În limbajul C putem specifica pentru câmpurile de tip int sau char dimensiunea în biţi pe care să o ocupe. Dimensiunea în biţi se specifică plasând imediat după definirea câmpului caracterul : urmat de numărul de biţi pe care dorim să îl ocupe câmpul. Putem redefini structura de mai sus astfel:

struct data_biti{

unsigned int zi : 5;unsigned int luna : 4;int an : 15;

};

Dacă urmărim (cu ajutorul operatorului sizeof) dimensiunea ocupată de structura redefinită astfel, vom vedea că este întradevăr mai mică. Deşi ne-am aştepta ca ea să fie de 3 octeţi, în practică ea este de 4 octeţi. Acest lucru se întâmplă din motive de aliniere a variabilelor în memorie (deoarece tipul de bază al câmpurilor este int, care înseamnă 4 octeţi, structura este extinsă la multiplu de 4 octeţi).

Într-o structură pot alterna câmpurile definite pe biţi cu cele definite clasic. Spre exemplu să considerăm o structură pentru descrierea unor produse de panificatie. Vom reţine tipul produsului (paine, covrig sau corn), greutatea produsului în kg (număr real) şi numărul de cereale ce intră în compoziţia produsului (minim 0, maxim 7). Tipul produsului poate lua trei valori pe care le codificăm cu 0, 1 şi 2. Ca urmare avem nevoie de doi biţi pentru memorarea tipului. Greutatea este număr real şi o vom păstra într-un câmp de tip float. Numărul de cereale poate lua valori de la 0 până la 7, deci încape pe 3 biţi. Avem următoarea definire a structurii:

struct panificatie{

unsigned int tip : 2; /* 0 - paine; 1 - covrig; 2 - corn */float greutate; /* greutate in kg */unsigned int cereale : 3; /* numarul de cereale ce intra in compozitie, maxim 7 */

};

Primul câmp ocupă 2 biţi, al doilea ocupă 4 octeţi, fiind de tip float, iar al treilea ocupă 3 biţi. În total avem 2+32+3=37 biţi, care încap în 5 octeţi. Totuşi dacă urmărim dimensiunea structurii folosind operatorul sizeof, vom vedea că în realitate ocupă 12 octeţi. Asta deoarece atunci când un câmp pe biţi este urmat de un câmp definit clasic, câmpul pe biţi este completat automat cu biţi neutilizaţi până la dimensiunea câmpului de bază. Cum în exemplul nostru câmpul tip are ca tip de bază tipul int, el va fi completat cu biţi nefolosiţi până la 4 octeţi. La fel se întâmplă şi dacă ultimul câmp din structură este definit pe biţi: el va fi completat cu biţi neutilizaţi până la dimensiunea tipului de bază (tot int în cazul nostru).

Pentru structura noastră harta memoriei arată astfel:

2 biţi pentru câmpul tip

30 de biţi neutilizaţi 4 octeţi (32 de biţi) pentru câmpul greutate

3 biţi pentru câmpul cereale

29 de biţi neutilizaţi

Avem în total 30+29=59 de biţi neutilizaţi. Pentru a scădea la minim risipa de spaţiu, trebuie să grupăm câmpurile pe biţi unul lângă altul. Rescriem structura astfel:

struct panificatie_optim{

unsigned int tip : 2; /* 0 - paine; 1 - covrig; 2 - corn */unsigned int cereale : 3; /* numarul de cereale ce intra in

compozitie, maxim 7 */float greutate; /* greutatea in kg */

};

De data aceasta se adaugă biţi neutilizaţi doar după câmpul cereale. Harta memoriei arată astfel:

2 biţi pentru câmpul tip

3 biţi pentru câmpul cereale

27 de biţi neutilizaţi 4 octeţi (32 de biţi) pentru câmpul greutate

Numărul biţilor neutilizaţi a scăzut la 27, iar dimensiunea totală a structurii a scăzut la 8 octeţi.

Atenţie la modificatorul unsigned. Un câmp definit pe doi biţi cu modificatorul unsigned va reţine valori de la 0 până la 3. Dacă nu apare modificatorul unsigned, atunci câmpul este cu semn şi va reţine valori de la -2 până la 1. Trebuie avut în vedere acest lucru atunci când definim structuri folosind câmpuri pe biţi.

Parametri din linie de comandă

Când scriem un program C, pentru a putea rula programul trebuie să îl transformăm din fişier text (codul sursă este păstrat în fişiere text) în fişier binar executabil. Această transformare se face prin două operaţii: compilare şi link-editare. În general ambele operaţii sunt efectuate automat de compilator (gcc), astfel încât noi nu suntem conştienţi de ele.

Ceea ce putem constata noi e că dacă avem un fişier sursă, spre exemplu “prog.c”, şi îl compilăm şi link-edităm cu succes (gcc –o prog prog.c), pe disc apare un fişier numit “prog”. Fişierul “prog.c” este fişier text, iar fişierul “prog” este fişier binar executabil. Din linia de comandă putem rula fişierul binar executabil. Pentru a rula fişierul binar din linie de comandă, scriem numele lui precedat de caracterele ./

Dacă fişierul sursă se numeşte “prog.c”, iar fişierul binar se numeşte “prog”, atunci în linia de comandă vom scrie ./prog

Sistemele de operare ne permit să transmitem parametri la programele pe care le rulăm. Pentru a transmite parametri, trebuie doar să ii înşirăm după numele programului pe care îl rulăm. Spre exemplu scriem în linia de comandă ./prog parametru1 parametru2 parametru3

Pentru a putea citi din program parametri care au fost transmişi din linia de comandă, trebuie să folosim construcţii specifice ale limbajului de programare. În limbajul C parametri din linia de comandă ajung în program ca şi argumente ale funcţiei main. Mai exact ca şi două argumente: un

prim argument de tip int care specifică numărul parametrilor transmişi, şi un al doilea parametru care este un şir de pointeri la char. Fiecare din pointerii din acest şir de pointeri indică spre un sir de caractere reprezentând unul din parametri veniţi din linia de comandă.

Un program C care afişează toţi parametri primiţi din linia de comandă este:

#include <stdio.h>

int main(int argc, char* argv[]){ int i; printf("Avem %d parametri din linia de comanda.\n\n", argc); for (i=0; i<argc; i++) printf("Parametrul %i: '%s'\n", i, argv[i]); return 0;}

Dacă salvăm programul într-un fişier “lcom.c”şi îl compilăm şi link-edităm va rezulta fişierul binar “lcom”.

Dacă deschidem un terminal şi rulăm programul fără nici un parametru, ne-am aştepta să se afişeze că avem zero parametri din linia de comandă. Vom vedea că în realitate avem un parametru. Asta deoarece întotdeauna sistemul de operare trimite automat spre program ca prim parametru din linia de comandă numele fişierului executabil care a fost rulat.

Dacă noi scriem în linia de comandă “./lcom”, rezultatul va fi:

$ ./lcomAvem 1 parametri din linia de comanda.

Parametrul 0: './lcom'

Dacă scriem câţiva parametri din linia de comandă, programul îi va afişa pe toţi. Din nou sistemul de operare va plasa pe prima poziţie numele programului care a fost rulat.

$ ./lcom unu doi trei patru cinciAvem 6 parametri din linia de comanda.

Parametrul 0: './lcom'Parametrul 1: 'unu'Parametrul 2: 'doi'Parametrul 3: 'trei'Parametrul 4: 'patru'Parametrul 5: 'cinci'

Toţi parametri care ajung la program din linia de comandă, ajung sub formă de şiruri de caractere. Chiar dacă noi dorim să trimitem numere, ele sunt transmise ca şiruri de caractere. Pentru a le folosi ca numere, trebuie să le convertim noi explicit, folosind funcţiile de conversie atoi şi atof din bilioteca <stdlib.h>.

Un exemplu de program care foloseşte parametri din linia de comandă sub formă de numere întregi este următorul:

#include <stdio.h>#include <stdlib.h>

void stelute(int n){ int i; for (i=0; i<n; i++) printf("*");}

void spatii(int n){ int i; for (i=0; i<n; i++) printf(" ");}

int main(int argc, char* argv[]){ int i, n; for (i=1; i<argc; i++) { n = atoi(argv[i]); if (i % 2 == 1) stelute(n); else spatii(n); } printf("\n"); return 0;}

Programul citeste numere care i se transmit din linia de comandă. În funcţie de aceste numere el afişează pe o linie steluţe şi spaţii. Spre exemplu dacă se transmit numerele 3, 4, 5 şi 6, programul afişează 3 steluţe, 4 spaţii, 5 steluţe şi 6 spaţii. Observaţi că s-a folosit funcţia atoi pentru a converti parametri din şir de caractere în întreg.

De regulă parametri din linie de comandă se folosesc pentru a automatiza execuţia programelor. Automatizarea execuţiei programelor se face prin script-uri care sunt rulate de sistemul de operare. Pentru Linux, asemenea script-uri se scriu sub formă de fişiere cu extensia .sh. Un script contine o secvenţă de comenzi care se doreşte să fie rulate împreună.

Dacă salvăm programul anterior într-un fişier cu numele “stelute.c”, astfel încât fişierul binar rezultat să fie “stelute”, atunci putem scrie următorul fişier tp.sh:

./stelute 7 3 5

./stelute 0 3 1 6 1 4 1

./stelute 0 3 1 6 1 5 1

./stelute 0 3 1 6 1 5 1

./stelute 0 3 1 6 1 4 1

./stelute 0 3 1 6 5

./stelute 0 3 1 6 1

./stelute 0 3 1 6 1

./stelute 0 3 1 6 1

./stelute 0 3 1 6 1

./stelute 0 3 1 6 1

Dacă rulăm acest fişier .sh, efectul va fi că se va rula în mod automat programul stelute.exe, de 11 ori, cu secvenţele de parametri specificaţi. Pe ecran vor apare literele TP (de la Tehnici de Programare):

$ ./tp.sh******* ***** * * * * * * * * * * * * * ***** * * * * * * * * * *

Probleme propuse

1. Definiţi o structură pentru memorarea următoarelor informaţii despre animale:- numărul de picioare: număr întreg, minim 0 (ex. şarpe), maxim 1000 (ex. miriapod)- greutatea în kg: număr real- periculos pentru om: da/nu- abrevierea ştiinţifică a speciei: şir de maxim 8 caractere- vârsta maximă în ani: număr întreg, minim 0, maxim 2000

Unde este posibil, codificaţi informaţiile prin numere întregi. Spre exemplu “da”=0, “nu”=1.

Definiţi structura în aşa fel încât să ocupe spaţiul minim de memorie posibil. Afişaţi spaţiul de memorie ocupat, folosind operatorul sizeof. Folosind structura definită, citiţi de la tastatură informaţii despre un animal, pe urmă afişaţi-le pe ecran.

2. Scrieţi un program care criptează sau decriptează un şir de cuvinte.

Criptarea se face după un algoritm simplu. Ştim că fiecare literă din alfabet are asociat un număr de ordine. Numerele de ordine ale tuturor caracterelor (nu doar litere) formează ceea ce se numeşte tabela de coduri ASCII. Pentru a afla numărul de ordine al unui caracter, e suficient să îl afişăm ca şi întreg. Spre exemplu:

char c = 'a';printf("Numarul de ordine al lui '%c' este %d.\n", c, c);

Pentru a cripta un anumit cuvânt, avem nevoie de un număr întreg N numit cheie de criptare. Criptarea se realizează astfel: la numărul de ordine al fiecarei litere a cuvântului se adună N şi rezultă o nouă literă. Cuvântul criptat este constituit din noile litere ce se obţin.

Spre exemplu să considerăm cuvântul “abecedar” şi cheia de criptare 1.

Literele originale

a b e c e d a r

Numerele de ordine ale literelor originale

97 98 101 99 101 100 97 114

Numerele de ordine ale literelor criptate

98 99 102 100 102 101 98 115

Literele criptate

b c f d f e b s

Incrementarea numerelor de ordine se face circular, adica litera z incrementată cu 1 devine litera a.

Operaţia de decriptare se face exact invers. Având un cuvânt şi o cheie de decriptare N, se scade din numerele de ordine ale literelor cuvântului valoarea N, obţinându-se astfel literele cuvântului decriptat.

Scrieţi un program care face operaţii de criptare şi decriptare conform algoritmului descris. Programul va primi următorii parametri din linia de comandă:– Primul parametru va fi una din valorile “enc” sau “dec”. Dacă valoarea este “enc” atunci se va face criptare, dacă este “dec” se va face decriptare. Dacă primul parametru are altă valoare, se va afişa un mesaj de eroare.– Al doilea parametru este un număr întreg reprezentând cheia N de criptare/decriptare.– Următorii parametri sunt cuvinte care trebuie criptate sau decriptate, după caz, în funcţie de valoare primului parametru. Cuvintele pot conţine atât litere mari, cât şi litere mici, dar ele vor trebui convertite la litere mici înainte de a face operaţia de criptare/decriptare.

Programul va afişa pe ecran cuvintele obţinute în urma criptării/decriptării cuvintelor trimise din linia de comandă.

Spre exemplu dacă rulăm programul cu parametri “./criptare enc 1 abecedar” programul trebuie să afişeze “bcfdfebs”. Dacă rulăm “./criptare dec 1 bcfdfebs” programul va afişa “abecedar”.

Dacă rulăm “./criptare enc 1 zaraza” programul va afişa “absbab”.

Dacă rulăm “./criptare enc 10 vine VINE primavara PRImaVAra” programul va afişa “fsxo fsxo zbswkfkbk zbswkfkbk”.