Многие протоколы и алгоритмы требуют сериализации или перечисления связанных сущностей. Например, протокол связи должен знать, идет ли какой-то пакет «до» или «после» какого-то другого пакета. IETF ( Internet Engineering Task Force ) RFC 1982 пытается определить «арифметику серийных номеров» для целей манипулирования и сравнения этих порядковых номеров . Короче говоря, когда абсолютное значение серийного номера уменьшается более чем на половину максимального значения (например, 128 в 8-битном значении), оно считается «после» первого, тогда как другие уменьшения считаются «до».
Эта задача гораздо сложнее, чем может показаться на первый взгляд, поскольку большинство алгоритмов используют фиксированный размер ( двоичные ) представления для порядковых чисел. Часто важно, чтобы алгоритм не «сломался», когда числа становятся настолько большими, что они увеличиваются в последний раз и «оборачиваются» вокруг своих максимальных числовых диапазонов (мгновенно переходят от большого положительного числа к 0 или большому отрицательному числу). Некоторые протоколы предпочитают игнорировать эти проблемы и просто используют очень большие целые числа для своих счетчиков, в надежде, что программа будет заменена (или они выйдут из эксплуатации) до того, как возникнет проблема (см. Y2K ).
Многие протоколы связи применяют арифметику серийных номеров к порядковым номерам пакетов в своей реализации протокола скользящего окна . Некоторые версии TCP используют защиту от перевернутых порядковых номеров (PAWS) . PAWS применяет ту же арифметику серийных номеров к временным меткам пакетов, используя временную метку как расширение старших битов порядкового номера. [1]
Обсуждается только добавление небольшого положительного целого числа к порядковому номеру и сравнение двух порядковых номеров. Обсуждаются только беззнаковые двоичные реализации, с произвольным размером в битах, отмеченным в RFC (и ниже) как "SERIAL_BITS".
Добавление целого числа к порядковому номеру представляет собой простое сложение беззнаковых целых чисел, за которым следует операция беззнакового остатка для возврата результата в допустимый диапазон (обычно неявно в беззнаковом сложении в большинстве архитектур):
Добавление значения ниже 0 или выше 2 SERIAL_BITS−1 − 1 не определено. По сути, добавление значений за пределами этого диапазона приведет к «переносу» результирующего порядкового номера и (часто) приведет к числу, которое считается «меньше» исходного порядкового номера.
Представлен способ сравнения двух порядковых номеров i 1 и i 2 (целочисленных представлений без знака порядковых номеров s 1 и s 2 ).
Равенство определяется как простое числовое равенство.
Представленный для сравнения алгоритм сложен, поскольку он должен учитывать, близко ли первое порядковое число к «концу» своего диапазона значений, и, таким образом, меньшее «обернутое» число может фактически считаться «большим», чем первое порядковое число. Таким образом, i 1 считается меньшим, чем i 2, только если
Алгоритмы, представленные в RFC, имеют по крайней мере один существенный недостаток: существуют порядковые номера, для которых сравнение не определено. Поскольку многие алгоритмы реализуются независимо несколькими независимыми сотрудничающими сторонами, часто невозможно предотвратить возникновение всех таких ситуаций.
Авторы RFC 1982 признают это, не предлагая общего решения:
Хотя можно было бы определить тест таким образом, что неравенство не будет обладать этим удивительным свойством, будучи определенным для всех пар значений, такое определение было бы излишне обременительным для реализации и трудным для понимания, и все равно допускало бы случаи, когда
s1 < s2 и (s1 + 1) > (s2 + 1)что столь же неинтуитивно.
Таким образом, проблемный случай остается неопределенным, реализации могут свободно возвращать либо результат, либо помечать ошибку, а пользователи должны заботиться о том, чтобы не зависеть от какого-либо конкретного результата. Обычно это означает, что не следует позволять этим конкретным парам чисел сосуществовать.
Таким образом, часто бывает трудно или невозможно избежать всех «неопределенных» сравнений порядковых номеров. Однако доступно относительно простое решение. Отображение беззнаковых порядковых номеров на знаковые арифметические операции дополнения до двух определяет каждое сравнение любого порядкового номера, а сама операция сравнения значительно упрощается. Все сравнения, указанные в RFC, сохраняют свои исходные значения истинности; затрагиваются только ранее «неопределенные» сравнения.
Алгоритм RFC 1982 определяет, что для N -битных порядковых номеров существует 2 N −1 − 1 значений, считающихся «больше чем», и 2 N −1 − 1 значений, считающихся «меньше чем». Сравнение с оставшимся значением (находящимся ровно на 2 N −1 расстоянии) считается «неопределенным».
Большинство современных аппаратных средств реализуют двоичные арифметические операции с дополнением до двух со знаком . Эти операции полностью определены для всего диапазона значений для любых операндов, которые им даны, поскольку любое двоичное число размером N бит может содержать 2 N различных значений, и поскольку одно из них занято значением 0, остается нечетное количество мест для всех ненулевых положительных и отрицательных чисел. Просто существует на одно отрицательное число больше, чем положительных, которые можно представить. Например, 16-битное значение с дополнением до двух может содержать числа в диапазоне от−32 768 в+32 767 .
Таким образом, если мы просто переведем порядковые номера в целые числа с дополнительным кодом и допустим, что число порядковых номеров, считающихся «меньше», будет на одно число порядковых номеров больше, чем число порядковых номеров, считающихся «больше», то мы сможем использовать простые знаковые арифметические сравнения вместо логически неполной формулы, предложенной в RFC.
Вот несколько примеров (снова в 16 битах), сравнивающих некоторые случайные порядковые числа с порядковым числом со значением 0:
беззнаковый двоичный со знакомрасстояние между значениями последовательности-------- ------ -------- 32767 == 0x7FFF == 32767 1 == 0x0001 == 1 0 == 0x0000 == 0 65535 == 0xFFFF == −1 65534 == 0xFFFE == −2 32768 == 0x8000 == −32768
Легко видеть, что знаковая интерпретация порядковых номеров находится в правильном порядке, пока мы «вращаем» рассматриваемый порядковый номер так, чтобы его 0 совпадал с порядковым номером, с которым мы его сравниваем. Оказывается, это просто делается с помощью беззнакового вычитания и простой интерпретации результата как знакового числа в дополнительном коде. Результатом является знаковое «расстояние» между двумя порядковыми номерами. Еще раз, если i1и i2являются беззнаковыми двоичными представлениями порядковых номеров s 1 и s 2 , расстояние от s 1 до s 2 равно
расстояние = ( со знаком )( i1 - i2 ) Если расстояние равно 0, числа равны. Если оно < 0, то s 1 «меньше» или «перед» s 2 . Просто, чисто и эффективно, и полностью определено. Однако не без сюрпризов.
Вся арифметика порядковых чисел должна иметь дело с «обёртыванием» порядковых чисел; число 2 N −1 равноудалено в обоих направлениях, в терминах порядковых чисел RFC 1982. В нашей математике они оба считаются «меньше» друг друга:
расстояние1 = ( со знаком )( 0x8000 - 0x0 ) == ( со знаком ) 0x8000 == -32768 < 0 расстояние2 = ( со знаком )( 0x0 - 0x8000 ) == ( со знаком ) 0x8000 == -32768 < 0 Это, очевидно, верно для любых двух порядковых чисел, расстояние между которыми составляет 0x8000.
Более того, реализация арифметики серийных чисел с использованием арифметики дополнения до двух подразумевает серийные числа с длиной в битах, соответствующей целочисленным размерам машины; обычно 16-бит, 32-бит и 64-бит. Реализация 20-битных серийных чисел требует сдвигов (предполагая 32-битные int):
расстояние = ( со знаком )(( i1 << 12 ) - ( i2 << 12 ))