Algoritmos de checksum rápidos

[tsk]

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.

[Picuino]

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.

[planeta9999]

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.

[tsk]

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.

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

[Picuino]

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.

[Picuino]

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.

[tsk]

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.

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

[Picuino]

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.

[Picuino]

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.

[planeta9999]

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

[Picuino]

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.

[Picuino]

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.

[planeta9999]

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.