L'implementazione di base di CRC32 di Wikipedia differisce dallo standard CRC32 visto online

Ho un'implementazione di base CRC32 in seguito a Wikipedia Code Fragment:1 sample. Penso di averlo fatto bene, con la modifica dell'uso di un registro n bit per il remainderPolynomial invece dell'uso di n + 1 bit come nell'esempio.L'implementazione di base di CRC32 di Wikipedia differisce dallo standard CRC32 visto online

Il risultato che ottengo si differenzia dai risultati di implementazione CRC32 online. Cosa devo cambiare qui nella mia implementazione?

Si prega di ignorare le istruzioni di Console.Writeline per la logica.

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; 
    }

Non sto cercando il modo migliore per ottimizzare la logica, dal momento che sto solo cercando di seguire campione Wikipedia utilizzando C#.

Messaggio di input: 'A' (esadecimale: 0x41) uscita: 0x30476DC0 Secondo this website: uscita dovrebbe essere: 0xD3D99E8B

penso che mi manca sia l'inversione/inizializzazione del CRC, ma sono non sono sicuro di come cambiare questa implementazione di base per ottenere il risultato equivalente al risultato del sito web.

uscita a correre il mio programma:

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

L'ultima riga in hex: 0x30476DC0

Seguito @ Mark Adler Commenti: **

ho modificato il sopra come segue, le seguenti sono le modifiche (i commenti sono aggiunti in linea al codice):

inizializzato a 0xFFFFFFFF
invertito il byte di messaggio di input

XOR al valore finale, invertire il valore XORed

public static UInt32 GenerateCRC_32 (byte [] messaggio) { byte [] augmentedMsg = new byte [message.Length + 8]; message.CopyTo (augmentedMsg, 4); // Modified per creare lo spazio per l'inizializzazione

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;

}

uscita:

---------------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)

Questo non è l'output previsto. Ho implementato lo stesso utilizzando il codice tabella di ricerca di seguito, il risultato è esattamente come sopra (0xC7F9861B), che è sbagliato

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; 
    }

Mentre se uso il codice qui sotto (che evita l'aumento del messaggio) ha dato risultato giusto.

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() e poly32 come accennato nei commenti: **

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; 
    }

fonte

2015-04-20 Titus

Cosa fa 'Reverse' fare? Non vedo alcun codice per quello. –

Inoltre non hai definito 'poly32'. –

Grazie per la risposta. Scusa non ho il codice ora, dal momento che sono in un posto diverso, incollerò il codice che ho usato per il contrario in un paio di giorni. The Reverse() riflette solo i dati binari, puoi vedere un esempio di utilizzo di Reverse nel mio output. 'XOR^0xFFFFFFFF: 11011000011000011001111111100011 (D8619FE3) Invertito Abv: 11000111111110011000011000011011 (C7F9861B)'. Mi dispiace anche per non aver definito 'poly32', ho rinominato 'poly' nel mio primo esempio in 'poly32' così 'const UInt32 poly32 = 0x04C11DB7;' è la definizione. Grazie! – Titus

Lo standard CRC si fa riferimento si riflette, cioè i bit sono invertiti, e viene inizializzato con 0xfffffff e la il CRC finale è in esclusiva o con 0xffffffff.

Si sta generando il CRC con i bit non invertiti, con il CRC iniziale pari a zero e senza esclusivi o alla fine.

Generalmente per implementare un CRC con inversione di bit, i byte di input rimangono invariati, ma riflettono il polinomio e si spostano nell'altra direzione. I byte di input vengono inseriti nella parte inferiore del CRC anziché in cima. Questo riduce anche il numero totale di byte da elaborare da quattro su un approccio di messaggio aumentato.

Aggiornamento per domanda aggiornamento:

Il codice in questione tenta al messaggio "aumentare", ma poi non ha nemmeno usare l'aumento. Invece utilizza i dati a partire dall'offset 4, che equivale a utilizzare il messaggio originale dall'offset 0.

Ciò che invece deve essere fatto è di non provare nemmeno ad aumentare il messaggio, e l'esclusivo - o il messaggio nella parte superiore del CRC invece di provare a inserire il messaggio nella parte inferiore del CRC.

Inoltre, l'inversione del CRC, l'applicazione del messaggio invertito, e quindi l'inversione del CRC di nuovo, equivale a non fare nulla di ciò, e invece di invertire il polinomio e spostare nella direzione opposta. Il polinomio è una costante, quindi l'inversione viene eseguita durante la scrittura del codice, come indicato nella mia risposta originale. 0x04c11db7 invertito è 0xedb88320.

Quindi il codice finisce per guardare come questo (in 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; 
}

fonte

2015-04-20 17:05:27

Grazie per la risposta! Ho aggiunto "8" byte vuoti (nel secondo esempio) alla matrice invece di "4" (come si vede nel primo esempio), 'byte [] augmentedMsg = new byte [message.Length + 8];' così effettivamente gli ultimi quattro byte vuoti del messaggio di aumento sono presenti e vengono utilizzati (l'aumento è aggiunto alla fine del messaggio) anche se inizia a 4. Ho usato i primi byte vuoti "4" per inizializzare il resto su 0xFFFFFFFF ' remainder = ~ remainder; // Sovrascrivi il precedente e inizializza il registro su 0xFFFFFFFF' – Titus

I primi quattro byte non vengono mai usati, quindi non ha senso. –

Ho voluto darti la taglia prima che scada, nell'ultimo minuto, perché mi hai aiutato così tanto signore !. Come risposta al tuo commento precedente, Sì, non aveva senso aggiungere i primi quattro byte vuoti volontariamente e non usarlo mai. L'ho solo mantenuto per avere la modifica dal primo al secondo minimo di esempio. colpa mia!.Pertanto, solo i primi quattro byte non vengono mai utilizzati, ma gli ultimi quattro byte sono stati utilizzati come un aumento del messaggio. Credo che con e senza aumento entrambi dovrebbero restituire lo stesso risultato, ma il mio risultato è stato diverso (errato). Scusa per averti disturbato all'infinito. Grazie! – Titus

L'implementazione di base di CRC32 di Wikipedia differisce dallo standard CRC32 visto online

risposta

Problemi correlati