Ich habe mich lange gefragt, wie Daten komprimiert werden, auch in Zip-Dateien. Einmal habe ich mich entschlossen, meine Neugier zu befriedigen: zu lernen, wie Komprimierung funktioniert, und mein eigenes Zip-Programm zu schreiben. Die Implementierung ist zu einer aufregenden Übung in der Programmierung geworden. Es macht Ihnen große Freude, eine debuggte Maschine zu erstellen, die Daten aufnimmt, ihre Bits in eine effizientere Darstellung überträgt und sie dann wieder sammelt. Ich hoffe, Sie werden auch daran interessiert sein, darüber zu lesen.Der Artikel erklärt ausführlich, wie Zip-Dateien und das Komprimierungsschema funktionieren: LZ77-Komprimierung, Huffman-Algorithmus, Deflate-Algorithmus und mehr. Sie lernen die Geschichte der Entwicklung der Technologie kennen und sehen sich ziemlich effektive Implementierungsbeispiele an, die in C von Grund auf neu geschrieben wurden. Der Quellcode ist hier: hwzip-1.0.zip .Ich bin Ange Albertini , Gynvael Coldwind , Fabian Giesen , Jonas Skeppstedt ( Web ), Primiano Tucci und Nico Weber sehr dankbar , die wertvolles Feedback zu den Entwürfen dieses Artikels gegeben haben.Inhalt
Geschichte
PKZip
In den achtziger und frühen neunziger Jahren, bevor sich das Internet verbreitete, verwendeten Computerbegeisterte DFÜ-Modems, um über das Telefonnetz eine Verbindung zum Bulletin Board Systems (BBS) -Netzwerk herzustellen. BBS war ein interaktives Computersystem, mit dem Benutzer Nachrichten senden, Spiele spielen und Dateien austauschen konnten. Um online zu gehen, war es ausreichend, einen Computer, ein Modem und eine gute BBS-Telefonnummer zu haben. Zahlen wurden in Computerzeitschriften und auf anderen BBS veröffentlicht.Ein wichtiges Werkzeug zur Erleichterung der Verteilung von Dateien war der Archivierer . Sie können eine oder mehrere Dateien in einer einzigen Archivdatei speichernum Informationen bequemer zu speichern oder zu übertragen. Im Idealfall komprimierte das Archiv auch Dateien, um Platz und Zeit für die Übertragung über das Netzwerk zu sparen. In den Tagen von BBS war der Arc-Archivierer beliebt, geschrieben von Tom Henderson von System Enhancement Associates (SEA), einer kleinen Firma, die er mit seinem Schwager gründete.In den späten 1980er Jahren veröffentlichte der Programmierer Phil Katz seine eigene Version von Arc, PKArc. Es war mit SEA Arc kompatibel, funktionierte jedoch dank der in Assemblersprache geschriebenen Unterprogramme und der Verwendung einer neuen Komprimierungsmethode schneller. Das Programm wurde populär, Katz kündigte seinen Job und schuf PKWare, um sich auf die weitere Entwicklung zu konzentrieren. Der Legende nach fand der größte Teil der Arbeit in der Küche seiner Mutter in Glendale, Wisconsin, statt.Foto von Phil Katz aus einem Artikel im Milwaukee Sentinel vom 19. September 1994.Die SEA war jedoch mit Katz 'Initiative nicht zufrieden. Das Unternehmen beschuldigte ihn einer Marken- und Urheberrechtsverletzung. Die Rechtsstreitigkeiten und Kontroversen im BBS-Netzwerk und in der PC-Welt sind als Arc Wars bekannt geworden . Am Ende wurde der Streit zugunsten der SEA beigelegt .Katz gab Arc auf und schuf 1989 ein neues Archivierungsformat, das er Zip nannte und der Öffentlichkeit zugänglich machte :, , , . , ".ZIP", , , , , , , , , .
Katz 'Programm zum Erstellen solcher Dateien hieß PKZip und verbreitete sich bald in der Welt von BBS und PC.Einer der Aspekte, die höchstwahrscheinlich zum Erfolg des Zip-Formats beigetragen haben, ist, dass die Dokumentation mit PKZip, Application Note , geliefert wurde , in dem die Funktionsweise des Formats ausführlich erläutert wurde. Auf diese Weise konnten andere das Format erlernen und Programme erstellen, die Zip-Dateien generieren, extrahieren oder auf andere Weise mit ihnen interagieren.Zip - ein verlustfreies Komprimierungsformat : Nach dem Entpacken sind die Daten dieselben wie vor der Komprimierung. Der Algorithmus sucht nach Redundanz in den Quelldaten und präsentiert Informationen effizienter. Dieser Ansatz unterscheidet sich von der verlustbehafteten Komprimierung., das in Formaten wie JPEG und MP3 verwendet wird: Beim Komprimieren werden einige der Informationen, die für das menschliche Auge oder Ohr weniger auffällig sind, verworfen.PKZip wurde als Shareware vertrieben: Es konnte frei verwendet und kopiert werden, aber der Autor schlug den Benutzern vor, das Programm zu „registrieren“. Für 47 US-Dollar erhalten Sie gedruckte Anweisungen, Premium-Support und eine erweiterte Version der App.Eine der Schlüsselversionen von PKZip war 2.04c, veröffentlicht am 28. Dezember 1992 ( Version 2.04g wurde kurz danach veröffentlicht ). Es wurde der Standard-Deflate-Komprimierungsalgorithmus verwendet. Die Version bestimmte die Weiterentwicklung der Komprimierung in Zip-Dateien ( Artikel zur Veröffentlichung ).Seitdem wurde das Zip-Format in vielen anderen Dateiformaten verwendet. Beispielsweise verwenden Java-Archive (.jar), Android-Anwendungspakete (.apk) und Microsoft Office-DOCX-Dateien das Zip-Format. Viele Formate und Protokolle verwenden denselben Komprimierungsalgorithmus, Deflate. Angenommen, Webseiten werden wahrscheinlich als GZIP-Datei in Ihren Browser übertragen, deren Format die Deflate-Komprimierung verwendet.Phil Katz starb im Jahr 2000. PKWare existiert weiterhin und unterstützt das Zip-Format, obwohl sich das Unternehmen hauptsächlich auf Datenschutzsoftware konzentriert.Info-Zip und Zlib
Kurz nach der Veröffentlichung von PKZip im Jahr 1989 erschienen andere Programme zum Entpacken von Zip-Dateien. Zum Beispiel ein Entpackungsprogramm , das auf Unix-Systemen entpackt werden kann. Im März 1990 wurde eine Mailingliste namens Info-ZIP erstellt.Die Info-ZIP- Gruppe hat kostenlose Open-Source-Programme unzip und zip veröffentlicht , mit denen Zip-Dateien entpackt und erstellt wurden. Der Code wurde auf viele Systeme portiert und ist immer noch der Standard für Zip-Programme für Unix-Systeme. Dies trug später dazu bei, die Popularität von Zip-Dateien zu erhöhen.Sobald die Info-Postleitzahl, die die Deflate-Komprimierung und -Dekomprimierung durchgeführt hat, in eine separate Zlib- Bibliothek verschoben wurde, die sie geschrieben habenJean-loup Gailly (Kompression) und Mark Adler (Auspacken).Jean-loup Gailly (links) und Mark Adler (rechts) beim USENIX STUG Award 2009.Einer der Gründe für die Erstellung der Bibliothek war die bequeme Verwendung der Deflate-Komprimierung in anderen Anwendungen und Formaten, z. B. im neuen gzip und PNG . Diese neuen Formate sollten Compress und GIF ersetzen , die den patentgeschützten LZW-Algorithmus verwendeten.Im Rahmen der Erstellung dieser Formate verfasste Peter Deutsch die Deflate-Spezifikation und veröffentlichte sie im Mai 1996 unter dem Namen Internet RFC 1951 . Dies stellte sich als eine zugänglichere Beschreibung im Vergleich zum ursprünglichen PKZip-Anwendungshinweis heraus.Heute wird zlib überall eingesetzt. Vielleicht ist er jetzt dafür verantwortlich, diese Seite auf einem Webserver zu komprimieren und in Ihrem Browser zu entpacken. Heutzutage werden die meisten Zip-Dateien mit zlib komprimiert und dekomprimiert.Winzip
Viele von denen, die PKZip nicht fanden, verwendeten WinZip. PC-Benutzer wechselten von DOS zu Windows und von PKZip zu WinZip.Alles begann mit einem Projekt des Programmierers Nico Mac, der Software für OS / 2 bei der Mansfield Software Group in Storrs-Mansfield, Connecticut, entwickelte. Nico verwendete den Presentation Manager, dies ist eine grafische Benutzeroberfläche in OS / 2, und er war verärgert, dass er jedes Mal, wenn er Zip-Dateien erstellen wollte, von einem Dateimanager zu DOS-Befehlen wechseln musste.Mac schrieb ein einfaches GUI-Programm, das direkt im Presentation Manager mit Zip-Dateien arbeitete, nannte es PMZip und veröffentlichte es in den 1990er Jahren als Shareware.OS / 2 war nicht erfolgreich und die PC-Welt übernahm Microsoft Windows. 1991 beschloss Mac, das Schreiben von Windows-Programmen zu lernen, und sein erstes Projekt bestand darin, seine Zip-Anwendung auf ein neues Betriebssystem zu portieren. Im April 1991 wurde WinZip 1.00 veröffentlicht . Es wurde als Shareware mit einer 21-tägigen Testphase und einer Registrierungsgebühr von 29 USD verteilt. Sie sah so aus:In den ersten Versionen von WinZip wurde PKZip unter der Haube verwendet. Ab Version 5.0 im Jahr 1993 wurde Code aus Info-ZIP für die direkte Verarbeitung von Zip-Dateien verwendet. Die Benutzeroberfläche hat sich ebenfalls schrittweise weiterentwickelt.WinZip 6.3 unter Windows 3.11 für Arbeitsgruppen.WinZip war in den 1990er Jahren eines der beliebtesten Shareware-Programme. Am Ende hat es jedoch an Relevanz verloren, da die Unterstützung für Zip-Dateien in Betriebssysteme eingebettet wurde. Windows arbeitet seit 2001 mit ihnen als „komprimierte Ordner“ (Windows XP), dafür wird die DynaZip- Bibliothek verwendet.Mac hieß ursprünglich Nico Mak Computing. Im Jahr 2000 wurde es in WinZip Computing umbenannt und in diesen Jahren verließ Mack es. Im Jahr 2005 verkaufte Vector Capital das Unternehmenund am Ende ging es in den Besitz von Corel über , das WinZip immer noch als Produkt herausbringt.Lempel-Ziv-Kompression (LZ77)
Die Zip-Komprimierung besteht aus zwei Hauptbestandteilen: Lempel-Ziv-Komprimierung und Huffman-Code.Eine Möglichkeit, den Text zu komprimieren, besteht darin, eine Liste gängiger Wörter oder Phrasen zu erstellen, wobei verschiedene Arten dieser Wörter im Text durch Links zum Wörterbuch ersetzt werden. Beispielsweise kann das lange Wort "Komprimierung" im Quelltext als # 1234 dargestellt werden, wobei sich 1234 auf die Position des Wortes in der Liste bezieht. Dies wird als Wörterbuchkomprimierung bezeichnet .Unter dem Gesichtspunkt der universellen Komprimierung weist dieses Verfahren jedoch mehrere Nachteile auf. Was genau sollte in das Wörterbuch aufgenommen werden? Die Quelldaten können in verschiedenen Sprachen vorliegen, es kann sich sogar um nicht lesbaren Text handeln. Und wenn das Wörterbuch nicht im Voraus zwischen Komprimierung und Dekomprimierung vereinbart wurde, muss es zusammen mit den komprimierten Daten gespeichert und übertragen werden, was den Vorteil der Komprimierung verringert.Eine elegante Lösung für dieses Problem besteht darin, die Quelldaten selbst als Wörterbuch zu verwenden. Im Jahr 1977 schlugen Jacob Ziv und Abraham Lempel (der bei Technion arbeitete), ein universeller Algorithmus für die sequentielle Datenkomprimierung , ein Komprimierungsschema vor, bei dem die Quelldaten als Folge von Tripletts dargestellt werden:(, , )
wo
sie
eine Rückwärtsverbindung zu der Folge von Zeichen bilden , dass Sie von der vorherigen Position im ursprünglichen Text kopieren möchten, und
dies ist das nächste Zeichen in den erzeugten Daten.Abraham Lempel und Jacob Ziv.Betrachten Sie die folgenden Zeilen:It was the best of times,
it was the worst of times,
In der zweiten Zeile kann die Sequenz "t was the w" als (26, 10, w) dargestellt werden, da sie neu erstellt wird, indem 10 Zeichen von der Position von 26 Zeichen zurück in den Buchstaben "w" kopiert werden. Für Zeichen, die noch nicht angezeigt wurden, werden Backlinks mit der Länge Null verwendet. Zum Beispiel kann das anfängliche "I" als (0, 0, I) dargestellt werden.Dieses Schema wird als Lempel-Ziv-Komprimierung oder LZ77-Komprimierung bezeichnet. In praktischen Implementierungen des Algorithmus wird jedoch normalerweise ein Teil des Tripletts nicht verwendet
. Stattdessen werden Zeichen einzeln generiert und (
,
) Paare für Backlinks verwendet (diese Option wird als LZSS- Komprimierung bezeichnet ). Wie Literale und Backlinks codiert werden, ist ein separates Problem. Wir werden es im Folgenden bei der Analyse des Algorithmus berücksichtigenDie Entleerung .Dieser Text:It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
it was the epoch of belief,
it was the epoch of incredulity,
it was the season of Light,
it was the season of Darkness,
it was the spring of hope,
it was the winter of despair,
we had everything before us,
we had nothing before us,
we were all going direct to Heaven,
we were all going direct the other way
Sie können Folgendes komprimieren:It was the best of times,
i(26,10)wor(27,24)age(25,4)wisdom(26,20)
foolishnes(57,14)epoch(33,4)belief(28,22)incredulity
(33,13)season(34,4)Light(28,23)Dark(120,17)
spring(31,4)hope(231,14)inter(27,4)despair,
we had everyth(57,4)before us(29,9)no(26,20)
we(12,3)all go(29,4)direct to Heaven
(36,28)(139,3)(83,3)(138,3)way
Eine der wichtigen Eigenschaften von Backlinks ist, dass sie sich überlappen können. Dies geschieht, wenn die Länge größer als der Abstand ist. Zum Beispiel:Fa-la-la-la-la
Sie können komprimieren auf:Fa-la(3,9)
Es mag Ihnen seltsam erscheinen, aber die Methode funktioniert: Nachdem die Bytes der ersten drei "-la" kopiert wurden, wird das Kopieren mit den neu generierten Bytes fortgesetzt.Tatsächlich ist dies eine Art der Codierung von Serienlängen , bei der ein Teil der Daten wiederholt kopiert wird, um die gewünschte Länge zu erhalten.Ein interaktives Beispiel für die Verwendung der Lempel-Ziv-Komprimierung für Texte wird in einem Artikel von Colin Morris gezeigt. Werden Pop-Texte immer repetitiver? .Das Folgende ist ein Beispiel für das Kopieren von Backlinks in C. Bitte beachten Sie, dass wir aufgrund möglicher Überlappungen memcpy
oder nicht verwenden können memmove
.
static inline void lz77_output_backref(uint8_t *dst, size_t dst_pos,
size_t dist, size_t len)
{
size_t i;
assert(dist <= dst_pos && "cannot reference before beginning of dst");
for (i = 0; i < len; i++) {
dst[dst_pos] = dst[dst_pos - dist];
dst_pos++;
}
}
Das Generieren von Literalen ist einfach, aber der Vollständigkeit halber verwenden wir eine Hilfsfunktion:
static inline void lz77_output_lit(uint8_t *dst, size_t dst_pos, uint8_t lit)
{
dst[dst_pos] = lit;
}
Beachten Sie, dass der Aufrufer dieser Funktion sicherstellen muss, dass dst
genügend Platz für die generierten Daten vorhanden ist und dass der Backlink vor dem Start des Puffers nicht auf die Position zugreift.Es ist schwierig, beim Entpacken keine Daten mithilfe von Backlinks zu generieren, sondern diese beim Komprimieren der Quelldaten zuerst zu erstellen. Dies kann auf verschiedene Arten geschehen, aber wir werden die Methode verwenden, die auf Hash-Tabellen von zlib basiert, die in RFC 1951 vorgeschlagen wird.Wir werden eine Hash-Tabelle mit den Positionen dreistelliger Präfixe verwenden, die zuvor in der Zeile gefunden wurden (kürzere Backlinks bringen keine Vorteile). Deflate erlaubt Backlinks innerhalb der vorherigen 32.768 Zeichen - dies wird als Fenster bezeichnet. Dies sorgt für eine Streaming-Komprimierung: Die Eingabedaten werden jeweils ein wenig verarbeitet, sofern das Fenster mit den letzten Bytes im Speicher gespeichert ist. Unsere Implementierung setzt jedoch voraus, dass uns alle Eingabedaten zur Verfügung stehen und dass wir sie gleichzeitig vollständig verarbeiten können. Auf diese Weise können Sie sich auf die Komprimierung konzentrieren und nicht auf die Abrechnung, die für die Stream-Verarbeitung erforderlich ist.Wir werden zwei Arrays verwenden: in head
enthält den Hash-Wert des dreistelligen Präfixes für die Position in der Eingabe und in prev
enthält die Position der vorherigen Position mit diesem Hash-Wert. Tatsächlich ist head[h]
dies die Überschrift einer verknüpften Liste von Präfixpositionen mit einem Hash h
und prev[x]
empfängt das Element vor x
der Liste.#define LZ_WND_SIZE 32768
#define LZ_MAX_LEN 258
#define HASH_SIZE 15
#define NO_POS SIZE_MAX
bool lz77_compress(const uint8_t *src, size_t len,
bool (*lit_callback)(uint8_t lit, void *aux),
bool (*backref_callback)(size_t dist, size_t len, void *aux),
void *aux)
{
size_t head[1U << HASH_SIZE];
size_t prev[LZ_WND_SIZE];
uint16_t h;
size_t i, j, dist;
size_t match_len, match_pos;
size_t prev_match_len, prev_match_pos;
for (i = 0; i < sizeof(head) / sizeof(head[0]); i++) {
head[i] = NO_POS;
}
Um eine neue Zeichenfolgenposition in die Hash-Tabelle einzufügen prev
, wird sie aktualisiert, um die vorherige anzugeben head
, und anschließend selbst aktualisiert head
:static void insert_hash(uint16_t hash, size_t pos, size_t *head, size_t *prev)
{
prev[pos % LZ_WND_SIZE] = head[hash];
head[hash] = pos;
}
Achten Sie beim Indizieren auf die Modulo-Operation prev
: Wir interessieren uns nur für die Positionen, die in das aktuelle Fenster fallen.Anstatt den Hash-Wert für jedes dreistellige Präfix von Grund auf neu zu berechnen, verwenden wir einen Ring-Hash und aktualisieren ihn ständig, sodass nur die letzten drei Zeichen in seinem Wert wiedergegeben werden:static uint16_t update_hash(uint16_t hash, uint8_t c)
{
hash <<= 5;
hash ^= c;
hash &= (1U << HASH_SIZE) - 1;
return hash;
}
Die Hash-Karte kann dann verwendet werden, um effizient nach vorherigen Übereinstimmungen mit einer Sequenz zu suchen, wie unten gezeigt. Die Suche nach Übereinstimmungen ist die ressourcenintensivste Komprimierungsoperation, daher wird die Suchtiefe in der Liste begrenzt.Durch Ändern verschiedener Parameter, z. B. der Suchtiefe in der Liste der Präfixe und Durchführen von verzögerten Vergleichen, wie unten beschrieben, können Sie die Geschwindigkeit erhöhen, indem Sie den Komprimierungsgrad verringern. Die Einstellungen in unserem Code werden so ausgewählt, dass sie der maximalen Komprimierungsstufe in zlib entsprechen.
static size_t find_match(const uint8_t *src, size_t pos, uint16_t hash,
size_t prev_match_len, size_t max_match_len,
const size_t *head, const size_t *prev,
size_t *match_pos)
{
size_t max_match_steps = 4096;
size_t i, l;
bool found;
if (prev_match_len == 0) {
prev_match_len = 2;
}
if (prev_match_len >= max_match_len) {
return 0;
}
if (prev_match_len >= 32) {
max_match_steps /= 4;
}
found = false;
i = head[hash];
while (max_match_steps != 0) {
if (i == NO_POS) {
break;
}
assert(i < pos && "Matches should precede pos.");
if (pos - i > LZ_WND_SIZE) {
break;
}
l = cmp(src, i, pos, prev_match_len, max_match_len);
if (l != 0) {
assert(l > prev_match_len);
assert(l <= max_match_len);
found = true;
*match_pos = i;
prev_match_len = l;
if (l == max_match_len) {
return l;
}
}
i = prev[i % LZ_WND_SIZE];
max_match_steps--;
}
if (!found) {
return 0;
}
return prev_match_len;
}
static size_t cmp(const uint8_t *src, size_t i, size_t j,
size_t prev_match_len, size_t max_match_len)
{
size_t l;
assert(prev_match_len < max_match_len);
for (l = 0; l < prev_match_len + 1; l++) {
if (src[i + prev_match_len - l] !=
src[j + prev_match_len - l]) {
return 0;
}
}
assert(l == prev_match_len + 1);
for (; l < max_match_len; l++) {
if (src[i + l] != src[j + l]) {
break;
}
}
assert(l > prev_match_len);
assert(l <= max_match_len);
assert(memcmp(&src[i], &src[j], l) == 0);
return l;
}
Sie können die Funktion mit lz77_compress
diesem Code beenden , um nach vorherigen Übereinstimmungen zu suchen:
h = 0;
if (len >= 2) {
h = update_hash(h, src[0]);
h = update_hash(h, src[1]);
}
prev_match_len = 0;
prev_match_pos = 0;
for (i = 0; i + 2 < len; i++) {
h = update_hash(h, src[i + 2]);
match_len = find_match(src, i, h, prev_match_len,
min(LZ_MAX_LEN, len - i), head, prev,
&match_pos);
insert_hash(h, i, head, prev);
if (prev_match_len != 0 && prev_match_len >= match_len) {
dist = (i - 1) - prev_match_pos;
if (!backref_callback(dist, prev_match_len, aux)) {
return false;
}
for (j = i + 1; j < min((i - 1) + prev_match_len,
len - 2); j++) {
h = update_hash(h, src[j + 2]);
insert_hash(h, j, head, prev);
}
i = (i - 1) + prev_match_len - 1;
prev_match_len = 0;
continue;
}
if (match_len == 0) {
assert(prev_match_len == 0);
if (!lit_callback(src[i], aux)) {
return false;
}
continue;
}
if (prev_match_len != 0) {
if (!lit_callback(src[i - 1], aux)) {
return false;
}
}
prev_match_len = match_len;
prev_match_pos = match_pos;
}
if (prev_match_len != 0) {
dist = (i - 1) - prev_match_pos;
if (!backref_callback(dist, prev_match_len, aux)) {
return false;
}
i = (i - 1) + prev_match_len;
}
for (; i < len; i++) {
if (!lit_callback(src[i], aux)) {
return false;
}
}
return true;
}
Dieser Code sucht nach dem längsten Backlink, der an der aktuellen Position generiert werden kann. Vor der Ausgabe entscheidet das Programm jedoch, ob es möglich ist, an der nächsten Position eine noch längere Übereinstimmung zu finden. In zlib wird dies als verzögerte Vergleichsbewertung bezeichnet . Dies ist immer noch ein gieriger Algorithmus: Er wählt die längste Übereinstimmung aus, auch wenn die aktuell kürzere es Ihnen ermöglicht, später eine Übereinstimmung noch länger zu erzielen und eine stärkere Komprimierung zu erzielen.Die Lempel-Ziv-Komprimierung kann sowohl schnell als auch langsam arbeiten. Zopfliverbrachte viel Zeit damit, nach optimalen Backlinks zu suchen, um zusätzliche Komprimierungsprozentsätze zu erzielen. Dies ist nützlich für Daten, die einmal komprimiert und dann wiederverwendet werden, z. B. für statische Informationen auf einem Webserver. Auf der anderen Seite der Skala befinden sich Kompressoren wie Snappy und LZ4 , die nur mit dem letzten 4-Byte-Präfix verglichen werden und sehr schnell sind. Diese Art der Komprimierung ist in Datenbanken und RPC-Systemen nützlich, in denen sich die für die Komprimierung aufgewendete Zeit auszahlt, indem Zeit beim Senden von Daten über ein Netzwerk oder auf die Festplatte gespart wird.Die Idee, Quelldaten als Wörterbuch zu verwenden, ist sehr elegant, aber Sie können auch von einem statischen Wörterbuch profitieren. Brotli ist ein LZ77-basierter Algorithmus, der jedoch auch einen großen verwendetstatisches Wörterbuch der Zeichenfolge, die häufig im Netzwerk gefunden werden.Der LZ77-Code kann in lz77.h und lz77.c angezeigt werden .Huffman-Code
Der zweite Zip-Komprimierungsalgorithmus ist der Huffman-Code.Der Begriff Code bezieht sich in diesem Zusammenhang auf ein System zur Darstellung von Daten in einer anderen Form. In diesem Fall interessieren wir uns für Code, mit dem vom Lempel-Ziv-Algorithmus generierte Literale und Backlinks effizient dargestellt werden können.Traditionell wird englischer Text unter Verwendung des amerikanischen Standardcodes für den Informationsaustausch (ASCII) dargestellt . Dieses System weist jedem Zeichen eine Nummer zu, die normalerweise in einer 8-Bit-Darstellung gespeichert ist. Hier sind die ASCII-Codes für die Großbuchstaben des englischen Alphabets:Ein Byte pro Zeichen ist eine bequeme Möglichkeit, Text zu speichern. Sie können leicht auf Teile des Textes zugreifen oder diese ändern, und es ist immer klar, wie viele Bytes zum Speichern von N Zeichen erforderlich sind oder wie viele Zeichen in N Bytes gespeichert sind. Dies ist jedoch nicht der effektivste Weg in Bezug auf den belegten Raum. Beispielsweise wird im Englischen der Buchstabe E am häufigsten verwendet, und Z wird am wenigsten verwendet. In Bezug auf das Volumen ist es daher effizienter, eine kürzere Bitdarstellung für E und eine längere für Z zu verwenden, anstatt jedem Zeichen die gleiche Anzahl von Bits zuzuweisen.Ein Code, der Codierungen unterschiedlicher Länge für unterschiedliche Quellzeichen angibt, wird als Code variabler Länge bezeichnet . Das bekannteste Beispiel ist der Morsecode., in dem jedes Zeichen mit Punkten und Strichen codiert ist, die ursprünglich per Telegraph mit kurzen und langen Impulsen übertragen wurden:Einer der Nachteile des Morsecodes besteht darin, dass ein Codewort ein Präfix eines anderen sein kann. Zum Beispiel hat • • - • keine eindeutige Dekodierung: Es kann F oder ER sein. Dies wird durch Pausen (drei Punkte lang) zwischen den Buchstaben während der Übertragung gelöst. Es wäre jedoch besser, wenn Codewörter keine Präfixe anderer Wörter sein könnten. Dieser Code wird als nicht neu fixiert bezeichnet . ASCII-Code mit fester Länge wird nicht neu fixiert, da Codewörter immer dieselbe Länge haben. Codes mit variabler Länge können jedoch auch nicht neu fixiert werden. Telefonnummern werden oft nicht fixiert. Bevor die Notrufnummer 112 in Schweden eingeführt wurde, mussten alle Nummern, die mit 112 beginnen, geändert werden. In den USA gibt es keine einzige Telefonnummer, die mit 911 beginnt.Um die Größe der codierten Nachricht zu minimieren, ist es besser, einen nicht fixierten Code zu verwenden, in dem häufig vorkommende Zeichen kürzere Codewörter haben. Der optimale Code ist derjenige, der das kürzestmögliche Ergebnis generiert - die Summe der Längen von Codewörtern multipliziert mit ihrer Häufigkeit ist das minimal mögliche. Dies wird zu Ehren des Erfinders eines effizienten Algorithmus zum Erzeugen solcher Codes als Nicht-Präfix-Code mit minimaler Redundanz oder als Huffman-Code bezeichnet .Huffman-Algorithmus
Während des Studiums der Materialien für seine Doktorarbeit über Elektrotechnik am MIT besuchte David Huffman einen Kurs über Informationstheorie, der von Robert Fano unterrichtet wurde. Der Legende nach erlaubte Fano seinen Schülern zu wählen: Schreiben Sie die Abschlussprüfung oder den Kurs. Huffman entschied sich für Letzteres und erhielt das Thema der Suche nach präfixlosen Codes mit minimaler Redundanz. Es wird angenommen, dass er nicht wusste, dass Fano zu dieser Zeit selbst an dieser Aufgabe arbeitete (der Shannon-Fano-Algorithmus war in jenen Jahren die bekannteste Methode ). Huffmans Arbeit wurde 1952 unter dem Titel Eine Methode zur Konstruktion von Mindestredundanzcodes veröffentlicht. Seitdem ist ihr Algorithmus weit verbreitet.David Huffman Pressemitteilung UC Santa Cruz.Der Huffman-Algorithmus erstellt nicht neu fixierten Code mit minimaler Redundanz für den Zeichensatz und dessen Verwendungshäufigkeit. Der Algorithmus wählt wiederholt zwei Zeichen aus, die in den Quelldaten am wenigsten wahrscheinlich sind - beispielsweise X und Y - und ersetzt sie durch ein zusammengesetztes Zeichen, das „X oder Y“ bedeutet. Die Häufigkeit des Auftretens eines zusammengesetzten Symbols ist die Summe der Häufigkeiten zweier Quellensymbole. Die Codewörter für X und Y können beliebige Codewörter sein, die dem zusammengesetzten Zeichen "X oder Y" gefolgt von 0 oder 1 zugewiesen werden, um die ursprünglichen Zeichen zu unterscheiden. Wenn die Eingabedaten auf ein Zeichen reduziert werden, funktioniert der Algorithmus nicht mehr ( Videoerklärung ).Hier ist ein Beispiel für den Algorithmus, der an einem kleinen Zeichensatz arbeitet:Erste Iteration der Verarbeitung:Die beiden seltensten Symbole C und D werden aus der Menge entfernt und durch ein zusammengesetztes Symbol ersetzt, dessen Frequenz die Summe der Frequenzen C und D ist:Jetzt sind die seltensten Symbole B und ein zusammengesetztes Symbol mit einer Häufigkeit von 5. Sie werden aus dem Satz entfernt und durch ein zusammengesetztes Symbol mit einer Häufigkeit von 9 ersetzt:Schließlich werden A und ein zusammengesetztes Symbol mit einer Frequenz von 9 zu einem neuen Symbol mit einer Frequenz von 15 kombiniert:Der gesamte Satz wurde auf ein Zeichen reduziert, die Verarbeitung ist abgeschlossen.Der Algorithmus erstellte eine Struktur namens Huffman-Baum . Eingabezeichen sind Blätter, und je höher die Häufigkeit eines Zeichens ist, desto höher befindet es sich. Ausgehend von der Wurzel des Baums können Sie Codewörter für Zeichen generieren, indem Sie 0 oder 1 hinzufügen, wenn Sie sich nach links bzw. rechts bewegen. Es stellt sich so heraus:Kein Codewort ist ein Präfix für ein anderes. Je öfter ein Symbol vorkommt, desto kürzer ist sein Codewort.Der Baum kann auch zum Dekodieren verwendet werden: Wir beginnen bei der Wurzel und gehen nach rechts oder links für den Wert mit 0 oder 1 vor dem Zeichen. Beispielsweise wird die Zeile 010100 in ABBA decodiert.Beachten Sie, dass die Länge jedes Codeworts der Tiefe des entsprechenden Baumknotens entspricht. Wie wir im nächsten Teil sehen werden, benötigen wir keinen echten Baum, um Codewörter zuzuweisen. Es reicht aus, die Länge der Wörter selbst zu kennen. Das Ergebnis unserer Implementierung des Huffman-Algorithmus ist daher die Länge der Codewörter.Um den Zeichensatz zu speichern und die niedrigsten Frequenzen effizient zu finden, verwenden wir die binäre Heap- Datenstruktur . Insbesondere interessieren unsMin-Heap , da der Mindestwert oben liegen sollte.
static void swap32(uint32_t *a, uint32_t *b)
{
uint32_t tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
static void minheap_down(uint32_t *heap, size_t n, size_t i)
{
size_t left, right, min;
assert(i >= 1 && i <= n && "i must be inside the heap");
while (i * 2 <= n) {
left = i * 2;
right = i * 2 + 1;
min = left;
if (right <= n && heap[right] < heap[left]) {
min = right;
}
if (heap[min] < heap[i]) {
swap32(&heap[min], &heap[i]);
i = min;
} else {
break;
}
}
}
static void minheap_heapify(uint32_t *heap, size_t n)
{
size_t i;
for (i = n / 2; i >= 1; i--) {
minheap_down(heap, n, i);
}
}
Um die Häufigkeit von n
Zeichen zu verfolgen , werden wir eine Reihe von n
Elementen verwenden. Außerdem möchten wir jedes Mal, wenn ein zusammengesetztes Symbol erstellt wird, beide Quellensymbole damit verknüpfen. Daher hat jedes Symbol ein „Kommunikationselement“.Um den Elementelement- n
Heap und die n
Kommunikationselemente zu speichern , verwenden wir ein Array von n * 2 + 1
Elementen. Wenn zwei Zeichen auf dem Heap durch eines ersetzt werden, verwenden wir das zweite Element, um den Link zum neuen Zeichen zu speichern. Dieser Ansatz basiert auf der Implementierung der Verwaltung von Gigabyte von Witten, Moffat und Bell.An jedem Knoten im Heap werden die 16 höchstwertigen Bits zum Speichern der Symbolfrequenz und die 16 niedrigstwertigen Bits zum Speichern des Index des Symbolkommunikationselements verwendet. Aufgrund der Verwendung hoher Bits wird die Frequenzdifferenz durch das Ergebnis eines 32-Bit-Vergleichs zwischen zwei Elementen des Heaps bestimmt.Aufgrund dieser Darstellung müssen wir sicherstellen, dass die Häufigkeit der Zeichen immer in 16 Bit passt. Nach Abschluss des Algorithmus hat das endgültige zusammengesetzte Symbol die Häufigkeit aller kombinierten Symbole, dh diese Summe sollte in 16 Bit angegeben werden. Unsere Deflate-Implementierung überprüft dies, indem sie gleichzeitig bis zu 64.535 Zeichen verarbeitet.Symbole mit einer Frequenz von Null erhalten Codewörter mit einer Länge von Null und nehmen nicht an der Kompilierung der Codierung teil.Wenn das Codewort die angegebene maximale Tiefe erreicht, werden wir die Häufigkeitsverteilung durch Auferlegen einer Frequenzbegrenzung „glätten“ und es erneut versuchen (ja, mit Hilfe goto
). Es gibt ausgefeiltere Möglichkeiten, eine tiefenbegrenzte Huffman-Codierung durchzuführen, aber diese ist einfach und effizient.#define MAX_HUFFMAN_SYMBOLS 288
static void compute_huffman_lengths(const uint16_t *freqs, size_t n,
uint8_t max_len, uint8_t *lengths)
{
uint32_t nodes[MAX_HUFFMAN_SYMBOLS * 2 + 1], p, q;
uint16_t freq;
size_t i, h, l;
uint16_t freq_cap = UINT16_MAX;
#ifndef NDEBUG
uint32_t freq_sum = 0;
for (i = 0; i < n; i++) {
freq_sum += freqs[i];
}
assert(freq_sum <= UINT16_MAX && "Frequency sum too large!");
#endif
assert(n <= MAX_HUFFMAN_SYMBOLS);
assert((1U << max_len) >= n && "max_len must be large enough");
try_again:
h = 0;
for (i = 0; i < n; i++) {
freq = freqs[i];
if (freq == 0) {
continue;
}
if (freq > freq_cap) {
freq = freq_cap;
}
h++;
nodes[h] = ((uint32_t)freq << 16) | (uint32_t)(n + h);
}
minheap_heapify(nodes, h);
if (h < 2) {
for (i = 0; i < n; i++) {
lengths[i] = (freqs[i] == 0) ? 0 : 1;
}
return;
}
while (h > 1) {
p = nodes[1];
nodes[1] = nodes[h--];
minheap_down(nodes, h, 1);
q = nodes[1];
nodes[1] = ((p & 0xffff0000) + (q & 0xffff0000))
| (uint32_t)(h + 1);
nodes[p & 0xffff] = nodes[q & 0xffff] = (uint32_t)(h + 1);
minheap_down(nodes, h, 1);
}
h = 0;
for (i = 0; i < n; i++) {
if (freqs[i] == 0) {
lengths[i] = 0;
continue;
}
h++;
p = nodes[n + h];
l = 1;
while (p != 2) {
l++;
p = nodes[p];
}
if (l > max_len) {
assert(freq_cap != 1 && "Cannot lower freq_cap!");
freq_cap /= 2;
goto try_again;
}
assert(l <= UINT8_MAX);
lengths[i] = (uint8_t)l;
}
}
Eine elegante Alternative zur binären Heap-Option besteht darin, Zeichen in zwei Warteschlangen zu speichern. Das erste enthält die Quellzeichen, sortiert nach Häufigkeit. Wenn ein zusammengesetztes Symbol erstellt wird, wird es sekundär hinzugefügt. Somit befindet sich das Symbol mit der niedrigsten Frequenz immer an der ersten Position einer der Warteschlangen. Dieser Ansatz wird von Jan van Leeuwen in Über die Konstruktion von Huffman-Bäumen (1976) beschrieben.Die Huffman-Codierung ist optimal für Nicht-Präfix-Codes, in anderen Fällen gibt es jedoch effizientere Methoden: arithmetische Codierung und asymmetrische Zahlensysteme .Huffmans kanonische Codes
Im obigen Beispiel haben wir einen Huffman-Baum erstellt:Wenn wir von der Wurzel gehen und 0 für den linken Zweig und 1 für den rechten verwenden, erhalten wir die folgenden Codes:Die Entscheidung, 0 für den linken Zweig und 1 für den rechten Zweig zu verwenden, scheint willkürlich. Wenn wir das Gegenteil tun, erhalten wir:Wir können zwei Zweige, die von einem Knoten stammen, willkürlich mit Null und Eins markieren (Hauptsache, die Bezeichnungen sind unterschiedlich) und trotzdem den entsprechenden Code erhalten:Obwohl der Huffman-Algorithmus die erforderlichen Codewortlängen für nicht fixierten Code mit minimaler Redundanz bereitstellt, gibt es viele Möglichkeiten, einzelne Codewörter zuzuweisen.Angesichts der Länge des vom Huffman-Algorithmus berechneten Codeworts weist der kanonische Huffman-Code Zeichen auf bestimmte Weise Codewörter zu. Dies ist nützlich, da Sie damit Codewortlängen mit komprimierten Daten speichern und übertragen können: Der Decoder kann Codewörter basierend auf ihren Längen wiederherstellen. Natürlich können Sie Symbolfrequenzen speichern und übertragen und den Huffman-Algorithmus im Decoder ausführen, dies erfordert jedoch mehr Arbeit und mehr Speicherplatz vom Decoder. Eine weitere sehr wichtige Eigenschaft ist, dass die Struktur kanonischer Codes eine effiziente Decodierung verwendet.Die Idee ist, Zeichen nacheinander untereinander Codewörter zuzuweisen. Das erste Codewort ist 0. Das nächste ist ein Wort mit einer Länge des vorherigen Wortes + 1. Das erste Wort mit einer Länge von N besteht aus dem letzten Wort der Länge N-1, wobei eins hinzugefügt wird (um ein neues Codewort zu erhalten) und ein Schritt nach links verschoben wird (um die Länge zu erhöhen).In der Terminologie des Hoffman-Baums werden den Wörtern nacheinander Codewörter in der Reihenfolge von links nach rechts zugewiesen, und zwar eine Ebene nach der anderen, wobei sie sich beim Übergang zur nächsten Ebene nach links verschieben.In unserem ABCD-Beispiel hat der Huffman-Algorithmus Codewörter mit Längen von 1, 2, 3 und 3 zugewiesen. Das erste Wort ist 0. Dies ist auch das letzte Wort der Länge 1. Für die Länge 2 nehmen wir 0 und addieren 1, um den nächsten Code zu erhalten, der zum Präfix von Zwei-Bit-Codes wird Verschieben Sie nach links und erhalten Sie 10. Dies ist nun das letzte Wort der Länge 2. Um die Länge 3 zu erhalten, addieren wir 1 und verschieben: 110. Um das nächste Wort der Länge 3 zu erhalten, addieren wir 1: 111.Die Implementierung des kanonischen Codegenerators ist unten dargestellt. Beachten Sie, dass der Deflate-Algorithmus erwartet, dass Codewörter auf der Grundlage des LSB-first-Prinzips (zuerst das niedrigstwertige Bit) generiert werden. Das heißt, das erste Bit des Codeworts sollte im niedrigstwertigen Bit gespeichert werden. Dies bedeutet, dass wir die Reihenfolge der Bits ändern müssen, beispielsweise mithilfe der Nachschlagetabelle.#define MAX_HUFFMAN_BITS 15
static void compute_canonical_code(uint16_t *codewords, const uint8_t *lengths,
size_t n)
{
size_t i;
uint16_t count[MAX_HUFFMAN_BITS + 1] = {0};
uint16_t code[MAX_HUFFMAN_BITS + 1];
int l;
for (i = 0; i < n; i++) {
count[lengths[i]]++;
}
count[0] = 0;
code[0] = 0;
for (l = 1; l <= MAX_HUFFMAN_BITS; l++) {
code[l] = (uint16_t)((code[l - 1] + count[l - 1]) << 1);
}
for (i = 0; i < n; i++) {
l = lengths[i];
if (l == 0) {
continue;
}
codewords[i] = reverse16(code[l]++, l);
}
}
static inline uint16_t reverse16(uint16_t x, int n)
{
uint16_t lo, hi;
uint16_t reversed;
assert(n > 0);
assert(n <= 16);
lo = x & 0xff;
hi = x >> 8;
reversed = (uint16_t)((reverse8_tbl[lo] << 8) | reverse8_tbl[hi]);
return reversed >> (16 - n);
}
Setzen Sie nun alles zusammen und schreiben Sie den Encoder-Initialisierungscode:typedef struct huffman_encoder_t huffman_encoder_t;
struct huffman_encoder_t {
uint16_t codewords[MAX_HUFFMAN_SYMBOLS];
uint8_t lengths[MAX_HUFFMAN_SYMBOLS];
};
void huffman_encoder_init(huffman_encoder_t *e, const uint16_t *freqs, size_t n,
uint8_t max_codeword_len)
{
assert(n <= MAX_HUFFMAN_SYMBOLS);
assert(max_codeword_len <= MAX_HUFFMAN_BITS);
compute_huffman_lengths(freqs, n, max_codeword_len, e->lengths);
compute_canonical_code(e->codewords, e->lengths, n);
}
Wir machen auch eine Funktion, um den Encoder unter Verwendung der bereits berechneten Codelängen zu konfigurieren:
void huffman_encoder_init2(huffman_encoder_t *e, const uint8_t *lengths,
size_t n)
{
size_t i;
for (i = 0; i < n; i++) {
e->lengths[i] = lengths[i];
}
compute_canonical_code(e->codewords, e->lengths, n);
}
Effiziente Huffman-Dekodierung
Der einfachste Weg, Huffman zu dekodieren, besteht darin, den Baum von der Wurzel aus zu durchlaufen, jeweils ein Eingabebit zu lesen und zu entscheiden, welcher Zweig als nächstes, links oder rechts verwendet werden soll. Wenn ein Blattknoten erreicht ist, handelt es sich um ein dekodiertes Zeichen.Diese Methode wird oft an Universitäten und in Büchern gelehrt. Es ist einfach und elegant, aber die Verarbeitung von Bit zu Bit ist zu langsam. Das Dekodieren mit der Nachschlagetabelle ist viel schneller. Für das obige Beispiel, in dem die maximale Codewortlänge drei Bit beträgt, können Sie die folgende Tabelle verwenden:Obwohl es nur vier Zeichen gibt, benötigen wir eine Tabelle mit acht Einträgen, um alle möglichen Drei-Bit-Kombinationen abzudecken. Symbole mit Codewörtern, die kürzer als drei Bits sind, haben mehrere Einträge in der Tabelle. Zum Beispiel wurde das Wort 10 mit 10 0 und 10 1 „ergänzt“ , um alle Drei-Bit-Kombinationen ab 10 abzudecken.Um auf diese Weise zu dekodieren, müssen Sie in der Tabelle mit den folgenden drei Eingabebits indizieren und sofort das entsprechende Zeichen und die Länge seines Codeworts finden. Die Länge ist wichtig, da wir trotz der Betrachtung der nächsten drei Bits die gleiche Anzahl von Eingabebits wie die Länge des Codeworts erhalten müssen.Die auf Suchtabellen basierende Methode funktioniert sehr schnell, hat jedoch einen Nachteil: Die Größe der Tabelle verdoppelt sich mit jedem zusätzlichen Bit in der Länge des Codeworts. Das heißt, der Aufbau der Tabelle verlangsamt sich exponentiell, und wenn sie nicht mehr in den Prozessor-Cache passt, beginnt die Methode langsam zu arbeiten.Aus diesem Grund wird die Nachschlagetabelle normalerweise nur für Codewörter verwendet, die nicht größer als eine bestimmte Länge sind. Und für längere Wörter gehen Sie anders vor. So wie die Huffman-Codierung häufigeren Zeichen kürzere Codewörter zuweist, ist die Verwendung einer Nachschlagetabelle für kurze Codewörter in vielen Fällen eine hervorragende Optimierung.In zlibEs werden mehrere Ebenen von Suchtabellen verwendet. Wenn das Codewort für die erste Tabelle zu lang ist, wird die Suche in die sekundäre Tabelle verschoben, um die verbleibenden Bits zu indizieren.Es gibt jedoch eine andere, sehr elegante Methode, die auf den Eigenschaften kanonischer Huffman-Codes basiert. Es wird in Über die Implementierung von Präfixcodes für minimale Redundanz (Moffat und Turpin, 1997) beschrieben und auch in Charles Blooms The Lost Huffman Paper erläutert .Nehmen wir die Codewörter aus der kanonischen Version: 0, 10, 110, 111. Wir verfolgen die ersten Codewörter jeder Länge sowie die Nummer jedes Codeworts in der allgemeinen Reihenfolge - "Symbolindex".Da Codewörter nacheinander zugewiesen werden, können wir in der obigen Tabelle das Symbol finden, das diese Bits darstellen, wenn wir die Anzahl der Bits kennen. Zum Beispiel sehen wir für das Drei-Bit-111, dass dies ein Versatz von eins gegenüber dem ersten Codewort dieser Länge (110) ist. Der erste Zeichenindex dieser Länge ist 3, und ein Versatz von eins ergibt einen Index von 4. Eine andere Tabelle vergleicht den Zeichenindex mit dem Zeichen:sym_idx = d->first_symbol[len] + (bits - d->first_code[len]);
sym = d->syms[sym_idx];
Eine kleine Optimierung: Anstatt den ersten Zeichenindex und das erste Codewort separat zu speichern, können wir den ersten Index in der Tabelle abzüglich des ersten Codeworts speichern:sym_idx = d->offset_first_sym_idx[len] + bits;
sym = d->syms[sym_idx];
Um zu verstehen, wie viele Bits geschätzt werden müssen, verwenden wir erneut die Codesequenz-Eigenschaft. In unserem Beispiel sind alle gültigen Ein-Bit-Codewörter streng kleiner als 1, zwei Bit - streng weniger als 11, drei Bit - weniger als 1000 (tatsächlich gilt dies für alle Drei-Bit-Werte). Mit anderen Worten, das gültige N-Bit-Codewort muss strikt kleiner sein als das erste N-Bit-Codewort plus die Anzahl der N-Bit-Codewörter. Darüber hinaus können wir diese Grenzen nach links verschieben, sodass sie alle drei Bit breit sind. Nennen wir es restriktive Bits für jede der Codewortlängen:Der Begrenzer für Länge 3 ist auf 4 Bit übergelaufen, dies bedeutet jedoch nur, dass jedes Drei-Bit-Wort ausreicht.Wir können zwischen den Drei-Bit-Eingabedaten suchen und mit den restriktiven Bits vergleichen, um zu verstehen, wie lang unser Codewort ist. Nach Abschluss verschieben wir die Eingabebits, um nur die richtige Anzahl zu berechnen, und suchen dann den Zeichenindex:for (len = 1; len <= 3; len++) {
if (bits < d->sentinel_bits[len]) {
bits >>= 3 - len;
sym_idx = d->offset_first_sym_idx[len] + bits;
}
}
Die zeitliche Komplexität des Prozesses ist in Bezug auf die Anzahl der Bits in den Codewörtern linear, aber der Platz wird effizient genutzt, bei jedem Schritt ist nur Laden und Vergleichen erforderlich, und da kürzere Codewörter häufiger sind, ermöglicht das Verfahren die Optimierung der Komprimierung in vielen Situationen.Vollständiger Decodercode:#define HUFFMAN_LOOKUP_TABLE_BITS 8
typedef struct huffman_decoder_t huffman_decoder_t;
struct huffman_decoder_t {
struct {
uint16_t sym : 9;
uint16_t len : 7;
} table[1U << HUFFMAN_LOOKUP_TABLE_BITS];
uint16_t sentinel_bits[MAX_HUFFMAN_BITS + 1];
uint16_t offset_first_sym_idx[MAX_HUFFMAN_BITS + 1];
uint16_t syms[MAX_HUFFMAN_SYMBOLS];
#ifndef NDEBUG
size_t num_syms;
#endif
};
static inline uint64_t lsb(uint64_t x, int n)
{
assert(n >= 0 && n <= 63);
return x & (((uint64_t)1 << n) - 1);
}
static inline int huffman_decode(const huffman_decoder_t *d, uint16_t bits,
size_t *num_used_bits)
{
uint64_t lookup_bits;
size_t l;
size_t sym_idx;
lookup_bits = lsb(bits, HUFFMAN_LOOKUP_TABLE_BITS);
assert(lookup_bits < sizeof(d->table) / sizeof(d->table[0]));
if (d->table[lookup_bits].len != 0) {
assert(d->table[lookup_bits].len <= HUFFMAN_LOOKUP_TABLE_BITS);
assert(d->table[lookup_bits].sym < d->num_syms);
*num_used_bits = d->table[lookup_bits].len;
return d->table[lookup_bits].sym;
}
bits = reverse16(bits, MAX_HUFFMAN_BITS);
for (l = HUFFMAN_LOOKUP_TABLE_BITS + 1; l <= MAX_HUFFMAN_BITS; l++) {
if (bits < d->sentinel_bits[l]) {
bits >>= MAX_HUFFMAN_BITS - l;
sym_idx = (uint16_t)(d->offset_first_sym_idx[l] + bits);
assert(sym_idx < d->num_syms);
*num_used_bits = l;
return d->syms[sym_idx];
}
}
*num_used_bits = 0;
return -1;
}
Um den Decoder zu konfigurieren, berechnen wir die kanonischen Codes wie für huffman_encoder_init vor und füllen verschiedene Tabellen aus:
bool huffman_decoder_init(huffman_decoder_t *d, const uint8_t *lengths,
size_t n)
{
size_t i;
uint16_t count[MAX_HUFFMAN_BITS + 1] = {0};
uint16_t code[MAX_HUFFMAN_BITS + 1];
uint32_t s;
uint16_t sym_idx[MAX_HUFFMAN_BITS + 1];
int l;
#ifndef NDEBUG
assert(n <= MAX_HUFFMAN_SYMBOLS);
d->num_syms = n;
#endif
for (i = 0; i < sizeof(d->table) / sizeof(d->table[0]); i++) {
d->table[i].len = 0;
}
for (i = 0; i < n; i++) {
assert(lengths[i] <= MAX_HUFFMAN_BITS);
count[lengths[i]]++;
}
count[0] = 0;
code[0] = 0;
sym_idx[0] = 0;
for (l = 1; l <= MAX_HUFFMAN_BITS; l++) {
code[l] = (uint16_t)((code[l - 1] + count[l - 1]) << 1);
if (count[l] != 0 && code[l] + count[l] - 1 > (1U << l) - 1) {
return false;
}
s = (uint32_t)((code[l] + count[l]) << (MAX_HUFFMAN_BITS - l));
d->sentinel_bits[l] = (uint16_t)s;
assert(d->sentinel_bits[l] == s && "No overflow.");
sym_idx[l] = sym_idx[l - 1] + count[l - 1];
d->offset_first_sym_idx[l] = sym_idx[l] - code[l];
}
for (i = 0; i < n; i++) {
l = lengths[i];
if (l == 0) {
continue;
}
d->syms[sym_idx[l]] = (uint16_t)i;
sym_idx[l]++;
if (l <= HUFFMAN_LOOKUP_TABLE_BITS) {
table_insert(d, i, l, code[l]);
code[l]++;
}
}
return true;
}
static void table_insert(huffman_decoder_t *d, size_t sym, int len,
uint16_t codeword)
{
int pad_len;
uint16_t padding, index;
assert(len <= HUFFMAN_LOOKUP_TABLE_BITS);
codeword = reverse16(codeword, len);
pad_len = HUFFMAN_LOOKUP_TABLE_BITS - len;
for (padding = 0; padding < (1U << pad_len); padding++) {
index = (uint16_t)(codeword | (padding << len));
d->table[index].sym = (uint16_t)sym;
d->table[index].len = (uint16_t)len;
assert(d->table[index].sym == sym && "Fits in bitfield.");
assert(d->table[index].len == len && "Fits in bitfield.");
}
}
Entleeren
Der 1993 in PKZip 2.04c eingeführte Deflate-Algorithmus ist eine Standardkomprimierungsmethode in modernen Zip-Dateien. Es wird auch in gzip, PNG und vielen anderen Formaten verwendet. Es verwendet eine Kombination aus LZ77-Komprimierung und Huffman-Codierung, die wir in diesem Abschnitt diskutieren und implementieren werden.Vor Deflate verwendete PKZip die Komprimierungsmethoden Shrink, Reduce und Implode. Heute sind sie selten, obwohl sie nach Deflate noch einige Zeit in Gebrauch waren, weil sie weniger Speicher verbrauchten. Aber wir werden sie nicht berücksichtigen.Bitströme
Deflate speichert Huffman-Codewörter in einem Bitstrom nach dem LSB-First-Prinzip. Dies bedeutet, dass das erste Bit des Streams im niedrigstwertigen Bit des ersten Bytes gespeichert ist.Betrachten Sie einen Bitstrom (von links nach rechts gelesen) 1-0-0-1-1. Wenn es nach dem LSB-first-Prinzip gespeichert wird, wird der Bytewert 0b00011001 (binär) oder 0x19 (hexadezimal). Es mag scheinen, dass der Stream einfach rückwärts dargestellt wird (in gewissem Sinne auch), aber der Vorteil ist, dass es für uns einfacher ist, die ersten N Bits aus einem Computerwort zu erhalten: Wir verstecken einfach die N niedrigstwertigen Bits.Diese Prozeduren stammen aus bitstream.h :
typedef struct istream_t istream_t;
struct istream_t {
const uint8_t *src;
const uint8_t *end;
size_t bitpos;
size_t bitpos_end;
};
static inline void istream_init(istream_t *is, const uint8_t *src, size_t n)
{
is->src = src;
is->end = src + n;
is->bitpos = 0;
is->bitpos_end = n * 8;
}
Unser Huffman-Decoder muss die folgenden Bits im Stream betrachten (genügend Bits für das längste mögliche Codewort) und dann den Stream mit der Anzahl der vom decodierten Symbol verwendeten Bits fortsetzen:#define ISTREAM_MIN_BITS (64 - 7)
static inline uint64_t istream_bits(const istream_t *is)
{
const uint8_t *next;
uint64_t bits;
int i;
next = is->src + (is->bitpos / 8);
assert(next <= is->end && "Cannot read past end of stream.");
if (is->end - next >= 8) {
bits = read64le(next);
} else {
bits = 0;
for (i = 0; i < is->end - next; i++) {
bits |= (uint64_t)next[i] << (i * 8);
}
}
return bits >> (is->bitpos % 8);
}
static inline bool istream_advance(istream_t *is, size_t n) {
if (is->bitpos + n > is->bitpos_end) {
return false;
}
is->bitpos += n;
return true;
}
Das Fazit ist, dass Sie auf 64-Bit-Computern istream_bits
normalerweise als Single-Boot-Befehl und als Arithmetik ausgeführt werden können, da sich die Strukturelemente istream_t
in Registern befinden. read64le ist in bits.h implementiert (moderne Compiler konvertieren es nach dem Little-Endian-Prinzip in einen einzelnen 64-Bit-Download):
static inline uint64_t read64le(const uint8_t *p)
{
return ((uint64_t)p[0] << 0) |
((uint64_t)p[1] << 8) |
((uint64_t)p[2] << 16) |
((uint64_t)p[3] << 24) |
((uint64_t)p[4] << 32) |
((uint64_t)p[5] << 40) |
((uint64_t)p[6] << 48) |
((uint64_t)p[7] << 56);
}
Wir brauchen auch eine Funktion, um den Bitstrom bis zur Grenze des nächsten Bytes fortzusetzen:
static inline size_t round_up(size_t x, size_t m)
{
assert((m & (m - 1)) == 0 && "m must be a power of two");
return (x + m - 1) & (size_t)(-m);
}
static inline const uint8_t *istream_byte_align(istream_t *is)
{
const uint8_t *byte;
assert(is->bitpos <= is->bitpos_end && "Not past end of stream.");
is->bitpos = round_up(is->bitpos, 8);
byte = is->src + is->bitpos / 8;
assert(byte <= is->end);
return byte;
}
Für einen ausgehenden Bitstrom schreiben wir Bits unter Verwendung eines Lese-, Änderungs- und Schreibprozesses. Im schnellen Fall können Sie ein Bit mit einem 64-Bit-Lesevorgang, einer Art Bit-Operation und einem 64-Bit-Schreibvorgang schreiben.
typedef struct ostream_t ostream_t;
struct ostream_t {
uint8_t *dst;
uint8_t *end;
size_t bitpos;
size_t bitpos_end;
};
static inline void ostream_init(ostream_t *os, uint8_t *dst, size_t n)
{
os->dst = dst;
os->end = dst + n;
os->bitpos = 0;
os->bitpos_end = n * 8;
}
static inline size_t ostream_bit_pos(const ostream_t *os)
{
return os->bitpos;
}
static inline size_t ostream_bytes_written(ostream_t *os)
{
return round_up(os->bitpos, 8) / 8;
}
static inline bool ostream_write(ostream_t *os, uint64_t bits, size_t n)
{
uint8_t *p;
uint64_t x;
int shift, i;
assert(n <= 57);
assert(bits <= ((uint64_t)1 << n) - 1 && "Must fit in n bits.");
if (os->bitpos_end - os->bitpos < n) {
return false;
}
p = &os->dst[os->bitpos / 8];
shift = os->bitpos % 8;
if (os->end - p >= 8) {
x = read64le(p);
x = lsb(x, shift);
x |= bits << shift;
write64le(p, x);
} else {
x = 0;
for (i = 0; i < os->end - p; i++) {
x |= (uint64_t)p[i] << (i * 8);
}
x = lsb(x, shift);
x |= bits << shift;
for (i = 0; i < os->end - p; i++) {
p[i] = (uint8_t)(x >> (i * 8));
}
}
os->bitpos += n;
return true;
}
static inline void write64le(uint8_t *dst, uint64_t x)
{
dst[0] = (uint8_t)(x >> 0);
dst[1] = (uint8_t)(x >> 8);
dst[2] = (uint8_t)(x >> 16);
dst[3] = (uint8_t)(x >> 24);
dst[4] = (uint8_t)(x >> 32);
dst[5] = (uint8_t)(x >> 40);
dst[6] = (uint8_t)(x >> 48);
dst[7] = (uint8_t)(x >> 56);
}
Wir müssen auch effizient Bytes in den Stream schreiben. Natürlich können Sie 8-Bit-Aufnahmen wiederholt ausführen, aber die Verwendung ist viel schneller memcpy
:
static inline bool ostream_write_bytes_aligned(ostream_t *os,
const uint8_t *src,
size_t n)
{
if (os->bitpos_end - round_up(os->bitpos, 8) < n * 8) {
return false;
}
os->bitpos = round_up(os->bitpos, 8);
memcpy(&os->dst[os->bitpos / 8], src, n);
os->bitpos += n * 8;
return true;
}
Auspacken (Inflation)
Da der Komprimierungsalgorithmus als Entleeren bezeichnet wird - Blasen, Luft aus etwas extrahieren - wird der Entpackungsprozess manchmal als Inflation bezeichnet . Wenn Sie diesen Prozess zum ersten Mal studieren, werden wir verstehen, wie das Format funktioniert. Sie können den Code im ersten Teil von deflate.h und deflate.c , bits.h , tables.h und tables.c sehen (generiert mit generate_tables.c ).Mit Deflate komprimierte Daten werden als eine Reihe von Blöcken gespeichert .. Jeder Block beginnt mit einem 3-Bit-Header, in dem das erste (niedrigstwertige) Bit gesetzt wird, wenn dies der letzte Block der Reihe ist, und die anderen beiden Bits geben seinen Typ an.Es gibt drei Arten von Blöcken: unkomprimiert (0), komprimiert mit festen Huffman-Codes (1) und komprimiert mit „dynamischen“ Huffman-Codes (2).Dieser Code führt das Entpacken mit Hilfsfunktionen für verschiedene Arten von Blöcken durch, die wir später implementieren werden:typedef enum {
HWINF_OK,
HWINF_FULL,
HWINF_ERR
} inf_stat_t;
inf_stat_t hwinflate(const uint8_t *src, size_t src_len, size_t *src_used,
uint8_t *dst, size_t dst_cap, size_t *dst_used)
{
istream_t is;
size_t dst_pos;
uint64_t bits;
bool bfinal;
inf_stat_t s;
istream_init(&is, src, src_len);
dst_pos = 0;
do {
bits = istream_bits(&is);
if (!istream_advance(&is, 3)) {
return HWINF_ERR;
}
bfinal = bits & 1;
bits >>= 1;
switch (lsb(bits, 2)) {
case 0:
s = inf_noncomp_block(&is, dst, dst_cap, &dst_pos);
break;
case 1:
s = inf_fixed_block(&is, dst, dst_cap, &dst_pos);
break;
case 2:
s = inf_dyn_block(&is, dst, dst_cap, &dst_pos);
break;
default:
return HWINF_ERR;
}
if (s != HWINF_OK) {
return s;
}
} while (!bfinal);
*src_used = (size_t)(istream_byte_align(&is) - src);
assert(dst_pos <= dst_cap);
*dst_used = dst_pos;
return HWINF_OK;
}
Unkomprimierte Entleerungsblöcke
Dies sind "gespeicherte" Blöcke, der einfachste Typ. Es beginnt mit der nächsten 8-Bit-Grenze des Bitstroms mit einem 16-Bit-Wort (len), das die Länge des Blocks angibt. Dahinter befindet sich ein weiteres 16-Bit-Wort (nlen), das die Wörter len ergänzt (die Reihenfolge der Bits ist invertiert). Es wird angenommen, dass nlen als einfache len-Prüfsumme fungiert: Wenn die Datei beschädigt ist, ergänzen sich die Werte wahrscheinlich nicht und das Programm kann einen Fehler erkennen.Nach len und nlen sind unkomprimierte Daten. Da die Blocklänge ein 16-Bit-Wert ist, ist die Datengröße auf 65.535 Byte begrenzt.static inf_stat_t inf_noncomp_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
const uint8_t *p;
uint16_t len, nlen;
p = istream_byte_align(is);
if (!istream_advance(is, 32)) {
return HWINF_ERR;
}
len = read16le(p);
nlen = read16le(p + 2);
p += 4;
if (nlen != (uint16_t)~len) {
return HWINF_ERR;
}
if (!istream_advance(is, len * 8)) {
return HWINF_ERR;
}
if (dst_cap - *dst_pos < len) {
return HWINF_FULL;
}
memcpy(&dst[*dst_pos], p, len);
*dst_pos += len;
return HWINF_OK;
}
Blöcke mit festen Huffman-Codes entleeren
Komprimierte Deflate-Blöcke verwenden Huffman-Code, um eine Folge von LZ77-Literalen darzustellen. Backlinks werden mithilfe von Blockendmarkierungen unterbrochen. Für Literale, Backlink-Längen und Markierungen wird der litlen Huffman-Code verwendet . Und für Backlink-Entfernungen wird Dist- Code verwendet .Litlen codiert Werte im Bereich von 0 bis 285. Die Werte 0-255 werden für Literalbytes verwendet, 256 ist die Blockende-Markierung und 257-285 werden für Backlink-Längen verwendet.Backlinks sind 3-258 Bytes lang. Der Litlen-Wert bestimmt die Basislänge, zu der null oder mehr zusätzliche Bits aus dem Stream hinzugefügt werden , um die volle Länge gemäß der folgenden Tabelle zu erhalten. Zum Beispiel bedeutet ein kleiner Wert von 269 eine Basislänge von 19 und zwei zusätzliche Bits. Das Hinzufügen von zwei Bits aus dem Stream ergibt die endgültige Länge von 19 bis 22.Es ist zu beachten, dass ein Litlen-Wert von 284 plus 5 zusätzliche Bits Längen von 227 bis 258 darstellen kann. Die Spezifikation besagt jedoch, dass die Länge 258 - die maximale Länge des Backlinks - unter Verwendung eines separaten Litlen-Werts dargestellt werden muss. Dies soll die Codierung in Situationen reduzieren, in denen häufig die maximale Länge erreicht wird.Der Dekomprimierer verwendet die Tabelle, um die Basislänge und zusätzliche Bits aus dem Litlen-Wert (minus 257) zu erhalten:
struct litlen_tbl_t {
uint16_t base_len : 9;
uint16_t ebits : 7;
};
const struct litlen_tbl_t litlen_tbl[29] = {
{ 3, 0 },
{ 4, 0 },
...
{ 227, 5 },
{ 258, 0 }
};
Huffmans fester Litlen-Code ist kanonisch und verwendet die folgenden Codewortlängen (286–287 sind keine gültigen Litlen-Werte, sie sind jedoch an der Codegenerierung beteiligt):Der Dekompressor speichert diese Längen in einer Tabelle, die für die Übertragung an huffman_decoder_init
:const uint8_t fixed_litlen_lengths[288] = {
8,
8,
...
8,
};
Die Backlink-Abstände variieren von 1 bis 32.768. Sie werden unter Verwendung eines Schemas codiert, das einem Längencodierungsschema ähnlich ist. Der Huffman-Code dist codiert Werte von 0 bis 29, von denen jeder der Basislänge entspricht, zu der zusätzliche Bits hinzugefügt werden, um den endgültigen Abstand zu erhalten:Huffmans fester Code dist ist kanonisch. Alle Codewörter sind 5 Bit lang. Es ist einfach, der Dekomprimierer speichert die Codes in einer Tabelle, die verwendet werden kann huffman_decoder_init
(dist-Werte 30–31 sind nicht korrekt. Es wird angezeigt, dass sie an der Generierung von Huffman-Codes beteiligt sind, aber tatsächlich keine Auswirkung haben):const uint8_t fixed_dist_lengths[32] = {
5,
5,
...
5,
};
Dekomprimierungs- oder Entpackungscode - Block mit festen Huffman-Codes entleeren:static inf_stat_t inf_fixed_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
huffman_decoder_t litlen_dec, dist_dec;
huffman_decoder_init(&litlen_dec, fixed_litlen_lengths,
sizeof(fixed_litlen_lengths) /
sizeof(fixed_litlen_lengths[0]));
huffman_decoder_init(&dist_dec, fixed_dist_lengths,
sizeof(fixed_dist_lengths) /
sizeof(fixed_dist_lengths[0]));
return inf_block(is, dst, dst_cap, dst_pos, &litlen_dec, &dist_dec);
}
#define LITLEN_EOB 256
#define LITLEN_MAX 285
#define LITLEN_TBL_OFFSET 257
#define MIN_LEN 3
#define MAX_LEN 258
#define DISTSYM_MAX 29
#define MIN_DISTANCE 1
#define MAX_DISTANCE 32768
static inf_stat_t inf_block(istream_t *is, uint8_t *dst, size_t dst_cap,
size_t *dst_pos,
const huffman_decoder_t *litlen_dec,
const huffman_decoder_t *dist_dec)
{
uint64_t bits;
size_t used, used_tot, dist, len;
int litlen, distsym;
uint16_t ebits;
while (true) {
bits = istream_bits(is);
litlen = huffman_decode(litlen_dec, (uint16_t)bits, &used);
bits >>= used;
used_tot = used;
if (litlen < 0 || litlen > LITLEN_MAX) {
return HWINF_ERR;
} else if (litlen <= UINT8_MAX) {
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
if (*dst_pos == dst_cap) {
return HWINF_FULL;
}
lz77_output_lit(dst, (*dst_pos)++, (uint8_t)litlen);
continue;
} else if (litlen == LITLEN_EOB) {
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
return HWINF_OK;
}
assert(litlen >= LITLEN_TBL_OFFSET && litlen <= LITLEN_MAX);
len = litlen_tbl[litlen - LITLEN_TBL_OFFSET].base_len;
ebits = litlen_tbl[litlen - LITLEN_TBL_OFFSET].ebits;
if (ebits != 0) {
len += lsb(bits, ebits);
bits >>= ebits;
used_tot += ebits;
}
assert(len >= MIN_LEN && len <= MAX_LEN);
distsym = huffman_decode(dist_dec, (uint16_t)bits, &used);
bits >>= used;
used_tot += used;
if (distsym < 0 || distsym > DISTSYM_MAX) {
return HWINF_ERR;
}
dist = dist_tbl[distsym].base_dist;
ebits = dist_tbl[distsym].ebits;
if (ebits != 0) {
dist += lsb(bits, ebits);
bits >>= ebits;
used_tot += ebits;
}
assert(dist >= MIN_DISTANCE && dist <= MAX_DISTANCE);
assert(used_tot <= ISTREAM_MIN_BITS);
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
if (dist > *dst_pos) {
return HWINF_ERR;
}
if (round_up(len, 8) <= dst_cap - *dst_pos) {
output_backref64(dst, *dst_pos, dist, len);
} else if (len <= dst_cap - *dst_pos) {
lz77_output_backref(dst, *dst_pos, dist, len);
} else {
return HWINF_FULL;
}
(*dst_pos) += len;
}
}
Beachten Sie diese Optimierung: Wenn im ausgehenden Puffer nicht genügend Speicherplatz vorhanden ist, geben wir Backlinks mit der folgenden Funktion aus, die jeweils 64 Bit kopiert. Dies ist in dem Sinne „chaotisch“, dass häufig einige zusätzliche Bytes kopiert werden (bis zum nächsten Vielfachen von 8). Es funktioniert jedoch viel schneller lz77_output_backref
, da weniger zyklische Iterationen und Speicherzugriffe erforderlich sind. Tatsächlich werden kurze Backlinks jetzt in einer Iteration verarbeitet, was sehr gut für die Vorhersage von Verzweigungen geeignet ist.
static void output_backref64(uint8_t *dst, size_t dst_pos, size_t dist,
size_t len)
{
size_t i;
uint64_t tmp;
assert(len > 0);
assert(dist <= dst_pos && "cannot reference before beginning of dst");
if (len > dist) {
lz77_output_backref(dst, dst_pos, dist, len);
return;
}
i = 0;
do {
memcpy(&tmp, &dst[dst_pos - dist + i], 8);
memcpy(&dst[dst_pos + i], &tmp, 8);
i += 8;
} while (i < len);
}
Blöcke mit dynamischen Huffman-Codes entleeren
Das Entleeren von Blöcken mit dynamischen Huffman-Codes funktioniert auf die gleiche Weise wie oben beschrieben. Anstelle der vordefinierten Codes für litlen und dist verwenden sie jedoch die Codes, die am Anfang des Blocks im Deflate-Stream selbst gespeichert sind. Der Name ist wahrscheinlich nicht erfolgreich, da dynamische Huffman-Codes auch als Codes bezeichnet werden, die sich während der Codierung ändern - dies ist eine adaptive Huffman-Codierung . Die hier beschriebenen Codes haben nichts mit diesem Verfahren zu tun. Sie sind nur in dem Sinne dynamisch, dass unterschiedliche Blöcke unterschiedliche Codes verwenden können.Das Generieren dynamischer Litlen- und Dist-Codes ist der schwierigste Teil des Deflate-Formats. Aber sobald die Codes erzeugt werden, Dekompression wird auf die gleiche Weise wie im vorherigen Teil beschrieben, unter Verwendung von inf_block
:static inf_stat_t inf_dyn_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
inf_stat_t s;
huffman_decoder_t litlen_dec, dist_dec;
s = init_dyn_decoders(is, &litlen_dec, &dist_dec);
if (s != HWINF_OK) {
return s;
}
return inf_block(is, dst, dst_cap, dst_pos, &litlen_dec, &dist_dec);
}
Litlen- und Dist-Codes für dynamische Deflate-Blöcke werden als eine Reihe von Codewortlängen gespeichert. Die Längen selbst werden mit dem dritten Huffman-Code codelen codiert . Dieser Code wird durch die Länge der Codewörter ( codelen_lens
) bestimmt, die im Block gespeichert sind (habe ich erwähnt, dass es schwierig ist?).Am Anfang des dynamischen Blocks befinden sich 14 Bits, die die Anzahl der Litlen-, Dist- und Codelen-Längen von Codewörtern bestimmen, die aus dem Block gelesen werden müssen:#define MIN_CODELEN_LENS 4
#define MAX_CODELEN_LENS 19
#define MIN_LITLEN_LENS 257
#define MAX_LITLEN_LENS 288
#define MIN_DIST_LENS 1
#define MAX_DIST_LENS 32
#define CODELEN_MAX_LIT 15
#define CODELEN_COPY 16
#define CODELEN_COPY_MIN 3
#define CODELEN_COPY_MAX 6
#define CODELEN_ZEROS 17
#define CODELEN_ZEROS_MIN 3
#define CODELEN_ZEROS_MAX 10
#define CODELEN_ZEROS2 18
#define CODELEN_ZEROS2_MIN 11
#define CODELEN_ZEROS2_MAX 138
static const int codelen_lengths_order[MAX_CODELEN_LENS] =
{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
static inf_stat_t init_dyn_decoders(istream_t *is,
huffman_decoder_t *litlen_dec,
huffman_decoder_t *dist_dec)
{
uint64_t bits;
size_t num_litlen_lens, num_dist_lens, num_codelen_lens;
uint8_t codelen_lengths[MAX_CODELEN_LENS];
uint8_t code_lengths[MAX_LITLEN_LENS + MAX_DIST_LENS];
size_t i, n, used;
int sym;
huffman_decoder_t codelen_dec;
bits = istream_bits(is);
num_litlen_lens = lsb(bits, 5) + MIN_LITLEN_LENS;
bits >>= 5;
assert(num_litlen_lens <= MAX_LITLEN_LENS);
num_dist_lens = lsb(bits, 5) + MIN_DIST_LENS;
bits >>= 5;
assert(num_dist_lens <= MAX_DIST_LENS);
num_codelen_lens = lsb(bits, 4) + MIN_CODELEN_LENS;
bits >>= 4;
assert(num_codelen_lens <= MAX_CODELEN_LENS);
if (!istream_advance(is, 5 + 5 + 4)) {
return HWINF_ERR;
}
Dann kommen die Codewortlängen für den Codelen-Code. Diese Längen sind die üblichen Drei-Bit-Werte, werden jedoch in der in angegebenen speziellen Reihenfolge geschrieben codelen_lengths_order
. Da 19 Längen bestimmt werden müssen, wird nur der Stream gelesen num_codelen_lens
. alles andere ist implizit null. Die Längen werden in einer bestimmten Reihenfolge aufgelistet, sodass die Längen von Null eher am Ende der Liste liegen und nicht im Block gespeichert werden.
for (i = 0; i < num_codelen_lens; i++) {
bits = istream_bits(is);
codelen_lengths[codelen_lengths_order[i]] =
(uint8_t)lsb(bits, 3);
if (!istream_advance(is, 3)) {
return HWINF_ERR;
}
}
for (; i < MAX_CODELEN_LENS; i++) {
codelen_lengths[codelen_lengths_order[i]] = 0;
}
if (!huffman_decoder_init(&codelen_dec, codelen_lengths,
MAX_CODELEN_LENS)) {
return HWINF_ERR;
}
Durch Einstellen des Codelen-Decoders können wir die Länge der Codewörter litlen und dist vom Stream lesen.
i = 0;
while (i < num_litlen_lens + num_dist_lens) {
bits = istream_bits(is);
sym = huffman_decode(&codelen_dec, (uint16_t)bits, &used);
bits >>= used;
if (!istream_advance(is, used)) {
return HWINF_ERR;
}
if (sym >= 0 && sym <= CODELEN_MAX_LIT) {
code_lengths[i++] = (uint8_t)sym;
}
16, 17 und 18 sind keine reellen Längen, sondern Indikatoren dafür, dass die vorherige Länge mehrmals wiederholt werden muss oder dass Sie die Länge Null wiederholen müssen: else if (sym == CODELEN_COPY) {
if (i < 1) {
return HWINF_ERR;
}
n = lsb(bits, 2) + CODELEN_COPY_MIN;
if (!istream_advance(is, 2)) {
return HWINF_ERR;
}
assert(n >= CODELEN_COPY_MIN && n <= CODELEN_COPY_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i] = code_lengths[i - 1];
i++;
}
} else if (sym == CODELEN_ZEROS) {
n = lsb(bits, 3) + CODELEN_ZEROS_MIN;
if (!istream_advance(is, 3)) {
return HWINF_ERR;
}
assert(n >= CODELEN_ZEROS_MIN &&
n <= CODELEN_ZEROS_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i++] = 0;
}
} else if (sym == CODELEN_ZEROS2) {
n = lsb(bits, 7) + CODELEN_ZEROS2_MIN;
if (!istream_advance(is, 7)) {
return HWINF_ERR;
}
assert(n >= CODELEN_ZEROS2_MIN &&
n <= CODELEN_ZEROS2_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i++] = 0;
}
} else {
return HWINF_ERR;
}
}
Beachten Sie, dass Litlen- und Dist-Längen einzeln in das Array eingelesen werden code_lengths
. Sie können nicht separat gelesen werden, da Codelängenläufe von den letzten kleinen Längen auf die ersten dist Längen übertragen werden können.Nachdem wir die Codewortlängen vorbereitet haben, können wir Huffman-Decoder konfigurieren und zur Aufgabe des Decodierens von Literalen und Backlinks zurückkehren: if (!huffman_decoder_init(litlen_dec, &code_lengths[0],
num_litlen_lens)) {
return HWINF_ERR;
}
if (!huffman_decoder_init(dist_dec, &code_lengths[num_litlen_lens],
num_dist_lens)) {
return HWINF_ERR;
}
return HWINF_OK;
}
Kompression (Deflation)
In den vorherigen Teilen haben wir alle für die Deflate-Komprimierung erforderlichen Tools erstellt: Lempel-Ziv, Huffman-Codierung, Bitströme und eine Beschreibung der drei Arten von Deflate-Blöcken. Und in diesem Teil werden wir alles zusammenfügen, um die Deflate-Komprimierung zu erreichen.Komprimierung Lempel-Ziv analysiert die Quelldaten in eine Folge von Backlinks und Literalen. Diese Sequenz muss wie im vorherigen Teil beschrieben in Deflate-Blöcke unterteilt und codiert werden. Die Auswahl einer Partitionierungsmethode wird häufig als Blockierung bezeichnet.. Einerseits bedeutet jeder neue Block eine Art Overhead, dessen Volumen von der Art des Blocks und seinem Inhalt abhängt. Weniger Blöcke - weniger Aufwand. Andererseits können sich diese Kosten für die Erstellung eines neuen Blocks auszahlen. Zum Beispiel, wenn die Eigenschaften der Daten es Ihnen ermöglichen, die Huffman-Codierung effizienter durchzuführen und die Gesamtmenge der generierten Daten zu reduzieren.Das Blockieren ist eine schwierige Optimierungsaufgabe. Einige Kompressoren (zum Beispiel Zopfli ) versuchen es besser als andere, aber die meisten verwenden einfach den gierigen Ansatz: Sie geben Blöcke aus, sobald sie eine bestimmte Größe erreichen.Verschiedene Arten von Blöcken haben ihre eigenen Größenbeschränkungen:- Nicht komprimierte Blöcke dürfen nicht mehr als 65.535 Byte enthalten.
- Huffman-Festcodes haben keine maximale Größe.
- Dynamische Huffman-Codes haben im Allgemeinen keine maximale Größe, aber da unsere Implementierung des Huffman-Algorithmus 16-Bit-Zeichenfolgen verwendet, sind wir auf 65.535 Zeichen beschränkt.
Um Blöcke jeglichen Typs frei zu verwenden, beschränken Sie ihre Größe auf 65.534 Bytes:
#define MAX_BLOCK_LEN_BYTES 65534
Um den ausgehenden Bitstrom und den Inhalt des aktuellen Blocks während der Komprimierung zu verfolgen, verwenden wir die folgende Struktur:typedef struct deflate_state_t deflate_state_t;
struct deflate_state_t {
ostream_t os;
const uint8_t *block_src;
size_t block_len;
size_t block_len_bytes;
uint16_t litlen_freqs[LITLEN_MAX + 1];
uint16_t dist_freqs[DISTSYM_MAX + 1];
struct {
uint16_t distance;
union {
uint16_t lit;
uint16_t len;
} u;
} block[MAX_BLOCK_LEN_BYTES + 1];
};
static void reset_block(deflate_state_t *s)
{
s->block_len = 0;
s->block_len_bytes = 0;
memset(s->litlen_freqs, 0, sizeof(s->litlen_freqs));
memset(s->dist_freqs, 0, sizeof(s->dist_freqs));
}
Um dem Block Arbeitsergebnisse hinzuzufügen, verwenden lz77_compress
wir die Rückruffunktionen, und wenn die maximale Größe erreicht ist, schreiben wir den Block in den Bitstrom:static bool lit_callback(uint8_t lit, void *aux)
{
deflate_state_t *s = aux;
if (s->block_len_bytes + 1 > MAX_BLOCK_LEN_BYTES) {
if (!write_block(s, false)) {
return false;
}
s->block_src += s->block_len_bytes;
reset_block(s);
}
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
s->block[s->block_len ].distance = 0;
s->block[s->block_len++].u.lit = lit;
s->block_len_bytes++;
s->litlen_freqs[lit]++;
return true;
}
static bool backref_callback(size_t dist, size_t len, void *aux)
{
deflate_state_t *s = aux;
if (s->block_len_bytes + len > MAX_BLOCK_LEN_BYTES) {
if (!write_block(s, false)) {
return false;
}
s->block_src += s->block_len_bytes;
reset_block(s);
}
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
s->block[s->block_len ].distance = (uint16_t)dist;
s->block[s->block_len++].u.len = (uint16_t)len;
s->block_len_bytes += len;
assert(len >= MIN_LEN && len <= MAX_LEN);
assert(dist >= MIN_DISTANCE && dist <= MAX_DISTANCE);
s->litlen_freqs[len2litlen[len]]++;
s->dist_freqs[distance2dist[dist]]++;
return true;
}
Das Interessanteste ist die Aufnahme von Blöcken. Wenn der Block nicht komprimiert ist, ist alles einfach:static bool write_uncomp_block(deflate_state_t *s, bool final)
{
uint8_t len_nlen[4];
if (!ostream_write(&s->os, (0x0 << 1) | final, 3)) {
return false;
}
len_nlen[0] = (uint8_t)(s->block_len_bytes >> 0);
len_nlen[1] = (uint8_t)(s->block_len_bytes >> 8);
len_nlen[2] = ~len_nlen[0];
len_nlen[3] = ~len_nlen[1];
if (!ostream_write_bytes_aligned(&s->os, len_nlen, sizeof(len_nlen))) {
return false;
}
if (!ostream_write_bytes_aligned(&s->os, s->block_src,
s->block_len_bytes)) {
return false;
}
return true;
}
Um einen statischen Huffman-Block zu schreiben, generieren wir zuerst kanonische Codes basierend auf festen Codewortlängen für Litlen- und Dist-Codes. Dann iterieren wir den Block und schreiben die Zeichen auf, die diese Codes verwenden:static bool write_static_block(deflate_state_t *s, bool final)
{
huffman_encoder_t litlen_enc, dist_enc;
if (!ostream_write(&s->os, (0x1 << 1) | final, 3)) {
return false;
}
huffman_encoder_init2(&litlen_enc, fixed_litlen_lengths,
sizeof(fixed_litlen_lengths) /
sizeof(fixed_litlen_lengths[0]));
huffman_encoder_init2(&dist_enc, fixed_dist_lengths,
sizeof(fixed_dist_lengths) /
sizeof(fixed_dist_lengths[0]));
return write_huffman_block(s, &litlen_enc, &dist_enc);
}
static bool write_huffman_block(deflate_state_t *s,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t i, nbits;
uint64_t distance, dist, len, litlen, bits, ebits;
for (i = 0; i < s->block_len; i++) {
if (s->block[i].distance == 0) {
litlen = s->block[i].u.lit;
assert(litlen <= LITLEN_EOB);
if (!ostream_write(&s->os,
litlen_enc->codewords[litlen],
litlen_enc->lengths[litlen])) {
return false;
}
continue;
}
len = s->block[i].u.len;
litlen = len2litlen[len];
bits = litlen_enc->codewords[litlen];
nbits = litlen_enc->lengths[litlen];
ebits = len - litlen_tbl[litlen - LITLEN_TBL_OFFSET].base_len;
bits |= ebits << nbits;
nbits += litlen_tbl[litlen - LITLEN_TBL_OFFSET].ebits;
distance = s->block[i].distance;
dist = distance2dist[distance];
bits |= (uint64_t)dist_enc->codewords[dist] << nbits;
nbits += dist_enc->lengths[dist];
ebits = distance - dist_tbl[dist].base_dist;
bits |= ebits << nbits;
nbits += dist_tbl[dist].ebits;
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
}
return true;
}
Das Schreiben von dynamischen Huffman-Blöcken ist natürlich schwieriger, da sie eine schwierige Codierung von Litlen- und Dist-Codes enthalten. Um diese Codierung darzustellen, verwenden wir die folgende Struktur:typedef struct codelen_sym_t codelen_sym_t;
struct codelen_sym_t {
uint8_t sym;
uint8_t count;
};
Zuerst verwerfen wir das Ende ihrer Nulllängen der Codewörter litlen und dist und kopieren sie dann zur nachfolgenden Codierung in ein reguläres Array. Wir können nicht alle Nullen verwerfen: Es ist unmöglich, einen Deflate-Block zu codieren, wenn kein einziger dist-Code darin enthalten ist. Es ist auch unmöglich, weniger als 257 Litlen-Codes zu haben, aber da wir immer eine Byte-Endmarkierung haben, gibt es für ein Zeichen von 256 immer eine Codelänge ungleich Null.
static size_t encode_dist_litlen_lens(const uint8_t *litlen_lens,
const uint8_t *dist_lens,
codelen_sym_t *encoded,
size_t *num_litlen_lens,
size_t *num_dist_lens)
{
size_t i, n;
uint8_t lens[LITLEN_MAX + 1 + DISTSYM_MAX + 1];
*num_litlen_lens = LITLEN_MAX + 1;
*num_dist_lens = DISTSYM_MAX + 1;
assert(litlen_lens[LITLEN_EOB] != 0 && "EOB len should be non-zero.");
while (litlen_lens[*num_litlen_lens - 1] == 0) {
(*num_litlen_lens)--;
}
assert(*num_litlen_lens >= MIN_LITLEN_LENS);
while (dist_lens[*num_dist_lens - 1] == 0 && *num_dist_lens > 1) {
(*num_dist_lens)--;
}
assert(*num_dist_lens >= MIN_DIST_LENS);
n = 0;
for (i = 0; i < *num_litlen_lens; i++) {
lens[n++] = litlen_lens[i];
}
for (i = 0; i < *num_dist_lens; i++) {
lens[n++] = dist_lens[i];
}
return encode_lens(lens, n, encoded);
}
Nachdem wir die Codelängen zu einem Array hinzugefügt haben, führen wir die Codierung mit Sonderzeichen durch, um dieselben Codelängen auszuführen.
static size_t encode_lens(const uint8_t *lens, size_t n, codelen_sym_t *encoded)
{
size_t i, j, num_encoded;
uint8_t count;
i = 0;
num_encoded = 0;
while (i < n) {
if (lens[i] == 0) {
for (j = i; j < min(n, i + CODELEN_ZEROS2_MAX) &&
lens[j] == 0; j++);
count = (uint8_t)(j - i);
if (count < CODELEN_ZEROS_MIN) {
encoded[num_encoded++].sym = 0;
i++;
continue;
}
if (count <= CODELEN_ZEROS_MAX) {
assert(count >= CODELEN_ZEROS_MIN &&
count <= CODELEN_ZEROS_MAX);
encoded[num_encoded].sym = CODELEN_ZEROS;
encoded[num_encoded++].count = count;
} else {
assert(count >= CODELEN_ZEROS2_MIN &&
count <= CODELEN_ZEROS2_MAX);
encoded[num_encoded].sym = CODELEN_ZEROS2;
encoded[num_encoded++].count = count;
}
i = j;
continue;
}
encoded[num_encoded++].sym = lens[i++];
for (j = i; j < min(n, i + CODELEN_COPY_MAX) &&
lens[j] == lens[i - 1]; j++);
count = (uint8_t)(j - i);
if (count >= CODELEN_COPY_MIN) {
assert(count >= CODELEN_COPY_MIN &&
count <= CODELEN_COPY_MAX);
encoded[num_encoded].sym = CODELEN_COPY;
encoded[num_encoded++].count = count;
i = j;
continue;
}
}
return num_encoded;
}
Die für die Codierung verwendeten Zeichen werden mit dem Huffman-Code codelen aufgezeichnet. Die Längen der Codewörter aus dem Codelen-Code werden in einer bestimmten Reihenfolge in den Block geschrieben, sodass es wahrscheinlicher ist, dass am Ende keine Längen von Null enden. Hier ist eine Funktion, die berechnet, wie viele Längen geschrieben werden sollen:static const int codelen_lengths_order[19] =
{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
size_t count_codelen_lens(const uint8_t *codelen_lens)
{
size_t n = MAX_CODELEN_LENS;
while (codelen_lens[codelen_lengths_order[n - 1]] == 0) {
n--;
}
assert(n >= MIN_CODELEN_LENS && n <= MAX_CODELEN_LENS);
return n;
}
Angenommen, wir haben bereits die Codes litlen und dist festgelegt, die Codierung der Längen ihrer Codewörter und den Code für diese Längen festgelegt. Jetzt können wir einen dynamischen Huffman-Block schreiben:static bool write_dynamic_block(deflate_state_t *s, bool final,
size_t num_litlen_lens, size_t num_dist_lens,
size_t num_codelen_lens,
const huffman_encoder_t *codelen_enc,
const codelen_sym_t *encoded_lens,
size_t num_encoded_lens,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t i;
uint8_t codelen, sym;
size_t nbits;
uint64_t bits, hlit, hdist, hclen, count;
bits = (0x2 << 1) | final;
nbits = 3;
hlit = num_litlen_lens - MIN_LITLEN_LENS;
bits |= hlit << nbits;
nbits += 5;
hdist = num_dist_lens - MIN_DIST_LENS;
bits |= hdist << nbits;
nbits += 5;
hclen = num_codelen_lens - MIN_CODELEN_LENS;
bits |= hclen << nbits;
nbits += 4;
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
for (i = 0; i < num_codelen_lens; i++) {
codelen = codelen_enc->lengths[codelen_lengths_order[i]];
if (!ostream_write(&s->os, codelen, 3)) {
return false;
}
}
for (i = 0; i < num_encoded_lens; i++) {
sym = encoded_lens[i].sym;
bits = codelen_enc->codewords[sym];
nbits = codelen_enc->lengths[sym];
count = encoded_lens[i].count;
if (sym == CODELEN_COPY) {
bits |= (count - CODELEN_COPY_MIN) << nbits;
nbits += 2;
} else if (sym == CODELEN_ZEROS) {
bits |= (count - CODELEN_ZEROS_MIN) << nbits;
nbits += 3;
} else if (sym == CODELEN_ZEROS2) {
bits |= (count - CODELEN_ZEROS2_MIN) << nbits;
nbits += 7;
}
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
}
return write_huffman_block(s, litlen_enc, dist_enc);
}
Für jeden Block möchten wir den Typ verwenden, der die geringste Anzahl von Bits erfordert. Die Länge eines unkomprimierten Blocks kann schnell berechnet werden:
static size_t uncomp_block_len(const deflate_state_t *s)
{
size_t bit_pos, padding;
bit_pos = ostream_bit_pos(&s->os) + 3;
padding = round_up(bit_pos, 8) - bit_pos;
return 3 + padding + 2 * 16 + s->block_len_bytes * 8;
}
Für Huffman-codierte Blöcke können Sie die Körperlänge anhand der Litlen- und Dist-Frequenzen von Zeichen und Codewortlängen berechnen:
static size_t huffman_block_body_len(const deflate_state_t *s,
const uint8_t *litlen_lens,
const uint8_t *dist_lens)
{
size_t i, freq, len;
len = 0;
for (i = 0; i <= LITLEN_MAX; i++) {
freq = s->litlen_freqs[i];
len += litlen_lens[i] * freq;
if (i >= LITLEN_TBL_OFFSET) {
len += litlen_tbl[i - LITLEN_TBL_OFFSET].ebits * freq;
}
}
for (i = 0; i <= DISTSYM_MAX; i++) {
freq = s->dist_freqs[i];
len += dist_lens[i] * freq;
len += dist_tbl[i].ebits * freq;
}
return len;
}
Die Gesamtlänge des statischen Blocks beträgt 3 Bits des Headers plus der Länge des Körpers. Das Berechnen der Headergröße eines dynamischen Blocks erfordert viel mehr Arbeit:
static size_t dyn_block_len(const deflate_state_t *s, size_t num_codelen_lens,
const uint16_t *codelen_freqs,
const huffman_encoder_t *codelen_enc,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t len, i, freq;
len = 3;
len += 5 + 5 + 4;
len += 3 * num_codelen_lens;
for (i = 0; i < MAX_CODELEN_LENS; i++) {
freq = codelen_freqs[i];
len += codelen_enc->lengths[i] * freq;
if (i == CODELEN_COPY) {
len += 2 * freq;
} else if (i == CODELEN_ZEROS) {
len += 3 * freq;
} else if (i == CODELEN_ZEROS2) {
len += 7 * freq;
}
}
return len + huffman_block_body_len(s, litlen_enc->lengths,
dist_enc->lengths);
}
Jetzt werden wir alles zusammenfügen und die Hauptfunktion zum Schreiben von Blöcken erstellen:
static bool write_block(deflate_state_t *s, bool final)
{
size_t old_bit_pos, uncomp_len, static_len, dynamic_len;
huffman_encoder_t dyn_litlen_enc, dyn_dist_enc, codelen_enc;
size_t num_encoded_lens, num_litlen_lens, num_dist_lens;
codelen_sym_t encoded_lens[LITLEN_MAX + 1 + DISTSYM_MAX + 1];
uint16_t codelen_freqs[MAX_CODELEN_LENS] = {0};
size_t num_codelen_lens;
size_t i;
old_bit_pos = ostream_bit_pos(&s->os);
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
assert(s->litlen_freqs[LITLEN_EOB] == 0);
s->block[s->block_len ].distance = 0;
s->block[s->block_len++].u.lit = LITLEN_EOB;
s->litlen_freqs[LITLEN_EOB] = 1;
uncomp_len = uncomp_block_len(s);
static_len = 3 + huffman_block_body_len(s, fixed_litlen_lengths,
fixed_dist_lengths);
huffman_encoder_init(&dyn_litlen_enc, s->litlen_freqs,
LITLEN_MAX + 1, 15);
huffman_encoder_init(&dyn_dist_enc, s->dist_freqs, DISTSYM_MAX + 1, 15);
num_encoded_lens = encode_dist_litlen_lens(dyn_litlen_enc.lengths,
dyn_dist_enc.lengths,
encoded_lens,
&num_litlen_lens,
&num_dist_lens);
for (i = 0; i < num_encoded_lens; i++) {
codelen_freqs[encoded_lens[i].sym]++;
}
huffman_encoder_init(&codelen_enc, codelen_freqs, MAX_CODELEN_LENS, 7);
num_codelen_lens = count_codelen_lens(codelen_enc.lengths);
dynamic_len = dyn_block_len(s, num_codelen_lens, codelen_freqs,
&codelen_enc, &dyn_litlen_enc,
&dyn_dist_enc);
if (uncomp_len <= dynamic_len && uncomp_len <= static_len) {
if (!write_uncomp_block(s, final)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == uncomp_len);
} else if (static_len <= dynamic_len) {
if (!write_static_block(s, final)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == static_len);
} else {
if (!write_dynamic_block(s, final, num_litlen_lens,
num_dist_lens, num_codelen_lens,
&codelen_enc, encoded_lens,
num_encoded_lens, &dyn_litlen_enc,
&dyn_dist_enc)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == dynamic_len);
}
return true;
}
Schließlich sollte der Initiator des gesamten Komprimierungsprozesses den Anfangszustand festlegen, die Lempel-Ziv-Komprimierung starten und den resultierenden Block schreiben:
bool hwdeflate(const uint8_t *src, size_t src_len, uint8_t *dst,
size_t dst_cap, size_t *dst_used)
{
deflate_state_t s;
ostream_init(&s.os, dst, dst_cap);
reset_block(&s);
s.block_src = src;
if (!lz77_compress(src, src_len, &lit_callback,
&backref_callback, &s)) {
return false;
}
if (!write_block(&s, true)) {
return false;
}
assert(s.block_src + s.block_len_bytes == src + src_len);
*dst_used = ostream_bytes_written(&s.os);
return true;
}
Zip-Dateiformat
Oben haben wir untersucht, wie die in Zip-Dateien verwendete Deflate-Komprimierung funktioniert. Was ist mit dem Dateiformat selbst? In diesem Teil werden wir die Struktur und Implementierung im Detail untersuchen. Der Code ist in zip.h und zip.c verfügbar .Überblick
Das Dateiformat wird in PKZip Application Note beschrieben :- Jede Datei oder jedes Archivelement in einer Zip-Datei verfügt über einen lokalen Dateikopf mit Metadaten zu dem Element.
- . , , , Zip-.
- , . , . Zip-.
Jedes Archivelement wird komprimiert und einzeln gespeichert. Dies bedeutet, dass selbst wenn Übereinstimmungen zwischen Dateien im Archiv vorhanden sind, diese nicht berücksichtigt werden, um die Komprimierung zu verbessern.Die Position des zentralen Katalogs am Ende ermöglicht es Ihnen, das Archiv schrittweise zu vervollständigen. Wenn Dateielemente komprimiert werden, werden sie dem Archiv hinzugefügt. Der Index wird nach allen komprimierten Größen aufgezeichnet, sodass Sie die Offsets aller Dateien ermitteln können. Das Hinzufügen von Dateien zu einem vorhandenen Archiv ist recht einfach, es wird nach dem letzten Element platziert und das zentrale Verzeichnis wird überschrieben.Die Möglichkeit, Archive schrittweise zu erstellen, war besonders wichtig für die Verbreitung von Informationen auf zahlreichen Disketten oder Volumes. Beim Komprimieren schlug PKZip vor, dass Benutzer neue Disketten einlegen und das zentrale Verzeichnis in die letzten (letzten) schreiben. Um ein Archiv mit mehreren Volumes zu entpacken, forderte PKZip zuerst die letzte zu schreibende Diskette zum Lesen des zentralen Verzeichnisses an und dann den Rest der Diskette, die zum Extrahieren der angeforderten Dateien erforderlich ist.Dies mag Sie überraschen, aber es gab keine Regel, die verbot, mehrere Dateien mit demselben Namen im Archiv zu haben. Dies kann beim Auspacken zu großer Verwirrung führen: Wenn mehrere Dateien mit demselben Namen vorhanden sind, welche sollten Sie auspacken? Dies könnte wiederum zu Sicherheitsproblemen führen. Aufgrund des "Master Key" -Fehlers in Android (CVE-2013-4787 , Folien und Video aus dem Bericht über Black Hat) Ein Angreifer könnte bei der Installation von Programmen die Überprüfungen des Betriebssystems für kryptografische Signaturen umgehen. Android-Programme werden in APK- Dateien verteilt, bei denen es sich um Zip-Dateien handelt. Wenn das APK mehrere Dateien mit demselben Namen enthielt, wählte der Signaturprüfcode die letzte Datei mit demselben Namen aus, und das Installationsprogramm wählte die erste Datei aus, dh die Überprüfung wurde nicht durchgeführt. Mit anderen Worten, dieser kleine Unterschied zwischen den beiden Zip-Bibliotheken ermöglichte es, das gesamte Sicherheitsmodell des Betriebssystems zu umgehen.Im Gegensatz zu den meisten Formaten sollten Zip-Dateien nicht mit einer Signatur oder einer magischen Nummer beginnen. Es wird im Allgemeinen nicht angegeben, dass die Zip-Datei auf eine bestimmte Weise gestartet werden soll. Auf diese Weise können Sie problemlos Dateien erstellen, die sowohl als Zip-Datei als auch als anderes Format gültig sind - Polyglot-Dateien . Beispielsweise sind selbstextrahierende Zip-Archive (z. B. pkz204g.exe ) normalerweise sowohl ausführbare als auch Zip-Dateien: Der erste Teil ist ausführbar, gefolgt von einer Zip-Datei (die vom ausführbaren Teil entpackt wird). Das Betriebssystem kann es als ausführbare Datei ausführen, das Zip-Programm öffnet es jedoch als Zip-Datei. Diese Funktion kann dazu führen, dass Sie am Anfang der Datei keine Signatur benötigen.Obwohl solche polyglotten Dateien intelligent sind, können sie zu Sicherheitsproblemen führen, da sie Programme austricksen können, die versuchen, den Inhalt der Datei zu bestimmen, und auch die Bereitstellung von Schadcode an einem Ort mit Dateien unterschiedlichen Typs ermöglichen. Bei Exploits wurden beispielsweise GIFAR- Dateien verwendet, bei denen es sich gleichzeitig um gültige GIF-Bilder und Java-Archive handelt (JAR, eine Art Zip-Datei). Weitere Informationen zu diesem Problem finden Sie im Artikel Missbrauch von Dateiformaten (ab Seite 18).Wie wir weiter unten sehen werden, verwenden Zip-Dateien 32-Bit-Felder für Offsets und Größen, um die Größe des Archivs und seiner Elemente auf vier Gigabyte zu begrenzen. In Application Note 4.5PKWare hat Formaterweiterungen hinzugefügt, die die Verwendung von 64-Bit-Offsets und -Größen ermöglichen. Dateien, die diese Erweiterungen verwenden, haben das Zip64-Format, werden jedoch nicht berücksichtigt.Datenstrukturen
Ende des zentralen Verzeichniseintrags
Das Ende eines zentralen Verzeichniseintrags (EOCDR) wird normalerweise als Ausgangspunkt für das Lesen einer Zip-Datei verwendet. Es enthält den Speicherort und die Größe des zentralen Verzeichnisses sowie optionale Kommentare zum gesamten Archiv.In Zip-Dateien, die mehrere Disketten oder Volumes belegten, enthielt EOCDR auch Informationen darüber, welche Festplatte wir derzeit verwenden, auf welcher Festplatte das zentrale Verzeichnis startet usw. Heutzutage wird diese Funktionalität nur noch selten verwendet, und der Code in diesem Artikel verarbeitet solche Dateien nicht.EOCDR wird durch die Signatur 'P' 'K' bestimmt, gefolgt von den Bytes 5 und 6. Es folgt die folgende Struktur, die Zahlen werden nach dem Little-Endian-Prinzip gespeichert:
struct eocdr {
uint16_t disk_nbr;
uint16_t cd_start_disk;
uint16_t disk_cd_entries;
uint16_t cd_entries;
uint32_t cd_size;
uint32_t cd_offset;
uint16_t comment_len;
const uint8_t *comment;
};
EOCDR sollte sich am Ende der Datei befinden. Da sich jedoch möglicherweise ein Kommentar mit einer beliebigen Länge von 16 Bit in seinem Schwanz befindet, muss möglicherweise eine bestimmte Position gefunden werden:
#define READ16(p) ((p) += 2, read16le((p) - 2))
#define READ32(p) ((p) += 4, read32le((p) - 4))
#define EOCDR_BASE_SZ 22
#define EOCDR_SIGNATURE 0x06054b50
static bool find_eocdr(struct eocdr *r, const uint8_t *src, size_t src_len)
{
size_t comment_len;
const uint8_t *p;
uint32_t signature;
for (comment_len = 0; comment_len <= UINT16_MAX; comment_len++) {
if (src_len < EOCDR_BASE_SZ + comment_len) {
break;
}
p = &src[src_len - EOCDR_BASE_SZ - comment_len];
signature = READ32(p);
if (signature == EOCDR_SIGNATURE) {
r->disk_nbr = READ16(p);
r->cd_start_disk = READ16(p);
r->disk_cd_entries = READ16(p);
r->cd_entries = READ16(p);
r->cd_size = READ32(p);
r->cd_offset = READ32(p);
r->comment_len = READ16(p);
r->comment = p;
assert(p == &src[src_len - comment_len] &&
"All fields read.");
if (r->comment_len == comment_len) {
return true;
}
}
}
return false;
}
Das Aufzeichnen von EOCDR ist einfach. Diese Funktion schreibt und gibt die Anzahl der geschriebenen Bytes zurück:
#define WRITE16(p, x) (write16le((p), (x)), (p) += 2)
#define WRITE32(p, x) (write32le((p), (x)), (p) += 4)
static size_t write_eocdr(uint8_t *dst, const struct eocdr *r)
{
uint8_t *p = dst;
WRITE32(p, EOCDR_SIGNATURE);
WRITE16(p, r->disk_nbr);
WRITE16(p, r->cd_start_disk);
WRITE16(p, r->disk_cd_entries);
WRITE16(p, r->cd_entries);
WRITE32(p, r->cd_size);
WRITE32(p, r->cd_offset);
WRITE16(p, r->comment_len);
assert(p - dst == EOCDR_BASE_SZ);
if (r->comment_len != 0) {
memcpy(p, r->comment, r->comment_len);
p += r->comment_len;
}
return (size_t)(p - dst);
}
Zentraler Dateikopf
Das zentrale Verzeichnis besteht aus zentralen Dateiköpfen, die nacheinander für jedes Archivelement geschrieben werden. Jede Überschrift beginnt mit der Signatur 'P', 'K', 1, 2, und dann gibt es eine solche Struktur:#define EXT_ATTR_DIR (1U << 4)
#define EXT_ATTR_ARC (1U << 5)
struct cfh {
uint16_t made_by_ver;
uint16_t extract_ver;
uint16_t gp_flag;
uint16_t method;
uint16_t mod_time;
uint16_t mod_date;
uint32_t crc32;
uint32_t comp_size;
uint32_t uncomp_size;
uint16_t name_len;
uint16_t extra_len;
uint16_t comment_len;
uint16_t disk_nbr_start;
uint16_t int_attrs;
uint32_t ext_attrs;
uint32_t lfh_offset;
const uint8_t *name;
const uint8_t *extra;
const uint8_t *comment;
};
made_by_ver
und extract_ver
codieren Sie Informationen über das Betriebssystem und die Version des Programms, mit dem dieses Element hinzugefügt wurde, sowie darüber, welche Version zum Abrufen erforderlich ist. Die wichtigsten acht Bits codieren das Betriebssystem (z. B. 0 bedeutet DOS, 3 bedeutet Unix, 10 bedeutet Windows NTFS) und die unteren acht Bits codieren die Softwareversion. Setzen Sie den Dezimalwert auf 20, was Kompatibilität mit PKZip 2.0 bedeutet.gp_flag
enthält verschiedene Flags. Wir sind interessiert:- Bit 0, das die Tatsache der Verschlüsselung des Elements anzeigt (wir werden dies nicht berücksichtigen);
- Und die Bits 1 und 2, die den Grad der Deflate-Komprimierung codieren (0 - normal, 1 - maximal, 2 - schnell, 3 - sehr schnell).
method
codiert eine Komprimierungsmethode. 0 - Daten nicht komprimiert, 8 - Delate angewendet. Andere Werte beziehen sich auf alte oder neue Algorithmen, aber fast alle Zip verwenden diese beiden Werte.mod_time
und mod_date
enthalten das Datum und die Uhrzeit der Änderung der Datei, codiert im MS-DOS-Format . Mit diesem Code konvertieren wir die üblichen C-Zeitstempel time_t
in und aus dem MS-DOS-Format:
static time_t dos2ctime(uint16_t dos_date, uint16_t dos_time)
{
struct tm tm = {0};
tm.tm_sec = (dos_time & 0x1f) * 2;
tm.tm_min = (dos_time >> 5) & 0x3f;
tm.tm_hour = (dos_time >> 11);
tm.tm_mday = (dos_date & 0x1f);
tm.tm_mon = ((dos_date >> 5) & 0xf) - 1;
tm.tm_year = (dos_date >> 9) + 80;
tm.tm_isdst = -1;
return mktime(&tm);
}
static void ctime2dos(time_t t, uint16_t *dos_date, uint16_t *dos_time)
{
struct tm *tm = localtime(&t);
*dos_time = 0;
*dos_time |= tm->tm_sec / 2;
*dos_time |= tm->tm_min << 5;
*dos_time |= tm->tm_hour << 11;
*dos_date = 0;
*dos_date |= tm->tm_mday;
*dos_date |= (tm->tm_mon + 1) << 5;
*dos_date |= (tm->tm_year - 80) << 9;
}
Das Feld crc32
enthält den Wert des zyklisch redundanten Codes unkomprimierter Daten. Es wird verwendet, um die Datenintegrität nach dem Abrufen zu überprüfen. Implementierung hier: crc32.c .comp_size
und uncomp_size
enthalten die komprimierte und unkomprimierte Größe der Elementdateidaten. Die folgenden drei Felder enthalten die Länge des Namens, des Kommentars und zusätzlicher Daten unmittelbar nach dem Titel. disk_nbr_start
Entwickelt für Archive mit mehreren Disketten.int_attrs
und ext_attrs
beschreiben Sie die internen und externen Attribute der Datei. Interne beziehen sich auf den Inhalt der Datei. Das niedrigstwertige Bit gibt beispielsweise an, ob die Datei nur Text enthält. Externe Attribute geben an, ob die Datei ausgeblendet, schreibgeschützt usw. ist. Der Inhalt dieser Felder hängt insbesondere vom Betriebssystem abmade_by_ver
. Unter DOS enthalten die unteren 8 Bits das Dateiattributbyte, das aus dem Systemaufruf Int 21 / AX = 4300h abgerufen werden kann . Zum Beispiel bedeutet Bit 4, dass es sich um ein Verzeichnis handelt, und Bit 5 bedeutet, dass das Attribut "Archiv" festgelegt ist (true für die meisten Dateien unter DOS). Soweit ich weiß, werden diese Bits aus Kompatibilitätsgründen in anderen Betriebssystemen ähnlich gesetzt. Unter Unix enthalten die hohen 16 Bits dieses Felds Dateimodusbits, die von stat (2) in zurückgegeben werden st_mode
.lfh_offset
teilt uns mit, wo nach dem lokalen Dateikopf gesucht werden soll. name
- Dateiname (C-Zeile) und comment
- optionaler Kommentar für dieses Archivelement (C-Zeile). extra
kann optionale zusätzliche Daten enthalten, z. B. Informationen zum Eigentümer der Unix-Datei, genaueres Datum und Uhrzeit der Änderung oder Zip64-Felder.Mit dieser Funktion werden die zentralen Header von Dateien gelesen:
#define CFH_BASE_SZ 46
#define CFH_SIGNATURE 0x02014b50
static bool read_cfh(struct cfh *cfh, const uint8_t *src, size_t src_len,
size_t offset)
{
const uint8_t *p;
uint32_t signature;
if (offset > src_len || src_len - offset < CFH_BASE_SZ) {
return false;
}
p = &src[offset];
signature = READ32(p);
if (signature != CFH_SIGNATURE) {
return false;
}
cfh->made_by_ver = READ16(p);
cfh->extract_ver = READ16(p);
cfh->gp_flag = READ16(p);
cfh->method = READ16(p);
cfh->mod_time = READ16(p);
cfh->mod_date = READ16(p);
cfh->crc32 = READ32(p);
cfh->comp_size = READ32(p);
cfh->uncomp_size = READ32(p);
cfh->name_len = READ16(p);
cfh->extra_len = READ16(p);
cfh->comment_len = READ16(p);
cfh->disk_nbr_start = READ16(p);
cfh->int_attrs = READ16(p);
cfh->ext_attrs = READ32(p);
cfh->lfh_offset = READ32(p);
cfh->name = p;
cfh->extra = cfh->name + cfh->name_len;
cfh->comment = cfh->extra + cfh->extra_len;
assert(p == &src[offset + CFH_BASE_SZ] && "All fields read.");
if (src_len - offset - CFH_BASE_SZ <
cfh->name_len + cfh->extra_len + cfh->comment_len) {
return false;
}
return true;
}
static size_t write_cfh(uint8_t *dst, const struct cfh *cfh)
{
uint8_t *p = dst;
WRITE32(p, CFH_SIGNATURE);
WRITE16(p, cfh->made_by_ver);
WRITE16(p, cfh->extract_ver);
WRITE16(p, cfh->gp_flag);
WRITE16(p, cfh->method);
WRITE16(p, cfh->mod_time);
WRITE16(p, cfh->mod_date);
WRITE32(p, cfh->crc32);
WRITE32(p, cfh->comp_size);
WRITE32(p, cfh->uncomp_size);
WRITE16(p, cfh->name_len);
WRITE16(p, cfh->extra_len);
WRITE16(p, cfh->comment_len);
WRITE16(p, cfh->disk_nbr_start);
WRITE16(p, cfh->int_attrs);
WRITE32(p, cfh->ext_attrs);
WRITE32(p, cfh->lfh_offset);
assert(p - dst == CFH_BASE_SZ);
if (cfh->name_len != 0) {
memcpy(p, cfh->name, cfh->name_len);
p += cfh->name_len;
}
if (cfh->extra_len != 0) {
memcpy(p, cfh->extra, cfh->extra_len);
p += cfh->extra_len;
}
if (cfh->comment_len != 0) {
memcpy(p, cfh->comment, cfh->comment_len);
p += cfh->comment_len;
}
return (size_t)(p - dst);
}
Lokaler Dateikopf
Den Daten jedes Archivelements geht ein lokaler Dateikopf voraus, der die meisten Informationen aus dem zentralen Kopf wiederholt.Die Duplizierung von Daten in den zentralen und lokalen Headern wurde wahrscheinlich eingeführt, damit PKZip beim Entpacken nicht das gesamte zentrale Verzeichnis im Speicher behält. Stattdessen können beim Extrahieren jeder Datei der Name und andere Informationen aus dem lokalen Header gelesen werden. Darüber hinaus sind lokale Header nützlich, um Dateien aus Zip-Archiven wiederherzustellen, in denen das zentrale Verzeichnis fehlt oder beschädigt ist.Diese Redundanz ist jedoch auch die Hauptquelle für Unsicherheit. Was passiert beispielsweise, wenn die Dateinamen in den zentralen und lokalen Headern nicht übereinstimmen? Dies führt häufig zu Fehlern und Sicherheitsproblemen.Nicht alle Informationen aus der zentralen Überschrift werden dupliziert. Zum Beispiel Felder mit Dateiattributen. Wenn das drittniedrigste Bit gp_flags
(CRC-32) angegeben wird , werden die komprimierten und nicht komprimierten Felder auf Null zurückgesetzt, und diese Informationen befinden sich im Datenbeschreibungsblock nach den Daten der Datei selbst (wir werden sie nicht berücksichtigen). Auf diese Weise können Sie einen lokalen Header aufzeichnen, bevor die Dateigröße des Elements bekannt ist oder auf welche Größe es komprimiert wird.Der lokale Header beginnt mit der Signatur 'P', 'K', 3, 4, und dann gibt es eine solche Struktur:
struct lfh {
uint16_t extract_ver;
uint16_t gp_flag;
uint16_t method;
uint16_t mod_time;
uint16_t mod_date;
uint32_t crc32;
uint32_t comp_size;
uint32_t uncomp_size;
uint16_t name_len;
uint16_t extra_len;
const uint8_t *name;
const uint8_t *extra;
};
Diese Funktionen lesen und schreiben lokale Header wie andere Datenstrukturen:
#define LFH_BASE_SZ 30
#define LFH_SIGNATURE 0x04034b50
static bool read_lfh(struct lfh *lfh, const uint8_t *src, size_t src_len,
size_t offset)
{
const uint8_t *p;
uint32_t signature;
if (offset > src_len || src_len - offset < LFH_BASE_SZ) {
return false;
}
p = &src[offset];
signature = READ32(p);
if (signature != LFH_SIGNATURE) {
return false;
}
lfh->extract_ver = READ16(p);
lfh->gp_flag = READ16(p);
lfh->method = READ16(p);
lfh->mod_time = READ16(p);
lfh->mod_date = READ16(p);
lfh->crc32 = READ32(p);
lfh->comp_size = READ32(p);
lfh->uncomp_size = READ32(p);
lfh->name_len = READ16(p);
lfh->extra_len = READ16(p);
lfh->name = p;
lfh->extra = lfh->name + lfh->name_len;
assert(p == &src[offset + LFH_BASE_SZ] && "All fields read.");
if (src_len - offset - LFH_BASE_SZ < lfh->name_len + lfh->extra_len) {
return false;
}
return true;
}
static size_t write_lfh(uint8_t *dst, const struct lfh *lfh)
{
uint8_t *p = dst;
WRITE32(p, LFH_SIGNATURE);
WRITE16(p, lfh->extract_ver);
WRITE16(p, lfh->gp_flag);
WRITE16(p, lfh->method);
WRITE16(p, lfh->mod_time);
WRITE16(p, lfh->mod_date);
WRITE32(p, lfh->crc32);
WRITE32(p, lfh->comp_size);
WRITE32(p, lfh->uncomp_size);
WRITE16(p, lfh->name_len);
WRITE16(p, lfh->extra_len);
assert(p - dst == LFH_BASE_SZ);
if (lfh->name_len != 0) {
memcpy(p, lfh->name, lfh->name_len);
p += lfh->name_len;
}
if (lfh->extra_len != 0) {
memcpy(p, lfh->extra, lfh->extra_len);
p += lfh->extra_len;
}
return (size_t)(p - dst);
}
Implementierung von Zip Read
Mit den oben genannten Funktionen implementieren wir das Lesen der Zip-Datei in den Speicher und erhalten einen Iterator für den Zugriff auf die Archivelemente:typedef size_t zipiter_t;
typedef struct zip_t zip_t;
struct zip_t {
uint16_t num_members;
const uint8_t *comment;
uint16_t comment_len;
zipiter_t members_begin;
zipiter_t members_end;
const uint8_t *src;
size_t src_len;
};
bool zip_read(zip_t *zip, const uint8_t *src, size_t src_len)
{
struct eocdr eocdr;
struct cfh cfh;
struct lfh lfh;
size_t i, offset;
const uint8_t *comp_data;
zip->src = src;
zip->src_len = src_len;
if (!find_eocdr(&eocdr, src, src_len)) {
return false;
}
if (eocdr.disk_nbr != 0 || eocdr.cd_start_disk != 0 ||
eocdr.disk_cd_entries != eocdr.cd_entries) {
return false;
}
zip->num_members = eocdr.cd_entries;
zip->comment = eocdr.comment;
zip->comment_len = eocdr.comment_len;
offset = eocdr.cd_offset;
zip->members_begin = offset;
for (i = 0; i < eocdr.cd_entries; i++) {
if (!read_cfh(&cfh, src, src_len, offset)) {
return false;
}
if (cfh.gp_flag & 1) {
return false;
}
if (cfh.method != ZIP_STORED && cfh.method != ZIP_DEFLATED) {
return false;
}
if (cfh.method == ZIP_STORED &&
cfh.uncomp_size != cfh.comp_size) {
return false;
}
if (cfh.disk_nbr_start != 0) {
return false;
}
if (memchr(cfh.name, '\0', cfh.name_len) != NULL) {
return false;
}
if (!read_lfh(&lfh, src, src_len, cfh.lfh_offset)) {
return false;
}
comp_data = lfh.extra + lfh.extra_len;
if (cfh.comp_size > src_len - (size_t)(comp_data - src)) {
return false;
}
offset += CFH_BASE_SZ + cfh.name_len + cfh.extra_len +
cfh.comment_len;
}
zip->members_end = offset;
return true;
}
Wie oben erwähnt, sind Elementiteratoren einfach Offsets zum zentralen Dateikopf, über den Sie auf Elementdaten zugreifen können:typedef enum { ZIP_STORED = 0, ZIP_DEFLATED = 8 } method_t;
typedef struct zipmemb_t zipmemb_t;
struct zipmemb_t {
const uint8_t *name;
uint16_t name_len;
time_t mtime;
uint32_t comp_size;
const uint8_t *comp_data;
method_t method;
uint32_t uncomp_size;
uint32_t crc32;
const uint8_t *comment;
uint16_t comment_len;
bool is_dir;
zipiter_t next;
};
zipmemb_t zip_member(const zip_t *zip, zipiter_t it)
{
struct cfh cfh;
struct lfh lfh;
bool ok;
zipmemb_t m;
assert(it >= zip->members_begin && it < zip->members_end);
ok = read_cfh(&cfh, zip->src, zip->src_len, it);
assert(ok);
ok = read_lfh(&lfh, zip->src, zip->src_len, cfh.lfh_offset);
assert(ok);
m.name = cfh.name;
m.name_len = cfh.name_len;
m.mtime = dos2ctime(cfh.mod_date, cfh.mod_time);
m.comp_size = cfh.comp_size;
m.comp_data = lfh.extra + lfh.extra_len;
m.method = cfh.method;
m.uncomp_size = cfh.uncomp_size;
m.crc32 = cfh.crc32;
m.comment = cfh.comment;
m.comment_len = cfh.comment_len;
m.is_dir = (cfh.ext_attrs & EXT_ATTR_DIR) != 0;
m.next = it + CFH_BASE_SZ +
cfh.name_len + cfh.extra_len + cfh.comment_len;
assert(m.next <= zip->members_end);
return m;
}
Implementierung von Zip-Datensätzen
Um eine Zip-Datei in den Speicherpuffer zu schreiben, müssen Sie zunächst herausfinden, wie viel Speicher dafür zugewiesen werden muss. Und da wir nicht wissen, wie viele Daten wir komprimieren werden, bevor wir versuchen zu schreiben, berechnen wir die obere Grenze basierend auf den Größen der nicht komprimierten Elemente:
uint32_t zip_max_size(uint16_t num_memb, const char *const *filenames,
const uint32_t *file_sizes, const char *comment)
{
size_t comment_len, name_len;
uint64_t total;
uint16_t i;
comment_len = (comment == NULL ? 0 : strlen(comment));
if (comment_len > UINT16_MAX) {
return 0;
}
total = EOCDR_BASE_SZ + comment_len;
for (i = 0; i < num_memb; i++) {
assert(filenames[i] != NULL);
name_len = strlen(filenames[i]);
if (name_len > UINT16_MAX) {
return 0;
}
total += CFH_BASE_SZ + name_len;
total += LFH_BASE_SZ + name_len;
total += file_sizes[i];
}
if (total > UINT32_MAX) {
return 0;
}
return (uint32_t)total;
}
Dieser Code schreibt die Zip-Datei unter Verwendung der Deflate-Komprimierung jedes Elements und reduziert deren Größe:
uint32_t zip_write(uint8_t *dst, uint16_t num_memb,
const char *const *filenames,
const uint8_t *const *file_data,
const uint32_t *file_sizes,
const time_t *mtimes,
const char *comment,
void (*callback)(const char *filename, uint32_t size,
uint32_t comp_size))
{
uint16_t i;
uint8_t *p;
struct eocdr eocdr;
struct cfh cfh;
struct lfh lfh;
bool ok;
uint16_t name_len;
uint8_t *data_dst;
size_t comp_sz;
uint32_t lfh_offset, cd_offset, eocdr_offset;
p = dst;
for (i = 0; i < num_memb; i++) {
assert(filenames[i] != NULL);
assert(strlen(filenames[i]) <= UINT16_MAX);
name_len = (uint16_t)strlen(filenames[i]);
data_dst = p + LFH_BASE_SZ + name_len;
if (hwdeflate(file_data[i], file_sizes[i], data_dst,
file_sizes[i], &comp_sz) &&
comp_sz < file_sizes[i]) {
lfh.method = ZIP_DEFLATED;
assert(comp_sz <= UINT32_MAX);
lfh.comp_size = (uint32_t)comp_sz;
} else {
memcpy(data_dst, file_data[i], file_sizes[i]);
lfh.method = ZIP_STORED;
lfh.comp_size = file_sizes[i];
}
if (callback != NULL) {
callback(filenames[i], file_sizes[i], lfh.comp_size);
}
lfh.extract_ver = (0 << 8) | 20;
lfh.gp_flag = (lfh.method == ZIP_DEFLATED ? (0x1 << 1) : 0x0);
ctime2dos(mtimes[i], &lfh.mod_date, &lfh.mod_time);
lfh.crc32 = crc32(file_data[i], file_sizes[i]);
lfh.uncomp_size = file_sizes[i];
lfh.name_len = name_len;
lfh.extra_len = 0;
lfh.name = (const uint8_t*)filenames[i];
p += write_lfh(p, &lfh);
p += lfh.comp_size;
}
assert(p - dst <= UINT32_MAX);
cd_offset = (uint32_t)(p - dst);
lfh_offset = 0;
for (i = 0; i < num_memb; i++) {
ok = read_lfh(&lfh, dst, SIZE_MAX, lfh_offset);
assert(ok);
cfh.made_by_ver = lfh.extract_ver;
cfh.extract_ver = lfh.extract_ver;
cfh.gp_flag = lfh.gp_flag;
cfh.method = lfh.method;
cfh.mod_time = lfh.mod_time;
cfh.mod_date = lfh.mod_date;
cfh.crc32 = lfh.crc32;
cfh.comp_size = lfh.comp_size;
cfh.uncomp_size = lfh.uncomp_size;
cfh.name_len = lfh.name_len;
cfh.extra_len = 0;
cfh.comment_len = 0;
cfh.disk_nbr_start = 0;
cfh.int_attrs = 0;
cfh.ext_attrs = EXT_ATTR_ARC;
cfh.lfh_offset = lfh_offset;
cfh.name = lfh.name;
p += write_cfh(p, &cfh);
lfh_offset += LFH_BASE_SZ + lfh.name_len + lfh.comp_size;
}
assert(p - dst <= UINT32_MAX);
eocdr_offset = (uint32_t)(p - dst);
eocdr.disk_nbr = 0;
eocdr.cd_start_disk = 0;
eocdr.disk_cd_entries = num_memb;
eocdr.cd_entries = num_memb;
eocdr.cd_size = eocdr_offset - cd_offset;
eocdr.cd_offset = cd_offset;
eocdr.comment_len = (uint16_t)(comment == NULL ? 0 : strlen(comment));
eocdr.comment = (const uint8_t*)comment;
p += write_eocdr(p, &eocdr);
assert(p - dst <= zip_max_size(num_memb, filenames, file_sizes,
comment));
return (uint32_t)(p - dst);
}
Hwzip
Jetzt wissen wir, wie man Zip-Dateien liest und schreibt, wie man die darin gespeicherten Daten komprimiert und dekomprimiert. Schreiben wir nun ein einfaches Zip-Programm, das alle diese Tools enthält. Der Code ist unter hwzip.c verfügbar .Wir werden ein Makro für die einfache Fehlerbehandlung und mehrere Hilfsfunktionen für die überprüfte Speicherzuordnung verwenden:#define PERROR_IF(cond, msg) if (cond) { perror(msg); exit(1); }
static void *xmalloc(size_t size)
{
void *ptr = malloc(size);
PERROR_IF(ptr == NULL, "malloc");
return ptr;
}
static void *xrealloc(void *ptr, size_t size)
{
ptr = realloc(ptr, size);
PERROR_IF(ptr == NULL, "realloc");
return ptr;
}
Die beiden anderen Funktionen werden zum Lesen und Schreiben von Dateien verwendet:static uint8_t *read_file(const char *filename, size_t *file_sz)
{
FILE *f;
uint8_t *buf;
size_t buf_cap;
f = fopen(filename, "rb");
PERROR_IF(f == NULL, "fopen");
buf_cap = 4096;
buf = xmalloc(buf_cap);
*file_sz = 0;
while (feof(f) == 0) {
if (buf_cap - *file_sz == 0) {
buf_cap *= 2;
buf = xrealloc(buf, buf_cap);
}
*file_sz += fread(&buf[*file_sz], 1, buf_cap - *file_sz, f);
PERROR_IF(ferror(f), "fread");
}
PERROR_IF(fclose(f) != 0, "fclose");
return buf;
}
static void write_file(const char *filename, const uint8_t *data, size_t n)
{
FILE *f;
f = fopen(filename, "wb");
PERROR_IF(f == NULL, "fopen");
PERROR_IF(fwrite(data, 1, n, f) != n, "fwrite");
PERROR_IF(fclose(f) != 0, "fclose");
}
Unser Zip-Programm kann drei Funktionen ausführen: Erstellen Sie eine Liste der Inhalte von Zip-Dateien und extrahieren Sie diese sowie erstellen Sie Zip-Dateien. Auflistung ist nirgends einfacher:static void list_zip(const char *filename)
{
uint8_t *zip_data;
size_t zip_sz;
zip_t z;
zipiter_t it;
zipmemb_t m;
printf("Listing ZIP archive: %s\n\n", filename);
zip_data = read_file(filename, &zip_sz);
if (!zip_read(&z, zip_data, zip_sz)) {
printf("Failed to parse ZIP file!\n");
exit(1);
}
if (z.comment_len != 0) {
printf("%.*s\n\n", (int)z.comment_len, z.comment);
}
for (it = z.members_begin; it != z.members_end; it = m.next) {
m = zip_member(&z, it);
printf("%.*s\n", (int)m.name_len, m.name);
}
printf("\n");
free(zip_data);
}
Die Extraktion ist etwas komplizierter. Wir werden Hilfsfunktionen für die Nullterminierung des Dateinamens (um ihn weiterzugeben fopen
) und das Entpacken verwenden:static char *terminate_str(const char *str, size_t n)
{
char *p = xmalloc(n + 1);
memcpy(p, str, n);
p[n] = '\0';
return p;
}
static uint8_t *inflate_member(const zipmemb_t *m)
{
uint8_t *p;
size_t src_used, dst_used;
assert(m->method == ZIP_DEFLATED);
p = xmalloc(m->uncomp_size);
if (hwinflate(m->comp_data, m->comp_size, &src_used, p, m->uncomp_size,
&dst_used) != HWINF_OK) {
free(p);
return NULL;
}
if (src_used != m->comp_size || dst_used != m->uncomp_size) {
free(p);
return NULL;
}
return p;
}
Unser Programm überspringt alle Archivelemente mit Verzeichnissen. Dies geschieht, um die sogenannten Path-Traversal-Angriffe zu vermeiden : Ein böswilliges Archiv wird verwendet, um die Datei von außerhalb des vom Benutzer angegebenen Verzeichnisses zu schreiben. Lesen Sie die Details in den Info-ZIP-FAQ .static void extract_zip(const char *filename)
{
uint8_t *zip_data;
size_t zip_sz;
zip_t z;
zipiter_t it;
zipmemb_t m;
char *tname;
uint8_t *inflated;
const uint8_t *uncomp_data;
printf("Extracting ZIP archive: %s\n\n", filename);
zip_data = read_file(filename, &zip_sz);
if (!zip_read(&z, zip_data, zip_sz)) {
printf("Failed to read ZIP file!\n");
exit(1);
}
if (z.comment_len != 0) {
printf("%.*s\n\n", (int)z.comment_len, z.comment);
}
for (it = z.members_begin; it != z.members_end; it = m.next) {
m = zip_member(&z, it);
if (m.is_dir) {
printf(" (Skipping dir: %.*s)\n",
(int)m.name_len, m.name);
continue;
}
if (memchr(m.name, '/', m.name_len) != NULL ||
memchr(m.name, '\\', m.name_len) != NULL) {
printf(" (Skipping file in dir: %.*s)\n",
(int)m.name_len, m.name);
continue;
}
assert(m.method == ZIP_STORED || m.method == ZIP_DEFLATED);
printf(" %s: %.*s",
m.method == ZIP_STORED ? "Extracting" : " Inflating",
(int)m.name_len, m.name);
fflush(stdout);
if (m.method == ZIP_STORED) {
assert(m.uncomp_size == m.comp_size);
inflated = NULL;
uncomp_data = m.comp_data;
} else {
inflated = inflate_member(&m);
if (inflated == NULL) {
printf("Error: inflation failed!\n");
exit(1);
}
uncomp_data = inflated;
}
if (crc32(uncomp_data, m.uncomp_size) != m.crc32) {
printf("Error: CRC-32 mismatch!\n");
exit(1);
}
tname = terminate_str((const char*)m.name, m.name_len);
write_file(tname, uncomp_data, m.uncomp_size);
printf("\n");
free(inflated);
free(tname);
}
printf("\n");
free(zip_data);
}
Um ein Zip-Archiv zu erstellen, lesen wir die Eingabedateien und füttern sie zip_write
. Da Sie in der Standard-C-Bibliothek die Änderungszeit für Dateien nicht abrufen können, verwenden wir die aktuelle Zeit (ich lasse dies als Hausaufgabe, um diese Funktion zu beheben).void zip_callback(const char *filename, uint32_t size, uint32_t comp_size)
{
bool deflated = comp_size < size;
printf(" %s: %s", deflated ? "Deflated" : " Stored", filename);
if (deflated) {
printf(" (%u%%)", 100 - 100 * comp_size / size);
}
printf("\n");
}
static void create_zip(const char *zip_filename, const char *comment,
uint16_t n, const char *const *filenames)
{
time_t mtime;
time_t *mtimes;
uint8_t **file_data;
uint32_t *file_sizes;
size_t file_size, zip_size;
uint8_t *zip_data;
uint16_t i;
printf("Creating ZIP archive: %s\n\n", zip_filename);
if (comment != NULL) {
printf("%s\n\n", comment);
}
mtime = time(NULL);
file_data = xmalloc(sizeof(*file_data) * n);
file_sizes = xmalloc(sizeof(*file_sizes) * n);
mtimes = xmalloc(sizeof(*mtimes) * n);
for (i = 0; i < n; i++) {
file_data[i] = read_file(filenames[i], &file_size);
if (file_size >= UINT32_MAX) {
printf("%s is too large!\n", filenames[i]);
exit(1);
}
file_sizes[i] = (uint32_t)file_size;
mtimes[i] = mtime;
}
zip_size = zip_max_size(n, filenames, file_sizes, comment);
if (zip_size == 0) {
printf("zip writing not possible");
exit(1);
}
zip_data = xmalloc(zip_size);
zip_size = zip_write(zip_data, n, filenames,
(const uint8_t *const *)file_data,
file_sizes, mtimes, comment, zip_callback);
write_file(zip_filename, zip_data, zip_size);
printf("\n");
free(zip_data);
for (i = 0; i < n; i++) {
free(file_data[i]);
}
free(mtimes);
free(file_sizes);
free(file_data);
}
Schließlich werden main
die Befehlszeilenargumente überprüft und entschieden, was zu tun ist:static void print_usage(const char *argv0)
{
printf("Usage:\n\n");
printf(" %s list <zipfile>\n", argv0);
printf(" %s extract <zipfile>\n", argv0);
printf(" %s create <zipfile> [-c <comment>] <files...>\n", argv0);
printf("\n");
}
int main(int argc, char **argv) {
printf("\n");
printf("HWZIP " VERSION " -- A very simple ZIP program ");
printf("from https://www.hanshq.net/zip.html\n");
printf("\n");
if (argc == 3 && strcmp(argv[1], "list") == 0) {
list_zip(argv[2]);
} else if (argc == 3 && strcmp(argv[1], "extract") == 0) {
extract_zip(argv[2]);
} else if (argc >= 3 && strcmp(argv[1], "create") == 0) {
if (argc >= 5 && strcmp(argv[3], "-c") == 0) {
create_zip(argv[2], argv[4], (uint16_t)(argc - 5),
(const char *const *)&argv[5]);
} else {
create_zip(argv[2], NULL, (uint16_t)(argc - 3),
(const char *const *)&argv[3]);
}
} else {
print_usage(argv[0]);
return 1;
}
return 0;
}
Montageanleitungen
Ein vollständiger Satz von Quelldateien ist unter hwzip-1.0.zip verfügbar . So kompilieren Sie HWZip unter Linux oder Mac:$ clang generate_tables.c && ./a.out > tables.c
$ clang -O3 -DNDEBUG -march=native -o hwzip crc32.c deflate.c huffman.c \
hwzip.c lz77.c tables.c zip.c
Unter Windows an der Eingabeaufforderung des Entwicklers in Visual Studio (wenn Sie nicht über Visual Studio verfügen, laden Sie die Build-Tools herunter ):cl /TC generate_tables.c && generate_tables > tables.c
cl /O2 /DNDEBUG /MT /Fehwzip.exe /TC crc32.c deflate.c huffman.c hwzip.c
lz77.c tables.c zip.c /link setargv.obj
Setargv.obj zum Erweitern von Wildcard-Befehlszeilenargumenten .)Fazit
Es ist erstaunlich, wie sich die Technologie schnell und langsam entwickelt. Das Zip-Format wurde vor 30 Jahren basierend auf Technologie aus den fünfziger und siebziger Jahren erstellt. Und obwohl sich seitdem viel geändert hat, sind die Zip-Dateien tatsächlich gleich geblieben und sind heute häufiger als je zuvor. Ich denke, es wird nützlich sein, ein gutes Verständnis dafür zu haben, wie sie funktionieren.Übungen
- Lassen Sie HWZip die Zeit aufzeichnen, zu der die Datei geändert wurde, und nicht die aktuelle Zeit, zu der das Archiv erstellt wurde. Verwenden Sie stat (2) unter Linux oder Mac und GetFileTime unter Windows. Oder fügen Sie ein Befehlszeilenflag hinzu, mit dem der Benutzer eine bestimmte Zeit für Dateiänderungen festlegen kann.
- gzip-. — , Deflate ( ). RFC 1952.
- Zip- . HWZip ,
read_file
mmap(2) Linux Mac CreateFileMapping Windows. - HWZip , Zip64. appnote.txt.