Schreiben Sie ein Komprimierungsprogramm für gzip-Dateien

11

Die Aufgabe dieser Herausforderung ist wie folgt:

Schreiben Sie ein Programm, das eine Datei von angemessener Größe (z. B. <16 MB) von stdin oder einem anderen Ort liest (wie Sie möchten, aber nicht fest codiert sein dürfen), und setzen Sie die komprimierte Ausgabe auf stdout. Die Ausgabe muss eine gültige gzip-komprimierte Datei sein. Wenn die komprimierte Datei über gunzip ausgeführt wird, sollte sie genau dieselbe Datei wie zuvor liefern.

Regeln

  • Die verwendete Programmiersprache muss bekannt sein, bevor dieser Wettbewerb beginnt
  • Die Punktzahl Ihres Programms ist die Anzahl der Zeichen des Quellcodes oder des zusammengestellten Programms (was auch immer kürzer ist).
  • Sie dürfen keine vorhandenen Komprimierungsbibliotheken verwenden.
  • Habe Spaß!
FUZxxl
quelle
2
Ist die Verwendung von eingebauten Bibliotheken erlaubt?
Hallvabo
@ Hallvabo: Nein. Ich habe das vergessen. Thx
FUZxxl
2
Der wahrscheinlich beste Weg, dies zu tun, besteht darin, die Eingabe am Anfang jedes Blocks mit den Markierungen "Der folgende Block ist unkomprimiert" aufzufüllen.
Anon.
gzip ist eine Programmiersprache. Keine vollständige Turing.
Alexandru
1
Dies ist ziemlich identisch mit dem Problem mit Waffen und Reißverschlüssen . Warum jemand seine Antworten hier und nicht auf codegolf.com veröffentlichen würde, ist mir ein Rätsel, es sei denn, er möchte sie in einer Sprache lösen, die von codegolf.com nicht unterstützt wird (z. B. GolfScript).
Chris Jester-Young

Antworten:

10

C # (534 Zeichen)

using System.IO;using B=System.Byte;class X{static void Main(string[]a){var f=File.ReadAllBytes(a[0]);int l=f.Length,i=0,j;var p=new uint[256];for(uint k=0,r=0;k<256;r=++k){for(j=0;j<8;j++)r=r>>1^(r&1)*0xedb88320;p[k]=r;}uint c=~(uint)0,n=c;using(var o=File.Open(a[0]+".gz",FileMode.Create)){o.Write(new B[]{31,139,8,0,0,0,0,0,4,11},0,10);for(;i<l;i++){o.Write(new B[]{(B)(i<l-1?0:1),1,0,254,255,f[i]},0,6);c=p[(c^f[i])&0xFF]^c>>8;}c^=n;o.Write(new[]{(B)c,(B)(c>>8),(B)(c>>16),(B)(c>>24),(B)l,(B)(l>>8),(B)(l>>16),(B)(l>>24)},0,8);}}}

Viel lesbarer:

using System.IO;
using B = System.Byte;
class X
{
    static void Main(string[] a)
    {
        // Read file contents
        var f = File.ReadAllBytes(a[0]);
        int l = f.Length, i = 0, j;

        // Initialise table for CRC hashsum
        var p = new uint[256];
        for (uint k = 0, r = 0; k < 256; r = ++k)
        {
            for (j = 0; j < 8; j++)
                r = r >> 1 ^ (r & 1) * 0xedb88320;
            p[k] = r;
        }

        uint c = ~(uint) 0, n = c;

        // Write the output file
        using (var o = File.Open(a[0] + ".gz", FileMode.Create))
        {
            // gzip header
            o.Write(new B[] { 31, 139, 8, 0, 0, 0, 0, 0, 4, 11 }, 0, 10);
            for (; i < l; i++)
            {
                // deflate block header plus one byte of payload
                o.Write(new B[] { (B) (i < l - 1 ? 0 : 1), 1, 0, 254, 255, f[i] }, 0, 6);
                // Compute CRC checksum
                c = p[(c ^ f[i]) & 0xFF] ^ c >> 8;
            }
            c ^= n;
            o.Write(new[] {
                // CRC checksum
                (B) c, (B) (c >> 8), (B) (c >> 16), (B) (c >> 24),
                // original file size
                (B) l, (B) (l >> 8), (B) (l >> 16), (B) (l >> 24)
            }, 0, 8);
        }
    }
}

Bemerkungen:

  • Erwartet den Pfad zur Datei als erstes Befehlszeilenargument.

  • Ausgabedatei ist Eingabedatei + .gz.

  • Ich verwende keine Bibliotheken, um gzip, deflate oder CRC32 auszuführen. Es ist alles drin.

  • Dieser „Kompressor“ erhöht die Dateigröße um den Faktor 6. Er ist jedoch im gültigen gzip-Format!

  • Getestet mit GNU gunzip und WinRAR.

Timwi
quelle