TODOPIC

Misceláneas - Interés General => Off Topic => Mensaje iniciado por: planeta9999 en 11 de Septiembre de 2017, 08:18:51

Título: Algoritmos de checksum rápidos
Publicado por: planeta9999 en 11 de Septiembre de 2017, 08:18:51


¿ 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
Título: Re:Algoritmos de checksum rápidos
Publicado por: KILLERJC en 11 de Septiembre de 2017, 10:42:10
El micro que estas utilizando no posee un modulo CRC el cual puedas enviarle por DMA los datos?
Título: Re:Algoritmos de checksum rápidos
Publicado por: tsk en 11 de Septiembre de 2017, 11:02:48
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/
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 11 de Septiembre de 2017, 11:35:50
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.
Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 11 de Septiembre de 2017, 12:44:50
Cita de: KILLERJC en 11 de Septiembre de 2017, 10:42:10
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.

(http://i.imgur.com/5oKKybD.jpg)

Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 11 de Septiembre de 2017, 13:19:02
Cita de: Picuino en 11 de Septiembre de 2017, 11:35:50
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.



Título: Re:Algoritmos de checksum rápidos
Publicado por: tsk en 11 de Septiembre de 2017, 14:35:24
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

(https://i.imgur.com/U09pWjLl.png)

Con una función hash crc32 % 32, ya que son 32 slots en la tabla
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 12 de Septiembre de 2017, 02:35:49
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.
Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 12 de Septiembre de 2017, 07:09:25


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.

Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 12 de Septiembre de 2017, 16:36:20
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.

Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 12 de Septiembre de 2017, 16:45:25
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.
Título: Re:Algoritmos de checksum rápidos
Publicado por: tsk en 12 de Septiembre de 2017, 20:16:09
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

Citar
– 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
Citar
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
Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 12 de Septiembre de 2017, 20:33:28

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.

Título: Re:Algoritmos de checksum rápidos
Publicado por: tsk en 12 de Septiembre de 2017, 20:42:13
Cita de: planeta9999 en 12 de Septiembre de 2017, 20:33:28

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
Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 12 de Septiembre de 2017, 21:10:14
 
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.
Título: Re:Algoritmos de checksum rápidos
Publicado por: tsk en 12 de Septiembre de 2017, 22:27:37
Por lo general no, ya que depende de las configuraciones, el polinomio, entre otras cosas, pero en su manual de referencia puedes ver como funciona, pero es bastante flexible el CRC del Kinetis como para que lo puedas configurar para que el resultado sea de alguna de las utilidades que se puedan encontrar ahí afuera.

https://www.nxp.com/docs/en/reference-manual/K66P144M180SF5RMV2.pdf ( hoja 915)

Y lo único es que lo tienes que replicar por software, probablemente alguien ya hizo el programa que genera el crc de acuerdo al kinetis.

Código: [Seleccionar]
>>> from PyCRC.CRC32 import CRC32
>>> hex(CRC32().calculate("12345"))
'0xcbf53a1c'

Código: [Seleccionar]
$ crc32 crcany/test.txt
261dafe6

De acuerdo a la forma de calcular del stm32

Código: [Seleccionar]
$ python crc2.py crcany/test.txt
crc = 0xe1ef3f35

https://www.lammertbies.nl/comm/info/crc-calculation.html
Código: [Seleccionar]
0xCBF53A1C

Es cuestion de que veas como calcula los valores Kinetis y lo intentes replicar. Hay una aplicación llamada srecord que supuestamente calcula el CRC para que se pueda agregar el bin que se va a subir al MCU, aunque sólo lo he usado para concatenar 2 .hex, así que no sabría como funciona realmente esa opción.
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 13 de Septiembre de 2017, 02:56:13
Insisto. Un CRC16 te va a dar 65536 combinaciones. De sobra para que no haya colisiónes en 10 imágenes.
El CRC32 te da más de 4000.000.000 combinaciones. Es como matar moscas a cañonazos. una colisión es casi imposible.

El cálculo CRC por software puede llegar a ser más rápido que por hardware si trabaja con tablas. No te fíes de ninguna comparativa de velocidad porque depende mucho. Al final lo mejor es que lo compares tú mismo con tus algoritmos. A mi me parece que el algoritmo CRC16 por soft que te he dejado puede llegar a ser más rápido y si algún dia cambias de micro, no dependes de que tenga CRC hardware.
Para 10 imagenes, incluso para muchas más, no te dará problemas.


Hay pocas combinaciones que pueden alterar el resultado del CRC y todas son estandar o se pueden averiguar. No te preocupes por eso. El CRC no es un algoritmo criptográfico, está diseñado para detectar pequeños errores de transmisión.

Saludos.
Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 13 de Septiembre de 2017, 06:26:56
Lo probaré, de todas formas no son 10 imágenes, esas son las que generan el disparo para reemplazar una animación, el proceso debe de calcular el cheksum de todas las imágenes que le entren y buscarlo en una tabla para ver si toca leer y cambiar la animación.

Un juego completo puede tener unas 20.000 imágenes de 128x32 o 192x64, cada punto con un nivel de grises de 4 bits (16 niveles).

Si con CRC32 va bien, lo dejaré por seguridad. Otro producto que hace algo parecido al mío, trabaja con MD5 y con un procesador más lento, un STM32F407 a 168Mhz, y les va bien. Además yo uso un tarjetero SD por SDIO a 4bit y el producto de la competencia lo tiene por SPI a 1 hilo. Si a ellos les va bién, con un procesador más lento, un algoritmo más pesado y un tarjetero más lento, a mi me debería de ir sin problemas.
Título: Re:Algoritmos de checksum rápidos
Publicado por: tsk en 13 de Septiembre de 2017, 10:46:39
Cita de: Picuino en 13 de Septiembre de 2017, 02:56:13
El cálculo CRC por software puede llegar a ser más rápido que por hardware si trabaja con tablas. No te fíes de ninguna comparativa de velocidad porque depende mucho. Al final lo mejor es que lo compares tú mismo con tus algoritmos. A mi me parece que el algoritmo CRC16 por soft que te he dejado puede llegar a ser más rápido y si algún dia cambias de micro, no dependes de que tenga CRC hardware.

A ver, quiero que me expliques como

Código: [Seleccionar]
while(len--) crc = (crc << 8) ^ crctable[((crc >> 8) ^ *ptr++)];

Puede ser más rápido que

Código: C
  1. /* Enter Data to the CRC calculator */
  2.   for(index = 0U; index < BufferLength; index++)
  3.   {
  4.     hcrc->Instance->DR = pBuffer[index];
  5.   }

Código: [Seleccionar]
80003f0: 6804      ldr r4, [r0, #0] ;2
 80003f2: f851 5023 ldr.w r5, [r1, r3, lsl #2] ;5
 80003f6: 6025      str r5, [r4, #0] ;2
 80003f8: 3301      adds r3, #1 ;1
 80003fa: 4293      cmp r3, r2 ;1
 80003fc: d3f8      bcc.n 80003f0 <HAL_CRC_Calculate+0x1e> ; 1 a 4
 
Para el bcc.n voy a considerar que usa 1 ciclo. Si los sumamos, nos dan un total de 9 ciclos de reloj.

Citar
F = 72Mhz
t = 1/F
c = 9
total_time_in_ms = t*c*2048*1000

Esto nos da un tiempo de 0.256ms, que es muy cercano a los 0.257ms que se obtuvieron con las pruebas en el hardware.

Por más tablas que uses, cuantas operaciones estas haciendo, cuantos accesos a memoria RAM estas realizando dentro del ciclo.

Primero tienes que leer el valor actual del CRC que está en memoria RAM, el acceso no es instantáneo
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 13 de Septiembre de 2017, 13:24:42
Si tienes ese número de imágenes, olvídate del CRC16. Puede darte un falso positivo con demasiada facilidad.

Tienes que ir a un CRC32. Si todavía tienes colisiones, puedes añadir también un Fletcher u otro.

tsk: no he dicho que en este caso sea más rápido. Depende de la velocidad del hardware y del software y del tamaño de la tabla.
Lo que si puedes ver en tu comparativa es que el CRC16 soft es casi tan rápido como el CRC32 hard.
Y el CRC32 soft no es más lento que el CRC16 por soft en un micro de 32 bit.

Por lo tanto la opción software no es tan lenta como ponías en un mensaje anterior.

Un saludo.
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 13 de Septiembre de 2017, 13:41:56
En cuanto al MD5 no tiene ningún sentido.
La única ventaja que tiene es que es muy largo y tiene menos colisiones, pero eso se puede conseguir de otras formas más sencillas.
Es un algoritmo criptográfico y por lo tanto innecesariamente lento y sin aceleración hardware.

Si el CRC32 te da colisiones (poco probable) puedes solucionarlo de otras maneras más sencillas, como añadir otro cálculo checksum rápido o calcular un CRC128, tan grande como el md5 y mucho más rápido.

Saludos.
Título: Re:Algoritmos de checksum rápidos
Publicado por: tsk en 13 de Septiembre de 2017, 17:16:08
Cita de: Picuino en 13 de Septiembre de 2017, 13:24:42
tsk: no he dicho que en este caso sea más rápido. Depende de la velocidad del hardware y del software y del tamaño de la tabla.
Lo que si puedes ver en tu comparativa es que el CRC16 soft es casi tan rápido como el CRC32 hard.
Y el CRC32 soft no es más lento que el CRC16 por soft en un micro de 32 bit.

Por lo tanto la opción software no es tan lenta como ponías en un mensaje anterior.

Un saludo.

Ve lo que pusiste, por eso mi incognita.

Citar
El cálculo CRC por software puede llegar a ser más rápido que por hardware si trabaja con tablas

Si lees el pdf, viene el diagrama del algoritmo que usaron, por eso lo puse, para que vieran contra que lo están comparando. Es claro que tu como fabricante siempre vas a alterar de alguna forma los resultados de tus pruebas e incluso comparar con los peores algoritmos.

Aquí está la estimación para el algoritmo que pusiste (que al final es similar al crc32)

Código: [Seleccionar]
8000f4c: 8802      ldrh r2, [r0, #0] ; 1
 8000f4e: ea82 2213 eor.w r2, r2, r3, lsr #8 ; 1
 8000f52: 4907      ldr r1, [pc, #28] ; (8000f70 <CalculateCRC16+0x2c>) 2
 8000f54: f931 2012 ldrsh.w r2, [r1, r2, lsl #1] ; 2
 8000f58: ea82 2303 eor.w r3, r2, r3, lsl #8; 1
 8000f5c: b29b      uxth r3, r3 ; 1
 8000f5e: 4621      mov r1, r4 ;1
 8000f60: 3002      adds r0, #2 ;1
 8000f62: 1e4c      subs r4, r1, #1 ; 1
 8000f64: 2900      cmp r1, #0 ;1
 8000f66: d1f1      bne.n 8000f4c <CalculateCRC16+0x8> ;1
 
 Tomando en cuenta que el sitio de ARM coloca

 
Código: [Seleccionar]
EOR Rd, Rn, <op2>
 dode <op2> puede ser

 
Código: [Seleccionar]
#0xXXXXX - Valor inmediato
 Rm - Registro
 Rm, LSL #8 - Shift inmediato
 Rm, LSL Rs
 
Con un tiempo de ejecución de 1 ciclo de reloj. Tendrías un aproximado de 13 ciclos de reloj, lo que te daría un aproximado de 0.3698ms por  cada 2048 palabras, lo que al final te representaría alrededor de 2.22ms para procesar una imagen, contra los 1.542ms por usarlo en hardware.

Ahora vamos a la práctica:

Los dos en las mismas condiciones, 1000 repeticiones dentro de un ciclo for

Código: [Seleccionar]
CRC16 time: 601ms
CRC32 time: 286ms

Porque subió el tiempo en CRC32, con respecto a los anteriores, porque estoy tomando encuenta todo el ciclo for.
¿Porqué el tiempo en el CRC16 sube más de lo que se espera (0.3698 a 0.601)?

Tengo la impresión que es aquí.
Código: [Seleccionar]
8000f52: 4907      ldr r1, [pc, #28] ; (8000f70 <CalculateCRC16+0x2c>) 2
 8000f54: f931 2012 ldrsh.w r2, [r1, r2, lsl #1] ; 2

Hay dependencia, y como estos trabaja a través de un pipeline le tenemos que agregar unos cuantos ciclos mas.

Saludos
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 14 de Septiembre de 2017, 02:29:17
Ok. Mi experiencia viene de micros de 8 bits y hardware antiguo. Veo que con los micros de 32 bits las optimizaciones harware y software cambian bastante los resultados respecto a los micros pequeños.

Para planeta:
la velocidad de soft es suficiente como para que puedas hacer el cálculo por programa si acaso algún dia cambias de micro y no tiene modulo CRC hardware.

Saludos.
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 14 de Septiembre de 2017, 02:45:29
Planeta, he hecho un pequeño cálculo de probabilidades.
La probabilidad de que de 20000 fotos diferentes alguna te de el mismo CRC32 que el de las 10 fotos a identificar es de 0,005%.

Si quieres identificar 100 fotos, la probabilidad de colision sube a 0,05%

No creo que vayas a tener problemas. Si te quieres asegurar más, vete a un CRC64 y será más fácil que un meteorito acabe con la vida en la tierra a que tengas una colisión entre fotos.

También puedes utilizar técnicas de aceleración. Guarda también el CRC de los primeros 10 bytes de las imágenes buenas. Si no coincide, descartas la mayoría de las imágenes con un cálculo mínimo.

Saludos.
Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 14 de Septiembre de 2017, 03:17:45


Con CRC32 creo que me arreglaré bien, como tengo la librería para usarlo por software y por hardware (con Kinetis), probaré los dos.

Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 14 de Septiembre de 2017, 11:34:33
Hay dos parámetros para que ambos coincidan.

Por un lado el polinomio. No hay muchos donde elegir.
En Wikipedia aparecen 4 para el CRC32: https://en.wikipedia.org/wiki/Polynomial_representations_of_cyclic_redundancy_checks


Por otro lado se puede seleccionar la semilla o seed. Es el valor inicial del CRC32 con el que comienzas. Puede ser cero, pero se suele colocar otro valor. Las posibilidades son muchas (4000 millones), pero en la práctica se suele inicializar con el valor 0xFFFFFFFF

Un saludo.
Título: Re:Algoritmos de checksum rápidos
Publicado por: Picuino en 14 de Septiembre de 2017, 11:41:19
Se me olvidaba.

¿Puedes encontrarte algún caso en el que la máquina que envía las fotos quiera engañar a tu circuito?
Esto es, enviarte una imagen distinta que tenga a propósito el mismo CRC32 de otra imagen clave.

Por ejemplo, porque el que diseña la máquina quiere dejar en mal lugar el rendimiento de tu circuito.

En ese caso si deberías utilizar hash criptográficos y calcular un SHA-256 (el MD5 se quedaría corto). Eso si, va a ser bastante más lento.

Saludos.
Título: Re:Algoritmos de checksum rápidos
Publicado por: planeta9999 en 14 de Septiembre de 2017, 11:52:03
Cita de: Picuino en 14 de Septiembre de 2017, 11:41:19
Se me olvidaba.

¿Puedes encontrarte algún caso en el que la máquina que envía las fotos quiera engañar a tu circuito?
Esto es, enviarte una imagen distinta que tenga a propósito el mismo CRC32 de otra imagen clave.

Por ejemplo, porque el que diseña la máquina quiere dejar en mal lugar el rendimiento de tu circuito.


No, eso no puede pasar, son máquinas recreativas de los años 90, entonces ni siquiera existían los paneles LED RGB.