Network Working Group                                                                                         R. Braden
Request for Comments: 1071                                                                                             ISI
D. Borman
Cray Research
C. Partridge
BBN Laboratories
September 1988
Расчет контрольных сумм в Internet
Computing the Internet Checksum
Статус документа
В этом документе дается обзор эффективности методов и алгоритмов расчета контрольных сумм Internet. Документ не является стандартом, но описывает ряд полезных методов реализации. Документ может распространяться свободно.
1. Введение
В этом документе обсуждаются методы эффективного расчета контрольных Internet - IP, UDP и TCP.
сумм, используемых стандартными протоколами
Эффективность расчета контрольных сумм очень важна с точки зрения производительности. В результате эффективной реализации остальных компонент протокольной обработки расчет контрольных сумм стал, например, одним из факторов, ограничивающих производительность TCP. Обычно для процедур расчета контрольных сумм используется ручная оптимизация с учетом особенностей работы конкретного процессора - экономия доли микросекунды в расчете на один байт данных TCP может привести к существенному снижению суммарного расхода процессорного времени.
В общих чертах алгоритм расчета контрольной суммы очень прост:
(1)  Соседние октеты информации, для которой создается контрольная сумма, объединяются в 16-битовые целые числа и для этих чисел формируется 16-битовое поразрядное дополнение до 1.
(2)  При расчете контрольной суммы значение самого поля контрольной суммы принимается нулевым. Для 16-битовых поразрядных дополнений вычисляется сумма. Для полученного в результате 16-битового целого числа создается 16-битовое поразрядное дополнение до 1 и помещается в поле контрольной суммы.
(3)  Для проверки контрольной суммы вычисляется сумма поразрядных дополнений до 1 для того же набора октетов, включая поле контрольной суммы. Если в результате получается значение, все биты которого равны 1 (-0 в арифметике дополнений до 1), это говорит о корректности контрольной суммы.
Предположим, что контрольная сумма определяется для последовательности октетов А, В, С, D, ... , Y, Z. Будем использовать обозначение [а,Ь] для 16-битовых целых чисел а*256+Ь, где а и b являются байтами. Тогда сумма 16-битовых дополнений до 1 для этих байтов будет задаваться одним из выражений:
[А, В] +' [C,D] +' ... +' [Y,Z] [А, В] +' [C,D] +' ... +' [Z,0]
где +' указывает сложение поразрядных дополнений до четным и нечетным количеством байтов, соответственно.
[1] [2] 1. Приведенные выше выражения относятся к последовательностям с
В двоичных машинах сумма поразрядных дополнений до единицы должна вычисляться с использованием "кругового переноса"1, т. е, при переполнении старшего бита значение переносится в младший, как показано в примерах ниже.
В параграфе2 рассматриваются свойства контрольной суммы, которые могут использоваться для ускорения расчетов. ПараграфЗ содержит несколько числовых примеров для наиболее важных методов реализации. В параграфе 4 приведены несколько конкретных алгоритмов для использования с распространенными типами процессоров. Авторы признательны Van Jacobson и Charley Kline за их вклад в алгоритмы, опубликованные в этом параграфе.
Свойства контрольных сумм Internet изначально были рассмотрены Биллом Пламмером (Bill Plummer) в документе IEN-45, названном "Checksum Function Design". Поскольку документ IEN-45 не получил широкого распространения, он включен в качестве приложения к данному RFC.
2. Расчет контрольной суммы
Эта простая контрольная сумма имеет множество чудесных вычисления расчетов. Эти свойства обсуждаются ниже.
математических свойств, которые могут быть использованы для
1"end around carry"
rfc.com.ru
rfc.com.ru
_Перевод RFC 1071
(A) Кумулятивность и ассоциативность
После того, как байты были распределены на четные и нечетные2, суммирование может проводиться в любом порядке с возможностью разбиения на произвольные группы.
Например, сумму [1] можно представить в форме:
( [А, В] +' [C,D] +' ... +' [J,0] ) +' ( [0,К] +' ... +' [Y,Z] )                                 [3]
(B) Независимость от порядка байтов
Сумма 16-битовых целых чисел может вычисляться для любого порядка байтов. Т. е., если мы рассчитаем сумму, сменив порядок байтов:
[В, А] +' [D,C] +' ... +' [Z,Y]                                          [4]
результат будет отличаться от значения [1] только сменой порядка байтов! Для того, чтобы это стало более понятным, отметим, что в обоих случаях перенос происходит из бита 15 в бит 0 и из бита 7 в бит 8. Иными словами, смена порядка суммируемых байтов лишь приводит к смене порядка байтов результата, но сохраняет порядок битов в каждом байте результата.
Следовательно, сумма может рассчитываться одинаково, независимо от используемого оборудованием порядка байтов ("big-endian" или "little-endian"3). В качестве примера предположим, что машина "little-endian" вычисляет контрольную сумму данных, хранящихся в памяти с использованием сетевого ("big-endian") порядка байтов. Выборка каждого 16-битового слова будет приводить к смене мест байт в словах, что приведет к суммирования [4]; однако при сохранении результата в памяти снова произойдет смена мест байтов и будет восстановлен сетевой порядок.
Смена мест байтов может явно использоваться для решения проблем, связанных с выравниванием по границе. Например, вторая группа в [3] может быть рассчитана, как:
[K,L] +' ... +' [Z,0]
если байты результата поменять местами до того, как они будут добавлены к сумме первой группы (см. пример ниже).
(C) Параллельное суммирование
На машинах с размером слова, кратным 16 битам, можно использовать дополнительное увеличение скорости расчетов. Поскольку сложение ассоциативно, мы не обязаны складывать целые числа в порядке их следования в сообщении. Вместо этого мы можем складывать их “параллельно" используя более длинные машинные слова.
Для параллельного расчета контрольной суммы просто выполняется операция поразрядного дополнения до 1 для стандартного размера машинного слова. Например, на 32-разрядных машинах мы можем складывать одновременно по 4 байта : [A,B,C,D]+'„. После завершения расчета результат более длинное слово "вталкивается" в 16 битов путем сложения 16-битовых сегментов. При каждом сложении могут происходить переносы битов, которые следует учитывать.
Поскольку порядок байтов не имеет значения, мы можем посчитать 32-битовых слов [D,C,B,A]+'„. или [B,A,D,C]+'„. и потом поменять местами байты окончательной 16-битовой суммы (см. примеры ниже). Допускаются любые перестановки, которые будут обеспечивать сложение всех четных байтов в один байт суммы, а всех нечетных - в другой байт.
Ниже описано еще несколько методов ускорения расчета контрольных сумм.
(1)  Отложенные переносы
Для некоторых типов процессоров эффективность расчета контрольных сумм может быть повышена за счет того, что добавление битов переноса осуществляется после завершения цикла суммирования.
Можно складывать 16-битовые слова в 32-битовую переменную, чтобы все биты переноса складывались в старших 16 битах. Этот вариант позволяет отказаться от использования команд, понимающих перенос битов, но требует удвоенного числа операций сложения, поскольку складываются 32-битовые сегменты. Который из вариантов будет быстрее, зависит от системной архитектуры.
(2)  Использование циклов
Для повышения эффективности часто бывает полезно создание внутреннего цикла суммирования, выполняющего серию команд сложения за один проход. Этот метод часто дает существенное повышение эффективности, хотя может значительно усложнить логику программы.
(3)  Объединение суммирования и копирования данных
Кроме вычисления суммы время расходуется также на копирование данных из одного места памяти в другое. В обоих случаях узким местом является скорость шины памяти (например, скорость выборки данных из памяти). На некоторых машинах (особенно на сравнительно медленных и простых микрокомпьютерах) производительность можно существенно повысить за счет объединения операций суммирования и копирования при котором происходит только одна выборка из памяти для обеих операций.
(4)  Нарастающие обновления
В некоторых случаях можно избежать повторного вычисления всей контрольной суммы, если сменился только заголовок. Наиболее ярким примером может служить изменение поля TTL в заголовке IP при пересылке пакетов шлюзом, но есть и другие примеры (скажем, обновление source route). В таких случаях можно обновить контрольную сумму даже без просмотра сообщения или дейтаграммы.
Для обновления контрольной суммы достаточно просто добавить к ней разность между новым и прежним значениями изменившегося 16-битового слова. Чтобы понять, как это работает, напомним, что каждое целое число имеет аддитивную инверсию4, а операция сложения ассоциативна. Если исходное значение слова обозначить т, новое значение - т', а исходную контрольную сумму - С, тогда новая сумма С будет равна:
2По порядку их следования, а не по значениям байтов. Прим. перев.
3“Сначала старший" или "сначала младший". Для обозначения этих вариантов используются также термины сетевой (network byte
order) и "хостовый" (host byte order). Прим. перев.
4Число, совпадающее по значению и противоположное по знаку. Прим. перев.__________________________________________
rfc.com.ru                                                                                     2                                                            rfc.com.ru
Перевод RFC 1071
С = С + (-га) + га' = С + (га' -га)
3. Численные примеры
Ниже рассматриваются явные примеры расчета сумм дополнений до 1 на машине с дополнением до 2. Примеры показывают, как одну и ту же сумму можно рассчитать путем сложения байтов, 16-битовых слов с нормальным и измененным порядком байтов, а также 32-битовых слов с 3 вариантами порядка байтов. Все числа задаются в шестнадцатеричном формате.
Побайтовое Нормальный порядок Обратный порядок
Байты 0-1 00
01
0001
0100
Байты 2-3 £2
03
f203
03f2
Байты 4-5 f4
f5
f4f5
f5f4
Байты 6-7 f6
f7
f6f7
f7f6
Сумма 1 2dc
lfO
2ddf0
lf2dc
dc
f0
ddfO
f2dc
Переносы 1
2
2
1
Сумма 2 dd
f2
ddf2
f2dd
Итог dd
f2
ddf2
ddf2
Байты 0-3 oooif203
010003f2
03f20100
Байты 4-7 f4f5f6f7
f5f4f7f6
f7f6f5f4
Сумма1 0f4f7e8fa
0f6f4fbe8
0fbe8f6f4
Переносы
0
0
0
Верхняя половина
f4f7
f6f4
fbe8
Нижняя половина
e8fa
fbe8
f6f4
Сумма 2
lddfl
lf2dc
lf2dc
ddfl
f2dc
f2dc
Переносы
1
1
1
Сумма 3
ddf2
f2dd
f2dd
Итог
ddf2
ddf2
ddf2
В заключение приводится пример суммирования в виде двух групп, из ко"
Побайтовое
Нормальный порядок
Байты 0-1
00 01
0001
Байт 2
F2 (00)
f200
Сумма 1
f2 01
f201
Байты 4-5
03 f4
03f4
Байты 6-7
f5 f6
f5f6
Байт 8
f7 (00)
f700
Сумма 2
lfOea
Сумма 2
fOea
Перенос
1
Сумма 3
fOeb
Сумма 1
f201
Сумма 3 после смены порядка
fOeb
Сумма 4
lddfl
Сумма 4
ddfl
Перенос
1
Сумма 5
ddf2
4. Примеры реализации
Ниже приводятся примеры реализации алгоритма подсчета контрольных сумм Internet, которые доказали свою эффективность для разных типов CPU. В каждом случае приводится ядро алгоритма без включения дополнительного кода (например, свящывания подпрограмм).
4.1 Код на языке C
Приведенный ниже пример на языке С показывает расчет контрольной суммы с использованием внутреннего цикла сложения 16-битовых значений в 32-битовый "аккумулятор".
in 6
{
/* Расчет контрольной суммы Internet для count байтов, начиная с addr. */ register long sum = 0; while( count > 1 ) { /* Внутренний цикл */ sum += * (unsigned short) addr++; count -= 2; }
/* Прибавляем байт переноса, если он есть */ if( count > 0 )
sum += * (unsigned char *) addr; /* поместим 32-битовую сумму в 16 битов */ while (sum>>16)
sum = (sum & 0xffff) + (sum >> 16); checksum = ~sum;
}
rfc.com.ru
3
rfc.com.ru
Перевод RFC 1071
4.2 Motorola 68020
Ниже приведен пример ассемблерной реализации алгоритма для процессора Motorola 68020. Этот вариант использует суммирование 32-битовых значений в один прием и использует внутренний цикл сложения с 16 операциями. Для простоты была опущена логика дополнения последнего слова для случаев, когда число суммируемых байтов не кратно 4. Результат сохраняется в регистре d0.
При тактовой частоте алгоритм Van Jacobson.
процессора 20 МГц время расчета контрольной суммы составляет 134 мксек/кбайт. Разработал этот
movl
dl,d2
Isrl
#6,dl
andl
#0x3c, d2
negl
d2
andb
#0xf,cc
count/64 = # число проходов цикла Нахождение частей блока
| Сброс X (расширенный флаг переноса)
jmp pc@(2$-.-2:b,d2) | Переход в цикл 1$: | Начало внутреннего цикла...
movl         a0@+,d2            /
addxl       d2,dO                /
movl         a0@+,d2            /
addxl       d2,dO                /
Выборка 32-битового слова
Сложение слова и предыдущего переноса Выборка 32-битового слова
Сложение слова и предыдущего переноса
/
еще 14 повторов
2$:
dbra
d1,1$ | (Отметим, что dbra не воздействует на X)
movl
d0,dl
swap
dl
addxw
dl,d0
jcc
3$
addw
#l,d0
| Вталкивание 32 битов суммы в 16 битов | (Отметим, что swap не воздействует на X)
3$:
andl
#0xffff, dO
4.3 Cray
Ниже приводится ассемблерная реализация алгоритма для процессора Cray, которую предложил Charley Kline. Расчет контрольной суммы производится как векторная операция, обеспечивающая одновременное сложение до 512 байтов с базовым блоком суммирования 32 бита. Для простоты из примера исключены фрагменты, обеспечивающие возможность работы с короткими блоками.
Регистр А1 содержит адрес 512-байтового блока памяти для контрольной суммы. Две первых копии данных загружаются в два векторных регистра. Один вектор сдвигается вправо на 32 бита, а для второго используется операция AND с 32-битовой маской. После этого векторы складываются. Поскольку все эти операции связаны в цепочку, они дают один результат на каждый цикл процессора. Далее производится сжатие (collaps) результирующего вектора в цикле, который прибавляет каждый элемент к скалярному регистру. В заключение выполняется перенос и результат помещается в 16 битов.
ЕВМ
АО
А1
VL
64
S1
<32
А2
32
VI
,А0,1
V2
S1&V1
V3
V1>A2
VI
V2+V3
А2
63
S1
0
S4
<16
А4
16
CK$LOOP S2
VI, А2
А2
А2-1
АО
А2
S1
S1+S2
JAN
CK$LOOP
S2
S1&S4
S1
S1>A4
S1
S1+S2
S2
S1&S4
S1
S1>A4
S1
S1+S2
S1
#S1
CMR
используются полные векторы
формируется 32-битовая маска из правой части.
загрузка пакета в V1 формирование “правых” 32 битов в V2. формирование “левых” 32 битов в V3. Сложение. Подготовка к сжатию в скаляр.
Form 16-bit mask from the right.
В
формирование “правых” 16 битов в S2 формирование “левых” 16 битов в S1
формирование “правых” 16 битов в S2 формирование “левых” 16 битов в S1
Получение дополнения до 1 этой точке S1 будет содержать контрольную сумму.
rfc.com.ru
4
rfc.com.ru
Перевод RFC 1071_______________________________________________
4.4 IBM 370
Следующий пример на ассемблере для процессора IBM 370 суммирует по 4 байта одновременно. Для простоты опущен код дополнения, используемых для выравнивания данных по 4-байтовой границе и обращения порядка байтов, когда это требуется. Результат сохраняется в регистре RCARRY.
Этот код на процессоре IBM 3090 давал время расчета 27 мксек/кбайт при расчете контрольной суммы байтов, содержащих только единицы. Время расчета снижается до 24.3 мксек/кбайт, если применить средства выравнивания слов (специальная обработка в начале и в конце, а при необходимости замена местами байтов при расчете с нечетной позиции).
Регистры RADDR и RCOUNT содержат адрес и размер суммируемого блока.
(RCARRY, RSUM) должны быть парой регистров (RCOUNT, RMOD) должны быть парой регистров
(четный/нечетный). (четный/нечетный).
CHECKSUM SR RSUM,RSUM
SR RCARRY,RCARRY LA RONE,1
Сброс рабочих регистров.
Установка значения 1.
SRDA    RCOUNT,6
AR         RCOUNT, RONE
SRL      RMOD,26
AR         RADDR,R3
S           RADDR,=F(64)
SRL      RMOD, 1
LH        RMOD,DOPEVEC9(RMOD)
В           LOOP(RMOD)
nt/64 в RCOUNT.
1 = # число циклов. мер частичного блока в RMOD. авнивание для компенсации перехода
цикл. OD/4)*2 – индекс “полуслов”.
используется специальный вектор для и перехода в цикл...
смещения
Внутренний цикл:
AL        RSUM,0(,RADDR)
BC        12,*+6
AR        RCARRY,RONE
AL        RSUM,4(,RADDR)
BC        12,*+6
AR        RCARRY,RONE
Сложить логические слова Переход, если нет переноса Добавить 1 переноса
Сложить логические слова Branch if no carry Добавить 1 переноса
* LOOP
еще 14 повторов
A BCT
RADDR,=F'64' Увеличить адресный указатель RCOUNT,LOOP Перейти к Count
Прибавить переносы к сумме и “затолкнуть” в 16 битов
ALR      RCARRY,RSUM
BC        12,*+6
AR        RCARRY,RONE
Сложить слова SUM и CARRY
и учесть возможный перенос
SRDL    RCARRY,16
Поместить 32-битовую в 16 битов
сумму
SRL      RSUM,16
DONE
ALR      RCARRY,RSUM
C           RCARRY,=X'0000FFFF' Прибавить оставшийся перенос
BNH      DONE
S           RCARRY,=X'0000FFFF'
X           RCARRY,=X'0000FFFF' Дополнить до 1
rfc.com.ru
5
rfc.com.ru