src/AlienImage/AlienImage_GIFLZWDict.cxx

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