Algoritmos de checksum rápidos

[planeta9999]

¿ Teneis experiencia con algoritmos de checksum ?.
Necesito aplicarlo para identificar imágenes, pero tiene que ser muy rápido, en este caso es irrelevante lo seguro que sea , solo importa que sea muy rápido.

En principo he pensado en usar CRC32. Buscando información por Google, parece que sería el más rápido, no se si hay algún otro que lo supere.

En una comparativa que alguien ha hecho en PHP, ejecutando un bucle de 1.000.000 de llamadas, le dió esta clasificación de varios algoritmos.

hash('crc32', 'The quick brown fox jumped over the lazy dog.');#  750ms   8 chars
hash('crc32b','The quick brown fox jumped over the lazy dog.');#  700ms   8 chars
hash('md5',   'The quick brown fox jumped over the lazy dog.');#  770ms  32 chars
hash('sha1',  'The quick brown fox jumped over the lazy dog.');#  880ms  40 chars
hash('sha256','The quick brown fox jumped over the lazy dog.');# 1490ms  64 chars
hash('sha384','The quick brown fox jumped over the lazy dog.');# 1830ms  96 chars
hash('sha512','The quick brown fox jumped over the lazy dog.');# 1870ms 128 chars

[KILLERJC]

El micro que estas utilizando no posee un modulo CRC el cual puedas enviarle por DMA los datos?

[tsk]

En realidad CRC32 es usado más para detectar y corregir errores por lo que existe una probabilidad mayor de encontrar colisiones, es decir que dos entradas completamente distintas generen la misma suma. Sólo tienes que verificar que no tengas colisiones en los datos que vas a manejar, de ahí en fuera es rápido y muchos MCUs vienen con el módulo CRC.

El siguiente código simula lo que hace el módulo de los STM32, probablemente lo puedas adaptar a como lo hacen los Kinetis.

Código: Python

1. POLY = 0x04C11DB7
2.  
3. custom_crc_table = {}
4.  
5. def int_to_bytes(i):
6.     return [(i >> 24) & 0xFF, (i >> 16) & 0xFF, (i >> 8) & 0xFF, i & 0xFF]
7.  
8.  
9. def generate_crc32_table(_poly):
10.  
11.     global custom_crc_table
12.  
13.     for i in range(256):
14.         c = i << 24
15.  
16.         for j in range(8):
17.             c = (c << 1) ^ _poly if (c & 0x80000000) else c << 1
18.  
19.         custom_crc_table[i] = c & 0xffffffff
20.  
21. def custom_crc32(buf):
22.  
23.     global custom_crc_table
24.     crc = 0xffffffff
25.     for integer in buf:
26.         b = [0,0,0,ord(integer)]
27.         for byte in b:
28.             crc = ((crc << 8) & 0xffffffff) ^ custom_crc_table[(crc >> 24) ^ byte]
29.  
30.     return crc
31.  
32.  
33. def calc_checksum(file_name):
34.     buf = open(file_name,"rb").read()
35.     generate_crc32_table(POLY)
36.     custom_crc = custom_crc32(buf)
37.     return(hex(custom_crc))
38.  
39. if __name__ == "__main__":
40.     import sys
41.  
42.     filename = sys.argv[1]
43.     print(calc_checksum(filename))

Código: [Seleccionar]

python crc.py crc.py
0x255bd57b
No todos dan el mismo resultado ya que usan polinomios distintos, por ejemplo si uso el comando crc32 en Linux obtendría

Código: [Seleccionar]

crc32 crc.py
37d48cf8
Pero si requieres disminuir la probabilidad de colisiones podrías usar md5, según dicen que también es rápido, aunque no tanto como CRC32.

Puedes probar varias funciones de hashing con mbedTLS https://tls.mbed.org/

[Picuino]

Si quieres que sea rápido, utiliza uno más simple todavía sobre una parte de la imagen (por ejemplo suma de los primeros 1024 bytes de la imagen). Eso va a ser 1000 veces más rápido.

En el caso de que el checksum simple coincida, puedes hacer una segunda ronda con CRC32 más lento para comprobar si realmente coinciden.

Así te quitas rápidamente de en medio muchas fotos y sólo tienes que hacer el CRC32 lento en unas pocas fotos.

Si el CRC32 lo puedes calcular con anterioridad y guardarlo en la propia foto (por ejemplo en la información EXIF), entonces lo más rápido es recuperarle directamente de la información EXIF sin calcular nada.

Saludos.

[planeta9999]

El micro que estas utilizando no posee un modulo CRC el cual puedas enviarle por DMA los datos?

Parece que si, pero de momento no encuentro nada que explique como utilizarlo. También tiene encriptación por hardware y generador de números aleatorios.

Por DMA no se si podré, porque ya tengo dos procesos que lo utilizan por SPI, no he indagado todavía sobre el uso del DMA.

[planeta9999]

Si quieres que sea rápido, utiliza uno más simple todavía sobre una parte de la imagen (por ejemplo suma de los primeros 1024 bytes de la imagen). Eso va a ser 1000 veces más rápido.

En el caso de que el checksum simple coincida, puedes hacer una segunda ronda con CRC32 más lento para comprobar si realmente coinciden.

Así te quitas rápidamente de en medio muchas fotos y sólo tienes que hacer el CRC32 lento en unas pocas fotos.

Si el CRC32 lo puedes calcular con anterioridad y guardarlo en la propia foto (por ejemplo en la información EXIF), entonces lo más rápido es recuperarle directamente de la información EXIF sin calcular nada.

Saludos.

No es una imagen convencional, es una matriz de 128x32 o de 192x64, cada punto con un nivel de grises de 4 bits.

Se tiene que calcular muy rápido en tiempo real, porque si coincide el checksum con el guardado en una tabla, se tiene que leer un fichero en SD para reemplazar la imagen original monocroma, por una coloreada. Todo eso mientras esa animación sale por un display led, creo que a 60 fps o más.

[tsk]

En sí CRC32 es bastante rápido como para que tengas algún problema en conseguir más de 60fps. Me inclino a pensar en que vas a contar con una gran cantidad de imágenes por lo que estarías buscando una forma rápida y eficiente de recorrer la tabla en búsqueda del archivo. Aprovechando que vas a obtener el CRC32, este mismo lo podrías usar para crear una tabla hash, en lugar de un arreglo enorme.

Código: C

1. typdef struct file_p {
2.   char *filename;
3.   uint32_t crc32;
4.   file_p *next;
5. } file_p;

Código: C

1. file_p hash_table[32];

Entonces creas una función hash que sea bastante rápida que te permita añadir cada archivo en un slot de la tabla hash correspondiente. Esta función hash ya la tienes con el CRC32.

En el peor de los casos vas a tener que todo va a caer en un slot, pero eso no ocurre, en el mejor de los casos todos va a estar distribuidos de forma equitativa.

Así por ejemplo, si tienes 10000 imágenes, en el mejor de los casos reducirías la búsqueda a sólo 313 elementos tomando el caso de tener 32 slots en la tabla hash, y si tienes 64 a sólo 157. Son valores con los que tendrías que jugar y explorar como se comportan las imágenes que vas a usar.

Modifiqué mi código anterior para calcular el crc de los archivos en un directorio y asignarles su slot en la tabla hash.

Código: Python

1. POLY = 0x04C11DB7
2.  
3. custom_crc_table = {}
4.  
5. def int_to_bytes(i):
6.     return [(i >> 24) & 0xFF, (i >> 16) & 0xFF, (i >> 8) & 0xFF, i & 0xFF]
7.  
8.  
9. def generate_crc32_table(_poly):
10.  
11.     global custom_crc_table
12.  
13.     for i in range(256):
14.         c = i << 24
15.  
16.         for j in range(8):
17.             c = (c << 1) ^ _poly if (c & 0x80000000) else c << 1
18.  
19.         custom_crc_table[i] = c & 0xffffffff
20.  
21. def custom_crc32(buf):
22.  
23.     global custom_crc_table
24.     crc = 0xffffffff
25.     for integer in buf:
26.         b = [0,0,0,ord(integer)]
27.         for byte in b:
28.             crc = ((crc << 8) & 0xffffffff) ^ custom_crc_table[(crc >> 24) ^ byte]
29.  
30.     return crc
31.  
32.  
33. def calc_checksum(file_name):
34.     buf = open(file_name,"rb").read()
35.     #generate_crc32_table(POLY)
36.     custom_crc = custom_crc32(buf)
37.     return(hex(custom_crc), custom_crc)
38.  
39. if __name__ == "__main__":
40.     import sys
41.     import os
42.     generate_crc32_table(POLY)
43.     d = "/home/alex/Escritorio"
44.     files = os.listdir(d)
45.     f_counter = 0
46.     csv = open("hash_slots.txt","w")
47.     for f in files:
48.         f_path = os.path.join(d,f)
49.         if os.path.isfile(f_path) == True:
50.             f_counter +=1
51.             print(f_counter)
52.             ch,hs = calc_checksum(f_path)
53.             csv.write("%s\n"%(hs%32))
54.  
55.     csv.close()
56.     print(f_counter)
57.     #filename = sys.argv[1]
58.     #crc_hex,crc_int = calc_checksum(filename)
59.     #hash_slot = crc_int % 64;
60.     #print("crc = %s hash table slot: %d"%(crc_hex, hash_slot))

Tan sólo 165 archivos y su distribución es la siguiente



Con una función hash crc32 % 32, ya que son 32 slots en la tabla

[Picuino]

En vez de hacer una tabla con el checksum de las imágenes que quieres sustituir, marca la imagen a sustituir directamente o haz una tabla con núneros índice, más rápida.
No entiendo por qué quieres hacerlo en tiempo real, en vez de hacer el cálculo antes (por ejemplo al arrancar el micro)

Saludos.

[planeta9999]

Las imágenes no se pueden marcar de ninguna manera, las genera una máquina recreativa en tiempo real, se reciben en mi placa y se reemplazan por imágenes coloreadas.

A cada imagen recibida se le calcula su checksum y se búsca en una tabla, si está se reemplaza toda la animación completa, que está almacenada en una tarjeta SD, una animación puede tener muchos fotogramas. Solo es necesario identificar con checksum la primera imagen de la animación, el resto ya se reemplazan todas secuencilamente.

En un juego pueden haber unas 10-15 imágenes clave, que indican el inicio de una animación.

[Picuino]

Para identificar esas imágenes no hace falta tanto como un CRC32, con una simple suma de varios bytes centrales sería suficiente y rapidísimo.

Checksum simples:
Sumar todos los bytes en una palabra pequeña de 8 o 16 bits. Los desbordamientos o overflow se pierden.
XOR de todos los bytes entre sí
Suma y suma de sumas (Fletcher checksum) https://en.wikipedia.org/wiki/Fletcher%27s_checksum#Implementation
Combinaciones de los anteriores


Por otro lado, aquí rápido significa menos de 10 milisegundos y eso te lo da con creces un CRC32. Si tienes CRC32 por hardware, no te compliques y usalo. En caso contrario yo usaría los checksum simples de toda la vida y ni siquiera de toda la imagen.

Saludos.

[Picuino]

Si te interesa, los CRC16 por soft basados en tabla son muy rápidos en un ARM:

https://stackoverflow.com/questions/22432066/how-to-use-table-based-crc-16-code

Código: C

1. #include <stdio.h>
2.  
3. unsigned int crctable[256] =
4. {
5.    0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF,
6.    0x8C48, 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7,
7.    0x0919, 0x1890, 0x2A0B, 0x3B82, 0x4F3D, 0x5EB4, 0x6C2F, 0x7DA6,
8.    0x8551, 0x94D8, 0xA643, 0xB7CA, 0xC375, 0xD2FC, 0xE067, 0xF1EE,
9.    0x1232, 0x03BB, 0x3120, 0x20A9, 0x5416, 0x459F, 0x7704, 0x668D,
10.    0x9E7A, 0x8FF3, 0xBD68, 0xACE1, 0xD85E, 0xC9D7, 0xFB4C, 0xEAC5,
11.    0x1B2B, 0x0AA2, 0x3839, 0x29B0, 0x5D0F, 0x4C86, 0x7E1D, 0x6F94,
12.    0x9763, 0x86EA, 0xB471, 0xA5F8, 0xD147, 0xC0CE, 0xF255, 0xE3DC,
13.    0x2464, 0x35ED, 0x0776, 0x16FF, 0x6240, 0x73C9, 0x4152, 0x50DB,
14.    0xA82C, 0xB9A5, 0x8B3E, 0x9AB7, 0xEE08, 0xFF81, 0xCD1A, 0xDC93,
15.    0x2D7D, 0x3CF4, 0x0E6F, 0x1FE6, 0x6B59, 0x7AD0, 0x484B, 0x59C2,
16.    0xA135, 0xB0BC, 0x8227, 0x93AE, 0xE711, 0xF698, 0xC403, 0xD58A,
17.    0x3656, 0x27DF, 0x1544, 0x04CD, 0x7072, 0x61FB, 0x5360, 0x42E9,
18.    0xBA1E, 0xAB97, 0x990C, 0x8885, 0xFC3A, 0xEDB3, 0xDF28, 0xCEA1,
19.    0x3F4F, 0x2EC6, 0x1C5D, 0x0DD4, 0x796B, 0x68E2, 0x5A79, 0x4BF0,
20.    0xB307, 0xA28E, 0x9015, 0x819C, 0xF523, 0xE4AA, 0xD631, 0xC7B8,
21.    0x48C8, 0x5941, 0x6BDA, 0x7A53, 0x0EEC, 0x1F65, 0x2DFE, 0x3C77,
22.    0xC480, 0xD509, 0xE792, 0xF61B, 0x82A4, 0x932D, 0xA1B6, 0xB03F,
23.    0x41D1, 0x5058, 0x62C3, 0x734A, 0x07F5, 0x167C, 0x24E7, 0x356E,
24.    0xCD99, 0xDC10, 0xEE8B, 0xFF02, 0x8BBD, 0x9A34, 0xA8AF, 0xB926,
25.    0x5AFA, 0x4B73, 0x79E8, 0x6861, 0x1CDE, 0x0D57, 0x3FCC, 0x2E45,
26.    0xD6B2, 0xC73B, 0xF5A0, 0xE429, 0x9096, 0x811F, 0xB384, 0xA20D,
27.    0x53E3, 0x426A, 0x70F1, 0x6178, 0x15C7, 0x044E, 0x36D5, 0x275C,
28.    0xDFAB, 0xCE22, 0xFCB9, 0xED30, 0x998F, 0x8806, 0xBA9D, 0xAB14,
29.    0x6CAC, 0x7D25, 0x4FBE, 0x5E37, 0x2A88, 0x3B01, 0x099A, 0x1813,
30.    0xE0E4, 0xF16D, 0xC3F6, 0xD27F, 0xA6C0, 0xB749, 0x85D2, 0x945B,
31.    0x65B5, 0x743C, 0x46A7, 0x572E, 0x2391, 0x3218, 0x0083, 0x110A,
32.    0xE9FD, 0xF874, 0xCAEF, 0xDB66, 0xAFD9, 0xBE50, 0x8CCB, 0x9D42,
33.    0x7E9E, 0x6F17, 0x5D8C, 0x4C05, 0x38BA, 0x2933, 0x1BA8, 0x0A21,
34.    0xF2D6, 0xE35F, 0xD1C4, 0xC04D, 0xB4F2, 0xA57B, 0x97E0, 0x8669,
35.    0x7787, 0x660E, 0x5495, 0x451C, 0x31A3, 0x202A, 0x12B1, 0x0338,
36.    0xFBCF, 0xEA46, 0xD8DD, 0xC954, 0xBDEB, 0xAC62, 0x9EF9, 0x8F70
37. };
38.  
39. unsigned int CalculateCRC16( void *ptr, unsigned int len) {
40.    unsigned int crc = 0xFFFF;   // Initial Seed
41.    while (len--)  crc = (crc << 8) ^ crctable[((crc >> 8) ^ *ptr++)];
42.    return (crc);
43. }
44.  
45. int main() {
46.    printf("%d", CalculateCRC16("1234567890", 5));
47.    return 0;  
48. }

Saludos.

[tsk]

Pero cuando haces algo por software este siempre va a ser mas lento que por hardware.

Como referencia sobre la velocidad de cálculo del CRC

De http://www.st.com/content/ccc/resource/technical/document/application_note/39/89/da/89/9e/d7/49/b1/DM00068118.pdf/files/DM00068118.pdf/jcr:content/translations/en.DM00068118.pdf

– Hardware: STM32373C-EVAL board (STM32F37x device)
– System clock: HSE (8 MHz crystal oscillator)
– Toolchain: Keil V4.60.0.0
– CRC configurations: Default values of the CRC registers
CRC_CR: 0x0000 0000; POLYSIZE is 32, No REV_IN and No REV_OUT
CRC_INIT: 0XFFFF FFFF
CRC_POLY: 0X04D11 CDB7
– Input data: 256 words

Performance

CRC algorithm 78094 clock cycle
CRC peripheral 1287 clock cycle

El procesador es un STM32F373VC (ARM Cortex M4) que puede ir hasta los 72Mhz, así que tomando el tamaño de una de las imágenes más grandes de 192x64 px, de los cuales menciona que tienen un tamaño de 4 bits, de los cuales no se como los va a almacenar o como es que son envíados, pero tomando el caso que almacenarán 8 pixels por palabra, tendría que procesar un total de 1536 palabras.

Tomando en cuenta que puede procesar 256 palabras (32 bits) en 1287 ciclos de reloj (72Mhz), podría obtener el CRC de una imagen en 7722 ciclos de reloj o 0.10725ms, esto equivale a poder procesar un total de 9324 imágenes por segundo.

1 px por palabra daría la capacidad de procesar 1165 imágenes por segundo trabajando a 72Mhz, lo cual es bastante alto en comparación con los 60fps.

En forma práctica usando un stm32f103c8t6 (ARM Cortex M3) a 72MHz, calcula el crc de 2048 palabras en 0.257ms, por lo que si se usa 1px por palabra se traduciría en obtener el crc de una imagen de 192x64 en 1.542ms, este número puede ser ligeramente menor ya que las pruebas las realicé efectuando 1000 cálculos de crc en un arreglo de 2048 uint32_t, aunque si se almacenan 8 pixels por palabra, el tiempo se reduce a 0.2ms por imagen. Por así decirlo puede procesar alrededor 7.96887 millones de palabras por segundo lo que es un número considerablemente alto.

Código: [Seleccionar]

CRC 0x61B8C874, time: 257ms
CRC 0x61B8C874, time: 257ms
CRC 0x61B8C874, time: 257ms
Aunque es totalmente obvio que se va a usar otro MCU con mucha mayor potencia que este, lo que le daría una gran capacidad de procesamiento.

Checa este vídeo, es con un stm32f103

[planeta9999]

Estoy usando un Kinetis MK66 a 180 Mhz. No he encontrado informacion sobre calcular un checksum por hardware, creo que se puede, pero no se como.

En la librería CRC que tengo tambien esta CRC16  y creo que CRC8. No se si puedo usarlas o haria problemas de checksum repetidos para imsgenes distintas.

[tsk]

Estoy usando un Kinetis MK66 a 180 Mhz. No he encontrado informacion sobre calcular un checksum por hardware, creo que se puede, pero no se como.

En la librería CRC que tengo tambien esta CRC16  y creo que CRC8. No se si puedo usarlas o haria problemas de checksum repetidos para imsgenes distintas.

Usando el SDK de Kinetis

http://mcuxpresso.nxp.com/apidoc/2.0/group__crc__driver.html

Entre más pequeña sea la suma de verificación se incrementa la probabilidad de colisiones.

-----
Si estas usando el Teensy

https://github.com/FrankBoesing/FastCRC

Dice que usa el hardware CRC en los teensy

[planeta9999]

 
Ok, gracias tsk, lo probaré. Precisamente hace un momento ya había encontrado la librería FastCRC, y veo que tiene fuentes para calcular CRC por software y por hardware.

Estoy viendo un código fuente, de otro producto que hace lo mismo que yo quiero hacer, pero ellos usan MD5. Creo que CRC32 es bastante más rápido, y supongo que si lo calculo por hardware, será mucho más rapido que por software.

Mi duda ahora, es que si hago el cálculo del CRC32 por hardware en un Kinetis MK66, coincidirá con el checksum que calcule por software en un programa para PC, sobre el mismo fichero de imágenes. Tengo que editar e identificar las imágenes clave, en un programa de edición de las animaciones, este lo iba a hacer en principio en QT, pero al final va a ser un programa online por internet con acceso web. La cuestión es que ambos deben de calcular los mismos códigos usando CRC32 para las mismas imágenes. Por lo que he leído, los resultados pueden variar según que fórmulas se apliquen.