|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 18 Jan 2002 11:39:47
To : Arthur Vartanov
Subject : Re: Контрольные суммы или коды для обнаружения ошибок
--------------------------------------------------------------------------------
AV> 1. Строить алгоритмы по обнаружению
AV> (с заданной вероятностью) заданного
AV> количества ошибок в блоке данных определенной длины.
AV> Исправление ошибок не требуется.
AV> 2. Крайне желательно, чтобы
AV> полученные алгоритмы были
AV> наиболее просты в реализации в железе,
AV> т.е. использовались бы только операции сдвига,
AV> сложения по модулю 2, коньюнкции и дизьюнкции.
ща используется практически только CRC32 ...
Я его пробовал - мне не понравился, и сделал свой.
Работает он гораздо лучше, но использует
циклический сдвиг переменной длины (зависит от данных).
Это сложная операция для железа ?
производительности добился порядка 5 тактов на байт (на пне2)
для более длинных кусков данных
можно обрабатывать по DWORDам, но это менее качественно,
зато в 4 раза быстрее :)
Для кусков данных длиннее, чем ... где-то 32 байтов
(Hу и информативных хоть сколько-нить)
есть вот такой алгоритм - работает довольно хорошо на практике,
как ни странно ...
DWORD c1, c2;
for(...)
{
c1 += data[i];
c2 += c1;
}
return (любая вкусная смесь из c1 и с2 - например - (c1 ^ c2));
разумеется - можешь модифицировать как хошь ...
хошь - побольше бит сделай, чем DWORD ...
хошь - добавь c3 ...
хошь - извратись, и векторизируй -
ну - параллельно DWORDы обрабатывай -
будет БЫСТРЕЕ, но менее качественно,
хотя, для длинных строчек несущественно ...
Если нужно что-то более качественное - можно подумать ...
Вообще - можно взять любой криптохэш или шифр,
упростить (взять раундов поменьше, таблицу замен поменьше)
и получишь довольно хорошо работающий хэш ...
Имхо - для "достаточно случайных" данных
(например, архив, или зашифрованное)
подойдёт простое заXORивание ;-)
Я, правда давненько этим занимался ...
В итоге пришёл к такой схеме -
информация, передаваемая по сети
1. Сжимается.
2. Шифруется сцеплением блоков
3. Перед шифрованием добавляется
32(64) бит нулей в конец,
при дешифрование проверяется.
или просто заXORивание ...
работало хорошо ... даже очень.
Проверял качество хэшей так -
делал массив - хэш табличку
и проверял равномерность её заполнения.
Вопрос 2All -
мож я чего-то не так делал,
если с ходу сделаный самоделаный хеш
оказался ЛУЧШЕ, чем повсеместно используемый CRC32 ??
Всего наилучшего !
--
Отправлено через сервер Talk.Ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Контрольные суммы или коды для обнаружения ошибок