Estoy buscando un algoritmo de suma de comprobación donde, para un gran bloque de datos, la suma de comprobación es igual a la suma de las sumas de comprobación de todos los bloques de componentes más pequeños. La mayoría de lo que he encontrado proviene de los RFC 1624/1141 que proporcionan esta funcionalidad. ¿Alguien tiene alguna experiencia con estas técnicas de sumas de verificación o similares?Sumas de verificación incrementales
Solo he usado sumas de comprobación Adler/Fletcher que funcionan como usted lo describe.
Hay una buena comparación de las implementaciones crypto ++ hash/checksum here.
He estado tratando de jugar con Adler y parece que no puedo obtener el resultado esperado, ¿quieres decir: 'adler ('wiki') + adler ('pedia')' debe producir el mismo resumen que 'adler ('wikipedia')', o ¿me estoy perdiendo algo? –
Para responder a la pregunta de amistad de Amigate Clark Kent, para propósitos de identificación de archivos es probable que desee una función hash criptográfica, que intenta garantizar que dos archivos tengan una probabilidad extremadamente baja de producir el mismo valor. generalmente se usa solo para la detección de errores y puede proporcionar el mismo valor para dos archivos muy diferentes.
Muchas funciones hash criptográficas, tales como MD5 y SHA-1, utilizar la Merkle–Damgård construction, en el que hay un cálculo para comprimir un bloque de datos en un tamaño fijo, y luego se combinan con un valor de tamaño fijo desde el bloque anterior (o un vector de inicialización para el primer bloque). Por lo tanto, son capaces de trabajar en un modo de transmisión, incrementalmente computando a medida que avanzan.
Si solo se trata de combinar rápidamente las sumas de comprobación de los bloques más pequeños para llegar a las sumas de comprobación del mensaje más grande (no necesariamente por suma simple) puede hacerlo con un algoritmo de tipo CRC (o similar).
El algoritmo CRC-32 es tan simple como esto:
uint32_t update(uint32_t state, unsigned bit)
{
if (((state >> 31)^bit) & 1) state = (state << 1)^0x04C11DB7;
else state = (state << 1);
return state;
}
Matemáticamente, el estado representa un polinomio sobre el GF2 campo que siempre se reduce el módulo del polinomio generador. Dado un nuevo bit b el viejo estado se transforma en el nuevo estado como este
state --> (state * x^1 + b * x^32) mod G
donde G es el polinomio generador y la adición se realiza en GF2 (xor). Esta suma de control es lineal en el sentido de que puede escribir el mensaje M como una suma (XOR) de los mensajes A, B, C, ... como esto
10110010 00000000 00000000 = A = a 00000000 00000000
00000000 10010001 00000000 = B = 00000000 b 00000000
00000000 00000000 11000101 = C = 00000000 00000000 c
-------------------------------------------------------------
= 10110010 10010001 11000101 = M = a b c
con las siguientes propiedades
M = A + B + C
checksum(M) = checksum(A) + checksum(B) + checksum(C)
Una vez más, me refiero al + en GF2 que puede implementar con un XOR binario.
Por último, es posible calcular checksum(B) basado en checksum(b) y la posición de la sub-bloque b relativa a B. La parte simple es liderar ceros. Los ceros a la izquierda no afectan en absoluto la suma de comprobación. Entonces checksum(0000xxxx) es lo mismo que checksum(xxxx). Si desea calcular la suma de comprobación de un mensaje de relleno cero (a la derecha -> ceros a la izquierda) dada la suma de verificación del mensaje no acolchado, es un poco más complicado.Pero no tan complicado:
zero_pad(old_check_sum, number_of_zeros)
:= (old_check_sum * x^{number_of_zeros} ) mod G
= (old_check_sum * (x^{number_of_zeros} mod G)) mod G
lo tanto, obtener la suma de comprobación de un mensaje rellena de ceros es sólo una cuestión de multiplicar la "suma de comprobación polinomio" del mensaje no acolchada con algún otro polinomio (x^{number_of_zeros} mod G) que sólo depende en la cantidad de ceros que quieres agregar Puede calcular esto previamente en una tabla o usar el algoritmo cuadrado y multiplicar para calcular rápidamente esta potencia.
Lectura recomendada: Painless Guide to CRC Error Detection Algorithms
¿Tiene que ser específicamente igual a la suma aritmética de las sumas de comprobación de los bloques más pequeños, o sólo de manera más general quiere ser capaz de calcular la suma de comprobación del bloque grande de la sumas de comprobación de los bloques más pequeños? –
Me parece que el problema de la suma de verificación se considera en la actualidad "principalmente resuelto" y a menudo se descarta como "obligado a IO" y, por lo tanto, no es interesante desde el punto de vista del rendimiento algorítmico. Pero OK, "IO obligado" es, ¿qué podemos hacer con IO? Bueno, si pudiéramos calcular los hashes mientras IO todavía está caliente en los cachés, estaría bien. –
@Amigable Clark Kent Quizás hubiera sido mejor abrir una nueva pregunta, con sus requisitos exactos, en lugar de hacer una copia de seguridad de una respuesta existente. ¿Estás buscando una suma de comprobación para detectar errores? ¿Estás buscando una función hash criptográfica? ¿Se requiere que la suma de comprobación esté compuesta de alguna combinación de las sumas de comprobación de cada bloque, como pregunta la pregunta original, o solo se requiere calcular la suma de comprobación de forma incremental en una secuencia de datos y dar una suma de comprobación para toda la secuencia una vez? ya terminaste? –