README.md 18.5 KB
Newer Older
Igor Zhirkov's avatar
Igor Zhirkov committed
1
# Assignment: Image rotation
Igor Zhirkov's avatar
Igor Zhirkov committed
2
---
Igor Zhirkov's avatar
Igor Zhirkov committed
3
Лабораторная работа: Поворот картинки
Igor Zhirkov's avatar
Igor Zhirkov committed
4

Igor Zhirkov's avatar
Igor Zhirkov committed
5 6
# Подготовка

Igor Zhirkov's avatar
Igor Zhirkov committed
7
- Прочитайте главу 12 (стр. 221, 231–239) и 13 (целиком) "Low-level programming: C, assembly and program execution". 
Igor Zhirkov's avatar
Igor Zhirkov committed
8 9 10 11 12 13 14 15 16

На защите мы можем обсуждать любые вопросы из учебника из глав 8–13 включительно.

# Структура BMP файла

BMP файл состоит из заголовка и растрового массива.
Заголовок задаётся следующей структурой (обратите внимание на атрибут `packed`):

```c
17
// Описание для gcc и clang
Igor Zhirkov's avatar
Igor Zhirkov committed
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
#include  <stdint.h>
struct bmp_header __attribute__((packed))
{
        uint16_t bfType;
        uint32_t  bfileSize;
        uint32_t bfReserved;
        uint32_t bOffBits;
        uint32_t biSize;
        uint32_t biWidth;
        uint32_t  biHeight;
        uint16_t  biPlanes;
        uint16_t biBitCount;
        uint32_t biCompression;
        uint32_t biSizeImage;
        uint32_t biXPelsPerMeter;
        uint32_t biYPelsPerMeter;
        uint32_t biClrUsed;
        uint32_t  biClrImportant;
};
```

Сразу после него (всегда ли?) идёт растровый массив, в котором последовательно хранятся пиксели по строчкам.
Каждый пиксель задаётся структурой размером 3 байта:

```c
43
   struct pixel { uint8_t b, g, r; };
Igor Zhirkov's avatar
Igor Zhirkov committed
44 45
```

46 47
## Padding

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
48 49
Если ширина изображения в байтах кратна четырём, то строчки идут одна за другой без пропусков.
Если ширина не кратна четырём, то она дополняется мусорными байтами до ближайшего числа, кратного четырём.
50
Эти байты называются *padding*.
Igor Zhirkov's avatar
Igor Zhirkov committed
51 52 53 54

Пример:

1. Изображение имеет ширину 12 пикселей = 12 * 3 байт = 36 байт. Ширина кратна четырём, каждая следующая строчка начинается сразу после предыдущей.
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
55
2. Изображение имеет ширину 5 пикселей. 5 * 3 = 15 байт, ближайшее число кратное четырём (округление вверх) это 16. После каждой строчки будет отступ в 16-15 = 1 байт перед началом следующей.
Igor Zhirkov's avatar
Igor Zhirkov committed
56

57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
Обратите внимание: отступы в *байтах*, не в пикселях.



# Пользователям компилятора от Microsoft 

Вам придётся задать структуру по-другому, без атрибута `packed`:

```c
#include  <stdint.h>
#pragma pack(push, 1)
struct bmp_header 
{
        uint16_t bfType;
        uint32_t  bfileSize;
        uint32_t bfReserved;
        uint32_t bOffBits;
        uint32_t biSize;
        uint32_t biWidth;
        uint32_t  biHeight;
        uint16_t  biPlanes;
        uint16_t biBitCount;
        uint32_t biCompression;
        uint32_t biSizeImage;
        uint32_t biXPelsPerMeter;
        uint32_t biYPelsPerMeter;
        uint32_t biClrUsed;
        uint32_t  biClrImportant;
};
#pragma pack(pop)
```

Объяснение этого прочтите находится на страницах 235&ndash;239 учебника. 

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
91

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
92
# Об архитектуре
Igor Zhirkov's avatar
Igor Zhirkov committed
93

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
94
Программа разделена на модули; каждый модуль это `.c` файл, который становится файлом с расширением `.o`.
Igor Zhirkov's avatar
Igor Zhirkov committed
95

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
Продуманная архитектура приложения в каждом конкретном модуле минимизирует
знания о других модулях по следующим причинам:

- Когда программист работает над одним модулем (разрабатывает, модифицирует,
  ищет ошибки), ему проще не держать в голове знания про всю остальную
  программу. Скрытие информации про другие модули позволяет ему не брать в 
  голову детали их внутреннего устройства.
- Пусть модуль A не использует определения из модуля B, но имеет к ним доступ.
  Разумеется, можно как угодно менять B и это не скажется на A. 
  Однако есть шанс, что автор программы или кто-то из будущих соавторов может
  использовать в модуле A определения из B &mdash; ведь к ним есть доступ.  Это
  установит жёсткую связь между A и B, и будет нельзя больше свободно менять B не
  влияя на A. Программы являются сложными системами, и мы хотим иметь минимум
  связей между их элементами, иначе модификация (и исправление ошибок) будут
  требовать постоянной модификации не одной, а многих частей программы.
Igor Zhirkov's avatar
Igor Zhirkov committed
111

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
112
В нашем случае в программе разумно выделить несколько частей.
Igor Zhirkov's avatar
Igor Zhirkov committed
113

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
114 115
## Часть 1: Внутренний формат

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
116 117
Описание внутреннего представления картинки `struct image`, очищенное от
деталей формата, и функции для работы с ним: создание, деинициализация и т.д.
118

Igor Zhirkov's avatar
Igor Zhirkov committed
119 120 121 122 123 124
   ```c
   struct image {
     uint64_t width, height;
     struct pixel* data;
   };
   ```
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
125 126 127 128 129
  
  Эта часть программы не должна знать ни про входные форматы, ни про трансформации.

## Часть 2: Входные форматы

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
130 131 132
Каждый входной формат описывается в отдельном модуле; они предоставляют функции
для считывания файлов разных форматов в `struct image` и для записи на диск в
тех же форматах.
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
133

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
134 135 136
Эти модули знают про модуль, описывающий `struct image`, но ничего не знают про
трансформации. Поэтому можно будет добавлять новые трансформации не переписывая
код для входных форматов.
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
137

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
138 139 140 141
  Как только мы считали изображение во внутренний формат, мы должны забыть, из
какого формата оно было считано!  Именно поэтому в `struct image` оставлен
только самый минимум деталей изображения (размеры), и никаких частей
bmp-заголовка.  Для BMP начать можно с:
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
142

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
143 144 145 146 147 148 149 150 151
```c
/*  deserializer   */
enum read_status  {
  READ_OK = 0,
  READ_INVALID_SIGNATURE,
  READ_INVALID_BITS,
  READ_INVALID_HEADER
  /* коды других ошибок  */
  };
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
152

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
153
enum read_status from_bmp( FILE* in, struct image* img );
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
154

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
155 156 157 158 159 160
/*  serializer   */
enum  write_status  {
  WRITE_OK = 0,
  WRITE_ERROR
  /* коды других ошибок  */
};
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
161

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
162
enum write_status to_bmp( FILE* out, struct image const* img );
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
163

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
164
```
Igor Zhirkov's avatar
Igor Zhirkov committed
165

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
Функции `from_bmp` и `to_bmp` принимают уже открытый файл, что позволяет
им работать с заранее открытыми файлами `stdin`, `stdout`, `stderr`.

Функции `from_bmp` и `to_bmp` не должны ни открывать, ни закрывать файлы.
Для ошибок открытия/закрытия, возможно, вам захочется ввести отдельные типы
перечислений.

Как только мы считали изображение во внутренний формат, мы должны забыть, из
какого формата оно было считано! Именно поэтому в `struct image` оставлен
только самый минимум деталей изображения (размеры), и никаких частей
bmp-заголовка.

Вам также потребуются функции, аналогичные `from_bmp` и `to_bmp`, которые
будут принимать имена файлов и заниматься корректным открытием (`fopen`) и
закрытием (`fclose`) файлов; на открытых файлах они могут запускать `from_bmp`
и `to_bmp`.

Имеет смысл разделять открытие/закрытие файлов и работу с ними. Уже
открытие и закрытие могут сопровождаться ошибками (см. `man fopen` и 
`man fclose`) и хочется отделить обработку ошибок открытия/закрытия и
обработку ошибок чтения/записи.
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
187 188 189 190 191



## Часть 3: Трансформации

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
192 193 194 195 196
Каждая трансформация описывается в отдельном модуле. Эти модули знают про
модуль, описывающий `struct image`, но ничего не знают про входные форматы.
Поэтому можно будет добавлять новые входные форматы не переписывая код для
трансформаций. Без дополнительных усилий мы получим возможность, описав входной
формат, сразу же поддержать все трансформации над ним.
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
197 198 199 200 201 202 203 204

Вам потребуется функция для поворота картинки в её внутреннем представлении:

   ```c
   /* создаёт копию изображения, которая повёрнута на 90 градусов */
   struct image rotate( struct image const source );
   ```
   
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
205 206
Вам может пригодиться [программа для отображения заголовков BMP файлов](https://gitlab.se.ifmo.ru/low-level-programming/bmp-header-viewer) 
**ВНИМАНИЕ** это программа для просмотра заголовков BMP файлов. Это не заготовка для решения! Можете скомпилировать её с помощью `make` и проверять заголовки на битность; в решении вам нужно поддерживать только 24-битные BMP файлы.
Igor Zhirkov's avatar
Igor Zhirkov committed
207

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
208
## Часть 4: всё остальное
Igor Zhirkov's avatar
Igor Zhirkov committed
209

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
210
Остальная часть программы может быть организована любым осмысленным способом. Возможно, вам захочется написать небольшую библиотеку для ввода-вывода, работы со строками и т.д.
Igor Zhirkov's avatar
Igor Zhirkov committed
211

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
212
Приветствуется разумное создание новых модулей и введение дополнительных функций для удобства, где это необходимо.
Igor Zhirkov's avatar
Igor Zhirkov committed
213

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
214 215 216 217
Дополнительные функции, которые вы ввели для удобства, но которые не относятся по смыслу ни к одному из этих модулей, можно выделить
в отдельный модуль. Часто его называют `util.c` или как-то похоже.

# Задание
Igor Zhirkov's avatar
Igor Zhirkov committed
218 219


Igor Zhirkov's avatar
update  
Igor Zhirkov committed
220 221
- Необходимо реализовать поворот изображения в формате BMP на 90 градусов против 
  часовой стрелки. Формат использования такой:
Igor Zhirkov's avatar
Igor Zhirkov committed
222

Igor Zhirkov's avatar
update  
Igor Zhirkov committed
223 224 225 226 227
```
./image-transformer <source-image> <transformed-image>
```

- Архитектура приложения описана в предыдущем разделе. 
Nikita Akatyev's avatar
Nikita Akatyev committed
228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267
- Код размещается в директории `solution/src`, заголовочные файлы ищутся в `solution/include`.

## Система сборки и тестирования

- Используйте команду `make` для того, чтобы собрать ваш код в исполняемый файл
  `build/image-transformer`. Проверьте, что в вашей системе установлены программа
  `make` версии как минимум 4.0 и компилятор `clang`. Флаги для компиляции берутся
  из `compile_flags.txt` &mdash; вы можете добавить свои флаги в конец
  этого файла или в саму команду `make`. Например, чтобы собрать код с оптимизациями
  и протестировать скорость выполнения, вы можете использовать `make CFLAGS=-O3`.
  С помощью `LDFLAGS` можно передать дополнительные параметры линковщику.
- Используйте `make check`, чтобы проверить вашу программу через статический анализатор
  `clang-tidy`. Список проверок описан в файле `clang-tidy-checks.txt`. Вы можете добавить
  свои проверки в конец этого файла или в параметр `CLANG_TIDY_CHECKS` для `make`.
- Вы можете собрать код с поддержкой определенных динамических анализаторов (санитайзеров).
  Санитайзеры могут дать подробную информацию о возможных и реальных ошибках в программе вместо
  классического сообщения о segmentation fault. Исполняемые файлы будут также размещены в директории `build`, но для санитайзеров выделены отдельные
  поддиректории с их названием.
  Поддерживаются следующие санитайзеры:
  - `make SANITIZER=asan` &mdash; [AddressSanitizer](https://clang.llvm.org/docs/AddressSanitizer.html),
    набор проверок на некорректное использование адресов памяти. Примеры:
    use-after-free, double-free, выход за пределы стека, кучи или статического блока.
  - `make SANITIZER=lsan` &mdash; [LeakSanitizer](https://clang.llvm.org/docs/LeakSanitizer.html),
    проверки на утечки памяти.
  - `make SANITIZER=msan` &mdash; [MemorySanitizer](https://clang.llvm.org/docs/MemorySanitizer.html),
    проверяет, что любая используемая ячейка памяти проинициализирована на момент чтения из нее.
  - `make SANITIZER=usan` &mdash; [UndefinedBehaviourSanitizer](https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html),
    набор базовых проверок на неопределенное поведение. Примеры: переполнение численного типа,
    null-pointer dereference.
  - `make SANITIZER=none` &mdash; собрать код без санитайзеров (по умолчанию).
  - `make SANITIZER=all` &mdash; собрать 5 версий кода, каждая с одной из предыдущих опций.
- Используйте `make clean` для очистки временных файлов и директории `build`.
- Директория `tester` содержит код и изображения для тестирования вашей программы. Используйте
  `make -k test`, чтобы запустить тесты и вывести отчет по их выполнению. Параметры `CFLAGS`,
  `LDFLAGS` и `SANITIZER` также могут быть переданы программам, используемым в тестах.
- Чтобы запустить конкретный тест, посмотрите его название в отчете всех тестов (оно же название
  директории с изображениями в `testers/tests`) и запустите `make -k test-<name>`. Например,
  чтобы запустить тест №1 ([изначальная картинка](testers/tests/1/input.bmp) ->
  [ожидаемый результат](testers/tests/1/output_expected.bmp)), используйте `make -k test-1`.
- Ваша программа будет тестироваться в
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
268
  [Docker-контейнере](https://gitlab.se.ifmo.ru/low-level-programming/docker-c-test-machine/),
Nikita Akatyev's avatar
Nikita Akatyev committed
269 270 271
  вы можете использовать его для тестирования вашего кода локально. В контейнере будут запущены:
  - Статический анализатор - аналогичен команде `make check`
  - Тесты с санитайзерами - аналогичен команде `make -k test SANITIZER=all`
Igor Zhirkov's avatar
Igor Zhirkov committed
272

Igor Zhirkov's avatar
Igor Zhirkov committed
273
# Для самопроверки
274

Igor Zhirkov's avatar
Fixes  
Igor Zhirkov committed
275
- Прочитайте [правила хорошего стиля](https://gitlab.se.ifmo.ru/c-language/main/-/wikis/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%B0-%D1%81%D1%82%D0%B8%D0%BB%D1%8F-%D0%BD%D0%B0%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D1%8F-%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC-%D0%BD%D0%B0-C). Ваше решение должно им соответствовать.
Igor Zhirkov's avatar
Igor Zhirkov committed
276
- Архитектура: думайте о том, как бы вы хотели организовать код, чтобы легко добавлять входные форматы (не только BMP) и трансформации (не только поворот на 90 градусов).
Igor Zhirkov's avatar
update  
Igor Zhirkov committed
277
- Пожалуйста, присылайте решение в виде pull-request. [Инструкция](https://gitlab.se.ifmo.ru/cse/main/-/wikis/%D0%9A%D0%B0%D0%BA-%D0%BF%D0%BE%D1%81%D0%BB%D0%B0%D1%82%D1%8C-%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5-%D0%BD%D0%B0-%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D1%83).