src/AlienImage/AlienImage_GIFLZWDict.cxx

   1 // Created by: DCB
   2 // Copyright (c) 1998-1999 Matra Datavision
   3 // Copyright (c) 1999-2012 OPEN CASCADE SAS
   4 //
   5 // The content of this file is subject to the Open CASCADE Technology Public
   6 // License Version 6.5 (the "License"). You may not use the content of this file
   7 // except in compliance with the License. Please obtain a copy of the License
   8 // at http://www.opencascade.org and read it completely before using this file.
   9 //
  10 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  11 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  12 //
  13 // The Original Code and all software distributed under the License is
  14 // distributed on an "AS IS" basis, without warranty of any kind, and the
  15 // Initial Developer hereby disclaims all such warranties, including without
  16 // limitation, any warranties of merchantability, fitness for a particular
  17 // purpose or non-infringement. Please see the License for the specific terms
  18 // and conditions governing the rights and limitations under the License.
  19
  20 // Notes:       Most of code is taken from Xw_save_gif_image.c file (ZOV)
  21
  22 #include <AlienImage_GIFLZWDict.hxx>
  23 #include <stdio.h>
  24
  25 const Handle(Standard_Type)& STANDARD_TYPE(AlienImage_GIFLZWDict)
  26 {
  27   static Handle(Standard_Type) _atype =
  28     new Standard_Type ("AlienImage_GIFLZWDict", sizeof (AlienImage_GIFLZWDict));
  29   return _atype;
  30 }
  31
  32 //=============================================================================
  33 // Functions to write GIF image to file.
  34 //=============================================================================
  35
  36 //===================== Static definitions ===================
  37 static AlienImage_GIFLZWDict* dict;
  38 static int startBits, codeBits, nextCode, bumpCode, rack, mask, putIdx,
  39            ClearCode, EOFCode, FreeCode;
  40
  41 static void  _init_dict  (void);
  42 static int   _find_child (int, int);
  43 static BOOL  _put_bits   (BYTE *, ULONG, UINT, OSD_File&);
  44 static BOOL  _flush_bits (BYTE *, OSD_File&);
  45
  46
  47 //=============================================================================
  48 int _lzw_encode (OSD_File& file, const BYTE* pData, int width, int height, int inc)
  49 {
  50   int   i, x, y;
  51   BYTE  byte, OutBuff [BUFF_SIZE];
  52   const BYTE *pLine;
  53   int   strCode, chr;
  54
  55   dict = (AlienImage_GIFLZWDict*) malloc (sizeof (AlienImage_GIFLZWDict)*TBL_SIZE);
  56   if (dict == NULL)
  57     goto _ExitError;
  58
  59   x     = y = 0;
  60   pLine = pData;
  61
  62   OutBuff[ 0 ] = 0;
  63   putIdx       = 1;
  64   mask         = 0x01;
  65   rack         = 0;
  66   startBits    = 8;
  67   ClearCode    = 1 << startBits;
  68   EOFCode      = ClearCode + 1;
  69   FreeCode     = EOFCode + 1;
  70
  71   _init_dict ();
  72
  73   byte = startBits;
  74
  75   file.Write (&byte, sizeof(byte));
  76   if (file.Failed ())
  77     goto _ExitError;
  78
  79   strCode = pLine[ x++ ];
  80
  81   if (!_put_bits (OutBuff, (ULONG) ClearCode, codeBits, file))
  82     goto _ExitError;
  83
  84   while (y < height) {
  85
  86     chr = pLine[ x++ ];
  87
  88     i = _find_child ( strCode, chr );
  89
  90     if ( dict[ i ].code != UNUSED )
  91       strCode = dict[ i ].code;
  92
  93     else {
  94       dict[ i ].code = nextCode++;
  95       dict[ i ].prnt = strCode;
  96       dict[ i ].byte = chr;
  97
  98       if (!_put_bits (OutBuff, (ULONG) strCode, codeBits, file))
  99         goto _ExitError;
 100
 101       strCode = chr;
 102
 103       if (nextCode > MAX_CODE) {
 104         if (!_put_bits (OutBuff, (ULONG) ClearCode, codeBits, file))
 105           goto _ExitError;
 106
 107         _init_dict ();
 108       }
 109       else if (nextCode > bumpCode) {
 110         ++codeBits;
 111         bumpCode <<= 1;
 112       }
 113     }
 114
 115     if (x == width) {
 116       x = 0;
 117       ++y;
 118       pLine += inc;
 119     }
 120   }
 121
 122   if (!_put_bits (OutBuff, (ULONG) strCode, codeBits, file)) goto _ExitError;
 123   if (!_put_bits (OutBuff, (ULONG) EOFCode, codeBits, file)) goto _ExitError;
 124   if (!_flush_bits (OutBuff, file)) goto _ExitError;
 125
 126   if (dict)
 127     free (dict);
 128   return TRUE;
 129
 130
 131 _ExitError:
 132   if (dict)
 133     free (dict);
 134   return FALSE;
 135 }
 136
 137 //====================================================================
 138 static void _init_dict ()
 139 {
 140   memset (dict, UNUSED, sizeof (AlienImage_GIFLZWDict)*TBL_SIZE);
 141   nextCode = FreeCode;
 142   codeBits = startBits + 1;
 143   bumpCode = 1 << codeBits;
 144 }
 145
 146 //====================================================================
 147 static int _find_child (int prntCode, int chr)
 148 {
 149   int idx, offset;
 150
 151   idx = (  chr << ( NBITS - 8 )  ) ^ prntCode;
 152   offset = idx ? TBL_SIZE - idx : 1;
 153
 154   for (;;) {
 155
 156     if (dict[ idx ].code == UNUSED ||
 157         dict[ idx ].prnt == prntCode && dict[ idx ].byte == ( BYTE )chr)
 158       return idx;
 159
 160     idx = ( idx >= offset ) ? idx - offset : idx + TBL_SIZE - offset;
 161   }
 162 }
 163
 164 //====================================================================
 165 static BOOL _put_bits (BYTE *OutBuff, ULONG code, UINT nBits, OSD_File& file)
 166 {
 167   BOOL  retVal = TRUE;
 168   ULONG msk;
 169
 170   msk = 1;
 171
 172   while (msk != (ULONG) (1 << nBits)) {
 173     if ( msk & code )
 174       rack |= mask;
 175     mask <<= 1;
 176
 177     if ((mask & 0xFF) == 0) {
 178       OutBuff[ putIdx++ ] = rack;
 179       ++OutBuff[ 0 ];
 180
 181       if (putIdx == BUFF_SIZE) {
 182         file.Write (OutBuff, BUFF_SIZE);
 183         if (file.Failed ()) {
 184           retVal = FALSE;
 185           break;
 186         }
 187         putIdx = 1;
 188         OutBuff[ 0 ] = 0;
 189       }
 190       rack = 0;
 191       mask = 0x01;
 192     }
 193     msk <<= 1;
 194   }
 195   return retVal;
 196 }
 197
 198 //====================================================================
 199 static BOOL _flush_bits (BYTE* OutBuff, OSD_File& file)
 200 {
 201   BOOL  retVal = TRUE;
 202   BYTE  byte;
 203
 204   if ( mask != 0x01 ) {
 205     OutBuff[ putIdx++ ] = rack;
 206     ++OutBuff[ 0 ];
 207   }
 208
 209   if (putIdx != 1) {
 210     file.Write (OutBuff, putIdx);
 211     if (file.Failed ())
 212       retVal = FALSE;
 213   }
 214
 215   if (retVal) {
 216     byte = 0;
 217     file.Write (&byte, 1);
 218     if (file.Failed ())
 219       retVal = FALSE;
 220   }
 221   return retVal;
 222 }
 223
 224 //=============================================================================
 225 // Functions to convert from 24 to 8 color image
 226 //=============================================================================
 227 static int __fastcall quick_check ( PBYTE, int, int, PBYTE, LPRGBQUAD );
 228 //static int __fastcall quick_quant ( PBYTE, int, int, PBYTE, LPRGBQUAD );
 229 static int __fastcall ppm_quant   ( PBYTE, int, int, PBYTE, LPRGBQUAD );
 230
 231 BOOL __fastcall _convert24to8 (
 232                         LPRGBQUAD cTable, PBYTE pData24, PBYTE pData8,
 233                         int w, int h
 234                        )
 235 {
 236   BOOL retVal = FALSE;
 237   while ( 1 ) {
 238     if (  quick_check ( pData24, w, h, pData8, cTable )  ) {
 239 okRet:
 240       retVal = TRUE;
 241       break;
 242     } else if (  ppm_quant ( pData24, w, h, pData8, cTable ) != -1  ) {
 243 ////////////////////
 244       for ( int i = 0; i < 256; ++i ) {
 245         BYTE b = cTable[ i ].rgbRed;
 246         cTable[ i ].rgbRed  = cTable[ i ].rgbBlue;
 247         cTable[ i ].rgbBlue = b;
 248       }  // end for
 249 ////////////////////
 250       goto okRet;
 251     }  // end if
 252     break;
 253   }  // end while
 254   return retVal;
 255 }  // end _convert24to8
 256
 257 //*************************************************************************//
 258 //* The following code based on code from the 'pbmplus' package written by //
 259 //*  Jef Poskanzer                                                         //
 260 //*************************************************************************//
 261 //***//
 262 #define MAXCOLORS 32767
 263
 264 #define PPM_GETR( p ) (  ( p ).r  )
 265 #define PPM_GETG( p ) (  ( p ).g  )
 266 #define PPM_GETB( p ) (  ( p ).b  )
 267
 268 #define PPM_ASSIGN( p, red, grn, blu ) \
 269  { ( p ).r = ( red ); ( p ).g = ( grn ); ( p ).b = ( blu ); }
 270
 271 #define PPM_EQUAL( p, q ) \
 272  (  ( p ).r == ( q ).r && ( p ).g == ( q ).g && ( p ).b == ( q ).b  )
 273
 274
 275 #define PPM_DEPTH( newp, p, oldmaxval, newmaxval )                              \
 276  PPM_ASSIGN(                                                                    \
 277   ( newp ),                                                                     \
 278   (  ( int )PPM_GETR( p )  ) * (  ( int )newmaxval  ) / (  ( int )oldmaxval  ), \
 279   (  ( int )PPM_GETG( p )  ) * (  ( int )newmaxval  ) / (  ( int )oldmaxval  ), \
 280   (  ( int )PPM_GETB( p )  ) * (  ( int )newmaxval  ) / (  ( int )oldmaxval  )  \
 281  )
 282
 283
 284 #define HASH_SIZE 6553
 285
 286 #define ppm_hashpixel( p )                  \
 287  (    (   (  ( int )PPM_GETR( p ) * 33023 + \
 288              ( int )PPM_GETG( p ) * 30013 + \
 289              ( int )PPM_GETB( p ) * 27011   \
 290           ) & 0x7fffffff                    \
 291       ) % HASH_SIZE                         \
 292  )
 293
 294 #define PPM_LUMIN( p ) \
 295          (  77 * PPM_GETR( p ) + 150 * PPM_GETG( p ) + 29 * PPM_GETB( p )  )
 296
 297 typedef struct { BYTE r, g, b; } pixel;
 298
 299 struct chist_item {
 300         pixel color;
 301         int   value;
 302        };
 303
 304 typedef struct chist_item* chist_vec;
 305
 306 typedef struct chist_list_item* chist_list;
 307 typedef chist_list*             chash_table;
 308
 309 struct chist_list_item {
 310         struct chist_item ch;
 311         chist_list        next;
 312        };
 313
 314 struct box {
 315         int index;
 316         int colors;
 317         int sum;
 318        };
 319
 320 typedef struct box* box_vector;
 321
 322 static chist_vec   __fastcall ppm_computechist ( pixel**,   int, int, int, PINT );
 323 static void        __fastcall ppm_freechist    ( chist_vec                      );
 324 static chist_vec   __fastcall mediancut        ( chist_vec, int, int, int, int  );
 325 static chash_table            ppm_allocchash   ( void                           );
 326 static void        __fastcall ppm_freechash    ( chash_table                    );
 327 static chash_table __fastcall ppm_computechash ( pixel**,   int, int, int, PINT );
 328 static chist_vec   __fastcall ppm_chashtochist ( chash_table, int               );
 329
 330 static int redcompare   ( const void*, const void* );
 331 static int greencompare ( const void*, const void* );
 332 static int bluecompare  ( const void*, const void* );
 333 static int sumcompare   ( const void*, const void* );
 334
 335 static int __fastcall ppm_quant (
 336                        PBYTE pic24, int cols, int rows, PBYTE pic8, LPRGBQUAD rgbmap
 337                       ) {
 338
 339
 340  pixel**     pixels;
 341  pixel*      pP;
 342  int         row;
 343  int         col, limitcol;
 344  BYTE        maxval, newmaxval;
 345  int         colors;
 346  int         index;
 347  chist_vec   chv, colormap;
 348  chash_table cht;
 349  int         i;
 350  PBYTE       picptr;
 351  LPRGBQUAD   pRGB;
 352  int         pad;
 353
 354  index  = 0;
 355  maxval = 255;
 356 // pad    = PAD( cols * 3 );
 357  pad = 0;
 358
 359  pixels = ( pixel** )MALLOC(  rows * sizeof ( pixel* )  );
 360
 361  if ( pixels == NULL ) return -1;
 362
 363  for ( row = 0; row < rows; ++row ) {
 364
 365   pixels[ row ] = ( pixel* )MALLOC(  cols * sizeof ( pixel )  );
 366
 367   if ( pixels[ row ] == NULL ) {
 368 freeMemory:
 369    while ( --row >= 0 ) FREE( pixels[ row ] );
 370
 371    FREE( pixels );
 372
 373    return -1;
 374
 375   }  // end if
 376
 377   for ( col = 0, pP = pixels[ row ]; col < cols; ++col, ++pP ) {
 378
 379    pP -> r = *pic24++;
 380    pP -> g = *pic24++;
 381    pP -> b = *pic24++;
 382
 383   }  // end for
 384
 385   pic24 += pad;
 386
 387  }  // end for
 388
 389  for ( ;; ) {
 390
 391   chv = ppm_computechist ( pixels, cols, rows, MAXCOLORS, &colors );
 392
 393   if (  chv != ( chist_vec )0  ) break;
 394
 395   newmaxval = maxval / 2;
 396
 397   for ( row = 0; row < rows; ++row )
 398
 399    for ( col = 0, pP = pixels[ row ]; col < cols; ++col, ++pP )
 400
 401     PPM_DEPTH( *pP, *pP, maxval, newmaxval );
 402
 403   maxval = newmaxval;
 404
 405  }  // end for
 406
 407  colormap = mediancut ( chv, colors, rows * cols, maxval, 256 );
 408
 409  if (  colormap == ( chist_vec )NULL  ) {
 410 freeMemory_1:
 411   ppm_freechist ( chv );
 412   row = rows;
 413   goto freeMemory;
 414
 415  }  // end if
 416
 417  ppm_freechist ( chv );
 418
 419  cht = ppm_allocchash ();
 420
 421  picptr = pic8;
 422
 423  for ( row = 0;  row < rows;  ++row ) {
 424
 425   col      = 0;
 426   limitcol = cols;
 427   pP       = pixels[ row ];
 428
 429   do {
 430
 431    int        hash;
 432    chist_list chl;
 433
 434    hash = ppm_hashpixel ( *pP );
 435
 436    for ( chl = cht[ hash ];  chl;  chl = chl -> next )
 437
 438     if (  PPM_EQUAL( chl -> ch.color, *pP )  ) {
 439
 440      index = chl -> ch.value;
 441      break;
 442
 443     }  // end if
 444
 445    if ( !chl ) {
 446
 447     int  i, r1, g1, b1, r2, g2, b2;
 448     long dist, newdist;
 449
 450         r1 = PPM_GETR( *pP );
 451         g1 = PPM_GETG( *pP );
 452         b1 = PPM_GETB( *pP );
 453         dist = 2000000000;
 454
 455         for ( i = 0; i < 256; ++i ) {
 456
 457      r2 = PPM_GETR( colormap[ i ].color );
 458      g2 = PPM_GETG( colormap[ i ].color );
 459      b2 = PPM_GETB( colormap[ i ].color );
 460
 461      newdist = ( r1 - r2 ) * ( r1 - r2 ) +
 462                ( g1 - g2 ) * ( g1 - g2 ) +
 463                ( b1 - b2 ) * ( b1 - b2 );
 464
 465      if ( newdist < dist ) {
 466
 467       index = i;
 468       dist  = newdist;
 469
 470      }  // end if
 471
 472     }  // end for
 473
 474     hash = ppm_hashpixel( *pP );
 475         chl  = ( chist_list )MALLOC(  sizeof ( struct chist_list_item )  );
 476
 477         if ( chl == NULL ) {
 478
 479      ppm_freechash ( cht );
 480      goto freeMemory_1;
 481
 482     }  // end if
 483
 484         chl -> ch.color = *pP;
 485         chl -> ch.value = index;
 486         chl -> next     = cht[ hash ];
 487         cht[ hash ]     = chl;
 488
 489    }  // end if
 490
 491    *picptr++ = index;
 492    ++col;
 493    ++pP;
 494
 495   } while ( col != limitcol );
 496
 497  }  // end for
 498
 499  for ( i = 0, pRGB = rgbmap; i < 256; ++i, ++pRGB ) {
 500
 501   PPM_DEPTH( colormap[ i ].color, colormap[ i ].color, maxval, 255 );
 502
 503   pRGB -> rgbRed   = PPM_GETR( colormap[ i ].color );
 504   pRGB -> rgbGreen = PPM_GETG( colormap[ i ].color );
 505   pRGB -> rgbBlue  = PPM_GETB( colormap[ i ].color );
 506
 507  }  // end for
 508
 509  for ( i = 0; i < rows; ++i ) FREE( pixels[ i ] );
 510
 511  FREE( pixels );
 512
 513  ppm_freechist ( colormap );
 514  ppm_freechash ( cht      );
 515
 516  return 0;
 517
 518 }  // end ppm_quant
 519
 520 static void __fastcall ppm_freechist ( chist_vec chv ) {
 521
 522  FREE(  ( LPVOID )chv  );
 523
 524 }  // end ppm_freechist
 525
 526 static chist_vec __fastcall mediancut (
 527                              chist_vec chv, int colors, int sum,
 528                              int maxval, int newcolors
 529                             ) {
 530
 531  chist_vec  colormap;
 532  box_vector bv;
 533  int        bi, i;
 534  int        boxes;
 535
 536  bv = ( box_vector )MALLOC(  sizeof( struct box        ) * newcolors  );
 537
 538  if ( bv == NULL ) return ( chist_vec )NULL;
 539
 540  colormap = ( chist_vec  )MALLOC(  sizeof( struct chist_item ) * newcolors  );
 541
 542  if ( colormap == NULL ) {
 543
 544   FREE( bv );
 545   return ( chist_vec )NULL;
 546
 547  }  // end if
 548
 549  for ( i = 0; i < newcolors; ++i ) PPM_ASSIGN( colormap[ i ].color, 0, 0, 0 );
 550
 551  bv[ 0 ].index  = 0;
 552  bv[ 0 ].colors = colors;
 553  bv[ 0 ].sum    = sum;
 554  boxes          = 1;
 555
 556  while ( boxes < newcolors ) {
 557
 558   int indx, clrs;
 559   int sm;
 560   int minr, maxr, ming, maxg, minb, maxb, v;
 561   int halfsum, lowersum;
 562
 563   for ( bi = 0; bv[ bi ].colors < 2 && bi < boxes; ++bi );
 564
 565   if ( bi == boxes ) break;
 566
 567   indx = bv[ bi ].index;
 568   clrs = bv[ bi ].colors;
 569   sm   = bv[ bi ].sum;
 570
 571   minr = maxr = PPM_GETR( chv[ indx ].color );
 572   ming = maxg = PPM_GETG( chv[ indx ].color );
 573   minb = maxb = PPM_GETB( chv[ indx ].color );
 574
 575   for ( i = 1; i < clrs; ++i ) {
 576
 577    v = PPM_GETR( chv[ indx + i ].color );
 578
 579    if ( v < minr ) minr = v;
 580    if ( v > maxr ) maxr = v;
 581
 582    v = PPM_GETG( chv[ indx + i ].color );
 583
 584    if ( v < ming ) ming = v;
 585    if ( v > maxg ) maxg = v;
 586
 587    v = PPM_GETB( chv[ indx + i ].color );
 588
 589    if ( v < minb ) minb = v;
 590    if ( v > maxb ) maxb = v;
 591
 592   }  // end for
 593
 594   {  // begin local block
 595
 596    pixel p;
 597    int   rl, gl, bl;
 598
 599    PPM_ASSIGN( p, maxr - minr, 0, 0 );
 600    rl = PPM_LUMIN( p );
 601
 602    PPM_ASSIGN( p, 0, maxg - ming, 0 );
 603    gl = PPM_LUMIN( p );
 604
 605    PPM_ASSIGN( p, 0, 0, maxb - minb );
 606    bl = PPM_LUMIN( p );
 607
 608    if ( rl >= gl && rl >= bl )
 609
 610     qsort (
 611      ( char* )&chv[ indx ], ( size_t )clrs,
 612      sizeof ( struct chist_item ), redcompare
 613     );
 614
 615    else if ( gl >= bl )
 616
 617     qsort (
 618      ( char* )&chv[ indx ], ( size_t )clrs,
 619      sizeof ( struct chist_item ), greencompare
 620     );
 621
 622    else
 623
 624     qsort (
 625      ( char* )&chv[ indx ], ( size_t )clrs,
 626      sizeof ( struct chist_item ), bluecompare
 627     );
 628
 629   }  // end local block
 630
 631   lowersum = chv[ indx ].value;
 632   halfsum  = sm / 2;
 633
 634   for ( i = 1; i < clrs - 1; ++i) {
 635
 636    if ( lowersum >= halfsum ) break;
 637
 638    lowersum += chv[ indx + i ].value;
 639
 640   }  // end for
 641
 642   bv[ bi ].colors = i;
 643   bv[ bi ].sum    = lowersum;
 644
 645   bv[ boxes   ].index  = indx + i;
 646   bv[ boxes   ].colors = clrs - i;
 647   bv[ boxes++ ].sum    = sm - lowersum;
 648
 649   qsort (
 650    ( char* )bv, ( size_t )boxes, sizeof ( struct box ), sumcompare
 651   );
 652
 653  }  // end while
 654
 655  for ( bi = 0; bi < boxes; ++bi ) {
 656
 657   int  indx = bv[ bi ].index;
 658   int  clrs = bv[ bi ].colors;
 659   long r = 0, g = 0, b = 0, sum = 0;
 660
 661   for ( i = 0; i < clrs; ++i ) {
 662
 663    r += PPM_GETR( chv[ indx + i ].color ) * chv[ indx + i ].value;
 664    g += PPM_GETG( chv[ indx + i ].color ) * chv[ indx + i ].value;
 665    b += PPM_GETB( chv[ indx + i ].color ) * chv[ indx + i ].value;
 666
 667    sum += chv[ indx + i ].value;
 668
 669   }  // end for ( i . . . )
 670
 671   r = r / sum;  if ( r > maxval ) r = maxval;
 672   g = g / sum;  if ( g > maxval ) g = maxval;
 673   b = b / sum;  if ( b > maxval ) b = maxval;
 674
 675   PPM_ASSIGN(  colormap[ bi ].color, ( BYTE )r, ( BYTE )g, ( BYTE )b  );
 676
 677  }  // end for ( bi . . . )
 678
 679  FREE( bv );
 680
 681  return colormap;
 682
 683 }  // end mediancut
 684
 685 static int redcompare ( const void* p1, const void* p2 ) {
 686
 687  return ( int )PPM_GETR(   (  ( chist_vec )p1  ) -> color   ) -
 688         ( int )PPM_GETR(   (  ( chist_vec )p2  ) -> color   );
 689
 690 }  // end redcompare
 691
 692 static int greencompare ( const void* p1, const void* p2 ) {
 693
 694  return ( int )PPM_GETG(   (  ( chist_vec )p1  ) -> color   ) -
 695         ( int )PPM_GETG(   (  ( chist_vec )p2  ) -> color   );
 696
 697 }  // end greencompare
 698
 699 static int bluecompare ( const void* p1, const void* p2 ) {
 700
 701  return ( int )PPM_GETB(   (  ( chist_vec )p1  ) -> color   ) -
 702         ( int )PPM_GETB(   (  ( chist_vec )p2  ) -> color   );
 703
 704 }  // end bluecompare
 705
 706 static int sumcompare ( const void* p1, const void* p2 ) {
 707
 708  return (  ( box_vector )p2  ) -> sum - (  ( box_vector )p1  ) -> sum;
 709
 710 }  // end sumcompare
 711
 712 static chash_table ppm_allocchash ( void ) {
 713
 714  chash_table cht;
 715
 716  cht = ( chash_table )MALLOC(  HASH_SIZE * sizeof ( chist_list )  );
 717
 718  return cht;
 719
 720 }  // end ppm_allocchash
 721
 722 static chist_vec __fastcall ppm_computechist (
 723                              pixel** pixels, int cols, int rows, int maxcolors,
 724                              PINT colorsP
 725                             ) {
 726
 727  chash_table cht;
 728  chist_vec chv;
 729
 730  cht = ppm_computechash ( pixels, cols, rows, maxcolors, colorsP );
 731
 732  if ( cht == NULL ) return ( chist_vec )NULL;
 733
 734  chv = ppm_chashtochist ( cht, maxcolors );
 735
 736  ppm_freechash ( cht );
 737
 738  return chv;
 739
 740 }  // end ppm_computechist
 741
 742 static chash_table __fastcall ppm_computechash (
 743                                pixel** pixels, int cols, int rows, int maxcolors,
 744                                PINT colorsP
 745                               ) {
 746
 747  chash_table     cht;
 748  register pixel* pP;
 749  chist_list      chl;
 750  int             col, row, hash;
 751
 752  cht      = ppm_allocchash ();
 753  *colorsP = 0;
 754
 755  for ( row = 0; row < rows; ++row )
 756
 757   for ( col = 0, pP = pixels[ row ];  col < cols;  ++col, ++pP ) {
 758
 759    hash = ppm_hashpixel ( *pP );
 760
 761    for ( chl = cht[ hash ]; chl != ( chist_list )0; chl = chl -> next )
 762
 763     if (  PPM_EQUAL( chl -> ch.color, *pP )  ) break;
 764
 765    if (  chl != ( chist_list)0  )
 766
 767     ++( chl->ch.value );
 768
 769    else {
 770
 771         if (  ( *colorsP )++ > maxcolors  ) {
 772
 773      ppm_freechash ( cht );
 774
 775      return ( chash_table )NULL;
 776
 777     }  // end if
 778
 779     chl = ( chist_list )MALLOC(  sizeof( struct chist_list_item )  );
 780
 781     if ( chl == NULL ) return ( chash_table )NULL;
 782
 783     chl -> ch.color = *pP;
 784     chl -> ch.value = 1;
 785     chl -> next     = cht[ hash ];
 786     cht[ hash ]     = chl;
 787
 788   }  // end else
 789
 790  }  // end for
 791
 792  return cht;
 793
 794 }  // end ppm_computechash
 795
 796 static chist_vec __fastcall ppm_chashtochist ( chash_table cht, int maxcolors ) {
 797
 798  chist_vec  chv;
 799  chist_list chl;
 800  int        i, j;
 801
 802  chv = ( chist_vec )MALLOC(  maxcolors * sizeof ( struct chist_item )  );
 803
 804  if ( chv == NULL) return chv;
 805
 806  j = 0;
 807
 808  for ( i = 0; i < HASH_SIZE; ++i )
 809
 810   for ( chl = cht[ i ];  chl != ( chist_list )0;  chl = chl -> next ) {
 811
 812    chv[ j ] = chl -> ch;
 813    ++j;
 814
 815   }  // end for
 816
 817   return chv;
 818
 819 }  // end ppm_chashtochist
 820
 821 static void __fastcall ppm_freechash ( chash_table cht ) {
 822
 823  int        i;
 824  chist_list chl, chlnext;
 825
 826  for ( i = 0; i < HASH_SIZE; ++i )
 827
 828   for ( chl = cht[ i ];  chl != ( chist_list )0; chl = chlnext ) {
 829
 830    chlnext = chl -> next;
 831    FREE( chl );
 832
 833   }  // end for
 834
 835  FREE( cht );
 836
 837 }  // end ppm_freechash
 838
 839 static int __fastcall quick_check (
 840                        PBYTE pic24, int w, int h, PBYTE pic8, LPRGBQUAD rgbmap
 841                       ) {
 842
 843  unsigned long colors[ 256 ], col;
 844  int           i, j, nc, low, high, mid, pad;
 845  PBYTE         p, pix;
 846
 847  nc  = 0;
 848  mid = 0;
 849 // pad = PAD( w * 3 );
 850  pad = 0;
 851
 852  for ( i = 0, p = pic24; i < h; ++i ) {
 853
 854   for ( j = 0; j < w; ++j ) {
 855
 856    col  = (   (  ( unsigned long )*p++  ) << 16   );
 857    col += (   (  ( unsigned long )*p++  ) <<  8   );
 858    col += (   (  ( unsigned long )*p++  ) <<  0   );
 859
 860    low = 0;  high = nc - 1;
 861
 862    while ( low <= high ) {
 863
 864     mid = ( low + high ) / 2;
 865
 866     if ( col < colors[ mid ] )
 867
 868      high = mid - 1;
 869
 870     else if ( col > colors[ mid ] )
 871
 872      low  = mid + 1;
 873
 874     else break;
 875
 876    }  // end while
 877
 878    if ( high < low ) {
 879
 880     if ( nc >= 256 ) return FALSE;
 881
 882     memcpy (
 883      ( char* )&colors[ low + 1 ], ( char* )&colors[ low ],
 884      ( nc - low ) * sizeof ( unsigned long )
 885     );
 886
 887     colors[ low ] = col;
 888     ++nc;
 889
 890    }  // end if
 891
 892   }  // end for ( j . . . )
 893
 894   p += pad;
 895
 896  }  // end for ( i . . . )
 897
 898  for ( i = 0, p = pic24, pix = pic8; i < h; ++i ) {
 899
 900   for ( j = 0; j < w; ++j ) {
 901
 902    col  = (   (  ( unsigned long )*p++  ) << 16   );
 903    col += (   (  ( unsigned long )*p++  ) <<  8   );
 904    col += *p++;
 905
 906    low = 0;  high = nc - 1;
 907
 908    while ( low <= high ) {
 909
 910     mid = ( low + high ) / 2;
 911
 912     if ( col < colors[ mid ] )
 913
 914      high = mid - 1;
 915
 916     else if ( col > colors[ mid ] )
 917
 918      low  = mid + 1;
 919
 920     else break;
 921
 922    }  // end while
 923
 924    *pix++ = mid;
 925
 926   }  // end for ( j . . . )
 927
 928   p += pad;
 929
 930  }  // end for ( i . . . )
 931
 932  for ( i = 0; i < nc; ++i, ++rgbmap ) {
 933
 934   rgbmap -> rgbRed   = ( BYTE )( colors[ i ] >>  0 ) & 0xFF;
 935   rgbmap -> rgbGreen = ( BYTE )( colors[ i ] >>  8 ) & 0xFF;
 936   rgbmap -> rgbBlue  = ( BYTE )( colors[ i ] >> 16 ) & 0xFF;
 937
 938  }  // end for
 939
 940  return nc;
 941
 942 }  // end quick_check
 943
 944 #ifdef BSHIFT           //HPUX COMPATIBILLITY
 945 #undef BSHIFT
 946 #endif
 947 #define RMASK  0xE0
 948 #define RSHIFT    0
 949 #define GMASK  0xE0
 950 #define GSHIFT    3
 951 #define BMASK  0xC0
 952 #define BSHIFT    6
 953 #define RANGE( a, b, c ) { if ( a < b ) a = b;  if ( a > c ) a = c; }
 954
 955 //static int __fastcall quick_quant (
 956 //                       PBYTE p24, int w, int h, PBYTE p8, LPRGBQUAD rgbmap
 957 //                      ) {
 958
 959 // PBYTE pp;
 960 // int   r1, g1, b1;
 961 // PINT  thisline, nextline, thisptr, nextptr, tmpptr;
 962 // int   i, j, val, pwide3;
 963 // int   imax, jmax;
 964 // int   pad;
 965
 966 //// pad = PAD( w * 3 );
 967 // pad = 0;
 968
 969 // pp     = p8;
 970 // pwide3 = w * 3;
 971 // imax   = h - 1;
 972 // jmax   = w - 1;
 973
 974 // for ( i = 0; i < 256; ++i ) {
 975
 976 //  rgbmap[ i ].rgbRed   = (   (  ( i << RSHIFT ) & RMASK  ) * 255 + RMASK / 2   ) / RMASK;
 977 //  rgbmap[ i ].rgbGreen = (   (  ( i << GSHIFT ) & GMASK  ) * 255 + GMASK / 2   ) / GMASK;
 978 //  rgbmap[ i ].rgbBlue  = (   (  ( i << BSHIFT ) & BMASK  ) * 255 + BMASK / 2   ) / BMASK;
 979
 980 // }  // end for
 981
 982 // thisline = ( PINT )MALLOC(  pwide3 * sizeof ( int )  );
 983
 984 // if ( thisline == NULL ) return 1;
 985
 986 // nextline = ( PINT )MALLOC(  pwide3 * sizeof ( int )  );
 987
 988 // if ( nextline == NULL ) {
 989
 990 //  FREE( thisline );
 991 //  return 1;
 992
 993 // }  // end if
 994
 995 // for ( j = pwide3, tmpptr = nextline; j; --j ) *tmpptr++ = ( int )*p24++;
 996
 997 // p24 += pad;
 998
 999 // for ( i = 0; i < h; ++i ) {
1000
1001 //  tmpptr   = thisline;
1002 //  thisline = nextline;
1003 //  nextline = tmpptr;
1004 //
1005 //  if ( i != imax ) {
1006
1007 //   for ( j = pwide3, tmpptr = nextline; j; --j ) *tmpptr++ = ( int )*p24++;
1008 //
1009 //   p24 += pad;
1010
1011 //  }  // end if
1012
1013 //  for ( j = 0, thisptr = thisline, nextptr = nextline; j < w; ++j, ++pp ) {
1014
1015 //   r1 = *thisptr++;
1016 //   RANGE( r1, 0, 255 );
1017
1018 //   g1 = *thisptr++;
1019 //   RANGE(g1,0,255);
1020
1021 //   b1 = *thisptr++;
1022 //   RANGE(b1,0,255);
1023
1024 //   val = (   (  ( r1 & RMASK ) >> RSHIFT  ) |
1025 //             (  ( g1 & GMASK ) >> GSHIFT  ) |
1026 //                 (  ( b1 & BMASK ) >> BSHIFT  )   );
1027 //   *pp = val;
1028
1029 //   r1 -= rgbmap[ val ].rgbRed;
1030 //   g1 -= rgbmap[ val ].rgbGreen;
1031 //   b1 -= rgbmap[ val ].rgbBlue;
1032
1033 //   if ( j != jmax ) {
1034
1035 //    thisptr[ 0 ] += ( r1 * 7 ) / 16;
1036 //    thisptr[ 1 ] += ( g1 * 7 ) / 16;
1037 //    thisptr[ 2 ] += ( b1 * 7 ) / 16;
1038
1039 //   }  // end if
1040
1041 //   if ( i != imax ) {
1042
1043 //    nextptr[ 0 ] += ( r1 * 5 ) / 16;
1044 //    nextptr[ 1 ] += ( g1 * 5 ) / 16;
1045 //    nextptr[ 2 ] += ( b1 * 5 ) / 16;
1046
1047 //    if ( j > 0 ) {
1048
1049 //     nextptr[ -3 ] += ( r1 * 3 ) / 16;
1050 //     nextptr[ -2 ] += ( g1 * 3 ) / 16;
1051 //     nextptr[ -1 ] += ( b1 * 3 ) / 16;
1052
1053 //    }  // end if
1054
1055 //    if ( j != jmax ) {
1056
1057 //     nextptr[ 3 ] += ( r1 ) / 16;
1058 //     nextptr[ 4 ] += ( g1 ) / 16;
1059 //     nextptr[ 5 ] += ( b1 ) / 16;
1060
1061 //    }  // end if
1062
1063 //        nextptr += 3;
1064
1065 //   }  // end if
1066
1067 //  }  // end for ( j . . . )
1068
1069 // }  // end for ( i . . . )
1070
1071 // FREE( thisline );
1072 // FREE( nextline );
1073
1074 // return 0;
1075
1076 //}  // end quick_quant
1077 //***//
1078 //*************************************************************************//
1079