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

Описание формата ZIP файла. Часть 1

ZIP файл состоит из трех областей:

  • сжатые/несжатые данные, (последовательность структур типа LocalFileHeader, сами данные и необязательных DataDescriptor)
  • центральный каталог (последовательность структур CentralDirectoryFileHeader)
  • описание центрального каталога (End of central directory record (EOCD))

С начала файла идет набор из LocalFileHeader, непосредственно данные и (необязательно) структура Data descriptor. Затем структуры типа CentralDirectoryFileHeader для каждого файла и папки в ZIP архиве и завершает все это структура End of central directory record.

Local File Header

Используется для описания метаданных файла (имя файла, контрольная сумма, время и дата модификации, сжатый/несжатый размер). Как правило сразу после этой структуры следует содержимое файла.

LocalFileHeader

struct LocalFileHeader
{
    // Обязательная сигнатура, равна 0x04034b50
    uint32_t signature;
    // Минимальная версия для распаковки
    uint16_t versionToExtract;
    // Битовый флаг
    uint16_t generalPurposeBitFlag;
    // Метод сжатия (0 - без сжатия, 8 - deflate)
    uint16_t compressionMethod;
    // Время модификации файла
    uint16_t modificationTime;
    // Дата модификации файла
    uint16_t modificationDate;
    // Контрольная сумма
    uint32_t crc32;
    // Сжатый размер
    uint32_t compressedSize;
    // Несжатый размер
    uint32_t uncompressedSize;
    // Длина название файла
    uint16_t filenameLength;
    // Длина поля с дополнительными данными
    uint16_t extraFieldLength;
    // Название файла (размером filenameLength)
    uint8_t *filename;
    // Дополнительные данные (размером extraFieldLength)
    uint8_t *extraField;
};

Сразу после этой структуры идут данные размером compressedSize при использовании сжатия или размером uncompressedSize в противном случае.

Иногда бывает невозможно вычислить данные на момент записи LocalFileHeader, тогда в crc32, compressedSize и uncompressedSize записываются нули, третий бит в generalPurposeBitFlag ставится в единицу, а после LocalFileHeader добавляется структура типа DataDescriptor.

Data descriptor

Если по какой-то причине содержимое файла невозможно создать одновременно с заголовком типа LocalFileHeader, то сразу после него следует структура DataDescriptor, где идет находится дополнение метаданных для LocalFileHeader (контрольная сумма, сжатый/несжатый размер).

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

DataDescriptor

struct DataDescriptor
{
    // Необязательная сигнатура, равна 0x08074b50
    uint32_t signature;
    // Контрольная сумма
    uint32_t crc32;
    // Сжатый размер
    uint32_t compressedSize;
    // Несжатый размер
    uint32_t uncompressedSize;
};

Central directory file header

Расширенное описание метаданных файла. Содержит дополненную версию LocalFileHeader (добавляются поля номер диска, файловые атрибуты, смещение до LocalFileHeader от начала ZIP файла).

CenterDirectoryFileHeader

struct CentralDirectoryFileHeader
{
    // Обязательная сигнатура, равна 0x02014b50 
    uint32_t signature;
    // Версия для создания
    uint16_t versionMadeBy;
    // Минимальная версия для распаковки
    uint16_t versionToExtract;
    // Битовый флаг
    uint16_t generalPurposeBitFlag;
    // Метод сжатия (0 - без сжатия, 8 - deflate)
    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;
    // Смещение до структуры LocalFileHeader
    uint32_t localFileHeaderOffset;
    // Имя файла (длиной filenameLength)
    uint8_t *filename;
    // Дополнительные данные (длиной extraFieldLength)
    uint8_t *extraField;
    // Комментарий к файла (длиной fileCommentLength)
    uint8_t *fileComment;
};

End of central directory record (EOCD)

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

EOCD

struct EOCD
{
    // Обязательная сигнатура, равна 0x06054b50
    uint32_t signature;
    // Номер диска
    uint16_t diskNumber;
    // Номер диска, где находится начало Central Directory
    uint16_t startDiskNumber;
    // Количество записей в Central Directory в текущем диске
    uint16_t numberCentralDirectoryRecord;
    // Всего записей в Central Directory
    uint16_t totalCentralDirectoryRecord;
    // Размер Central Directory
    uint32_t sizeOfCentralDirectory;
    // Смещение Central Directory
    uint32_t centralDirectoryOffset;
    // Длина комментария
    uint16_t commentLength;
    // Комментарий (длиной commentLength)
    uint8_t *comment;
};

Папки в ZIP файле представлены двумя структурами LocalFileHeader и CentralDirectoryFileHeader с нулевым размером и контрольной суммой. Название папки заканчивается слешем «/».

Конструктор, деструктор и автоматический стек в C++

С удивлением узнал об интересном способе использования стека в нестандартных целях. Посмотрите внимательно на код ниже.

Его фишка в том, что класс Sample в конструкторе сохраняет предыдущий инстанс типа Sample, а в деструкторе — восстанавливает. При этом метод Sample::instance() всегда будет возвращать текущий объект типа Sample.

Не имею ни малейшего понятия — зачем это может вам понадобиться, но мне пришлось столкнуться с таким впервые, так что спешу поделиться с общественностью.

class Sample
{
public:
    Sample()
        : prevInst_s(curInst_s)
    {
        curInst_s = this;
    }

    ~Sample()
    {
        curInst_s = prevInst_s;
    }

    static Sample *instance()
    {
        return curInst_s;
    }

private:
    Sample *prevInst_s;
    static Sample *curInst_s;
};

Sample *Sample::curInst_s = NULL;

Пример использования такого функционала под катом. (в комментариях указано — какой instance сейчас текущий)

#include <stdio.h>

class Sample
{
public:
    Sample(const char *name)
        : name_(name)
        , prevInst_s(curInst_s)
    {
        curInst_s = this;
        printf("current: %s\n", name_);
    }

    ~Sample()
    {
        curInst_s = prevInst_s;

        if (curInst_s)
        {
            printf("restore: %s\n", curInst_s->name_);
        }
    }

    static Sample *instance()
    {
        return curInst_s;
    }

private:
    const char *name_;
    Sample *prevInst_s;
    static Sample *curInst_s;
};

Sample *Sample::curInst_s = NULL;


int main()
{
    /*
     *
     * Sample::instance() => NULL
     *
     */
    {
        Sample sampleA("A");
        /*
         *
         * Sample::instance() => A
         *
         */
        {
            Sample sampleB("B");
            /*
             *
             *  Sample::instance() => B
             *
             */
        }
        /* 
         * 
         * Sample::instance() => A
         *
         */
        {
            Sample sampleC("C");
            /*
             *
             * Sample::instance() => C
             *
             */
            {
                Sample sampleD("D");
                /*
                 *
                 * Sample::instance() => D
                 *
                 */
            }
            /*
             *
             * Sample::instance() => C
             *
             */
        }
        /*
         *
         * Sample::instance() => A
         *
         */
    }
    /*
     *
     * Sample::instance() => NULL
     *
     */
}

Решение проблемы с нехваткой памяти при загрузке текстур в Android

Как известно, в популярной нынче мобильной ОС Android есть фатальный недостаток — это язык Java. Более того, каждому приложению выделяется кусок памяти размером от 32-х мегабайт до бесконечности в зависимости от желания производителя мобильного телефона.

Если вы делаете большое приложение с использованием OpenGLES и пачкой больших текстур размером 2048×2048 (а это 16 мегабайт для формата RGBA), то памяти для загрузки у вас не будет. После загрузки второй-третьей, пятой текстуры с помощью BitmapFactory приложение упадет с OutOfMemoryError, что есть очень плохо.

Хочу поделиться решением этой проблемы. Она состоит из двух пунктов: загружать изображения из PNG с помощью libpng и исключить работу с большими блоками данных из Java части.

Решение первой части и исходники для прямой загрузки изображения из PNG файла можно найти на stackoverflow.com.

Для работы с памятью создадим вот такой Java класс:

package com.example.memory;

import java.nio.IntBuffer;

public class MemoryManager {
    public static native IntBuffer create(int sizeInBytes);


    public static native void release(IntBuffer buffer);
}

И нативную часть (язык cpp):

#include <jni.h>

#ifdef __cplusplus
extern "C" {
#endif
JNIEXPORT jobject JNICALL Java_com_example_memory_MemoryManager_create(
    JNIEnv *env,
    jclass cls,
    jint sizeInBytes)
{
    // Выделяем блок памяти
    void *buf = malloc(sizeInBytes);
    // Создаем буфер 
    return env->NewDirectByteBuffer(buf, 0);
}

JNIEXPORT void JNICALL Java_com_example_memory_MemoryManager_release(
    JNIEnv *env,
    jclass cls,
    jobject buffer)
{
    // Освобождаем память
    free(env->GetDirectBufferAddress(buffer));
}
#ifdef __cplusplus
}
#endif

Далее алгоритм работы такой:

  1. Читаем высоту и ширины изображения из первых 24 байт PNG (подробности в статье на хабре: Получаем тип и размеры изображения без скачивания его целиком, используя Python)
  2. Выделяем IntBuffer с помощью MemoryManager размером W*H*4 (32bit RGBA, 4 байта на пиксель)
  3. Считываем в него PNG файл
  4. Загружаем эти данные в текстуру с помощью glTexImage2d
  5. Освобождаем IntBuffer в MemoryManager

Честно говоря, я слабо понимаю — почему в нативе вызывается функция NewDirectByteBuffer, а в Java приходит IntBuffer, а не ByteBuffer. Загадка какая-то.

UPD: Если вы решили пойти стандартным путем с загрузкой Bitmap и GLUtil.texImage2D, то не забывайте вызывать bitmap.recycle() после загрузки изображения в текстуру, дабы освободить нативную память.

Самая маленькая программа на C/C++, которая вызывает segmentation fault

Самый маленький код, который после компиляции с помощью gcc вызывает segmentation fault:

main;

Компилируем:

$ gcc crash.c
crash.c:1: warning: data definition has no type or storage class

Запускаем:

$ ./a.out
Segmentation fault

Увидел не так давно на хабре, делюсь.

Вопросы программисту C/C++ на собеседовании с ответами

Заметил, что на собеседовании часто задают одни и те же вопросы по программированию. Если бы брали на работу водителя, то некоторые вопросы звучат примерно так:

  • В какую сторону надо крутить руль, чтоб повернуть направо?
  • За что отвечает педаль сцепления/тормоза/газа?

Такое конечно случается далеко не всегда, но первые пару вопросов обычно такого рода («А какую надо давить педаль, чтоб автомобиль остановился?»). Публикую свои ответы на некоторые вопросы для программистов. Вдруг кому пригодится.. Возможно, здесь много ошибок и помарок — при составлении этого списка я не пользовался интернетом. Старался выдать, что знаю сам.

Как можно оптимизировать данный цикл?

void func(int *array, int len)
{
    for (int i = 0; i < len; i++)
    {
        array[i] = array[i] * array[i];
    }
}

Вот таким образом:

void func(int *array, int len)
{
    const int *end = array + len;

    while (array != end)
    {
        const int value = *array;
        *array++ = value * value;
    }
}

В исходном цикле каждый раз происходит вычисление позиции элемента в массиве array. Переписав функцию мы избавляемся от этого вычисления. Вопрос, кстати, спорный, но за что купил, за то и продаю. В современных компилятора разница минимальна из-за применяемых оптимизаций, в 2007-м году разницы была заметна.

В чем отличие std::list<T> от std::vector<T>?

std::vector<T> — это обертка над обычным С/C++ массивом. Соответственно:

  • если std::vector<T> заполнен, то при добавлении нового элемента, массив удаляется целиком и создается заново с бОльшим размером
  • любой элемент массива можно получить моментально, потому что позиция элемента вычисляется банальным прибавлением индекса к первому элементу (array[i] = array + i)
  • удаление любого элемента из массива, кроме последнего, приведет к перемещению всех элементов справа от удаляемого на одну позицию влево (при соблюдении некоторых условий, можно воспользоваться хаком)
  • занимает неразрывный блок памяти

std::list<T> — это список элементов, которые связаны между собой указателями prev (предыдущий элемент) и next (следующий элемент). Внутри себя std::list<T> хранит указатель на первый элемент и последний (зависит от реализации). Исходя из этого:

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

В языке Java различия между ArrayList и LinkedList практически такие же.

Почему в C++ нужно использовать new вместо теплого лампового malloc()?

Потому что malloc() тупо выделяет блок памяти и возвращает этот блок программисту. А new выделяет память и вызывает конструктор объекта. Тоже самое относится к delete и free(). delete вызывает деструктор и освобождает память. free() просто освобождает память. Также есть размещающий new (placement new), который создает объект в уже выделенной вами памяти.

void *memory = malloc(sizeof(MyClass));
MyClass *object = new (memory) MyClass();

В чем отличие между new/delete и new[]/delete[]?

new выделяет память для одного элемента и вызывает конструктор для него, в то время как new[] выделяет память для массива элементов и вызывает конструктор для каждого из них. delete должен вызываться для объекта выделенного с помощью new, а delete[] для массива, выделенного с помощью new[]. От проблем соответствия new/delete вас могут избавить классы std::auto_ptr<T> (для одного элемента) и std::tr1::scoped_array<T> (для массива элементов). Которые сами вызывают правильный delete в деструкторе.

Для чего нужен тип std::auto_ptr<T>?

В стародавние времена вы должны были сами следить за тем, чтоб после каждого new был вызван свой delete. Это было жутко неудобно (программисты Си выкручиваются из этой ситуации вставляя goto):

bool func()
{
    Stream *stream = new Stream;

    if (0 != stream->open("some stream"))
    {
        delete stream;
        return false;
    }

    if (0 != stream->load())
    {
        delete stream;
        return false;
    }

    // Выполняем полезную работу
    // Закончили полезную работу
    delete stream;
    return true;
}

После появление std::auto_ptr<T> стало возможным переписать функцию таким образом:

bool func()
{
    std::auto_ptr<Stream> stream(new Stream);

    if (0 != stream->open("some stream"))
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }

    if (0 != stream->load())
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }

    // Выполняем полезную работу
    // Закончили полезную работу

    // Здесь "delete stream" вызывается автоматически
    return true;
}

И еще очень важный момент: std::auto_ptr<T> владеет объектом единолично. Вы не сможете шарить объект между двумя std::auto_ptr<T> (используйте в таких случаях std::shared_ptr<T>):

void func() 
{
    Object *object = new Object;

    std::auto_ptr<Object> ptr1(object); // object теперь живет внутри ptr1
    std::auto_ptr<Object> ptr2(ptr1); // ptr1 опустел, object внутри ptr2

    // здесь деструктор ptr2 удалит object
    // а здесь вызовется деструктор ptr1 впустую
}

И помните: std::auto_ptr<T> не подходит для массивов выделенных с помощью new[]. Для этих целей используйте std::tr1::scoped_array<T> или boost::scoped_array<T>.
В современном мире вместо std::auto_ptr принято использовать std::unique_ptr, а для массивов std::unique_ptr<T[]>.

Что такое RAII?

Это переводится как «Получение ресурса есть инициализация». Идея вкратце такая: в конструкторе открываем/блокируем ресурс, в деструкторе закрываем/освобождаем ресурс. Вот пример:

class FILEWrap
{
public:
    FILEWrap( const char *fileName )
        : f_(fopen(fileName, "rb"))
    {
    }

    ~FILEWrap()
    {
        if (f_)
        {
            fclose(f_);
        }
    }

private:
    FILE *f_;
};

Или более каноничный пример (блокирование мьютекса или критической секции):

class MutexLock
{
public:
    MutexLock(Mutex &mutex)
        : mutex_(mutex)
    {
        mutex.lock();
    }

    ~MutexLock()
    {
        mutex.unlock();
    }

private:
    Mutex &mutex_;
};

Зачем нужен виртуальный деструктор?

Попробуем обойтись без него:

#include <stdio.h>

class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }

    ~A() 
    { 
        printf("destruct A\n"); 
    }
};


class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }

    ~B() 
    { 
        printf("destruct B\n"); 
    }
};


int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Вывод:

construct A
construct B
destruct A

Как можно заметить деструктор B не вызвался. Сделаем деструктор класса A виртуальным и посмотрим что получится:

#include <stdio.h>

class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }

    virtual ~A() 
    { 
        printf("destruct A\n"); 
    }
};


class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }

    ~B() 
    { 
        printf("destruct B\n"); 
    }
};


int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Теперь все отлично:

construct A
construct B
destruct B
destruct A

В каком порядке инициализируются члены класса?

Члены класса создаются в порядке их объявления в классе. Уничтожаются они в обратном порядке. Давайте проверим:

#include <stdio.h>
 
class Printer
{
public:
    Printer( const char *n ) 
        : n_(n)
    {
        printf("+%s ", n_);
    }
 
    ~Printer() 
    {
        printf("-%s ", n_);
    }
 
private:
    const char *n_;
};


class A : public Printer
{   
public:
    A() 
        : Printer("A") 
    {
    }
};


class B : public Printer
{
public:
    B() 
        : Printer("B") 
    {
    }
};


class C : public Printer
{
public:
    C() 
        : Printer("C") 
    {
    }
};
 
 
class Test
{
private:
    A A_;
    B B_;
    C C_;
};
 
 
int main()
{
    Test test;
}

Запустим:

+A +B +C -C -B -A

Все правильно.

Порядок объявления очень важен, если один член класса во время инициализации использует данные другого члена. Кстати, компилятор gcc выдает warning (с флагом -Wall), если вы описали инициализацию членов класса в другом порядке. И это еще одна причина в пользу использования настройки компилятора «считать предупреждения ошибками» (в gcc это флаг -Werror).

Личный блог Евгения Жирнова