// ==========================================================

// LFPQuantizer class implementation

//

// Design and implementation by

// - 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 "Quantizers.h"

#include "FreeImage.h"

#include "Utilities.h"

LFPQuantizer::LFPQuantizer(unsigned PaletteSize) :

    m_size(0), m_limit(PaletteSize), m_index(0) {

  m_map = new MapEntry[MAP_SIZE];

  memset(m_map, 0xFF, MAP_SIZE * sizeof(MapEntry));

}

LFPQuantizer::~LFPQuantizer() {

    delete[] m_map;

}

FIBITMAP* LFPQuantizer::Quantize(FIBITMAP *dib, int ReserveSize, RGBQUAD *ReservePalette) {

  if (ReserveSize > 0 && ReservePalette != NULL) {

    AddReservePalette(ReservePalette, ReserveSize);

  }

  const unsigned width = FreeImage_GetWidth(dib);

  const unsigned height = FreeImage_GetHeight(dib);

  FIBITMAP *dib8 = FreeImage_Allocate(width, height, 8);

  if (dib8 == NULL) {

    return NULL;

  }

  const unsigned src_pitch = FreeImage_GetPitch(dib);

  const unsigned dst_pitch = FreeImage_GetPitch(dib8);

  const BYTE * const src_bits = FreeImage_GetBits(dib);

  BYTE * const dst_bits = FreeImage_GetBits(dib8);

  unsigned last_color = -1;

  int last_index = 0;

  if (FreeImage_GetBPP(dib) == 24) {

    // Getting the source pixel as an unsigned int is much faster than

    // working with FI_RGBA_xxx and shifting. However, this may fail

    // for the very last pixel, since its rgbReserved member (alpha)

    // may actually point to an address beyond the bitmap's memory. So,

    // we do not process the last scanline in the first loop.

    // Process all but the last scanline.

    for (unsigned y = 0; y < height - 1; ++y) {

      BYTE *dst_line = dst_bits + y * dst_pitch;

      const BYTE *src_line = src_bits + y * src_pitch;

      for (unsigned x = 0; x < width; ++x) {

        const unsigned color = *((unsigned *) src_line) & 0x00FFFFFF;

        if (color != last_color) {

          last_color = color;

          last_index = GetIndexForColor(color);

          if (last_index == -1) {

            FreeImage_Unload(dib8);

            return NULL;

          }

        }

        dst_line[x] = last_index;

        src_line += 3;

      }

    }

    // Process all but the last pixel of the last scanline.

    BYTE *dst_line = dst_bits + (height - 1) * dst_pitch;

    const BYTE *src_line = src_bits + (height - 1) * src_pitch;

    for (unsigned x = 0; x < width - 1; ++x) {

      const unsigned color = *((unsigned *) src_line) & 0x00FFFFFF;

      if (color != last_color) {

        last_color = color;

        last_index = GetIndexForColor(color);

        if (last_index == -1) {

          FreeImage_Unload(dib8);

          return NULL;

        }

      }

      dst_line[x] = last_index;

      src_line += 3;

    }

    // Process the last pixel (src_line should already point to it).

    const unsigned color = 0 | src_line[FI_RGBA_BLUE] << FI_RGBA_BLUE_SHIFT

        | src_line[FI_RGBA_GREEN] << FI_RGBA_GREEN_SHIFT

        | src_line[FI_RGBA_RED] << FI_RGBA_RED_SHIFT;

    if (color != last_color) {

      last_color = color;

      last_index = GetIndexForColor(color);

      if (last_index == -1) {

        FreeImage_Unload(dib8);

        return NULL;

      }

    }

    dst_line[width - 1] = last_index;

  } else {

    for (unsigned y = 0; y < height; ++y) {

      BYTE *dst_line = dst_bits + y * dst_pitch;

      const BYTE *src_line = src_bits + y * src_pitch;

      for (unsigned x = 0; x < width; ++x) {

        const unsigned color = *((unsigned *) src_line) & 0x00FFFFFF;

        if (color != last_color) {

          last_color = color;

          last_index = GetIndexForColor(color);

          if (last_index == -1) {

            FreeImage_Unload(dib8);

            return NULL;

          }

        }

        dst_line[x] = last_index;

        src_line += 4;

      }

    }

  }

  WritePalette(FreeImage_GetPalette(dib8));

  return dib8;

}

/**

 * 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

 */

inline int LFPQuantizer::GetIndexForColor(unsigned color) {

  unsigned bucket = hash(color) & (MAP_SIZE - 1);

  while (m_map[bucket].color != color) {

    if (m_map[bucket].color == EMPTY_BUCKET) {

      if (m_size == m_limit) {

        return -1;

      }

      m_map[bucket].color = color;

      m_map[bucket].index = m_index++;

      ++m_size;

      break;

    }

    bucket = (bucket + 1) % MAP_SIZE;

  }

  return m_map[bucket].index;

}

/**

 * 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 LFPQuantizer::AddReservePalette(const void *palette, unsigned size) {

  if (size > MAX_SIZE) {

    size = MAX_SIZE;

  }

  unsigned *ppal = (unsigned *) palette;

  const unsigned offset = m_limit - size;

  for (unsigned i = 0; i < size; ++i) {

    const unsigned color = *ppal++;

    const unsigned index = i + offset;

    unsigned bucket = hash(color) & (MAP_SIZE - 1);

    while((m_map[bucket].color != EMPTY_BUCKET) && (m_map[bucket].color != color)) {

      bucket = (bucket + 1) % MAP_SIZE;

    }

    if(m_map[bucket].color != color) {

      m_map[bucket].color = color;

      m_map[bucket].index = index;

    }

  }

  m_size += size;

}

/**

 * Copies the newly created palette into the specified destination

 * palette. 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 LFPQuantizer::WritePalette(void *palette) {

  for (unsigned i = 0; i < MAP_SIZE; ++i) {

    if (m_map[i].color != EMPTY_BUCKET) {

      ((unsigned *) palette)[m_map[i].index] = m_map[i].color;

    }

  }

}