хеширование

[psb]

интересно, как в 4 байта сделать точность выше, чем у crc32?? crc32 - вполне себе хороший некриптографический хеш. изменение только одного входного бита сильно влияет на результат. так чего же еще нужно-то? если надо длиннее сам хеш и не хочется заморачиваться со сложными md5, sha, посчитайте тот же crc32 но задом-наперед. будет 8 байт хеша...

[jerri]

прошу прощения а разве crc32 не 4 байта занимает?

[Barmaley_m]

Автор, а почему, зачем тебе нужна "точность" выше, чем у CRC32? Какие ты можешь себе представить себе гипотетические ситуации, чтобы "точность" CRC32 оказалась недостаточной?

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

Для оценки хеш-фукнций с точки зрения защиты от случайных совпадений используется понятие "дистанция Хэмминга" - минимальное количество бит, которые необходимо инвертировать в исходных данных для получения хеш-коллиции. Имеется в виду инверсия не любых бит, а наиболее неудачное их сочетание. Для CRC32 дистанция Хэмминга составляет 6 бит, для XOR она составляет два бита, для ADD примерно столько же, для суммы Флетчера что-то среднее между 2 и 6 (3 кажется). Я некоторое время назад исследовал этот вопрос и пришел к выводу, что для обеспечения хорошей (некриптографической) защиты от коллизии следует использовать CRC, но этот алгоритм довольно затратен по вычислениям, поэтому, когда важна скорость, можно использовать сумму Флетчера.

---------- Post added at 22:15 ---------- Previous post was at 22:13 ----------

А вообще, автор, расскажи, зачем тебе нужен хеш, в какой ситуации ты планируешь его использовать? Может мы подскажем, что лучше, исходя из решаемой задачи.

[balu_dark]

Может человек переделывает платку Igrosoft раз упорно не признается для чего ему это. но для таких применений уже как раз нужен хотя бы MD5.

[mishutka]

Благодарю всех за ответы - я остановлюсь на crc32 - просьба - напишите на basice плз алгоритм как его подсчитать?

[jerri]

реализация на PC асмврядли на басике будет быстро

[Barmaley_m]

Для реализации CRC есть два варианта. Первый - быстрый, но использует память. Так, например, для CRC32 требуется 256*4 = 1024 байт памяти. Однако при этом удается избежать дорогостоящей операции побитового сдвига. Другой алгоритм, который не использует память, кроме как для счетчиков и текущего значения CRC, более приспособлен для применения в микроконтроллерах, где обычно очень мало памяти, однако этот алгоритм в несколько раз медленнее.

Вот быстрый алгоритм на 386 asm, который я использовал в своей программе CRC Wacher. На современных процах такой алгоритм может обрабатывать сотни мегабайт в секунду с неполной нагрузкой на проц. Автор программы - не я (нашел где-то в интернете исходник). Сначала требуется подготовить таблицу в памяти, это делает следующая программка:

// Build CRC table
DWORD* ctbl = crctable;
__asm
{
mov edx,ctbl;

xor ebx,ebx // table pointer
InitTableLoop:
xor eax,eax // eax=0 for new position
mov al,bl // low 8 bytes of ebx new position
xor cx,cx
entryLoop:
test eax,1
jz no_topbit
shr eax,1
xor eax,0xEDB88320 // poly
jmp entrygoon
no_topbit:
shr eax,1
entrygoon:
inc cx
test cx,8
jz entryLoop
mov dword ptr[ebx*4+edx],eax
inc ebx
test ebx,256
jz InitTableLoop
}

Та же подпрограмма, переведенная на язык С:
DWORD* edx = ctbl;
DWORD ebx = 0;
DWORD eax;
unsigned short cx;

do
{
eax = 0; // eax=0 for new position
eax = ebx & 0xFF; // low 8 bits of ebx new position
cx = 0;
do
{
if(eax & 1)
{
eax>>=1;
eax ^= 0xEDB88320; // poly
}
else
{
eax>>=1;
}
cx++;
} while(cx<8);
*(edx+ebx) = eax;
ebx++;
} while(ebx<256);

Для вычисления CRC, когда исходная таблица в памяти подготовлена, используется следующая программа (в двух вариантах, на асме и на си):
DWORD comp_crc(DWORD* crctbl, const char* data, DWORD inicrc, int dsize)
{
#ifdef _M_IX86
__asm
{
mov eax,inicrc
mov esi,data
mov ecx,dsize
mov edx,crctbl
xor ebx,ebx
compCrcLoop:
xor al,byte ptr[esi]
mov bl,al
shr eax,8
xor eax,dword ptr[4*ebx+edx]
inc esi
loop compCrcLoop
}
#else
DWORD eax = inicrc;
const unsigned char* esi = (const unsigned char*)data;
int ecx = dsize;
DWORD* edx = crctbl;
DWORD ebx = 0;

do
{
eax ^= *esi;
ebx = eax & 0x000000FF;
eax >>= 8;
eax ^= *(edx+ebx);
esi++;
} while(--ecx);
return eax;
#endif
}
аргументы программы:
crctbl - таблица, рассчитанная приведенной выше программой подготовки;
data - блок данных, по которым надо посчитать crc
inicrc - исходное значение CRC
dsize - размер данных, в байтах
возвращаемое значение - обновленное значение CRC

Данная программа позволяет обрабатывать большие блоки данных по частям. Сначала нужно проинициализировать исходное значение CRC числом FFFFFFFF. После этого нужно вызвать comp_crc для каждой части последовательно, при этом каждый раз обновляя текущее значение CRC. По окончании обработки большого файла текущее значение CRC нужно проинвертировать - это и будет искомый CRC32.

Если файл маленький и влезает в память целиком - то comp_crc нужно вызывать только один раз. Сценарий примерно такой:
DWORD crc = 0xFFFFFFFF;
crc = comp_crc(crctbl, data, crc, dsize);
crc = ~crc;
В результате исполнения этих трех строк в переменной crc будет значение crc32 от блока данных.

[mishutka]

Оно спасибо конечно за процедуры на x86, но хотелось бы увидеть ВЫЧИСЛЕНИЕ (а не табличное копирование) CRC32 на Sinclair Basic - скорость пускай вас не беспокоит

[psb]

на синклер-бейсике нет ни сдвигов, ни ксора... лучше посмотреть реализацию на си и понять смысл. там кратко и ёмко. а потом уже переписать на бейсик для понимания.

[jerri]

Ну ты конечно серьезно предлагаешь всем тут шевелить ушами через верхнюю левую пятку wiki

---------- Post added at 14:02 ---------- Previous post was at 13:57 ----------

вот тут еще пакет вариантов