Write a GIF encoder

Question

Yes, the good old GIF. Loved for its versatility, hated for its patents and partly obsoleted due to its limitations (and patents), GIF consists, at the core, of a color palette and a palette-indexed image compressed using the LZW algorithm.

Your task is to write a program that reads an image in ASCII PPM format ("P3" magic number) from the standard input, and writes the same image (identical pixel-by-pixel) in GIF format to the standard output. The output can either be in binary form, or ASCII text with each byte represented by a number between 0 and 255 (inclusive), separated by whitespace.

The input image is guaranteed not to have more than 256 different colors.

Scoring:

Your program will be tested on 3 sample images, and your score will be calculated as:
program size + sum(output size - reference size for each sample image)
Lowest score wins.

Requirements:

• Your program must work with any similar kinds of images of various sizes, and not be limited to the sample images. You could, for example, restrict the dimensions to be multiples of 2 or assume that the ppm max color is 255, but it should still work with a wide variety of input images.
• The output must be a valid GIF file that can be loaded with any compliant program (after converting back to binary if using the ASCII output option).
• You can not use any image processing functions (built-in or third-party), your program must contain all the relevant code.
• Your program must be runnable in Linux using freely available software.
• The source code must use only ASCII characters.

Sample images:

Here are the 3 sample images that will be used for scoring. You can download a zip archive with the ppm files (use the download button on the top of that page). Or you can convert them from the png images below, using ImageMagick with the following command:

convert file.png -compress none file.ppm

I am also providing the MD5 checksums of the ppm files for confirmation.

1. amber

Reference size: 38055
MD5 checksum of ppm: d1ad863cb556869332074717eb278080

2. blueeyes

Reference size: 28638
MD5 checksum of ppm: e9ad410057a5f6c25a22a534259dcf3a

3. peppers

Reference size: 53586
MD5 checksum of ppm: 74112dbdbb8b7de5216f9e24c2e1a627

Answer 1

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

Another approach. This time I am trying to save the image in tiles of size 64xH. This is fine according to specs, but some software may show only the first tile or an animation. The tiles compress better because of better spacial locality. I still do normal compression as well for the second image and choose whatever came shorter. Since this compresses the image twice, it is twice as slow compared to my previous solution.

#!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 = 365 418 9521 51168 56639

Either there is some bug in my code or the second image is optimized for a specific encoder as seemingly insignificant change reduced the size to the reference exactly. Takes about 30s-60s per image.

Golfed version.

#!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),';'

The only decision a GIF compressor can take is when to reset the LZW dictionary. In general because of how the images for this task were chosen the best moment to do so is each 4096 codes which is the moment the dictionary would overflow. With such limit the dictionary never overflows which saves a couple of bytes in the implementation. This is how it works in detail:

#!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

Adding a heuristic to guess the reset point improves compression a bit but not enough to justify the extra code:

#!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),';'

Answer 2

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

Just a dumb reference implementation. It's slow, doesn't do any actual compression and it's not golfed.

"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