Тестовое задание для программиста в Trickster Games

7 апреля 2015 107 #c++#trickster games

Давным-давно, в далеком 2007 году, я работал в славной компании «Trickster Games». Сейчас ее уже нет, но она была известна как разработчик игр для детей и квеста «Петрович и все, все, все..».

Так вот, в те далекие времена мы придумали тестовое задание для программиста:

#include "SomeStream.h"

void main()
{
    SomeStream stream;
    stream.info() << "Привет, мир!";
}

Задача: реализовать класс SomeStream таким образом, чтобы после выполнения main() в std::cout было выведено «Привет, мир!\n» (без кавычек). То есть добавить перевод строки в конец фразы.

Тогда никто из кандидатов не смог его решить. Может вам повезет? (:

Вот вам подсказка: крутая система логирования.

Использование библиотеки FreeType для растеризации символов

16 марта 2015 2.0K #c++#freetype #рекомендую

Всем поклонникам OpenSource приложений известна библиотека растеризации шрифтов FreeType. Её используют практически все графические приложения под GNU/Linux. Давайте освоим эту библиотеку.

Основные объекты FreeType:

FT_Library — основной объект библиотеки, который нужно инициализировать перед работой
FT_Face — представляет загруженный шрифт со всеми его характеристиками, который загружается с помощью FT_Library
FT_Glyph — глиф шрифта, который создается при помощи FT_Face

Таким образом, для отображения символа нам надо создать объект типа FT_Library, затем загрузить шрифт в объект типа FT_Face, после этого рисовать символы при помощи FT_Glyph.

Символ из шрифта можно извлечь двумя способами:

Получить информацию для его рисования кривыми
Получить готовое изображение

Первый способ нам неинтересен, будем использовать сразу второй. Поехали (проверка ошибок убрана для упрощения кода):

#include <ft2build.h>
#include FT_FREETYPE_H

int main()
{
    // Библиотека FreeType
    FT_Library library = 0;

    // Инициализация библиотеки
    FT_Init_FreeType(&library);

    // Шрифт
    FT_Face face = 0;

    // Загрузка шрифта
    FT_New_Face(library, "tahoma.ttf", 0, &face);

    // Установка размера пикселя
    FT_Set_Pixel_Sizes(face, 24, 12);

    // Код символа (юникод)
    const FT_ULong charCode = L'W';

    // Загрузка глифа из шрифта с его отрисовкой
    FT_Load_Char(face, charCode, FT_LOAD_RENDER);

    // Получение готового к использованию глифа
    FT_GlyphSlot glyph = face->glyph;

    // Получение размеров глифа
    const int width = glyph->bitmap.width;
    const int height = glyph->bitmap.rows;
    const int pitch = glyph->bitmap.pitch;

    // Вывод символа в консоли
    for (int y = 0; y < height; ++y)
    {
        for (int x = 0; x < width; ++x)
        {
            // Получение прозрачности точки (x, y)
            const int a = glyph->bitmap.buffer[y * pitch + x];

            if (a > 127)
            {
                printf("*");
            }
            else
            {
                printf(" ");
            }
        }
        printf("\n");
    }

    // Удаление шрифта
    FT_Done_Face(face);
    face = 0;

    // Удаление библиотеки
    FT_Done_FreeType(library);
    library = 0;
}

Консоль:

**        ***      ***
 **      ****      **
 **      ****     ***
  **    **  **    **
  **    *   **   ***
   **  **    **  **
   **  *      * ***
    ****      ****
    ***        ***

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

положение горизонтальной базовой линии (например, «W» — внизу, «y» — примерно середина высоты)
межстрочный интервал (если вы хотите вывести многострочный текст)
кернинг (расстояние между различными буквами)

Эти параметры доступны через структуру FT_Face. Подробнее о работе с текстом — в следующей части!

Выводим текст в OpenGL/ES 2.0

13 марта 2015 870 #freetype #opengl

Перед каждый разработчиком, если он пишет приложение графическое на своём движке, рано или поздно встаёт вопрос: каким образом вывести текст. Напомню, что OpenGL/ES умеет только рисовать треугольники и накладывать на них текстуру.

Существуют три основных подхода:

Готовые текстовые битмапы

Все надписи, которые встречаются в игре, рисуются заранее в текстуру. Такой вариант самый быстрый и простой в реализации для программиста. Фактически, вам надо взять текстуру и ее нарисовать (надеюсь вы это уже умеете).
Даёт полный простор для творчества, можно рисовать любую надпись, любым стилем и цветом.
Для оптимизации можно все надписи поместить в одну текстуру и рисовать все надписи на экране в один проход. При локализации необходимо рисовать другую текстуру с переведенным текстом.

Плюсы:

Максимальная производительность
Полная свобода дизайна (любые стили и эффекты)
Всю работу делает художник/дизайнер

Минусы:

Медленная локализация
Большой расход памяти
Нельзя динамически менять текст

Текстура с символами (текстурный атлас)

Для реализации этого способа необходимо заранее сгенерировать текстурный атлас с каждым символом из шрифта.
Самый медленный в реализации способ из предложенных, зато каждый символ может быть нарисован в любом стиле. Но помните, что для каждого языка придётся заново рисовать каждый символ в выбранном вами стиле.

Плюсы:

Относительно высокая производительность
Быстрая локализация (сгенерировать новую текстуру для языка)
Шрифт в любом стиле
Динамическое изменение надписи

Минусы:

Необходимо написать генератор этих текстур
Для разных языков нужны разные атласы
Локализация увеличивает размер приложения

Динамическая генерация из файла шрифта

Фактически этот вариант представляет собой второй способ, но вместо текстуры с символами, используется файл шрифта (например ttf), где все эти символы описаны в векторном формате. В этом случае вместо мегабайтных текстур вам необходимо хранить один файл шрифта размером в десятки, максимум сотни, килобайт.

Текстуру можно создавать двумя способами: заполнить её всеми используемыми символами (26 — латинский алфавит, 33 — кириллица) или добавлять символ только тогда, когда он понадобится. Уже сложившейся традицией для генерации символа из шрифта является использование библиотеки FreeType.

Плюсы:

Минимальный расход памяти (один файл шрифта)
Простая локализация
Полная динамичность текста
Поддержка всех языков

Минусы:

Требует больше CPU при первом использовании символов
Ограниченный стиль (зависит от шрифта)
Сложная реализация

Подробнее о работе с FreeType (+ практический пример) читайте в моём следующем посте: «Использование библиотеки FreeType для растеризации символов».

Запись ZIP файла

11 июня 2014 964 #c++#zip #zlib #полезная статья

Запись ZIP файла практически операция чтения наоборот:

для каждого файла в архиве необходимо записать LocalFileHeader, затем содержимое файла, предварительно посчитав контрольную сумму
для каждой записи LocalFileHeader, записываем CentralDirectoryFileHeader
записываем EOCD

Теперь подробнее по пунктам

Запись Local File Header

Для каждого файла в архиве существуют две записи — это LocalFileHeader и CentralDirectoryFileHeader. При записи необходимо создавать эти структуры одновременно, только LocalFileHeader записывать сразу, а для CentralDirectoryFileHeader сохранять информацию во временный список для использования ее потом. Также для данных необходимо посчитать контрольную сумму с помощью функции crc32(), которую предоставляет библиотека zlib.

Пример кода

struct LocalFileHeader
{
    uint16_t versionToExtract;
    uint16_t generalPurposeBitFlag;
    uint16_t compressionMethod;
    uint16_t modificationTime;
    uint16_t modificationDate;
    uint32_t crc32;
    uint32_t compressedSize;
    uint32_t uncompressedSize;
    uint16_t filenameLength;
    uint16_t extraFieldLength;
 
} __attribute__((packed));

struct FileInfo
{
    uint32_t compressedSize;
    uint32_t uncompressedSize;
    uint16_t compressionMethod;
    uint32_t crc32;
    uint32_t offset;
};

// Буфер для чтения
std::vector<uint8_t> readBuffer;
// Буфер для сжатых данных
std::vector<uint8_t> dataBuffer;
// Информация для создания Central directory file header
std::vector<FileInfo> fileInfoList;
// Список файлов
std::vector<std::string> filenames;
 
for (size_t i = 0; i < filenames.size(); ++i)
{
    const std::string filename = filenames[i];
 
    // Открываем файл для чтения
    std::ifstream f(filename.c_str(), std::ios::binary | std::ios::in);
 
    // Структура типа Local File Header
    LocalFileHeader lfh;
    memset(&lfh, 0, sizeof(lfh));
 
    // Узнаем размер файла
    f.seekg(0, f.end);
    lfh.uncompressedSize = f.tellg();
    f.seekg(0, f.beg);
 
    // Считаем весь файл целиком в readBuffer
    readBuffer.resize(lfh.uncompressedSize);
    f.read((char *) readBuffer.data(), lfh.uncompressedSize);
 
    // Считаем контрольную сумму
    lfh.crc32 = crc32(0, readBuffer.data(), lfh.uncompressedSize);
 
    // Выделим память для сжатых данных
    dataBuffer.resize(lfh.uncompressedSize);
 
    // Структура для сжатия данных
    z_stream zStream;
    memset(&zStream, 0, sizeof(zStream));
    deflateInit2(
        &zStream, 
        Z_BEST_SPEED,
        Z_DEFLATED,
        -MAX_WBITS,
        8,
        Z_DEFAULT_STRATEGY);
 
    // Сжимаем данные
    zStream.avail_in = lfh.uncompressedSize;
    zStream.next_in = readBuffer.data();
    zStream.avail_out = lfh.uncompressedSize;
    zStream.next_out = dataBuffer.data();
    deflate(&zStream, Z_FINISH);
 
    // Размер сжатых данных
    lfh.compressedSize = zStream.total_out;
    lfh.compressionMethod = Z_DEFLATED;
 
    // Очистка
    deflateEnd(&zStream);
 
    // Длина имени файла
    lfh.filenameLength = filename.size();
 
    // Сохраним смещение к записи Local File Header внутри архива
    const uint32_t lfhOffset = os.tellp();
 
    // Запишем сигнатуру Local File Header
    const uint32_t signature = 0x04034b50;
    os.write((char *) &signature, sizeof(signature));
 
    // Запишем Local File Header
    os.write((char *) &lfh, sizeof(lfh));
    // Запишем имя файла
    os.write(filename.c_str(), filename.size());
    // Запишем данные
    os.write((char *) dataBuffer.data(), lfh.compressedSize);
 
    // Сохраним все данные для Central directory file header
    FileInfo fileInfo;
    fileInfo.compressedSize = lfh.compressedSize;
    fileInfo.uncompressedSize = lfh.uncompressedSize;
    fileInfo.compressionMethod = lfh.compressionMethod;
    fileInfo.crc32 = lfh.crc32;
    fileInfo.offset = lfhOffset;
    fileInfoList.push_back(fileInfo);
}

Запись Central directory file header

Используя данные, полученные на предыдущем шаге, записываем для каждого файла структуру типа CentralDirectoryFileHeader. Предварительно необходимо сохранить смещение в файле для финальной записи EOCD.

Пример кода

struct CentralDirectoryFileHeader
{
    uint16_t versionMadeBy;
    uint16_t versionToExtract;
    uint16_t generalPurposeBitFlag;
    uint16_t compressionMethod;
    uint16_t modificationTime;
    uint16_t modificationDate;
    uint32_t crc32;
    uint32_t compressedSize;
    uint32_t uncompressedSize;
    uint16_t filenameLength;
    uint16_t extraFieldLength;
    uint16_t fileCommentLength;
    uint16_t diskNumber;
    uint16_t internalFileAttributes;
    uint32_t externalFileAttributes;
    uint32_t localFileHeaderOffset;
 
} __attribute__((packed));

// Смещение первой записи для EOCD    
const uint32_t firstOffsetCDFH = os.tellp();

for (int i = 0; i < filenames.size(); ++i)
{
    const std::string &filename = filenames[i];
    const FileInfo &fileInfo = fileInfoList[i];
    CentralDirectoryFileHeader cdfh;
    memset(&cdfh, 0, sizeof(cdfh));

    cdfh.compressedSize = fileInfo.compressedSize;
    cdfh.uncompressedSize = fileInfo.uncompressedSize;
    cdfh.compressionMethod = fileInfo.compressionMethod;
    cdfh.crc32 = fileInfo.crc32;
    cdfh.localFileHeaderOffset = fileInfo.offset;
    cdfh.filenameLength = filename.size();

    // Запишем сигнатуру
    const uint32_t signature = 0x02014b50;
    os.write((char *) &signature, sizeof(signature));

    // Запишем структуру
    os.write((char *) &cdfh, sizeof(cdfh));

    // Имя файла
    os.write(filename.c_str(), cdfh.filenameLength);
}

// Посчитаем размер данных для следующего шага
const uint32_t lastOffsetCDFH = os.tellp();

Запись EOCD

Самый простой этап — сформировать и записать структуру типа EOCD.

Пример кода

EOCD eocd;
memset(&eocd, 0, sizeof(eocd));
eocd.centralDirectoryOffset = firstOffsetCDFH;
eocd.numberCentralDirectoryRecord = filenames.size();
eocd.totalCentralDirectoryRecord = filenames.size();
eocd.sizeOfCentralDirectory = lastOffsetCDFH - firstOffsetCDFH;

// Пишем сигнатуру
const uint32_t signature = 0x06054b50;
os.write((char *) &signature, sizeof(signature));

// Пишем EOCD
os.write((char *) &eocd, sizeof(eocd));

Замечания по коду:

ничего не раскрыто по поводу структуру DataDescriptor (ни разу не сталкивался)
иногда размер сжатых данных превышает размер несжатых, поэтому выделяйте память по науке (смотри документацию zlib)
если размер данных очень большой, то придется воспользоваться структурой DataDescriptor

Чтение ZIP файла

4 июня 2014 2.1K #c++#zip #zlib #полезная статья

Алгоритм получения данных из ZIP файла:

находим запись EOCD
загружаем записи CentralDirectoryFileHeader
для каждой CentralDirectoryFileHeader, находим и загружаем LocalFileHeader
данные располагаются сразу после LocalFileHeader, иногда размер данных записывается после самих данных в структуру DataDescriptor, об этом сигнализирует флаг generalPurposeBitFlag

Теперь каждый шаг подробнее.

Находим запись EOCD

Эта запись располагается в конце файла. Ее поиск производится от конца файла к началу по сигнатуре. Стартовое место поиска равно размеру файла минус размер структуры EOCD. Если сигнатура не найдена, то смещаемся к началу файла по одному байту за раз.

Пример кода

struct EOCD 
{
    uint16_t diskNumber;
    uint16_t startDiskNumber;
    uint16_t numberCentralDirectoryRecord;
    uint16_t totalCentralDirectoryRecord;
    uint32_t sizeOfCentralDirectory;
    uint32_t centralDirectoryOffset;
    uint16_t commentLength;

} __attribute__((packed));

// Вычисляем размер файла
is.seekg(0, is.end);
const size_t fileSize = is.tellg();

// Ищем сигнатуру EOCD
for (size_t offset = fileSize - sizeof(EOCD); offset != 0; --offset)
{
    uint32_t signature = 0;

    // Считываем четыре байта сигнатуры
    is.seekg(offset, is.beg);
    is.read((char *) &signature, sizeof(signature));

    if (0x06054b50 == signature)
    {
        // Есть контакт!
        break;
    }
}

EOCD eocd;
is.read((char *) &eocd, sizeof(eocd));

// Считываем комментарий, если есть
if (eocd.commentLength)
{
    // Длина комментария
    uint8_t *comment = new uint8_t[eocd.commentLength + 1];
    is.read((char *) comment, eocd.commentLength);

    // Выведем комментарий в консоль
    comment[eocd.commentLength] = 0;
    std::cout << comment;

    delete [] comment;
}

Загружаем записи Central directory file header

Смещение для поиска первой записи Central directory file header находится в EOCD, который мы загрузили на предыдущем шаге. Записи располагаются последовательно одна за другой. Загрузка происходит следующим образом: считываем поля, размер которых известен, затем загружаем остальные поля (filename, extraField, fileComment).

Пример кода

struct CentralDirectoryFileHeader
{
    uint32_t signature;
    uint16_t versionMadeBy;
    uint16_t versionToExtract;
    uint16_t generalPurposeBitFlag;
    uint16_t compressionMethod;
    uint16_t modificationTime;
    uint16_t modificationDate;
    uint32_t crc32;
    uint32_t compressedSize;
    uint32_t uncompressedSize;
    uint16_t filenameLength;
    uint16_t extraFieldLength;
    uint16_t fileCommentLength;
    uint16_t diskNumber;
    uint16_t internalFileAttributes;
    uint32_t externalFileAttributes;
    uint32_t localFileHeaderOffset;

} __attribute__((packed));

// Смещение первой записи
is.seekg(eocd.centralDirectoryOffset, is.beg);

for (uint16_t i = 0; i < eocd.numberCentralDirectoryRecord; ++i)
{
    CentralDirectoryFileHeader cdfh;

    is.read((char *) &cdfh, sizeof(cdfh));

    if (0x02014b50 != cdfh.signature)
    {
        // Ошибка
        break;
    }

    // Считываем имя файла/папки
    if (cdfh.filenameLength)
    {
        uint8_t *filename = new uint8_t[cdfh.filenameLength + 1];
        is.read((char *) filename, cdfh.filenameLength);
 
        filename[cdfh.filenameLength] = 0;
        std::cout << filename << "\n";
 
        delete [] filename;
    }

    // Пропускаем дополнительные поля
    if (cdfh.extraFieldLength)
    {
        is.seekg(cdfh.extraFieldLength, is.cur);
    }
 
    // Пропускаем комментарий
    if (cdfh.fileCommentLength)
    {
        is.seekg(cdfh.fileCommentLength, is.cur);
    }

}

Загружаем записи Local File Header

Для каждой записи типа CentralDirectoryFileHeader существует запись типа Local File Header. Ее расположение в файле описывается полем CentralDirectoryFileHeader.localFileHeaderOffset. Переходим по смещению, считываем поля известной длины, затем остальные поля (filename, extraField).

Пример кода

struct LocalFileHeader
{
    uint32_t signature;
    uint16_t versionToExtract;
    uint16_t generalPurposeBitFlag;
    uint16_t compressionMethod;
    uint16_t modificationTime;
    uint16_t modificationDate;
    uint32_t crc32;
    uint32_t compressedSize;
    uint32_t uncompressedSize;
    uint16_t filenameLength;
    uint16_t extraFieldLength;

} __attribute__((packed));

// Переходим к началу записи
is.seekg(cdfh.localFileHeaderOffset, is.beg);

// Считываем ее целиком
LocalFileHeader lfh;
is.read((char *) &lfh, sizeof(lfh));

if (0x04034b50 != lfh.signature)
{
    // Ошибка
    break;
}

// Пропускаем название файла
is.seekg(lfh.filenameLength, is.cur);
// Пропускаем дополнительную информацию
is.seekg(lfh.extraFieldLength, is.cur);

Загружаем данные

Для этого шага нам понадобится библиотека zlib, потому что данные сжимаются методом deflate. Как правило, сразу после LocalFileHeader идут данные размером compressedSize. Если данные сжаты, то флаг compressionMethod равен 8 (или Z_DEFLATED), иначе он нулевой (или Z_STORED). Сжатые данные необходимо считать во временный буфер размером compressedSize и распаковать с помощью библиотеки zlib в буфер размером uncompressedSize.

// Выделяем буфер для чтения данных
uint8_t *readBuffer = new uint8_t[lfh.compressedSize];
// Считываем данные в буфер
is.read((char *) readBuffer, lfh.compressedSize);

// Если сжатие не применяется
if (0 == lfh.compressionMethod)
{
    // То необходимые данные уже лежат в буфере для чтения
}
// Данные сжаты методом deflate
else if (Z_DEFLATED == lfh.compressionMethod)
{
    // Выделяем буфер для распакованных данных
    uint8_t *result = new uint8_t[lfh.uncompressedSize];

    // Инициализация структуры для распаковки
    z_stream zs;
    memset(&zs, 0, sizeof(zs));
    inflateInit2(&zs, -MAX_WBITS);

    // Размер входного буфера
    zs.avail_in = lfh.compressedSize;
    // Входной буфер
    zs.next_in = readBuffer;
    // Размер выходного буфера
    zs.avail_out = lfh.uncompressedSize;
    // Выходной буфер
    zs.next_out = result;

    // Распаковка
    inflate(&zs, Z_FINISH);

    // Очищаем структуру для распаковки
    inflateEnd(&zs);

    // Удаляем буфер для распакованных данных
    delete [] result;
}
// Удаляем буфер для чтения
delete [] readBuffer;

Общие комментарии по коду

странная конструкция __attribute__((packed)) всего лишь означает команду для GCC не использовать выравнивание внутри структуры, для Visual Studio читайте про #pragma push(pack/pop)
обратите внимание, что поток типа z_stream инициализируется с помощью функции inflateInit2(). Это сделано потому, что стандартная функция inflateInit() ожидает в начале потока данных специальный заголовок, который отсутствует в ZIP файле
is — это объект типа std::istream (например std::ifstream)
не стоит выделять буфер для чтения каждый раз, лучше вычислить его заранее и выделить один раз в начале программы
проверьте метод сжатия перед чтением данных, тогда при отсутствии сжатия, можно читать данные сразу в нужный буфер
если размер файла внутри ZIP архива неизвестен и может быть очень большим, то распаковывайте его частями
структуру типа z_stream можно инициализировать и удалять только один раз, а перед работой с ней вызвать функцию inflateReset2()
в коде совсем не учитывается порядок байтов, так что будьте внимательны при переносе на другую платформу

P.S. Есть способ чтения быстрее и короче: с начала файла считываем все структуры типа LocalFileHeader, проверяя сигнатуру, если сигнатуры неправильная, значит все файлы считаны.

Список постов в категории "Программирование > C++"

Готовые текстовые битмапы

Текстура с символами (текстурный атлас)

Динамическая генерация из файла шрифта

Запись Local File Header

Запись Central directory file header

Запись EOCD

Находим запись EOCD

Загружаем записи Central directory file header

Загружаем записи Local File Header

Загружаем данные

Общие комментарии по коду