/* -*- mode: C++; tab-width: 4 -*- */
/* ================================================================================== */
/* Copyright (c) 1998-1999 3Com Corporation or its subsidiaries. All rights reserved. */
/* ================================================================================== */

#include "EmulatorCommon.h"
#include "Quantizer.h"

static long PrvGetRowBytes (LPBITMAPINFO dib);

struct NODE
{
	Bool	bIsLeaf;		// TRUE if node has no children
	uae_u32 nPixelCount;	// Number of pixels represented by this leaf
	uae_u32 nRedSum;		// Sum of red components
	uae_u32 nGreenSum;		// Sum of green components
	uae_u32 nBlueSum;		// Sum of blue components
	NODE*	pChild[8];		// Pointers to child nodes
	NODE*	pNext;			// Pointer to next reducible node
};

CQuantizer::CQuantizer (uae_u32 nMaxColors, uae_u32 nColorBits)
{
	assert (nColorBits <= 8);

	m_pTree = NULL;
	m_nLeafCount = 0;
	for (int i=0; i<=(int) nColorBits; i++)
		m_pReducibleNodes[i] = NULL;
	m_nMaxColors = nMaxColors;
	m_nColorBits = nColorBits;
}

CQuantizer::~CQuantizer ()
{
	if (m_pTree != NULL)
		DeleteTree (&m_pTree);
}

Bool CQuantizer::ProcessImage (/*HANDLE hImage*/LPBITMAPINFO bm, void* bits)
{
	uae_u32 rmask, gmask, bmask;
	int rright, gright, bright;
	int rleft, gleft, bleft;
	uae_u8* pbBits;
	uae_u32* pwBits;
	uae_u32* pdwBits;
	uae_u8 r, g, b;
	uae_u32 wColor;
	uae_u32 dwColor;
	int i, j;
	HDC hdc;
	uae_u8* pBuffer;
	BITMAPINFO bmi;

#if 0
	DIBSECTION ds;
	::GetObject (hImage, sizeof (ds), &ds);
	int nPad = ds.dsBm.bmWidthBytes - (((ds.dsBmih.biWidth *
		ds.dsBmih.biBitCount) + 7) / 8);
#else
	int nPad = ::PrvGetRowBytes (bm) - (((bm->bmiHeader.biWidth *
		bm->bmiHeader.biBitCount) + 7) / 8);
#endif

#if 0
   switch (ds.dsBmih.biBitCount) {
#else
   switch (bm->bmiHeader.biBitCount) {
#endif

#if 0
	case 1: // 1-bit DIB
	case 4: // 4-bit DIB
	case 8: // 8-bit DIB
		//
		// The strategy here is to use ::GetDIBits to convert the
		// image into a 24-bit DIB one scan line at a time. A pleasant
		// side effect of using ::GetDIBits in this manner is that RLE-
		// encoded 4-bit and 8-bit DIBs will be uncompressed.
		//
		hdc = ::GetDC (NULL);
		pBuffer = new uae_u8[ds.dsBmih.biWidth * 3];

		::ZeroMemory (&bmi, sizeof (bmi));
		bmi.bmiHeader.biSize = sizeof (BITMAPINFOHEADER);
		bmi.bmiHeader.biWidth = ds.dsBmih.biWidth;
		bmi.bmiHeader.biHeight = ds.dsBmih.biHeight;
		bmi.bmiHeader.biPlanes = 1;
		bmi.bmiHeader.biBitCount = 24;
		bmi.bmiHeader.biCompression = BI_RGB;

		for (i=0; i<ds.dsBmih.biHeight; i++) {
			::GetDIBits (hdc, (HBITMAP) hImage, i, 1, pBuffer, &bmi,
				DIB_RGB_COLORS);
			pbBits = pBuffer;
			for (j=0; j<ds.dsBmih.biWidth; j++) {
				b = *pbBits++;
				g = *pbBits++;
				r = *pbBits++;
				AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
					m_pReducibleNodes);
				while (m_nLeafCount > m_nMaxColors)
					ReduceTree (m_nColorBits, &m_nLeafCount,
						m_pReducibleNodes);
			}
		}

		delete pBuffer;
		::ReleaseDC (NULL, hdc);
		break;

	case 16: // 16-bit DIB
		if (ds.dsBmih.biCompression == BI_BITFIELDS) {
			rmask = ds.dsBitfields[0];
			gmask = ds.dsBitfields[1];
			bmask = ds.dsBitfields[2];
		}
		else {
			rmask = 0x7C00;
			gmask = 0x03E0;
			bmask = 0x001F;
		}

		rright = GetRightShiftCount (rmask);
		gright = GetRightShiftCount (gmask);
		bright = GetRightShiftCount (bmask);

		rleft = GetLeftShiftCount (rmask);
		gleft = GetLeftShiftCount (gmask);
		bleft = GetLeftShiftCount (bmask);

		pwBits = (uae_u32*) ds.dsBm.bmBits;
		for (i=0; i<ds.dsBmih.biHeight; i++) {
			for (j=0; j<ds.dsBmih.biWidth; j++) {
				wColor = *pwBits++;
				b = (uae_u8) (((wColor & (uae_u32) bmask) >> bright) << bleft);
				g = (uae_u8) (((wColor & (uae_u32) gmask) >> gright) << gleft);
				r = (uae_u8) (((wColor & (uae_u32) rmask) >> rright) << rleft);
				AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
					m_pReducibleNodes);
				while (m_nLeafCount > m_nMaxColors)
					ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
			}
			pwBits = (uae_u32*) (((uae_u8*) pwBits) + nPad);
		}
		break;
#endif

	case 24: // 24-bit DIB
#if 0
		pbBits = (uae_u8*) ds.dsBm.bmBits;
#else
		pbBits = (uae_u8*) bits;
#endif
#if 0
		for (i=0; i<ds.dsBmih.biHeight; i++) {
			for (j=0; j<ds.dsBmih.biWidth; j++) {
#else
		for (i=0; i<bm->bmiHeader.biHeight; i++) {
			for (j=0; j<bm->bmiHeader.biWidth; j++) {
#endif
				b = *pbBits++;
				g = *pbBits++;
				r = *pbBits++;
				AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
					m_pReducibleNodes);
				while (m_nLeafCount > m_nMaxColors)
					ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
			}
			pbBits += nPad;
		}
		break;

#if 0
	case 32: // 32-bit DIB
		if (ds.dsBmih.biCompression == BI_BITFIELDS) {
			rmask = ds.dsBitfields[0];
			gmask = ds.dsBitfields[1];
			bmask = ds.dsBitfields[2];
		}
		else {
			rmask = 0x00FF0000;
			gmask = 0x0000FF00;
			bmask = 0x000000FF;
		}

		rright = GetRightShiftCount (rmask);
		gright = GetRightShiftCount (gmask);
		bright = GetRightShiftCount (bmask);

		pdwBits = (uae_u32*) ds.dsBm.bmBits;
		for (i=0; i<ds.dsBmih.biHeight; i++) {
			for (j=0; j<ds.dsBmih.biWidth; j++) {
				dwColor = *pdwBits++;
				b = (uae_u8) ((dwColor & bmask) >> bright);
				g = (uae_u8) ((dwColor & gmask) >> gright);
				r = (uae_u8) ((dwColor & rmask) >> rright);
				AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
					m_pReducibleNodes);
				while (m_nLeafCount > m_nMaxColors)
					ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
			}
			pdwBits = (uae_u32*) (((uae_u8*) pdwBits) + nPad);
		}
		break;
#endif

	default: // Unrecognized color format
		return FALSE;
	}
	return TRUE;
}

int CQuantizer::GetLeftShiftCount (uae_u32 dwVal)
{
	int nCount = 0;
	for (int i=0; i<sizeof (uae_u32) * 8; i++) {
		if (dwVal & 1)
			nCount++;
		dwVal >>= 1;
	}
	return (8 - nCount);
}

int CQuantizer::GetRightShiftCount (uae_u32 dwVal)
{
	for (int i=0; i<sizeof (uae_u32) * 8; i++) {
		if (dwVal & 1)
			return i;
		dwVal >>= 1;
	}
	return -1;
}

void CQuantizer::AddColor (NODE** ppNode, uae_u8 r, uae_u8 g, uae_u8 b,
	uae_u32 nColorBits, uae_u32 nLevel, uae_u32* pLeafCount, NODE** pReducibleNodes)
{
	static uae_u8 mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };

	//
	// If the node doesn't exist, create it.
	//
	if (*ppNode == NULL)
		*ppNode = CreateNode (nLevel, nColorBits, pLeafCount,
			pReducibleNodes);

	//
	// Update color information if it's a leaf node.
	//
	if ((*ppNode)->bIsLeaf) {
		(*ppNode)->nPixelCount++;
		(*ppNode)->nRedSum += r;
		(*ppNode)->nGreenSum += g;
		(*ppNode)->nBlueSum += b;
	}

	//
	// Recurse a level deeper if the node is not a leaf.
	//
	else {
		int shift = 7 - nLevel;
		int nIndex = (((r & mask[nLevel]) >> shift) << 2) |
			(((g & mask[nLevel]) >> shift) << 1) |
			((b & mask[nLevel]) >> shift);
		AddColor (&((*ppNode)->pChild[nIndex]), r, g, b, nColorBits,
			nLevel + 1, pLeafCount, pReducibleNodes);
	}
}

NODE* CQuantizer::CreateNode (uae_u32 nLevel, uae_u32 nColorBits, uae_u32* pLeafCount,
	NODE** pReducibleNodes)
{
	NODE* pNode;

	if ((pNode = (NODE*) HeapAlloc (GetProcessHeap (), HEAP_ZERO_MEMORY,
		sizeof (NODE))) == NULL)
		return NULL;

	pNode->bIsLeaf = (nLevel == nColorBits) ? TRUE : FALSE;
	if (pNode->bIsLeaf)
		(*pLeafCount)++;
	else {
		pNode->pNext = pReducibleNodes[nLevel];
		pReducibleNodes[nLevel] = pNode;
	}
	return pNode;
}

void CQuantizer::ReduceTree (uae_u32 nColorBits, uae_u32* pLeafCount,
	NODE** pReducibleNodes)
{
	//
	// Find the deepest level containing at least one reducible node.
	//
	for (int i=nColorBits - 1; (i>0) && (pReducibleNodes[i] == NULL); i--);

	//
	// Reduce the node most recently added to the list at level i.
	//
	NODE* pNode = pReducibleNodes[i];
	pReducibleNodes[i] = pNode->pNext;

	uae_u32 nRedSum = 0;
	uae_u32 nGreenSum = 0;
	uae_u32 nBlueSum = 0;
	uae_u32 nChildren = 0;

	for (i=0; i<8; i++) {
		if (pNode->pChild[i] != NULL) {
			nRedSum += pNode->pChild[i]->nRedSum;
			nGreenSum += pNode->pChild[i]->nGreenSum;
			nBlueSum += pNode->pChild[i]->nBlueSum;
			pNode->nPixelCount += pNode->pChild[i]->nPixelCount;
			HeapFree (GetProcessHeap (), 0, pNode->pChild[i]);
			pNode->pChild[i] = NULL;
			nChildren++;
		}
	}

	pNode->bIsLeaf = TRUE;
	pNode->nRedSum = nRedSum;
	pNode->nGreenSum = nGreenSum;
	pNode->nBlueSum = nBlueSum;
	*pLeafCount -= (nChildren - 1);
}

void CQuantizer::DeleteTree (NODE** ppNode)
{
	for (int i=0; i<8; i++) {
		if ((*ppNode)->pChild[i] != NULL)
			DeleteTree (&((*ppNode)->pChild[i]));
	}
	HeapFree (GetProcessHeap (), 0, *ppNode);
	*ppNode = NULL;
}

void CQuantizer::GetPaletteColors (NODE* pTree, RGBQUAD* prgb, uae_u32* pIndex)
{
	if (pTree->bIsLeaf) {
		prgb[*pIndex].rgbRed =
			(uae_u8) ((pTree->nRedSum) / (pTree->nPixelCount));
		prgb[*pIndex].rgbGreen =
			(uae_u8) ((pTree->nGreenSum) / (pTree->nPixelCount));
		prgb[*pIndex].rgbBlue =
			(uae_u8) ((pTree->nBlueSum) / (pTree->nPixelCount));
		prgb[*pIndex].rgbReserved = 0;
		(*pIndex)++;
	}
	else {
		for (int i=0; i<8; i++) {
			if (pTree->pChild[i] != NULL)
				GetPaletteColors (pTree->pChild[i], prgb, pIndex);
		}
	}
}

uae_u32 CQuantizer::GetColorCount ()
{
	return m_nLeafCount;
}

void CQuantizer::GetColorTable (RGBQUAD* prgb)
{
	uae_u32 nIndex = 0;
	GetPaletteColors (m_pTree, prgb, &nIndex);
}


/***********************************************************************
 *
 * FUNCTION:	PrvGetRowBytes
 *
 * DESCRIPTION:	.
 *
 * PARAMETERS:	none
 *
 * RETURNED:	nothing
 *
 ***********************************************************************/

long PrvGetRowBytes (LPBITMAPINFO dib)
{
	uae_s32	biWidth = dib->bmiHeader.biWidth;
	uae_s16	biBitCount = dib->bmiHeader.biBitCount;

	return ((biWidth * biBitCount + 31) & ~31) / 8;
}