Контрольная сумма BSD

Алгоритм контрольной суммы BSD был широко используемым устаревшим алгоритмом контрольной суммы . Он был реализован в старой BSD и также доступен через утилиту командной строки sum .

Этот алгоритм бесполезен с точки зрения безопасности и слабее, чем CRC-32 cksum для обнаружения ошибок. ^{[1] [2]}

Ниже приведена соответствующая часть исходного кода GNU sum ( лицензия GPL ). Он вычисляет 16-битную контрольную сумму, суммируя все байты (8-битные слова) входного потока данных. Чтобы избежать многих недостатков простого сложения данных, аккумулятор контрольной суммы циклически вращается вправо на один бит на каждом шаге перед добавлением нового символа.

int bsdChecksumFromFile ( FILE * fp ) /* Дескриптор файла для входных данных */ { int checksum = 0 ; /* Контрольная сумма mod 2^16. */         for ( int ch = getc ( fp ); ch != EOF ; ch = getc ( fp )) { checksum = ( checksum >> 1 ) + (( checksum & 1 ) << 15 ); checksum += ch ; checksum &= 0xffff ; /* Сохраняем в пределах. */ } return checksum ; }                                

Как упоминалось выше, этот алгоритм вычисляет контрольную сумму, сегментируя данные и добавляя их в аккумулятор, который циклически смещается вправо между каждым суммированием. Чтобы аккумулятор оставался в пределах возвращаемого значения, выполняется битовая маскировка единицами.

Пример: вычисление 4-битной контрольной суммы с использованием сегментов размером 4 бита ( big-endian )

Ввод: 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

• официальный исходный код FreeBSD sum
• официальная страница руководства GNU sum
• Исходный код GNU-суммы