12.11 Prüfsummen 

Damit Fehler bei Dateien oder bei Übertragungen von Daten auffallen, wird eine Prüfsumme (engl. checksum) gebildet. Prüfsummen werden vor der Übertragung erstellt und mit dem Paket versendet. Der Empfänger berechnet diese Prüfsumme neu und vergleicht sie mit dem übertragenen Wert. Stimmt der berechnete Wert mit dem übertragenen überein, so war die Übertragung höchstwahrscheinlich in Ordnung. Es ist ziemlich unwahrscheinlich, dass eine Änderung von Bits nicht auffällt. Genauso werden korrupte Archive erkannt. Pro Datei wird eine Prüfsumme berechnet. Soll die Datei entpackt werden, so errechnen wir wieder die Summe. Ist diese fehlerhaft, so muss die Datei fehlerhaft sein. (Wir wollen hier ausschließen, dass zufälligerweise die Prüfsumme fehlerhaft ist, was natürlich auch passieren kann.)

12.11.1 Die Schnittstelle Checksum 

Wir finden Zugang zur Prüfsummenberechnung über die Schnittstelle java.util.zip. Checksum, die für ganz allgemeine Prüfsummen steht. Eine Prüfsumme wird entweder für ein Feld oder ein Byte berechnet. Checksum liefert die Schnittstelle zum Initialisieren und Auslesen von Prüfsummen, die von konkreten Prüfsummen-Klassen implementiert werden muss.

interface java.util.zip.Checksum

long getValue() Liefert die aktuelle Prüfsumme.

void reset() Setzt die aktuelle Prüfsumme auf einen Anfangswert.

void update( int b ) Aktualisiert die aktuelle Prüfsumme mit b.

void update( byte b[], int off, int len ) Aktualisiert die aktuelle Prüfsumme mit dem Feld.

Bisher finden sich in den Java-Bibliotheken nur die Klassen CRC32 und Adler32, die von der Schnittstelle Checksum Gebrauch machen. Aber mit wenig Aufwand lässt sich beispielsweise eine Klasse schreiben, die die einfache Paritätsüberprüfung übernimmt. Dies können wir zum Beispiel bei der Übertragung von Daten an der seriellen Schnittstelle verwenden. (Glücklicherweise ist dies im Fall der seriellen Schnittstelle schon in der Hardware implementiert.)

12.11.2 Die Klasse CRC32 

Oft werden Prüfsummen durch Polynome gebildet. Die Prüfsumme, die für Dateien verwendet wird, heißt CRC32, und das bildende Polynom lautet:

Nun lässt sich zu einer 32-Bit-Zahl eine Prüfsumme berechnen, die für genau diese vier Bytes steht. Damit bekommen wir aber noch keinen ganzen Block kodiert. Um das zu erreichen, berechnen wir den Wert eines Zeichens und Xor-verknüpfen den alten CRC-Wert mit dem neuen. Jetzt lassen sich beliebig Blöcke sichern. Ohne groß zu überlegen, dürfte klar sein, dass viel Zeit für die Berechnung aufgewendet werden muss. Bisher ist der mathematische Algorithmus auch nicht in Java, sondern in C implementiert. Er nutzt Tabellen, um möglichst schnell zu sein.

CRC32 crc = new CRC32();
byte ba[] = new byte[(int)in.available()];
in.read( ba );
crc.update( ba );
in.close();

CRC32 implementiert nicht nur alle Methoden, sondern fügt noch zwei Funktionen und natürlich einen Konstruktor hinzu.

class java.util.zip.CRC32
implements Checksum

CRC32() Erzeugt ein neues CRC32-Objekt mit der Start-Prüfsumme 0.

long getValue() Liefert den CRC32-Wert.

void reset() Setzt die interne Prüfsumme auf 0.

void update( byte b[] ) Aktualisiert die Prüfsumme mit dem Feld, durch Aufruf von update(b, 0, b.length).

void update( int b ) Implementiert update() aus Checksum für ein Byte. Nativ implementiert.

void update( byte b[], int off, int len ) Implementiert update() aus Checksum für ein Feld. Nativ implementiert.

CRC eines Datenstroms berechnen

Wir wollen nun ein kleines Testprogramm entwickeln, mit dem wir die CRC32 eines Datenstroms berechnen. Dazu schreiben wir die Methode crc32(), die einen InputStream erwartet. Anschließend werden so lange Bytefolgen ausgelesen, bis available() Null liefert. Für unser Testprogramm, welches einen FileInputStream liefert, wird available() die Dateigröße liefern. Bei großen Dateien ist es sicherlich angebracht, Blöcke einzulesen, die dann mit der crc.update(byte[])-Methode verarbeitet werden.

Listing 12.31 CRC32Demo.java

import java.io.*;
import java.util.zip.*;

class CRC32Demo
{
  static long crc32( InputStream in ) throws IOException
  {
    CRC32 crc = new CRC32();
    int blockLen;
    while ( (blockLen = (int) in.available()) > 0 )
    {
      byte ba[] = new byte[blockLen];
      in.read( ba );
      crc.update( ba );
    }
    return crc.getValue();
  }
  static public void main( String args[] ) throws IOException
  {
    InputStream is = CRC32Demo.class.getResourceAsStream( "CRC32Demo.java");
    System.out.println( crc32(is) );
    is.close();
  }
}

Ein Datenstrom mit gleichzeitiger CRC-Berechnung

Auch das Dienstprogramm Jar - ein Java-Programm unter sun.tools.jar - macht Gebrauch von der CRC32-Klasse. Wir finden hier etwas ganz Interessantes im Quellcode wieder, und zwar einen Ausgabestrom, der nicht Daten schreibt, sondern nur die Prüfsumme berechnet. Für den eigenen Gebrauch ist es sicherlich spannender, einen Datenstrom über einen FilterOutputStream so zu implementieren, dass auch Daten gleich geschrieben werden. Der nachfolgende Auszug zeigt die wesentlichen Schritte. Nun müssen wir nur noch einen Konstruktor schreiben, der sich den OutputStream in out merkt, und dann werden die Daten in diesen Strom geschrieben.

Listing 12.32 CRC32OutputStream.java

import java.io.*;
import java.util.zip.CRC32;

class CRC32OutputStream extends FilterOutputStream
{
  private CRC32 crc = new CRC32();
  public CRC32OutputStream( OutputStream out )
  {
    super( out );
  }
  public void write( int i ) throws IOException
  {
    crc.update( i );
    out.write( i );
  }
  public void write( byte b[] ) throws IOException
  {
    crc.update( b, 0, b.length );
    out.write( b, 0, b.length );
  }
  public void write( byte b[], int off, int len )
    throws IOException
  {
    crc.update( b, off, len );
    out.write( b, off, len );
  }
}

Wir hätten in unserem Programm natürlich wieder auf die Implementierung der beiden write()-Methoden mit Feldern verzichten können, da der FilterOutputStream eine Umleitung macht, doch diese ist ja mit dem bekannten Geschwindigkeitsverlust verbunden. Da wir nicht wollen, dass jedes einzelne Byte geschrieben und mit einer Prüfsumme versehen wird, gönnen wir uns die paar Zeilen mehr.

12.11.3 Die Adler32-Klasse

Diese Klasse ist eine weitere Klasse, mit der sich eine Prüfsumme berechnen lässt. Doch warum zwei Verfahren? Ganz einfach. Die Berechnung von CRC32-Prüfsummen kostet - obwohl in C(++) programmiert - viel Zeit. Die Adler32-Prüfsumme lässt sich wesentlich schneller berechnen und bietet ebenso eine geringe Wahrscheinlichkeit, dass Fehler unentdeckt bleiben. Der Algorithmus heißt nach seinem Programmierer Mark Adler und ist eine Erweiterung des Fletcher¹-Algorithmus, definiert im ITU-T X.224/ISO 8073 Standard, auf 32-Bit-Zahlen. Die Adler32-Prüfsumme setzt sich aus zwei Summen für ein Byte zusammen. s1 ist die Summe aller Bytes und s2 die Summe aller s1. Beide Werte werden Modulo 65521 genommen. Am Anfang ist s1=1 und s2=0. Die Adler32-Prüfsumme speichert den Wert als s2*65536 + s1 in der MSB (Most-Significant-Byte First, Netzwerkreihenfolge).

Eine Beschreibung der Kompression und des Adler32-Algorithmus findet sich im Internet-Draft »ZLIB Compressed Data Format Specification version 3.3«.

class java.util.zip.Adler32
implements Checksum

Adler32() Erzeugt ein neues Adler32-Objekt mit der Start-Prüfsumme 1.

long getValue() Liefert den Adler32-Wert.

void reset() Setzt die interne Prüfsumme auf 1.

Die update()-Methoden werden aus dem Interface implementiert.

¹Fletcher, J. G., »An Arithmetic Checksum for Serial Transmissions«. IEEE Transactions on Communications, Ausgabe. COM-30, Nummer. 1, Januar 1982, Seite 247-252