Арифметика серийных номеров - Serial number arithmetic
Много протоколы и алгоритмы требуют сериализации или перечисления связанных сущностей. Например, протокол связи должен знать, приходит ли какой-то пакет «до» или «после» другого пакета. В IETF (Инженерная группа Интернета ) RFC 1982 пытается определить "Арифметику серийных номеров" с целью манипулирования и сравнения этих порядковые номера.
Эта задача намного сложнее, чем может показаться на первый взгляд, потому что большинство алгоритмов используют фиксированный размер (двоичный ) представления для порядковых номеров. Часто важно, чтобы алгоритм не «ломался», когда числа становятся настолько большими, что они увеличиваются в последний раз и «оборачиваются» вокруг своих максимальных числовых диапазонов (мгновенно переходят от большого положительного числа к 0 или большому отрицательному числу). номер). К сожалению, некоторые протоколы предпочитают игнорировать эти проблемы и просто используют очень большие целые числа для своих счетчиков в надежде, что программа будет заменена (или они будут удалены) до того, как проблема возникнет (см. Y2K ).
Многие протоколы связи применяют арифметику серийных номеров к порядковым номерам пакетов в их реализации протокол скользящего окна. Некоторые версии TCP используют защита от упакованных порядковых номеров (PAWS). PAWS применяет ту же арифметику серийных номеров к отметкам времени пакетов, используя отметку времени как расширение старших битов порядкового номера.[1]
Операции с порядковыми номерами
Только добавление небольшого позитива целое число к порядковому номеру и сравнение двух порядковых номеров обсуждаются. Обсуждаются только двоичные реализации без знака с произвольным размером в битах, отмеченным в RFC (и ниже) как «SERIAL_BITS».
Добавление
Добавление целого числа к порядковому номеру - это простое добавление целого числа без знака, за которым следует беззнаковое Операция по модулю чтобы вернуть результат в диапазон (обычно неявно в беззнаковом сложении на большинстве архитектур).
s '= (s + n) по модулю (2 ^ SERIAL_BITS)
Добавление значения вне диапазона
[0 .. (2 ^ (SERIAL_BITS - 1) - 1)]
не определено. По сути, добавление значений за пределами этого диапазона приведет к "переносу" результирующего порядкового номера и (часто) к получению числа, которое считается "меньше" исходного порядкового номера!
Сравнение
Представлено средство сравнения двух порядковых номеров i1 и i2 (беззнаковые целочисленные представления порядковых номеров s1 и s2).
Равенство определяется как простое числовое равенство. Алгоритм, представленный для сравнения, очень сложен, поскольку необходимо учитывать, находится ли первый порядковый номер близко к «концу» своего диапазона значений, и, таким образом, меньшее «свернутое» число может фактически считается "большим", чем первый порядковый номер. Таким образом, i1 считается меньше i2, только если:
(i1i2 и i1 - i2> 2 ^ (SERIAL_BITS - 1))
Аналогично, i1 считается больше i2, только если:
(i12 ^ (SERIAL_BITS - 1)) или (i1> i2 и i1 - i2 <2 ^ (SERIAL_BITS - 1))
Недостатки
Алгоритмы, представленные в RFC, имеют по крайней мере один существенный недостаток: существуют порядковые номера, для которых сравнение не определено. Поскольку многие алгоритмы реализуются независимо несколькими независимыми взаимодействующими сторонами, часто невозможно предотвратить возникновение всех таких ситуаций.
Хотя можно было бы определить тест таким образом, чтобы неравенство не обладало этим удивительным свойством, хотя оно было определено для всех пар значений, такое определение было бы излишне обременительным для реализации, трудным для понимания и все же разрешить случаи, когда s1(s2 + 1), что так же неинтуитивно. Таким образом, проблемный случай остается неопределенным, реализации могут возвращать либо результат, либо отмечать ошибку, и пользователи должны позаботиться о том, чтобы не зависеть от какого-либо конкретного результата. Обычно это означает недопущение сосуществования этих конкретных пар чисел.
Таким образом, часто бывает трудно или невозможно избежать всех «неопределенных» сравнений порядковых номеров. Однако доступно относительно простое решение. Путем отображения беззнаковых порядковых номеров на подписанные Два дополнения арифметические операции, каждое сравнение любого порядкового номера определяется, а сама операция сравнения значительно упрощается. Все сравнения, указанные в RFC, сохраняют свои исходные значения истинности; затрагиваются только ранее "неопределенные" сравнения.
Общее решение
В RFC 1982 алгоритм определяет, что для N-битных порядковых номеров существует 2(N − 1)-1 значение считается "больше чем", и 2(N − 1)−1 считается «меньше чем». Сравнение с оставшимся значением (ровно 2N − 1 дальний) считается "неопределенным".
Подписано самое современное оборудование Два дополнения двоичные арифметические операции. Эти операции полностью определены для всего диапазона значений любых операндов, которые им заданы, поскольку любое N-битное двоичное число может содержать 2N различных значений, и поскольку одно из них занято значением 0, остается нечетное количество пятен для всех ненулевых положительных и отрицательных чисел. Просто существует представимое отрицательное число на одно больше, чем положительных. , 16-битное значение дополнения до 2 может содержать числа в диапазоне от -32768 до +32767.
Таким образом, если мы просто переопределим порядковые номера как целые числа с дополнением до 2 и допустим, что еще один порядковый номер считается «меньше чем», чем порядковые номера, считающиеся «больше чем», мы должны иметь возможность использовать простые арифметические сравнения со знаком. вместо логически неполной формулы, предложенной RFC.
Вот несколько примеров (снова в 16 битах), сравнивающих некоторые случайные порядковые номера с порядковым номером со значением 0.
беззнаковая двоичная знаковая последовательность значений расстояние -------- ------ -------- 32767 == 0x7fff == 32767 1 == 0x0001 == 1 0 == 0x0000 == 0 65535 == 0xffff == −1 65534 == 0xfffe == −2 32768 == 0x8000 == −32768
Легко видеть, что знаковая интерпретация порядковых номеров находится в правильном порядке, если мы «вращаем» рассматриваемый порядковый номер так, чтобы его 0 совпадал с порядковым номером, с которым мы его сравниваем. Оказывается, это просто делается с помощью беззнакового вычитания и простой интерпретации результата как знакового дополнения до двух. В результате получается «расстояние» со знаком между двумя порядковыми номерами. Еще раз, если i1 и i2 являются беззнаковыми двоичными представлениями порядковых номеров s1 и s2, расстояние от s1 до s2 равно:
расстояние = (подписанный)( i1 - i2 )Если расстояние равно 0, числа равны. Если он <0, то s1 «меньше» или «раньше» s2. Простой, чистый, эффективный и полностью определенный. Однако не обошлось и без сюрпризов.
Вся арифметика порядковых номеров должна иметь дело с «упаковкой» порядковых номеров; число 2N − 1 равноудалена в обоих направлениях, в RFC 1982 условия порядкового номера. В нашей математике они оба считаются «меньше» друг друга:
расстояние1 = (подписанный)(0x8000 - 0x0) == (подписанный)0x8000 == -32768 < 0 расстояние2 = (подписанный)(0x0 - 0x8000) == (подписанный)0x8000 == -32768 < 0Очевидно, это верно для любых двух порядковых номеров с расстоянием между ними 0x8000.
Кроме того, реализация арифметики серийных номеров с использованием арифметики с дополнением до двух подразумевает серийные номера битовой длины, соответствующие целочисленным размерам машины; обычно 16-, 32- и 64-битные. Реализация 20-битных серийных номеров требует сдвигов (при условии 32-битных целых чисел):
расстояние = (подписанный)((i1 << 12) - (i2 << 12))