algorithm - pseint - diagrama de flujo suma de numeros pares e impares

¿Algoritmo de suma de comprobación robusto y rápido?

Question

¿Qué algoritmo de suma de comprobación puede recomendar en el siguiente caso de uso?

Quiero generar sumas de comprobación de pequeños archivos JPEG (~ 8 kB cada uno) para verificar si el contenido ha cambiado. Lamentablemente, no es una opción utilizar la fecha del sistema de archivos modificada .
La suma de comprobación no necesita ser criptográficamente fuerte, pero debe indicar de forma robusta los cambios de cualquier tamaño.

El segundo criterio es la velocidad, ya que debería ser posible procesar al menos cientos de imágenes por segundo (en una CPU moderna).

El cálculo se realizará en un servidor con varios clientes. Los clientes envían las imágenes a través de Gigabit TCP al servidor. Entonces, no hay E / S de disco como cuello de botella.

Answer 1

Es probable que CRC32 sea lo suficientemente bueno, aunque hay pocas posibilidades de que se produzca una colisión, por lo que un archivo que se modificó podría parecer que no lo fue porque las dos versiones generan la misma suma de comprobación. Para evitar esta posibilidad, sugiero usar MD5, que será lo suficientemente rápido, y las posibilidades de que se produzca una colisión se reducen hasta el punto en que es casi infinito.

Como han dicho otros, con muchos archivos pequeños, su cuello de botella de rendimiento real va a ser E / S, así que el problema es lidiar con eso. Si publica algunos detalles más, es probable que alguien sugiera una forma de solucionarlo también.

Answer 2

Hay muchos algoritmos rápidos de CRC que deberían hacer el truco: http://www.google.com/search?hl=es&q=fast+crc&aq=f&oq=

Editar: ¿Por qué el odio? CRC es totalmente apropiado, como lo demuestran las otras respuestas. Una búsqueda en Google también fue apropiada, ya que no se especificó ningún idioma. Este es un viejo y viejo problema que se ha resuelto tantas veces que no es probable que haya una respuesta definitiva.

Answer 3

Si tiene muchos archivos pequeños, su cuello de botella será E / S de archivo y probablemente no un algoritmo de suma de comprobación.

Aquí se puede encontrar una lista de funciones hash (que se puede considerar como una suma de comprobación).

¿Hay alguna razón por la que no pueda usar la fecha del sistema de archivos modificada para determinar si un archivo ha cambiado? Eso probablemente sería más rápido.

Answer 4

CRC

Answer 5

Su requisito más importante es "verificar si el contenido ha cambiado".

Si es muy importante que se detecte CUALQUIER cambio en el archivo, MD-5, SHA-1 o incluso SHA-256 deberían ser su elección.

Dado que usted indicó que la suma de comprobación NO es criptográficamente buena, recomendaría CRC-32 por tres razones. CRC-32 da buenas distancias de hamming sobre un archivo de 8K. CRC-32 será al menos un orden de magnitud más rápido que el MD-5 para calcular (su segundo requisito). A veces, como es importante, CRC-32 solo requiere 32 bits para almacenar el valor que se va a comparar. MD-5 requiere 4 veces el almacenamiento y SHA-1 requiere 5 veces el almacenamiento.

Por cierto, cualquier técnica se reforzará anteponiendo la longitud del archivo al calcular el hash.

Answer 6

De acuerdo con la página Wiki señalada por Luke, ¡MD5 es en realidad más rápido que CRC32!

Lo intenté usando Python 2.6 en Windows Vista y obtuve el mismo resultado.

Aquí hay algunos resultados:

crc32: 162.481544276 MBps md5: 224.489791549 MBps

crc32: 168.332996575 MBps md5: 226.089336532 MBps

crc32: 155.851515828 MBps md5: 194.943289532 MBps

Estoy pensando en la misma pregunta también, y estoy tentado de usar la variación de Adler-32 de Rsync para detectar diferencias de archivos.

Answer 7

Solo una postdata a lo anterior; jpegs usa compresión con pérdida y la extensión de la compresión puede depender del programa utilizado para crear el jpeg, la paleta de colores y / o profundidad de bits en el sistema, mostrar gamma, tarjeta gráfica y niveles de compresión / configuración de color configurados por el usuario. Por lo tanto, comparar jpegs construidos en diferentes computadoras / plataformas o usar diferentes software será muy difícil en el nivel de bytes.

Answer 8

• CRC-32 viene a la mente principalmente porque es barato de calcular

• Cualquier tipo de E / S viene a la mente principalmente porque este será el factor limitante para tal empresa;)

• El problema no es calcular las sumas de comprobación, el problema es obtener las imágenes en la memoria para calcular la suma de comprobación.

• Yo sugeriría un monitoreo "escalonado":

  • etapa 1: verifique los cambios de las marcas de tiempo de los archivos y si detecta un cambio, entregue a ...
    (no es necesario en su caso como se describe en la versión editada)

  • Etapa 2: obtener la imagen en la memoria y calcular la suma de comprobación

• También es importante: multihilo : configuración de una tubería que permite procesar varias imágenes en paralelo si hay varios núcleos de CPU disponibles.

Answer 9

Si está recibiendo los archivos en la red, puede calcular la suma de comprobación a medida que recibe el archivo. Esto asegurará que usted calculará la suma de verificación mientras los datos están en la memoria. Por lo tanto, no tendrá que cargarlos en la memoria del disco.

Creo que si aplica este método, verá una sobrecarga de casi cero en su sistema.

Estas son las rutinas que estoy usando en un sistema integrado que hace control de suma de comprobación en el firmware y otras cosas.

static const uint32_t crctab[] = {
    0x0,
    0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
    0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6,
    0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
    0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, 0x5f15adac,
    0x5bd4b01b, 0x569796c2, 0x52568b75, 0x6a1936c8, 0x6ed82b7f,
    0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 0x709f7b7a,
    0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
    0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58,
    0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033,
    0xa4ad16ea, 0xa06c0b5d, 0xd4326d90, 0xd0f37027, 0xddb056fe,
    0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
    0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 0xe13ef6f4,
    0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
    0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5,
    0x2ac12072, 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
    0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca, 0x7897ab07,
    0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb, 0x6f52c06c,
    0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1,
    0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
    0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b,
    0xbb60adfc, 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698,
    0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044, 0x902b669d,
    0x94ea7b2a, 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
    0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 0xc6bcf05f,
    0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
    0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80,
    0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
    0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, 0x5c007b8a,
    0x58c1663d, 0x558240e4, 0x51435d53, 0x251d3b9e, 0x21dc2629,
    0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 0x3f9b762c,
    0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
    0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e,
    0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65,
    0xeba91bbc, 0xef68060b, 0xd727bbb6, 0xd3e6a601, 0xdea580d8,
    0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
    0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 0xae3afba2,
    0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
    0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74,
    0x857130c3, 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
    0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c, 0x7b827d21,
    0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd, 0x6c47164a,
    0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 0x18197087,
    0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
    0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d,
    0x2056cd3a, 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce,
    0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb,
    0xdbee767c, 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
    0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 0x89b8fd09,
    0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
    0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf,
    0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
};

typedef struct crc32ctx
{
    uint32_t crc;
    uint32_t length;
} CRC32Ctx;


#define COMPUTE(var, ch)    (var) = (var) << 8 ^ crctab[(var) >> 24 ^ (ch)]

void crc32_stream_init( CRC32Ctx* ctx )
{
    ctx->crc = 0;
    ctx->length = 0;
}

void crc32_stream_compute_uint32( CRC32Ctx* ctx, uint32_t data )
{
    COMPUTE( ctx->crc, data & 0xFF );
    COMPUTE( ctx->crc, ( data >> 8 ) & 0xFF );
    COMPUTE( ctx->crc, ( data >> 16 ) & 0xFF );
    COMPUTE( ctx->crc, ( data >> 24 ) & 0xFF );
    ctx->length += 4;
}

void crc32_stream_compute_uint8( CRC32Ctx* ctx, uint8_t data )
{
    COMPUTE( ctx->crc, data );
    ctx->length++;
}

void crc32_stream_finilize( CRC32Ctx* ctx )
{
    uint32_t len = ctx->length;
    for( ; len != 0; len >>= 8 )
    {
        COMPUTE( ctx->crc, len & 0xFF );
    }
    ctx->crc = ~ctx->crc;
}

/*** pseudo code ***/
CRC32Ctx crc;
crc32_stream_init(&crc);

while((just_received_buffer_len = received_anything()))
{
    for(int i = 0; i < just_received_buffer_len; i++)
    {
        crc32_stream_compute_uint8(&crc, buf[i]); // assuming buf is uint8_t*
    }
}
crc32_stream_finilize(&crc);
printf("%x", crc.crc); // ta daaa

Answer 10

adler32, disponible en los encabezados de zlib, se anuncia como significativamente más rápido que crc32, aunque solo es un poco menos preciso.