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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

• CRC-32 имеет в виду, главным образом, потому что это дешево для вычисления

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

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

• Я бы предложил "постановочный" мониторинг:

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

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

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

Answer 4

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

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

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

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 5

CRC

Answer 6

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

Answer 7

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

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

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

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

Answer 8

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

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

Answer 9

По словам Вики страницы , на которую указывает Люк, 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 для обнаружения различий в файлах.

Answer 10

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