GitBucket
/*
* =====================================================================================
*
* Filename: build-table.cpp
*
* Description:
*
* Version: 1.0
* Created: 03/04/2011 22:11:22
* Revision: none
* Compiler: gcc
*
* Author: John Ryland (jryland), jryland@xiaofrog.com
* Company: InvertedLogic
*
* =====================================================================================
*/
#include <QApplication>
#include <QPixmap>
#include <QImage>
#include <stdio.h>
#include "dct.h"
unsigned char uclamp(int x)
{
if (x < 0)
return 0;
if (x > 255)
return 255;
return x;
}
signed char sclamp(int x)
{
if (x < -127)
return -127;
if (x > 128)
return 128;
return x;
}
void output(FILE *f, unsigned char *image)
{
int probabilitiesB[65536];
int *probabilitiesA = (int*)malloc(64*65536*sizeof(int));
memset(probabilitiesA, 0, 64*65536*sizeof(int));
memset(probabilitiesB, 0, 65536*sizeof(int));
int prevBlockDCT[64];
memset(prevBlockDCT, 0, 64*sizeof(int));
/*
for (int j = 0; j < 32; j++) {
for (int i = 0; i < 32; i++) {
unsigned int val = 0;
for (int x = 0; x < 16; x++)
for (int y = 0; y < 16; y++)
val += image[512*(j*16+y)+i*16+x];
unsigned int b = val / 256;
fwrite(&b, 4, 1, f);
}
}
*/
for (int j = 0; j < 32; j++) {
for (int i = 0; i < 32; i++) {
unsigned char min = 255;
unsigned char max = 0;
unsigned char count[256];
memset(count, 0, 256);
for (int x = 0; x < 16; x++)
for (int y = 0; y < 16; y++) {
unsigned char pix = image[512*(j*16+y)+i*16+x];
if ( pix < min )
min = pix;
if ( pix > max )
max = pix;
count[pix]++;
}
// perhaps scan for outliers?
// could code for outliers with position
// (two nibbles for the 16x16 coord, and value, total 2 bytes per outlier)
// need heuristic to determine the number of outliers to code this way
//printf("min: %i, max: %i, range: %i\n", min, max, max-min);
//unsigned int b = val / 256;
unsigned char scale = 0;
unsigned char range = max - min;
if ( range > 16 ) {
unsigned char r = range >> 4;
while (r) {
scale += 1;
r >>= 1;
}
}
unsigned char distinctValueCount = 0;
for (int i = 0; i < 256; i++) {
if ( count[i] )
distinctValueCount++;
}
unsigned char min_exclude_outter = 255;
unsigned char max_exclude_outter = 0;
for (int i = 0; i < 256; i++) {
if ( count[i] ) {
count[i]--;
for (; i < 256; i++) {
if ( count[i] ) {
count[i]--;
break;
}
}
}
}
for (int i = 255; i >= 0; i--) {
if ( count[i] ) {
count[i]--;
for (; i >= 0; i--) {
if ( count[i] ) {
count[i]--;
break;
}
}
}
}
for (int i = 0; i < 256; i++) {
if ( count[i] ) {
min_exclude_outter = i;
break;
}
}
for (int i = 255; i >= 0; i--) {
if ( count[i] ) {
max_exclude_outter = i;
break;
}
}
unsigned char scale2 = 0;
unsigned char range2 = max_exclude_outter - min_exclude_outter;
if ( range2 > 16 ) {
unsigned char r = range2 >> 4;
while (r) {
scale2 += 1;
r >>= 1;
}
}
/*
printf("min: %i, max: %i, range: %i, scale: %i, distincts: %i, mi2: %i, ma2: %i, r2: %i, s2: %i\n", min,
max, range, scale, distinctValueCount, min_exclude_outter, max_exclude_outter,
range2, scale2);
*/
/*
for (int i = min; i < max; i++) {
}
*/
/*
If very small range - subtract min, write min and write with the lower bpp needed
If small distinct values - write a small LUT and write with the lower bpp needed
If small range excluding outliers - write out outliers, subtract min and write with lower bpp
Last case is if many different values over large range (kind of random image) - quantize?
Or do deltas, idea being that the values are spread over a wide range but if the image
has any coherency to it, then the deltas might be consistently low provided following a
pattern over the area that corresponds with the consistency in the image.
Perhaps need to use a cost equation to find optimal method
*/
/*
2 bits - method
3 bits - bpp
3 bits - LUT/outliers count
*/
unsigned char method = 0;
unsigned char bpp = 0;
unsigned char lut_count = 0;
// Sometimes it is better to use distinctValues instead, even if range is low.
// Also range might be low, but removing outliers can save space too with a smaller range
// can do a cost calculation:
//
// r1 = range
// r2 = range after removing outliers
// dv = distinct values
//
// c1 = cost 1 = bpp for r1 * 256 bits
// c2 = cost 2 = bpp for r2 * (256 - outliers) + outliers * 16 bits
// c3 = cost 3 = bpp for dv * 256 + dv * 8 bits
//
// Other method is doing the delta between each pixel and calculate the range of deltas
// (and also perhaps the distinct values of deltas)
// Perhaps need some various zig-zag patterns to follow to find the pattern that has
// the smallest range or set of delta values
// bpp for r1 * 256 bits + 16 bits for pattern (assuming 65536 different patterns)
// with the entropy coding that goes over everything as a final step, having runs of
// similar values might be better, so a reorder of the 16x16 cell values with a pattern
// might be useful in some cases (c1, c2, c3)
// find lowest cost method
enum {
RAW = -1,
RANGE, LUT, LUT_OUT
};
unsigned int range_bpp = 0;
unsigned int lut_bpp = 0;
unsigned int lut_out_bpp = 0;
unsigned int lowest_cost = 8 * 256; // raw coding
unsigned int lc_meth = RAW; // raw coding
unsigned int c1 = range_bpp * 256;
if ( c1 < lowest_cost ) {
lowest_cost = c1;
lc_meth = RANGE;
}
unsigned int c2 = distinctValueCount * 8 + lut_bpp * 256;
if ( c2 < lowest_cost ) {
lowest_cost = c2;
lc_meth = LUT;
}
range = 32;
distinctValueCount = 32;
if ( range < 16 ) {
method = 0;
if ( range == 0 ) {
bpp = 0;
} else if ( range == 1 ) {
bpp = 1;
} else if ( range <= 3 ) {
bpp = 2;
//} else if ( range <= 7 ) {
// bpp = 3;
} else {
bpp = 4;
}
printf("method: %i, bpp: %i, ", method, bpp);
printf("min: %i, max: %i, range: %i, scale: %i, distincts: %i, mi2: %i, ma2: %i, r2: %i, s2: %i\n", min,
max, range, scale, distinctValueCount, min_exclude_outter, max_exclude_outter,
range2, scale2);
method = (method << 6) | (bpp << 3) | lut_count;
fwrite(&method, 1, 1, f);
fwrite(&min, 1, 1, f);
//fwrite(&scale, 1, 1, f);
if ( bpp == 0 ) {
} else {
for (int y = 0; y < 16; y++)
for (int x = 0; x < 16; x+=(8/bpp)) {
unsigned char pix = 0;
for (int k = 0; k < (8/bpp); k++)
pix = (pix << bpp) | (image[512*(j*16+y)+i*16+x+k] - min);
fwrite(&pix, 1, 1, f);
}
}
} else if ( distinctValueCount < 16 ) {
method = 1;
if ( distinctValueCount == 0 ) {
bpp = 0;
} else if ( distinctValueCount == 1 ) {
bpp = 1;
} else if ( distinctValueCount <= 3 ) {
bpp = 2;
//} else if ( distinctValueCount <= 7 ) {
// bpp = 3;
} else {
bpp = 4;
}
printf("method: %i, bpp: %i, ", method, bpp);
printf("min: %i, max: %i, range: %i, scale: %i, distincts: %i, mi2: %i, ma2: %i, r2: %i, s2: %i\n", min,
max, range, scale, distinctValueCount, min_exclude_outter, max_exclude_outter,
range2, scale2);
//lut_count = (distinctValueCount + 1) / 2;
method = (method << 6) | (bpp << 3) | lut_count;
fwrite(&method, 1, 1, f);
fwrite(&distinctValueCount, 1, 1, f);
for (int x = 0; x < 16; x++)
for (int y = 0; y < 16; y++) {
unsigned char pix = image[512*(j*16+y)+i*16+x];
count[pix]++;
}
unsigned char lut[256];
unsigned char t = 0;
for (unsigned int c = 0; c <= 255; c++) {
if ( count[c] ) {
unsigned char ch = c;
fwrite(&ch, 1, 1, f);
lut[c] = t;
t++;
}
}
if ( bpp == 0 ) {
} else {
for (int y = 0; y < 16; y++)
for (int x = 0; x < 16; x+=(8/bpp)) {
unsigned char pix = 0;
for (int k = 0; k < (8/bpp); k++)
pix = (pix << bpp) | lut[image[512*(j*16+y)+i*16+x+k]];
fwrite(&pix, 1, 1, f);
}
}
} else /* quantize */ {
method = 2;
method = (method << 6) | (bpp << 3) | lut_count;
fwrite(&method, 1, 1, f);
for (int s1 = 0; s1 < 2; s1++) {
for (int t1 = 0; t1 < 2; t1++) {
int pixels[64];
int blockDCT[64];
for (int y = 0; y < 8; y++)
for (int x = 0; x < 8; x++)
pixels[y*8+x] = image[512*(j*16+y+s1*8)+i*16+x+t1*8];
encodeDCT(pixels, blockDCT);
int zeroCount = 0;
int ti = 63;
while ( !blockDCT[ti] ) {
zeroCount++;
ti--;
}
for (int x = 1; x < 64; x++) {
signed short s = blockDCT[x];
unsigned short us = (unsigned short)s;
probabilitiesA[x*65536 + us]++;
if (s > -200)
probabilitiesB[s + 200]++;
}
/*
unsigned long long signs = 0;
for (int x = 0; x < 64; x++) {
signs <<= 1;
if ( blockDCT[x] < 0 ) {
signs |= 1;
blockDCT[x] = -blockDCT[x];
}
}
fwrite(&signs, 8, 1, f);
*/
/*
unsigned long long plane;
for (int y = 0; y < 7; y++) {
plane = 0;
for (int x = 0; x < 64; x++) {
plane <<= 1;
if ( blockDCT[x] & (0x40>>y) )
plane |= 1;
}
fwrite(&plane, 8, 1, f);
}
*/
/*
unsigned int bits[256] = {
0xF | -127, // -127
0xF | -5, // -5
0x0E, // -4
0x0C, // -3
0x04, // -2
0x00, // -1
0x01, // 1
0x05, // 2
0x0D, // 3
0xF | 4, // 4
0xF | 128, // 128
};
unsigned int count[256] = {
12, // -127
12, // -5
4, // -4
4, // -3
3, // -2
2, // -1
2, // 1
3, // 2
4, // 3
12, // 4
12, // 128
};
*/
// 1 -1
// 01 1
// 001 -2
// 0001 2
// 00001 -3
// 000001 3
// 0000001 -4
// 00000001 4
// 00000000 x x
// 00 -1
// 01 1
// 10 moreA
// 11 moreB
// moreA
// 100 -2
// 101 2
// moreB
// 1100 -3
// 1101 3
// 1110 moreE
// 1111 moreD
// moreE
// 1110 1 -4
// 1110 01 4
// 1110 001 -5
// 1110 0001 5
// 1110 00001 -6
// 1110 000001 6
// 1110 0000001 -7
// 1110 00000001 7
// moreD
// 1111 x
// 1010 0000 4
// 0001 5
// 0010 6
// 0011 7
// 0100 8
// 0101 9
// 0110 10
// 0111 11
// 1000 12
// 1001 13
// 1010 14
// 1011 15
// 1100 16
// 1101 17
// 1110 18
// 1111 19
// moreD
// 1011 0000 20
// 0001 21
// 0010 22
// 0011 23
// 0100 24
// 0101 25
// 0110 26
// 0111 27
// 1000 28
// 1001 29
// 1010 30
// 1011 31
// 1100 32
// 1101 33
// 1110 34
// 1111 35
// moreE
// 1110 0000 -4
// 0001
// 0010
// 0011
// 0100
// 0101
// 0110
// 0111
// 1000
// 1001
// 1010
// 1011
// 1100
// 1101
// 1110
// 1111
// moreF
// 1111 0000
// 0001
// 0010
// 0011
// 0100
// 0101
// 0110
// 0111
// 1000
// 1001
// 1010
// 1011
// 1100
// 1101
// 1110
// 1111 moreG
// moreG
// 1111 1111 0000 0000 x
// 0000 0001 x
// 0000 0010 x
// 000 -1
// 001 1
// 010 -2
// 011 2
// 100 -3
// 101 3
// 110 moreA
// 111 moreB
// moreA
// 110000 4
// 110001 -4
// 110010 5
// 110011 -5
// 110100 6
// 110101 -6
// 110110 7
// 110111 -7
// moreB
// 11100000 8
// 11100001 -8
// 11100010 9
// 11100011 -9
// 11100100 10
// 11100101 -10
// 11100110 11
// 11100111 -11
// 11101000 12
// 11101001 -12
// 11101010 13
// 11101011 -13
// 11101100 14
// 11101101 -14
// 11101110 15
// 11101111 -15
// 11110000 16
// 11110001 -16
// 11110010 17
// 11110011 -17
// 11110100 18
// 11110101 -18
// 11110110 19
// 11110111 -19
// 11111000 20
// 11111001 -20
// 11111010 21
// 11111011 -21
// 11111100 22
// 11111101 -22
// 11111110 23
// 11111111 -23
int bitsBuffered = 0;
unsigned long bits = 0;
signed int blockDCTcode[64];
blockDCTcode[0] = blockDCT[0] - prevBlockDCT[0];
blockDCTcode[1] = blockDCT[1];
for (int x = 2; x < 3; x++)
//blockDCTcode[x] = blockDCT[x];
//blockDCTcode[x] = blockDCT[x] - prevBlockDCT[x];
blockDCTcode[x] = blockDCT[x] - blockDCT[x-1];
for (int x = 3; x < 64; x++) {
blockDCTcode[x] = blockDCT[x];
//blockDCTcode[x] = blockDCT[x] - blockDCT[x-1];
//blockDCTcode[x] = blockDCT[x] - prevBlockDCT[x];
}
unsigned long long zeros = 0;
for (int x = 0; x < 64; x++) {
zeros <<= 1;
if ( blockDCTcode[x] == 0 )
zeros |= 1;
}
fwrite(&zeros, 8, 1, f);
unsigned char count = 64 - zeroCount;
//fwrite(&count, 1, 1, f);
if ( count > 32 )
printf("count = %i\n", count);
printf("blockDCT = ");
for (int x = 0; x < 64; x++) {
//for (int x = 0; x < 64; x++) {
signed int c2 = blockDCTcode[x];
signed int ch = blockDCTcode[x];
//if (x > 10)
// ch -= blockDCT[x-1];
//if ( ch > 32 || ch < -32 )
// printf("blockDCT[x] = %i\n", ch);
//if (x == 0) {//5 && x < 8) {
//ch = (ch - blockDCT[x-1]) - (prevBlockDCT[x] - prevBlockDCT[x-1]);
// ch = ch - prevBlockDCT[x];
//}
/*
if (x > 1) {
ch = ch - blockDCT[x-1];
}
*/
if (c2 != 0)
printf("%i,", ch);
signed char c = ch;
if (c2 != 0) {
if ( c > -4 && c <= 4 ) {
int llut[9] = { 7,5,3,1,0,2,4,6,8 };
int t = llut[c + 4];
bitsBuffered += t;
bits <<= t;
bits |= 1;
} else {
bitsBuffered += 16;
bits <<= 16;
bits |= (unsigned char)(c & 0xFF);
}
/*
switch (c) {
case -1:
bitsBuffered++;
bits <<= 1;
bits |= 1;
break;
case 1:
bitsBuffered += 2;
bits <<= 2;
bits |= 1;
break;
case -2:
bitsBuffered += 3;
bits <<= 3;
bits |= 1;
break;
case 2:
bitsBuffered += 4;
bits <<= 4;
bits |= 1;
break;
case -3:
bitsBuffered += 5;
bits <<= 5;
bits |= 1;
break;
case 3:
bitsBuffered += 6;
bits <<= 6;
bits |= 1;
break;
case -4:
bitsBuffered += 7;
bits <<= 7;
bits |= 1;
break;
case 4:
bitsBuffered += 8;
bits <<= 8;
bits |= 1;
break;
default:
bitsBuffered += 16;
bits <<= 16;
bits |= (unsigned char)(c & 0xFF);
break;
}
*/
// fwrite(&c, 1, 1, f);
while ( bitsBuffered >= 8 ) {
unsigned long long b = (bits >> (bitsBuffered - 8)) & 0xFF;
unsigned char b2 = (unsigned char)b;
fwrite(&b2, 1, 1, f);
bitsBuffered -= 8;
//bits >>= 8;
}
}
// 1 -1
// 01 1
// 001 -2
// 0001 2
// 00001 -3
// 000001 3
// 0000001 -4
// 00000001 4
// 00000000 x x
}
printf("\n");
while ( bitsBuffered > 0 ) {
unsigned long long b = (bits >> (bitsBuffered - 8)) & 0xFF;
if ( bitsBuffered < 8 ) {
b = (bits << (8 - bitsBuffered)) & 0xFF;
b |= 0xFF >> (bitsBuffered - 8);
//b = (bits & (0xFF >> (8 - bitsBuffered)));
//b <<= 8 - bitsBuffered;
}
unsigned char b2 = (unsigned char)b;
fwrite(&b2, 1, 1, f);
bitsBuffered -= 8;
//bits >>= 8;
}
/*
unsigned char b2 = 0xFF;
fwrite(&b2, 1, 1, f);
b2 = 0xAB;
fwrite(&b2, 1, 1, f);
*/
for (int x = 0; x < 64; x++)
prevBlockDCT[x] = blockDCT[x];
}
}
/*
fwrite(&min, 1, 1, f);
fwrite(&scale, 1, 1, f);
for (int y = 0; y < 16; y++)
for (int x = 0; x < 16; x+=2) {
unsigned char pix1 = image[512*(j*16+y)+i*16+x+0];
unsigned char pix2 = image[512*(j*16+y)+i*16+x+1];
pix1 -= min;
pix1 >>= scale;
pix2 -= min;
pix2 >>= scale;
pix1 = (pix1 << 4) | pix2;
fwrite(&pix1, 1, 1, f);
}
*/
}
}
}
for (int x = 0; x < 64; x++)
{
int highest = 0;
int hy = 0;
for (int y = 0; y < 65536; y++) {
if ( probabilitiesA[x*65536 + y] > highest) {
highest = probabilitiesA[x*65536 + y];
hy = y;
}
}
printf("Highest prob value at [%i] is %i (%i)\n", x, hy, highest);
}
for (int x = 0; x < 400; x++) {
printf("prob value at [%i] is %i (%i)\n", x-200, probabilitiesB[x]);
}
}
int main(int argc, char *argv[])
{
QApplication app(argc, argv);
printf("starting\n");
initTables();
// testDCT();
// exit(0);
const int size = 512*512;
unsigned char *image = (unsigned char *)malloc(size);
printf("alloced mem\n");
memset(image, 0, size);
printf("zeroed mem\n");
QImage pix( QString("test02.png") );
int w = pix.width();
int h = pix.height();
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
image[y*w+x] = pix.pixel(x,y);
}
}
FILE *f = fopen("blah.out", "w");
printf("opened output\n");
output(f, image);
printf("written output\n");
fclose(f);
printf("closed output\n");
QImage outputImage(512, 512, QImage::Format_RGB888);
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
unsigned char p = image[y*w+x];
unsigned int p2 = p;
p2 = (p2 << 16) | (p2 << 8) | p2;
outputImage.setPixel(x, y, p2);
}
}
outputImage.save("output.png");
outputImage.save("output.jpg");
return 0;//app.exec();
}