From d71eec8062e852e56f03102ba4b4e87dc485821d Mon Sep 17 00:00:00 2001 From: docwhat Date: Sun, 14 Nov 1999 06:43:18 +0000 Subject: Initial revision git-svn-id: http://svn.leocad.org/trunk@2 c7d43263-9d01-0410-8a33-9dba5d9f93d6 --- common/quant.cpp | 639 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 639 insertions(+) create mode 100644 common/quant.cpp (limited to 'common/quant.cpp') diff --git a/common/quant.cpp b/common/quant.cpp new file mode 100644 index 0000000..f32cc68 --- /dev/null +++ b/common/quant.cpp @@ -0,0 +1,639 @@ +/////////////////////////////////////// +// DL1 Quantization + +#include +#include +#include +#include "quant.h" + +//#define FAST // improves speed but uses a lot of memory +#define QUAL1 // slightly improves quality +//#define QUAL2 // slightly improves quality + +//#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 + +static void dlq_finish(); +static int build_table(unsigned char *image, unsigned long pixels); +static void fixheap(unsigned long id); +static void reduce_table(int num_colors); +static void set_palette(int index, int level); +static void closest_color(int index, int level); +static int quantize_image(unsigned char *in, unsigned char *out, int width, int height, int dither); +static int bestcolor(int r, int g, int b); + +static unsigned char palette[3][256]; +static CUBE *rgb_table[6]; +static unsigned short r_offset[256], g_offset[256], b_offset[256]; +static CLOSEST_INFO c_info; +static int tot_colors, pal_index; +static unsigned long *squares; +static FCUBE *heap = NULL; +static short *dl_image = NULL; + +bool dl1quant(unsigned char *inbuf, unsigned char *outbuf, int width, int height, int quant_to, int dither, unsigned char userpal[3][256]) +{ + int i; + + // dlq_init + 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; + + // dlq_start + 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) + { + dlq_finish(); + return false; + } + + pal_index = 0; + + if (build_table(inbuf, width*height) == 0) + { + dlq_finish(); + return false; + } + + reduce_table(quant_to); + set_palette(0, 0); + + if (quantize_image(inbuf, outbuf, width, height, dither) == 0) + { + dlq_finish(); + return false; + } + + dlq_finish(); + for (i = 0; i < 256; i++) + { + userpal[0][i] = palette[0][i]; + userpal[1][i] = palette[1][i]; + userpal[2][i] = palette[2][i]; + } + + return true; +} + +static void dlq_finish(void) +{ + for (int 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 +static int build_table(unsigned char *image, unsigned long pixels) +{ + unsigned long i = 0, index = 0, cur_count = 0, head = 0, tail = 0; + long 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 = (unsigned short)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; +} + +static void fixheap(unsigned long id) +{ + unsigned char thres_level = heap[id].level; + unsigned long thres_index = heap[id].index, index = 0; + unsigned long half_totc = tot_colors >> 1; + unsigned long thres_val = rgb_table[thres_level][thres_index].pixels_in_cube; + + while (id <= half_totc) + { + index = id << 1; + + if (index < (unsigned long)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 = (unsigned short)thres_index; +} + +static void reduce_table(int num_colors) +{ + while (tot_colors > num_colors) + { + unsigned char tmp_level = heap[1].level, t_level = (tmp_level - 1) > 0 ? (tmp_level - 1) : 0; + unsigned long 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 = (unsigned short)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); + } +} + +static 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) + { + unsigned long 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] = (unsigned char)((r_sum + (sum >> 1)) / sum); + palette[1][pal_index] = (unsigned char)((g_sum + (sum >> 1)) / sum); + palette[2][pal_index] = (unsigned char)((b_sum + (sum >> 1)) / sum); + + pal_index++; + } +} + +static void closest_color(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)) + closest_color((index << 3) + i, level + 1); + + if (rgb_table[level][index].pixel_count) + { + long dist, r_dist, g_dist, b_dist; + unsigned char pal_num = rgb_table[level][index].palette_index; + + // Determine if this color is "closest". + r_dist = palette[0][pal_num] - c_info.red; + g_dist = palette[1][pal_num] - c_info.green; + b_dist = palette[2][pal_num] - c_info.blue; + + dist = squares[r_dist] + squares[g_dist] + squares[b_dist]; + + if (dist < (long)c_info.distance) + { + c_info.distance = dist; + c_info.palette_index = pal_num; + } + } +} + +// returns 1 on success, 0 on failure +static int quantize_image(unsigned char *in, unsigned char *out, int width, int height, int dither) +{ + if (!dither) + { + unsigned long i = 0, pixels = width * height; + unsigned short level = 0, index = 0; + unsigned char tmp_r = 0, tmp_g = 0, tmp_b = 0, cube = 0; + unsigned char *lookup = NULL; + + lookup = (unsigned char*)malloc(sizeof(char) * 32768); + if (lookup == NULL) + return 0; + + for (i = 0; i < 32768; i++) + if (rgb_table[5][i].pixel_count) + { + tmp_r = (unsigned char)((i & 0x4000) >> 7 | (i & 0x0800) >> 5 | + (i & 0x0100) >> 3 | (i & 0x0020) >> 1 | + (i & 0x0004) << 1); + tmp_g = (unsigned char)((i & 0x2000) >> 6 | (i & 0x0400) >> 4 | + (i & 0x0080) >> 2 | (i & 0x0010) >> 0 | + (i & 0x0002) << 2); + tmp_b = (unsigned char)((i & 0x1000) >> 5 | (i & 0x0200) >> 3 | + (i & 0x0040) >> 1 | (i & 0x0008) << 1 | + (i & 0x0001) << 3); + #ifdef QUAL2 + lookup[i] = bestcolor(tmp_r, tmp_g, tmp_b); + #else + c_info.red = tmp_r + 4; + c_info.green = tmp_g + 4; + c_info.blue = tmp_b + 4; + level = 0; + index = 0; + for (;;) { + cube = (tmp_r&128) >> 5 | (tmp_g&128) >> 6 | (tmp_b&128) >> 7; + if ((rgb_table[level][index].children & (1 << cube)) == 0) { + c_info.distance = (unsigned long)~0L; + closest_color(index, level); + lookup[i] = c_info.palette_index; + break; + } + level++; + index = (index << 3) + cube; + tmp_r <<= 1; + tmp_g <<= 1; + tmp_b <<= 1; + } + #endif + } + + for (i = 0; i < pixels; i++) + { + #ifdef FAST + out[i] = lookup[dl_image[i]]; + #else + out[i] = lookup[r_offset[in[0]] + g_offset[in[1]] + b_offset[in[2]]]; + in += 3; + #endif + } + + free(lookup); + + } + else // dither + { + #if defined(DITHER2) || defined(DITHER4) + long i = 0, j = 0; + long r_pix = 0, g_pix = 0, b_pix = 0; + long offset = 0, dir = 0; + long two_val = 0, odd_scanline = 0; + long err_len = (width + 2) * 3; + unsigned char *range_tbl = NULL, *range = NULL; + short *lookup = NULL, *erowerr = NULL, *orowerr = NULL; + short *thisrowerr = NULL, *nextrowerr = NULL; + char *dith_max_tbl = NULL, *dith_max = NULL; + + lookup = (short*)malloc(sizeof(short) * 32768); + erowerr = (short*)malloc(sizeof(short) * err_len); + orowerr = (short*)malloc(sizeof(short) * err_len); + range_tbl = (unsigned char*)malloc(3 * 256); + range = range_tbl + 256; + dith_max_tbl= (char*)malloc(512); + dith_max = dith_max_tbl + 256; + + if (range_tbl == NULL || lookup == NULL || erowerr == NULL || orowerr == NULL || dith_max_tbl == NULL) + { + if (range_tbl != NULL) + { + free(range_tbl); + range_tbl=NULL; + } + if (lookup != NULL) + { + free(lookup); + lookup=NULL; + } + if (erowerr != NULL) + { + free(erowerr); + erowerr=NULL; + } + if (orowerr != NULL) + { + free(orowerr); + orowerr=NULL; + } + if (dith_max_tbl != NULL) + { + free(dith_max_tbl); + dith_max_tbl=NULL; + } + return 0; + } + + for (i = 0; i < err_len; i++) + erowerr[i] = 0; + + for (i = 0; i < 32768; i++) + lookup[i] = -1; + + for (i = 0; i < 256; i++) + { + range_tbl[i] = 0; + range_tbl[i + 256] = (unsigned char) i; + range_tbl[i + 512] = 255; + } + + for (i = 0; i < 256; i++) + { + dith_max_tbl[i] = -DITHER_MAX; + dith_max_tbl[i + 256] = DITHER_MAX; + } + for (i = -DITHER_MAX; i <= DITHER_MAX; i++) + dith_max_tbl[i + 256] = (char)i; + + for (i = 0 ; i < height; i++) + { + if (odd_scanline) + { + dir = -1; + in += (width - 1) * 3; + out += (width - 1); + thisrowerr = orowerr + 3; + nextrowerr = erowerr + width * 3; + } + else + { + dir = 1; + thisrowerr = erowerr + 3; + nextrowerr = orowerr + width * 3; + } + + nextrowerr[0] = nextrowerr[1] = nextrowerr[2] = 0; + + for (j = 0; j < width; j++) + { + #ifdef DITHER2 + r_pix = range[(thisrowerr[0] >> 1) + in[0]]; + g_pix = range[(thisrowerr[1] >> 1) + in[1]]; + b_pix = range[(thisrowerr[2] >> 1) + in[2]]; + #else + r_pix = range[((thisrowerr[0] + 8) >> 4) + in[0]]; + g_pix = range[((thisrowerr[1] + 8) >> 4) + in[1]]; + b_pix = range[((thisrowerr[2] + 8) >> 4) + in[2]]; + #endif + offset = (r_pix&248) << 7 | (g_pix&248) << 2 | b_pix >> 3; + if (lookup[offset] < 0) + lookup[offset] = bestcolor(r_pix, g_pix, b_pix); + *out = (unsigned char)lookup[offset]; + r_pix = dith_max[r_pix - palette[0][lookup[offset]]]; + g_pix = dith_max[g_pix - palette[1][lookup[offset]]]; + b_pix = dith_max[b_pix - palette[2][lookup[offset]]]; + + #ifdef DITHER2 + nextrowerr[0 ] = (short)r_pix; + thisrowerr[0+3] += (short)r_pix; + nextrowerr[1 ] = (short)g_pix; + thisrowerr[1+3] += (short)g_pix; + nextrowerr[2 ] = (short)b_pix; + thisrowerr[2+3] += (short)b_pix; + #else + two_val = r_pix * 2; + nextrowerr[0-3] = r_pix; + r_pix += two_val; + nextrowerr[0+3] += r_pix; + r_pix += two_val; + nextrowerr[0 ] += r_pix; + r_pix += two_val; + thisrowerr[0+3] += r_pix; + two_val = g_pix * 2; + nextrowerr[1-3] = g_pix; + g_pix += two_val; + nextrowerr[1+3] += g_pix; + g_pix += two_val; + nextrowerr[1 ] += g_pix; + g_pix += two_val; + thisrowerr[1+3] += g_pix; + two_val = b_pix * 2; + nextrowerr[2-3] = b_pix; + b_pix += two_val; + nextrowerr[2+3] += b_pix; + b_pix += two_val; + nextrowerr[2 ] += b_pix; + b_pix += two_val; + thisrowerr[2+3] += b_pix; + #endif + thisrowerr += 3; + nextrowerr -= 3; + in += dir * 3; + out += dir; + } + + if ((i % 2) == 1) + { + in += (width + 1) * 3; + out += (width + 1); + } + + odd_scanline = !odd_scanline; + } + + free(range_tbl); + free(lookup); + free(erowerr); + free(orowerr); + free(dith_max_tbl); + #else + long i = 0, j = 0; + long r_pix = 0, g_pix = 0, b_pix=0; + long r_err = 0, g_err = 0, b_err=0; + long offset = 0; + BYTE *range_tbl = (BYTE*)malloc(3 * 256), *range = range_tbl + 256; + short *lookup = (sshort *)malloc(sizeof(short) * 32768); + + if (range_tbl == NULL || lookup == NULL) + { + if (range_tbl != NULL) + free(range_tbl); + if (lookup != NULL) + free(lookup); + return 0; + } + + for (i = 0; i < 32768; i++) + lookup[i] = -1; + + for (i = 0; i < 256; i++) + { + range_tbl[i] = 0; + range_tbl[i + 256] = (BYTE) i; + range_tbl[i + 512] = 255; + } + + for (i = 0; i < height; i++) + { + r_err = g_err = b_err = 0; + for (j = width - 1; j >= 0; j--) + { + r_pix = range[(r_err >> 1) + in[0]]; + g_pix = range[(g_err >> 1) + in[1]]; + b_pix = range[(b_err >> 1) + in[2]]; + + offset = (r_pix&248) << 7 | (g_pix&248) << 2 | b_pix >> 3; + + if (lookup[offset] < 0) + lookup[offset] = bestcolor(r_pix, g_pix, b_pix); + + *out++ = (unsigned char)lookup[offset]; + + r_err = r_pix - palette[0][lookup[offset]]; + g_err = g_pix - palette[1][lookup[offset]]; + b_err = b_pix - palette[2][lookup[offset]]; + + in += 3; + } + } + + free(range_tbl); + free(lookup); + #endif + } + + return 1; +} + +static int bestcolor(int r, int g, int b) +{ + unsigned long i = 0, bestcolor = 0, curdist = 0, mindist = 0; + long rdist = 0, gdist = 0, bdist = 0; + + r = (r & 248) + 4; + g = (g & 248) + 4; + b = (b & 248) + 4; + mindist = 200000; + + for (i = 0; i < (unsigned long)tot_colors; i++) + { + rdist = palette[0][i] - r; + gdist = palette[1][i] - g; + bdist = palette[2][i] - b; + curdist = squares[rdist] + squares[gdist] + squares[bdist]; + + if (curdist < mindist) + { + mindist = curdist; + bestcolor = i; + } + } + return bestcolor; +} -- cgit v1.2.3