Статус документа
В этом документе дается обзор эффективности методов и алгоритмов расчета контрольных сумм Internet. Документ не является стандартом, но описывает ряд полезных методов реализации. Документ может распространяться свободно.
1. Введение
В этом документе обсуждаются методы эффективного расчета контрольных сумм, используемых стандартными протоколами Internet — IP, UDP и TCP.
Эффективность расчета контрольных сумм очень важна с точки зрения производительности. В результате эффективной реализации остальных компонент протокольной обработки расчет контрольных сумм стал, например, одним из факторов, ограничивающих производительность TCP. Обычно для процедур расчета контрольных сумм используется ручная оптимизация с учетом особенностей работы конкретного процессора — экономия доли микросекунды в расчете на один байт данных TCP может привести к существенному снижению суммарного расхода процессорного времени.
В общих чертах алгоритм расчета контрольной суммы очень прост:
Соседние октеты информации, для которой создается контрольная сумма, объединяются в 16-битовые целые числа и для этих чисел формируется 16-битовое поразрядное дополнение до 1.
При расчете контрольной суммы значение самого поля контрольной суммы принимается нулевым. Для 16-битовых поразрядных дополнений вычисляется сумма. Для полученного в результате 16-битового целого числа создается 16-битовое поразрядное дополнение до 1 и помещается в поле контрольной суммы.
Для проверки контрольной суммы вычисляется сумма поразрядных дополнений до 1 для того же набора октетов, включая поле контрольной суммы. Если в результате получается значение, все биты которого равны 1 (-0 в арифметике дополнений до 1), это говорит о корректности контрольной суммы.
Предположим, что контрольная сумма определяется для последовательности октетов A, B, C, D, ... , Y, Z. Будем использовать обозначение [a,b] для 16-битовых целых чисел a*256+b, где a и b являются байтами. Тогда сумма 16-битовых дополнений до 1 для этих байтов будет задаваться одним из выражений:
[A,B] +' [C,D] +' ... +' [Y,Z] [1] [A,B] +' [C,D] +' ... +' [Z,0] [2]
где +' указывает сложение поразрядных дополнений до 1. Приведенные выше выражения относятся к последовательностям с четным и нечетным количеством байтов, соответственно.
В двоичных машинах сумма поразрядных дополнений до единицы должна вычисляться с использованием «кругового переноса», т. е, при переполнении старшего бита значение переносится в младший, как показано в примерах ниже.
В параграфе 2 рассматриваются свойства контрольной суммы, которые могут использоваться для ускорения расчетов. Параграф 3 содержит несколько числовых примеров для наиболее важных методов реализации. В параграфе 4 приведены несколько конкретных алгоритмов для использования с распространенными типами процессоров. Авторы признательны Van Jacobson и Charley Kline за их вклад в алгоритмы, опубликованные в этом параграфе.
Свойства контрольных сумм Internet изначально были рассмотрены Биллом Пламмером (Bill Plummer) в документе IEN-45, названном «Checksum Function Design». Поскольку документ IEN-45 не получил широкого распространения, он включен в качестве приложения к данному RFC.