Area : Встроенные системы Date : Tue Jun 09, 08:05 From : George Shepelev 2:461/124 To : Dmitry Pushkin Subj : CRC для однокpисталлок ──────────────────────────────────────────────────────────────────────────────── Hallo Dmitry! Понедельник 08 Июня 1998 18:58, Dmitry Pushkin wrote to George Shepelev: GS>> Если нужно быстрый алгоритм, а параметры чуть хуже CRC-16 DP> Можно даже хуже CRC-8 (мне интеpесно узнать и сpавнить любые методы). DP> В пpинципе, pазмеp пакета кpайне мал (5-30 байт), но его обязательно надо DP> защитить от помехи, пpичем контpолем четности нельзя воспользоваться, так DP> как этот бит используется для "шиpоковещательной" адpесации. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Area : ZX.SPECTRUM From : George Shepelev 2:461/124 Пят Май 22 98 19:06 To : Eugene Mironchuk Subj : ASM "под себя" ─────────────────────────────────────────────────────────────────────────────── Hallo Eugene! Среда 20 Мая 1998 21:42, Eugene Mironchuk wrote to George Shepelev: EM>>> Imho, 3-4 байта с головой хватит (CRC+XOR+ADD+???). Только CRC - EM>>> обязательно!!! GS>> Есть более удобная штука - коды Флетчера. Считаются быстро и прак- GS>> тически такая-же надёжность, как у CRC. EM> А можно поподpобнее? Интеpесно... Ой! Hапросился на свою голову! ;) Значит так. Алгоритм предложен в конце 70-х годов. Он с высокой вероятностью обнаруживает одиночные ошибки (0,001538% вероятность ошибки, у CRC - 0,001526%) и обнаруживает парные ошибки в битах, отдалённых не дальше 2040 (у CRC 65535) (255 и 8191 байт в блоке соответственно). Описание алгоритма: Имеются два однобайтовых числа. Вначале их обнуляют. Затем в первом числе подсчитывается контрольная сумма проверяемых данных по модулю 255 (это зна- чит, что значение FFh сбрасывается в 0), а во втором числе используется этот же алгоритм, только вместо проверяемых данных суммируется значение из пер- вого числа. Чтобы было понятнее, вот алгоритм в псевдокодах: integer i, sum1, sum2; sum1 = 0; sum2 = 0; for i from 1 to message_length do sum1 = ( sum1 + message[i] ) modulo 255; sum2 = ( sum2 + sum1 ) modulo 255; end for Полученные значения передают вместе с данными, что позволяет проверить их правильность. Удобно просто в конец блока данных дописать два байта, обнуля- ющие коды Флетчера при проверке. Их вычисляют так: check1 = 255 - (( sum1 + sum2 ) modulo 255 ); message[ message_length + 1 ] = check1; check2 = 255 - (( sum1 + check1 ) modulo 255); message[message_length + 2 ] = check2; Алгоритм позволяет использовать один трюк, резко уменьшающий число процессорных команд, необходимых для его реализации. Для этого вместо деления по модулю 255 к сумме прибавляют перенос, оставшийся от прош- лого сложения. Единственная проблема - в конце вычислений может потребо- ваться учесть этот перенос и проверить результат на совпадение с FFh. Вот как выглядит внутренний цикл программы на ассемблере 68010: ; D0 регистр накопления первого числа (sum1) ; D1 регистр накопления второго числа (sum2) ; D2 длина сообщения в буфере (len) ; D4 содержит 0 для команды сложения ; A0 указатель в буфере (ptr) loop add.b (A0)+,D0 ; sub1 += *ptr++; addx.b D4,D0 ; if ( sum1 >= 256 ) sum1 += 1; add.1 D0,D1 ; sum2 += sum1; dbra D2,loop ; while (len--); В результате этот метод работает почти в 20 раз быстрее, чем вычисление CRC16. Поэтому стОит подумать по поводу его использования на Спектруме... Хотя система команд у восьмибитного Z80 конечно послабее 16-разрядной Моторолы ;) Более подробную статью можно посмотреть в "журнале д-ра Добба" 1/1993. С уважением George P.S. От себя. Для большей "случайности" результата при вычислении CRC в архиваторах zip, arj и т.п. используют не нулевые начальные значения. Может оказаться разумным использовать этот же подход и с кодами Флетчера... А может и нет ;) P.P.S. В такой математике я слабо разбираюсь, но на пальцах могу объяснять, почему этот метод надёжнее простой суммы. Изменение порядка байт не влияет на простую сумму, в то время как коды Флетчера мгновенно обнаружат ошибку: sum1 = ( A + B ) mod 255 sum2 = ( A + ( A + B ) mod 255 ) mod 255 Ясно, что A и B во втором выражении не взаимозаменимы... - --- GoldED 2.50.Beta6+ * Origin: Пессимист это хорошо