Статус документа
В этом документе дается обзор эффективности методов и алгоритмов расчета контрольных сумм 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.
2. Расчет контрольной суммы
Эта простая контрольная сумма имеет множество чудесных математических свойств, которые могут быть использованы для вычисления расчетов. Эти свойства обсуждаются ниже.
- A. Кумулятивность и ассоциативность
После того, как байты были распределены на четные и нечетные, суммирование может проводиться в любом порядке с возможностью разбиения на произвольные группы.
Например, сумму [1] можно представить в форме:
( [A,B] +' [C,D] +' ... +' [J,0] ) +' ( [0,K] +' ... +' [Y,Z] ) [3]- B. Независимость от порядка байтов
Сумма 16-битовых целых чисел может вычисляться для любого порядка байтов. Т. е., если мы рассчитаем сумму, сменив порядок байтов:
[B,A] +' [D,C] +' ... +' [Z,Y] [4]
результат будет отличаться от значения [1] только сменой порядка байтов! Для того, чтобы это стало более понятным, отметим, что в обоих случаях перенос происходит из бита 15 в бит 0 и из бита 7 в бит 8. Иными словами, смена порядка суммируемых байтов лишь приводит к смене порядка байтов результата, но сохраняет порядок битов в каждом байте результата.
Следовательно, сумма может рассчитываться одинаково, независимо от используемого оборудованием порядка байтов («big-endian» или «little-endian»). В качестве примера предположим, что машина «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-битовой суммы (см. примеры ниже). Допускаются любые перестановки, которые будут обеспечивать сложение всех четных байтов в один байт суммы, а всех нечетных — в другой байт.
Ниже описано еще несколько методов ускорения расчета контрольных сумм:
- Отложенные переносы
Для некоторых типов процессоров эффективность расчета контрольных сумм может быть повышена за счет того, что добавление битов переноса осуществляется после завершения цикла суммирования.
Можно складывать 16-битовые слова в 32-битовую переменную, чтобы все биты переноса складывались в старших 16 битах. Этот вариант позволяет отказаться от использования команд, понимающих перенос битов, но требует удвоенного числа операций сложения, поскольку складываются 32-битовые сегменты. Который из вариантов будет быстрее, зависит от системной архитектуры.
- Использование циклов
- Для повышения эффективности часто бывает полезно создание внутреннего цикла суммирования, выполняющего серию команд сложения за один проход. Этот метод часто дает существенное повышение эффективности, хотя может значительно усложнить логику программы.
- Объединение суммирования и копирования данных
- Кроме вычисления суммы время расходуется также на копирование данных из одного места памяти в другое. В обоих случаях узким местом является скорость шины памяти (например, скорость выборки данных из памяти). На некоторых машинах (особенно на сравнительно медленных и простых микрокомпьютерах) производительность можно существенно повысить за счет объединения операций суммирования и копирования при котором происходит только одна выборка из памяти для обеих операций.
- Нарастающие обновления
В некоторых случаях можно избежать повторного вычисления всей контрольной суммы, если сменился только заголовок. Наиболее ярким примером может служить изменение поля TTL в заголовке IP при пересылке пакетов шлюзом, но есть и другие примеры (скажем, обновление source route). В таких случаях можно обновить контрольную сумму даже без просмотра сообщения или дейтаграммы.
Для обновления контрольной суммы достаточно просто добавить к ней разность между новым и прежним значениями изменившегося 16-битового слова. Чтобы понять, как это работает, напомним, что каждое целое число имеет аддитивную инверсию, а операция сложения ассоциативна. Если исходное значение слова обозначить m, новое значение — m', а исходную контрольную сумму — C, тогда новая сумма C' будет равна:
C' = C + (-m) + m' = C + (m' - m)
3. Численные примеры
Ниже рассматриваются явные примеры расчета сумм дополнений до 1 на машине с дополнением до 2. Примеры показывают, как одну и ту же сумму можно рассчитать путем сложения байтов, 16-битовых слов с нормальным и измененным порядком байтов, а также 32-битовых слов с 3 вариантами порядка байтов. Все числа задаются в шестнадцатеричном формате.
Byte-by-byte "Normal" Swapped
Order Order
Byte 0/1: 00 01 0001 0100
Byte 2/3: f2 03 f203 03f2
Byte 4/5: f4 f5 f4f5 f5f4
Byte 6/7: f6 f7 f6f7 f7f6
--- --- ----- -----
Sum1: 2dc 1f0 2ddf0 1f2dc
dc f0 ddf0 f2dc
Carrys: 1 2 2 1
-- -- ---- ----
Sum2: dd f2 ddf2 f2dd
Final Swap: dd f2 ddf2 ddf2
Byte 0/1/2/3: 0001f203 010003f2 03f20100
Byte 4/5/6/7: f4f5f6f7 f5f4f7f6 f7f6f5f4
-------- -------- --------
Sum1: 0f4f7e8fa 0f6f4fbe8 0fbe8f6f4
Carries: 0 0 0
Top half: f4f7 f6f4 fbe8
Bottom half: e8fa fbe8 f6f4
----- ----- -----
Sum2: 1ddf1 1f2dc 1f2dc
ddf1 f2dc f2dc
Carrys: 1 1 1
---- ---- ----
Sum3: ddf2 f2dd f2dd
Final Swap: ddf2 ddf2 ddf2
В заключение приводится пример суммирования в виде двух групп, из которых вторая начинается на нечетной границе.
Byte-by-byte Normal
Order
Byte 0/1: 00 01 0001
Byte 2/ : f2 (00) f200
--- --- -----
Sum1: f2 01 f201
Byte 4/5: 03 f4 03f4
Byte 6/7: f5 f6 f5f6
Byte 8/: f7 (00) f700
--- --- -----
Sum2: 1f0ea
Sum2: f0ea
Carry: 1
-----
Sum3: f0eb
Sum1: f201
Sum3 byte swapped: ebf0
-----
Sum4: 1ddf1
Sum4: ddf1
Carry: 1
-----
Sum5: ddf2
4. Примеры реализации
Ниже приводятся примеры реализации алгоритма подсчета контрольных сумм Internet, которые доказали свою эффективность для разных типов CPU. В каждом случае приводится ядро алгоритма без включения дополнительного кода (например, свящывания подпрограмм).
4.1. Код на языке C
Приведенный ниже пример на языке 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;
}
4.2. Motorola 68020
Ниже приведен пример ассемблерной реализации алгоритма для процессора Motorola 68020. Этот вариант использует суммирование 32-битовых значений в один прием и использует внутренний цикл сложения с 16 операциями. Для простоты была опущена логика дополнения последнего слова для случаев, когда число суммируемых байтов не кратно 4. Результат сохраняется в регистре d0.
При тактовой частоте процессора 20 МГц время расчета контрольной суммы составляет 134 мксек/кбайт. Разработал этот алгоритм Van Jacobson.
movl d1,d2
lsrl #6,d1 | count/64 = # число проходов цикла
andl #0x3c,d2 | Нахождение частей блока
negl d2
andb #0xf,cc | Сброс X (расширенный флаг переноса)
jmp [email protected]
(2$-.-2:b,d2) | Переход в цикл
1$: | Начало внутреннего цикла...
movl [email protected]
+,d2 | Выборка 32-битового слова
addxl d2,d0 | Сложение слова и предыдущего переноса
movl [email protected]
+,d2 | Выборка 32-битового слова
addxl d2,d0 | Сложение слова и предыдущего переноса
| ... еще 14 повторов
2$:
dbra d1,1$ | (Отметим, что dbra не воздействует на X)
movl d0,d1 | Вталкивание 32 битов суммы в 16 битов
swap d1 | (Отметим, что swap не воздействует на X)
addxw d1,d0
jcc 3$
addw #1,d0
3$:
andl #0xffff,d0
4.3. Cray
Ниже приводится ассемблерная реализация алгоритма для процессора Cray, которую предложил Charley Kline. Расчет контрольной суммы производится как векторная операция, обеспечивающая одновременное сложение до 512 байтов с базовым блоком суммирования 32 бита. Для простоты из примера исключены фрагменты, обеспечивающие возможность работы с короткими блоками.
Регистр A1 содержит адрес 512-байтового блока памяти для контрольной суммы. Две первых копии данных загружаются в два векторных регистра. Один вектор сдвигается вправо на 32 бита, а для второго используется операция AND с 32-битовой маской. После этого векторы складываются. Поскольку все эти операции связаны в цепочку, они дают один результат на каждый цикл процессора. Далее производится сжатие (collaps) результирующего вектора в цикле, который прибавляет каждый элемент к скалярному регистру. В заключение выполняется перенос и результат помещается в 16 битов.
EBM
A0 A1
VL 64 используются полные векторы
S1 <32 формируется 32-битовая маска из правой части.
A2 32
V1 ,A0,1 загрузка пакета в V1
V2 S1&V1 формирование "правых" 32 битов в V2.
V3 V1>A2 формирование "левых" 32 битов в V3.
V1 V2+V3 Сложение.
A2 63 Подготовка к сжатию в скаляр.
S1 0
S4 <16 Form 16-bit mask from the right.
A4 16
CK$LOOP S2 V1,A2
A2 A2-1
A0 A2
S1 S1+S2
JAN CK$LOOP
S2 S1&S4 формирование " правых" 16 битов в S2
S1 S1>A4 формирование " левых" 16 битов в S1
S1 S1+S2
S2 S1&S4 формирование " правых" 16 битов в S2
S1 S1>A4 формирование " левых" 16 битов в S1
S1 S1+S2
S1 #S1 Получение дополнения до 1
CMR В этой точке S1 будет содержать контрольную сумму.
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 Count/64 в RCOUNT.
AR RCOUNT,RONE +1 = # число циклов.
SRL RMOD,26 Размер частичного блока в RMOD.
AR RADDR,R3 Выравнивание для компенсации перехода
S RADDR,=F(64) в цикл.
SRL RMOD,1 (RMOD/4)*2 - индекс "полуслов".
LH RMOD,DOPEVEC9(RMOD) используется специальный вектор для
B LOOP(RMOD) смещения и перехода в цикл...
*
* Внутренний цикл:
*
LOOP AL RSUM,0(,RADDR) Сложить логические слова
BC 12,*+6 Переход, если нет переноса
AR RCARRY,RONE Добавит ь 1 переноса
AL RSUM,4(,RADDR) Сложить логические слова
BC 12,*+6 Branch i f no carry
AR RCARRY,RONE Добавить 1 переноса
*
* ... еще 14 повторов ...
*
A RADDR,=F'64' Увеличить адресный указатель
BCT RCOUNT,LOOP Перейти к Count
*
* Прибавить переносы к сумме и "затолкнуть" в 16 битов
*
ALR RCARRY,RSUM Сложить слова SUM и CARRY
BC 12,*+6 и учесть возможный перенос
AR RCARRY,RONE
SRDL RCARRY,16 Поместить 32-битовую сумму
SRL RSUM,16 в 16 битов
ALR RCARRY,RSUM
C RCARRY,=X'0000FFFF' Прибавить оставшийся перенос
BNH DONE
S RCARRY,=X'0000FFFF'
DONE X RCARRY,=X'0000FFFF' Дополнить до 1
Литература
| [1] | Cerf, V.G. и Kahn, Robert E., «A Protocol for Packet Network Communications», IEEE Transactions on Communications, vol. COM-22, No. 5, Май 1974. |
| [2] | Kahn, Robert E., «The Organization of Computer Resources into a Packet Radio Network», IEEE Transactions on Communications, vol. COM-25, no. 1, pp. 169-178, Январь 1977. |
| [3] | Jacobs, Irwin, et al., «CPODA — A Demand Assignment Protocol for SatNet», Fifth Data Communications Symposium, September 27-9, 1977, Snowbird, Utah |
| [4] | Bolt Beranek and Newman, Inc. «Specifications for the Interconnection of a Host and an IMP», Report 1822, Январь 1976 edition. |
| [5] | Dean, Richard A., «Elements of Abstract Algebra», John Wyley and Sons, Inc., 1966 |
| [6] | Peterson, W. Wesley, «Error Correcting Codes», M.I.T. Press Cambridge MA, 4th edition, 1968. |
| [7] | Avizienis, Algirdas, «A Study of the Effectiveness of Fault-Detecting Codes for Binary Arithmetic», Jet Propulsion Laboratory Technical Report No. 32-711, September 1, 1965. |
| [8] | Kirstein, Peter, private communication |
| [9] | Cerf, V. G. и Postel, Jonathan B., «Specification of Internetwork Transmission Control Program Version 3», University of Southern California Information Sciences Institute, Январь 1978. |
| [10] | Digital Equipment Corporation, «PDP-10 Reference Handbook», 1970, pp. 114-5. |
| [11] | Swanson, Robert, «Understanding Cyclic Redundancy Codes», Computer Design, November, 1975, pp. 93-99. |
| [12] | Clements, Robert C., private communication. |
| [13] | Conklin, Peter F., and Rodgers, David P., «Advanced Minicomputer Designed by Team Evaluation of Hardware/Software Tradeoffs», Computer Design, Апрель 1978, pp. 136-7. |