Арифметика серийного номера
Многие протоколы и алгоритмы требуют сериализации или перечисления связанных объектов. Например, протокол связи должен знать, приходит ли какой-то пакет «до» или «после» другого пакета. IETF инжинирингу ( Специальная группа по интернет- ) RFC 1982 пытается определить «арифметику серийных номеров» для целей манипулирования и сравнения этих порядковых номеров . Короче говоря, когда значение абсолютного серийного номера уменьшается более чем на половину максимального значения (например, 128 в 8-битном значении), оно считается «после» первого, тогда как другие уменьшения считаются «до» .
Эта задача гораздо сложнее, чем может показаться на первый взгляд, поскольку большинство алгоритмов используют представления фиксированного размера ( двоичные ) для порядковых номеров. Часто важно, чтобы алгоритм не «сломался», когда числа становятся настолько большими, что они увеличиваются в последний раз и «обертываются» вокруг своих максимальных числовых диапазонов (мгновенно переходя от большого положительного числа к 0 или к большому отрицательному числу). ). Некоторые протоколы предпочитают игнорировать эти проблемы и просто используют очень большие целые числа для своих счетчиков в надежде, что программа будет заменена (или они уйдут из эксплуатации) до того, как возникнет проблема (см. Y2K ).
Многие протоколы связи применяют арифметику серийных номеров к порядковым номерам пакетов в своей реализации протокола скользящего окна . Некоторые версии TCP используют защиту от завернутых порядковых номеров (PAWS) . PAWS применяет ту же арифметику серийного номера к временным меткам пакетов, используя временную метку как расширение старших битов порядкового номера. [1]
Операции с порядковыми номерами [ править ]
только добавление небольшого положительного целого числа Обсуждаются к порядковому номеру и сравнение двух порядковых номеров. Обсуждаются только беззнаковые двоичные реализации с произвольным размером в битах, отмеченным в RFC (и ниже) как «SERIAL_BITS».
Дополнение [ править ]
Добавление целого числа к порядковому номеру представляет собой простое сложение целого числа без знака, за которым следует операция по модулю без знака , чтобы вернуть результат в диапазон (обычно подразумеваемый при сложении без знака в большинстве архитектур):
- s ' = ( s + n ) по модулю 2 SERIAL_BITS
Добавление значения ниже 0 или выше 2 SERIAL_BITS-1 − 1 не определено. По сути, добавление значений за пределами этого диапазона приведет к «переворачиванию» результирующего порядкового номера и (часто) к получению числа, которое считается «меньше» исходного порядкового номера.
Сравнение [ править ]
средство сравнения двух порядковых номеров i 1 и i 2 (беззнаковое целочисленное представление порядковых номеров s 1 и s 2 Представлено ).
Равенство определяется как простое числовое равенство.
Алгоритм, представленный для сравнения, сложен: он должен учитывать, близок ли первый порядковый номер к «концу» своего диапазона значений, и, таким образом, меньшее «обернутое» число фактически может считаться «большим», чем первая последовательность. число. Таким образом, i 1 считается меньшим, чем i 2, только если
- ( я 1 < я 2 и я 2 - я 1 < 2 SERIAL_BITS-1 ) или
- ( я 1 > я 2 и я 1 - я 2 > 2 SERIAL_BITS-1 )
Недостатки [ править ]
Алгоритмы, представленные RFC, имеют как минимум один существенный недостаток: существуют порядковые номера, для которых сравнение не определено. Поскольку многие алгоритмы реализуются независимо несколькими независимыми сотрудничающими сторонами, зачастую невозможно предотвратить возникновение всех подобных ситуаций.
Авторы RFC 1982 признает это, не предлагая общего решения:
Хотя можно было бы определить тест таким образом, чтобы неравенство не обладало бы этим удивительным свойством, будучи определено для всех пар значений, такое определение будет неоправданно обременительны для реализации и трудны для понимания, и по-прежнему будет допускать случаи, когда
s1 < s2 and (s1 + 1) > (s2 + 1)что столь же неинтуитивно.
Таким образом, проблемный случай остается неопределенным, реализации могут свободно вернуть либо результат, либо отметить ошибку, и пользователи должны быть осторожны не зависеть от какого-либо конкретного результата. Обычно это будет означать избегая сосуществования этих конкретных пар чисел.
Таким образом, часто трудно или невозможно избежать всех «неопределенных» сравнений порядковых номеров. Однако существует относительно простое решение. Сопоставляя беззнаковые порядковые номера с арифметическими операциями дополнения до двух знаков , определяется каждое сравнение любого порядкового номера, а сама операция сравнения значительно упрощается. Все сравнения, указанные в RFC, сохраняют свои исходные значения истинности; Затрагиваются только ранее «неопределенные» сравнения.
Общее решение [ править ]
The Алгоритм RFC 1982 определяет, что для N -битных порядковых номеров существует 2 Н -1 − 1 значение считается «больше» и 2 Н -1 − 1 считается «меньше чем». Сравнение с остаточным значением (ровно 2 Н -1 -далекий) считается «неопределенным».
Большинство современных аппаратных средств реализуют со знаком до двух двоичные арифметические операции . Эти операции полностью определены для всего диапазона значений любых заданных им операндов, поскольку любое N -битное двоичное число может содержать 2 Н различные значения, и поскольку одно из них занято значением 0, для всех ненулевых положительных и отрицательных чисел остается нечетное количество мест. Просто существует на одно представимое отрицательное число больше, чем положительных. Например, 16-битное значение дополнения до 2 может содержать числа в диапазоне от -32 768 до +32 767 .
Итак, если мы просто переделаем порядковые номера как целые числа, дополняемые до 2, и позволим иметь на один порядковый номер, считающийся «меньше чем», больше, чем количество порядковых номеров, считающихся «больше», мы сможем вместо этого использовать простые арифметические сравнения со знаком. логически неполной формулы, предложенной RFC.
Вот несколько примеров (опять же в 16 битах), сравнивающих некоторые случайные порядковые номера с порядковым номером со значением 0:
unsigned binary signed
sequence value distance
-------- ------ --------
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 равно
distance = (signed)(i1 - i2)
Если расстояние равно 0, числа равны. Если оно < 0, то s 1 «меньше» или «до» s 2 . Простой, понятный, эффективный и полностью определенный. Однако не обошлось без сюрпризов.
Вся арифметика порядковых номеров должна иметь дело с «обертыванием» порядковых номеров; номер 2 Н -1 равноудалено в обоих направлениях, в RFC 1982 Термины порядкового номера . В нашей математике они оба считаются «меньше» друг друга:
distance1 = (signed)(0x8000 - 0x0) == (signed)0x8000 == -32768 < 0
distance2 = (signed)(0x0 - 0x8000) == (signed)0x8000 == -32768 < 0
Очевидно, это справедливо для любых двух порядковых номеров, расстояние между которыми составляет 0x8000.
Более того, реализация арифметики серийных номеров с использованием арифметики с дополнением до двух подразумевает, что серийные номера битовой длины соответствуют целочисленным размерам машины; обычно 16-битные, 32-битные и 64-битные. Реализация 20-битных серийных номеров требует изменений (при условии, что целые числа 32-битные):
distance = (signed)((i1 << 12) - (i2 << 12))