Programare: Tema 5

Problema 2 Scrieţi o funcţie care calculează câtul şi restul la împărţirea a doi întregi fără semn, calculând pe rând fiecare bit din rezultat (ca la împărţirea din şcoala primară)

Problema 3 Scrieţi o funcţie care ia ca parametri două numere întregi fără semn şi returnează rezultatul împărţirii lor, ca float, calculând succesiv fiecare bit din mantisă.

Problema 4 Scrieţi un program care calculează o sumă de control CRC (cyclic redundancy check) pentru un text, conform standardului POSIX.
Fundamentul matematic este următorul: textul e asimilat unui şir de L biţi, pentru care se calculează o sumă de control pe W biţi. Orice şir de n biţi poate fi asociat cu un polinom de grad < n, în care bitul k este coeficientul lui x la puterea k. Se ia textul, privit ca un astfel de polinom, şi se calculează restul împărţirii la un polinom prestabilit de grad W, considerând toţi coeficienţii modulo 2. De exemplu, pentru textul pe L=8 biti 10011100, adică x^7 + x^4 + x^3 + x^2 şi polinomul x^4 + x^3 + x^0 (11001, de grad W=4) obţinem:
x^7 + x^4 + x^3 + x^2 = (x^3 + x^2 + x^1)*(x^4 + x^3 + x^0) + x^1 (mod 2)
deci restul x^1 interpretat pe W=4 biţi este 0010. Împărţirea poate fi implementată prin algoritmul clasic cu deplasare şi scădere succesivă. Exprimând totul în calcule pe biţi, avem nevoie de o valoare pe W biţi în care ţinem minte restul curent. Scăderea pentru polinoame modulo 2 (identică cu adunarea) se face prin SAU exclusiv bit cu bit (nu există deplasare, fiecare bit corespunde unui coeficient separat). Dacă bitul superior (poziţia W-1) este 1, atunci în iteraţia curentă, după deplasarea la stânga şi aducerea următoarei cifre din deîmpărţit, bitul W va fi 1 şi împărţitorul (de grad W) va "intra" în rest (poate fi "scăzut" prin XOR, coeficientul în cât este 1). Dacă nu, se continuă fără scădere cu următoarea iteraţie (cifra din cât este 0). Cum ne interesează doar restul, nu trebuie să reţinem câtul; calculul se încheie când au fost consumaţi toţi biţii din deîmpărţit (textul dat).
În cazul particular al standardului POSIX, suma de control se calculează pe 32 de biţi, iar polinomul de grad 32 folosit ca împărţitor are următorii biţi pe 1 (coeficienţi): 32, 26, 23, 22, 16, 12, 11, 10, 8, 7, 5, 4, 2, 1, 0. (Asemenea polinoame se aleg pentru proprietăţile bune de detectare a erorilor). Şirul de biţi codificat e format din caracterele textului, în ordine, fiecare începând cu bitul cel mai semnificativ; apoi lungimea textului, în caractere, pe numărul minim necesar de octeţi, începând cu cel mai puţin semnificativ; apoi 32 de biţi 0 (4 caractere nule). Suma de control e restul pe 32 de biţi, negat bit cu bit (pentru că, adăugată la mesaj, permite verificarea faptului că acelaşi algoritm ar trebui să dea restul 0).
Indicaţii: Din descrierea algoritmului, rezultă că vom manipula un număr pe 32 de biţi (restul curent), de exemplu un long. Testul valorii 1 pentru bitul cel mai semnificativ trebuie făcut înainte de deplasarea la stânga, care va provoca dispariţia lui. Din acelaşi motiv, nu vom reprezenta bitul 32 al împărţitorului, calculele descrise ţinând cont implicit că acesta e 1. Împărţirea poate fi făcută pas cu pas, pe măsură ce se citesc caractere din text, însă nu poate începe până când în deîmpărţitul iniţial nu s-au acumulat 32 de biţi (4 caractere), şi e disponibil încă un caracter din care şă se "aducă" biţii următori. La sfârşitul textului, se continuă algoritmul cu octeţii reprezentând lungimea textului, şi cei 4 octeţi finali de zero (care ne asigură că deîmpărţitul va avea >= 32 de biţi chiar dacă textul e mai scurt).
Textul poate fi citit la alegere, fie până la linie nouă, fie până la sfârşit de fişier, cu un ciclu de tipul

 while ((c = getchar()) != EOF) { /* prelucreazâ c */ }