Господа, посоветуйте быстрый алгоритм подсчета CRC блока 32кБ.
CRC16,CRC32...MD5 не подходят из за большого времени счёта.
По быстродействию устраивает одно чтение байта и одна (максимум 2) операция с ним.

Реализовал вот так.
Весь блок рассматриваю как последовательность 8-ми байтных целых чисел и просто их суммирую.
В результате CRC тоже 8-мь байт.
Вопрос: если CRC сделать не восемь а девять или десять байт, будет ли надёжнее?

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

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

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

Быстрее и надёжнее стандартного табличного CRC вы вряд ли изобретёте. ИМХО.
Если конечно не будете использовать аппаратный блок микроконтроллера для расчёта CRC как например в STM32.

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

Ага понял.
Нужно тестить внешнюю флеш на предмет самопроизвольной порчи и правильности монтажа оной.
Не думаю что самопроизвольный сбой может выглядеть как перестановка N-байтных слов.
А вот кз/обрыв по адресу/сам и данным возможен.
Как бы оную быстро и качественно протестить?
Может рассматривать её как посл. челых чисел с нечётным кол-вом байт?

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

Можно сначала заполнить всю тестируемую память данными ПСП (псевдослучайная последовательность), затем сравнить с заново запущенным генератором ПСП.
Для 32кБ хватит 16-бит ПСП, например такой: LFSR
ПСП на LFSR работает быстро: 1 сдвиг + 1 условный XOR.
Проверка всей памяти целиком после её полной записи хороша тем, что обнаруживает ошибки при обрывах/КЗ в адресных линиях, чего не обнаружить, если тестировать по 1-2 байта(write/read/compare) в цикле перебирая адреса.

Проц внешнюю флеш может только читать!
Он должен протестировать то что ему подсунули.
И либо работать с этими данным либо ругаться.

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

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

Чем быстрее тем лучше. Проц работает на 32MHz но всего лишь 5-10% времени он может уделить для тестирования флешки.
Тест 512-ти областей по 32кБ (16МВ) с подсчётом CRC32 (по табличному алг.) идёт примерно 2 минуты и это ужасно долго!
Тоже самое с КС 20 сек, красота!


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

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

Надеюсь.
На всяк. случай алгоритм несколько поменял:
КС сделал 7-ми байтной и сложение заменил на XOR.


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

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

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

А можно поподробнее?

1/2 цикла однако...

Суммы действительно хватит, скорее всего. Для примера, в тех же LPC214x целостность расположенной во Flash таблицы векторов прерываний контролируется именно так. Размер таблицы - восемь 32-разрядных слов. Загрузчик после включения питания суммирует их и получает 32-разрядный же результат. Возможные биты переполнения отбрасываются, и в результате должен получиться ноль. Любой другой результат указывает на повреждение таблицы векторов ...

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

Возможно ляпну ерунду, но у xmega есть некая "крипто-хрень". Может ее озадачить?

Дааа, DES быстрая однако.

Надо подумать

Для xmega оно, конечно, офтопик, но вот вроде бы быстрее:
http://w..._generators.pdf
http://sourceforge.net/projects/slicing-by-8/

А что, если загрузить R0-15 некой константой
затем N раз

R0=R0 XOR FLASH[N*8+0]
R1=R1 XOR FLASH[N*8+1]
...
R7=R7 XOR FLASH[N*8+7]
DES 0

В результате в R0-R7 получится некий рандомайз и к томуже быстрее чем просто KC (на 8-мь байт 8-мь чтений и один DES) !

Но будет ли оное надёжнее чем просто КС ?

Можно попробовать код Флетчера, где то на форуме это уже обсуждалось.
В кратце

unsigned Crc1 = 0; // для большей надежности можно инициализировать какой либо константой
unsigned Crc2 = 0;
for (int i=0; i<n;i++)
{ Crc1 += Buf[i]; // пи сложении переносы не учитываются
Crc2 += Crc1;
}
Crc2++; // позволяет избежать ситуаций Crc1 == Crc2==0, или Crc1 == Crc2==-1;
При размере переменных 8 бит, гарантировано считается блок на 256 байт. Для бОльшего блока необходима бОльшая разрядность.
Насколько бОльше не скажу, применял для коротких сообщений (20-25 байт) в восьмибитнике, но думаю вики поможет в этом вопросе

ИМХО Да скорее всего никак. Вы представьте , что у Вас нет , предположим ,одной линии данных или адреса и что Вы получите прочитав из Flash данные, ничего не зная какие они должны быть? Ну пусть Вы их проссумируете , но это уже не те данные. Соответсвенно не та сумма
Ваш проц изначально должен знать , сумму или CRC , например "разбросанных" по адресному пространству 10 - 100 ячеек FLASH и уже на основании этого Вы с уверенностью сможете сказать - есть или нет ошибки в монтаже или прошивке FLASH и при необходимости вычислить линию адреса или данных с которой есть проблема.

А почему Вы решили что он её не знает???
Именно её то он и знает и должен сравнить оную с вновь рассчитанной.


Для этого есть техники у них и лупы и тестера и паяльники, пусть ищут.

Ну наверное потому, что Вы об этом не писали. К тому же и сейчас не понятно , что он знает CRC или КС.
А уж облегчить жизнь техникам - святое

Какая разница? Чего надо то и будет знать.
Вопрос лишь в том как ему побыстрее определить что ему правильно подключили правильно прошитую внешнюю ROM.

Ну вот , что-то уже прояснилось.
Раз уж процу ещё ничего не известно, тогда Вы можете заложить 2 направления
1. "Быстрый" - предварительная оценка , здесь можно делать что захотите , но что бы быстро. Например КС по 1 байту из каждого адреса или вообще страницы
2. "Медленный" - CRC всей FLASH , если предварительный выдал ошибку , тут уже всё равно спешить не куда , кому-то с этим надо будет разбираться и что-то мне подсказывает , что не Вам

Т.е. Вы предлагаете что бы процессор считал правильной с флешку у которой в каждой странице правильно записан лишь один единственный байт?

А почему бы и нет, для быстрой проверки. К тому же я предлагал сумму байт или можете взять CRC8 , что конечно надёжней. Там же написано здесь можно и только в случае проблем .....
Устройте "пробег" по всем адресам 1 2 4 8 16 32 ...... по одному байту с каждого

Для быстрой первичной проверки на закоротки в шинах (беря байты со смещением, к примеру, инкрементируя адрес не на размер страницы, а на простое число) этого достаточно.
В зависимости от задачи — как можно быстрее отказаться от плохой ситуации или как можно быстрее убедиться в хорошей — и методы разные.

Может и глупость скажу.
Возьмите контрольные суммы от блоков, лучше не более 256 байт, и загоните эти суммы в CRC16 по любому методу.

Не вижу разницы.
Любая из задач меня устраивает. Главное чтобы быстро.


Блин 16МБ / 256 * 2 = 128 КВ памяти только на CRC !
Но надо попробывать на сколько быстрее (на моём 8-ми битном проце) считается CRC16 чем CRC32.
Возможно и устроит.

Так ли уж обязательно надо быстро? Можно придумать какой-нибудь альтернативный выбор. Нажал кнопку при сбросе (закоротил перемычку) - пошла медленная серьезная проверка устройства. Не нажал - обычный рабочий режим.

Это надо в первую очередь для того что бы проц не запустился случайно с не рабочей флешкой.
При отладке 2-3 изделий можно конечно и подождать.
А если надо 1000 отладить, 33 часа уйдёт только на проверку флеш.
А если некоторые придётся выключить и снова включить да еще и несколько раз.

то совершенно необязательно проверять их флешки строго одну за другой, можно синхронно запустить проверку. Или нет?

А если вдруг непропаянная ножка найдется, то сразу - в мусорную корзину, чтобы время на пайку не терять? Как в Афгане подбитые грузовики - с дороги в пропасть, чтобы спасти остальные?

Можно конечно, но это дополнительные затраты на стендовое оборудование и т.д.


Я так понял что идеи кончились и пошёл просто стёб.

При таком подходе можно в схемотехнику всепить CPLD-шку, которая будет максимально быстро считать CRC.
Но только кто будет её проверять? А в принципе, сам микроконтроллер это может делать..
ЗЫ: Мой пост - не стёб, всё на полном серьёзе. BGAшная CPLD весит совсем мало и по деньгам, и по размерам...

Можно конечно, но всётаки цена изделия важнее времени его отладки.


Охотно верю, но добавление в устройство дополнительных мс да еще и в BGA!!! абсолютно не приемлемо.

Мне думается, получив каждую новую плату, тестировщик пару минут будет ее только в руках крутить-вертеть, осматривать визуально. Прежде, чем подключать питание и т.д.

Зачем?
В конце флеша хранится только CRC16. Которая получается так:

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

Ни чё он не крутит.
Вытащил из коробки, тестером прозвонил питание на предмет кз, воткнул в неё шлейфы и всё что нужно, подал питание и на компе нажал ENTER. (максимум 15 сек).
За 8 сек всё прожглось, проц стартует с проверки флеш (2е минуты!).

И чё? У меня прошивка тестовой версии-проверка внешней флешки -зашивка рабочей версии минут 8 занимает.Какая разница - плату включил и само пошло, результат программа выдаст: всё ок или где-то застряло.

И чё? Вас 8 минут устраивает, а мне и 2 много!


Правильно ли я понял?
Вы предлагаете считать CRC16 контрольных сумм всех блоков?

Если вопрос только в работе тестировщика, то почему не проверять одновременно несколько плат? Пока на одной тесты бегают он другую готовит и так по кругу.

8 / 8 = 1.
Т.е., как уже говорили, можно сделать многоместный стенд.
У меня 10-местный :-), за 3 минуты прошивается-тестируется десять плат.

Не я :-)

Надо подумать.


Ну да.
Идею сразу не понял. Спасибо _Pasha и Вам.
Тогда уж лучше CRC32 посчитать, вызов процедуры crc всего то 128 раз на блок!



Именно так и происходит. Раздражает лишь то что новую он готовит намного быстрее чем бегают тесты в предыдущей.

CRC32 у Вас вызывается 262144 раза. Но оно длиннее чем CRC16. Вот и выбирайте, приемлемо ли время тестирования.