RFC: 1071
Оригинал: Computing the Internet Checksum
Категория: Не определено
Дата публикации:
Авторы: , ,
Перевод: Николай Малых

RFC 1071, Страница 2 из 9

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-битовой суммы (см. примеры ниже). Допускаются любые перестановки, которые будут обеспечивать сложение всех четных байтов в один байт суммы, а всех нечетных — в другой байт.

2007 - 2017 © Русские переводы RFC, IETF, ISOC.