9
\$\begingroup\$

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

amber.png

Reference size: 38055
MD5 checksum of ppm: d1ad863cb556869332074717eb278080

2. blueeyes

blueeyes.png

Reference size: 28638
MD5 checksum of ppm: e9ad410057a5f6c25a22a534259dcf3a

3. peppers

peppers.png

Reference size: 53586
MD5 checksum of ppm: 74112dbdbb8b7de5216f9e24c2e1a627

\$\endgroup\$
  • 1
    \$\begingroup\$ Moderator note: Off-topic/obsolete comments removed. Please see meta for discussion on the sample images in this question. \$\endgroup\$ – Doorknob Mar 15 '15 at 23:03
  • \$\begingroup\$ It seems the second image was treated with something like this: websiteoptimization.com/speed/tweak/lossy that would explain better compression ratio it has and sensitivity to the LZW encoder tweaks. \$\endgroup\$ – nutki Mar 17 '15 at 18:34
  • 1
    \$\begingroup\$ “The source code must use only ASCII characters.”—so, in other words, we are not allowed to do this challenge in APL? \$\endgroup\$ – FUZxxl Mar 18 '15 at 14:56
  • \$\begingroup\$ @FUZxxl true, but you can use J. You are also not allowed to use Aheui or to do base conversion tricks in GolfScript/CJam. \$\endgroup\$ – aditsu Mar 18 '15 at 20:59
4
\$\begingroup\$

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),';'
\$\endgroup\$
  • \$\begingroup\$ Very nice! Although it takes a lot more than 30s per image here. I was quite impressed with the -30 from the previous version, I wonder if you can combine the methods and get a lower score. Also, could you write a bit about what the program does? \$\endgroup\$ – aditsu Mar 17 '15 at 15:10
  • \$\begingroup\$ Requiring the width to be a multiple of 64 seems a bit extreme... \$\endgroup\$ – aditsu Mar 18 '15 at 21:06
  • \$\begingroup\$ @aditsu, It is not required, if the width is not multiple of 64 the tiling method is not tried and regular compression is used. Of course at a cost of another ~100 characters I could make the last tile variable size. \$\endgroup\$ – nutki Mar 18 '15 at 21:10
  • \$\begingroup\$ Very slow, and the tiled images show as animations, but.. well done, it's quite impressive to see you can really make them smaller. \$\endgroup\$ – aditsu Jul 14 '15 at 16:23
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.