Minus Null
Die Prüfsummenberechnung der grundlegenden IP Protokolle benutzt das Einerkomplement. Wenn man, wie ich, gern an Paketen rumspielt, sollte man die Prüfsummenberechnung beherrschen.
Ein Ruf aus alten Tagen
Nach einem längeren Studium von Online-Quellen, die durch die Bank unergiebig waren, verwies man mich auf TAoCP Band 2. Verdammt. Das steht vor mir. Leider ist es diesmal nicht mehr als eine Sammlung von Stichpunkten. Knuth benutzt für MIX eine Darstellung mit getrenntem Vorzeichenbit.
Richtig erklärt (lesen!) wird das Einerkomplement von den Entwicklerns und Nutzern der Univac.
Kurz gesagt bietet das Einerkomplement eine einfache Ausführung von Negation (bitweises nicht), Addition (Volladdierer), Subtraktion (modifizierter Volladdierer), Multiplikation (nach links schieben) und Division (nach rechts schieben) vorzeichenbehafteter Zahlen. Diese Vorteile werden durch ein umlaufendes Carry, sowie zwei Darstellungen der Null (+0 und -0) erkauft.
Beim wesentlich bekannterem Zweierkomplement entfallen die Probleme mit der doppelten Null und dem umlaufenden Carry. Im Gegenzug scheitert die Multiplikation und Division mit negativen Zahlen und man bekommte eine Zahl für die es kein Inverses gibt.
Altlasten oder Designziel?
Die Auswahl des Einerkomplements für die Prüfsummen der IP-Protokolle gründet sich auf zwei Eigenschaften:
- Es bildet eine abelsche Gruppe: Man kann beliebig umsortieren, vertauschen, umgruppieren und es gibt eine Umkehroperation. Man kann subtrahieren.Veränderungen an dem IP-Paket sind so ohne komplexe Neuberechnung in Änderungen an der Prüfsumme umrechenbar. Die Prüfsumme wird zum Abschluß negiert und ist Bestandteil der Berechnung, so daß der Empfänger bei korrekten Paketen eine -0 erhalten muß.
- Invarianz gegen Endianess: Durch das umlaufende Carry ist es egal, ob die Zahlen auf Big oder Little Endian Systemen verarbeitet werden. Solange der Überlauf die Bits in der gleichen Reihenfolge durchläuft, ist das Ergebnis immer das Gleiche.
Beide Eigenschaften zusammen gestatten den Einsatz größerer Berechnungseinheiten, ja sogar massiv parallele Berechnungen durch Vektoroperationen. Es ist so möglich extrem schnell und einfach die Berechnungen vorzunehmen.
Desweiteren kann die Prüfsummenberechnung auf praktisch allen damals existierenden Plattformen ohne Konvertierungsaufwand durchgeführt werden. Was erstmal nicht geht, sind middle-endian Systeme wie die PDP11. Die Begrenzung der Prüfsumme auf 16bit gestattet auch der PDP11 mit einer konsitenten Endianess und damit ohne Konvertierungsaufwand zu arbeiten.
Besonders relevant ist diese Invarianz, da Netzwerke big-endian (lesen!) sind, während viele Prozessoren little-endian (lesen!) einsetzen.
Die Existenz einer +0 und einer -0 gestattet es, zu signalisieren, ob eine Prüfsumme berechnet wurde oder nicht. So kann man die Prüfsummenberechnung aktiv auslassen um UDP-Pakete auch mit leichten Fehlern durchzulassen. Dies ist beispielsweise bei VoIP nützlich, wenn Bitfehler weniger Schaden anrichten als komplett verlorene Pakete. +0 signalisiert hier die Abwesenheit von Prüfungen.
Interessant ist die Tatsache, daß man zum Zeitpunkt der UDP-Norm noch beide Nullen als mögliche Ergebnisse der Rechnung in Erwägung zog und explizit behandelt. Bei TCP und IP gibt es keine Sonderbedeutung von ±0. Man hielt es nicht für notwendig, auf solche Besonderheiten im Standard einzugehen.
Erst mit der Zeit hat man erst erkannt, daß verschiedene Tricks der inkrementellen Berechnung das Nullproblem gar nicht erkannt hatten. Der Standardcode kann gar keine +0 generiern. Warum das so ist, erkläre ich weiter unten. Wie sehr die beiden Nullen in Vergessenheit geraten sind, offenbart Code, der die legitim auftretende -0 als Fehlerkennung verwendet.
Andererseits kann man die Berechnung der Prüfsumme der Netzkartenhardware überlassen. Beim "Checksum Offloading" muß entschieden werden, ob die Hardware die Prüfsumme berechnen soll oder nicht. Auch hier signalisiert nur die +0 im Checksum-Feld den Wunsch nach Berechnung. Eine zwangsweise Neuberechnung der Prüfsumme würde die Fehlererkennung (insbesondere beim Routing) ad absurdum führen.
Betrachtet man die Alternativen, klären sich weitere Vorbehalte:
- CRC Prüfsummen sind zwar sehr gute Fehlerdetektoren, sind aber keine Gruppen. Dadurch erfordern aber selbst kleine Änderungen vollständige Neuberechnungen. Das TTL Feld könnte dann nicht Bestandteil der Prüfsumme sein. Auch NAT hätte es vermutlich nicht (so schnell) gegeben.
- Das Zweierkomplement ist heute die dominierende Implementierung der Binärarithmetik. Sie ist aber nicht endianess invariant. Zur Prüfsummenberechnung wäre also stets eine Konvertierung der Daten notwendig.
- Einfaches XOR erfüllt ebenfalls alle Anforderungen, ist aber deutlich schwächer bei der Fehlerdetektion. Da es damals rechenmäßig kaum einen Unterschied zwischen Einerkomplement und XOR gab, wurde das stärkere Verfahren bevorzugt.
Das magische "End Around Carry"
Zunächst sind noch einige Überlegungen notwendig, um sich elementare Eigenschaften des Einerkomplements zu vergegenwärtigen. Die Additionsstufe des Einerkomplements entspricht der des Zweierkomplements mit dem Unterschied, daß das Carry rückgekoppelt ist. Beim Zweierkomplement wird das Carry aus einem extra CPU-Flag eingeschoben und nach der Addition wieder dort verstaut. Dieses CPU-Flag gibt es bei Einerkomplement-CPUs schlicht nicht.
Das umlaufende Carry kann jedoch nicht zu einer Endlosschleife führen. Jeder Volladdierer muß (das Carry sei c) nur die Kombinationen 0+0+c = 0c, 1+1+c=1c sowie den 1+0+c=c(~c) bzw. 0+1+c=c(~c) bearbeiten. In den ersten beiden Fälle wird das ausgehende Carry Bit zwangsweise auf einen festen Wert gesetzt. Die Mischfälle sind interessanter, aber hier wird das Carry unverändert durchgereicht. Es gibt keinen Fall, wo die Rückkopplung des Carry zu einem Widerspruch, also einem flappenden Bit führen kann. Die Einerkomplementaddition ist also trotz umlaufenden Carry ist also binnen einer Runde stabil.
Von besonderem Interesse ist eine Eingabe, bei der nur die Mischfälle 1+0 oder 0+1 auftreten. In diesen Fällen gibt es keinen Volladdierer, der den Wert des Carry festlegen könnte. Ist das umlaufende Carry eins, so lautet das Ergebnis der Addition +0. Ist das umlaufende Carry null, so lautet das Ergebnis stattdessen -0. Beides sind valide Ergebnisse, die von Architektur, Algorithmus und Kontext der Berechnung abhängen. Dieses umlaufende Carry und die Existenz der zwei Nullwerte sind also unmittelbar verwand. Ja, sie sind der gleiche Effekt. Die ±0 ist die explizite Darstellung des umlaufenden Carry.
Andererseits ist es bei der Implementierung der Addition auf Zweierkomplement-Architekturen nicht möglich, Bits zu verlieren. Eventuelle Überläufe werden später hinzuaddiert und nicht rückgekoppelt. Einmal gesetzte Bits (z.B. die IP Version) leaken bis zum Ergebnis durch. Die Algorithmen zur Prüfsummenberechnung auf Zweierkomplementsysteme haben so durch die normative Kraft der Faktischen die Generierung der +0 verhindert.
Summiert man die Carries durch 32bit Arithmetik in den höherwertigen Bits auf, so kann man die Einerkomplement Rechnungen auch im Zweierkomplement ausführen. Alle Carry-Bits, die man vergessen hatte, liegen in den höherwertigen 16bit. Wieviele solche Additionen kann man ausführen, ohne daß einem der Carry-Speicher selbst überläuft? Im schlimmsten Fall hat jede Addition ein unverarbeitetes Carry. Man kann also 216-1 Additionen ausführen. Dies entspricht einem Speicherbereich von 217-2 Byte. also 130 kByte. Für IP-Pakete ist das unbedenklich, da diese maximal halb so groß werden dürfen. Problematisch bei IPv6 sind paketübereifende Payloads, deren Prüfsummen länger werden dürfen, als ein Paket an Daten faßt. Man kann also mit 32bit Arithmetik bedenkenlos paketweise rechen.
Eigener Code
Jetzt sind die Voraussetzungen geschaffen, eignen Einerkomplement-Code zu schreiben. Das steht dann aber in einem extra Artikel.