bradley@halibut.cis.upenn.edu (John Bradley) (11/28/90)
Submitted-by: bradley@halibut.cis.upenn.edu (John Bradley)
Posting-number: Volume 10, Issue 86
Archive-name: xv/part08
#!/bin/sh
# to extract, remove the header and type "sh filename"
if `test ! -s ./xv24to8.c`
then
echo "writting ./xv24to8.c"
cat > ./xv24to8.c << '\BARFOO\'
/*
* xv24to8.c - contains the 24-to-8-bit Conv24to8 procedure
*
* The Conv24to8 procedure takes a pointer to a 24-bit image (loaded
* previously). The image will be a w * h * 3 byte array of
* bytes. The image will be arranged with 3 bytes per pixel (in order
* R, G, and B), pixel 0 at the top left corner. (As normal.)
* The procedure also takes a maximum number of colors to use (numcols)
*
* The Conv24to8 procedure will set up the following: it will allocate and
* create 'pic', a pWIDE*pHIGH 8-bit picture. it will set up pWIDE and pHIGH.
* it will load up the r[], g[], and b[] colormap arrays. it will NOT
* calculate numcols, since the cmap sort procedure has to be called anyway
*
* Conv24to8 returns '0' if successful, '1' if it failed (presumably on a
* malloc())
*
* contains:
* Cont24to8()
* InitFSDTables()
*/
/*
* Copyright 1989, 1990 by the University of Pennsylvania
*
* Permission to use, copy, and distribute for non-commercial purposes,
* is hereby granted without fee, providing that the above copyright
* notice appear in all copies and that both the copyright notice and this
* permission notice appear in supporting documentation.
*
* The software may be modified for your own purposes, but modified versions
* may not be distributed.
*
* This software is provided "as is" without any express or implied warranty.
*/
#include "xv.h"
#define MAX_CMAP_SIZE 256
#define COLOR_DEPTH 8
#define MAX_COLOR 256
#define B_DEPTH 5 /* # bits/pixel to use */
#define B_LEN (1<<B_DEPTH)
#define C_DEPTH 2
#define C_LEN (1<<C_DEPTH) /* # cells/color to use */
typedef struct colorbox {
struct colorbox *next, *prev;
int rmin,rmax, gmin,gmax, bmin,bmax;
int total;
} CBOX;
typedef struct {
int num_ents;
int entries[MAX_CMAP_SIZE][2];
} CCELL;
static byte *pic24;
static int num_colors, WIDE, HIGH;
static int histogram[B_LEN][B_LEN][B_LEN];
CBOX *freeboxes, *usedboxes;
CCELL **ColorCells;
static void get_histogram();
static CBOX *largest_box();
static void splitbox();
static void shrinkbox();
static void assign_color();
static CCELL *create_colorcell();
static void map_colortable();
static int quant_fsdither();
static int Quick24to8();
static int QuickCheck();
static byte tbl1[256], /* tables used in F-S Dithering */
tbl3[256], /* contain i/16, 3i/16, 5i/16, 7i/16, */
tbl5[256], /* (i=0-255) respectively */
tbl7[256];
/****************************/
int Conv24to8(p,w,h,nc)
/****************************/
byte *p;
int w,h,nc;
{
int i;
CBOX *box_list, *ptr;
/* copy arguments to local-global variables */
pic24 = p; pWIDE = WIDE = w; pHIGH = HIGH = h; num_colors = nc;
/* allocate pic immediately, so that if we can't allocate it, we don't
waste time running this algorithm */
pic = (byte *) malloc(WIDE * HIGH);
if (pic == NULL) {
fprintf(stderr,"%s: Conv24to8() - failed to allocate 'pic'\n",cmd);
return(1);
}
/* quick check: if we're going to display a greyscale or 1-bit image,
DON'T run this annoyingly time-consuming code. Just convert the 24-bit
color image to an 8-bit greyscale. This takes virtually no time, by
comparision, and it has the same effect. */
if (mono || nc==0) {
byte *pp, *p24;
for (i=0; i<256; i++) r[i]=g[i]=b[i]=i; /* greyscale colormap */
pp = pic; p24 = pic24;
for (i=WIDE*HIGH; i>0; i--, pp++, p24+=3)
*pp = (p24[0]*11 + p24[1]*16 + p24[2]*5) >> 5; /* pp=.33R+.5G+.17B */
return(0);
}
if (!noqcheck && QuickCheck(pic24,w,h,nc)) {
/* see if it's a <256 color RGB pic */
SetISTR(ISTR_INFO,"No color compression was necessary.\n");
return 0;
}
else if (!slow24) {
SetISTR(ISTR_INFO,"Doing quick 24-bit to 8-bit conversion.");
return(Quick24to8(pic24,w,h));
}
else
SetISTR(ISTR_INFO,"Doing full 24-bit to 8-bit conversion.");
/**** STEP 1: create empty boxes ****/
usedboxes = NULL;
box_list = freeboxes = (CBOX *) malloc(num_colors * sizeof(CBOX));
if (box_list == NULL) {
fprintf(stderr,"%s: Conv24to8() - failed to allocate 'freeboxes'\n",cmd);
return(1);
}
for (i=0; i<num_colors; i++) {
freeboxes[i].next = &freeboxes[i+1];
freeboxes[i].prev = &freeboxes[i-1];
}
freeboxes[0].prev = NULL;
freeboxes[num_colors-1].next = NULL;
/**** STEP 2: get histogram, initialize first box ****/
ptr = freeboxes;
freeboxes = ptr->next;
if (freeboxes) freeboxes->prev = NULL;
ptr->next = usedboxes;
usedboxes = ptr;
if (ptr->next) ptr->next->prev = ptr;
get_histogram(ptr);
/**** STEP 3: continually subdivide boxes until no more free boxes remain */
while (freeboxes) {
ptr = largest_box();
if (ptr) splitbox(ptr);
else break;
}
/**** STEP 4: assign colors to all boxes ****/
for (i=0, ptr=usedboxes; i<num_colors && ptr; i++, ptr=ptr->next) {
assign_color(ptr, &r[i], &g[i], &b[i]);
}
/* We're done with the boxes now */
num_colors = i;
free(box_list);
box_list = freeboxes = usedboxes = NULL;
/**** STEP 5: scan histogram and map all values to closest color */
/* 5a: create cell list as described in Heckbert[2] */
ColorCells = (CCELL **) calloc(C_LEN*C_LEN*C_LEN, sizeof(CCELL *));
/* 5b: create mapping from truncated pixel space to color table entries */
map_colortable();
/**** STEP 6: scan image, match input values to table entries */
i=quant_fsdither();
/* free everything that can be freed */
free(ColorCells);
return i;
}
/****************************/
static void get_histogram(box)
CBOX *box;
/****************************/
{
int i,j,r,g,b,*ptr;
byte *p;
box->rmin = box->gmin = box->bmin = 999;
box->rmax = box->gmax = box->bmax = -1;
box->total = WIDE * HIGH;
/* zero out histogram */
ptr = &histogram[0][0][0];
for (i=B_LEN*B_LEN*B_LEN; i>0; i-- ) *ptr++ = 0;
/* calculate histogram */
p = pic24;
for (i=0; i<HIGH; i++)
for (j=0; j<WIDE; j++) {
r = (*p++) >> (COLOR_DEPTH-B_DEPTH);
g = (*p++) >> (COLOR_DEPTH-B_DEPTH);
b = (*p++) >> (COLOR_DEPTH-B_DEPTH);
if (r < box->rmin) box->rmin = r;
if (r > box->rmax) box->rmax = r;
if (g < box->gmin) box->gmin = g;
if (g > box->gmax) box->gmax = g;
if (b < box->bmin) box->bmin = b;
if (b > box->bmax) box->bmax = b;
histogram[r][g][b]++;
}
}
/******************************/
static CBOX *largest_box()
/******************************/
{
CBOX *tmp, *ptr;
int size = -1;
tmp = usedboxes;
ptr = NULL;
while (tmp) {
if ( (tmp->rmax > tmp->rmin ||
tmp->gmax > tmp->gmin ||
tmp->bmax > tmp->bmin) && tmp->total > size ) {
ptr = tmp;
size = tmp->total;
}
tmp = tmp->next;
}
return(ptr);
}
/******************************/
static void splitbox(ptr)
CBOX *ptr;
/******************************/
{
int hist2[B_LEN], first, last, i, rdel, gdel, bdel;
CBOX *new;
int *iptr, *histp, ir, ig, ib;
int rmin,rmax,gmin,gmax,bmin,bmax;
enum {RED,GREEN,BLUE} which;
/*
* see which axis is the largest, do a histogram along that
* axis. Split at median point. Contract both new boxes to
* fit points and return
*/
first = last = 0; /* shut RT hcc compiler up */
rmin = ptr->rmin; rmax = ptr->rmax;
gmin = ptr->gmin; gmax = ptr->gmax;
bmin = ptr->bmin; bmax = ptr->bmax;
rdel = rmax - rmin;
gdel = gmax - gmin;
bdel = bmax - bmin;
if (rdel>=gdel && rdel>=bdel) which = RED;
else if (gdel>=bdel) which = GREEN;
else which = BLUE;
/* get histogram along longest axis */
switch (which) {
case RED:
histp = &hist2[rmin];
for (ir=rmin; ir<=rmax; ir++) {
*histp = 0;
for (ig=gmin; ig<=gmax; ig++) {
iptr = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++) {
*histp += *iptr;
++iptr;
}
}
++histp;
}
first = rmin; last = rmax;
break;
case GREEN:
histp = &hist2[gmin];
for (ig=gmin; ig<=gmax; ig++) {
*histp = 0;
for (ir=rmin; ir<=rmax; ir++) {
iptr = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++) {
*histp += *iptr;
++iptr;
}
}
++histp;
}
first = gmin; last = gmax;
break;
case BLUE:
histp = &hist2[bmin];
for (ib=bmin; ib<=bmax; ib++) {
*histp = 0;
for (ir=rmin; ir<=rmax; ir++) {
iptr = &histogram[ir][gmin][ib];
for (ig=gmin; ig<=gmax; ig++) {
*histp += *iptr;
iptr += B_LEN;
}
}
++histp;
}
first = bmin; last = bmax;
break;
}
/* find median point */
{
int sum, sum2;
histp = &hist2[first];
sum2 = ptr->total/2;
histp = &hist2[first];
sum = 0;
for (i=first; i<=last && (sum += *histp++)<sum2; i++);
if (i==first) i++;
}
/* Create new box, re-allocate points */
new = freeboxes;
freeboxes = new->next;
if (freeboxes) freeboxes->prev = NULL;
if (usedboxes) usedboxes->prev = new;
new->next = usedboxes;
usedboxes = new;
{
int sum1,sum2,j;
histp = &hist2[first];
sum1 = 0;
for (j = first; j < i; ++j) sum1 += *histp++;
sum2 = 0;
for (j = i; j <= last; ++j) sum2 += *histp++;
new->total = sum1;
ptr->total = sum2;
}
new->rmin = rmin; new->rmax = rmax;
new->gmin = gmin; new->gmax = gmax;
new->bmin = bmin; new->bmax = bmax;
switch (which) {
case RED: new->rmax = i-1; ptr->rmin = i; break;
case GREEN: new->gmax = i-1; ptr->gmin = i; break;
case BLUE: new->bmax = i-1; ptr->bmin = i; break;
}
shrinkbox(new);
shrinkbox(ptr);
}
/****************************/
static void shrinkbox(box)
CBOX *box;
/****************************/
{
int *histp,ir,ig,ib;
int rmin,rmax,gmin,gmax,bmin,bmax;
rmin = box->rmin; rmax = box->rmax;
gmin = box->gmin; gmax = box->gmax;
bmin = box->bmin; bmax = box->bmax;
if (rmax>rmin) {
for (ir=rmin; ir<=rmax; ir++)
for (ig=gmin; ig<=gmax; ig++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->rmin = rmin = ir;
goto have_rmin;
}
}
have_rmin:
if (rmax>rmin)
for (ir=rmax; ir>=rmin; --ir)
for (ig=gmin; ig<=gmax; ig++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->rmax = rmax = ir;
goto have_rmax;
}
}
}
have_rmax:
if (gmax>gmin) {
for (ig=gmin; ig<=gmax; ig++)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->gmin = gmin = ig;
goto have_gmin;
}
}
have_gmin:
if (gmax>gmin)
for (ig=gmax; ig>=gmin; --ig)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][ig][bmin];
for (ib=bmin; ib<=bmax; ib++)
if (*histp++ != 0) {
box->gmax = gmax = ig;
goto have_gmax;
}
}
}
have_gmax:
if (bmax>bmin) {
for (ib=bmin; ib<=bmax; ib++)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][gmin][ib];
for (ig=gmin; ig<=gmax; ig++) {
if (*histp != 0) {
box->bmin = bmin = ib;
goto have_bmin;
}
histp += B_LEN;
}
}
have_bmin:
if (bmax>bmin)
for (ib=bmax; ib>=bmin; --ib)
for (ir=rmin; ir<=rmax; ir++) {
histp = &histogram[ir][gmin][ib];
for (ig=gmin; ig<=gmax; ig++) {
if (*histp != 0) {
bmax = ib;
goto have_bmax;
}
histp += B_LEN;
}
}
}
have_bmax: return;
}
/*******************************/
static void assign_color(ptr,rp,gp,bp)
CBOX *ptr;
byte *rp,*gp,*bp;
/*******************************/
{
*rp = ((ptr->rmin + ptr->rmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
*gp = ((ptr->gmin + ptr->gmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
*bp = ((ptr->bmin + ptr->bmax) << (COLOR_DEPTH - B_DEPTH)) / 2;
}
/*******************************/
static CCELL *create_colorcell(r1,g1,b1)
int r1,g1,b1;
/*******************************/
{
register int i,tmp, dist;
register CCELL *ptr;
register byte *rp,*gp,*bp;
int ir,ig,ib, mindist;
ir = r1 >> (COLOR_DEPTH-C_DEPTH);
ig = g1 >> (COLOR_DEPTH-C_DEPTH);
ib = b1 >> (COLOR_DEPTH-C_DEPTH);
r1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
g1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
b1 &= ~1 << (COLOR_DEPTH-C_DEPTH);
ptr = (CCELL *) malloc(sizeof(CCELL));
*(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
ptr->num_ents = 0;
/* step 1: find all colors inside this cell, while we're at
it, find distance of centermost point to furthest
corner */
mindist = 99999999;
rp=r; gp=g; bp=b;
for (i=0; i<num_colors; i++,rp++,gp++,bp++)
if( *rp>>(COLOR_DEPTH-C_DEPTH) == ir &&
*gp>>(COLOR_DEPTH-C_DEPTH) == ig &&
*bp>>(COLOR_DEPTH-C_DEPTH) == ib) {
ptr->entries[ptr->num_ents][0] = i;
ptr->entries[ptr->num_ents][1] = 0;
++ptr->num_ents;
tmp = *rp - r1;
if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
dist = tmp*tmp;
tmp = *gp - g1;
if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
dist += tmp*tmp;
tmp = *bp - b1;
if (tmp < (MAX_COLOR/C_LEN/2)) tmp = MAX_COLOR/C_LEN-1 - tmp;
dist += tmp*tmp;
if (dist < mindist) mindist = dist;
}
/* step 3: find all points within that distance to box */
rp=r; gp=g; bp=b;
for (i=0; i<num_colors; i++,rp++,gp++,bp++)
if (*rp >> (COLOR_DEPTH-C_DEPTH) != ir ||
*gp >> (COLOR_DEPTH-C_DEPTH) != ig ||
*bp >> (COLOR_DEPTH-C_DEPTH) != ib) {
dist = 0;
if ((tmp = r1 - *rp)>0 || (tmp = *rp - (r1 + MAX_COLOR/C_LEN-1)) > 0 )
dist += tmp*tmp;
if( (tmp = g1 - *gp)>0 || (tmp = *gp - (g1 + MAX_COLOR/C_LEN-1)) > 0 )
dist += tmp*tmp;
if( (tmp = b1 - *bp)>0 || (tmp = *bp - (b1 + MAX_COLOR/C_LEN-1)) > 0 )
dist += tmp*tmp;
if( dist < mindist ) {
ptr->entries[ptr->num_ents][0] = i;
ptr->entries[ptr->num_ents][1] = dist;
++ptr->num_ents;
}
}
/* sort color cells by distance, use cheap exchange sort */
{
int n, next_n;
n = ptr->num_ents - 1;
while (n>0) {
next_n = 0;
for (i=0; i<n; ++i) {
if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
tmp = ptr->entries[i][0];
ptr->entries[i][0] = ptr->entries[i+1][0];
ptr->entries[i+1][0] = tmp;
tmp = ptr->entries[i][1];
ptr->entries[i][1] = ptr->entries[i+1][1];
ptr->entries[i+1][1] = tmp;
next_n = i;
}
}
n = next_n;
}
}
return (ptr);
}
/***************************/
static void map_colortable()
/***************************/
{
int ir,ig,ib, *histp;
CCELL *cell;
histp = &histogram[0][0][0];
for (ir=0; ir<B_LEN; ir++)
for (ig=0; ig<B_LEN; ig++)
for (ib=0; ib<B_LEN; ib++) {
if (*histp==0) *histp = -1;
else {
int i, j, tmp, d2, dist;
cell = *(ColorCells +
( ((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
+ ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH)
+ (ib>>(B_DEPTH-C_DEPTH)) ) );
if (cell==NULL)
cell = create_colorcell(ir<<(COLOR_DEPTH-B_DEPTH),
ig<<(COLOR_DEPTH-B_DEPTH),
ib<<(COLOR_DEPTH-B_DEPTH));
dist = 9999999;
for (i=0; i<cell->num_ents && dist>cell->entries[i][1]; i++) {
j = cell->entries[i][0];
d2 = r[j] - (ir << (COLOR_DEPTH-B_DEPTH));
d2 *= d2;
tmp = g[j] - (ig << (COLOR_DEPTH-B_DEPTH));
d2 += tmp*tmp;
tmp = b[j] - (ib << (COLOR_DEPTH-B_DEPTH));
d2 += tmp*tmp;
if( d2 < dist ) { dist = d2; *histp = j; }
}
}
histp++;
}
}
/*****************************/
static int quant_fsdither()
/*****************************/
{
register int *thisptr, *nextptr;
int *thisline, *nextline, *tmpptr;
int r1, g1, b1, r2, g2, b2;
int i, j, imax, jmax, oval;
byte *inptr, *outptr, *tmpbptr;
int lastline, lastpixel;
imax = HIGH - 1;
jmax = WIDE - 1;
thisline = (int *) malloc(WIDE * 3 * sizeof(int));
nextline = (int *) malloc(WIDE * 3 * sizeof(int));
if (thisline == NULL || nextline == NULL) {
fprintf(stderr,"%s: unable to allocate stuff for the 'dither' routine\n",
cmd);
return 1;
}
inptr = (byte *) pic24;
outptr = (byte *) pic;
/* get first line of picture */
for (j=WIDE * 3, tmpptr=nextline, tmpbptr=inptr; j; j--)
*tmpptr++ = (int) *tmpbptr++;
for (i=0; i<HIGH; i++) {
/* swap thisline and nextline */
tmpptr = thisline; thisline = nextline; nextline = tmpptr;
lastline = (i==imax);
/* read in next line */
for (j=WIDE * 3, tmpptr=nextline; j; j--)
*tmpptr++ = (int) *inptr++;
/* dither this line and put it into the output picture */
thisptr = thisline; nextptr = nextline;
for (j=0; j<WIDE; j++) {
lastpixel = (j==jmax);
r2 = *thisptr++; g2 = *thisptr++; b2 = *thisptr++;
if (r2<0) r2=0; else if (r2>=MAX_COLOR) r2=MAX_COLOR-1;
if (g2<0) g2=0; else if (g2>=MAX_COLOR) g2=MAX_COLOR-1;
if (b2<0) b2=0; else if (b2>=MAX_COLOR) b2=MAX_COLOR-1;
r1 = r2; g1 = g2; b1 = b2;
r2 >>= (COLOR_DEPTH-B_DEPTH);
g2 >>= (COLOR_DEPTH-B_DEPTH);
b2 >>= (COLOR_DEPTH-B_DEPTH);
if ( (oval=histogram[r2][g2][b2]) == -1) {
int ci, cj, dist, d2, tmp;
CCELL *cell;
cell = *( ColorCells +
( ((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2)
+ ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH )
+ (b2>>(B_DEPTH-C_DEPTH)) ) );
if (cell==NULL) cell = create_colorcell(r1,g1,b1);
dist = 9999999;
for (ci=0; ci<cell->num_ents && dist>cell->entries[ci][1]; ci++) {
cj = cell->entries[ci][0];
d2 = (r[cj] >> (COLOR_DEPTH-B_DEPTH)) - r2;
d2 *= d2;
tmp = (g[cj] >> (COLOR_DEPTH-B_DEPTH)) - g2;
d2 += tmp*tmp;
tmp = (b[cj] >> (COLOR_DEPTH-B_DEPTH)) - b2;
d2 += tmp*tmp;
if (d2<dist) { dist = d2; oval = cj; }
}
histogram[r2][g2][b2] = oval;
}
*outptr++ = oval;
r1 -= r[oval]; g1 -= g[oval]; b1 -= b[oval];
/* can't use tables because r1,g1,b1 go negative */
if (!lastpixel) {
thisptr[0] += (r1*7)/16;
thisptr[1] += (g1*7)/16;
thisptr[2] += (b1*7)/16;
}
if (!lastline) {
if (j) {
nextptr[-3] += (r1*3)/16;
nextptr[-2] += (g1*3)/16;
nextptr[-1] += (b1*3)/16;
}
nextptr[0] += (r1*5)/16;
nextptr[1] += (g1*5)/16;
nextptr[2] += (b1*5)/16;
if (!lastpixel) {
nextptr[3] += r1/16;
nextptr[4] += g1/16;
nextptr[5] += b1/16;
}
nextptr += 3;
}
}
}
free(thisline); free(nextline);
return 0;
}
/************************************/
static int Quick24to8(p24,w,h)
byte *p24;
int w,h;
{
/* floyd-steinberg dithering.
*
* ---- x 7/16
* 3/16 5/16 1/16
*
*/
/* called after 'pic' has been alloced, pWIDE,pHIGH set up, mono/1-bit
checked already */
byte *pp;
int r1, g1, b1;
int *thisline, *nextline, *thisptr, *nextptr, *tmpptr;
int i, j, rerr, gerr, berr, pwide3;
int imax, jmax;
pp = pic; pwide3 = w * 3; imax = h-1; jmax = w-1;
/* load up colormap, 3 bits R, 3 bits G, 2 bits B (RRRGGGBB) */
for (i=0; i<256; i++) {
r[i] = ((i&0xe0) * 255) / 0xe0;
g[i] = ((i&0x1c) * 255) / 0x1c;
b[i] = ((i&0x03) * 255) / 0x03;
}
thisline = (int *) malloc(pwide3 * sizeof(int));
nextline = (int *) malloc(pwide3 * sizeof(int));
if (!thisline || !nextline) {
fprintf(stderr,"%s: unable to allocate memory in Quick24to8()\n", cmd);
return(1);
}
/* get first line of picture */
for (j=pwide3, tmpptr=nextline; j; j--) *tmpptr++ = (int) *p24++;
for (i=0; i<h; i++) {
tmpptr = thisline; thisline = nextline; nextline = tmpptr; /* swap */
if (i!=imax) /* get next line */
for (j=pwide3, tmpptr=nextline; j; j--)
*tmpptr++ = (int) *p24++;
for (j=0, thisptr=thisline, nextptr=nextline; j<w; j++,pp++) {
r1 = *thisptr++; g1 = *thisptr++; b1 = *thisptr++;
RANGE(r1,0,255); RANGE(g1,0,255); RANGE(b1,0,255);
rerr = r1 & 0x1f; gerr = g1 & 0x1f; berr = b1 & 0x3f;
*pp = (r1&0xe0) | ((g1>>3)&0x1c) | (b1>>6);
if (j!=jmax) { /* adjust RIGHT pixel */
thisptr[0] += tbl7[rerr];
thisptr[1] += tbl7[gerr];
thisptr[2] += tbl7[berr];
}
if (i!=imax) { /* do BOTTOM pixel */
nextptr[0] += tbl5[rerr];
nextptr[1] += tbl5[gerr];
nextptr[2] += tbl5[berr];
if (j>0) { /* do BOTTOM LEFT pixel */
nextptr[-3] += tbl3[rerr];
nextptr[-2] += tbl3[gerr];
nextptr[-1] += tbl3[berr];
}
if (j!=jmax) { /* do BOTTOM RIGHT pixel */
nextptr[3] += tbl1[rerr];
nextptr[4] += tbl1[gerr];
nextptr[5] += tbl1[berr];
}
nextptr += 3;
}
}
}
return 0;
}
/****************************/
void InitFSDTables()
/****************************/
{
int i;
for (i=0; i<256; i++) { /* initialize Floyd-Steinberg division tables */
tbl1[i] = i/16;
tbl3[i] = (3*i)/16;
tbl5[i] = (5*i)/16;
tbl7[i] = (7*i)/16;
}
}
/****************************/
static int QuickCheck(pic24,w,h,maxcol)
byte *pic24;
int w,h,maxcol;
{
/* scans picture until it finds more than 'maxcol' different colors. If it
finds more than 'maxcol' colors, it returns '0'. If it DOESN'T, it does
the 24-to-8 conversion by simply sticking the colors it found into
a colormap, and changing instances of a color in pic24 into colormap
indicies (in pic) */
unsigned long colors[256],col;
int i, nc, low, high, mid;
byte *p, *pix;
if (maxcol>256) maxcol = 256;
/* put the first color in the table by hand */
nc = 0; mid = 0;
for (i=w*h,p=pic24; i; i--) {
col = (*p++ << 16);
col += (*p++ << 8);
col += *p++;
/* binary search the 'colors' array to see if it's in there */
low = 0; high = nc-1;
while (low <= high) {
mid = (low+high)/2;
if (col < colors[mid]) high = mid - 1;
else if (col > colors[mid]) low = mid + 1;
else break;
}
if (high < low) { /* didn't find color in list, add it. */
/* WARNING: this is an overlapped memory copy. memcpy doesn't do
it correctly, hence 'bcopy', which claims to */
if (nc>=maxcol) return 0;
bcopy(&colors[low], &colors[low+1], (nc - low) * sizeof(unsigned long));
colors[low] = col;
nc++;
}
}
/* run through the data a second time, this time mapping pixel values in
pic24 into colormap offsets into 'colors' */
for (i=w*h,p=pic24, pix=pic; i; i--,pix++) {
col = (*p++ << 16);
col += (*p++ << 8);
col += *p++;
/* binary search the 'colors' array. It *IS* in there */
low = 0; high = nc-1;
while (low <= high) {
mid = (low+high)/2;
if (col < colors[mid]) high = mid - 1;
else if (col > colors[mid]) low = mid + 1;
else break;
}
if (high < low) {
fprintf(stderr,"QuickCheck: impossible!\n");
exit(1);
}
*pix = mid;
}
/* and load up the 'desired colormap' */
for (i=0; i<nc; i++) {
r[i] = colors[i]>>16;
g[i] = (colors[i]>>8) & 0xff;
b[i] = colors[i] & 0xff;
}
return 1;
}
\BARFOO\
else
echo "will not over write ./xv24to8.c"
fi
echo "Finished archive 8 of 10"
exit
dan
----------------------------------------------------
O'Reilly && Associates argv@sun.com / argv@ora.com
Opinions expressed reflect those of the author only.
--
dan
----------------------------------------------------
O'Reilly && Associates argv@sun.com / argv@ora.com
Opinions expressed reflect those of the author only.