Надежный и быстрый алгоритм контрольной суммы?

Если у вас много маленьких файлов, узким местом будет файловый ввод-вывод, а не алгоритм контрольной суммы.

Список хэш-функций (который можно рассматривать как контрольную сумму) можно найти в здесь.

Есть ли причина, по которой вы не можете использовать дату изменения файловой системы, чтобы определить, был ли изменен файл? Вероятно, это было бы быстрее.

CRC

• CRC-32 приходит на ум в основном потому, что его дешево вычислить

• Любой вид ввода-вывода приходит на ум в основном потому, что он будет ограничивающим фактором для такого предприятия;)

• Проблема не в вычислении контрольных сумм, проблема в том, чтобы загрузить изображения в память для вычисления контрольной суммы.

• Я бы посоветовал «пошаговый» мониторинг:

  • этап 1: проверьте наличие изменений временных меток файла и, если вы обнаружите изменение, передайте на ...
    (не требуется в вашем случае, как описано в отредактированной версии)

  • этап 2: забираем изображение в память и вычисляем контрольную сумму

• Конечно, также важно: многопоточность: настройка конвейера, который позволяет обрабатывать несколько изображений параллельно, если доступно несколько ядер ЦП.

Есть много быстрых алгоритмов CRC, которые должны помочь: http://www.google.com/search?hl=en&q=fast+crc&aq=f&oq=

Редактировать: Почему ненавидят? CRC полностью уместен, о чем свидетельствуют другие ответы. Поиск в Google также был уместен, поскольку язык не был указан. Это старая, старая проблема, которую решали столько раз, что вряд ли можно будет дать окончательный ответ.

adler32, доступный в заголовках zlib, рекламируется как значительно более быстрый, чем crc32, но лишь немного менее точный.

CRC32, вероятно, достаточно хорош, хотя есть вероятность маленький, что вы можете получить коллизию, так что файл, который был изменен, может выглядеть так, как будто его не было, потому что две версии генерируют одинаковую контрольную сумму. Поэтому, чтобы избежать этой возможности, я предлагаю использовать MD5, который легко будет достаточно быстрым, а вероятность возникновения коллизии снижена до точки, где она почти бесконечно мала.

Как уже говорили другие, с большим количеством небольших файлов вашим настоящим узким местом в производительности будет ввод-вывод, поэтому проблема заключается в этом. Если вы опубликуете еще несколько деталей, кто-то, вероятно, предложит способ разобраться и в этом.

Ваше самое важное требование - «проверить, не изменилось ли содержимое».

Если наиболее важно, чтобы было обнаружено ЛЮБОЕ изменение в файле, вам следует выбрать MD-5, SHA-1 или даже SHA-256.

Учитывая, что вы указали, что контрольная сумма НЕ является криптографически хорошей, я бы рекомендовал CRC-32 по трем причинам. CRC-32 дает хорошие расстояния для файла 8K. CRC-32 будет вычисляться как минимум на порядок быстрее, чем MD-5 (ваше второе требование). Иногда важно, что CRC-32 требует только 32 бита для хранения сравниваемого значения. MD-5 требует в 4 раза больше памяти, а SHA-1 - в 5 раз больше.

Кстати, любой метод будет усилен, если при вычислении хеша указать длину файла.

Согласно Wiki страница, на который указал Люк, MD5 на самом деле быстрее CRC32!

Я сам пробовал это, используя Python 2.6 в Windows Vista, и получил тот же результат.

Вот некоторые результаты:

crc32: 162,481544276 Мбит / с md5: 224,489791549 Мбит / с

crc32: 168.332996575 Мбит / с md5: 226.089336532 Мбит / с

crc32: 155,851515828 Мбит / с md5: 194.943289532 Мбит / с

Я тоже думаю над тем же вопросом, и у меня возникает соблазн использовать вариант Adler-32 Rsync для обнаружения различий в файлах.

Просто постскриптум к вышесказанному; jpeg использует сжатие с потерями, и степень сжатия может зависеть от программы, используемой для создания jpeg, цветовой палитры и / или битовой глубины в системе, гаммы дисплея, видеокарты и установленных пользователем уровней сжатия / настроек цвета. Поэтому сравнение JPEG, созданных на разных компьютерах / платформах или с использованием разного программного обеспечения, будет очень сложно на байтовом уровне.

Если вы получаете файлы по сети, вы можете вычислить контрольную сумму при получении файла. Это гарантирует, что вы рассчитаете контрольную сумму, пока данные находятся в памяти. Следовательно, вам не придется загружать их в память с диска.

Я считаю, что если вы примените этот метод, вы увидите почти нулевые накладные расходы в своей системе.

Это процедуры, которые я использую во встроенной системе, которая контролирует контрольную сумму прошивки и прочего.

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