Limbaje de programare: Laborator 6

Reprezentare internă. Operatori pe biţi

Temă pentru laborator

Scrieţi, pentru un număr ales în baza 16, între 0x20 şi 0xff, reprezentarea sa în baza 2 şi în baza 10.

Scrieţi, pentru câte două perechi de numere diferite pe 8 biţi, între 20 şi 255, reprezentarea lor pe biţi şi rezultatul operaţiilor ŞI, SAU, SAU exclusiv.

Scrieţi o funcţie care ia ca parametru un întreg fără semn şi returnează numărul de biţi de 1 din reprezentarea sa.

Scrieţi o funcţie care ia ca parametru un întreg fără semn şi returnează cea mai semnificativă poziţie pe care are un bit de 1.

Scrieţi o funcţie care ia ca parametru un întreg fără semn şi îl scrie în baza 8, folosind operatori pe biţi.
Indicaţie: O cifră în baza 8 ocupă 3 biţi. Restul la împărţirea cu 8 se obţine prin ŞI cu numărul format din 3 biţi de 1, adică 7. Câtul la împărţirea cu 8 se obţine prin deplasare la dreapta cu 3 biţi.

Exerciţii pentru laborator: prelucrare de imagini

Reprezentarea imaginii Folosim pentru simplitate imagini în format bitmap (.bmp) care reprezintă independent culoarea fiecărui pixel din imagine. Varietatea paletei de culori e dată de numărul de biţi utilizaţi. Vom lucra cu imagini care folosesc 24 de biţi pe pixel. Culorile sunt codificate în format RGB: câte un octet (8 biţi) pentru fiecare din cele trei culori de bază: roşu, verde şi albastru. Valoarea 0xFF (255) reprezintă intensitate maximă, iar valoarea 0 intensitate zero. Toate trei componentele la maxim dau ca rezultat alb; toate trei valorile zero înseamnă negru. Valoarea 0xFF pentru R şi zero pentru celelalte reprezintă roşu aprins; valoarea 0xFF pentru roşu şi verde, împreună cu 0 pentru albastru dă galben, etc.

Structura unui fişier imagine Un fişier cu o imagine bitmap conţine întâi un antet cu informaţii despre imagine (dimensiune, metodă de codificare, paletă de culori, etc.). Pentru formatul bitmap cu care lucrăm, antetul are 54 de octeţi. După antet urmează imaginea propriu-zisă, reprezentată în acest caz cu câte 3 octeţi pe pixel.

Citirea şi scrierea imaginilor Pentru simplitate, programele pe care le scriem vor citi şi scrie fişierele de la intrarea standard respectiv la ieşirea standard. Aceasta ne va permite să scriem în continuare programele cu funcţiile simple şi cunoscute getchar şi putchar, care citesc, respectiv scriu câte un octet (un caracter) de la intrarea / la ieşirea standard. Numele fişierelor imagine cu care lucrăm le indicăm din linia de comandă:
./programexecutabil < intrare.bmp > iesire.bmp

Structura programului Întrucât nu vom modifica dimensiunile imaginii, antetul va fi copiat neschimbat în imaginea de ieşire. Programul nostru va avea deci structura:

// copiaza 54 de caractere(octeti) cu getchar/putchar de la intrare la iesire
// cat timp nu s-a terminat intrarea
  // citeste cate un octet (sau cate trei pentru un pixel)
  // modifica octetul conform prelucrarii dorite
  // scrie octetul la iesire

De implementat (partea 1) Codificaţi în program prelucrarea indicată (resetând cei mai puţini semnificativi 4 biţi din fiecare componentă de culoare), şi observaţi efectul. Variaţi apoi numărul de biţi afectaţi (5, 3, 2, ...). Implementaţi varianta în care setaţi biţii respectivi pe 1. Efectul de pete de culoare va fi acelaşi, dar imaginea va deveni mai luminoasă.

De implementat (partea 2) Puteţi efectua şi alte prelucrări care nu ţin de codificare: să inversaţi intensitatea culorilor din imagine (negativ), să o transformaţi în nuanţe de gri (folosind uniform media aritmetică a celor trei componente), să modificaţi luminozitatea, să obţineţi diverse efecte de culoare, etc.

Opţional Veţi observa că dacă nu modificaţi decât bitul cel mai puţin semnificativ (sau ultimii doi), efectele sunt practic nedetectabile cu ochiul liber. Vom folosi această observaţie pentru a încorpora astfel în imagine date ascunse fără ca altcineva să îşi dea seama de modificare (un procedeu numit steganografie).

Informaţia transmisă va fi un şir de numere generate aleator, cu funcţia standard rand (declarată în stdlib.h). Veţi scrie un program care codifică un şir de numere aleatoare într-o imagine, şi apoi un alt program care le extrage şi le afişează.

Pentru o structură cât mai simplă a programului e util să privim informaţia de codificat ca un şir de biţi: pentru fiecare componentă de culoare a fiecărui pixel vom solicita valoarea bitului pe care dorim să-l inserăm pe ultima poziţie. Vom scrie pentru aceasta o funcţie genbit care la fiecare apel va returna câte un bit (valoarea 1 sau 0) din informaţia pe care vrem s-o codificăm (şirul de numere aleatoare).

Funcţia va avea un contor care îi va spune câti biţi mai are disponibili (de furnizat) din număr. La fiecare apel, contorul va fi decrementat; când ajunge la 0, funcţia va genera un nou număr aleator.

În limbajul C, variabilele locale sunt distruse la revenirea dintr-un apel de funcţie (au durată de memorare "automată"), deci nu se păstrează valoarea lor. Excepţie fac variabilele declarate cu specificatorul static: valoarea acestora se păstrează între două apeluri. Atât contorul cât şi numărul aleator generat vor fi declarate cu durată de memorare statică. Funcţia noastră va avea deci structura:

int genbit(void)        // returneaza urmatorul bit de codificat
{
  static int cnt = 0;   // numarul de biti disponibil, initial 0
  static int nr;        // numarul aleator generat
  if (cnt == 0) {
    nr = rand();	// genereaza un nou numar aleator
    cnt = 8 * sizeof(int); // cati biti are numarul generat
    fprintf(stderr, "%d ", nr);     // tipareste numarul si un spatiu
  }
  // extrage un bit din numar (incepand de la un capat)
  // deplaseaza numarul cu o pozitie (pregateste bitul urmator)
  // decrementeaza contorul
  // returneaza valoarea bitului extras (1 sau 0)
}

Cu această funcţie, programul păstrează mai departe aceeaşi structură simplă de mai sus, în care citeşte succesiv octeţi imaginii de la intrare, îi modifică (cu bitul obţinut cu genbit) şi îi scrie la ieşire.

Scriem un al doilea program care extrage informaţia codificată dintr-o imagine. Pentru aceasta, concepem o funcţie pereche putbit care primeşte la fiecare apel câte un bit, îi asamblează într-un număr (în acelaşi sens în care au fost obţinuţi), iar când numărul e complet, îl tipăreşte la ieşire:

void putbit(int bit)
{
  static int cnt = 8 * sizeof(int);	// cati biti mai trebuie
  static int nr = 0;	// numarul care e asamblat
  // deplaseaza numarul si insereaza bitul
  // decrementeaza contorul
  // daca contorul e zero:
    // tipareste numarul obtinut
    // reinitializeaza contorul si numarul
}

Puteţi codifica şi o imagine de aceleaşi dimensiuni în ultimii 2 sau 3 biţi inferiori ai fiecărei componente de culoare din altă imagine. Imaginea codificată va avea un număr redus de nuanţe (8 nuanţe pentru fiecare componentă de culoare, dacă folosim 3 biţi). Recreem imaginea ascunsa plasând biţii codificaţi (de ex. 101) pe poziţiile superioare (1010000). Un exemplu e dat aici.