Escribir una utilidad de compresión para archivos gzip

La tarea de este desafío es la siguiente:

Escriba un programa que lea un archivo de tamaño razonable (digamos <16 MB) desde stdin o en cualquier otro lugar (como quiera, pero no debe estar codificado), y coloca la salida comprimida en stdout. La salida debe ser un archivo comprimido gzip válido y si el archivo comprimido se ejecuta a través de gunzip, debería producir exactamente el mismo archivo que antes.

Reglas

El lenguaje de programación utilizado debe conocerse antes de que comience esta competencia.
La puntuación de su programa es el número de caracteres del código fuente o del programa ensamblado (lo que sea más corto)
No está permitido usar ningún tipo de bibliotecas de compresión existentes.
¡Que te diviertas!

code-golf compression FUZxxl
fuente

¿Se permite el uso de bibliotecas integradas?

hallvabo

@hallvabo: No. Olvidé esto Thx

FUZxxl

Probablemente, la mejor manera de hacerlo es rellenar la entrada con los marcadores "el siguiente bloque está sin comprimir" al comienzo de cada bloque.

Anon

gzip es un lenguaje de programación. Sin embargo, no es un Turing completo.

Alexandru

Esto es prácticamente idéntico al problema de las armas y las cremalleras . No puedo entender por qué alguien publicaría sus respuestas aquí en lugar de en codegolf.com, a menos que quieran resolverlo en un lenguaje no compatible con codegolf.com (por ejemplo, GolfScript).

Chris Jester-Young

Respuestas:

C # (534 caracteres)

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);}}}

Mucho más legible:

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);
        }
    }
}

Comentarios:

Espera la ruta al archivo como primer argumento de línea de comandos.
El archivo de salida es el archivo de entrada + .gz.
No estoy usando ninguna biblioteca para hacer gzip, deflate o CRC32. Todo está ahí.
Este "compresor" aumenta el tamaño del archivo en un factor de 6. ¡Pero está en formato gzip válido!
Probado con GNU gunzip y WinRAR.

Timwi
fuente