Algorithme de checksum robuste et rapide?

Question

Quel algorithme de somme de contrôle pouvez-vous recommander dans le cas d'utilisation suivant?

Je souhaite générer des sommes de contrôle de petits fichiers JPEG (environ 8 ko chacun) pour vérifier si le contenu a changé. Utiliser la date de modification du système de fichiers n'est malheureusement pas une option.
La somme de contrôle ne doit pas nécessairement être cryptographiquement puissante, mais elle doit indiquer de manière robuste les modifications, quelle que soit leur taille.

Le deuxième critère est la vitesse , car il devrait être possible de traiter au moins centaines d'images par seconde (sur un processeur moderne).

Le calcul sera effectué sur un serveur avec plusieurs clients. Les clients envoient les images via Gigabit TCP au serveur. Il n'y a donc pas d'E / S de disque en tant que goulot d'étranglement.

Answer 1

Si vous avez beaucoup de petits fichiers, votre goulot d'étranglement sera un fichier d'E / S et probablement pas un algorithme de somme de contrôle.

Une liste des fonctions de hachage (qui peuvent être considérées comme une somme de contrôle) peut être trouvée ici .

Y a-t-il une raison pour laquelle vous ne pouvez pas utiliser la date du système de fichiers modifiée pour déterminer si un fichier a été modifié? Ce serait probablement plus rapide.

Answer 2

Il existe de nombreux algorithmes de CRC rapides qui devraient faire l'affaire: http://www.google.com/search?hl=fr& q = fast + crc & aq = f & amp; oq =

Modifier: Pourquoi cette haine? Le CRC est tout à fait approprié, comme en témoignent les autres réponses. Une recherche sur Google était également appropriée, car aucune langue n'était spécifiée. C’est un vieux problème qui a été résolu tant de fois qu’il n’ya probablement pas de réponse définitive.

Answer 3

• CRC-32 vient à l’esprit principalement parce que son calcul est peu coûteux

• Tout type d’E / S vient à l’esprit principalement parce que ce sera le facteur limitant pour une telle entreprise;)

• Le problème n'est pas de calculer les sommes de contrôle, le problème est de mettre les images en mémoire pour calculer le total de contrôle.

• Je suggérerais "en quinconce". suivi:

  • étape 1: recherchez les modifications d'horodatage des fichiers et, si vous détectez une modification, passez le relais à ...
    (inutile dans votre cas comme décrit dans la version modifiée)

  • étape 2: récupérer l’image en mémoire et calculer la somme de contrôle

• Bien sûr, il est également important: multi-threading : configuration d'un pipeline permettant le traitement de plusieurs images en parallèle si plusieurs cœurs de processeur sont disponibles.

Answer 4

CRC

Answer 5

Si vous recevez les fichiers sur le réseau, vous pouvez calculer la somme de contrôle au fur et à mesure que vous recevez le fichier. Cela garantira que vous calculerez la somme de contrôle pendant que les données sont en mémoire. Par conséquent, vous n’avez pas à les charger en mémoire à partir du disque.

Je pense que si vous appliquez cette méthode, votre système ne subira quasiment plus de frais généraux.

Il s’agit des routines que j’utilise sur un système intégré qui permet le contrôle de la somme de contrôle sur les microprogrammes et d’autres éléments.

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 6

adler32, disponible dans les en-têtes zlib, est présenté comme étant nettement plus rapide que crc32, tout en étant légèrement moins précis.

Answer 7

CRC32 est probablement suffisant, bien qu'il y ait une petite possibilité de collision, de sorte qu'un fichier modifié peut sembler ne pas l'être car les deux versions génèrent le même somme de contrôle. Pour éviter cette éventualité, je suggèrerais donc d'utiliser MD5, qui sera facilement assez rapide, et les risques de collision sont réduits au point de devenir presque infinis.

Comme d’autres l’ont dit, avec beaucoup de petits fichiers, votre véritable goulot d’étranglement en termes de performances créera des E / S, c’est pourquoi le problème est résolu. Si vous publiez quelques détails supplémentaires, quelqu'un vous proposera probablement également un moyen de résoudre ce problème.

Answer 8

Votre exigence la plus importante est "de vérifier si le contenu a été modifié".

S'il est primordial de détecter tout changement dans le fichier, choisissez MD-5, SHA-1 ou même SHA-256.

Étant donné que vous avez indiqué que la somme de contrôle N'EST PAS cryptographiquement satisfaisante, je recommanderais CRC-32 pour trois raisons. Le CRC-32 donne de bonnes distances de frappe sur un fichier de 8K. Le CRC-32 sera au moins un ordre de grandeur plus rapide que le MD-5 à calculer (votre deuxième exigence). Parfois aussi important, CRC-32 ne nécessite que 32 bits pour stocker la valeur à comparer. Le MD-5 nécessite 4 fois plus de stockage et le SHA-1 5 fois plus.

BTW, toute technique sera renforcée en ajoutant la longueur du fichier lors du calcul du hachage.

Answer 9

Selon la page du Wiki à laquelle Luke fait référence, MD5 est en réalité plus rapide que CRC32!

J'ai moi-même essayé cela en utilisant Python 2.6 sur Windows Vista et j'ai obtenu le même résultat.

Voici quelques résultats:

crc32: 162,481544276 Mbps md5: 224,489791549 Mbps

crc32: 168.332996575 Mbps md5: 226.089336532 Mbps

crc32: 155.851515828 Mbps md5: 194,943289532 Mbps

Je réfléchis également à la même question et je suis tenté d'utiliser la variante d'Adler-32 de Rsync pour détecter les différences entre les fichiers.

Answer 10

Juste un post-scriptum à ce qui précède; Les jpeg utilisent une compression avec perte et l'ampleur de la compression peut dépendre du programme utilisé pour créer le jpeg, la palette de couleurs et / ou la profondeur de bits sur le système, l'affichage gamma, la carte graphique et les niveaux de compression / paramètres de couleur définis par l'utilisateur. Par conséquent, il sera très difficile de comparer les fichiers JPEG créés sur différents ordinateurs / plates-formes ou à l'aide de logiciels différents au niveau des octets.