TinoLib

GrowPack

GrowPack ist ein spezielles Dateiformat, welches wie CVS arbeiten soll.

Wenn ich GrowPack in TinoLib integriere bedeutet das, dass ein zentraler Teil von GAT in TinoLib entsteht.

Hintergrund

Ich habe immer folgende Probleme:

  • Ein Datei-Paket liegt irgendwo rum.
  • Ich weiß nicht, ob es die aktuellste Version ist.
  • Es kann mehrere aktuelle Versionen geben (weil ich ein Schlamper bin und mal hier und mal da editiert habe).
  • Ich will niemals bei einem automatischen Merge etwas verlieren.
  • Ich mag es nicht, wenn sich am Dateianfang etwas verändert. Wachsen dürfen Dateien.
  • Nach Jahren ist unklar: Ist ein Bit geklappt oder ist die Datei noch unbeschädigt.
  • Ich möchte wenn möglich alles auf allen Seiten automatisch aktualisiert halten. Sprich ich editiere irgendwo im Netz die Datei und sie wandert von selber überall auf alle Systeme.
GrowPack soll genau diesen Spagat als Library-Format leisten:

  • Es definiert ein Format, um eine Datei zu archivieren.
  • Es steht aber evtl. mit anderen GrowPacks in Verbindung.
  • GrowPacks enthalten die gesamte Historie einer Datei.
  • GrowPacks können wachsen, wobei sie die Änderung in der Datei aufnehmen und ein neues Delta bilden.
  • Beim normalen Wachsen verändern sie ihren alten bisherigen Inhalt nicht.
  • GrowPacks können aber neu gepackt werden (für Effizienz), dabei bleibt der Inhalt aber gleich.
  • Das Wachsen ist unabhängig von der Art des gepackten Inhalts. Sprich, habe ich 2 GrowPacks die verschieden gepackt sind aber denselben Inhalt besitzen, dann können sie unterschiedlich groß sein. Ich kann ein Delta trotzdem an den GrowPack anhängen, ohne dass ich vorher auf den vorherigen Inhalt achten muss.
  • Das Format ist kryptographisch sicher.

Wie funktioniert's?

Es funktioniert ähnlich wie GIT mit seinen Zwischendeien, wobei ein GrowPack aber eine Zwischendatei und Datenspeicher in einem ist:

  • Deltas: Die Gruneinheit eines GrowPack ist das Delta. Ein Delta ist eine untrennbare Einheit, die mit einer eindeutigen kryptographischen ID versehen ist. Ein minimaler GrowPack besteht aus einem einzigen Delta.
  • Blöcke: Deltas bestehen aus mehreren Blöcken. Die Blöcke sind unabhängig, aber geordnet (durchnumeriert). Ein Delta enthält mindestens 2 Blöcke. Blöcke können "fremde" Informationen enthalten (siehe Reursion weiter unten). Diese "fremden" Informationen werden so bearbeitet, als wären sie dem aktuellen Delta vorne angestellt worden.
  • Trailer: Ein GrowPack wird immer von hinten nach vorne durchgescannt. Am Ende eines Deltas steht immer ein spezieller Block, Trailer genannt, der das aktuelle Delta und seinen Ursprung beschreibt. Der letzte Trailer im GrowPack soll nicht komprimiert sein (da er sehr kurz ist).
  • Ungeordnet: Die Reihenfolge der einzelen GrowPack-Teile ist ungeordnet. Es ist vollkommen einerlei, in welcher Reihenfolge sich Deltas im GrowPack befinden. Im Streaming-Bereich beginnt das Streamen mit dem letzten (aktuellen) Delta und es folgen die weiteren Deltas, bei Dateien befindet sich der letzte (aktuelle) Delta in der Regel am Ende des GrowPacks. Anderenfalls muss man den richtigen Delta per Hash referenzieren.
  • Komprimiert: Ein GrowPack ist komprimiert. Dabei ist es unerheblich, ob die Kompression "solid" ist, sprich von Anfang bis Ende durchgeht, oder aus mehreren Teilstücken besteht. Das Fehlen einer Kompression ist natürlich möglich.
  • Konkatenierbar: Man kann also zwei GrowPacks einfach konkatenieren. Es können verschiedene Kompressions-Formate verwendet werden. Es funktionieren auch Archive wie RAR etc., die "GrowPacks" enthalten (nicht-GrowPack konforme Bestandteile werden ignoriert).
  • Rekursiv: GrowPacks sind inhärent rekursiv. So kann ein komprimiertes Archiv wiederum komprimierte GrowPacks enthalten, ein Delta kann aber ebenso andere Deltas referenzieren oder ein Verzeichnis darstellen, das mehrere Deltas enthält, und Blöcke können jederzeit andere Blöcke, Deltas, GrowPacks oder Archive enthalten.
  • Kryptographisch: Ein Delta wird immer über seinen kryptographischen Hash seines Inhalts referenziert. Ebenso tragen alle Blöcke diesen Hash. Da die Blöcke auch numeriert sind, kann man ein Delta auch aus Bruchstücken zusammensetzen (vorausgesetzt man findet die Blöcke irgendwie).
  • Vollständig: Ein GrowPack ist vollständig, wenn er alle Deltas enthält, die notwendig sind, um das letzte Delta vollständig auszugeben. Hinweis: Das letzte Delta kann ein Verzeichnis sein, das mehrere Dateien enthält!
  • Korrekt: Ein GrowPack ist korrekt, wenn er den Ursprung eines Deltas enthält. Ein Korrektes Delta kann nur ausgegeben werden, wenn der Pfad der Deltas bis zum Ursprung nicht unterbrochen ist, d. h. alle Deltas bis zum Ursprung augegeben werden können.
  • Minimal: Ein GrowPack ist minimal, wenn er ausschließlich Deltas enthält, die notwendig sind, um das letzte Delta vollständig auszugeben.

Im Detail

Zahlen werden immer skaliert "LSB first" abgelegt. Jedes Byte enthält 7 Bit der Zahl, das High-Bit ist gesetzt wenn es sich um das LSB handelt.

Das ist rein pragmatisch, da von hinten nach vorne gearbeitet wird. Damit wird das MSB zuerst ausgelesen. Ist das oberste Bit gelöscht, wird der Wert um 7 Bit nach links verschoben, das nächste Byte legt dann die unteren 7 Bit fest. Ist vom nächsten Byte ebenfalls das oberste Bit gesetzt wird so lange derart weigergemacht, bis ein Byte mit gesetztem obersten Bit erscheint. Dann ist die Zahl vollständig eingelesen.

Bis auf den Fall mit der Fletcher-Summe wird dabei mit 32 Bit unsigned gearbeitet. Bei Fletcher sind es 64 Bit (das macht 9 Byte). Ich bin auf Fletcher verfallen, denn CRCs kommen zu häufig vor, und durch Streckung der Summe auf 9 Byte entsteht hoffendlich ein Verfahren, das sonst nicht Verwendung findet.

Block

Ein Block besitzt folgenden Aufbau:

  1. 4 Magic
  2. Daten
  3. n Hash des Deltas
  4. 1 Typ des Hash des Deltas
  5. 1+ Länge des Blocks
  6. 1+ Nummer des Blocks
  7. 1 Typ des Blocks
  8. 9 Fletcher 32 Checksum des Blocks
Der Block wird von hinten gelesen, also Zahl, Byte, Zahl, Zahl, Hash, wobei das erste (oberste) Byte den Typ des Hashs kodiert, so dass man weiss, wie lange dieser ist. Da man mit fehlendem Hash-Algorithmus die Kryptologische Struktur des Desltas nicht prüfen kann ist die Länge des Hashs nicht im Typ abgelegt.

Das Magic ist dafür da, dass man die Blöcke leichter per Utilities wie "File" erkennen kann. Das Magic ist "GPac" für den ersten Block, "gPAc" für alle mittleren, und "gpAC" für Trailer.

Trailer

Der Trailer ist der letzte Block. Es ist mit allem zusammen maximal 32 KB groß. Somit ergibt sich aus ihm der kryptographischen Hash des Deltas sowie die Anzahl aller Blöcke. Außerdem findet sich der Offset zum vorherigen Block über die Gesamtlänge des Blocks.

Das Datenfeld vom Trailer wird wieder von hinten nach vorne durchgearbeitet. Das gelesene Byte beschreibt immer den Typ des nächsten Datenfelds. Das eigentliche Datenfeld ist somit immer vor dem Byte das den Typ beschreibt.

Typen die notwendig sind:

  • Datenende (hat das Byte 00)
  • Kommentar (Text)
  • Wertepaar Name, Text
  • Wertepaar Name, Zahl (unsigned)
  • Wertepaar Name, idealisierter Timestamp (signed, Millisekunden seit Jahr 0)
  • Wertepaar Name, Vorzeichenzahl (64 Bit)
  • Hash (Ursprung)
  • Hash (notwendig für Korrektheit)
  • Hash (nicht notwendig für Korrektheit)
Der "Ursprungs-Hash" ist nur wichtig für Suchaktionen a la "suche Nachfolger mit Ursprung X". Ansonsten ist das gleichwertig zum Hash "notwendig für Korrektheit".

Am Ende der Parsens stößt man immer (sozusagen nahe am Anfang) auf das Datenende. Davor befindet sich eine 16-Bit-Zahl die die Länge des Trailers hinter der 16-Bit-Zahl angibt. Sind die oberen 8 Bit 0 kann man diese als das Datenende-Zeichen verwenden (Trailer dürften oft unter 256 Byte haben)!

Findet man also ein "gpAC"-Magic kann man mit den nächsten 2 Byte das Ende vom Trailer finden und so per Fletcher prüfen, ob es sich um einen validen Trailer handelt. Das dient dazu, bei Datenfehlern einen Synchronisationspunkt zu bekommen.

Delta

Ein Delta besteht einfach aus all seinen Blöcken bis hin zum Trailer. Der Inhalt des unkomprimierten Deltas muss mit seinem dem kryptographsichen Hash übereinstimmen.

Kompression

Es gibt den nicht seltenen Fall, dass der gesamte Block komprimiert ist. In diesem Fall ist auch das Magic komprimiert sowie das Blockende, das alle notwendigen Informationen enthält. Wie man in diesem Fall auf die richtige Dekompression schließen kann ist nicht definiert. Meistens wird es per File-Extension oder File-Magic gehen, so wie das immer der Fall ist. Die Kompression kann also implizit sein und wird (meistens) am fehlenden Magic erkannt.

Anderenfalls wird die Kompression in entsprechende "Kompression Blocks" gepackt, die definieren, welche Form der Dekompression zu verwenden ist. Das letzte Byte der Daten definiert dabei, wie die Kompression aussieht:

  • 00=Stream-Kompression, die Kompressionsart steht am Anfang der Daten
  • Steht am Anfang ebenfalls 00, ist der Block unkomprimiert (Dummy Kompression Block bzw. der Rest ist unkomprimiert)
  • 01=ZLIB
  • 02=BZIP2
  • 03 usw. steht dann für die noch zu definierenden Kompressionen
Im Fall der Stream-Kompression können mehrere verschiedenen Kompressionen zum Einsatz kommen. Es muss dabei aber beachtet werden, dass die Dekompression keine Bytes schluckt, denn die einzelnen komprimierten Blöcke fangen jeweils immer mit der Kompressionart an.

Blöcke können nicht in mehrere Kompressions-Blöcke eingeschlossen werden. Sind alle Daten eines Kompressions-Blocks verarbeitet sind auch alle darinnen eingeschlossenen anderen Blöcke beendet. Dies sorgt dafür, dass unsinnige 0-Bytes am Ende von TAR keine Probleme bereiten können. Die Datenblöcke sollten prinzipiell frei von derartigen an sich nicht benötigten Bytes gespeichert werden, denn einerseits erzeugt das unnötige Warnungen, andererseits verschwendet es Speicherplatz.

Hinweise

  • Dies ist nur ein Denkmodell. GrowPack gibt es bisher nicht.
  • GrowPack enthält keine digitalen Signaturen. Diese kann man aber ggf. in Trailer aufnehmen.
  • Einige Definitionen fehlen noch, z. B. wie sehen referenzierte Deltas, Verzeichnisse usw. aus.
  • Es ist möglich, einen GrowPack jederzeit neu und effizienter zu packen. Es ist möglich, vor der eigentlichen Kompression durch Referenzieren anderer Deltas (das sind Hash, Offset und Länge) massiv Platz zu sparen. Es ist weiterhin möglich, Deltas zu referenzieren, die an sich nichts mit dem GrowPack zu tun haben (also Fremd-Deltas kann man aufnehmen).
  • DRM etc. ist in GrowPack nicht enthalten. DRM-Methoden, dazu gehören auch Passwortschutz, sind für GrowPack prinzipiell abzulehnen. Es ist zulässig, verschlüsselte Archive in GrowPacks zu packen, wenn das Passwort automatisiert (im Trailer) definiert werden. Dies geht, indem man die Daten aus dem verschlüsselten Archiv per Delta referenziert.
  • Da GrowPack für Streaming designet wurde ist es zulässig, on the fly Transformationen auf GrowPacks anzuwenden. Dazu gehört, GrowPacks vollständig zu dekomprimieren, Deltas umzusortieren oder Blöcke einzufügen oder zu löschen (wenn sie für den Anwendungsfall nicht notwendig sind). Diese Transformationen dürfen nicht untersagt werden.
-Tino, 2006-01-23