Elmi
Quiero crear un número de 32 bits a partir de una cadena ASCII. El algoritmo CRC32 es exactamente lo que estoy buscando, pero no puedo usarlo porque la tabla que requiere es demasiado grande (es para un sistema integrado donde los recursos son MUY raros).
Entonces: ¿alguna sugerencia para un algoritmo CRC rápido y delgado? No importa cuando las colisiones son un poco más probables que con el CRC32 original.
marca adler
Las implementaciones de CRC usan tablas para acelerar. No son necesarios.
Aquí hay un CRC32 corto que usa el polinomio de Castagnoli (el mismo que usa la instrucción Intel crc32) o el polinomio de Ethernet (el mismo que usa en zip, gzip, etc.).
#include <stddef.h>
#include <stdint.h>
/* CRC-32C (iSCSI) polynomial in reversed bit order. */
#define POLY 0x82f63b78
/* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */
/* #define POLY 0xedb88320 */
uint32_t crc32c(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;
}
La inicial crc el valor debe ser cero. La rutina se puede llamar sucesivamente con fragmentos de datos para actualizar el CRC. Puede desenrollar el bucle interno para aumentar la velocidad, aunque su compilador podría hacerlo por usted de todos modos.
-
crc = (crc >> 1) ^ (POLY & (0 - (crc & 1)));es aproximadamente un 33 % más rápido cuando se compila para x86 con GCC/ICC/CLANG (104 MB/s frente a 134 MB/s). En el mismo sistema, el slice-8 es de 2040 MB/s e Intel CRC32C es de 8 GB/s, por lo que tal vez no haga mucha diferencia al final.– t0rakka
13 de febrero de 2018 a las 14:37
-
@SnappleLVR Más rápido aún sería una implementación de tabla por bytes o por palabras. Ver locoque generará dichas rutinas.
–Mark Adler
13 de febrero de 2018 a las 18:03
-
Comparado con la misma máquina que los resultados anteriores: 1430 MB/s, no está mal, pero slice-8 sigue siendo un 30 % más rápido y las instrucciones CRC32C son un 450 % más rápidas. Solo estaba señalando que la versión bit a bit simple se puede optimizar para que sea un 33 % más rápida con una pequeña modificación quirúrgica en la fuente. El código original compilado en “test/cmov” con CLANG y GCC usando -O3. La variante más rápida usa NEG/XOR/AND sencillos como se puede esperar de la fuente. El (0 – n) es solo un truco para permitir la negación en enteros sin signo. Entonces, para ser claros, no dije que fuera la rutina más rápida posible. xD
– t0rakka
14 de febrero de 2018 a las 9:22
jeb
Obviamente, la tabla de búsqueda más grande brindará el mejor rendimiento, pero puede usar cualquier tabla (más pequeña) para búsquedas de 16, 8 o 4 bits.
Así que los tamaños de las tablas son para crc32:
16bit-lookup: 4*2^16=256k
8bit-lookup: 4*2^8=1k
4bit-lookup: 4*2^4=64byte
La tabla de 4 bits es cuatro veces más lenta que la de 16 bits.
Lo que debe usar depende de sus requisitos de velocidad.
Como menciona Luka Rahne es buena idea ponerle una tabla a la memoria flash, pero en muchas plataformas no es suficiente usar la const palabra clave.
La mayoría de las veces, debe colocar la tabla en una sección ubicada en flash, modificando su archivo de comando del enlazador.
-
Ver también Rápido CRC32una página web de Stephan Brumme que proporciona una comparación con diferentes tamaños de mesa.
– Lobo
26 de agosto de 2021 a las 9:10
CRC32 se puede implementar sin tabla de búsqueda, o con una tabla de búsqueda de 1k byte si es necesario, sin una penalización de velocidad importante en comparación con la variante de tabla de búsqueda de 256k. ejemplo en wiki.osdev.org/CRC32. Si realmente debe guardar bytes, use adler32.
– dascandy
14 de enero de 2015 a las 9:47
lo que quieres decir con
ressources are VERY rare? ¿Menos de 64 MB, menos de 8 KB o menos de 512 bytes?– jeb
14 de enero de 2015 a las 9:49
Tal vez solo arregle ese código y ponga la tabla en flash. La mayoría de los enlazadores colocan variables constantes en flash, y en la actualidad, incluso las CPU de gama baja vienen con una cantidad decreciente de OTP. Simplemente defina la tabla para que sea const.
– Luka Rahne
14 de enero de 2015 a las 9:54
Si no tiene requisitos particulares para la calidad del hash/suma de control/lo que sea, algo muy simple como
boost::hash_combineo incluso solo XOR, podría ser lo suficientemente bueno.–Mike Seymour
14 de enero de 2015 a las 9:59
La pregunta no está fuera de tema. La policía de stackoverflow aparentemente no conoce la diferencia entre un algoritmo y una implementación. Está completamente en el tema aquí preguntar qué algoritmos existen para hacer una tarea en particular.
–Mark Adler
22/01/2017 a las 17:00