Changement de bits dans les sommes de contrôle Internet

Question

C'est certainement une question très stupide, mais pour une raison quelconque, j'ai des problèmes avec les calculs de total de contrôle Internet. Tous les algorithmes rétrospectifs essentiellement quelque chose comme ceci:

WORD chksm(WORD *startpos, WORD checklen){ 
ulong sum = 0; 
WORD answer = 0; 

while (checklen > 1) 
{ 
    sum += *startpos++; 
    checklen -= 2; 
} 

if (checklen == 1) 
{ 
    *(BYTE *)(&answer) = *(BYTE *)startpos; 
    sum += answer; 
} 

sum = (sum >> 16) + (sum & 0xffff); 
sum += (sum >> 16); 
answer = ~sum; 

return answer;} 

Je suis clair sur tout, sauf pour la ligne:

sum += (sum >> 16); 

Il ressemble à la ligne immédiatement avant d'ajouter les 16 bits à la 16 bits en bas, en laissant tous les zéros dans les 16 bits supérieurs. Si c'est le cas, alors, somme >> 16 ne serait-elle pas égale à zéro? Et si oui, pourquoi cette ligne est là? Ou suis-je (probablement) en train de subir un échec mental complet aujourd'hui?

Answer 1

Vous avez presque raison.

Les 16 bits élevés auraient pu être 1 en raison d'un report. Par exemple, FFFF + FFFF => 1FFFE ou peut-être FFFF + 1 => 10000.

Answer 2

Je pense qu'une ulong était de 32 bits de large qui signifie que:

sum = (sum >> 16) + (sum & 0xffff) 
sum += (sum >> 16); 

Ajoute les bits de sicteen supérieurs et des bits de sisteen bas ensemble. Et puis la ligne suivante fait la somme du résultat des seize premiers bits; qui pourrait en avoir un en raison d'une opération de portage.

Answer 3

Cela fait partie de la définition de la somme du complément à un. Vous prenez tous les bits de débordement et les rajoutez aux 16 bits inférieurs. Les ajouter de nouveau pourrait causer un débordement supplémentaire, donc vous le répétez jusqu'à ce que les bits supérieurs finissent tous zéro. Donc, sur le plan conceptuel, il est ceci:

while (sum >> 16 != 0) { 
    sum = (sum >> 16) + (sum & 0xffff); 
} 

Cependant cette boucle ne sera jamais exécuté au moins deux fois, une boucle explicite n'est pas nécessaire. Après le premier ajout, il peut y avoir ou non un débordement avec un bit de retenue se terminant dans les 16 bits supérieurs. Dans ce cas, les 16 bits supérieurs seront 0x0001 et vous devrez faire un plus plus d'ajouter que bit de report avant.

Imaginez le pire des cas où la somme finit comme 0xffffffff après la première boucle while. Ensuite, les ajouts procédez comme suit:

sum = (0xffffffff >> 16) + (0xffffffff & 0xffff) 
    = 0xffff + 0xffff 
    = 0x1fffe 

sum = (0x1fffe >> 16) + (0x1fffe & 0xffff) 
    = 0x1 + 0xfffe 
    = 0xffff 

Et avec deux ajouts nous avons terminé les 16 bits supérieurs sont maintenant claires. C'est le cas le plus défavorable, donc la boucle peut ainsi être déroulée à deux ajouts.

(Et puis après tout ce que vous prenez le complément à un de la somme finale, ce qui conduit au nom très déroutant pour cela:. Le complément à un de la somme du complément de celui Il m'a fallu beaucoup de temps pour envelopper ma tête Autour de cela, la première fois que je l'ai mis en œuvre — en particulier que la somme d'un complément n'implique pas l'opérateur de complément ~.)