checksum CRC utilizzando long (64 bit)

Question

Ho verificato diverse implementazioni di CRC64. Ad esempio, this, this e this. Il problema con tutti questi è che funzionano con i byte. Tuttavia, su un sistema a 64 bit, mi piacerebbe lavorare con long (8 byte). In questo modo, avrò bisogno di iterare di meno. Ad esempio, per i dati di 128 byte, utilizzando un byte, ho bisogno di iterare 128 volte, mentre con long, avrei bisogno di ripetere solo 16 volte.

Esiste un'implementazione CRC64 che utilizza long o una dimensione di parola superiore a un byte? Questi schemi possono essere modificati per farlo?

Answer 1

Il calcolo CRC utilizza un trucco per evitare di elaborare i dati bit per bit: utilizza una tabella di ricerca che consente di elaborare più bit contemporaneamente.

L'elaborazione di n bit richiede una tabella di ricerca di dimensioni 2^n. Le implementazioni che hai collegato leggono 1 byte (8 bit) alla volta, e infatti usano tutte una tabella di ricerca di dimensioni 256 == 2^8.

L'elaborazione di 64 bit alla volta richiederebbe una tabella di ricerca di dimensioni 2^64, il che non è pratico. Questo è il motivo per cui le implementazioni comuni di CRC eseguono l'elaborazione di 1 byte alla volta.

Mentre è possibile elaborare 2 byte alla volta utilizzando un array 65536-entry, è probabile che abbia un impatto negativo sulle prestazioni a causa dell'utilizzo di più memoria cache della CPU.