Контрольная сумма BSD
Алгоритм контрольной суммы BSD был широко используемым устаревшим алгоритмом контрольной суммы . Он был реализован в старой BSD , а также доступен через утилиту командной строки sum .
Этот алгоритм бесполезен с точки зрения безопасности и слабее, чем CRC-32, cksum для обнаружения ошибок. [1] [2]
Вычисление контрольной суммы BSD
[ редактировать ]Ниже приведена соответствующая часть исходного кода суммы GNU ( под лицензией GPL ). Он вычисляет 16-битную контрольную сумму путем сложения всех байтов (8-битных слов) входного потока данных. Чтобы избежать многих недостатков простого добавления данных, аккумулятор контрольной суммы поворачивается по кругу вправо на один бит на каждом этапе перед добавлением нового символа.
int bsdChecksumFromFile ( FILE * fp ) /* Дескриптор файла для входных данных */ { int checksum = 0 ; /* Контрольная сумма по модулю 2^16. */ for ( int ch = getc ( fp ); ch != EOF ; ch = getc ( fp )) { контрольная сумма = ( контрольная сумма >> 1 ) + (( контрольная сумма & 1 ) << 15 ); контрольная сумма += ch ; контрольная сумма &= 0xffff ; /* Держите его в пределах границ. */ } вернуть контрольную сумму ; }
Описание алгоритма
[ редактировать ]Как упоминалось выше, этот алгоритм вычисляет контрольную сумму путем сегментации данных и добавления их в аккумулятор, который циклически сдвигается вправо между каждым суммированием. Чтобы сохранить аккумулятор в пределах возвращаемого значения, выполняется битовая маскировка единицами.
Пример: вычисление 4-битной контрольной суммы с использованием сегментов размером 4 бита ( с прямым порядком байтов ).
Ввод: 101110001110 -> три сегмента: 1011, 1000, 1110.
Итерация 1:
сегмент: 1011 контрольная сумма: 0000 битовая маска: 1111
а) Примените циклический сдвиг к контрольной сумме:
0000 -> 0000
б) Сложите контрольную сумму и сегмент, примените к полученному результату битовую маску:
0000 + 1011 = 1011 -> 1011 и 1111 = 1011
Итерация 2:
сегмент: 1000 контрольная сумма: 1011 битовая маска: 1111
а) Примените циклический сдвиг к контрольной сумме:
1011 -> 1101
б) Сложите контрольную сумму и сегмент, примените к полученному результату битовую маску:
1101 + 1000 = 10101 -> 10101 и 1111 = 0101
Итерация 3:
сегмент: 1110 контрольная сумма: 0101 битовая маска: 1111
а) Примените циклический сдвиг к контрольной сумме:
0101 -> 1010
б) Сложите контрольную сумму и сегмент, примените к полученному результату битовую маску:
1010 + 1110 = 11000 -> 11000 и 1111 = 1000
Итоговая контрольная сумма: 1000