Снова возникла потребность поупражняться в академическом программировании. На сей раз надо было научиться быстро сравнивать хеши 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.
inline bool bcmp(BYTE *a, BYTE *b, int n){ for (int i = 0; i < n; i++) if(b[i] ^ a[i]) return false; return true; }Важно отметить, что здесь используется слово "inline", что свидетельствует о использовании C++.
Соответственно, сравнение хешей выглядит так:
if ( bcmp(md5hash1, md5hash2, 16) ){ //Сделать что-то, если равны } else { //Сделать что-то, если не равны }
Поскольку программирование, все-таки, не основное мое занятие, более чем уверен, что у кого-то возникнут более оригинальные идеи сравнения. Буду очень признателен, если кто-то поделится, заранее спасибо.
2 comments:
Сравнение DWORD (или QWORD, если приложение 64-битное) выполняется процессором значительно быстрее, чем по-байтное - он всё равно данные выгребает не по байту, а бо́льшими кусками.
Я склонен думать, что функция сравнения должна зависеть от того, в каком виде возвращается хеш из функции его вычисления: если он возвращается как здесь:
http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5
в виде массива байтов, то и сравнивать разумно побайтово, к и предложено в посте.
Если функция возвращает хеш в виде массива 4-байтовых слов, как здесь:
http://nayuki.eigenstate.org/page/fast-md5-hash-implementation-in-x86-assembly
Тогда и функцию сравнения имеет смысл переписать как-то так:
inline bool bcmp4(uint32_t *a, uint32_t *b, int n){
for (int i = 0; i < n; i++)
if (b[i] ^ a[i]) return false;
return true;
}
Касательно глубины сравнения, как я и отметил в посте, - в подавляющем большинстве случаев разные хеши будут различаться с первого же байта, поэтому сравнение большими блоками (скажем, по 4 байта) имеет немного смысла, как мне кажется.
Post a Comment