Sí, el buen viejo GIF. Amado por su versatilidad, odiado por sus patentes y parcialmente obsoleto debido a sus limitaciones (y patentes), el GIF consiste, en el núcleo, en una paleta de colores y una imagen indexada a la paleta comprimida usando el algoritmo LZW.

Su tarea es escribir un programa que lea una imagen en formato ASCII PPM (número mágico "P3") desde la entrada estándar, y escriba la misma imagen (idéntico píxel por píxel) en formato GIF en la salida estándar. La salida puede ser en forma binaria o texto ASCII con cada byte representado por un número entre 0 y 255 (inclusive), separados por espacios en blanco.

Se garantiza que la imagen de entrada no tendrá más de 256 colores diferentes.

Puntuación:

Su programa se probará en 3 imágenes de muestra, y su puntaje se calculará como:
tamaño del programa + suma (tamaño de salida - tamaño de referencia para cada imagen de muestra)
El puntaje más bajo gana.

Requisitos:

• Su programa debe funcionar con cualquier tipo similar de imágenes de varios tamaños, y no debe limitarse a las imágenes de muestra. Podría, por ejemplo, restringir las dimensiones a múltiplos de 2 o asumir que el color máximo de ppm es 255, pero aún así debería funcionar con una amplia variedad de imágenes de entrada.
• La salida debe ser un archivo GIF válido que se pueda cargar con cualquier programa compatible (después de volver a convertirlo en binario si se usa la opción de salida ASCII).
• No puede utilizar ninguna función de procesamiento de imágenes (integrada o de terceros), su programa debe contener todo el código relevante.
• Su programa debe ser ejecutable en Linux utilizando software disponible gratuitamente.
• El código fuente debe usar solo caracteres ASCII.

Imágenes de muestra:

Aquí están las 3 imágenes de muestra que se utilizarán para calificar. Puede descargar un archivo zip con los archivos ppm (use el botón de descarga en la parte superior de esa página). O puede convertirlos de las imágenes png a continuación, usando ImageMagick con el siguiente comando:

convert file.png -compress none file.ppm

También proporciono las sumas de verificación MD5 de los archivos ppm para su confirmación.

1. ámbar

Tamaño de referencia: 38055
MD5 suma de comprobación de ppm: d1ad863cb556869332074717eb278080

2. ojos azules

Tamaño de referencia: 28638
MD5 suma de comprobación de ppm: e9ad410057a5f6c25a22a534259dcf3a

3. pimientos

Tamaño de referencia: 53586
MD5 suma de comprobación de ppm: 74112dbdbb8b7de5216f9e24c2e1a627

Perl, 515 + -2922 + 0 + -2571 = -4978

Otro enfoque. Esta vez estoy tratando de guardar la imagen en mosaicos de tamaño 64xH. Esto está bien de acuerdo con las especificaciones, pero algunos programas pueden mostrar solo el primer mosaico o una animación. Las baldosas se comprimen mejor debido a una mejor localidad espacial. Todavía hago compresión normal también para la segunda imagen y elijo lo que sea más corto. Como esto comprime la imagen dos veces, es dos veces más lenta en comparación con mi solución anterior.

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@l=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
print+GIF89a,pack(vvCxxC768,@k,~8,@t);
sub v{($w,$h)=@_;for$k(0.."@k"/$w-1){
$k*=$w;$r='';@d=();@p=grep+($z++-$k)%"@k"<$w,@l;
$"=' ';$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
$h.=pack"Cv4n(C/a)*",44,$k,0,$w,$k[1],8,/.{0,255}/gs
}$b=$h if!$b||length$b>length$h}
"@k"%64||v 64;v"@k";print"$b;"

Perl, 354 + 12 + 0 + -1 = 365418 9521 51168 56639

O bien hay algún error en mi código o la segunda imagen está optimizada para un codificador específico, ya que un cambio aparentemente insignificante redujo el tamaño a la referencia exactamente. Toma alrededor de 30 a 60 por imagen.

Versión de golf.

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'

La única decisión que puede tomar un compresor GIF es cuándo restablecer el diccionario LZW. En general, debido a cómo se eligieron las imágenes para esta tarea, el mejor momento para hacerlo es cada 4096 códigos, que es el momento en que el diccionario se desbordaría. Con dicho límite, el diccionario nunca se desborda, lo que ahorra un par de bytes en la implementación. Así es como funciona en detalle:

#!perl -n0
# function to add one codeword to the output stream @r.
# the current codeword length is based on the dictionary size/
sub r{push@r,map"@_">>$_,0..log(@d|256)/log 2}
# get the dimensions into @k
@k=/(\d+) (\d+)/;
# get pixel indexes to @p and palette to @t
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
# convert index table into space separated string 
$_="@p ";$"='|';
# LZW encoder; while something to encode
while(/\S/){
# output reset code
r 256;
# reset code dictionary $d is the last code number,
# %d is the map of codes and @d list of codes
$d=257;%d=map{($_,$_-1)}@d=1..256;
# find codes using regexp, stop at dictionary overflow
while($d<4096&&s/^(@d) (\d*)/$2/){
unshift@d,$&;$d{$&}=++$d;r$d{$1}}}
# end LZW encoder; output end code
r 257;
# convert bit string @r to bytes $f
vec($f,$j++,1)=$_ for@r;
# output header up to the color table
print+GIF89a,pack(vvCvC768,@k,~8,0,@t),
# output rest of the header
pack(Cv4CC,44,0,0,@k,0,8),
# output the LZW compressed data $f slicing into sub-blocks
$f=~s/.{0,255}/chr(length$&).$&/egsr,';'

Perl, 394 + -8 + 0 + -12 = 374

Agregar una heurística para adivinar el punto de reinicio mejora un poco la compresión, pero no lo suficiente como para justificar el código adicional:

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while
(@d<4001||(/((@d) ){11}/,$&=~y/ //>12))&@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'

CJam, puntaje 155 + 35306 + 44723 + 21518 = 101702

Solo una tonta implementación de referencia. Es lento, no hace ninguna compresión real y no es golf.

"GIF89a":iS*SqN/S*S%1>:i3/:M0=2<256f{md\}S*:ZS247S0S0SM1>_|:PL*_,768\m0a*+S*S44S0S0S0S0SZS0S8SM1>Pf{\a#}254/256a*{512+2b1>W%}%:+8/{W%2b}%255/{_,S@S*S}/0S59