Problem Set 5: QR Code

QR Code

Скорее всего вы уже знаете, что такое QR код. На самом деле, это ничто иное как 2D массив, предназначенный на визуальную репрезентацию данных. QR (Quick Response) код был создан в Японии в 1994 коду в автопромышленности. Позже он перешёл и в другие области.

Для того, чтобы извлечь данные из QR кода, нужно использовать специальный сканер или приложение на телефоне.

В данном задании к счастью мы не будем программировать целый функционал подобного приложения, с помощью которого можно сосканировать QR код, вместо это мы рассмотрим главные принципы работы с 2D массивом.

QR код состоит из черных квадратов, помещенных сетке на белом фоне. Данная особенность позволяет таким устройствам, как камера или другим специальным устройствам, воспринимать изображение.

Для сохранения данных в QR коде используются стандартные моды, которые позволяют сохранять числа, альфанумерические символы, бинарные данные (байты), кандзи знаки. Помимо этого возможны и другие типы данных при условии использования расширений. Мы будем работать с бинарным типом данных.

Вашим заданием будет написать программу, которая бы смогла конвертировать короткий текст в байт-код, который потом будет группироваться в блоки и наоборот.

Для кодирования знаков из строки в бинарный тип используйте базовую ASCII таблицу.

Для сохранения байтов будут использоваться массивы типа bool, где 1 == true и 0 == false.

Блоки создаются из вертикально сложенных байтов. Байты сохраняются постепенно слева направо до тех пор, пока позволяет ширина блока. Только потом они сохраняются на новую "строку". Индекс новой "строки" для блока имеет offset в размере соответствующего размера байта (8 бит).

Example

Попробуем закодировать строку "Ahoj!". : 'A', 'h', 'o', 'j', '!', '\0'. Символы кодируются в формат двоичной системы (бинарной) на основе соответствующего значения символа в ASCII таблице. Нужно кодировать и символ окончания строки, поскольку данный знак также имеет соответствующее значение в таблице. Значения ранее упомянутых знаков следующие:

Именно это и будет вашим заданием: на основе ASCII значения символа высчитать значение символа в двоичном формате. Таким образом получится byte. То есть, если кодировать группу символов (строку), генерируется 2D массив, в котором на каждой строчке находится один byte.

Когда мы получим группу байтов (см. таблицу), мы можем сформировать "блоки". Блоки имеют определенное количество столбцов и "строк" (offset*8), и сформированы так, чтобы в блоки поместились все символы. Коды символов (байты) сохраняются в блоки вертикально, сначала слева направо, переходя вниз согласно offset-y. Если остались незаполненные блоки, их мы наполняем false (кодировки символа '\0').

Поскольку количество "строк" и столбцов в блоках известно заблаговременно, скажем, 2 "строки" и 3 столбца. Расставим символы нашей строки "Ahoj!" в таком порядке, в котором будут они будут сохранены в блоки.

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

Byte каждого символа будет сохранены вертикально. Таким образом, 2 "строки" (2*8) и 3 столбца для строки "Ahoj!" будут выглядеть следующим образом:

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

Если у нас 2 "строки" и 4 столбца, последовательно будет выглядеть следующе:

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

В блоках сохранены так:

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

Task 1: (Де)кодирование символа

Напишите функцию void encode_char(const char character, bool bits[8]) с двумя параметрами:

• const char character - символ, чье ASCII значение закодируется с десятичной в двоичную систему (бинарную).
• bool bits[8] - Массив значений true или false. Его длина составляет 8, поскольку каждый символ можно представить на 8 битах.

Функция не возвращает значения, но при этом наполняет массив bits значениями true или false. Поле будет содержать значение символа character в двоичной системе. При этом помните, что 1 == true и 0 == false.

Напишите функцию char decode_byte(const bool bits[8]) с параметром:

• const bool bits[8] - Массив значений true или false. Его длина составляет 8 символов, поскольку каждый символ можно закодировать на 8 битах.

Функция возвращает символ, который в ASCII таблице имеет такое же значение (в десятичной системе), которое записано в массиве bits в двоичном формате.

Functions Call Example

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

Assessment

За задание можно получить max. 3 балла (каждая функция имеет макс. 1.5 баллов).

Task 2: (Де)Кодирование строки

Напишите функцию void encode_string(const char string[], bool bytes[strlen(string)+1][8]) с двумя параметрами:

• const char string[] - Строка, которую нужно закодировать
• bool bytes[strlen(string)+1][8] - двумерный массив, у которого на каждой строке находится байт (8 битов)

Функция не возвращает никакого значения, но заполняет массив bytes значениями true или false. Массив будет содержать запись ASCII значений символов из строки string в двоичной системе включая символ окончания строки. Заметьте, 1 == true и 0 == false.

Напишите функцию void decode_bytes(const int rows, bool bytes[rows][8], char string[rows]) с тремя параметрами:

• const int rows - количество рядов массива bytes и количество символов строки string включая символ-терминатор
• bool bytes[rows][8] - Двумерный массив, который на каждой строчке содержит 1 байт (8 бит)
• char string[rows] - Строка, которую нужно создать декодируя данные из bytes

Функция не возвращает никакого значения, но наполняет string символами декодировав данные из bytes. Массив bytes содержит в себе на каждом ряду ровно 1 байт (8 битов), состоящий из значений true или false, которые представляют ASCII значение символов в двоичной системе включая символ окончания строки. Заметьте, что 1 == true и 0 == false.

Functions Call Example

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!

Assessment

За задание можно получить max. 3 балла (каждая функция имеет макс. 1.5 баллов).

Task 3: (Де)Кодирование блоков

Создайте функцию void bytes_to_blocks(const int cols, const int offset, bool blocks[offset*8][cols], const int rows, bool bytes[rows][8]) с параметрами:

• const int cols - Количество столбцов для блоков
• const int offset - Количество групп строк для блоков
• bool blocks[offset*8][cols] - Двурозмерное поле с четко установленным количеством строк и столбцов
• const int rows - Количество рядков (включая символ-терминатор)
• bool bytes[rows][8] - Двуразмерный массив с байтами кодов символов строки

Функция не возвращает никакого значения, но наполняет массив blocks кодами каждого из символов строки. Заметьте, что 1 == true и 0 == false.

Создайте фунцию void blocks_to_bytes(const int cols, const int offset, bool blocks[offset*8][cols], const int rows, bool bytes[rows][8]) с параметрами:

• const int cols - Количество столбцов для блоков
• const int offset - Количество групп строк для блоков
• bool blocks[offset*8][cols] - Двуразмерный массив для блоков с точно установленным количеством столбцов и рядков
• const int rows - Количество рядков (длина строки включая символ терминатор)
• bool bytes[rows][8] - Двуразмерный массив с байтами кодов для символов строки

Функция не возвращает никакого значения, но наполняет поле bytes кодами каждого из символов из строки. Заметьте, что 1 == true и 0 == false.

Functions Call Example

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

Assessment

За задание можно получить max. 5 баллов (каждая функция имеет макс. 2.5 баллов).

Minimal Requirements to Succeed

• Проект должен быть сдан и загружен в репозиторий git.kpi.fei.tuke.sk (см. ниже).
• Во время компиляции проекта не должна возникнуть ни одна ошибка! Проект будет собираться с помощью gcc со следующими параметрами:

gcc -std=c11 -Werror -Wall -lm 

• В вашей реализации не могут использоваться глобальные переменные.

Project Submission

Задание нужно сдать до 09.12.2024 (четверг). Последние тесты будут запущены в полночь этой даты.

Задание сдаётся с помощью системы контроля версий Git на сервере git.kpi.fei.tuke.sk.

Название вашего проекта должно быть точно в формате: zap-2024-id.

Сохраните иерархию файлов и директорий:

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

Значение отдельных файлов:

• README - файл, в котором указывается группа, которую вы посещаете на практиках, должна быть строго в формате:

GROUP : C1

• /ps5/qr.c - Код решения задания 1-3

Assessment and Testing

За целый проблем сет вы можете получить max. 11 баллов, из них max. по 3 баллу за задания номер 1 и 2, и max. по 5 баллов за задания номер 3. Любые 3 балла вам зачтутся в счёт зачёта, остальные как бонус на экзамене. Количество полученных баллов напрямую зависит от успешности тестов, которые будут выполняться над вашей программой. Проверяться в том числе будет:

• Иерархия файлов (находятся ли в репозитории все нужные файлы).
• Функционал вашей реализации.

Сборка будет осуществляться с помощью компилятора gcc со следующими параметрами:

gcc -std=c11 -Werror -Wall -lm

Ошибкой будет считаться:

• Использование глобальной переменной.
• Ошибки во время компиляции (предупреждения трактуются как ошибки).
• Если ваша реализация не пройдёт каким-то из тестов.

Тестирование проектов будет проходить каждые 3 часа, а именно: 0300, 0600, 0900, 1200, 1500, 1800, 2100 и 2400.

Проект будет проверен на плагиат. Соблюдайте этический кодекс! В случае выявления того факта, что вы сдали не ваше задание, вы рискуете быть исключенным с предмета.