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