Снова возникла потребность поупражняться в академическом программировании. На сей раз надо было научиться быстро сравнивать хеши MD5 .
Обычно при слове "MD5" перед глазами встает шестнадцатеричное представление 16-байтного числа, т.е. последовательно типа "7b68b20e5f46971e9daab02208c53f2c", поэтому первая идея сравнения была - сравнение двух 32-символьных срок с использованием strncmp .
Если наша хеширующая фунция возвращает MD5 не как строку, а как массив байтов (все нормальные функции именно так и делают), как например, здесь , то представляется совсем неразумным каждый раз рассчитав 16-и байтовый хеш, преобразовывать его в 32-символьную строку только для возможности выполнить сравнение. Ситуация особенно ухудшается, если нам надо выполнить миллион сравнений, - у нас будет миллион ненужных преобразований в строку.
Поэтому, второй мыслью было сравнение двух бинарных 16-байтных массивов с использованием memcmp . По скорости она примерно такая же как strncmp (разве что сейчас мы сравниваем 16 байтов, а выше сравнивали 32 байта), однако нет необходимости преобразовывать MD5 в строку исключительно для возможности сравнения.
Но и этот вариант показался тоже не оптимальным, поскольку memcmp слишком продвинута, чем это необходимо для нашей задачи - всего-то понять, идентичны хеши или нет, - мне не надо знать какой из них больше, а какой меньше.... Более того, с большой степенью вероятности разные хеши будут различаться с первого же байта, причем эта вероятность будет стремительно расти продвигаясь побайтово по хешу....
Все это навело на мысль следующей простой функции, которая, как мне показалось, продемонстрировала большую производительность чем memcmp и strncmp.
Соответственно, сравнение хешей выглядит так:
Поскольку программирование, все-таки, не основное мое занятие, более чем уверен, что у кого-то возникнут более оригинальные идеи сравнения. Буду очень признателен, если кто-то поделится, заранее спасибо.
Обычно при слове "MD5" перед глазами встает шестнадцатеричное представление 16-байтного числа, т.е. последовательно типа "7b68b20e5f46971e9daab02208c53f2c", поэтому первая идея сравнения была - сравнение двух 32-символьных срок с использованием strncmp .
Если наша хеширующая фунция возвращает MD5 не как строку, а как массив байтов (все нормальные функции именно так и делают), как например, здесь , то представляется совсем неразумным каждый раз рассчитав 16-и байтовый хеш, преобразовывать его в 32-символьную строку только для возможности выполнить сравнение. Ситуация особенно ухудшается, если нам надо выполнить миллион сравнений, - у нас будет миллион ненужных преобразований в строку.
Поэтому, второй мыслью было сравнение двух бинарных 16-байтных массивов с использованием memcmp . По скорости она примерно такая же как strncmp (разве что сейчас мы сравниваем 16 байтов, а выше сравнивали 32 байта), однако нет необходимости преобразовывать MD5 в строку исключительно для возможности сравнения.
Но и этот вариант показался тоже не оптимальным, поскольку memcmp слишком продвинута, чем это необходимо для нашей задачи - всего-то понять, идентичны хеши или нет, - мне не надо знать какой из них больше, а какой меньше.... Более того, с большой степенью вероятности разные хеши будут различаться с первого же байта, причем эта вероятность будет стремительно расти продвигаясь побайтово по хешу....
Все это навело на мысль следующей простой функции, которая, как мне показалось, продемонстрировала большую производительность чем memcmp и strncmp.
inlinebool bcmp(BYTE *a, BYTE *b, int n){Важно отметить, что здесь используется слово "inline", что свидетельствует о использовании C++.
for (int i = 0; i < n; i++)
if(b[i] ^ a[i])
return false;
return true;
}
Соответственно, сравнение хешей выглядит так:
if ( bcmp(md5hash1, md5hash2, 16) ){
//Сделать что-то, если равны
}
else {
//Сделать что-то, если не равны
}
Поскольку программирование, все-таки, не основное мое занятие, более чем уверен, что у кого-то возникнут более оригинальные идеи сравнения. Буду очень признателен, если кто-то поделится, заранее спасибо.
