[zombi 0]

Господа, посоветуйте быстрый алгоритм подсчета CRC блока 32кБ.

CRC16,CRC32...MD5 не подходят из за большого времени счёта.

По быстродействию устраивает одно чтение байта и одна (максимум 2) операция с ним.

 

Реализовал вот так.

Весь блок рассматриваю как последовательность 8-ми байтных целых чисел и просто их суммирую.

В результате CRC тоже 8-мь байт.

Вопрос: если CRC сделать не восемь а девять или десять байт, будет ли надёжнее?

 

А может кто то предложит еще какой то быстрый алгоритм?

[vvs157 0]

Весь блок рассматриваю как последовательность 8-ми байтных целых чисел и просто их суммирую.

В результате CRC тоже 8-мь байт.

Это не совсем CRC, это простая контрольная сумма, которая в отличие от CRC невосприимчива к перестановке байт.

[kovigor 5]

А может кто то предложит еще какой то быстрый алгоритм?

"Табличная" реализация расчета CRC имеется в той же Википедии и работает достаточно быстро. Может, вам лучше заменить МК на более производительный ? Или, если позволяет задача, можно подсчитывать CRC "на лету", подавая на вход вычислителя все новые и новые байты по мере их поступления в 32 - килобайтный массив ...

[demiurg_spb 0]

Быстрее и надёжнее стандартного табличного CRC вы вряд ли изобретёте. ИМХО.

Если конечно не будете использовать аппаратный блок микроконтроллера для расчёта CRC как например в STM32.

[_Pasha 0]

Процессор 8-разрядный?

Тогда возьмите CRC16 из модбаса, там таблицы для удобства обработки разбиты - отдельно мл. байт отдельно старший.

[zombi 0]

Это не совсем CRC, это простая контрольная сумма, которая в отличие от CRC невосприимчива к перестановке байт.

Ага понял.

Нужно тестить внешнюю флеш на предмет самопроизвольной порчи и правильности монтажа оной.

Не думаю что самопроизвольный сбой может выглядеть как перестановка N-байтных слов.

А вот кз/обрыв по адресу/сам и данным возможен.

Как бы оную быстро и качественно протестить?

Может рассматривать её как посл. челых чисел с нечётным кол-вом байт?

 

Проц Xmega128. Времени нет на любой CRC.

[ae_ 2]

...Проц Xmega128. Времени нет на любой CRC.

Можно сначала заполнить всю тестируемую память данными ПСП (псевдослучайная последовательность), затем сравнить с заново запущенным генератором ПСП.

Для 32кБ хватит 16-бит ПСП, например такой: LFSR

ПСП на LFSR работает быстро: 1 сдвиг + 1 условный XOR.

Проверка всей памяти целиком после её полной записи хороша тем, что обнаруживает ошибки при обрывах/КЗ в адресных линиях, чего не обнаружить, если тестировать по 1-2 байта(write/read/compare) в цикле перебирая адреса.

[zombi 0]

Можно сначала заполнить всю тестируемую память данными ПСП ...

Проц внешнюю флеш может только читать!

Он должен протестировать то что ему подсунули.

И либо работать с этими данным либо ругаться.

[vvs157 0]

Нужно тестить внешнюю флеш на предмет самопроизвольной порчи и правильности монтажа оной.

Для этого простой контрольной суммы действительно достаточно.

[haker_fox 61]

Времени нет на любой CRC.

А что такое время в Вашем случае? Как много его есть, и сколько можно использовать для подсчета КС? Вот Вы суммируете. А по таблице дольше вычислять? А надежность? Надежность CRC подтверждена математически? А надежность суммирования для случая проверки флеша?

[zombi 0]

А что такое время в Вашем случае? Как много его есть, и сколько можно использовать для подсчета КС?

Чем быстрее тем лучше. Проц работает на 32MHz но всего лишь 5-10% времени он может уделить для тестирования флешки.

Тест 512-ти областей по 32кБ (16МВ) с подсчётом CRC32 (по табличному алг.) идёт примерно 2 минуты и это ужасно долго!

Тоже самое с КС 20 сек, красота!

 

Вот Вы суммируете. А по таблице дольше вычислять?

Суммирую 0-й байт флеш с 0-м бaйтом KC, второй со вторым с учётом переноса и т.д. (всего одно чтение и одно сложение на байт).

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

 

А надежность? Надежность CRC подтверждена математически? А надежность суммирования для случая проверки флеша?

:laughing:

[Plain 197]

устраивает одно чтение байта и одна (максимум 2) операция с ним

Например, сложение и циклический сдвиг.

[zombi 0]

Для этого простой контрольной суммы действительно достаточно.

Надеюсь.

На всяк. случай алгоритм несколько поменял:

КС сделал 7-ми байтной и сложение заменил на XOR.

 

Например, сложение и циклический сдвиг.

Циклический сдвиг чего?

Одного байта результата сложения? или всей КС?

 

[Plain 197]

Если нужно просто убедиться в целости линий адресов и данных, то достаточно пройти память по диагонали, т.е. 4 КБ.

[Артём__ 0]

Проц Xmega128. Времени нет на любой CRC.

xmegaA или другая ? Есть ли у неё Crypto Engine?

Врядли конечно будет быстрее, по вдруг...

Если есть блок шифрования то нельзя ли выполнить команду DES? Но что-то не могу найти сколько циклов она выполняется, врядли 1.