//
//	This has been modified from Dennis Lee's original version
//	

/*
 * DL1 Quantization
 * ================
 *
 * File: dl1quant.c
 * Author: Dennis Lee   E-mail: denlee@ecf.utoronto.ca
 *
 * Copyright (C) 1993-1997 Dennis Lee
 *
 * C implementation of DL1 Quantization.
 * DL1 Quantization is a 2-pass color quantizer optimized for speed.
 * The method was designed around the steps required by a 2-pass
 * quantizer and constructing a model that would require the least
 * amount of extra work.  The resulting method is extremely fast --
 * about half the speed of a memcpy.  That should make DL1 Quant the
 * fastest 2-pass color quantizer.
 *
 * This quantizer's quality is also among the best, slightly
 * better than Wan et al's marginal variance based quantizer.  For
 * more on DL1 Quant's performance and other related information,
 * see DLQUANT.TXT included in this distribution.
 *
 *
 * NOTES
 * =====
 *
 * The dithering code is based on code from the IJG's jpeg library.
 *
 * This source code may be freely copied, modified, and redistributed,
 * provided this copyright notice is attached.
 * Compiled versions of this code, modified or not, are free for
 * personal use.  Compiled versions used in distributed software
 * is also free, but a notification must be sent to the author.
 * An e-mail to denlee@ecf.utoronto.ca will do.
 *
 */

#include "stdafx.h"

#ifdef __cplusplus
extern "C" {
#endif


#include <stdlib.h>
#include "dl1quant.h"

//#define FAST        /* improves speed but uses a lot of memory */
#define QUAL1       /* slightly improves quality */
//#define QUAL2       /* slightly improves quality */

/* define *one* of the following dither options */
//#define DITHER1     /* 1-val error diffusion dither */
#define DITHER2     /* 2-val error diffusion dither */
//#define DITHER4     /* 4-val error diffusion dither (Floyd-Steinberg) */

#define DITHER_MAX  20

LOCAL uchar palette[3][256];
LOCAL CUBE *rgb_table[6];
LOCAL ushort r_offset[256], g_offset[256], b_offset[256];
LOCAL CLOSEST_INFO c_info;
LOCAL int tot_colors, pal_index;
LOCAL ulong *squares;
LOCAL FCUBE *heap = NULL;
LOCAL short *dl_image = NULL;

/* returns 1 on success, 0 on failure */
GLOBAL int dl1quant(uchar *inbuf, 
					uchar *outbuf, 
					int width, 
					int height, 
					int quant_to,
					int dither, 
					uchar userpal[3][256]) {

	dlq_init();

    if (dlq_start() == 0) {
		dlq_finish();
		return 0;
	}

    if (build_table(inbuf, (ulong)width * (ulong)height) == 0) {
		dlq_finish();
		return 0;
    }
    
	reduce_table(quant_to);
    set_palette(0, 0);
    
	if (quantize_image(inbuf, outbuf, width, height, dither) == 0) {
		dlq_finish();
		return 0;
    }

    dlq_finish();
    copy_pal(userpal);

    return 1;
}

LOCAL void copy_pal(uchar userpal[3][256]) 
{
    int i;

    for (i = 0; i < 256; i++) {
		userpal[0][i] = palette[0][i];
		userpal[1][i] = palette[1][i];
		userpal[2][i] = palette[2][i];
    }
}

LOCAL void dlq_init(void) 
{
    int i;

	for (i=0;i<6;i++) {
		rgb_table[i]=NULL;
	}

	tot_colors=0;
	pal_index=0;

	heap = NULL;
	dl_image = NULL;

    for (i = 0; i < 256; i++) {
		r_offset[i] = (i & 128) << 7 | (i & 64) << 5 | (i & 32) << 3 |
				  (i & 16)  << 1 | (i & 8)  >> 1;
		g_offset[i] = (i & 128) << 6 | (i & 64) << 4 | (i & 32) << 2 |
				  (i & 16)  << 0 | (i & 8)  >> 2;
		b_offset[i] = (i & 128) << 5 | (i & 64) << 3 | (i & 32) << 1 |
				  (i & 16)  >> 1 | (i & 8)  >> 3;
    }


	c_info.palette_index=0;
	c_info.red=0;
	c_info.green=0;
	c_info.blue=0;
    c_info.distance=0;

    for (i = (-255); i <= 255; i++)
		c_info.squares[i+255] = i*i;

	for (i=0;i<256;i++) {
		palette[0][i]=0;
		palette[1][i]=0;
		palette[2][i]=0;
	}

    squares = c_info.squares + 255;
}

/* returns 1 on success, 0 on failure */
LOCAL int dlq_start(void) 
{
    int i;

    rgb_table[0] = (CUBE *) calloc(sizeof(CUBE), 1);
    rgb_table[1] = (CUBE *) calloc(sizeof(CUBE), 8);
    rgb_table[2] = (CUBE *) calloc(sizeof(CUBE), 64);
    rgb_table[3] = (CUBE *) calloc(sizeof(CUBE), 512);
    rgb_table[4] = (CUBE *) calloc(sizeof(CUBE), 4096);
    rgb_table[5] = (CUBE *) calloc(sizeof(CUBE), 32768);

    for (i = 0; i <= 5; i++)
		if (rgb_table[i] == NULL)
		    return 0;

    pal_index = 0;
    return 1;
}

LOCAL void dlq_finish(void) 
{
	int i;

	for (i=0;i<6;i++) {
		if (rgb_table[i] != NULL) {
			free(rgb_table[i]);
			rgb_table[i]=NULL;
		}
	}

    if (heap != NULL) {
		free(heap);
		heap=NULL;
	}
    
	if (dl_image != NULL) {
		free(dl_image);
		dl_image=NULL;
	}

	memset(&c_info, 0, sizeof(CLOSEST_INFO));

	tot_colors=pal_index=0;

}

/* returns 1 on success, 0 on failure */
LOCAL int build_table(uchar *image, ulong pixels) 
{
    ulong i=0;
	ulong index=0;
	ulong cur_count=0;
	ulong head=0;
	ulong tail=0;
    slong j=0;

    heap = (FCUBE *) malloc(sizeof(FCUBE) * 32769);
    if (heap == NULL)
		return 0;

#ifdef FAST
    dl_image = malloc(sizeof(short) * pixels);
    if (dl_image == NULL)
		return 0;
#endif

    for (i = 0; i < pixels; i++) {
#ifdef FAST
		dl_image[i] = index = r_offset[image[0]] + g_offset[image[1]] + b_offset[image[2]];
#else
		index = r_offset[image[0]] + g_offset[image[1]] + b_offset[image[2]];
#endif
#ifdef QUAL1
		rgb_table[5][index].r += image[0];
		rgb_table[5][index].g += image[1];
		rgb_table[5][index].b += image[2];
#endif
		rgb_table[5][index].pixel_count++;
		image += 3;
    }

    tot_colors = 0;
		for (i = 0; i < 32768; i++) {
		cur_count = rgb_table[5][i].pixel_count;
		if (cur_count) {
			heap[++tot_colors].level = 5;
			heap[tot_colors].index = (ushort)i;
			rgb_table[5][i].pixels_in_cube = cur_count;
#ifndef QUAL1
			rgb_table[5][i].r = cur_count * (((i & 0x4000) >> 7 |
					(i & 0x0800) >> 5 | (i & 0x0100) >> 3 |
					(i & 0x0020) >> 1 | (i & 0x0004) << 1) + 4);
			rgb_table[5][i].g = cur_count * (((i & 0x2000) >> 6 |
					(i & 0x0400) >> 4 | (i & 0x0080) >> 2 |
					(i & 0x0010) >> 0 | (i & 0x0002) << 2) + 4);
			rgb_table[5][i].b = cur_count * (((i & 0x1000) >> 5 |
					(i & 0x0200) >> 3 | (i & 0x0040) >> 1 |
					(i & 0x0008) << 1 | (i & 0x0001) << 3) + 4);
#endif
			head = i;
			for (j = 4; j >= 0; j--) {
				tail = head & 0x7;
				head >>= 3;
				rgb_table[j][head].pixels_in_cube += cur_count;
				rgb_table[j][head].children |= 1 << tail;
			}
		}
    }

    for (i = tot_colors; i > 0; i--)
		fixheap(i);

    return 1;
}

LOCAL void fixheap(ulong id) 
{
    uchar thres_level = heap[id].level;
    ulong thres_index = heap[id].index;
	ulong index=0;
	ulong half_totc = tot_colors >> 1;
	ulong thres_val = rgb_table[thres_level][thres_index].pixels_in_cube;

    while (id <= half_totc) {
		index = id << 1;

		if (index < (ulong)tot_colors)
			if (rgb_table[heap[index].level][heap[index].index].pixels_in_cube
			  > rgb_table[heap[index+1].level][heap[index+1].index].pixels_in_cube)
			index++;

		if (thres_val <= rgb_table[heap[index].level][heap[index].index].pixels_in_cube)
			break;
		else {
			heap[id] = heap[index];
			id = index;
		}
    }
    heap[id].level = thres_level;
    heap[id].index = (ushort)thres_index;
}

LOCAL void reduce_table(int num_colors) 
{
	while (tot_colors > num_colors) {

		uchar tmp_level = heap[1].level, t_level = max(0,tmp_level - 1);
		ulong tmp_index = heap[1].index, t_index = tmp_index >> 3;

		if (rgb_table[t_level][t_index].pixel_count)
			heap[1] = heap[tot_colors--];
		else {
			heap[1].level = t_level;
			heap[1].index = (ushort)t_index;
		}

		rgb_table[t_level][t_index].pixel_count += rgb_table[tmp_level][tmp_index].pixel_count;
		rgb_table[t_level][t_index].r += rgb_table[tmp_level][tmp_index].r;
		rgb_table[t_level][t_index].g += rgb_table[tmp_level][tmp_index].g;
		rgb_table[t_level][t_index].b += rgb_table[tmp_level][tmp_index].b;
		rgb_table[t_level][t_index].children &= ~(1 << (tmp_index & 0x7));

		fixheap(1);
    }
}

LOCAL void set_palette(int index, int level) 
{
    int i;

    if (rgb_table[level][index].children) {
		for (i = 7; i >= 0; i--) {
			if (rgb_table[level][index].children & (1 << i)) {
				set_palette((index << 3) + i, level + 1);
			}
		}
	}

    if (rgb_table[level][index].pixel_count) {
		ulong r_sum, g_sum, b_sum, sum;

		rgb_table[level][index].palette_index = pal_index;
		
		r_sum = rgb_table[level][index].r;
		g_sum = rgb_table[level][index].g;
		b_sum = rgb_table[level][index].b;
		
		sum = rgb_table[level][index].pixel_count;

		palette[0][pal_index] = (BYTE)((r_sum + (sum >> 1)) / sum);
		palette[1][pal_index] = (BYTE)((g_sum + (sum >> 1)) / sum);
		palette[2][pal_index] = (BYTE)((b_sum + (sum >> 1)) / sum);

		pal_index++;
    }