Main Page | Alphabetical List | Compound List | File List | Compound Members | File Members

palettize.c File Reference

#include "palettize.h"
#include <stdlib.h>
#include <assert.h>
#include "ram.h"
#include "mempool.h"

Go to the source code of this file.

Compounds

struct  hashNode
struct  octNode
struct  palInfo

Defines

#define new(type)   geRam_AllocateClear(sizeof(type))
#define allocate(ptr)   ptr = geRam_AllocateClear(sizeof(*ptr))
#define clear(ptr)   memset(ptr,0,sizeof(*ptr))
#define destroy(ptr)   if ( ptr ) { geRam_Free(ptr); (ptr) = NULL; } else
#define QUANT_BITS   (4)
#define QUANT_SHIFT   (8-QUANT_BITS)
#define QUANT_ROUND   (1<<(QUANT_SHIFT-1))
#define HASH_BITS   (QUANT_BITS*3)
#define HASH_SIZE   (1<<HASH_BITS)
#define HASH(R, G, B)   ( (((R)>>QUANT_SHIFT)<<(QUANT_BITS+QUANT_BITS)) + (((G)>>QUANT_SHIFT)<<(QUANT_BITS)) + (((B)>>QUANT_SHIFT)))
#define HASHROUNDED(R, G, B)   ( (((R+QUANT_ROUND)>>QUANT_SHIFT)<<(QUANT_BITS+QUANT_BITS)) + (((G+QUANT_ROUND)>>QUANT_SHIFT)<<(QUANT_BITS)) + (((B+QUANT_ROUND)>>QUANT_SHIFT)))
#define RGBbits(R, G, B, bits)   (((((R)>>(bits))&1)<<2) + ((((G)>>(bits))&1)<<1) + (((B)>>((bits)))&1))
#define doStep(bits)
#define doSteps()   do { node = pi->root; doStep(7); doStep(6); doStep(5); doStep(4); doStep(3); doStep(2); doStep(1); doStep(0); } while(0)

Typedefs

typedef palInfo palInfo
typedef octNode octNode
typedef hashNode hashNode

Functions

int __inline closestPalInlineRGB (int R, int G, int B, palInfo *pi)
int closestPal (int R, int G, int B, palInfo *pi)
palInfo * closestPalInit (uint8 *palette)
void closestPalFree (palInfo *info)
geBoolean palettizePlane (const geBitmap_Info *SrcInfo, const void *SrcBits, geBitmap_Info *DstInfo, void *DstBits, int SizeX, int SizeY)
int colorDistance (uint8 *ca, uint8 *cb)
int findClosestPalBrute (int R, int G, int B, palInfo *pi)
void addOctNode (octNode *root, int R, int G, int B, int palVal)
void addHash (palInfo *pi, int R, int G, int B, int palVal, int hash)
void Palettize_Start (void)
void Palettize_Stop (void)
int findClosestPal (int R, int G, int B, palInfo *pi)

Variables

MemPool * octNodePool = NULL
MemPool * hashNodePool = NULL
int PoolRefs = 0

Define Documentation

#define allocate (  ptr   )     ptr = geRam_AllocateClear(sizeof(*ptr))
 

Definition at line 53 of file palettize.c.

#define clear (  ptr   )     memset(ptr,0,sizeof(*ptr))
 

Definition at line 54 of file palettize.c.

#define destroy (  ptr   )     if ( ptr ) { geRam_Free(ptr); (ptr) = NULL; } else
 

Definition at line 55 of file palettize.c.

Referenced by closestPalFree(), createPaletteFast(), createPaletteGoodSub(), Hash_Destroy(), and Stack_Destroy().

#define doStep (  bits   ) 
 

Value:

do { kid = (node)->kids[ RGBbits(R,G,B,bits) ]; \
                                if ( kid ) node = kid; else return findClosestPal(R,G,B,pi); } while(0)

Definition at line 447 of file palettize.c.

 
#define doSteps (   )     do { node = pi->root; doStep(7); doStep(6); doStep(5); doStep(4); doStep(3); doStep(2); doStep(1); doStep(0); } while(0)
 

Definition at line 450 of file palettize.c.

Referenced by closestPal(), and closestPalInlineRGB().

#define HASH (  R,
G,
B   )     ( (((R)>>QUANT_SHIFT)<<(QUANT_BITS+QUANT_BITS)) + (((G)>>QUANT_SHIFT)<<(QUANT_BITS)) + (((B)>>QUANT_SHIFT)))
 

Definition at line 307 of file palettize.c.

Referenced by closestPalInit(), Hash_Add(), and Hash_Get().

#define HASH_BITS   (QUANT_BITS*3)
 

Definition at line 305 of file palettize.c.

#define HASH_SIZE   (1<<HASH_BITS)
 

Definition at line 306 of file palettize.c.

Referenced by addHash(), closestPalInit(), findClosestPal(), Hash_Add(), Hash_Create(), Hash_DeleteNode(), Hash_Get(), Hash_NumMembers(), and Hash_WalkNext().

#define HASHROUNDED (  R,
G,
B   )     ( (((R+QUANT_ROUND)>>QUANT_SHIFT)<<(QUANT_BITS+QUANT_BITS)) + (((G+QUANT_ROUND)>>QUANT_SHIFT)<<(QUANT_BITS)) + (((B+QUANT_ROUND)>>QUANT_SHIFT)))
 

Definition at line 308 of file palettize.c.

Referenced by findClosestPal().

#define new (  type   )     geRam_AllocateClear(sizeof(type))
 

Definition at line 52 of file palettize.c.

#define QUANT_BITS   (4)
 

Definition at line 302 of file palettize.c.

Referenced by addHash().

#define QUANT_ROUND   (1<<(QUANT_SHIFT-1))
 

Definition at line 304 of file palettize.c.

#define QUANT_SHIFT   (8-QUANT_BITS)
 

Definition at line 303 of file palettize.c.

#define RGBbits (  R,
G,
B,
bits   )     (((((R)>>(bits))&1)<<2) + ((((G)>>(bits))&1)<<1) + (((B)>>((bits)))&1))
 

Definition at line 337 of file palettize.c.

Typedef Documentation

typedef struct hashNode hashNode
 

typedef struct octNode octNode
 

Definition at line 310 of file palettize.c.

typedef struct palInfo palInfo
 

Definition at line 59 of file palettize.c.

Referenced by closestPalInit(), paletteOptimize(), and palettizePlane().

Function Documentation

void addHash (  palInfo *  pi,
int  R,
int  G,
int  B,
int  palVal,
int  hash
) 
 

Definition at line 543 of file palettize.c.

References B, hashNode::B, G, hashNode::G, palInfo::hash, HASH_SIZE, hashNodePool, MemPool_GetHunk(), hashNode::next, hashNode::pal, QUANT_BITS, R, and hashNode::R.

Referenced by closestPalInit(). 

00544 {
00545 hashNode *node;
00546 int i,h;
00547 
00548         for(i=0;i<8;i++) 
00549         {
00550                 h = hash + (i&1) + (((i>>1)&1)<<QUANT_BITS) + ((i>>2)<<(QUANT_BITS+QUANT_BITS));
00551                 if ( h <= HASH_SIZE ) 
00552                 {
00553                         node = MemPool_GetHunk(hashNodePool);
00554                         assert(node);
00555                         node->next = pi->hash[h];
00556                         pi->hash[h] = node;
00557                         node->R = R;
00558                         node->G = G;
00559                         node->B = B;
00560                         node->pal = palVal;
00561                 }
00562         }
00563 }

void addOctNode (  octNode *  root,
int  R,
int  G,
int  B,
int  palVal
) 
 

Definition at line 523 of file palettize.c.

References B, G, octNode::kids, MemPool_GetHunk(), octNode, octNodePool, octNode::parent, R, and RGBbits.

Referenced by closestPalInit(), createOctTree(), and findClosestPal(). 

00524 {
00525 int idx;
00526 int bits;
00527 octNode *node = root;
00528 
00529         for(bits=7;bits>0;bits--) 
00530         {
00531                 idx = RGBbits(R,G,B,bits);
00532                 if ( ! node->kids[idx] ) 
00533                 {
00534                         node->kids[idx] = MemPool_GetHunk(octNodePool);
00535                         node->kids[idx]->parent = node;
00536                 }
00537                 node = node->kids[idx];
00538         }
00539         idx = RGBbits(R,G,B,0);
00540         node->kids[idx] = (octNode *)(palVal+1);
00541 }

int closestPal (  int  R,
int  G,
int  B,
palInfo *  pi
) 
 

Definition at line 461 of file palettize.c.

References doSteps, and octNode. 

00462 {
00463 octNode *node,*kid;
00464 
00465         doSteps();
00466 
00467         assert( ((int)node) <= 256 && ((int)node) > 0 );
00468 
00469 return ((int)node)-1;
00470 }

void closestPalFree (  palInfo *  info  ) 
 

Definition at line 472 of file palettize.c.

References destroy, hashNodePool, MemPool_Reset(), and octNodePool. 

00473 {
00474 
00475         assert(pi);
00476         
00477         MemPool_Reset(octNodePool);
00478         MemPool_Reset(hashNodePool);
00479 
00480         destroy(pi);
00481 }

palInfo * closestPalInit (  uint8 *  palette  ) 
 

Definition at line 368 of file palettize.c.

References addHash(), addOctNode(), B, G, HASH, HASH_SIZE, MemPool_GetHunk(), NULL, octNodePool, palInfo::palette, palInfo, R, and palInfo::root. 

00369 {
00370 palInfo *pi;
00371 int i;
00372 
00373         i = HASH_SIZE;
00374 
00375         if ( (pi = new(palInfo)) == NULL )
00376                 return NULL;
00377 
00378         pi->palette = palette;
00379 
00380         pi->root = MemPool_GetHunk(octNodePool);
00381         assert(pi->root);
00382 
00383         for(i=0;i<256;i++) 
00384         {
00385                 int R,G,B;
00386                 R = palette[3*i]; G = palette[3*i+1]; B = palette[3*i+2];
00387                 addOctNode(pi->root,R,G,B,i);
00388                 addHash(pi,R,G,B,i,HASH(R,G,B));
00389         }
00390 
00391 return pi;
00392 }

int __inline closestPalInlineRGB (  int  R,
int  G,
int  B,
palInfo *  pi
) 
 

Definition at line 452 of file palettize.c.

References doSteps, and octNode.

Referenced by palettizePlane(). 

00453 {
00454 octNode *node,*kid;
00455 
00456         doSteps();
00457 
00458 return ((int)node)-1;
00459 }

int colorDistance (  uint8 *  ca,
uint8 *  cb
) 
 

Definition at line 510 of file palettize.c.

Referenced by findClosestPalBrute(). 

00511 {
00512 int d,x;
00513         d = 0;
00514         x = ca[0] - cb[0];
00515         d += x*x;
00516         x = ca[1] - cb[1];
00517         d += x*x;
00518         x = ca[2] - cb[2];
00519         d += x*x;
00520 return d;
00521 }

int findClosestPal (  int  R,
int  G,
int  B,
palInfo *  pi
) 
 

Definition at line 394 of file palettize.c.

References addOctNode(), hashNode::B, B, findClosestPalBrute(), hashNode::G, G, palInfo::hash, HASH_SIZE, hashNodePool, HASHROUNDED, MemPool_GetHunk(), hashNode::next, hashNode::pal, hashNode::R, R, and palInfo::root. 

00395 {
00396 hashNode *node;
00397 int hash,d,bestD,bestP;
00398 
00399         hash = HASHROUNDED(R,G,B);
00400         if ( hash > HASH_SIZE ) hash = HASH_SIZE;
00401 
00402         node = pi->hash[ hash ];
00403         if ( ! node ) 
00404         {
00405                 bestP = findClosestPalBrute(R,G,B,pi);
00406 #if 1
00407                 // helps speed a little; depends on how common individual RGB values are
00408                 // (makes it so that if we see this exact RGB again we return bestP right away)
00409                 addOctNode(pi->root,R,G,B,bestP);
00410 #endif
00411 #if 0
00412                 //this could help speed, but actually makes this method approximate
00413                 node = MemPool_GetHunk(hashNodePool);
00414                 assert(node);
00415                 node->next = pi->hash[hash];
00416                 pi->hash[hash] = node;
00417                 node->R = R;
00418                 node->G = G;
00419                 node->B = B;
00420                 node->pal = bestP;
00421 #endif
00422                 return bestP;
00423         }
00424 
00425         bestD = 99999999;       bestP = node->pal;
00426         while(node) 
00427         {
00428                 d = (R - node->R)*(R - node->R) + (G - node->G)*(G - node->G) + (B - node->B)*(B - node->B);
00429                 if ( d < bestD ) 
00430                 {
00431                         bestD = d;
00432                         bestP = node->pal;
00433                 }
00434                 node = node->next;
00435         }
00436 
00437 #if 1
00438         // <> ?
00439         // helps speed a little; depends on how common individual RGB values are
00440         // (makes it so that if we see this exact RGB again we return bestP right away)
00441         addOctNode(pi->root,R,G,B,bestP);
00442 #endif
00443 
00444         return bestP;
00445 }

int findClosestPalBrute (  int  R,
int  G,
int  B,
palInfo *  pi
) 
 

Definition at line 484 of file palettize.c.

References B, colorDistance(), G, palInfo::palette, R, and uint8.

Referenced by findClosestPal(). 

00485 {
00486 int d,p;
00487 int bestD,bestP;
00488 uint8 * pal;
00489 uint8 color[3];
00490 
00491         // now do a brute-force best-pal search to find the best pal entry
00492 
00493         color[0] = R;   color[1] = G;   color[2] = B;
00494         pal = pi->palette;
00495         bestD = colorDistance(color,pal);
00496         bestP = 0;
00497         for(p=1;p<256;p++)
00498         {
00499                 pal += 3;
00500                 d = colorDistance(color,pal);
00501                 if ( d < bestD ) 
00502                 {
00503                         bestD = d;
00504                         bestP = p;
00505                 }
00506         }
00507 return bestP;
00508 }

void Palettize_Start (  void   ) 
 

Definition at line 343 of file palettize.c.

References hashNodePool, MemPool_Create(), octNode, octNodePool, and PoolRefs.

Referenced by geBitmap_Start(). 

00344 {
00345         if ( PoolRefs == 0 )
00346         {
00347                 // we init with 256 octnodes, then add one for each unique color
00348                 octNodePool = MemPool_Create(sizeof(octNode),1024,1024);
00349                 assert(octNodePool);
00350                 hashNodePool = MemPool_Create(sizeof(hashNode),1024,1024);
00351                 assert(hashNodePool);
00352         }
00353         PoolRefs ++;
00354 }

void Palettize_Stop (  void   ) 
 

Definition at line 356 of file palettize.c.

References hashNodePool, MemPool_Destroy(), octNodePool, and PoolRefs.

Referenced by geBitmap_Stop(). 

00357 {
00358         PoolRefs --;
00359         if ( PoolRefs == 0 )
00360         {
00361                 MemPool_Destroy(&octNodePool);
00362                 MemPool_Destroy(&hashNodePool);
00363         }
00364 }

geBoolean palettizePlane (  const geBitmap_Info *  SrcInfo,
const void *  SrcBits,
geBitmap_Info *  DstInfo,
void *  DstBits,
int  SizeX,
int  SizeY
) 
 

Definition at line 68 of file palettize.c.

References A, B, closestPalFree(), closestPalInit(), closestPalInlineRGB(), geBitmap_Info::ColorKey, gePixelFormat_Operations::DecomposePixel, DstInfo, geBitmap_Info::Format, G, GE_FALSE, GE_PIXELFORMAT_24BIT_BGR, GE_PIXELFORMAT_24BIT_RGB, GE_PIXELFORMAT_8BIT_PAL, GE_TRUE, geBitmap_Palette_GetData(), geBoolean, gePixelFormat, gePixelFormat_BytesPerPel(), gePixelFormat_ColorGetter, gePixelFormat_Decomposer, gePixelFormat_GetOperations(), gePixelFormat_HasAlpha(), gePixelFormat_IsRaw(), gePixelFormat_PixelGetter, gePixelFormat_Operations::GetColor, gePixelFormat_Operations::GetPixel, geBitmap_Info::HasColorKey, palInfo, pushTSC, R, showPopTSC, SizeX, SizeY, geBitmap_Info::Stride, uint32, uint8, and y.

Referenced by BlitData_Palettize(). 

00071 {
00072 palInfo *palInfo;
00073 int x,y,xtra,bpp;
00074 gePixelFormat Format;
00075 int R,G,B,A;
00076 uint8 palette[768],*pSrc,*pDst;
00077 
00078         assert( SrcInfo && SrcBits );
00079         assert( DstInfo && DstBits );
00080 
00081         assert( DstInfo->Format == GE_PIXELFORMAT_8BIT_PAL );
00082         assert( gePixelFormat_IsRaw(SrcInfo->Format) );
00083 
00084         if ( ! DstInfo->Palette )
00085                 return GE_FALSE;
00086 
00087         if ( ! geBitmap_Palette_GetData(DstInfo->Palette,palette,GE_PIXELFORMAT_24BIT_RGB,256) )
00088                 return GE_FALSE;
00089 
00090 #ifdef _TSC
00091         pushTSC();
00092 #endif
00093 
00094         // rgbPlane is (planeLen*3) bytes
00095         // palette is 768 bytes
00096 
00097         palInfo = closestPalInit(palette);
00098         if ( ! palInfo ) return GE_FALSE;
00099 
00100         Format = SrcInfo->Format;
00101         bpp = gePixelFormat_BytesPerPel(Format);
00102         xtra = (SrcInfo->Stride - SizeX) * bpp;
00103         pSrc = (uint8 *)SrcBits;
00104         pDst = DstBits;
00105 
00106         if ( DstInfo->HasColorKey )
00107         {
00108         int DstCK;
00109         const gePixelFormat_Operations * ops;
00110                 ops = gePixelFormat_GetOperations(Format);
00111                 assert(ops);
00112                 DstCK = DstInfo->ColorKey;
00113 
00114                 if ( gePixelFormat_HasAlpha(Format) )   
00115                 {
00116                 gePixelFormat_ColorGetter GetColor;
00117                         GetColor = ops->GetColor;
00118                         for(y=SizeY;y--;)
00119                         {
00120                                 for(x=SizeX;x--;)
00121                                 {
00122                                         GetColor(&pSrc,&R,&G,&B,&A);
00123                                         if ( A < 128 )
00124                                         {
00125                                                 *pDst++ = DstCK;
00126                                         }
00127                                         else
00128                                         {
00129                                                 *pDst = closestPalInlineRGB(R,G,B,palInfo);
00130                                                 if ( *pDst == DstCK ) // {} this is really poor color-key avoidance!
00131                                                         *pDst ^= 1;
00132                                                 pDst++;
00133                                         }
00134                                 }
00135                                 pSrc += xtra;
00136                                 pDst += DstInfo->Stride - SizeX;
00137                         }
00138                 }
00139                 else if ( SrcInfo->HasColorKey )
00140                 {
00141                 uint32 SrcCK,Pixel;
00142                 gePixelFormat_PixelGetter GetPixel;
00143                 gePixelFormat_Decomposer DecomposePixel;
00144                         DecomposePixel = ops->DecomposePixel;
00145                         GetPixel = ops->GetPixel;
00146 
00147                         SrcCK = SrcInfo->ColorKey;
00148 
00149                         for(y=SizeY;y--;)
00150                         {
00151                                 for(x=SizeX;x--;)
00152                                 {
00153                                         Pixel = GetPixel(&pSrc);
00154                                         if ( Pixel == SrcCK )
00155                                         {
00156                                                 *pDst++ = DstCK;
00157                                         }
00158                                         else
00159                                         {
00160                                                 DecomposePixel(Pixel,&R,&G,&B,&A);
00161                                                 *pDst = closestPalInlineRGB(R,G,B,palInfo);
00162                                                 if ( *pDst == DstCK ) // {} this is really poor color-key avoidance!
00163                                                         *pDst ^= 1;
00164                                                 pDst++;
00165                                         }
00166                                 }
00167                                 pSrc += xtra;
00168                                 pDst += DstInfo->Stride - SizeX;
00169                         }
00170                 }
00171                 else
00172                 {
00173                 gePixelFormat_ColorGetter GetColor;
00174                         GetColor = ops->GetColor;
00175 
00176                         for(y=SizeY;y--;)
00177                         {
00178                                 for(x=SizeX;x--;)
00179                                 {
00180                                         GetColor(&pSrc,&R,&G,&B,&A);
00181                                         *pDst = closestPalInlineRGB(R,G,B,palInfo);
00182                                         if ( *pDst == DstCK ) // {} this is really poor color-key avoidance!
00183                                                 *pDst ^= 1;
00184                                         pDst++;
00185                                 }
00186                                 pSrc += xtra;
00187                                 pDst += DstInfo->Stride - SizeX;
00188                         }
00189                 }
00190         }
00191         else
00192         {
00193                 // dst does not have CK, and can't have alpha in this universe, so ignore src colorkey
00194         #if 0 // these special cases just avoid a functional-call overhead
00195                 if ( Format == GE_PIXELFORMAT_24BIT_RGB )
00196                 {
00197                         for(y=SizeY;y--;)
00198                         {
00199                                 for(x=SizeX;x--;)
00200                                 {
00201                                         R = *pSrc++; G = *pSrc++; B = *pSrc++;
00202                                         *pDst++ = closestPalInlineRGB(R,G,B,palInfo);
00203                                 }
00204                                 pSrc += xtra;
00205                                 pDst += DstInfo->Stride - SizeX;
00206                         }
00207                 }
00208                 else if ( Format == GE_PIXELFORMAT_24BIT_BGR )
00209                 {
00210                         for(y=SizeY;y--;)
00211                         {
00212                                 for(x=SizeX;x--;)
00213                                 {
00214                                         B = *pSrc++; G = *pSrc++; R = *pSrc++;
00215                                         *pDst++ = closestPalInlineRGB(R,G,B,palInfo);
00216                                 }
00217                                 pSrc += xtra;
00218                                 pDst += DstInfo->Stride - SizeX;
00219                         }
00220                 }
00221                 else
00222         #endif
00223                 {
00224                 const gePixelFormat_Operations * ops;
00225                 gePixelFormat_ColorGetter GetColor;
00226                         ops = gePixelFormat_GetOperations(Format);
00227                         assert(ops);
00228                         GetColor = ops->GetColor;
00229                         assert(GetColor);
00230                         for(y=SizeY;y--;)
00231                         {
00232                                 for(x=SizeX;x--;)
00233                                 {
00234                                         GetColor(&pSrc,&R,&G,&B,&A);
00235                                         *pDst++ = closestPalInlineRGB(R,G,B,palInfo);
00236                                 }
00237                                 pSrc += xtra;
00238                                 pDst += DstInfo->Stride - SizeX;
00239                         }
00240                 }
00241         }
00242 
00243 #ifdef _TSC
00244         showPopTSC("palettize");
00245 #endif
00246 
00247         closestPalFree(palInfo);
00248         
00249 return GE_TRUE;
00250 }

Variable Documentation

MemPool* hashNodePool = NULL [static]
 

Definition at line 340 of file palettize.c.

Referenced by addHash(), closestPalFree(), findClosestPal(), Palettize_Start(), and Palettize_Stop().

MemPool* octNodePool = NULL [static]
 

Definition at line 339 of file palettize.c.

Referenced by addOctNode(), closestPalFree(), closestPalInit(), Palettize_Start(), and Palettize_Stop().

int PoolRefs = 0 [static]
 

Definition at line 341 of file palettize.c.

Referenced by Palettize_Start(), and Palettize_Stop().

Generated on Tue Sep 30 12:37:50 2003 for GTestAndEngine by doxygen 1.3.2