text: // =============================================================
  // Quantizer objects and functions
  //
  // Design and implementation by:
  // - Herv?Drolon <drolon@infonie.fr>
  // - Carsten Klein (cklein05@users.sourceforge.net)
  //
  // This file is part of FreeImage 3
  //
  // COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY
  // OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES
  // THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
  // OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED
  // CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT
  // THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY
  // SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL
  // PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
  // THIS DISCLAIMER.
  //
  // Use at your own risk!
  // =============================================================
  
  // 
  ////////////////////////////////////////////////////////////////
  
  #include "FreeImage.h"
  
  ////////////////////////////////////////////////////////////////
  
  /**
    Xiaolin Wu color quantization algorithm
  */
  class WuQuantizer
  {
  public:
  
  typedef struct tagBox {
      int r0;			 // min value, exclusive
      int r1;			 // max value, inclusive
      int g0;  
      int g1;  
      int b0;  
      int b1;
      int vol;
  } Box;
  
  protected:
      float *gm2;
  	LONG *wt, *mr, *mg, *mb;
  	WORD *Qadd;
  
  	// DIB data
  	unsigned width, height;
  	unsigned pitch;
  	FIBITMAP *m_dib;
  
  protected:
      void Hist3D(LONG *vwt, LONG *vmr, LONG *vmg, LONG *vmb, float *m2, int ReserveSize, RGBQUAD *ReservePalette);
  	void M3D(LONG *vwt, LONG *vmr, LONG *vmg, LONG *vmb, float *m2);
  	LONG Vol(Box *cube, LONG *mmt);
  	LONG Bottom(Box *cube, BYTE dir, LONG *mmt);
  	LONG Top(Box *cube, BYTE dir, int pos, LONG *mmt);
  	float Var(Box *cube);
  	float Maximize(Box *cube, BYTE dir, int first, int last , int *cut,
  				   LONG whole_r, LONG whole_g, LONG whole_b, LONG whole_w);
  	bool Cut(Box *set1, Box *set2);
  	void Mark(Box *cube, int label, BYTE *tag);
  
  public:
  	// Constructor - Input parameter: DIB 24-bit to be quantized
      WuQuantizer(FIBITMAP *dib);
  	// Destructor
  	~WuQuantizer();
  	// Quantizer - Return value: quantized 8-bit (color palette) DIB
  	FIBITMAP* Quantize(int PaletteSize, int ReserveSize, RGBQUAD *ReservePalette);
  };
  
  
  /**
    NEUQUANT Neural-Net quantization algorithm by Anthony Dekker
  */
  
  // ----------------------------------------------------------------
  // Constant definitions
  // ----------------------------------------------------------------
  
  /** number of colours used: 
  	for 256 colours, fixed arrays need 8kb, plus space for the image
  */
  //static const int netsize = 256;
  
  /**@name network definitions */
  //@{
  //static const int maxnetpos = (netsize - 1);
  /// bias for colour values
  static const int netbiasshift = 4;
  /// no. of learning cycles
  static const int ncycles = 100;
  //@}
  
  /**@name defs for freq and bias */
  //@{
  /// bias for fractions
  static const int intbiasshift = 16;
  static const int intbias = (((int)1) << intbiasshift);
  /// gamma = 1024
  static const int gammashift = 10;
  // static const int gamma = (((int)1) << gammashift);
  /// beta = 1 / 1024
  static const int betashift = 10;
  static const int beta = (intbias >> betashift);
  static const int betagamma = (intbias << (gammashift-betashift));
  //@}
  
  /**@name defs for decreasing radius factor */
  //@{
  /// for 256 cols, radius starts
  //static const int initrad = (netsize >> 3);
  /// at 32.0 biased by 6 bits
  static const int radiusbiasshift = 6;
  static const int radiusbias = (((int)1) << radiusbiasshift);
  /// and decreases by a 
  //static const int initradius	= (initrad * radiusbias);
  // factor of 1/30 each cycle
  static const int radiusdec = 30;
  //@}
  
  /**@name defs for decreasing alpha factor */
  //@{
  /// alpha starts at 1.0
  static const int alphabiasshift = 10;
  static const int initalpha = (((int)1) << alphabiasshift);
  //@}
  
  /**@name radbias and alpharadbias used for radpower calculation */
  //@{
  static const int radbiasshift = 8;
  static const int radbias = (((int)1) << radbiasshift);
  static const int alpharadbshift = (alphabiasshift+radbiasshift);
  static const int alpharadbias = (((int)1) << alpharadbshift);	
  //@}
  
  class NNQuantizer
  {
  protected:
  	/**@name image parameters */
  	//@{
  	/// pointer to input dib
  	FIBITMAP *dib_ptr;
  	/// image width
  	int img_width;
  	/// image height
  	int img_height;
  	/// image line length
  	int img_line;
  	//@}
  
  	/**@name network parameters */
  	//@{
  
  	int netsize, maxnetpos, initrad, initradius;
  
  	/// BGRc
  	typedef int pixel[4];
  	/// the network itself
  	pixel *network;
  
  	/// for network lookup - really 256
  	int netindex[256];
  
  	/// bias array for learning
  	int *bias;
  	/// freq array for learning
  	int *freq;
  	/// radpower for precomputation
  	int *radpower;
  	//@}
  
  protected:
  	/// Initialise network in range (0,0,0) to (255,255,255) and set parameters
  	void initnet();	
  
  	/// Unbias network to give byte values 0..255 and record position i to prepare for sort
  	void unbiasnet();
  
  	/// Insertion sort of network and building of netindex[0..255] (to do after unbias)
  	void inxbuild();
  
  	/// Search for BGR values 0..255 (after net is unbiased) and return colour index
  	int inxsearch(int b, int g, int r);
  
  	/// Search for biased BGR values
  	int contest(int b, int g, int r);
  	
  	/// Move neuron i towards biased (b,g,r) by factor alpha
  	void altersingle(int alpha, int i, int b, int g, int r);
  
  	/// Move adjacent neurons by precomputed alpha*(1-((i-j)^2/[r]^2)) in radpower[|i-j|]
  	void alterneigh(int rad, int i, int b, int g, int r);
  
  	/** Main Learning Loop
  	@param sampling_factor sampling factor in [1..30]
  	*/
  	void learn(int sampling_factor);
  
  	/// Get a pixel sample at position pos. Handle 4-byte boundary alignment.
  	void getSample(long pos, int *b, int *g, int *r);
  
  
  public:
  	/// Constructor
  	NNQuantizer(int PaletteSize);
  
  	/// Destructor
  	~NNQuantizer();
  
  	/** Quantizer
  	@param dib input 24-bit dib to be quantized
  	@param sampling a sampling factor in range 1..30. 
  	1 => slower (but better), 30 => faster. Default value is 1
  	@return returns the quantized 8-bit (color palette) DIB
  	*/
  	FIBITMAP* Quantize(FIBITMAP *dib, int ReserveSize, RGBQUAD *ReservePalette, int sampling = 1);
  
  };
  
  /**
   * LFPQUANT - Lossless Fast Pseudo-Quantization Algorithm
   *
   * The Lossless Fast Pseudo-Quantization algorithm is no real quantization
   * algorithm, since it makes no attempt to create a palette, that is suitable
   * for all colors of the 24-bit source image. However, it provides very fast
   * conversions from 24-bit to 8-bit images, if the number of distinct colors
   * in the source image is not greater than the desired palette size. If the
   * number of colors in the source image is exceeded, the Quantize method of
   * this implementation stops the process and returns NULL.
   *
   * This implementation uses a very fast hash map implementation to collect
   * the source image's colors. It turned out that a customized implementation
   * of a hash table with open addressing (using linear probing) provides the
   * best performance. The hash table has 512 entries, which prevents the load
   * factor to exceed 0.5 as we have 256 entries at most. Each entry consumes
   * 64 bits, so the whole hash table takes 4KB of memory.
   *
   * For large images, the LFPQuantizer is typically up to three times faster
   * than the WuQuantizer.
   */
  class LFPQuantizer {
  public:
  	/** Constructor */
  	LFPQuantizer(unsigned PaletteSize);
  
  	/** Destructor */
  	~LFPQuantizer();
  
  	/**
  	 * Quantizer
  	 * @param dib input 24-bit or 32-bit bitmap to be quantized
  	 * @return returns the pseudo-quantized 8-bit bitmap
  	 */
  	FIBITMAP* Quantize(FIBITMAP *dib, int ReserveSize, RGBQUAD *ReservePalette);
  
  protected:
  	/** The maximum size of a palette. */
  	static const unsigned MAX_SIZE = 256;
  
  	/**
  	 * The size of the hash table. Must be a power of 2. By sizing it
  	 * MAX_SIZE * 2, we ensure the load factor not to exceed 0.5 at any
  	 * time, since we will have MAX_SIZE entries at most.
  	 */
  	static const unsigned MAP_SIZE = MAX_SIZE * 2;
  
  	/**
  	 * With open addressing we need a special value for empty buckets.
  	 * Both entry.color and entry.index are 0xFFFFFFFF for an empty
  	 * entry.
  	 */
  	static const unsigned EMPTY_BUCKET = 0xFFFFFFFF;
  
  	/**
  	 * This structure defines a single entry in the hash table. We use
  	 * color as the entry's key.
  	 */
  	typedef struct MapEntry {
  		unsigned color;
  		unsigned index;
  	} MapEntry;
  
  	/** The hash table. */
  	MapEntry *m_map;
  
  	/**
  	 * The current size of the newly created palette. Since the provided
  	 * reserve palette could contain duplicates, this is not necessarily
  	 * the number of entries in the hash table. Initialized to zero.
  	 */
  	unsigned m_size;
  
  	/**
  	 * The desired maximum number of entries in the newly created palette.
  	 * If m_size exceeds this value, the palette is full and the
  	 * quantization process is stopped. Initialized to the desired
  	 * palette size.
  	 */
  	unsigned m_limit;
  
  	/**
  	 *  The palette index used for the next color added. Initialized to
  	 *  zero (the reserve palette is put to the end of the palette).
  	 */
  	unsigned m_index;
  
  	/**
  	 * Ensures that hash codes that differ only by constant multiples
  	 * at each bit position have a bounded number of collisions.
  	 * @param h the initial (aka raw) hash code
  	 * @return the modified hash code
  	 */
  	static inline unsigned hash(unsigned h) {
  		h ^= (h >> 20) ^ (h >> 12);
  		return h ^ (h >> 7) ^ (h >> 4);
  	}
  
  	/**
  	 * Returns the palette index of the specified color. Tries to put the
  	 * color into the map, if it's not already present in the map. In that
  	 * case, a new index is used for the color. Returns -1, if adding the
  	 * color would exceed the desired maximum number of colors in the
  	 * palette.
  	 * @param color the color to get the index from
  	 * @return the palette index of the specified color or -1, if there
  	 * is no space left in the palette
  	 */
  	int GetIndexForColor(unsigned color);
  
  	/**
  	 * Adds the specified number of entries of the specified reserve
  	 * palette to the newly created palette.
  	 * @param *palette a pointer to the reserve palette to copy from
  	 * @param size the number of entries to copy
  	 */
  	void AddReservePalette(const void *palette, unsigned size);
  
  	/**
  	 * Copies the newly created palette into the specified destination
  	 * palettte. Although unused palette entries are not overwritten in
  	 * the destination palette, it is assumed to have space for at
  	 * least 256 entries.
  	 * @param palette a pointer to the destination palette
  	 */
  	void WritePalette(void *palette);
  
  };
  