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

Какой алгоритм контрольной суммы вы можете порекомендовать в следующем примере использования?

Я хочу создать контрольные суммы небольших файлов JPEG (~ 8 кБ каждый), чтобы проверить, изменилось ли содержимое. Использование измененной даты файловой системы, к сожалению, не является вариантом.
Контрольная сумма не должна быть криптографически сильной, но должна четко указывать изменения любого размера.

Второй критерий - скорость, так как в нем может обрабатываться как минимум сотни изображений в секунду (на современном процессоре).

Расчет будет выполнен на сервере с несколькими клиентами. Клиенты отправляют изображения через Gigabit TCP на сервер. Таким образом, нет дискового ввода/вывода как узкое место.

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

CRC

Ответ 4

CRC-32 возникает в виду, главным образом, потому что дешево рассчитать
Любой вид ввода-вывода возникает в основном потому, что это будет ограничивающим фактором для такого обязательства;)
Проблема заключается не в вычислении контрольных сумм, а в том, чтобы получить изображения в памяти для вычисления контрольной суммы.
Я бы предложил "ошеломленный" мониторинг:
- stage 1: проверьте изменения временных меток файла, и если вы обнаружите изменения, которые они переносят, чтобы...
  (не требуется в вашем случае, как описано в отредактированной версии)
- этап 2: получить изображение в память и вычислить контрольную сумму
Также важно: многопоточность: настройка конвейера, который позволяет обрабатывать несколько изображений параллельно, если доступно несколько ядер процессора.

Ответ 5

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

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

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

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

Самое важное требование - "проверить, изменился ли контент".

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

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

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

Ответ 9

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

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

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

crc32: 162.481544276 Мбит/с md5: 224.489791549 Мбит/с

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

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

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

Ответ 10

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