6 #include "s2tc_compressor.h"
7 #include "s2tc_common.h"
17 inline bool operator<(const color_t &a, const color_t &b)
29 // 16 differences must fit in int
30 // i.e. a difference must be lower than 2^27
32 // shift right, rounded
33 #define SHRR(a,n) (((a) + (1 << ((n)-1))) >> (n))
35 inline int color_dist_avg(const color_t &a, const color_t &b)
37 int dr = a.r - b.r; // multiplier: 31 (-1..1)
38 int dg = a.g - b.g; // multiplier: 63 (-1..1)
39 int db = a.b - b.b; // multiplier: 31 (-1..1)
40 return ((dr*dr) << 2) + dg*dg + ((db*db) << 2);
43 inline int color_dist_wavg(const color_t &a, const color_t &b)
45 int dr = a.r - b.r; // multiplier: 31 (-1..1)
46 int dg = a.g - b.g; // multiplier: 63 (-1..1)
47 int db = a.b - b.b; // multiplier: 31 (-1..1)
48 return ((dr*dr) << 2) + ((dg*dg) << 2) + (db*db);
52 inline int color_dist_yuv(const color_t &a, const color_t &b)
54 int dr = a.r - b.r; // multiplier: 31 (-1..1)
55 int dg = a.g - b.g; // multiplier: 63 (-1..1)
56 int db = a.b - b.b; // multiplier: 31 (-1..1)
57 int y = dr * 30*2 + dg * 59 + db * 11*2; // multiplier: 6259
58 int u = dr * 202 - y; // * 0.5 / (1 - 0.30)
59 int v = db * 202 - y; // * 0.5 / (1 - 0.11)
60 return ((y*y) << 1) + SHRR(u*u, 3) + SHRR(v*v, 4);
61 // weight for u: sqrt(2^-4) / (0.5 / (1 - 0.30)) = 0.350
62 // weight for v: sqrt(2^-5) / (0.5 / (1 - 0.11)) = 0.315
65 inline int color_dist_rgb(const color_t &a, const color_t &b)
67 int dr = a.r - b.r; // multiplier: 31 (-1..1)
68 int dg = a.g - b.g; // multiplier: 63 (-1..1)
69 int db = a.b - b.b; // multiplier: 31 (-1..1)
70 int y = dr * 21*2 + dg * 72 + db * 7*2; // multiplier: 6272
71 int u = dr * 202 - y; // * 0.5 / (1 - 0.21)
72 int v = db * 202 - y; // * 0.5 / (1 - 0.07)
73 return ((y*y) << 1) + SHRR(u*u, 3) + SHRR(v*v, 4);
74 // weight for u: sqrt(2^-4) / (0.5 / (1 - 0.21)) = 0.395
75 // weight for v: sqrt(2^-5) / (0.5 / (1 - 0.07)) = 0.328
78 inline int color_dist_srgb(const color_t &a, const color_t &b)
80 int dr = a.r * (int) a.r - b.r * (int) b.r; // multiplier: 31*31
81 int dg = a.g * (int) a.g - b.g * (int) b.g; // multiplier: 63*63
82 int db = a.b * (int) a.b - b.b * (int) b.b; // multiplier: 31*31
83 int y = dr * 21*2*2 + dg * 72 + db * 7*2*2; // multiplier: 393400
84 int u = dr * 409 - y; // * 0.5 / (1 - 0.30)
85 int v = db * 409 - y; // * 0.5 / (1 - 0.11)
86 int sy = SHRR(y, 3) * SHRR(y, 4);
87 int su = SHRR(u, 3) * SHRR(u, 4);
88 int sv = SHRR(v, 3) * SHRR(v, 4);
89 return SHRR(sy, 4) + SHRR(su, 8) + SHRR(sv, 9);
90 // weight for u: sqrt(2^-4) / (0.5 / (1 - 0.30)) = 0.350
91 // weight for v: sqrt(2^-5) / (0.5 / (1 - 0.11)) = 0.315
94 inline int srgb_get_y(const color_t &a)
97 int r = a.r * (int) a.r;
98 int g = a.g * (int) a.g;
99 int b = a.b * (int) a.b;
101 int y = 37 * (r * 21*2*2 + g * 72 + b * 7*2*2); // multiplier: 14555800
102 // square root it (!)
103 y = sqrtf(y) + 0.5f; // now in range 0 to 3815
107 inline int color_dist_srgb_mixed(const color_t &a, const color_t &b)
110 int ay = srgb_get_y(a);
111 int by = srgb_get_y(b);
113 int au = a.r * 191 - ay;
114 int av = a.b * 191 - ay;
115 int bu = b.r * 191 - by;
116 int bv = b.b * 191 - by;
121 return ((y*y) << 3) + SHRR(u*u, 1) + SHRR(v*v, 2);
126 // FIXME this is likely broken
127 inline int color_dist_lab_srgb(const color_t &a, const color_t &b)
130 float ar = powf(a.r / 31.0f, 2.4f);
131 float ag = powf(a.g / 63.0f, 2.4f);
132 float ab = powf(a.b / 31.0f, 2.4f);
133 float br = powf(b.r / 31.0f, 2.4f);
134 float bg = powf(b.g / 63.0f, 2.4f);
135 float bb = powf(b.b / 31.0f, 2.4f);
136 // convert to CIE XYZ
137 float aX = 0.4124f * ar + 0.3576f * ag + 0.1805f * ab;
138 float aY = 0.2126f * ar + 0.7152f * ag + 0.0722f * ab;
139 float aZ = 0.0193f * ar + 0.1192f * ag + 0.9505f * ab;
140 float bX = 0.4124f * br + 0.3576f * bg + 0.1805f * bb;
141 float bY = 0.2126f * br + 0.7152f * bg + 0.0722f * bb;
142 float bZ = 0.0193f * br + 0.1192f * bg + 0.9505f * bb;
143 // convert to CIE Lab
147 float aL = 116 * cbrtf(aY / Yn) - 16;
148 float aA = 500 * (cbrtf(aX / Xn) - cbrtf(aY / Yn));
149 float aB = 200 * (cbrtf(aY / Yn) - cbrtf(aZ / Zn));
150 float bL = 116 * cbrtf(bY / Yn) - 16;
151 float bA = 500 * (cbrtf(bX / Xn) - cbrtf(bY / Yn));
152 float bB = 200 * (cbrtf(bY / Yn) - cbrtf(bZ / Zn));
153 // euclidean distance, but moving weight away from A and B
154 return 1000 * ((aL - bL) * (aL - bL) + (aA - bA) * (aA - bA) + (aB - bB) * (aB - bB));
157 inline int color_dist_normalmap(const color_t &a, const color_t &b)
159 float ca[3], cb[3], n;
160 ca[0] = a.r / 31.0f * 2 - 1;
161 ca[1] = a.g / 63.0f * 2 - 1;
162 ca[2] = a.b / 31.0f * 2 - 1;
163 cb[0] = b.r / 31.0f * 2 - 1;
164 cb[1] = b.g / 63.0f * 2 - 1;
165 cb[2] = b.b / 31.0f * 2 - 1;
166 n = sqrt(ca[0] * ca[0] + ca[1] * ca[1] + ca[2] * ca[2]);
174 n = sqrt(cb[0] * cb[0] + cb[1] * cb[1] + cb[2] * cb[2]);
186 (cb[0] - ca[0]) * (cb[0] - ca[0])
188 (cb[1] - ca[1]) * (cb[1] - ca[1])
190 (cb[2] - ca[2]) * (cb[2] - ca[2])
193 // max value: 1000 * (4 + 4 + 4) = 6000
196 typedef int ColorDistFunc(const color_t &a, const color_t &b);
198 inline int alpha_dist(unsigned char a, unsigned char b)
200 return (a - (int) b) * (a - (int) b);
203 template <class T, class F>
205 // m: total color count (including non-counted inputs)
207 inline void reduce_colors_inplace(T *c, int n, int m, F dist)
215 for(i = 0; i < n; ++i)
218 for(j = i+1; j < n; ++j)
220 int d = dist(c[i], c[j]);
221 dists[i][j] = dists[j][i] = d;
227 for(j = 0; j < n; ++j)
229 int d = dist(c[i], c[j]);
233 for(i = 0; i < m; ++i)
234 for(j = i+1; j < m; ++j)
237 for(k = 0; k < n; ++k)
239 int di = dists[i][k];
240 int dj = dists[j][k];
244 if(bestsum < 0 || sum < bestsum)
256 template <class T, class F>
257 inline void reduce_colors_inplace_2fixpoints(T *c, int n, int m, F dist, const T &fix0, const T &fix1)
265 for(i = 0; i < n; ++i)
268 for(j = i+1; j < n; ++j)
270 int d = dist(c[i], c[j]);
271 dists[i][j] = dists[j][i] = d;
277 for(j = 0; j < n; ++j)
279 int d = dist(c[i], c[j]);
283 // then the two extra rows
284 for(j = 0; j < n; ++j)
286 int d = dist(fix0, c[j]);
289 for(j = 0; j < n; ++j)
291 int d = dist(fix1, c[j]);
294 for(i = 0; i < m; ++i)
295 for(j = i+1; j < m; ++j)
298 for(k = 0; k < n; ++k)
300 int di = dists[i][k];
301 int dj = dists[j][k];
302 int d0 = dists[m][k];
303 int d1 = dists[m+1][k];
304 int m = min(min(di, dj), min(d0, d1));
307 if(bestsum < 0 || sum < bestsum)
327 template<ColorDistFunc ColorDist> inline int refine_component_encode(int comp)
331 template<> inline int refine_component_encode<color_dist_srgb>(int comp)
335 template<> inline int refine_component_encode<color_dist_srgb_mixed>(int comp)
339 template<> inline int refine_component_encode<color_dist_lab_srgb>(int comp)
344 template<ColorDistFunc ColorDist> inline int refine_component_decode(int comp)
348 template<> inline int refine_component_decode<color_dist_srgb>(int comp)
350 return sqrtf(comp) + 0.5f;
352 template<> inline int refine_component_decode<color_dist_srgb_mixed>(int comp)
354 return sqrtf(comp) + 0.5f;
356 template<> inline int refine_component_decode<color_dist_lab_srgb>(int comp)
358 return sqrtf(comp) + 0.5f;
361 template<DxtMode dxt, ColorDistFunc ColorDist, CompressionMode mode, RefinementMode refine>
362 inline void s2tc_encode_block(unsigned char *out, const unsigned char *rgba, int iw, int w, int h, int nrandom)
364 color_t c[16 + (mode == MODE_RANDOM ? nrandom : 0)];
366 unsigned char ca[16];
370 if(mode == MODE_FAST)
372 // FAST: trick from libtxc_dxtn: just get brightest and darkest colors, and encode using these
374 color_t c0 = {0, 0, 0};
380 int dmin = ColorDist(c[0], c0);
388 for(x = 0; x < w; ++x)
389 for(y = !x; y < h; ++y)
391 c[2].r = rgba[(x + y * iw) * 4 + 2];
392 c[2].g = rgba[(x + y * iw) * 4 + 1];
393 c[2].b = rgba[(x + y * iw) * 4 + 0];
395 int d = ColorDist(c[2], c0);
409 ca[2] = rgba[(x + y * iw) * 4 + 3];
421 for(x = 0; x < w; ++x)
422 for(y = 0; y < h; ++y)
424 c[n].r = rgba[(x + y * iw) * 4 + 2];
425 c[n].g = rgba[(x + y * iw) * 4 + 1];
426 c[n].b = rgba[(x + y * iw) * 4 + 0];
428 ca[n] = rgba[(x + y * iw) * 4 + 3];
433 if(mode == MODE_RANDOM)
437 for(x = 1; x < n; ++x)
439 mins.r = min(mins.r, c[x].r);
440 mins.g = min(mins.g, c[x].g);
441 mins.b = min(mins.b, c[x].b);
442 maxs.r = max(maxs.r, c[x].r);
443 maxs.g = max(maxs.g, c[x].g);
444 maxs.b = max(maxs.b, c[x].b);
446 color_t len = { maxs.r - mins.r + 1, maxs.g - mins.g + 1, maxs.b - mins.b + 1 };
447 for(x = 0; x < nrandom; ++x)
449 c[m].r = mins.r + rand() % len.r;
450 c[m].g = mins.g + rand() % len.g;
451 c[m].b = mins.b + rand() % len.b;
457 // hack for last miplevel
465 reduce_colors_inplace(c, n, m, ColorDist);
467 reduce_colors_inplace_2fixpoints(ca, n, n, alpha_dist, (unsigned char) 0, (unsigned char) 255);
470 if(refine == REFINE_NEVER)
489 int nc0 = 0, na0 = 0, sc0r = 0, sc0g = 0, sc0b = 0, sa0 = 0;
490 int nc1 = 0, na1 = 0, sc1r = 0, sc1g = 0, sc1b = 0, sa1 = 0;
492 memset(out, 0, (dxt == DXT1) ? 8 : 16);
493 for(x = 0; x < w; ++x)
494 for(y = 0; y < h; ++y)
496 int pindex = (x+y*4);
497 c[2].r = rgba[(x + y * iw) * 4 + 2];
498 c[2].g = rgba[(x + y * iw) * 4 + 1];
499 c[2].b = rgba[(x + y * iw) * 4 + 0];
500 ca[2] = rgba[(x + y * iw) * 4 + 3];
506 int bitindex = pindex * 3;
507 da[0] = alpha_dist(ca[0], ca[2]);
508 da[1] = alpha_dist(ca[1], ca[2]);
509 da[2] = alpha_dist(0, ca[2]);
510 da[3] = alpha_dist(255, ca[2]);
511 if(da[2] <= da[0] && da[2] <= da[1] && da[2] <= da[3])
515 out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
517 out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
519 else if(da[3] <= da[0] && da[3] <= da[1])
522 out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
524 out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
526 out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
528 else if(da[0] <= da[1])
531 if(refine != REFINE_NEVER)
540 out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
541 if(refine != REFINE_NEVER)
548 if(ColorDist(c[0], c[2]) > ColorDist(c[1], c[2]))
550 int bitindex = pindex * 2;
551 out[bitindex / 8 + 12] |= (1 << (bitindex % 8));
552 if(refine != REFINE_NEVER)
555 sc1r += refine_component_encode<ColorDist>(c[2].r);
556 sc1g += refine_component_encode<ColorDist>(c[2].g);
557 sc1b += refine_component_encode<ColorDist>(c[2].b);
562 if(refine != REFINE_NEVER)
565 sc0r += refine_component_encode<ColorDist>(c[2].r);
566 sc0g += refine_component_encode<ColorDist>(c[2].g);
567 sc0b += refine_component_encode<ColorDist>(c[2].b);
573 int bitindex = pindex * 4;
574 out[bitindex / 8 + 0] |= (ca[2] << (bitindex % 8));
576 if(ColorDist(c[0], c[2]) > ColorDist(c[1], c[2]))
578 int bitindex = pindex * 2;
579 out[bitindex / 8 + 12] |= (1 << (bitindex % 8));
580 if(refine != REFINE_NEVER)
583 sc1r += refine_component_encode<ColorDist>(c[2].r);
584 sc1g += refine_component_encode<ColorDist>(c[2].g);
585 sc1b += refine_component_encode<ColorDist>(c[2].b);
590 if(refine != REFINE_NEVER)
593 sc0r += refine_component_encode<ColorDist>(c[2].r);
594 sc0g += refine_component_encode<ColorDist>(c[2].g);
595 sc0b += refine_component_encode<ColorDist>(c[2].b);
601 int bitindex = pindex * 2;
603 out[bitindex / 8 + 4] |= (3 << (bitindex % 8));
604 else if(ColorDist(c[0], c[2]) > ColorDist(c[1], c[2]))
606 out[bitindex / 8 + 4] |= (1 << (bitindex % 8));
607 if(refine != REFINE_NEVER)
610 sc1r += refine_component_encode<ColorDist>(c[2].r);
611 sc1g += refine_component_encode<ColorDist>(c[2].g);
612 sc1b += refine_component_encode<ColorDist>(c[2].b);
617 if(refine != REFINE_NEVER)
620 sc0r += refine_component_encode<ColorDist>(c[2].r);
621 sc0g += refine_component_encode<ColorDist>(c[2].g);
622 sc0b += refine_component_encode<ColorDist>(c[2].b);
629 if(refine != REFINE_NEVER)
631 // REFINEMENT: trick from libtxc_dxtn: reassign the colors to an average of the colors encoded with that value
635 if(refine == REFINE_CHECK)
641 ca[0] = (2 * sa0 + na0) / (2 * na0);
643 ca[1] = (2 * sa1 + na1) / (2 * na1);
645 if(refine == REFINE_CHECK)
652 c[0].r = refine_component_decode<ColorDist>((2 * sc0r + nc0) / (2 * nc0));
653 c[0].g = refine_component_decode<ColorDist>((2 * sc0g + nc0) / (2 * nc0));
654 c[0].b = refine_component_decode<ColorDist>((2 * sc0b + nc0) / (2 * nc0));
658 c[1].r = refine_component_decode<ColorDist>((2 * sc1r + nc1) / (2 * nc1));
659 c[1].g = refine_component_decode<ColorDist>((2 * sc1g + nc1) / (2 * nc1));
660 c[1].b = refine_component_decode<ColorDist>((2 * sc1b + nc1) / (2 * nc1));
663 if(refine == REFINE_CHECK)
667 for(x = 0; x < w; ++x)
668 for(y = 0; y < h; ++y)
670 int pindex = (x+y*4);
671 c[4].r = rgba[(x + y * iw) * 4 + 2];
672 c[4].g = rgba[(x + y * iw) * 4 + 1];
673 c[4].b = rgba[(x + y * iw) * 4 + 0];
674 ca[4] = rgba[(x + y * iw) * 4 + 3];
675 if(dxt == DXT1 && !ca[4])
677 int bitindex = pindex * 2;
678 if(out[bitindex / 8 + (dxt == DXT1 ? 4 : 12)] & (1 << (bitindex % 8)))
681 score_01 += ColorDist(c[1], c[4]);
682 score_23 += ColorDist(c[3], c[4]);
687 score_01 += ColorDist(c[0], c[4]);
688 score_23 += ColorDist(c[2], c[4]);
692 if(score_23 < score_01)
694 // refinement was BAD
699 // alpha refinement is always good and doesn't
700 // need to be checked because alpha is linear
711 for(int pindex = 0; pindex < 16; ++pindex)
713 int bitindex_set = pindex * 3;
714 int bitindex_test = bitindex_set + 3;
715 if(!(out[bitindex_test / 8] & (1 << (bitindex_test % 8))))
716 out[bitindex_set / 8] ^= (1 << (bitindex_set % 8));
728 out[4] ^= 0x55 & ~(out[4] >> 1);
729 out[5] ^= 0x55 & ~(out[5] >> 1);
730 out[6] ^= 0x55 & ~(out[6] >> 1);
731 out[7] ^= 0x55 & ~(out[7] >> 1);
735 out[12] ^= 0x55 & ~(out[12] >> 1);
736 out[13] ^= 0x55 & ~(out[13] >> 1);
737 out[14] ^= 0x55 & ~(out[14] >> 1);
738 out[15] ^= 0x55 & ~(out[15] >> 1);
748 out[8] = ((c[0].g & 0x07) << 5) | c[0].b;
749 out[9] = (c[0].r << 3) | (c[0].g >> 3);
750 out[10] = ((c[1].g & 0x07) << 5) | c[1].b;
751 out[11] = (c[1].r << 3) | (c[1].g >> 3);
754 out[0] = ((c[0].g & 0x07) << 5) | c[0].b;
755 out[1] = (c[0].r << 3) | (c[0].g >> 3);
756 out[2] = ((c[1].g & 0x07) << 5) | c[1].b;
757 out[3] = (c[1].r << 3) | (c[1].g >> 3);
762 // compile time dispatch magic
763 template<DxtMode dxt, ColorDistFunc ColorDist, CompressionMode mode>
764 inline s2tc_encode_block_func_t s2tc_encode_block_func(RefinementMode refine)
769 return s2tc_encode_block<dxt, ColorDist, mode, REFINE_NEVER>;
771 // these color dist functions do not need the refinement check, as they always improve the situation
772 if(ColorDist != color_dist_avg && ColorDist != color_dist_wavg)
773 return s2tc_encode_block<dxt, ColorDist, mode, REFINE_CHECK>;
776 return s2tc_encode_block<dxt, ColorDist, mode, REFINE_ALWAYS>;
780 template<DxtMode dxt, ColorDistFunc ColorDist>
781 inline s2tc_encode_block_func_t s2tc_encode_block_func(int nrandom, RefinementMode refine)
784 return s2tc_encode_block_func<dxt, ColorDist, MODE_RANDOM>(refine);
785 else if(nrandom == 0 || ColorDist == color_dist_normalmap) // MODE_FAST not supported for normalmaps, sorry
786 return s2tc_encode_block_func<dxt, ColorDist, MODE_NORMAL>(refine);
788 return s2tc_encode_block_func<dxt, ColorDist, MODE_FAST>(refine);
791 template<ColorDistFunc ColorDist>
792 inline s2tc_encode_block_func_t s2tc_encode_block_func(DxtMode dxt, int nrandom, RefinementMode refine)
797 return s2tc_encode_block_func<DXT1, ColorDist>(nrandom, refine);
800 return s2tc_encode_block_func<DXT3, ColorDist>(nrandom, refine);
804 return s2tc_encode_block_func<DXT5, ColorDist>(nrandom, refine);
810 s2tc_encode_block_func_t s2tc_encode_block_func(DxtMode dxt, ColorDistMode cd, int nrandom, RefinementMode refine)
815 return s2tc_encode_block_func<color_dist_rgb>(dxt, nrandom, refine);
818 return s2tc_encode_block_func<color_dist_yuv>(dxt, nrandom, refine);
821 return s2tc_encode_block_func<color_dist_srgb>(dxt, nrandom, refine);
824 return s2tc_encode_block_func<color_dist_srgb_mixed>(dxt, nrandom, refine);
827 return s2tc_encode_block_func<color_dist_lab_srgb>(dxt, nrandom, refine);
830 return s2tc_encode_block_func<color_dist_avg>(dxt, nrandom, refine);
834 return s2tc_encode_block_func<color_dist_wavg>(dxt, nrandom, refine);
837 return s2tc_encode_block_func<color_dist_normalmap>(dxt, nrandom, refine);
844 inline int diffuse(int *diff, int src, int shift)
846 int maxval = (1 << (8 - shift)) - 1;
848 int ret = max(0, min(src >> shift, maxval));
849 // simulate decoding ("loop filter")
850 int loop = (ret << shift) | (ret >> (8 - 2 * shift));
856 void rgb565_image(unsigned char *out, const unsigned char *rgba, int w, int h, int srccomps, int bgr, int alphabits)
865 for(y = 0; y < h; ++y)
866 for(x = 0; x < w; ++x)
868 out[(x + y * w) * 4 + 2] = diffuse(&diffuse_r, rgba[(x + y * w) * srccomps + 2], 3);
869 out[(x + y * w) * 4 + 1] = diffuse(&diffuse_g, rgba[(x + y * w) * srccomps + 1], 2);
870 out[(x + y * w) * 4 + 0] = diffuse(&diffuse_b, rgba[(x + y * w) * srccomps + 0], 3);
875 for(y = 0; y < h; ++y)
876 for(x = 0; x < w; ++x)
878 out[(x + y * w) * 4 + 2] = diffuse(&diffuse_r, rgba[(x + y * w) * srccomps + 0], 3);
879 out[(x + y * w) * 4 + 1] = diffuse(&diffuse_g, rgba[(x + y * w) * srccomps + 1], 2);
880 out[(x + y * w) * 4 + 0] = diffuse(&diffuse_b, rgba[(x + y * w) * srccomps + 2], 3);
885 int alphadiffuse = 8 - alphabits;
886 for(y = 0; y < h; ++y)
887 for(x = 0; x < w; ++x)
888 out[(x + y * w) * 4 + 3] = diffuse(&diffuse_a, rgba[(x + y * w) * srccomps + 3], alphadiffuse);
892 int alpharange = (1 << alphabits) - 1;
893 for(y = 0; y < h; ++y)
894 for(x = 0; x < w; ++x)
895 out[(x + y * w) * 4 + 3] = alpharange;