AAA

RFC 1071 — Расчет контрольных сумм в Internet

Статус документа

В этом документе дается обзор эффективности методов и алгоритмов расчета контрольных сумм Internet. Документ не является стандартом, но описывает ряд полезных методов реализации. Документ может распространяться свободно.

1. Введение

В этом документе обсуждаются методы эффективного расчета контрольных сумм, используемых стандартными протоколами Internet — IP, UDP и TCP.

Эффективность расчета контрольных сумм очень важна с точки зрения производительности. В результате эффективной реализации остальных компонент протокольной обработки расчет контрольных сумм стал, например, одним из факторов, ограничивающих производительность TCP. Обычно для процедур расчета контрольных сумм используется ручная оптимизация с учетом особенностей работы конкретного процессора — экономия доли микросекунды в расчете на один байт данных TCP может привести к существенному снижению суммарного расхода процессорного времени.

В общих чертах алгоритм расчета контрольной суммы очень прост:

  1. Соседние октеты информации, для которой создается контрольная сумма, объединяются в 16-битовые целые числа и для этих чисел формируется 16-битовое поразрядное дополнение до 1.

  2. При расчете контрольной суммы значение самого поля контрольной суммы принимается нулевым. Для 16-битовых поразрядных дополнений вычисляется сумма. Для полученного в результате 16-битового целого числа создается 16-битовое поразрядное дополнение до 1 и помещается в поле контрольной суммы.

  3. Для проверки контрольной суммы вычисляется сумма поразрядных дополнений до 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. Расчет контрольной суммы

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

Ниже описано еще несколько методов ускорения расчета контрольных сумм:

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     pc@(2$-.-2:b,d2)  | Переход в цикл

1$:     | Начало внутреннего цикла...

    movl    a0@+,d2     |  Выборка 32-битового слова
    addxl   d2,d0       |    Сложение слова и предыдущего переноса
    movl    a0@+,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. and Kahn, Robert E., «A Protocol for Packet Network Communications», IEEE Transactions on Communications, vol. COM-22, No. 5, May 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, January 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, January 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. and Postel, Jonathan B., «Specification of Internetwork Transmission Control Program Version 3», University of Southern California Information Sciences Institute, January 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, April 1978, pp. 136-7.

Перевод на русский язык

Николай Малых, moc.milib@hkylamn