1. дома
  2. Вопрос и ответ
  3. Основная реализация CRC32 в Википедии отличается от стандартной CRC32, видимой онлайн

Основная реализация CRC32 в Википедии отличается от стандартной CRC32, видимой онлайн

2015-04-20 4 views
12

У меня есть базовая реализация CRC32 после версии Code Fragment:1 sample от Википедии. Я думаю, что я сделал это правильно, с модификацией использования n-разрядного регистра для остатка Polyynomial вместо n + 1 бит использования в соответствии с примером.Основная реализация CRC32 в Википедии отличается от стандартной CRC32, видимой онлайн

В результате я получаю отличные результаты от результатов внедрения CRC32 в Интернете. Что мне нужно изменить здесь в моей реализации?

Просьба игнорировать Console.Writeline заявления для логики.

const UInt32 poly = 0x04C11DB7; 

    public static UInt32 GenerateCRC_32(byte[] message) 
    { 
     byte[] augmentedMsg = new byte[message.Length + 4]; 
     message.CopyTo(augmentedMsg, 0); 

     UInt32 remainder = Convert.ToUInt32(augmentedMsg[0]) << 24 | 
          Convert.ToUInt32(augmentedMsg[1]) << 16 | 
          Convert.ToUInt32(augmentedMsg[2]) << 8 | 
          Convert.ToUInt32(augmentedMsg[3]); 

     for (Int32 i = 4; i < augmentedMsg.Length; i++) 
     { 
      for (int bit = 0; bit < 8; bit++) 
      { 
       UInt32 nextBit = ((UInt32)augmentedMsg[i] >> (7 - bit)) & 0x01; 
       if ((remainder & 0x80000000) > 0) 
       { 
        Console.WriteLine("---------------DO XOR --------------------"); 
        Console.WriteLine(Convert.ToString(((remainder << 1) | nextBit), 2).PadLeft(32, '0')); 
        Console.WriteLine(Convert.ToString(poly, 2).PadLeft(32, '0')); 
        Console.WriteLine("------------------------------------------"); 

        remainder = ((remainder << 1) | nextBit)^poly; 

        Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0')); 
        Console.WriteLine("------------------------------------------"); 
       } 
       else 
       { 
        remainder = (remainder << 1) | nextBit; 

        Console.WriteLine("--------------NO---------------------"); 
        Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0')); 
        Console.WriteLine("------------------------------------------"); 
       } 
      } 
     } 

     Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0')); 
     Console.WriteLine(remainder.ToString("X")); 

     return remainder; 
    }

Я не ищу лучший способ оптимизировать логику, так как я просто пытаюсь следовать образцу Википедии с помощью C#.

Входное сообщение: «A» (шестнадцатеричный: 0x41) Выход: 0x30476DC0 По this website: Вывод должен быть: 0xD3D99E8B

Я думаю, что мне не хватает либо реверсирования/Инициализация КПР, но я не уверен, как изменить эту базовую реализацию, чтобы получить результат, эквивалентный результату веб-сайта.

Вывод о запуске моей программы:

--------------NO--------------------- 
10000010000000000000000000000000 
------------------------------------------ 
---------------DO XOR -------------------- 
00000100000000000000000000000000 
00000100110000010001110110110111 
------------------------------------------ 
00000000110000010001110110110111 
------------------------------------------ 
--------------NO--------------------- 
00000001100000100011101101101110 
------------------------------------------ 
--------------NO--------------------- 
00000011000001000111011011011100 
------------------------------------------ 
--------------NO--------------------- 
00000110000010001110110110111000 
------------------------------------------ 
--------------NO--------------------- 
00001100000100011101101101110000 
------------------------------------------ 
--------------NO--------------------- 
00011000001000111011011011100000 
------------------------------------------ 
--------------NO--------------------- 
00110000010001110110110111000000 
------------------------------------------ 
00110000010001110110110111000000

Последняя строка в шестнадцатеричном: 0x30476DC0

Последующая деятельность по итогам @Mark Адлер Комментарии: **

Я модифицировал выше следуют ниже, следующие изменения (комментарии добавлены в строку кода):

  1. инициализируется 0xFFFFFFFF
  2. Перевернутого байт входного сообщения

  3. исключающих до конечного значения, обратное значения операции XOR

    общественность статических UInt32 GenerateCRC_32 (байты [] сообщение) { байт [] augmentedMsg = новый байт [message.Length + 8]; message.CopyTo (дополненоMsg, 4); // Modified, чтобы создать пространство для инициализации

    UInt32 remainder = Convert.ToUInt32(augmentedMsg[0]) << 24 | 
        Convert.ToUInt32(augmentedMsg[1]) << 16 | 
        Convert.ToUInt32(augmentedMsg[2]) << 8 | 
        Convert.ToUInt32(augmentedMsg[3]); 

remainder = ~remainder; // Overwrite the above and initialized the register to 0xFFFFFFFF 

for (Int32 i = 4; i < augmentedMsg.Length; i++) 
{ 
    byte reversedMessage = Reverse(augmentedMsg[i]); // Reversed the augmented message byte 
    for (int bit = 0; bit < 8; bit++) 
    { 
     UInt32 nextBit = Convert.ToUInt32(reversedMessage >> (7 - bit)) & 0x1; // Use the reversed message byte 
     if ((remainder & 0x80000000) > 0) 
     { 
      Console.WriteLine("---------------DO XOR --------------------"); 
      Console.WriteLine(Convert.ToString(((remainder << 1) | nextBit), 2).PadLeft(32, '0')); 
      Console.WriteLine(Convert.ToString(poly32, 2).PadLeft(32, '0')); 
      Console.WriteLine("------------------------------------------"); 

      remainder = Convert.ToUInt32((UInt32)((UInt32)(remainder << 1) | nextBit)^poly32); 

      Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0')); 
      Console.WriteLine("------------------------------------------"); 
     } 
     else 
     { 
      remainder = (UInt32)((UInt32)(remainder << 1) | nextBit); 

      Console.WriteLine("--------------NO---------------------"); 
      Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0')); 
      Console.WriteLine("------------------------------------------"); 
     } 
    } 
} 

Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0') + "(" + remainder.ToString("X") + ")"); 

remainder = (~remainder); 

Console.WriteLine("XOR^0xFFFFFFFF : " + Convert.ToString(remainder, 2).PadLeft(32, '0') + "(" + remainder.ToString("X") + ")"); 

remainder = Reverse(remainder); 

Console.WriteLine("Reversed the Abv : " + Convert.ToString(remainder, 2).PadLeft(32, '0') + "(" + remainder.ToString("X") + ")"); 
return remainder;

    }

Выход:

---------------DO XOR -------------------- 
11111111111111111111111111111111 
00000100110000010001110110110111 
------------------------------------------ 
11111011001111101110001001001000 
------------------------------------------ 
---------------DO XOR -------------------- 
11110110011111011100010010010000 
00000100110000010001110110110111 
------------------------------------------ 
11110010101111001101100100100111 
------------------------------------------ 
---------------DO XOR -------------------- 
11100101011110011011001001001110 
00000100110000010001110110110111 
------------------------------------------ 
11100001101110001010111111111001 
------------------------------------------ 
---------------DO XOR -------------------- 
11000011011100010101111111110010 
00000100110000010001110110110111 
------------------------------------------ 
11000111101100000100001001000101 
------------------------------------------ 
---------------DO XOR -------------------- 
10001111011000001000010010001010 
00000100110000010001110110110111 
------------------------------------------ 
10001011101000011001100100111101 
------------------------------------------ 
---------------DO XOR -------------------- 
00010111010000110011001001111010 
00000100110000010001110110110111 
------------------------------------------ 
00010011100000100010111111001101 
------------------------------------------ 
--------------NO--------------------- 
00100111000001000101111110011011 
------------------------------------------ 
--------------NO--------------------- 
01001110000010001011111100110110 
------------------------------------------ 
--------------NO--------------------- 
10011100000100010111111001101100 
------------------------------------------ 
---------------DO XOR -------------------- 
00111000001000101111110011011000 
00000100110000010001110110110111 
------------------------------------------ 
00111100111000111110000101101111 
------------------------------------------ 
--------------NO--------------------- 
01111001110001111100001011011110 
------------------------------------------ 
--------------NO--------------------- 
11110011100011111000010110111100 
------------------------------------------ 
---------------DO XOR -------------------- 
11100111000111110000101101111000 
00000100110000010001110110110111 
------------------------------------------ 
11100011110111100001011011001111 
------------------------------------------ 
---------------DO XOR -------------------- 
11000111101111000010110110011110 
00000100110000010001110110110111 
------------------------------------------ 
11000011011111010011000000101001 
------------------------------------------ 
---------------DO XOR -------------------- 
10000110111110100110000001010010 
00000100110000010001110110110111 
------------------------------------------ 
10000010001110110111110111100101 
------------------------------------------ 
---------------DO XOR -------------------- 
00000100011101101111101111001010 
00000100110000010001110110110111 
------------------------------------------ 
00000000101101111110011001111101 
------------------------------------------ 
--------------NO--------------------- 
00000001011011111100110011111010 
------------------------------------------ 
--------------NO--------------------- 
00000010110111111001100111110100 
------------------------------------------ 
--------------NO--------------------- 
00000101101111110011001111101000 
------------------------------------------ 
--------------NO--------------------- 
00001011011111100110011111010000 
------------------------------------------ 
--------------NO--------------------- 
00010110111111001100111110100000 
------------------------------------------ 
--------------NO--------------------- 
00101101111110011001111101000000 
------------------------------------------ 
--------------NO--------------------- 
01011011111100110011111010000000 
------------------------------------------ 
--------------NO--------------------- 
10110111111001100111110100000000 
------------------------------------------ 
---------------DO XOR -------------------- 
01101111110011001111101000000000 
00000100110000010001110110110111 
------------------------------------------ 
01101011000011011110011110110111 
------------------------------------------ 
--------------NO--------------------- 
11010110000110111100111101101110 
------------------------------------------ 
---------------DO XOR -------------------- 
10101100001101111001111011011100 
00000100110000010001110110110111 
------------------------------------------ 
10101000111101101000001101101011 
------------------------------------------ 
---------------DO XOR -------------------- 
01010001111011010000011011010110 
00000100110000010001110110110111 
------------------------------------------ 
01010101001011000001101101100001 
------------------------------------------ 
--------------NO--------------------- 
10101010010110000011011011000010 
------------------------------------------ 
---------------DO XOR -------------------- 
01010100101100000110110110000100 
00000100110000010001110110110111 
------------------------------------------ 
01010000011100010111000000110011 
------------------------------------------ 
--------------NO--------------------- 
10100000111000101110000001100110 
------------------------------------------ 
---------------DO XOR -------------------- 
01000001110001011100000011001100 
00000100110000010001110110110111 
------------------------------------------ 
01000101000001001101110101111011 
------------------------------------------ 
--------------NO--------------------- 
10001010000010011011101011110110 
------------------------------------------ 
---------------DO XOR -------------------- 
00010100000100110111010111101100 
00000100110000010001110110110111 
------------------------------------------ 
00010000110100100110100001011011 
------------------------------------------ 
--------------NO--------------------- 
00100001101001001101000010110110 
------------------------------------------ 
--------------NO--------------------- 
01000011010010011010000101101100 
------------------------------------------ 
--------------NO--------------------- 
10000110100100110100001011011000 
------------------------------------------ 
---------------DO XOR -------------------- 
00001101001001101000010110110000 
00000100110000010001110110110111 
------------------------------------------ 
00001001111001111001100000000111 
------------------------------------------ 
--------------NO--------------------- 
00010011110011110011000000001110 
------------------------------------------ 
--------------NO--------------------- 
00100111100111100110000000011100 
------------------------------------------ 
00100111100111100110000000011100(279E601C) 
XOR^0xFFFFFFFF : 11011000011000011001111111100011(D8619FE3) 
Reversed the Abv : 11000111111110011000011000011011(C7F9861B)

Это не ожидаемый выход. Я осуществил то же самое, используя приведенный ниже код таблицы поиска, результат точно так же, как и выше (0xC7F9861B), что неправильно

public static UInt32 GenerateCRC_32_from_Table(byte[] message) 
    { 
     byte[] augmentedMsg = new byte[message.Length + 4]; 
     message.CopyTo(augmentedMsg, 0); 

     UInt32 remainder = 0xFFFFFFFF; 

     foreach (byte msgByte in augmentedMsg) 
     { 
      byte reversedMsgByte = Reverse(msgByte); 
      remainder = ((remainder << 8) | Convert.ToUInt32(reversedMsgByte))^crc32_table[((remainder >> 24)) & 0xFF]; 
     } 

     remainder = Reverse(~remainder); 
     return remainder; 
    }

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

public static UInt32 GenerateCRC_32_from_Table(byte[] message) 
    { 
     UInt32 remainder = 0xFFFFFFFF; 

     foreach (byte msgByte in message) 
     { 
      byte reversedMsgByte = Reverse(msgByte); 
      remainder = (remainder << 8)^crc32_table[((remainder >> 24)^Convert.ToUInt32(reversedMsgByte)) & 0xFF]; 
     } 

     remainder = Reverse(~remainder); 
     return remainder; 
    }

Reverse() и poly32, как указано в комментариях: **

const UInt32 poly32 = 0x04C11DB7; 

    public static UInt32 Reverse(UInt32 message) 
    { 
     UInt32 msgReversed = 0; 
     for (int i = 0; i < 32; i++) 
     { 
      msgReversed = ((message & 0x80000000) >> (31 - i)) | msgReversed; 
      message = message << 1; 
     } 
     return msgReversed; 
    } 

    public static byte Reverse(byte message) 
    { 
     byte msgReversed = 0; 
     for (int i = 0; i < 8; i++) 
     { 
      msgReversed = (byte)(((byte)((byte)(message) & 0x80) >> (7 - i)) | msgReversed); 
      message = (byte)(message << 1); 
     } 
     return msgReversed; 
    }

источник

2015-04-20 Titus

+0

Что 'Reverse' делать? Я не вижу никакого кода для этого. –

+0

Также вы не указали 'poly32'. –

+0

Благодарим вас за ответ. Извините, у меня нет кода сейчас, так как я нахожусь в другом месте, вставьте код, который я использовал для обращения через пару дней. Обратный() просто отражает двоичные данные, вы можете увидеть пример использования Reverse в моем выпуске. 'XOR^0xFFFFFFFF: 11011000011000011001111111100011 (D8619FE3) Перевернуто Abv: 11000111111110011000011000011011 (C7F9861B)'. Также извините за отсутствие определения «poly32», я переименовал «poly» в моем первом примере в «poly32», поэтому «const UInt32 poly32 = 0x04C11DB7;» это определение. Благодаря! – Titus

ответ

5

Стандарт CRC вы имеете в виду отражение, т.е. биты поменялись местами, и он инициализируется с 0xfffffff а окончательный CRC является эксклюзивным или с 0xffffffff.

Вы генерируете CRC с битами, не обращенными, при этом исходный CRC равен нулю, и без исключения - или в конце.

Как правило, для реализации CRC с битовым обратным преобразованием вы оставляете входные байты как есть, но отражаете многочлен и сдвигаете в другом направлении. Входные байты подаются в нижней части CRC вместо верхней. Это также уменьшает общее количество байтов, которые будут обрабатываться четырьмя по сравнению с расширенным подходом к сообщению.

Update для обновления вопрос:

Код в вопросе пытается «усилить» сообщение, но потом даже не использовать увеличение. Вместо этого он использует данные, начинающиеся со смещения 4, что эквивалентно использованию исходного сообщения со смещением 0.

Вместо этого нужно попытаться не увеличивать сообщение, а исключать - или сообщение в верхней части CRC вместо того, чтобы пытаться подать сообщение в нижней части CRC.

Кроме того, реверсирование CRC, обращение к обратному сообщению и повторное обращение к CRC эквивалентно тому, чтобы ничего не делать, а вместо этого перевернуть полином и сдвинуть в другом направлении. Полином является константой, поэтому разворот выполняется при написании кода, как указано в моем первоначальном ответе. 0x04c11db7 Обратный - 0xedb88320.

Поэтому код заканчивает тем, как это (в C):

#include <stddef.h> 
#include <stdint.h> 

/* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */ 
#define POLY 0xedb88320 

/* Compute CRC of buf[0..len-1] with initial CRC crc. This permits the 
    computation of a CRC by feeding this routine a chunk of the input data at a 
    time. The value of crc for the first chunk should be zero. */ 
uint32_t crc32(uint32_t crc, const unsigned char *buf, size_t len) 
{ 
    int k; 

    crc = ~crc; 
    while (len--) { 
     crc ^= *buf++; 
     for (k = 0; k < 8; k++) 
      crc = crc & 1 ? (crc >> 1)^POLY : crc >> 1; 
    } 
    return ~crc; 
}

источник

2015-04-20 17:05:27

+0

Благодарим вас за ответ! Я добавил «8» пустых байтов (во втором примере) к массиву вместо «4» (как показано в первом примере), 'byte [] augmentedMsg = новый байт [message.Length + 8];' так на самом деле последние четыре пустых байта расширения сообщения присутствуют и используются (добавление добавляется в конец сообщения), даже если оно начинается с 4. Я использовал первые «4» пустые байты, чтобы инициализировать остаток до 0xFFFFFFFF ' остаток = ~ остаток; // Запишите выше и инициализируйте регистр 0xFFFFFFFF' – Titus

+0

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

+0

Я хотел дать тебе щедрость до того, как она истечет, в последнюю минуту, потому что ты мне так помог! В ответ на ваш вышеприведенный комментарий Да, не было смысла добавлять первые четыре пустых байта добровольно и никогда не использовать его. Я просто сохранил его для модификации от первого до второго минимального примера. моя вина!.Таким образом, только первые четыре байта никогда не используются, но последние четыре байта использовались в качестве дополнения к сообщению. Я верю, и без увеличения оба должны возвратить тот же результат, но мой результат был другим (неверным). Извините за то, что вы бесконечно тянете. Благодаря! – Titus

 Смежные вопросы

  • Нет связанных вопросов^_^