Serialize Algorithmen leicht verständlich, Binary safe Read and Write

Bytesemantics zum Lesen und Schreiben von Daten in Dateien bzw. Handle, binary safe read and write

Der vorliegende Artikel beschreibt, wie Serialize-Algorithmen in Perl entwickelt werden können. Derartige Algorithmen sind jedoch keineswegs auf die Programmiersprache Perl beschränkt, sie gewinnen an Bedeutung für einen Bytesicheren (8Bit) Transport zum Austausch von Daten innerhalb einer Anwendung und zum Austausch von Daten von einer Anwendung zur Anderen, beispielsweise von JavaScript nach Perl, Perl nach PHP usw. und umgekehrt.

Der Dateibegriff nach Niklaus Wirth beschreibt eine Byte-Sequenz. Eine Datei wird sequentiell geschrieben und auch gelesen. In jeder Programmiersprache, außer JavaScript, heißt das Schreiben einer Datei: Es werden Bytes in einem Handle abgelegt. Dabei ist es unerheblich, ob das Handle auf eine im Dateisystem physikalisch vorliegende Datei zeigt oder auf einen Bereich im Hauptspeicher.

Zum Entwickeln IO::String

    use IO::String;
    my $FH = IO::String->new;

Das erstellt ein Handle im Hauptspeicher. $FH wird genauso verwendet wie jedes andere FileHandle oder STDIN, STDOUT. Sollen STDIN, STDOUT in Subfunktionen übergeben werden, verwende einen Typeglob, z.B. $eav = handle2eav(*STDIN); Für im Dateisystem physikalisch vorliegende Dateien, verwende IO::File. Das importiert Konstanten, welche den Modus beim Öffnen einer Datei bestimmen, z.B.:

    use IO::File;
    my $FH = IO::File->new;
    $FH->open('/path/file', O_CREAT|O_RDWR|O_BINARY) or die $!;

Beachte: Mit O_BINARY wird bereits beim Öffnen der Datei der Binärmodus eingeschaltet. Das ist insofern wichtig, als dass beim Lesen und Schreiben in das Handle seitens Betriebssystem keine eigenmächtigen Änderungen an der Datei vorgenomen werden, beispielsweise eine Sonderbehandlung von Zeilenumbrüchen. Merke, dass es in Binärdateien gar keine Zeilenumbrüche gibt, sondern einfach nur Bytes.

Die kleinste Speichereinheit ist das Byte

Ein Byte verkörpert eine Wertigkeit von 0..255. Eine Folge von mehreren Bytes können wir als ein Array bzw. eine Liste von Zahlen betrachten. Somit sähe ein einfacher Algorithmus zum Schreiben einer Liste von Zahlen so aus:

    use strict;
    use warnings;
    use IO::String;
    use bytes;

    my $FH = IO::String->new; # Erstelle ein Handle im Hauptspeicher
    foreach my $nr(1,2,3,4,55,255){
        $FH->print( pack "C", $nr  );
    }

    # Handle wieder auslesen
    $FH->seek(0,0); # zurück zum Anfang
    while( read($FH, my $buffer, 1) ){
        print unpack("C", $buffer), "\n";
    }
    # Die Zahlen 1 2 3 4 55 255 werden untereinander ausgegeben

Gut zu sehen: Egal wieviel Platz an Bytes, also wieviele Stellen eine Zahl von (0..255) selbst belegt, in der Datei belegt diese Zahl immer genau ein Byte. Dieser Fakt ist wichtig, denn ein Serialize-Algorithmus muss sicherstellen, dass die Daten auch wieder hergestellt werden können. So wird in obenstehendem Beispiel das Handle in Schritten von genau einem Byte gelesen, womit sich das gewünschte Ergebnis zeigt.

Big Endian, Little Endian für numerische Werte

Zum Kodieren größerer Zahlen als 255 werden mehrere Bytes benötigt. Vier Bytes aneinandergereiht ermöglichen so die Kodierung einer Zahl 0xFFFFffff, was den größten Wert für einen vorzeichenlosen Integer mit 32 Bit darstellt. Beim Aneinanderreihen mehrerer Bytes ist die sogenannte Byte-Order zu beachten, je nachdem, ob diese Order absteigend oder ansteigend erfolgt, liegt entweder ein Big-Endian oder ein Little-Endian vor. In Perl gibt es für den Big-Endian die pack-Schablone "N", diese Byte-Order wird auch als Network-Order bezeichnet. Obenstehendes Beispiel nun geändert für die Verwendung der pack-Schablone "N":

    use strict;
    use warnings;
    use IO::String;
    use bytes;

    my $FH = IO::String->new; # Erstelle ein Handle im Hauptspeicher
    foreach my $nr(1,2,3,4,55,255,3299123){
        $FH->print( pack "N", $nr  );
    }

    # Handle wieder auslesen
    $FH->seek(0,0); # zurück zum Anfang
    while( read($FH, my $buffer, 4) ){
        print unpack("N", $buffer), "\n";
    }
    # Die Zahlen 1 2 3 4 55 255 3299123 werden untereinander ausgegeben

Nunmehr wird zum Lesen einer jeden einzelnen Zahl das Handle in Schritten von vier Bytes durchgegangen und das Speichern sehr großer Zahlen wird möglich.

Die Funktionen pack() und unpack()

Die beiden Built-In-Funktionen benötigen eine Schablone, welche zum Einen die Anzahl der Bytes bestimmt und zum Anderen die Größe der Byte-Wertigkeit, den numerischen Wert. Beispiele in Kürze mit einer bildlichen Veranschaulichung der Bytes:

    □  = pack "C", 255;          # ein Byte für Integer von 0..255, ergibt ein Byte
    □□□□ = pack "N", 0xFFFFffff; # BigEndian für Integer von 0..0xFFFFffff, ergibt vier Bytes
    □□□□ = pack "V", 0xFFFFffff; # LittleEndian für Integer von 0..0xFFFFffff, ergibt vier Bytes

    # Mehrere Zahlen kombiniert
    □□□□ = pack ("CCCC", 1,2,3,4);
    □□□□ = pack ("C4", 1,2,3,4);   # dasselbe wie eine Zeile weiter oben
    # und wieder auspacken
    @numbers = unpack "CCCC", □□□□); # ergibt 1,2,3,4

    # ein vorzeichenloser Integer mit 32 Bit, 0xFFFFffff, 4294967295
    □□□□ = pack "N", 0xFFFFffff;
    □□□□ = pack "N", 4294967295;
    4294967295 <= unpack "N", □□□□           # scalarer Kontext: eine Zahl
    (255,255,255,255) <= unpack "CCCC", □□□□ # vier Zahlen im Listenkontext

Merke: Die Schablone bestimmt die Anzahl der Bytes UND die Anzahl der vorzeichenlosen Integer-Werte. Beim Serialisieren bietet sich die Schablone "N" an zum Verpacken einer Längenangabe (unsigned integer mit 32 Bit) in eine Sequenz von vier Bytes (□□□□) als BigEndian.

Literale und Strings

Mit use bytes; wird in Perl ein Pragma gesetzt, womit alle in Scalaren vorliegenden Strings nicht als Zeichenfolgen, sondern als Folge von Bytes betrachtet werden. Eine UTF-8-kodierte Zeichenfolge 'äöü' verkörpert nach dem Einschalten des o.g. Pragma eine Bytesequenz mit der Länge von 6 Bytes, obwohl es 3 Zeichen sind.

Beachte: Das Einschalten der Bytesemantics mit use bytes; ist wichtig zum Ermittlen der Längenangaben als Anzahl der Bytes und nicht als Anzahl der Zeichen.

Ein einfacher Algorithmus zum Schreiben einer Liste von Literalen

Nach dem Einschalten der Bytesemantics können wir nun eine Liste von beliebigen Literalen in ein Handle schreiben und daraus unzerknittert wieder hervorzaubern.

    use strict;
    use warnings;
    use IO::String;
    use bytes;

    my $FH = IO::String->new; # Erstelle ein Handle im Hauptspeicher
    foreach my $str( qw(foo bar baz dogs) ){
        $FH->print( pack("N", length $str).$str  );
    }

    # Daten wiederherstellen
    $FH->seek(0,0);
    while( read($FH, my $buffer,4) ){
        my $len = unpack "N", $buffer;
        read($FH, $buffer, $len);
        print "$buffer\n";
    }

    # ausgegeben werden untereinander foo bar baz dogs

Der Algorithmus ist leicht verständlich: Im Schleifenkörper lesen wir anfangs immer genau 4 Bytes zum Ermitteln der Längenangabe für den nachfolgenden Wert, d.h. als Nächstes wird mit dieser Längenangabe der Wert selbst aus dem Handle gelesen.

Der Algorithmus arbeitet binary safe, ein Wert selbst kann eine beliebige Bytefolge mit Oktettenwertigkeiten von 0..255 enthalten.

Logische Speichereinheiten

Mit dem bisher gezeigten Algorithmus haben wir als kleinste Logische Speichereinheit auf dem Low-Level (Byte-Ebene) ein Paar, bestehend aus einer Längenangabe und einem gespeicherten Wert. Wobei: Die Längenangabe selbst hat stets eine Länge von genau 4 Bytes als Big-Endian. Damit ist sichergestellt, dass die gewünschte Datenstuktur, in diesem Fall ein Array, aus der Sequenz wiederhergestellt werden kann. Wenn wir mit einem Textbetrachter in die Datei schauen, sehen wir in etwa so etwas:

    □□□□foo□□□□bar□□□□baz□□□□dogs

Wobei z.B. □□□□foo eine logische Speichereinheit darstellt, für genau einen Wert.

Transformationen, Polymorphie

Ein Array mit einer geradzahligen Anzahl von Array-Elementen kann auf Programmcode-Ebene auch als assoziatives Array aufgefasst werden, was in Perl einen einfachen Hash verkörpert. Somit können wir auch einen Hash mit dem oben gezeigten Algorithmus in einer Datei speichern. Dieser Hash entspricht dem Aufbau-Muster Attribute => Value (im Beispiel: foo => 'bar', bar => 'dogs').

Am Serialize-Algorithmus ändert sich nichts, allein der Programmcode bestimmt die aus der Sequenz zu gewinnende Datenstruktur, ein Array lässt sich in einen Hash transformieren und umgekehrt, vorausgesetzt, die Anzahl der Array-Elemente ist restlos teilbar durch zwei. Aufgrund dieser Vielgestaltigkeit, lassen sich als weitere Möglichkeit jeweils immer drei Werte zusammenfassen und ergeben eine Datenstruktur nach dem Muster Entity, Attribute, Value, in Perl bekannt als Hash-of-Hashes (HoH). Das heißt, dass es mit dem oben dargestellten Algorithmus und der damit verbundenen kleinsten Low-Level-Speichereinheit auch möglich ist, Perl HoH's in Dateien speichern zu können.

Zweidimensionale Arrays

Visuell ist eine Tabelle ein zweidimensionales Array, bestehend aus Zeilen und Spalten. Jeder Schnittpunkt einer Zeile mit einer Spalte definiert eine Zelle, in welcher sich der Wert befindet. Aber auch zum Serialisieren einer solchen Matrix lässt sich der bisher beschriebene Algorithmus anwenden, nämlich dadurch, dass die Matrix in einen %HoH transformiert wird:

Liegt die Matrix als Array-of-Arrays vor, haben wir sowohl den spaltenindex als auch den zeilenindex.

    $hoh{$spaltenindex}{$zeilenindex} = $value;

    # Komplettbeispiel, 2 Zeilen, 3 Spalten
    my $AoA = [
        [1,2,3],
        [4,5,6]
    ];

    my $HoH = {};

    foreach my $zeilenindex( 0 .. scalar @$AoA - 1){
        foreach my $spaltenindex( 0 .. scalar @{$AoA->[$zeilenindex]} - 1 ){
            $HoH->{$zeilenindex}{$spaltenindex} = $AoA->[$zeilenindex][$spaltenindex];
        }
    }

Der Hash-of-Hashes beinhaltet genau dieselben Informationen wie das Array-of-Array nunmehr mit dem Vorteil, dass die Werte über $zeilenindex und $spaltenindex direkt adressierbar sind..

Merke: Der wahlfreie Zugriff (Random Access, direkte Adressierbarkeit) wird nicht etwa in der Sequenz (auf Dateiebene) abgebildet sondern auf der in der Sequenz enthaltenen Datenstruktur. Der Aufbau einer Datei auf Byte-Ebene ist von der Datenstruktur unabhängig. Ein wahlfreier Zugriff erfolgt über die im Code vorliegende Datenstruktur, das ist ein Array oder ein Hash oder ein Scalar.

Undefinierte Werte

Beim Entwicklen von Serialize-Algorithmen ist zu beachten, wie mit undefinierten Werten umzugehen ist, z.B. mit sowas:

    my %h = ( foo => 'bar', baz => undef);

Ein undef lässt sich nämlich nicht so ohne Weiteres in einer Datei abbilden und obenstehender Algorithmus erzeugt eine Fehlermeldung:

    my $FH = IO::String->new; # Erstelle ein Handle im Hauptspeicher
    foreach my $nr(1,2,3,4,55,255,3299123, undef){
        $FH->print( pack "N", $nr  );
    }
    # Use of uninitialized value $nr in pack

Es wäre unklug, die Warnmeldungen für solche Fälle einfach abzuschalten, vielmehr sollte sich der Programmierer Gedanken darüber machen, wie mit undefinierten Werten in seinem Programm umzugehen ist. In Kürze zwei Möglichkeiten:

undef oder Leerstring wird mit einem zusätzlichen Byte gekennzeichnet
Das Byte wird mit der pack-Schablone "C" an die Längenangabe angehängt und hat z.B. den Wert 1 oder 0 (Leerstring oder undef)
undef wird einfach zu einem Leerstring gemacht
Eine Vereinbarung, die in vielen Fällen ausreicht

In beiden Fällen liegt beim Serialisieren ein definierter Wert vor, und die zweite Variante hat sogar den Vorzug, dass bei der Weiterverarbeitung der deserialisierten Daten nicht erneut auf undef geprüft werden muss, was freilich auch von der Endanwendung abhängt. In Fakt ist zu überlegen, ob undef über den Transport-Layer (Datei, Sequenz) zu transportieren ist oder nicht oder in welcher Form.

Performance-Optimierung

Es lassen sich weitere Algorithmen finden, womit sich die IO-Performance verbessern lässt. Nun, was heißt das? Bei einer gegebenen Sequenz:

    □□□□foo□□□□bar□□□□baz□□□□dogs

müsste die Perl-Funktion unpack("N", $buffer); viermal aufgerufen werden zum Ermitteln der jeweiligen Längenangaben, so hätten wir vier Schleifendurchläufe. Aufgrund der Tatsache, dass die Perl-Funktion unpack() ein Array liefert, können wir die Längenangaben auch zusammenfasssen, betrachte die Sequenz:

    □□□□□□□□□□□□□□□□foobarbazdogs

Der Aufruf der Perl-Funktion unpack() sieht dann so aus, nachdem 4*4 Bytes auf den Buffer gelesen wurden:

    read($FH, $buffer, 12);  # 4x4 Bytes
    my($len_foo, $len_bar, $len_baz, $len_dogs) = unpack "NNNN", $buffer;

Erforderlich ist jedoch nun, dass die Anzahl der Array-Elemente am Anfang der Sequenz zu finden ist, kein Problem, dafür genügt ein Big-Endian:

    □□□□

    read($FH, $buffer, 4);
    my $el_count = unpack "N", $buffer;

Aus der Anzahl der Array-Elemente ergibt sich die Anzahl der zu lesenden Bytes, die Schablone für den nächsten Aufruf der Funktion unpack() und das Array mit den Offset-Werten für den Rest der Datei:

    read($FH, $buffer, $el_count * 4);
    my @offsets = unpack "N$el_count", $buffer;

Schließlich müssen wir nur noch das Array mit den Offset-Angaben abarbeiten und bekommen alle Array-Elemente aus der Datei:

    @result = ();
    while( my $offset = shift @offsets){
        read($FH, $buffer, $offset);
        push @result, $buffer;
    }

Und hier mal alles zusammen:

    use strict;
    use warnings;
    use IO::String;
    use bytes;

    my $FH = IO::String->new;

    my @array = qw(foo bar boo dogs);

    # serialize
    my $el_count = scalar @array;
    $FH->print( pack "N", $el_count); # Anzahl der Array-Elemente
    my $packs = '';

    foreach my $el(@array){
        $packs .= pack "N", length $el;
    }
    $FH->print($packs);           # byte-kodierte Längenangaben
    $FH->print(join '', @array);  # Alle Elements mit einmal

    # deserialize
    $FH->seek(0,0);
    read($FH, my $buffer, 4);
    $el_count = unpack "N", $buffer;
    read($FH, $buffer, 4 * $el_count);
    my @offs = unpack "N$el_count", $buffer;

    while(my $offset = shift @offs){
        read($FH, $buffer, $offset);
        print "$buffer\n";
    }

    # Ausgabe untereinander: foo bar baz dogs

Mit dem Verständnis der bisher gezeigten Algorithmen ist es nicht weiter schwierig, einen Serializer für Hash-of-Hashes (Entity, Attribute, Value, EAV) zu entwickeln. Gerade das EAV-Model eröffnet viele Perspektiven für den Datenaustausch zwischen Perl und JavaScript (AJAX). Zum Beispiel die Übertragung der Daten einer kompletten Tabelle, welche sich im Browser befindet in einem PUT-Request, Anwendung siehe hier. Abstrakt gesehen werden in dieser Anwendung mehrere Objekte übertragen. Im Prinzip ist das auch nichts Neues, neu ist lediglich, dass anstelle JSON ein eigener Serialize-Algorithmus zum Einsatz kommt, der ohnehin serverseitig zur Verfügung steht, weil die Daten mit demselben Algorithmus in einer Datei persistent gespeichert werden, genauso wie die lokale Replik für JavaScript.

Gegenüber JSON ist ein Low-Level-Serializer jedoch binary safe und jegliche Sonderbehandlungen von Zeichen (etwa das Maskieren von Zeilenumbrüchen) entfallen komplett. Ja, sogar die Zeichenkodierung ist für einen Low-Level-Serializer völlig uninteressant, der interessiert sich nur für Bytes.

JavaScript (JS)

JavaScript kennt kein IO und demzufolge auch keine DateiHandler. Wohl aber gibt es in JS den ArrayBuffer und das Uint8Array. Darüber hinaus lassen sich in einem Uin8Array vorliegende mehrere Array-Elemente zusammenfassen, so dass über das Objekt DataView beispielsweise ein Big- oder Little-Endian erzeugt werden kann, hierzu werden 4 Array-Elemente zusammengefasst.

Somit ist es möglich, den oben gezeigten Algorithmus auf die Verarbeitung von Binärdaten bzw. Byte-Sequenzen auch in JS anzuwenden, woraus sich eine Vielzahl an Möglichkeiten zum Datenaustausch und Datentransport innerhalb einer Webanwendung ergeben (AJAX).

Philosophische Betrachtungen

Dateien sind gewöhnlich Sequenzen, sie werden sequentiell geschrieben und gelesen. Der Random Access hingegen wird über die im Programm verwendeten Datenstrukturen erreicht. (Niklaus Wirth um 1980)

Es ist bemerkenswert: Mit XML oder JSON wird versucht, den wahlfreien Zugriff auf Dateiebene abzubilden. Bemerkenswert insofern, als dass daraus gewisse Standards hervorgegangen sind zum maschinenlesbaren Transport von Daten Programmübergreifend. Letzteres bedeutet, dass Daten ein Programm verlassen und über Dateien, Sockets (HTTP, FTP) oder andere Handler (STDIN, STDOUT) transportiert werden.

Maschinenlesbarkeit von Dateien

Den menschlichen Algorithmus zum Lesen einer Datei auf Maschinen abzubilden ist nicht immer sinnvoll. Eine Maschine, ein Programm liest Dateien nämlich ganz anders als ein Mensch: In Schritten von Bytes oder in Schritten von mehreren Bytes. Für eine Maschine ist es beispielsweise auch unbedeutend, welche Zeichenkodierung in einer Datei vorliegt oder wo Zeilenumbrüche sind, für eine Maschine sind das einfach nur Folgen von Bytes. Wenn beispielsweise mit XML eine Datenstruktur auf Dateiebene (Text-Datei) abgebildet wurde, muss die Maschine einen Parser verwenden, womit die beabsichtigte Struktur so erkannt wird, wie ein Mensch diese erkennt.

Es liegt auf der Hand, dass ein Parser dazu erst die gesamte Datei in den Hauptspeicher lesen muss. Ein Serializer hingegen beginnt seine Arbeit sofort mit dem Lesen des ersten Bytes, er sammelt sozusagen die Daten auf und legt diese sofort (je nach Algorithmus) im Hauptspeicher ab.

Serialisieren von Daten nach MySQL

Serialize ist nicht auf Sequenzen (Dateien) beschränkt. Mit einem entsprechenden Algorithmus lassen sich Daten auch in eine Tabelle einer Datenbank serialisieren, wie dieser Artikel hier zeigt:


Anbieter: nmq​rstx-18­@yahoo.de, die Seite verwendet funktionsbedingt einen Session-Cookie und ist Bestandteil meines nach modernen Aspekten in Perl entwickelten Frameworks.