хеширование

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

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

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

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

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

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

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

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

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

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

Для реализации 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 от блока данных.

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

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

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

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

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