Problem Set 5: QR Code

QR Code

Pravdepodobne ste sa už stretli s QR kódom. Je to 2D pole určené na vizuálnu reprezentáciu údajov. QR (Quick Response) kód bol vytvorený v Japonsku v roku 1994 pre automobilový premysel. Neskôr sa rozšíril aj do iných oblastí, vrátane každodenného života.

K získaniu údajov z QR kódu je potrebné použiť skener alebo mať naištalovanú aplikáciu v telefóne, ktorá túto funkcionalitu zabezpečuje.

V tomto zadaní naštastie nebudeme programovať celú funcionalitu aplikácie, ktorá skenuje QR kód, ale na tomto kóde si ukážeme základné princípy pre prácu s 2D poľom.

QR kód pozostáva z čiernych štvorcov umiestnených v mriežke, ktoré sú na bielom pozadí. To umožnuje čitateľnosť kódu pre zariadenia ako kamera alebo nejaké špeciálne skenovacie zariadenie. My sa budeme zaujímať najmä o dátovú časť tohto kódu.

Pre uchovanie dát v QR kóde sa používajú štandardné módy, ktoré umožnujú uchovať čísla, alfanumerické znaky, binárne dáta (bajty), kanji, ale aj iné, ak sú použité rozšírenia. My budeme pracovať s binárnymi údajmi.

Vašou úlohou je naprogramovať zadanie tak, aby dokázalo konvertovať krátky text do bajtov a tie následne zoskupiť do blokov a naopak.

Pre kódovanie znakov z reťazca do binárnej sústavy používajte základnú ASCII tabuľku.

Pre uchovávanie bajtov sa budú používať polia typu bool, kde 1 == true a 0 == false.

Bloky sa skladajú z vertikálne uložených bajtov. Bajty sa ukladajú postupne zľava doprava, pokiaľ to šírka bloku dovolí. Až potom sa ukladajú do nového "riadku". Index nového "riadku" pre blok má offset o veľkosti zodpovedajúcej výške bajtu (8 bitov).

Príklad

Zakódujme si reťazec "Ahoj!". Kódovať je potrebné týchto 6 znakov: 'A', 'h', 'o', 'j', '!', '\0'. Znaky kódujeme do dvojkovej (binárnej) sústavy na základe ich hodnôt v ASCII tabuľke. Kódujeme aj terminátor, pretože tento znak má tiež svoju hodnotu v ASCII tabuľke. Hodnoty týchto znakov v ASCII tabuľke sú nasledovné:

A práve to bude Vašou úlohou: Na základe ASCII hodnoty znaku vypočítať, akú hodnotu má tento znak v dvojkovej sústave. Takto vznikne byte. Takže ak kódujete skupinu znakov (reťazec), generujete dvojrozmerné pole, v ktorom sa na každom riadku nachádza jeden byte.

Keď získame skupinu bajtov (viď. tabuľka), môžeme vytvoriť "bloky". Bloky majú definovaný počet stĺpcov aj "riadkov" (offset*8), a je stanovený tak, aby sa do blokov zmestili všetky znaky. Kódy znakov (bajty) sú do blokov ukladané vertikálne, najskôr zľava doprava, potom sa podľa offset-u presunieme nižšie a opäť ukladáme bajty vertikálne, zľava doprava. Ak sú k dispozícii bloky navyše, ukladáme do nich false (kódy znaku '\0').

Keďže počet "riadkov" aj stĺpcov v blokoch je dopredu definovaný, povedzme, že budeme mať 2 "riadky" a 3 stĺpce. Usporiadajme si znaky nášho reťazca "Ahoj!" v takom poradí, v akom budú ukladané do blokov:

'A'  'h'  'o'
'j'  '!' '\0'

Byte každého znaku je uložený vertikálne. Takže pre 2 "riadky" (2*8) a 3 stĺpce bude reťazec "Ahoj!" uložený do blokov nasledovne:

0    0    0
1    1    1
0    1    1
0    0    0
0    1    1
0    0    1
0    0    1
1    0    1

0    0    0
1    0    0
1    1    0
0    0    0
1    0    0
0    0    0
1    0    0
0    1    0

Pre 2 "riadky" a 4 stĺpce bude poradie znakov nasledovné:

'A'  'h'  'o'  'j'
'!'  '\0' '\0' '\0'

A v blokoch budú uložené nasledovne:

0    0    0    0
1    1    1    1
0    1    1    1
0    0    0    0
0    1    1    1
0    0    1    0
0    0    1    1
1    0    1    0

0    0    0    0
0    0    0    0
1    0    0    0
0    0    0    0
0    0    0    0
0    0    0    0
0    0    0    0
1    0    0    0

Úloha 1: (De)Kódovanie znaku

Vytvorte funkciu void encode_char(const char character, bool bits[8]) s dvoma parametrami:

• const char character - Znak, ktorého ASCII hodnota sa zakóduje z desiatkovej do dvojkovej (binárnej) sústavy
• bool bits[8] - Pole hodnôt true alebo false. Jeho veľkosť je 8, lebo každý znak je možné zakódovať na 8 bitov.

Funkcia nevráti žiadnu hodnotu, ale naplní pole bits hodnotami true alebo false. Pole bude obsahovať zápis ASCII hodnoty znaku character v dvojkovej sústave. Platí, že 1 == true a 0 == false.

Vytvorte funkciu char decode_byte(const bool bits[8]) s parametrom:

• const bool bits[8] - Pole hodnôt true alebo false. Jeho veľkosť je 8, lebo každý znak je možné zakódovať na 8 bitov.

Funkcia vráti znak, ktorý je v ASCII tabuľke zapísaný pod rovnakou hodnotou (v desiatkovej sústave), aká je zapísaná v poli bits v dvojkovej sústave.

Príklad použitia funkcií

bool bits1[8];
encode_char('A', bits1);
for(int i = 0; i < 8; i++){
    printf("%d", bits1[i]);
}
printf("\n");
// prints: 01000001

bool bits2[8] = {0,1,0,0,0,0,0,1};
printf("%c\n", decode_byte(bits2));
// prints: A

Hodnotenie

Táto úloha je za max. 3 body (každá funkcia je za max. 1.5 bodov).

Úloha 2: (De)Kódovanie reťazca

Vytvorte funkciu void encode_string(const char string[], bool bytes[strlen(string)+1][8]) s dvoma parametrami:

• const char string[] - Reťazec, ktorý je potrebné zakódovať na bajty
• bool bytes[strlen(string)+1][8] - Dvojrozmerné pole, ktoré na každom riadku obsahuje 1 bajt (8 bitov)

Funkcia nevráti žiadnu hodnotu, ale naplní pole bytes hodnotami true alebo false. Pole bude obsahovať zápis ASCII hodnôt znakov z reťazca string v dvojkovej sústave vrátane terminátora. Platí, že 1 == true a 0 == false.

Vytvorte funkciu void decode_bytes(const int rows, bool bytes[rows][8], char string[rows]) s troma parametrami:

• const int rows - Počet riadkov poľa bytes a počet znakov reťazca string vrátane terminátora
• bool bytes[rows][8] - Dvojrozmerné pole, ktoré na každom riadku obsahuje 1 bajt (8 bitov)
• char string[rows] - Reťazec, ktorý je potrebné vytvoriť dekódovaním údajov poľa bytes

Funkcia nevráti žiadnu hodnotu, ale naplní reťazec string znakmi dekódovaním údajov v poli bytes. Pole bytes obsahuje na každom riadku 1 bajt (8 bitov) s hodnotami true alebo false, čo vyjadruje ASCII hodnotu znakov v dvojkovej sústave vrátane terminátora. Platí, že 1 == true a 0 == false.

Príklad použitia funkcií

char* text = "Hello, how are you?";
const int len = strlen(text);
bool bytes1[len+1][8];
encode_string(text, bytes1);
for(int j = 0; j <= len; j++){
    printf("%c: ", text[j]);
    for(int i = 0; i < 8; i++){
        printf("%d", bytes1[j][i]);
    }
    printf("\n");
}
// prints:
// H: 01001000
// e: 01100101
// l: 01101100
// l: 01101100
// o: 01101111
// ,: 00101100
//  : 00100000
// h: 01101000
// o: 01101111
// w: 01110111
//  : 00100000
// a: 01100001
// r: 01110010
// e: 01100101
//  : 00100000
// y: 01111001
// o: 01101111
// u: 01110101
// ?: 00111111
// : 00000000

bool bytes2[7][8] = {
    {0,1,0,0,1,0,0,0},
    {0,1,1,0,0,1,0,1},
    {0,1,1,0,1,1,0,0},
    {0,1,1,0,1,1,0,0},
    {0,1,1,0,1,1,1,1},
    {0,0,1,0,0,0,0,1},
    {0,0,0,0,0,0,0,0}
};
char string[7];
decode_bytes(7, bytes2, string);
printf("%s\n", string);
// prints: Hello!

Hodnotenie

Táto úloha je za max. 3 body (každá funkcia je za max. 1.5 bodov).

Úloha 3: (De)Kódovanie blokov

Vytvorte funkciu void bytes_to_blocks(const int cols, const int offset, bool blocks[offset*8][cols], const int rows, bool bytes[rows][8]) s parametrami:

• const int cols - Počet stĺpcov pre bloky
• const int offset - Počet skupín riadkov pre bloky (upravuje počet riadkov pre bloky)
• bool blocks[offset*8][cols] - Dvojrozmerné pole pre bloky s presne definovaným počtom stĺpcov a riadkov
• const int rows - Počet riadkov (dĺžka reťazca vrátane terminátora)
• bool bytes[rows][8] - Dvojrozmerné pole s bajtami kódov pre znaky reťazca

Funkcia nevráti žiadnu hodnotu, ale naplní pole blocks blokmi bajtov, ktoré obsahujú kódy jednotlivých znakov reťazca. Platí, že 1 == true a 0 == false.

Vytvorte funkciu void blocks_to_bytes(const int cols, const int offset, bool blocks[offset*8][cols], const int rows, bool bytes[rows][8]) s parametrami:

• const int cols - Počet stĺpcov pre bloky
• const int offset - Počet skupín riadkov pre bloky (upravuje počet riadkov pre bloky)
• bool blocks[offset*8][cols] - Dvojrozmerné pole pre bloky s presne definovaným počtom stĺpcov a riadkov
• const int rows - Počet riadkov (dĺžka reťazca vrátane terminátora)
• bool bytes[rows][8] - Dvojrozmerné pole s bajtami kódov pre znaky reťazca

Funkcia nevráti žiadnu hodnotu, ale naplní pole bytes kódmi jednotlivých znakov reťazca. Platí, že 1 == true a 0 == false.

Príklad použitia funkcií

int length = 4+1, cols = 3, offset = 2;
bool bytes1[4+1][8] = {
    {0,1,0,0,0,0,0,1},
    {0,1,1,0,1,0,0,0},
    {0,1,1,0,1,1,1,1},
    {0,1,1,0,1,0,1,0},
    {0,0,0,0,0,0,0,0}
};
bool blocks1[offset*8][cols];
bytes_to_blocks(cols, offset, blocks1, length, bytes1);
for(int j = 0; j < offset*8; j++){
    for(int i = 0; i < cols; i++){
        printf("%d ", (blocks1[j][i] == true) ? 1 : 0);
    }
    printf("\n");
    if(j % 8 == 7){
        printf("\n");
    }
}
// prints:
// 0 0 0 
// 1 1 1 
// 0 1 1 
// 0 0 0 
// 0 1 1 
// 0 0 1 
// 0 0 1 
// 1 0 1 
// 
// 0 0 0 
// 1 0 0 
// 1 0 0 
// 0 0 0 
// 1 0 0 
// 0 0 0 
// 1 0 0 
// 0 0 0

bool blocks2[2*8][3] = {
    {0,0,0},
    {1,1,1},
    {0,1,1},
    {0,0,0},
    {0,1,1},
    {0,0,1},
    {0,0,1},
    {1,0,1},
    {0,0,0},
    {1,0,0},
    {1,0,0},
    {0,0,0},
    {1,0,0},
    {0,0,0},
    {1,0,0},
    {0,0,0}
};
bool bytes2[length][8];
blocks_to_bytes(3, 2, blocks2, length, bytes2);
for(int j = 0; j < length; j++){
    for(int i = 0; i < 8; i++){
        printf("%d", bytes2[j][i]);
    }
    printf("\n");
}
// prints:
// 01000001
// 01101000
// 01101111
// 01101010
// 00000000

Hodnotenie

Táto úloha je za max. 5 bodov (každá funkcia je za max. 2.5 bodov).

Požiadavky pre úspešné odovzdanie zadania

• Projekt musí byť odovzdaný včas v git repozitári na adrese git.kpi.fei.tuke.sk (viď nižšie).
• Počas prekladu nemôže dôjsť ku žiadnej chybe! Projekt sa bude prekladať prekladačom gcc pomocou nasledovných prepínačov:

gcc -std=c11 -Werror -Wall -lm 

• Vo výslednej implementácii sa nemôže nachádzať žiadna globálna premenná.

Odovzdávanie projektu

Zadanie odovzdajte do 12.12.2024 (piatok). Posledné testovanie prebehne v tento deň o polnoci.

Zadanie sa odovzdáva prostredníctvom systému na správu verzií Git na serveri git.kpi.fei.tuke.sk.

Názov Vášho projektu musí byť v tvare: zap-2024-id.

Projekt musí mať nasledujúcu štruktúru priečinkov a súborov:

.
├── ps5
│   └── qr.c
└── README

Význam jednotlivých súborov je nasledovný:

• README - Súbor, v ktorom bude uvedená Vaša skupina, ktorú navštevujete na cvičeniach:

GROUP : C1

• /ps5/qr.c - Zdrojový kód pre riešenia úloh 1-3

Hodnotenie a testovanie

Za zadanie môžete získať max. 11 bodov, z toho max. 3 body za úlohy č. 1 a 2, a max. 5 bodov za úlohu č. 3. Ľubovoľné 3 body sa započítajú do zápočtu, ostatné body sa započítajú do skúšky. Počet získaných bodov sa bude odrážať od výsledku testov, ktorými Vaše zadanie úspešne prejde. Overovať sa bude:

• Štruktúra Vášho projektu (či sa v ňom nachádzajú všetky potrebné súbory).
• Funkčnosť Vašej implementácie.

Váš kód sa bude prekladať prekladačom gcc s nasledovnými prepínačmi:

gcc -std=c11 -Werror -Wall -lm

Za chybu sa bude považovať:

• Ak vo Vašej implementácii použijete globálnu premennú.
• Ak počas prekladu dôjde ku chybe (upozornenia sú priamo konvertované na chyby).
• Ak Vaša implementácia neprejde niektorým z testov.

Testovanie Vašich riešení sa bude vykonávať automaticky každé 2 hodiny a to konkrétne o 0000, 0200, 0400, 0600, 0800, 1000, 1200, 1400, 1600, 1800, 2000 a 2200.

Vaše riešenia prejdú kontrolou originality. Preto sa pri práci na Vašom zadaní správajte podľa pravidiel etického kódexu! V prípade, že odovzdáte zadanie, ktoré nie je Vaše, môžete byť vylúčení z predmetu!