1  /********************************************************************** <BR>


2  This file is part of Crack dot Com's free source code release of


3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


4  information about compiling & licensing issues visit this URL</a>


5  <PRE> If that doesn't help, contact Jonathan Clark at


6  golgotha_source@usa.net (Subject should have "GOLG" in it)


7  ***********************************************************************/


8 


9  #include "arch.hh"


10  #include "quantize/median.hh"


11  #include "quantize/histogram.hh"


12  #include <stdlib.h>


13  #include "memory/malloc.hh"


14 


15  // counts for each color, global so that it can be accessed by qsort function


16  static w32 *counts;


17 


18 


19  static int red_compare(const void *a, const void *b)


20  {


21  w16 color1=counts[*((w16 *)a)],


22  color2=counts[*((w16 *)b)];


23 


24  return ((sw32) ((color1 & ( (1  2  4  8  16) << 11))>>11))


25  ((sw32) ((color2 & ( (1  2  4  8  16) << 11))>>11));


26  }


27 


28 


29  static int green_compare(const void *a, const void *b)


30  {


31  w16 color1=counts[*((w16 *)a)],


32  color2=counts[*((w16 *)b)];


33 


34  return ((sw32) (color1 & ( (1  2  4  8  16  32) << 5)))


35  ((sw32) (color2 & ( (1  2  4  8  16  32) << 5)));


36  }


37 


38 


39  static int blue_compare(const void *a, const void *b)


40  {


41  w16 color1=counts[*((w16 *)a)],


42  color2=counts[*((w16 *)b)];


43 


44  return ((sw32) (color1 & ( (1  2  4  8  16) << 0)))


45  ((sw32) (color2 & ( (1  2  4  8  16) << 0)));


46  }


47 


48 


49  struct box


50  {


51  w32 index;


52  w32 colors;


53  w32 sum;


54  };


55 


56  static int box_compare(const void *a, const void *b)


57  {


58  return ((box *)b)>sum((box *)a)>sum;


59  }


60 


61  inline void _16_to_rgb(w32 rgb, w8 &r, w8 &g, w8 &b)


62  {


63  b=(rgb & (1  2  4  8  16))<<3;


64  rgb>>=5;


65 


66  g=(rgb & (1  2  4  8  16  32))<<2;


67  rgb>>=6;


68 


69  r=(rgb & (1  2  4  8  16))<<3;


70  }


71 


72  void i4_median_cut(i4_histogram_class *hist,


73  w32 skip_colors,


74  w32 t_colors,


75  w32 *return_palette)


76 


77  {


78  enum { HIST_SIZE=0x10000, // 16 bit histogram table


79  MAX_COLORS=256 };


80 


81  counts=hist>counts;


82 


83  box *box_list=(box *)i4_malloc(sizeof(box) * MAX_COLORS, "boxes");


84 


85  // setup the initial box


86  w32 total_boxes = 1;


87  box_list[0].index = 0;


88  box_list[0].colors = hist>tcolors;


89  box_list[0].sum = hist>total_pixels;


90 


91  w32 box_index;


92  w32 loop_count;


93 


94  // split boxes until we have all the colors


95  while ( total_boxes < t_colorsskip_colors )


96  {


97  // Find the first splittable box.


98  for ( box_index = 0; box_index < total_boxes; ++box_index )


99  if (box_list[box_index].colors >= 2)


100  break;


101 


102  if ( box_index == total_boxes)


103  break; /* ran out of colors! */


104 


105 


106  w32 start = box_list[box_index].index;


107  w32 end = start + box_list[box_index].colors;


108 


109  w8 min_r=0xff, max_r=0x00,


110  min_g=0xff, max_g=0x00,


111  min_b=0xff, max_b=0x00,


112  r,g,b;


113 


114 


115  // now find the minimum and maximum r g b values for this box


116  for (loop_count = start; loop_count<end; loop_count++)


117  {


118  _16_to_rgb(hist>reference[loop_count],r,g,b);


119 


120  if (r>max_r) max_r=r;


121  if (r<min_r) min_r=r;


122 


123  if (g>max_g) max_g=g;


124  if (g<min_g) min_g=g;


125 


126  if (b>max_b) max_b=b;


127  if (b<min_b) min_b=b;


128  }


129 


130 


131  // Find the largest dimension, and sort by that component.


132  if (((max_r  min_r) >= (max_g  min_g)) && ((max_r  min_r) >= (max_b  min_b)))


133  qsort(hist>reference + start,


134  endstart, // total elements to sort


135  sizeof(w16),


136  red_compare);


137  else if ( (max_g  min_g) >= (max_b  min_b) )


138  qsort(hist>reference + start,


139  endstart, // total elements to sort


140  sizeof(w16),


141  green_compare);


142  else


143  qsort(hist>reference + start,


144  endstart, // total elements to sort


145  sizeof(w16),


146  blue_compare);


147 


148 


149 


150  // now find the division which closest divides into an equal number of pixels


151  w32 low_count= counts[hist>reference[start]];


152  w32 mid_number=box_list[box_index].sum/2;


153 


154  for (loop_count = start+1; loop_count<end1 && low_count<mid_number ; loop_count++)


155  low_count+=counts[hist>reference[loop_count]];


156 


157 


158  // now split the box


159  box_list[total_boxes].index = loop_count;


160  box_list[total_boxes].colors = endloop_count;


161  box_list[total_boxes].sum = box_list[box_index].sumlow_count;


162  total_boxes++;


163 


164  box_list[box_index].colors= loop_countstart;


165  box_list[box_index].sum = low_count;


166 


167  // sort to bring the biggest boxes to the top


168  qsort(box_list, total_boxes, sizeof(box), box_compare );


169 


170  /* for (int z=0;z<total_boxes;z++)


171  {


172  printf("box #%d : index = %d, colors= %d, sum=%d\n",z,


173  box_list[z].index, box_list[z].colors, box_list[z].sum);


174  } */


175 


176  }


177 


178 


179  // we should have 256 boxes, we now need to choose a color for each box


180  // we do this by averaging all the colors within the box


181  w32 r_tot, g_tot, b_tot;


182  for (box_index = 0; box_index<total_boxesskip_colors; box_index++)


183  {


184  r_tot = g_tot = b_tot = 0;


185 


186  w32 start = box_list[box_index].index;


187  w32 end = start + box_list[box_index].colors;


188 


189  w8 r,g,b;


190  for (loop_count = start; loop_count < end; loop_count++)


191  {


192  _16_to_rgb(hist>reference[loop_count],r,g,b);


193 


194  r_tot+=r;


195  g_tot+=g;


196  b_tot+=b;


197  }


198 


199  r_tot/=(endstart);


200  g_tot/=(endstart);


201  b_tot/=(endstart);


202 


203  return_palette[box_index+skip_colors] = (r_tot<<16)


204  (g_tot<<8) 


205  b_tot;


206  }


207 


208  for (;box_index + skip_colors<t_colors; box_index++)


209  return_palette[box_index+skip_colors] = 0;


210 


211 


212  i4_free(box_list);


213 


214  }


215 

