From 6c9ccb5327ef4ce3cea52c0ac8326bdeb787fb54 Mon Sep 17 00:00:00 2001
From: giraffedata <giraffedata@9d0c8265-081b-0410-96cb-a4ca84ce46f8>
Date: Sun, 8 Jul 2012 19:51:06 +0000
Subject: cleanup

git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@1711 9d0c8265-081b-0410-96cb-a4ca84ce46f8
---
 converter/ppm/ppmtospu.c | 60 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 41 insertions(+), 19 deletions(-)

(limited to 'converter/ppm/ppmtospu.c')

diff --git a/converter/ppm/ppmtospu.c b/converter/ppm/ppmtospu.c
index 2532f28f..e6b737a8 100644
--- a/converter/ppm/ppmtospu.c
+++ b/converter/ppm/ppmtospu.c
@@ -5,6 +5,7 @@
  *  Copyright (C) 1990, Steve Belczyk
  */
 
+#include <assert.h>
 #include <stdio.h>
 
 #include "pm_c_util.h"
@@ -82,10 +83,10 @@ parseCommandLine(int argc, const char ** argv,
 
 /* This is the stuff to remember about each pixel */
 struct PixelType {
-    int index4;  /* 4-bit color, used in bitmap */
-    int x;       /* Pixel's original x-position */
-    int pop;     /* Popularity of this pixel's color */
-    int color9;  /* 9-bit color this pixel actually got */
+    unsigned int index4;      /* 4-bit color, used in bitmap */
+    unsigned int x;           /* Pixel's original x-position */
+    unsigned int popularity;  /* Popularity of this pixel's color */
+    unsigned int color9;      /* 9-bit color this pixel actually got */
 };
 
 
@@ -216,35 +217,56 @@ dither(unsigned int       const row,
 
 
 
+static void
+swapPixelType(struct PixelType *  const pixelType,
+              unsigned int        const i,
+              unsigned int        const j) {
+
+    struct PixelType const w = pixelType[i];
+
+    pixelType[i] = pixelType[j];
+    pixelType[j] = w;
+}
+
+
+
 static void
 sort(struct PixelType * const pixelType,
      unsigned int       const left,
      unsigned int       const right) {
 /*----------------------------------------------------------------------------
-  Sort pixelType[] from element 'left' to element 'right'
-  Good ol' Quicksort
+  Sort pixelType[] from element 'left' through element 'right' in increasing
+  popularity.
+
+  Good ol' Quicksort.
 -----------------------------------------------------------------------------*/
-    struct PixelType x;
+    unsigned int const pivot = pixelType[(left+right)/2].popularity;
+
     int i, j;
     
-    i = left;
-    j = right;
-    x = pixelType[(left+right)/2];
-    
-    do {
-        while(pixelType[i].pop < x.pop)
+    /* Rearrange so that everything less than 'pivot' is on the left side of
+       the subject array slice, while everything else is on the right side (we
+       won't know until we're done where the dividing line between the sides
+       is), then sort those two sides.
+    */
+
+    assert(left <= right);
+
+    for (i = left, j = right; i <= j; ) {
+        while (pixelType[i].popularity < pivot)
             ++i;
-        while(x.pop < pixelType[j].pop)
+        while (pixelType[j].popularity >= pivot)
             --j;
         
         if (i <= j) {
-            struct PixelType const w = pixelType[i];
-            pixelType[i] = pixelType[j];
-            pixelType[j] = w;
+            /* A pixel not less popular than pivot is to the left of a pixel
+               less popular than pivot, so swap them.
+            */
+            swapPixelType(pixelType, i, j);
             ++i;
             --j;
         }
-    } while (i <= j);
+    }
     
     if (left < j)
         sort(pixelType, left, j);
@@ -273,7 +295,7 @@ computePalette(struct PixelType * const pixelType) {
 
     /* Set the popularity of each pixel's color */
     for (col = 0; col < 320; ++col)
-        pixelType[col].pop = hist[pixelType[col].color9];
+        pixelType[col].popularity = hist[pixelType[col].color9];
 
     /* Sort to find the most popular colors */
     sort(pixelType, 0, 319);
-- 
cgit 1.4.1