diff src/imgproc.c @ 269:b2472a1930f2 r20-5b33

Import from CVS: tag r20-5b33
author cvs
date Mon, 13 Aug 2007 10:27:19 +0200
parents 966663fcf606
children c5d627a313b1
line wrap: on
line diff
--- a/src/imgproc.c	Mon Aug 13 10:26:31 2007 +0200
+++ b/src/imgproc.c	Mon Aug 13 10:27:19 2007 +0200
@@ -44,8 +44,9 @@
 #include "lisp.h"
 #include "imgproc.h"
 
-static void get_histogram(quant_table *qt, unsigned char *pic,
-			  int width, int height, Colorbox* box)
+static void
+get_histogram(quant_table *qt, unsigned char *pic,
+	      int width, int height, Colorbox* box)
 {
   register unsigned char *inptr;
   register int red, green, blue;
@@ -55,32 +56,29 @@
   box->rmax = box->gmax = box->bmax = -1;
   box->total = width * height;
 
-  {
- register int *ptr = &(qt->histogram[0][0][0]);
-  for (i = B_LEN*B_LEN*B_LEN; i-- > 0;)
-    *ptr++ = 0;
-  }
   inptr = pic;
-  for (i = 0; i < height; i++) {
-    for (j = width; j-- > 0;) {
-      red = *inptr++ >> COLOR_SHIFT;
-      green = *inptr++ >> COLOR_SHIFT;
-      blue = *inptr++ >> COLOR_SHIFT;
-      if (red < box->rmin)
-	box->rmin = red;
-      if (red > box->rmax)
-	box->rmax = red;
-      if (green < box->gmin)
-	box->gmin = green;
-      if (green > box->gmax)
-	box->gmax = green;
-      if (blue < box->bmin)
-	box->bmin = blue;
-      if (blue > box->bmax)
-	box->bmax = blue;
-      qt->histogram[red][green][blue]++;
+  for (i = 0; i < height; i++)
+    {
+      for (j = width; j-- > 0;)
+	{
+	  red = *inptr++ >> COLOR_SHIFT;
+	  green = *inptr++ >> COLOR_SHIFT;
+	  blue = *inptr++ >> COLOR_SHIFT;
+	  if (red < box->rmin)
+	    box->rmin = red;
+	  if (red > box->rmax)
+	    box->rmax = red;
+	  if (green < box->gmin)
+	    box->gmin = green;
+	  if (green > box->gmax)
+	    box->gmax = green;
+	  if (blue < box->bmin)
+	    box->bmin = blue;
+	  if (blue > box->bmax)
+	    box->bmax = blue;
+	  qt->histogram[red][green][blue]++;
+	}
     }
-  }
 }
 
 static Colorbox *
@@ -103,81 +101,98 @@
 {
   register int *histp, ir, ig, ib;
 
-  if (box->rmax > box->rmin) {
-    for (ir = box->rmin; ir <= box->rmax; ++ir)
-      for (ig = box->gmin; ig <= box->gmax; ++ig) {
-	histp = &(qt->histogram[ir][ig][box->bmin]);
-	for (ib = box->bmin; ib <= box->bmax; ++ib)
-	  if (*histp++ != 0) {
-	    box->rmin = ir;
-	    goto have_rmin;
+  if (box->rmax > box->rmin)
+    {
+      for (ir = box->rmin; ir <= box->rmax; ++ir)
+	for (ig = box->gmin; ig <= box->gmax; ++ig)
+	  {
+	    histp = &(qt->histogram[ir][ig][box->bmin]);
+	    for (ib = box->bmin; ib <= box->bmax; ++ib)
+	      if (*histp++ != 0)
+		{
+		  box->rmin = ir;
+		  goto have_rmin;
+		}
 	  }
-      }
-  have_rmin:
-    if (box->rmax > box->rmin)
-      for (ir = box->rmax; ir >= box->rmin; --ir)
-	for (ig = box->gmin; ig <= box->gmax; ++ig) {
-	  histp = &(qt->histogram[ir][ig][box->bmin]);
-	  ib = box->bmin;
-	  for (; ib <= box->bmax; ++ib)
-	    if (*histp++ != 0) {
-	      box->rmax = ir;
-	      goto have_rmax;
+    have_rmin:
+      if (box->rmax > box->rmin)
+	for (ir = box->rmax; ir >= box->rmin; --ir)
+	  for (ig = box->gmin; ig <= box->gmax; ++ig)
+	    {
+	      histp = &(qt->histogram[ir][ig][box->bmin]);
+	      ib = box->bmin;
+	      for (; ib <= box->bmax; ++ib)
+		if (*histp++ != 0)
+		  {
+		    box->rmax = ir;
+		    goto have_rmax;
+		  }
 	    }
-	}
-  }
+    }
  have_rmax:
-  if (box->gmax > box->gmin) {
-    for (ig = box->gmin; ig <= box->gmax; ++ig)
-      for (ir = box->rmin; ir <= box->rmax; ++ir) {
-	histp = &(qt->histogram[ir][ig][box->bmin]);
-	for (ib = box->bmin; ib <= box->bmax; ++ib)
-	  if (*histp++ != 0) {
-	    box->gmin = ig;
-	    goto have_gmin;
+  if (box->gmax > box->gmin)
+    {
+      for (ig = box->gmin; ig <= box->gmax; ++ig)
+	for (ir = box->rmin; ir <= box->rmax; ++ir)
+	  {
+	    histp = &(qt->histogram[ir][ig][box->bmin]);
+	    for (ib = box->bmin; ib <= box->bmax; ++ib)
+	      if (*histp++ != 0)
+		{
+		  box->gmin = ig;
+		  goto have_gmin;
+		}
 	  }
-      }
-  have_gmin:
-    if (box->gmax > box->gmin)
-      for (ig = box->gmax; ig >= box->gmin; --ig)
-	for (ir = box->rmin; ir <= box->rmax; ++ir) {
-	  histp = &(qt->histogram[ir][ig][box->bmin]);
-	  ib = box->bmin;
-	  for (; ib <= box->bmax; ++ib)
-	    if (*histp++ != 0) {
-	      box->gmax = ig;
-	      goto have_gmax;
+    have_gmin:
+      if (box->gmax > box->gmin)
+	for (ig = box->gmax; ig >= box->gmin; --ig)
+	  for (ir = box->rmin; ir <= box->rmax; ++ir)
+	    {
+	      histp = &(qt->histogram[ir][ig][box->bmin]);
+	      ib = box->bmin;
+	      for (; ib <= box->bmax; ++ib)
+		if (*histp++ != 0)
+		  {
+		    box->gmax = ig;
+		    goto have_gmax;
+		  }
 	    }
-	}
-  }
+    }
  have_gmax:
-  if (box->bmax > box->bmin) {
-    for (ib = box->bmin; ib <= box->bmax; ++ib)
-      for (ir = box->rmin; ir <= box->rmax; ++ir) {
-	histp = &(qt->histogram[ir][box->gmin][ib]);
-	for (ig = box->gmin; ig <= box->gmax; ++ig) {
-	  if (*histp != 0) {
-	    box->bmin = ib;
-	    goto have_bmin;
+  if (box->bmax > box->bmin)
+    {
+      for (ib = box->bmin; ib <= box->bmax; ++ib)
+	for (ir = box->rmin; ir <= box->rmax; ++ir)
+	  {
+	    histp = &(qt->histogram[ir][box->gmin][ib]);
+	    for (ig = box->gmin; ig <= box->gmax; ++ig)
+	      {
+		if (*histp != 0)
+		  {
+		    box->bmin = ib;
+		    goto have_bmin;
+		  }
+		histp += B_LEN;
+	      }
 	  }
-	  histp += B_LEN;
-	}
-      }
-  have_bmin:
-    if (box->bmax > box->bmin)
-      for (ib = box->bmax; ib >= box->bmin; --ib)
-	for (ir = box->rmin; ir <= box->rmax; ++ir) {
-	  histp = &(qt->histogram[ir][box->gmin][ib]);
-	  ig = box->gmin;
-	  for (; ig <= box->gmax; ++ig) {
-	    if (*histp != 0) {
-	      box->bmax = ib;
-	      goto have_bmax;
+    have_bmin:
+      if (box->bmax > box->bmin)
+	for (ib = box->bmax; ib >= box->bmin; --ib)
+	  for (ir = box->rmin; ir <= box->rmax; ++ir)
+	    {
+	      histp = &(qt->histogram[ir][box->gmin][ib]);
+	      ig = box->gmin;
+	      for (; ig <= box->gmax; ++ig)
+		{
+		  if (*histp != 0)
+		    {
+		      box->bmax = ib;
+		      goto have_bmax;
+		    }
+		  histp += B_LEN;
+		}
 	    }
-	    histp += B_LEN;
-	  }
-	}
-  }
+    }
  have_bmax:
   ;
 }
@@ -207,52 +222,60 @@
   else
     axis = BLUE;
   /* get histogram along longest axis */
-  switch (axis) {
-  case RED:
-    histp = &hist2[ptr->rmin];
-    for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
-      *histp = 0;
-      for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
-	iptr = &(qt->histogram[ir][ig][ptr->bmin]);
-	for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
-	  *histp += *iptr++;
-      }
-      histp++;
+  switch (axis)
+    {
+    case RED:
+      histp = &hist2[ptr->rmin];
+      for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
+	{
+	  *histp = 0;
+	  for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
+	    {
+	      iptr = &(qt->histogram[ir][ig][ptr->bmin]);
+	      for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
+		*histp += *iptr++;
+	    }
+	  histp++;
+	}
+      first = ptr->rmin;
+      last = ptr->rmax;
+      break;
+    case GREEN:
+      histp = &hist2[ptr->gmin];
+      for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
+	{
+	  *histp = 0;
+	  for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
+	    {
+	      iptr = &(qt->histogram[ir][ig][ptr->bmin]);
+	      for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
+		*histp += *iptr++;
+	    }
+	  histp++;
+	}
+      first = ptr->gmin;
+      last = ptr->gmax;
+      break;
+    case BLUE:
+      histp = &hist2[ptr->bmin];
+      for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
+	{
+	  *histp = 0;
+	  for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
+	    {
+	      iptr = &(qt->histogram[ir][ptr->gmin][ib]);
+	      for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
+		{
+		  *histp += *iptr;
+		  iptr += B_LEN;
+		}
+	    }
+	  histp++;
+	}
+      first = ptr->bmin;
+      last = ptr->bmax;
+      break;
     }
-    first = ptr->rmin;
-    last = ptr->rmax;
-    break;
-  case GREEN:
-    histp = &hist2[ptr->gmin];
-    for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
-      *histp = 0;
-      for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
-	iptr = &(qt->histogram[ir][ig][ptr->bmin]);
-	for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
-	  *histp += *iptr++;
-      }
-      histp++;
-    }
-    first = ptr->gmin;
-    last = ptr->gmax;
-    break;
-  case BLUE:
-    histp = &hist2[ptr->bmin];
-    for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
-      *histp = 0;
-      for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
-	iptr = &(qt->histogram[ir][ptr->gmin][ib]);
-	for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
-	  *histp += *iptr;
-	  iptr += B_LEN;
-	}
-      }
-      histp++;
-    }
-    first = ptr->bmin;
-    last = ptr->bmax;
-    break;
-  }
   /* find median point */
   sum2 = ptr->total / 2;
   histp = &hist2[first];
@@ -286,22 +309,23 @@
   new->gmax = ptr->gmax;
   new->bmin = ptr->bmin;
   new->bmax = ptr->bmax;
-  switch (axis) {
-  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(qt, new);
-  shrinkbox(qt, ptr);
+  switch (axis)
+    {
+    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 (qt, new);
+  shrinkbox (qt, ptr);
 }
 
 
@@ -325,71 +349,76 @@
    *	   it, find distance of centermost point to furthest corner
    */
   mindist = 99999999;
-  for (i = 0; i < num_colors; ++i) {
-    if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir  ||
-	qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig  ||
-	qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
-      continue;
-    ptr->entries[ptr->num_ents][0] = i;
-    ptr->entries[ptr->num_ents][1] = 0;
-    ++ptr->num_ents;
-    tmp = qt->rm[i] - red;
-    if (tmp < (MAX_COLOR/C_LEN/2))
-      tmp = MAX_COLOR/C_LEN-1 - tmp;
-    dist = tmp*tmp;
-    tmp = qt->gm[i] - green;
-    if (tmp < (MAX_COLOR/C_LEN/2))
-      tmp = MAX_COLOR/C_LEN-1 - tmp;
-    dist += tmp*tmp;
-    tmp = qt->bm[i] - blue;
-    if (tmp < (MAX_COLOR/C_LEN/2))
-      tmp = MAX_COLOR/C_LEN-1 - tmp;
-    dist += tmp*tmp;
-    if (dist < mindist)
-      mindist = dist;
-  }
+  for (i = 0; i < num_colors; ++i)
+    {
+      if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir  ||
+	  qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig  ||
+	  qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
+	continue;
+      ptr->entries[ptr->num_ents][0] = i;
+      ptr->entries[ptr->num_ents][1] = 0;
+      ++ptr->num_ents;
+      tmp = qt->rm[i] - red;
+      if (tmp < (MAX_COLOR/C_LEN/2))
+	tmp = MAX_COLOR/C_LEN-1 - tmp;
+      dist = tmp*tmp;
+      tmp = qt->gm[i] - green;
+      if (tmp < (MAX_COLOR/C_LEN/2))
+	tmp = MAX_COLOR/C_LEN-1 - tmp;
+      dist += tmp*tmp;
+      tmp = qt->bm[i] - blue;
+      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 cell.
    */
-  for (i = 0; i < num_colors; ++i) {
-    if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir  &&
-	qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig  &&
-	qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
-      continue;
-    dist = 0;
-    if ((tmp = red - qt->rm[i]) > 0 ||
-	(tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
-      dist += tmp*tmp;
-    if ((tmp = green - qt->gm[i]) > 0 ||
-	(tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
-      dist += tmp*tmp;
-    if ((tmp = blue - qt->bm[i]) > 0 ||
-	(tmp = qt->bm[i] - (blue + 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;
+  for (i = 0; i < num_colors; ++i)
+    {
+      if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir  &&
+	  qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig  &&
+	  qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
+	continue;
+      dist = 0;
+      if ((tmp = red - qt->rm[i]) > 0 ||
+	  (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
+	dist += tmp*tmp;
+      if ((tmp = green - qt->gm[i]) > 0 ||
+	  (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
+	dist += tmp*tmp;
+      if ((tmp = blue - qt->bm[i]) > 0 ||
+	  (tmp = qt->bm[i] - (blue + 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
    */
-  for (n = ptr->num_ents - 1; n > 0; n = next_n) {
-    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;
-      }
-  }
+  for (n = ptr->num_ents - 1; n > 0; n = next_n)
+    {
+      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;
+	  }
+    }
   return (ptr);
 }
 
@@ -403,48 +432,53 @@
 
   for (ir = 0; ir < B_LEN; ++ir)
     for (ig = 0; ig < B_LEN; ++ig)
-      for (ib = 0; ib < B_LEN; ++ib, histp++) {
-	if (*histp == 0) {
-	  *histp = -1;
-	  continue;
+      for (ib = 0; ib < B_LEN; ++ib, histp++)
+	{
+	  if (*histp == 0)
+	    {
+	      *histp = -1;
+	      continue;
+	    }
+	  cell = *(qt->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 (qt, num_colors,
+				     ir << COLOR_SHIFT,
+				     ig << COLOR_SHIFT,
+				     ib << COLOR_SHIFT);
+	  if (cell == NULL) /* memory exhausted! punt! */
+	    return -1;
+	  dist = 9999999;
+	  for (i = 0; i < cell->num_ents &&
+		 dist > cell->entries[i][1]; ++i)
+	    {
+	      j = cell->entries[i][0];
+	      d2 = qt->rm[j] - (ir << COLOR_SHIFT);
+	      d2 *= d2;
+	      tmp = qt->gm[j] - (ig << COLOR_SHIFT);
+	      d2 += tmp*tmp;
+	      tmp = qt->bm[j] - (ib << COLOR_SHIFT);
+	      d2 += tmp*tmp;
+	      if (d2 < dist)
+		{
+		  dist = d2;
+		  *histp = j;
+		}
+	    }
 	}
-	cell = *(qt->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(qt, num_colors,
-				  ir << COLOR_SHIFT,
-				  ig << COLOR_SHIFT,
-				  ib << COLOR_SHIFT);
-	if (cell == NULL) /* memory exhausted! punt! */
-	  return -1;
-	dist = 9999999;
-	for (i = 0; i < cell->num_ents &&
-	       dist > cell->entries[i][1]; ++i) {
-	  j = cell->entries[i][0];
-	  d2 = qt->rm[j] - (ir << COLOR_SHIFT);
-	  d2 *= d2;
-	  tmp = qt->gm[j] - (ig << COLOR_SHIFT);
-	  d2 += tmp*tmp;
-	  tmp = qt->bm[j] - (ib << COLOR_SHIFT);
-	  d2 += tmp*tmp;
-	  if (d2 < dist) {
-	    dist = d2;
-	    *histp = j;
-	  }
-	}
-      }
   return 0;
 }
 
-quant_table *EImage_build_quantable(unsigned char *eimage, int width, int height, int num_colors)
+quant_table *
+build_EImage_quantable(unsigned char *eimage, int width, int height, int num_colors)
 {
   quant_table *qt;
   Colorbox *box_list, *ptr;
   int i,res;
 
-  qt = (quant_table*)xmalloc(sizeof(quant_table));
+  qt = (quant_table*)xmalloc_and_zero (sizeof(quant_table));
   if (qt == NULL) return NULL;
 
   assert (num_colors < 257 && num_colors > 2);
@@ -452,13 +486,14 @@
    * STEP 1:  create empty boxes
    */
   qt->usedboxes = NULL;
-  box_list = qt->freeboxes = (Colorbox *)xmalloc(num_colors*sizeof (Colorbox));
+  box_list = qt->freeboxes = (Colorbox *)xmalloc (num_colors*sizeof (Colorbox));
   qt->freeboxes[0].next = &(qt->freeboxes[1]);
   qt->freeboxes[0].prev = NULL;
-  for (i = 1; i < num_colors-1; ++i) {
-    qt->freeboxes[i].next = &(qt->freeboxes[i+1]);
-    qt->freeboxes[i].prev = &(qt->freeboxes[i-1]);
-  }
+  for (i = 1; i < num_colors-1; ++i)
+    {
+      qt->freeboxes[i].next = &(qt->freeboxes[i+1]);
+      qt->freeboxes[i].prev = &(qt->freeboxes[i-1]);
+    }
   qt->freeboxes[num_colors-1].next = NULL;
   qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]);
 
@@ -473,54 +508,57 @@
   qt->usedboxes = ptr;
   if (ptr->next)
     ptr->next->prev = ptr;
-  get_histogram(qt, eimage, width, height, ptr);
+  get_histogram (qt, eimage, width, height, ptr);
 
   /*
    * STEP 3: continually subdivide boxes until no more free
    * boxes remain or until all colors assigned.
    */
-  while (qt->freeboxes != NULL) {
-    ptr = largest_box(qt);
-    if (ptr != NULL)
-      splitbox(qt, ptr);
-    else
-      qt->freeboxes = NULL;
-  }
+  while (qt->freeboxes != NULL)
+    {
+      ptr = largest_box(qt);
+      if (ptr != NULL)
+	splitbox (qt, ptr);
+      else
+	qt->freeboxes = NULL;
+    }
 
   /*
    * STEP 4: assign colors to all boxes
    */
-  for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) {
-    qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
-    qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
-    qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
-    qt->um[i] = ptr->total;
-  }
+  for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next)
+    {
+      qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
+      qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
+      qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
+      qt->um[i] = ptr->total;
+    }
   qt->num_active_colors = i;
 
   /* We're done with the boxes now */
-  xfree(box_list);
+  xfree (box_list);
   qt->freeboxes = qt->usedboxes = NULL;
 
   /*
    * STEP 5: scan histogram and map all values to closest color
    */
   /* 5a: create cell list as described in Heckbert */
-  qt->ColorCells = (C_cell **)xmalloc(C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
-  memset(qt->ColorCells, 0, C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
+  qt->ColorCells = (C_cell **)xmalloc_and_zero (C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
   /* 5b: create mapping from truncated pixel space to color
      table entries */
-  res = map_colortable(qt, num_colors);
+  res = map_colortable (qt, num_colors);
 
   /* 5c: done with ColorCells */
-  for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) if (qt->ColorCells[i]) xfree(qt->ColorCells[i]);
-  xfree(qt->ColorCells);
+  for (i = 0; i < C_LEN*C_LEN*C_LEN; i++)
+    if (qt->ColorCells[i]) xfree (qt->ColorCells[i]);
+  xfree (qt->ColorCells);
   
-  if (res) {
-    /* we failed in memory allocation, so clean up an leave */
-    xfree(qt);
-    return NULL;
-  }
+  if (res)
+    {
+      /* we failed in memory allocation, so clean up an leave */
+      xfree(qt);
+      return NULL;
+    }
   
   return qt;
 }