Aritmética do número de série - Serial number arithmetic

Muitos protocolos e algoritmos requerem a serialização ou enumeração de entidades relacionadas. Por exemplo, um protocolo de comunicação deve saber se algum pacote vem "antes" ou "depois" de algum outro pacote. A RFC 1982 da IETF ( Internet Engineering Task Force ) tenta definir a "aritmética do número de série" para fins de manipulação e comparação desses números de seqüência .  

Esta tarefa é um pouco mais complexa do que pode parecer à primeira vista, porque a maioria dos algoritmos usa representações de tamanho fixo ( binário ) para números de sequência. Muitas vezes é importante para o algoritmo não "quebrar" quando os números se tornam tão grandes que são incrementados uma última vez e "envolvem" seus intervalos numéricos máximos (ir instantaneamente de um grande número positivo para 0 ou um grande número negativo ) Alguns protocolos optam por ignorar esses problemas e simplesmente usar números inteiros muito grandes para seus contadores, na esperança de que o programa seja substituído (ou eles se aposentem) antes que o problema ocorra (consulte Y2K ).

Muitos protocolos de comunicação aplicam aritmética de número de série a números de sequência de pacote em sua implementação de um protocolo de janela deslizante . Algumas versões do TCP usam proteção contra números de sequência agrupados (PAWS) . O PAWS aplica a mesma aritmética de número de série aos carimbos de data / hora do pacote, usando o carimbo de data / hora como uma extensão dos bits de ordem superior do número de sequência.

Operações em números de sequência

Apenas a adição de um pequeno inteiro positivo a um número de sequência e a comparação de dois números de sequência são discutidas. Apenas implementações binárias sem sinal são discutidas, com um tamanho arbitrário em bits anotado em todo o RFC (e abaixo) como "SERIAL_BITS".

Adição

Adicionar um inteiro a um número de sequência é uma simples adição de inteiro sem sinal, seguida por uma operação de módulo sem sinal para trazer o resultado de volta ao intervalo (geralmente implícito na adição sem sinal, na maioria das arquiteturas):

s' = (s + n) modulo (2^SERIAL_BITS)

Adição de um valor fora do intervalo

[0 .. (2^(SERIAL_BITS - 1) - 1)]

é indefinido. Basicamente, adicionar valores além desse intervalo fará com que o número de sequência resultante "empacote" e (frequentemente) resulte em um número que é considerado "menor que" o número de sequência original.

Comparação

É apresentado um meio de comparar dois números de sequência i1 e i2 (as representações inteiras sem sinal dos números de sequência s 1 e s 2 ).

A igualdade é definida como igualdade numérica simples. O algoritmo apresentado para comparação é complexo, tendo que levar em consideração se o primeiro número da sequência está próximo ao "fim" de sua faixa de valores, e assim um número "embrulhado" menor pode na verdade ser considerado "maior" do que a primeira sequência. número. Portanto, i1 é considerado menos do que i2 apenas se

(i1 < i2 and i2 - i1 < 2^(SERIAL_BITS - 1)) or
(i1 > i2 and i1 - i2 > 2^(SERIAL_BITS - 1))

Da mesma forma, i1 é considerado maior do que i2 apenas se

(i1 < i2 and i2 - i1 > 2^(SERIAL_BITS - 1)) or
(i1 > i2 and i1 - i2 < 2^(SERIAL_BITS - 1))

Deficiências

Os algoritmos apresentados pela RFC têm pelo menos uma lacuna significativa: existem números de sequência para os quais a comparação é indefinida. Uma vez que muitos algoritmos são implementados independentemente por várias partes cooperantes independentes, muitas vezes é impossível evitar que todas essas situações ocorram.

Os autores da RFC   1982 reconhecem isso sem oferecer uma solução geral:

Embora fosse possível definir o teste de forma que a desigualdade não tivesse essa propriedade surpreendente, embora fosse definida para todos os pares de valores, tal definição seria desnecessariamente onerosa de implementar e difícil de entender, e ainda seria permitir casos onde

s1 < s2 and (s1 + 1) > (s2 + 1)

o que é igualmente não intuitivo.

Assim, a pasta de problemas é deixada indefinida, as implementações são livres para retornar qualquer um dos resultados ou sinalizar um erro e os usuários devem tomar cuidado para não depender de nenhum resultado específico. Normalmente, isso significará evitar a coexistência desses pares de números específicos.

Assim, muitas vezes é difícil ou impossível evitar todas as comparações "indefinidas" de números de sequência. No entanto, uma solução relativamente simples está disponível. Ao mapear os números de sequência sem sinal em operações aritméticas de complemento de dois com sinal , cada comparação de qualquer número de sequência é definida e a própria operação de comparação é dramaticamente simplificada. Todas as comparações especificadas pelo RFC retêm seus valores verdadeiros originais; apenas as comparações anteriormente "indefinidas" são afetadas.

Solução geral

O algoritmo RFC   1982 especifica que, para números de sequência de N bits, há 2 ( N −1)  - 1 valores considerados "maiores que" e 2 ( N −1)  - 1 considerado "menor que". A comparação com o valor restante (exatamente 2 N −1 -distant) é considerada "indefinida".

A maioria dos implementos de hardware modernos assinou operações aritméticas binárias de complemento de dois . Essas operações são totalmente definidas para todo o intervalo de valores de quaisquer operandos que sejam fornecidos, uma vez que qualquer número binário de N bits pode conter 2 N valores distintos e, uma vez que um deles é tomado pelo valor 0, há um número ímpar de manchas deixadas para todos os números positivos e negativos diferentes de zero. Existe simplesmente mais um número negativo representável do que positivo. Por exemplo, um valor de complemento de 2 de 16 bits pode conter números que variam de -32768 a +32767.

Portanto, se simplesmente refazermos os números de sequência como inteiros de complemento de 2 e permitirmos que haja mais um número de sequência considerado "menor que" do que números de sequência considerados "maiores que", devemos ser capazes de usar comparações aritméticas com sinais simples. da fórmula logicamente incompleta proposta pela RFC.

Aqui estão alguns exemplos (em 16 bits, novamente), comparando alguns números de sequência aleatórios com o número de sequência com o valor 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

É fácil ver que a interpretação assinada dos números de sequência está na ordem correta, contanto que "giremos" o número de sequência em questão de modo que seu 0 corresponda ao número de sequência com o qual o estamos comparando. Acontece que isso é feito simplesmente usando uma subtração sem sinal e simplesmente interpretando o resultado como um número de complemento de dois com sinal. O resultado é a "distância" sinalizada entre os dois números de sequência. Mais uma vez, se i1 e i2 são as representações binárias sem sinal dos números de sequência s 1 e s 2 , a distância de s 1 a s 2 é

distance = (signed)(i1 - i2)

Se a distância for 0, os números são iguais. Se for <0, então s 1 é "menor que" ou "antes de" s 2 . Simples, limpo e eficiente e totalmente definido. Porém, não sem surpresas.

Toda aritmética de número de seqüência deve lidar com o "empacotamento" de números de seqüência; o número 2 N −1 é equidistante em ambas as direções, em termos de número de sequência RFC   1982 . Em nossa matemática, ambos são considerados "menos do que" um ao outro:

distance1 = (signed)(0x8000 - 0x0)    == (signed)0x8000 == -32768 < 0
distance2 = (signed)(0x0    - 0x8000) == (signed)0x8000 == -32768 < 0

Isso é obviamente verdadeiro para quaisquer dois números de sequência com distância de 0x8000 entre eles.

Além disso, a implementação da aritmética de número de série usando a aritmética de complemento de dois implica números de série de um comprimento de bit correspondente aos tamanhos inteiros da máquina; geralmente 16 bits, 32 bits e 64 bits. A implementação de números de série de 20 bits precisa de mudanças (assumindo ints de 32 bits):

distance = (signed)((i1 << 12) - (i2 << 12))

Veja também

Referências

links externos