хеш-функция

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 !

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!

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!

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 !

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

KF> XOR...

KF> CRC16.

Fletcher checksum, как я уже говорил в соседней конференции. Быстрее чем crc и не на много хуже.

dima