src/kits/shared/ColorQuantizer.cpp

   1 /* === C R E D I T S  &  D I S C L A I M E R S ==============
   2  * Permission is given by the author to freely redistribute and include
   3  * this code in any program as long as this credit is given where due.
   4  *
   5  * CQuantizer (c)  1996-1997 Jeff Prosise
   6  *
   7  * 31/08/2003 Davide Pizzolato - www.xdp.it
   8  * - fixed minor bug in ProcessImage when bpp<=8
   9  * - better color reduction to less than 16 colors
  10  *
  11  * COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT
  12  * WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT
  13  * LIMITATION, WARRANTIES THAT THE COVERED CODE IS FREE OF DEFECTS,
  14  * MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE OR NON-INFRINGING. THE ENTIRE
  15  * RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED CODE IS WITH YOU.
  16  * SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL
  17  * DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY
  18  * SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN
  19  * ESSENTIAL PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED
  20  * HEREUNDER EXCEPT UNDER THIS DISCLAIMER.
  21  *
  22  * Use at your own risk!
  23  * ==========================================================
  24  *
  25  * Modified for use with Haiku by David Powell & Stephan Aßmus.
  26  */
  27 #include "ColorQuantizer.h"
  28
  29 #include <stddef.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32
  33
  34 static inline uint8
  35 clip(float component)
  36 {
  37         if (component > 255.0)
  38                 return 255;
  39
  40         return (uint8)(component + 0.5f);
  41 }
  42
  43 struct BColorQuantizer::Node {
  44         bool                    isLeaf;         // TRUE if node has no children
  45         uint32                  pixelCount;     // Number of pixels represented by this leaf
  46         uint32                  sumR;           // Sum of red components
  47         uint32                  sumG;           // Sum of green components
  48         uint32                  sumB;           // Sum of blue components
  49         uint32                  sumA;           // Sum of alpha components
  50         Node*                   child[8];       // Pointers to child nodes
  51         Node*                   next;           // Pointer to next reducible node
  52 };
  53
  54
  55 BColorQuantizer::BColorQuantizer(uint32 maxColors, uint32 bitsPerColor)
  56         : fTree(NULL),
  57           fLeafCount(0),
  58           fMaxColors(maxColors),
  59           fOutputMaxColors(maxColors),
  60           fBitsPerColor(bitsPerColor)
  61 {
  62         // override parameters if out of range
  63         if (fBitsPerColor > 8)
  64                 fBitsPerColor = 8;
  65
  66         if (fMaxColors < 16)
  67                 fMaxColors = 16;
  68
  69         for (int i = 0; i <= (int)fBitsPerColor; i++)
  70                 fReducibleNodes[i] = NULL;
  71 }
  72
  73
  74 BColorQuantizer::~BColorQuantizer()
  75 {
  76         if (fTree != NULL)
  77                 _DeleteTree(&fTree);
  78 }
  79
  80
  81 bool
  82 BColorQuantizer::ProcessImage(const uint8* const * rowPtrs, int width,
  83         int height)
  84 {
  85         for (int y = 0; y < height; y++) {
  86                 for (int x = 0; x < width; x += 3) {
  87                         uint8 b = rowPtrs[y][x];
  88                         uint8 g = rowPtrs[y][x + 1];
  89                         uint8 r = rowPtrs[y][x + 2];
  90                         _AddColor(&fTree, r, g, b, 0, fBitsPerColor, 0, &fLeafCount,
  91                                 fReducibleNodes);
  92
  93                         while (fLeafCount > fMaxColors)
  94                                 _ReduceTree(fBitsPerColor, &fLeafCount, fReducibleNodes);
  95                 }
  96         }
  97
  98         return true;
  99 }
 100
 101
 102 uint32
 103 BColorQuantizer::GetColorCount() const
 104 {
 105         return fLeafCount;
 106 }
 107
 108
 109 void
 110 BColorQuantizer::GetColorTable(RGBA* table) const
 111 {
 112         uint32 index = 0;
 113         if (fOutputMaxColors < 16) {
 114                 uint32 sums[16];
 115                 RGBA tmpPalette[16];
 116                 _GetPaletteColors(fTree, tmpPalette, &index, sums);
 117                 if (fLeafCount > fOutputMaxColors) {
 118                         for (uint32 j = 0; j < fOutputMaxColors; j++) {
 119                                 uint32 a = (j * fLeafCount) / fOutputMaxColors;
 120                                 uint32 b = ((j + 1) * fLeafCount) / fOutputMaxColors;
 121                                 uint32 nr = 0;
 122                                 uint32 ng = 0;
 123                                 uint32 nb = 0;
 124                                 uint32 na = 0;
 125                                 uint32 ns = 0;
 126                                 for (uint32 k = a; k < b; k++){
 127                                         nr += tmpPalette[k].r * sums[k];
 128                                         ng += tmpPalette[k].g * sums[k];
 129                                         nb += tmpPalette[k].b * sums[k];
 130                                         na += tmpPalette[k].a * sums[k];
 131                                         ns += sums[k];
 132                                 }
 133                                 table[j].r = clip((float)nr / ns);
 134                                 table[j].g = clip((float)ng / ns);
 135                                 table[j].b = clip((float)nb / ns);
 136                                 table[j].a = clip((float)na / ns);
 137                         }
 138                 } else {
 139                         memcpy(table, tmpPalette, fLeafCount * sizeof(RGBA));
 140                 }
 141         } else {
 142                 _GetPaletteColors(fTree, table, &index, NULL);
 143         }
 144 }
 145
 146
 147 // #pragma mark - private
 148
 149
 150 void
 151 BColorQuantizer::_AddColor(Node** _node, uint8 r, uint8 g, uint8 b, uint8 a,
 152         uint32 bitsPerColor, uint32 level, uint32* _leafCount,
 153         Node** reducibleNodes)
 154 {
 155         static const uint8 kMask[8]
 156                 = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
 157
 158         // If the node doesn't exist, create it.
 159         if (*_node == NULL)
 160                 *_node = _CreateNode(level, bitsPerColor, _leafCount, reducibleNodes);
 161
 162         // Update color information if it's a leaf node.
 163         if ((*_node)->isLeaf) {
 164                 (*_node)->pixelCount++;
 165                 (*_node)->sumR += r;
 166                 (*_node)->sumG += g;
 167                 (*_node)->sumB += b;
 168                 (*_node)->sumA += a;
 169         } else {
 170                 // Recurse a level deeper if the node is not a leaf.
 171                 int shift = 7 - level;
 172                 int index = (((r & kMask[level]) >> shift) << 2) |
 173                                          (((g & kMask[level]) >> shift) << 1) |
 174                                          (( b & kMask[level]) >> shift);
 175                 _AddColor(&((*_node)->child[index]), r, g, b, a, bitsPerColor,
 176                         level + 1, _leafCount, reducibleNodes);
 177         }
 178 }
 179
 180
 181 BColorQuantizer::Node*
 182 BColorQuantizer::_CreateNode(uint32 level, uint32 bitsPerColor,
 183         uint32* _leafCount, Node** reducibleNodes)
 184 {
 185         Node* node = (Node*)calloc(1, sizeof(Node));
 186
 187         if (node == NULL)
 188                 return NULL;
 189
 190         node->isLeaf = (level == bitsPerColor) ? true : false;
 191         if (node->isLeaf)
 192                 (*_leafCount)++;
 193         else {
 194                 node->next = reducibleNodes[level];
 195                 reducibleNodes[level] = node;
 196         }
 197         return node;
 198 }
 199
 200
 201 void
 202 BColorQuantizer::_ReduceTree(uint32 bitsPerColor, uint32* _leafCount,
 203         Node** reducibleNodes)
 204 {
 205         int i = bitsPerColor - 1;
 206         // Find the deepest level containing at least one reducible node.
 207         for (; i > 0 && reducibleNodes[i] == NULL; i--)
 208                 ;
 209
 210         // Reduce the node most recently added to the list at level i.
 211         Node* node = reducibleNodes[i];
 212         reducibleNodes[i] = node->next;
 213
 214         uint32 sumR = 0;
 215         uint32 sumG = 0;
 216         uint32 sumB = 0;
 217         uint32 sumA = 0;
 218         uint32 childCount = 0;
 219
 220         for (i = 0; i < 8; i++) {
 221                 if (node->child[i] != NULL) {
 222                         sumR += node->child[i]->sumR;
 223                         sumG += node->child[i]->sumG;
 224                         sumB += node->child[i]->sumB;
 225                         sumA += node->child[i]->sumA;
 226                         node->pixelCount += node->child[i]->pixelCount;
 227
 228                         free(node->child[i]);
 229                         node->child[i] = NULL;
 230
 231                         childCount++;
 232                 }
 233         }
 234
 235         node->isLeaf = true;
 236         node->sumR = sumR;
 237         node->sumG = sumG;
 238         node->sumB = sumB;
 239         node->sumA = sumA;
 240
 241         *_leafCount -= (childCount - 1);
 242 }
 243
 244
 245 void
 246 BColorQuantizer::_DeleteTree(Node** _node)
 247 {
 248         for (int i = 0; i < 8; i++) {
 249                 if ((*_node)->child[i] != NULL)
 250                         _DeleteTree(&((*_node)->child[i]));
 251         }
 252         free(*_node);
 253         *_node = NULL;
 254 }
 255
 256
 257 void
 258 BColorQuantizer::_GetPaletteColors(Node* node, RGBA* table, uint32* _index,
 259         uint32* sums) const
 260 {
 261         if (node == NULL)
 262                 return;
 263
 264         if (node->isLeaf) {
 265                 table[*_index].r = clip((float)node->sumR / node->pixelCount);
 266                 table[*_index].g = clip((float)node->sumG / node->pixelCount);
 267                 table[*_index].b = clip((float)node->sumB / node->pixelCount);
 268                 table[*_index].a = clip((float)node->sumA / node->pixelCount);
 269                 if (sums)
 270                         sums[*_index] = node->pixelCount;
 271                 (*_index)++;
 272         } else {
 273                 for (int i = 0; i < 8; i++) {
 274                         if (node->child[i] != NULL)
 275                                 _GetPaletteColors(node->child[i], table, _index, sums);
 276                 }
 277         }
 278 }
 279