- Originally in SU.C_CPP
подскажите какую-нибудь простую хеш-функцию для 16-битной системы главное требование -- скорость
пока пользуюсь
uint hash(char buf, uint len) { uint r=0; for (uint i=0;i<len;i++) r=(r<<1)|buf[i]; return r; }
есть грабли ?
подскажите какую-нибудь простую хеш-функцию для 16-битной системы главное требование -- скорость
пока пользуюсь
uint hash(char buf, uint len) { uint r=0; for (uint i=0;i<len;i++) r=(r<<1)|buf[i]; return r; }
есть грабли ?
Hello, Dmitry! You wrote to All on Sun, 09 Apr 2006 18:09:48 +0400:
DP> подскажите какую-нибудь простую хеш-функцию для 16-битной системы DP> главное требование -- скорость DP> for (uint i=0;i<len;i++) r=(r<<1)|buf[i];
DP> есть грабли ? Лучше бы заменить ИЛИ на XOR, потому как иначе начиная со второго байта в среднем около половины битов (7/16) в хэш не попадают. А для ускорения можно сдвиг убрать и по 16 бит сразу считать:
uint r=0; uint* bufptr=(uint*)buf; for (uint i=0; i<len/2; i++) r ^= bufptr[i]; if(len & 0x01) r ^= buf[len-1]; return r;
With best regards, Sergey Zabelin. E-mail: snipped-for-privacy@telemak.ru
Привет, Sergey !
09 Apr 06 , 20:59 Sergey Zabelin писал к Dmitry Ponyatov:DP>> подскажите какую-нибудь простую хеш-функцию для 16-битной DP>> системы главное требование -- скорость for (uint i=0;i<len;i++) DP>> r=(r<<1)|buf[i];
DP>> есть грабли ? SZ> Лучше бы заменить ИЛИ на XOR, потому как иначе начиная со второго SZ> байта в среднем около половины битов (7/16) в хэш не попадают. А для SZ> ускорения можно сдвиг убрать и по 16 бит сразу считать:
SZ> uint r=0; SZ> uint* bufptr=(uint*)buf; SZ> for (uint i=0; i<len/2; i++) r ^= bufptr[i]; SZ> if(len & 0x01) r ^= buf[len-1]; SZ> return r;
'adc' - сложение с добавлением переноса - тоже вроде бы неплохой хэш?
. С уважением, Hикита. icq:240059686, lj-user:nicka_startcev ... Постепенно батарея и ужасно логорея он что-то куда-то вокзал
Привет Dmitry!
09 Apr 06 18:09, Dmitry Ponyatov писал All:DP> uint hash(char buf, uint len) DP> { DP> uint r=0; DP> for (uint i=0;i<len;i++) r=(r<<1)|buf[i]; DP> return r; DP> }
DP> есть грабли ?
Это вообще не хэш. При достаточной длине и случайности данных можно легко предсказать значение почти всех битов результата.
Всего наилучшего, [Team PCAD 2000] Алексей М. ... Я удалю твою жажду. Без возможности восстановления.
Привет Sergey!
09 Apr 06 20:59, Sergey Zabelin писал Dmitry Ponyatov:SZ> uint r=0; SZ> uint* bufptr=(uint*)buf; SZ> for (uint i=0; i<len/2; i++) r ^= bufptr[i]; SZ> if(len & 0x01) r ^= buf[len-1]; SZ> return r;
Это лучше, но позволяет "подогнать" данные под заранее известный хэш простым добавлением uint в любое место данных.
Всего наилучшего, [Team PCAD 2000] Алексей М. ... Программисты и программистки! Выше флаг промежуточного переноса!
Hello, Alex! You wrote to Dmitry Ponyatov on Mon, 10 Apr 2006 02:24:30 +0400:
AM> Это вообще не хэш. При достаточной длине и случайности данных можно легко AM> предсказать значение почти всех битов результата.
Собс-но, да. Сдвиг (арифметический) тоже недопустим, иначе в хеш попадают только последние 16 байт, и то не полностью
With best regards, Sergey Zabelin. E-mail: snipped-for-privacy@telemak.ru
Hello, Nickita! You wrote to Sergey Zabelin on Sun, 09 Apr 2006 23:55:54 +0400:
NA> 'adc' - сложение с добавлением переноса - тоже вроде бы неплохой хэш? На С неизящно реализуется, а так - тот же xor.
With best regards, Sergey Zabelin.
А чем CRC16 не угодил?
неправильно переписал, и ошибку не заметил:
t=r>>(sizeof(uint)*8-1),r=(r<<1)^buf[i]^t
// старший бит r заворачивается на младший
AF> А чем CRC16 не угодил?
пошустрее бы
Привет, Sergey !
10 Apr 06 , 04:41 Sergey Zabelin писал к Nickita A Startcev:NA>> 'adc' - сложение с добавлением переноса - тоже вроде бы неплохой NA>> хэш? SZ> Hа С неизящно реализуется, а так - тот же xor.
ага. вместо одного 'adc' получим штук пять операций.
. С уважением, Hикита. icq:240059686, lj-user:nicka_startcev ... Пятнистый шас Вирнус
Dmitry, ты ещё здесь сидишь?
Вторник Апрель 11 2006 20:18, Dmitry Ponyatov wrote to Anton Fedorov:
AF>> А чем CRC16 не угодил? DP> пошустрее бы
В допотопные времена в журнале Д-ра Добба приводился быстрый алгоритм формирования 2-х байтной сигнатуры. Сорри, название подзабыл, а текста под рукой нету. Кажется коды Флэтчера...
Георгий
XOR...
CRC16.
Есть. Значения должны быть более-менее равновероятно распределены. А у тебя постоянно 0xff там.
X-Virus-Scanned: amavisd-new at bezeqint.net
Hello, Kirill Frolov! You wrote in conference fido7.ru.embedded to Dmitry Ponyatov on Wed, 12 Apr 2006 17:35:37
+0000 (UTC):KF> XOR...
KF> CRC16.
Fletcher checksum, как я уже говорил в соседней конференции. Быстрее чем crc и не на много хуже.
dima
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.