Как точно рассчитывается CRC PNG?

Последние 4 часа изучаю алгоритм CRC. Я почти уверен, что уже освоился.

Я пытаюсь написать кодировщик png, и я не хочу использовать внешние библиотеки ни для вычисления CRC, ни для самого кодирования png.

Моя программа смогла получить те же CRC, что и примеры в учебных пособиях. Как в Википедии:  введите описание изображения здесь

Используя тот же полином и сообщение, что и в примере, я смог получить тот же результат в обоих случаях. Я смог сделать это и для нескольких других примеров.

Однако я не могу правильно рассчитать CRC файлов png. Я проверил это, создав пустой файл .png размером в один пиксель в Paint и используя его CRC для сравнения. Я скопировал данные (и имя блока) из блока IDAT файла png (который CRC вычисляется из) и вычисляет его CRC, используя полином, указанный в спецификации png.

Многочлен, представленный в спецификации png, имеет следующий вид:

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Что должно переводиться как:

1 00000100 11000001 00011101 10110111

Используя этот многочлен, я попытался получить CRC следующих данных:

01001001 01000100 01000001 01010100
00011000 01010111 01100011 11101000
11101100 11101100 00000100 00000000
00000011 00111010 00000001 10011100

Вот что я получаю:

01011111 11000101 01100001 01101000 (MSB First)
10111011 00010011 00101010 11001100 (LSB First)

Вот что такое CRC на самом деле:

11111010 00010110 10110110 11110111

Я не совсем уверен, как это исправить, но предполагаю, что я делаю эту часть из спецификации неверно:

В PNG 32-битный CRC инициализируется всеми единицами, а затем данные из каждого байта обрабатываются от младшего бита (1) до самого старшего бита (128). После обработки всех байтов данных CRC инвертируется (берется его дополнение). Это значение передается (сохраняется в потоке данных) MSB первым. С целью разделения на байты и упорядочивания младший бит 32-битной CRC определяется как коэффициент члена x31.

Я не совсем уверен, что могу все это понять.

Кроме того, вот код, который я использую для получения CRC:

 public BitArray GetCRC(BitArray data)
    {
        // Prepare the divident; Append the proper amount of zeros to the end
        BitArray divident = new BitArray(data.Length + polynom.Length - 1);
        for (int i = 0; i < divident.Length; i++)
        {
            if (i < data.Length)
            {
                divident[i] = data[i];
            }
            else
            {
                divident[i] = false;
            }
        }

        // Calculate CRC
        for (int i = 0; i < divident.Length - polynom.Length + 1; i++)
        {
            if (divident[i] && polynom[0])
            {
                for (int j = 0; j < polynom.Length; j++)
                {
                    if ((divident[i + j] && polynom[j]) || (!divident[i + j] && !polynom[j]))
                    {
                        divident[i + j] = false;
                    }
                    else
                    {
                        divident[i + j] = true;
                    }
                }
            }
        }

        // Strip the CRC off the divident
        BitArray crc = new BitArray(polynom.Length - 1);
        for (int i = data.Length, j = 0; i < divident.Length; i++, j++)
        {
            crc[j] = divident[i];
        }
        return crc;
    }

Итак, как мне исправить это, чтобы оно соответствовало спецификации PNG?


person MythicManiac    schedule 06.06.2014    source источник
comment
Вам необходимо прочитать это руководство. Во-первых, здесь не место для проверки вашего кода. Это неверно. Во-вторых, вы совершенно неверно подходите к вычислению CRC. Вы должны использовать операцию исключающее ИЛИ, а не && || (! && !), и использовать несколько бит за одну операцию. В-третьих, даже если ваш код заработал, вы не выполняете предварительную и постобработку CRC путем ее инвертирования.   -  person Mark Adler    schedule 06.06.2014
comment
Я знаю, что это не место для проверки моего кода, однако я подумал, что, возможно, это поможет с моим вопросом, если я включу код. Я пока не собираюсь обрабатывать несколько бит за одну операцию, потому что я хочу, чтобы самые основы работали, прежде чем я начну оптимизировать свой код, чтобы он был быстрее. Я хочу понимать код, а не просто копировать и вставлять его из любого места в Интернете. Кроме того, я думаю, что я довольно ясно дал понять, что мой код работает или, по крайней мере, работает над примерами, которые я нашел в руководствах, и учебник, который вы связали, является одним из них.   -  person MythicManiac    schedule 06.06.2014
comment
Ваш код не работает, поскольку ни один из предоставленных результатов не соответствует ожидаемому чистому CRC-32 предоставленных данных. Под чистым я подразумеваю без предварительной и пост-обработки CRC.   -  person Mark Adler    schedule 07.06.2014
comment
Вопрос, который я задаю, заключается в том, что именно представляет собой предварительный и пост-процесс? Либо я недостаточно прочел руководство (остановился на реализации, так как моя не работала), либо это не объясняется там.   -  person MythicManiac    schedule 07.06.2014
comment
Инвертируйте каждый бит в CRC. Затем выполните процесс CRC, который вы пытаетесь выполнить, с правильным полиномом и порядком битов. Затем, когда закончите, снова инвертируйте каждый бит в CRC. Эти две инверсии - это предварительная и постобработка. Чистая CRC не будет заменена строкой нулей любой длины. CRC до и после обработки будет заменен строкой нулей, и результат будет зависеть от того, сколько нулей.   -  person Mark Adler    schedule 07.06.2014
comment
Насколько я понимаю, это означает, что я должен сделать это, чтобы соответствовать спецификации: 1: Инициализировать CRC для всех единиц. 2: обработать CRC, используя первую версию полинома LSB. 3: переверните полученный CRC так, чтобы сначала был MSB. Если это неверно, вы должны понять, почему я не получаю результат правильно. Тем не менее, я ценю вашу помощь.   -  person MythicManiac    schedule 07.06.2014
comment
Да на 1. Я не уверен, что вы имеете в виду под 2. Многочлен нужно перевернуть, чтобы член x ^ 31 находился в младшем разряде. Сделав это, вы не сделаете 3. Вам также необходимо инвертировать каждый бит (0- ›1, 1-› 0) в конце.   -  person Mark Adler    schedule 07.06.2014
comment
@MarkAdler, что вы подразумеваете под инвертированием каждого бита CRC? вы имеете в виду инвертировать данные, которые вы вводите в алгоритм CRC, или инвертировать многочлен, или что-то еще? а что вы имеете в виду под MSB? самый старший БАЙТ или самый старший БИТ?   -  person MarcusJ    schedule 26.10.2017
comment
@MarcusJ Инвертировать каждый бит CRC означает инвертировать каждый бит CRC. CRC - это результат вычисления. Это не данные и не многочлен.   -  person Mark Adler    schedule 26.10.2017
comment
Здесь MSB - старший бит. CRC - это всегда биты. Они не зависят от существования байтов.   -  person Mark Adler    schedule 26.10.2017


Ответы (1)


Вы можете найти полную реализацию вычисления CRC (и кодировки PNG в целом) в этом общедоступный код:

static uint[] crcTable;

// Stores a running CRC (initialized with the CRC of "IDAT" string). When
// you write this to the PNG, write as a big-endian value
static uint idatCrc = Crc32(new byte[] { (byte)'I', (byte)'D', (byte)'A', (byte)'T' }, 0, 4, 0);

// Call this function with the compressed image bytes, 
// passing in idatCrc as the last parameter
private static uint Crc32(byte[] stream, int offset, int length, uint crc)
{
    uint c;
    if(crcTable==null){
        crcTable=new uint[256];
        for(uint n=0;n<=255;n++){
            c = n;
            for(var k=0;k<=7;k++){
                if((c & 1) == 1)
                    c = 0xEDB88320^((c>>1)&0x7FFFFFFF);
                else
                    c = ((c>>1)&0x7FFFFFFF);
            }
            crcTable[n] = c;
        }
    }
    c = crc^0xffffffff;
    var endOffset=offset+length;
    for(var i=offset;i<endOffset;i++){
        c = crcTable[(c^stream[i]) & 255]^((c>>8)&0xFFFFFF);
    }
    return c^0xffffffff;
}

1 https://web.archive.org/web/20150825201508/http://upokecenter.dreamhosters.com/articles/png-image-encoder-in-c/

person EricLaw    schedule 13.10.2014
comment
Это можно проверить с помощью блока IEND, который всегда должен генерировать байты 0xae 0x42 0x60 0x82, поскольку он никогда не меняет своего имени и никогда не имеет никакой полезной нагрузки. Посмотрите на свои существующие файлы: все они должны заканчиваться этими байтами. - person AmigoJack; 09.06.2021