[9fans] rgb2cmap

["rob pike" <rob@plan9.bell-labs.com>]

The version of rgb2cmap in the library and in the program that prints
the tables for the gif viewer has many problems.  Although it properly
recovers color map values given input RGB triples that match an
existing color in the RGBV map, its choices of color map entries for
RGB values not corresponding exactly to an entry in the map are, to
put it bluntly, awful.  Awful.

Russ Cox, Sean Dorward and I played around for a while trying to find
a simple, cheap algorithm that did a better job while maintaining the
inversion property, but have given up.  This message contains new
versions of /sys/src/libdraw/rgb.c and /sys/src/cmd/jpg/rgbrgbv.c that
employ a brute force but easy to understand method that satisfies the
inversion property and uses an easy to understand metric for values
outside the RGBV map.

If someone wants to work on a better algorithm, I'm all ears.  In the
meantime, have this.  Copy the files into their appropriate places and
build.

-rob

# To unbundle, run this file
echo /sys/src/libdraw/rgb.c
sed 's/.//' >/sys/src/libdraw/rgb.c <<'//GO.SYSIN DD /sys/src/libdraw/rgb.c'
-#include <u.h>
-#include <libc.h>
-#include <draw.h>
-
-/*
- * This original version, although fast and a true inverse of
- * cmap2rgb, in the sense that rgb2cmap(cmap2rgb(c))
- * returned the original color, does a terrible job for RGB
- * triples that do not appear in the color map, so it has been
- * replaced by the much slower version below, that loops
- * over the color map looking for the nearest point in RGB
- * space.  There is no visual psychology reason for that
- * criterion, but it's easy to implement and the results are
- * far more pleasing.
- *
-int
-rgb2cmap(int cr, int cg, int cb)
-{
-	int r, g, b, v, cv;
-
-	if(cr < 0)
-		cr = 0;
-	else if(cr > 255)
-		cr = 255;
-	if(cg < 0)
-		cg = 0;
-	else if(cg > 255)
-		cg = 255;
-	if(cb < 0)
-		cb = 0;
-	else if(cb > 255)
-		cb = 255;
-	r = cr>>6;
-	g = cg>>6;
-	b = cb>>6;
-	cv = cr;
-	if(cg > cv)
-		cv = cg;
-	if(cb > cv)
-		cv = cb;
-	v = (cv>>4)&3;
-	return ((((r<<2)+v)<<4)+(((g<<2)+b+v-r)&15));
-}
-*/
-
-int
-rgb2cmap(int cr, int cg, int cb)
-{
-	int i, r, g, b, sq;
-	ulong rgb;
-	int best, bestsq;
-
-	best = 0;
-	bestsq = 0x7FFFFFFF;
-	for(i=0; i<256; i++){
-		rgb = cmap2rgb(i);
-		r = (rgb>>16) & 0xFF;
-		g = (rgb>>8) & 0xFF;
-		b = (rgb>>0) & 0xFF;
-		sq = (r-cr)*(r-cr)+(g-cg)*(g-cg)+(b-cb)*(b-cb);
-		if(sq < bestsq){
-			bestsq = sq;
-			best = i;
-		}
-	}
-	return best;
-}
-
-int
-cmap2rgb(int c)
-{
-	int j, num, den, r, g, b, v, rgb;
-
-	r = c>>6;
-	v = (c>>4)&3;
-	j = (c-v+r)&15;
-	g = j>>2;
-	b = j&3;
-	den=r;
-	if(g>den)
-		den=g;
-	if(b>den)
-		den=b;
-	if(den==0) {
-		v *= 17;
-		rgb = (v<<16)|(v<<8)|v;
-	}
-	else{
-		num=17*(4*den+v);
-		rgb = ((r*num/den)<<16)|((g*num/den)<<8)|(b*num/den);
-	}
-	return rgb;
-}
-
-int
-cmap2rgba(int c)
-{
-	return (cmap2rgb(c)<<8)|0xFF;
-}
//GO.SYSIN DD /sys/src/libdraw/rgb.c
echo /sys/src/cmd/jpg/rgbrgbv.c
sed 's/.//' >/sys/src/cmd/jpg/rgbrgbv.c <<'//GO.SYSIN DD /sys/src/cmd/jpg/rgbrgbv.c'
-#include <u.h>
-#include <libc.h>
-#include <draw.h>
-
-/*
- * This version of closest() is now (feb 20, 2001) installed as rgb2cmap in libdraw
- */
-
-int
-closest(int cr, int cg, int cb)
-{
-	int i, r, g, b, sq;
-	ulong rgb;
-	int best, bestsq;
-
-	best = 0;
-	bestsq = 0x7FFFFFFF;
-	for(i=0; i<256; i++){
-		rgb = cmap2rgb(i);
-		r = (rgb>>16) & 0xFF;
-		g = (rgb>>8) & 0xFF;
-		b = (rgb>>0) & 0xFF;
-		sq = (r-cr)*(r-cr)+(g-cg)*(g-cg)+(b-cb)*(b-cb);
-		if(sq < bestsq){
-			bestsq = sq;
-			best = i;
-		}
-	}
-	return best;
-}
-
-void
-main(int argc, char *argv[])
-{
-	int i, rgb;
-	int r, g, b;
-	uchar close[16*16*16];
-
-	/* rgbmap */
-	print("uint rgbmap[256] = {\n");
-	for(i=0; i<256; i++){
-		if(i%8 == 0)
-			print("\t");
-		rgb = cmap2rgb(i);
-		r = (rgb>>16) & 0xFF;
-		g = (rgb>>8) & 0xFF;
-		b = (rgb>>0) & 0xFF;
-		print("0x%.6ulX, ", (r<<16) | (g<<8) | b);
-		if(i%8 == 7)
-			print("\n");
-	}
-	print("};\n\n");
-
-	/* closestrgb */
-	print("uchar closestrgb[16*16*16] = {\n");
-	for(r=0; r<256; r+=16)
-	for(g=0; g<256; g+=16)
-	for(b=0; b<256; b+=16)
-		close[(b/16)+16*((g/16)+16*(r/16))] = closest(r+8, g+8, b+8);
-	for(i=0; i<16*16*16; i++){
-		if(i%16 == 0)
-			print("\t");
-		print("%d,", close[i]);
-		if(i%16 == 15)
-			print("\n");
-	}
-	print("};\n\n");
-	exits(nil);
-}
//GO.SYSIN DD /sys/src/cmd/jpg/rgbrgbv.c