Быстрый алгоритм CRC, придумать надо Опции

[zombi]

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

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

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

[vvs157]

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

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

[kovigor]

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

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

[demiurg_spb]

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

[_Pasha]

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

[zombi]

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

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

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

[ae_]

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

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

[zombi]

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

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

[vvs157]

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

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

[haker_fox]

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

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

[zombi]

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

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

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

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

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

[Plain]

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

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

[zombi]

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

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

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

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

[Plain]

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

[_Артём_]

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

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

[zombi]

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

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

[_Артём_]

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

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

[kovigor]

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

[Plain]

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

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

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

[Sirko]

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

[zombi]

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

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

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

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

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

[ReAl]

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

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

[zombi]

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

А что, если загрузить 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) !

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

[редактор]

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

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

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 байт) в восьмибитнике, но думаю вики поможет в этом вопросе

[ILYAUL]

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

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

[zombi]

Ваш проц изначально должен знать , сумму или CRC ...

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

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

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

[ILYAUL]

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


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

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

[zombi]

К тому же и сейчас не понятно , что он знает CRC или КС.

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

[ILYAUL]

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

[zombi]

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

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

[ILYAUL]

А почему бы и нет, для быстрой проверки. К тому же я предлагал сумму байт или можете взять CRC8 , что конечно надёжней. Там же написано здесь можно

делать что захотите

и только в случае проблем .....
Устройте "пробег" по всем адресам 1 2 4 8 16 32 ...... по одному байту с каждого

[ReAl]

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

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

[_Pasha]

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

[zombi]

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

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

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

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

[ViKo]

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

[zombi]

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

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

[_Ivana]

При отладке 2-3 изделий можно конечно и подождать.
А если надо 1000 отладить,

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

[ViKo]

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

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

[zombi]

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

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

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

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

[VCO]

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

Сообщение отредактировал VCO - Aug 28 2012, 13:29

[zombi]

При таком подходе можно в схемотехнику всепить CPLD-шку ...

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

ЗЫ: Мой пост - не стёб, всё на полном серьёзе. BGAшная CPLD весит совсем мало и по деньгам, и по размерам...

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

[ViKo]

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

[ReAl]

Блин 16МБ / 256 * 2 = 128 КВ памяти только на CRC !

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

Код

инициализируем CRC16
цикл по блокам в 256 байт
    считаем 8- или 16-битную сумму блока, возможно с цикл. переносом или xor-ку всех байтов или что не жалко
    добавляем эту сумму к CRC16
усё

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

[zombi]

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

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

[_Артём_]

(2е минуты!).

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

[zombi]

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

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

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

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

[Flexz]

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

[ReAl]

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

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

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

Не я :-)

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

[zombi]

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

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

Не я :-)

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

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

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

[_Pasha]

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

[zombi]

CRC32 у Вас вызывается 262144 раза.

16*1024*1024 / 256 = 65536 раз. Не понимаю откуда 262144?

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

Само собой.

[_Pasha]

16*1024*1024 / 256 = 65536 раз. Не понимаю откуда 262144?

Пардон