s2tc_compressor.cpp

   1 #include <math.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "s2tc_compressor.h"
   6 #include "s2tc_common.h"
   7
   8 typedef struct
   9 {
  10         signed char r, g, b;
  11 }
  12 color_t;
  13
  14 inline bool operator<(const color_t &a, const color_t &b)
  15 {
  16         signed char d;
  17         d = a.r - b.r;
  18         if(d)
  19                 return d < 0;
  20         d = a.g - b.g;
  21         if(d)
  22                 return d < 0;
  23         d = a.b - b.b;
  24         return d < 0;
  25 }
  26 // 16 differences must fit in int
  27 // i.e. a difference must be lower than 2^27
  28
  29 // shift right, rounded
  30 #define SHRR(a,n) (((a) + (1 << ((n)-1))) >> (n))
  31
  32 inline int color_dist_avg(const color_t &a, const color_t &b)
  33 {
  34         int dr = a.r - b.r; // multiplier: 31 (-1..1)
  35         int dg = a.g - b.g; // multiplier: 63 (-1..1)
  36         int db = a.b - b.b; // multiplier: 31 (-1..1)
  37         return ((dr*dr) << 2) + dg*dg + ((db*db) << 2);
  38 }
  39
  40 inline int color_dist_yuv(const color_t &a, const color_t &b)
  41 {
  42         int dr = a.r - b.r; // multiplier: 31 (-1..1)
  43         int dg = a.g - b.g; // multiplier: 63 (-1..1)
  44         int db = a.b - b.b; // multiplier: 31 (-1..1)
  45         int y = dr * 30*2 + dg * 59 + db * 11*2; // multiplier: 6259
  46         int u = dr * 202 - y; // * 0.5 / (1 - 0.30)
  47         int v = db * 202 - y; // * 0.5 / (1 - 0.11)
  48         return ((y*y) << 1) + SHRR(u*u, 3) + SHRR(v*v, 4);
  49         // weight for u: sqrt(2^-4) / (0.5 / (1 - 0.30)) = 0.350
  50         // weight for v: sqrt(2^-5) / (0.5 / (1 - 0.11)) = 0.315
  51 }
  52
  53 inline int color_dist_rgb(const color_t &a, const color_t &b)
  54 {
  55         int dr = a.r - b.r; // multiplier: 31 (-1..1)
  56         int dg = a.g - b.g; // multiplier: 63 (-1..1)
  57         int db = a.b - b.b; // multiplier: 31 (-1..1)
  58         int y = dr * 21*2 + dg * 72 + db * 7*2; // multiplier: 6272
  59         int u = dr * 202 - y; // * 0.5 / (1 - 0.21)
  60         int v = db * 202 - y; // * 0.5 / (1 - 0.07)
  61         return ((y*y) << 1) + SHRR(u*u, 3) + SHRR(v*v, 4);
  62         // weight for u: sqrt(2^-4) / (0.5 / (1 - 0.21)) = 0.395
  63         // weight for v: sqrt(2^-5) / (0.5 / (1 - 0.07)) = 0.328
  64 }
  65
  66 inline int color_dist_srgb(const color_t &a, const color_t &b)
  67 {
  68         int dr = a.r * (int) a.r - b.r * (int) b.r; // multiplier: 31*31
  69         int dg = a.g * (int) a.g - b.g * (int) b.g; // multiplier: 63*63
  70         int db = a.b * (int) a.b - b.b * (int) b.b; // multiplier: 31*31
  71         int y = dr * 21*2*2 + dg * 72 + db * 7*2*2; // multiplier: 393400
  72         int u = dr * 409 - y; // * 0.5 / (1 - 0.30)
  73         int v = db * 409 - y; // * 0.5 / (1 - 0.11)
  74         int sy = SHRR(y, 3) * SHRR(y, 4);
  75         int su = SHRR(u, 3) * SHRR(u, 4);
  76         int sv = SHRR(v, 3) * SHRR(v, 4);
  77         return SHRR(sy, 4) + SHRR(su, 8) + SHRR(sv, 9);
  78         // weight for u: sqrt(2^-4) / (0.5 / (1 - 0.30)) = 0.350
  79         // weight for v: sqrt(2^-5) / (0.5 / (1 - 0.11)) = 0.315
  80 }
  81
  82 inline int srgb_get_y(const color_t &a)
  83 {
  84         // convert to linear
  85         int r = a.r * (int) a.r;
  86         int g = a.g * (int) a.g;
  87         int b = a.b * (int) a.b;
  88         // find luminance
  89         int y = 37 * (r * 21*2*2 + g * 72 + b * 7*2*2); // multiplier: 14555800
  90         // square root it (!)
  91         y = sqrt(y); // now in range 0 to 3815
  92         return y;
  93 }
  94
  95 inline int color_dist_srgb_mixed(const color_t &a, const color_t &b)
  96 {
  97         // get Y
  98         int ay = srgb_get_y(a);
  99         int by = srgb_get_y(b);
 100         // get UV
 101         int au = a.r * 191 - ay;
 102         int av = a.b * 191 - ay;
 103         int bu = b.r * 191 - by;
 104         int bv = b.b * 191 - by;
 105         // get differences
 106         int y = ay - by;
 107         int u = au - bu;
 108         int v = av - bv;
 109         return ((y*y) << 3) + SHRR(u*u, 1) + SHRR(v*v, 2);
 110         // weight for u: ???
 111         // weight for v: ???
 112 }
 113
 114 // FIXME this is likely broken
 115 inline int color_dist_lab_srgb(const color_t &a, const color_t &b)
 116 {
 117         // undo sRGB
 118         float ar = powf(a.r / 31.0f, 2.4f);
 119         float ag = powf(a.g / 63.0f, 2.4f);
 120         float ab = powf(a.b / 31.0f, 2.4f);
 121         float br = powf(b.r / 31.0f, 2.4f);
 122         float bg = powf(b.g / 63.0f, 2.4f);
 123         float bb = powf(b.b / 31.0f, 2.4f);
 124         // convert to CIE XYZ
 125         float aX = 0.4124f * ar + 0.3576f * ag + 0.1805f * ab;
 126         float aY = 0.2126f * ar + 0.7152f * ag + 0.0722f * ab;
 127         float aZ = 0.0193f * ar + 0.1192f * ag + 0.9505f * ab;
 128         float bX = 0.4124f * br + 0.3576f * bg + 0.1805f * bb;
 129         float bY = 0.2126f * br + 0.7152f * bg + 0.0722f * bb;
 130         float bZ = 0.0193f * br + 0.1192f * bg + 0.9505f * bb;
 131         // convert to CIE Lab
 132         float Xn = 0.3127f;
 133         float Yn = 0.3290f;
 134         float Zn = 0.3583f;
 135         float aL = 116 * cbrtf(aY / Yn) - 16;
 136         float aA = 500 * (cbrtf(aX / Xn) - cbrtf(aY / Yn));
 137         float aB = 200 * (cbrtf(aY / Yn) - cbrtf(aZ / Zn));
 138         float bL = 116 * cbrtf(bY / Yn) - 16;
 139         float bA = 500 * (cbrtf(bX / Xn) - cbrtf(bY / Yn));
 140         float bB = 200 * (cbrtf(bY / Yn) - cbrtf(bZ / Zn));
 141         // euclidean distance, but moving weight away from A and B
 142         return 1000 * ((aL - bL) * (aL - bL) + (aA - bA) * (aA - bA) + (aB - bB) * (aB - bB));
 143 }
 144
 145 inline int color_dist_normalmap(const color_t &a, const color_t &b)
 146 {
 147         float ca[3], cb[3];
 148         ca[0] = a.r / 31.0 * 2 - 1;
 149         ca[1] = a.g / 63.0 * 2 - 1;
 150         ca[2] = a.b / 31.0 * 2 - 1;
 151         cb[0] = b.r / 31.0 * 2 - 1;
 152         cb[1] = b.g / 63.0 * 2 - 1;
 153         cb[2] = b.b / 31.0 * 2 - 1;
 154
 155         return
 156                 500 *
 157                 (
 158                         (cb[0] - ca[0]) * (cb[0] - ca[0])
 159                         +
 160                         (cb[1] - ca[1]) * (cb[1] - ca[1])
 161                         +
 162                         (cb[2] - ca[2]) * (cb[2] - ca[2])
 163                 )
 164                 ;
 165         // max value: 500 * (4 + 4 + 4) = 6000
 166 }
 167
 168 typedef int ColorDistFunc(const color_t &a, const color_t &b);
 169
 170 inline int alpha_dist(unsigned char a, unsigned char b)
 171 {
 172         return (a - (int) b) * (a - (int) b);
 173 }
 174
 175 template <class T, class F>
 176 // n: input count
 177 // m: total color count (including non-counted inputs)
 178 // m >= n
 179 void reduce_colors_inplace(T *c, int n, int m, F dist)
 180 {
 181         int i, j, k;
 182         int bestsum = -1;
 183         int besti = 0;
 184         int bestj = 1;
 185         int dists[m][n];
 186         // first the square
 187         for(i = 0; i < n; ++i)
 188         {
 189                 dists[i][i] = 0;
 190                 for(j = i+1; j < n; ++j)
 191                 {
 192                         int d = dist(c[i], c[j]);
 193                         dists[i][j] = dists[j][i] = d;
 194                 }
 195         }
 196         // then the box
 197         for(; i < m; ++i)
 198         {
 199                 for(j = 0; j < n; ++j)
 200                 {
 201                         int d = dist(c[i], c[j]);
 202                         dists[i][j] = d;
 203                 }
 204         }
 205         for(i = 0; i < m; ++i)
 206                 for(j = i+1; j < m; ++j)
 207                 {
 208                         int sum = 0;
 209                         for(k = 0; k < n; ++k)
 210                         {
 211                                 int di = dists[i][k];
 212                                 int dj = dists[j][k];
 213                                 int m  = min(di, dj);
 214                                 sum += m;
 215                         }
 216                         if(bestsum < 0 || sum < bestsum)
 217                         {
 218                                 bestsum = sum;
 219                                 besti = i;
 220                                 bestj = j;
 221                         }
 222                 }
 223         if(besti != 0)
 224                 c[0] = c[besti];
 225         if(bestj != 1)
 226                 c[1] = c[bestj];
 227 }
 228 template <class T, class F>
 229 void reduce_colors_inplace_2fixpoints(T *c, int n, int m, F dist, const T &fix0, const T &fix1)
 230 {
 231         int i, j, k;
 232         int bestsum = -1;
 233         int besti = 0;
 234         int bestj = 1;
 235         int dists[m+2][n];
 236         // first the square
 237         for(i = 0; i < n; ++i)
 238         {
 239                 dists[i][i] = 0;
 240                 for(j = i+1; j < n; ++j)
 241                 {
 242                         int d = dist(c[i], c[j]);
 243                         dists[i][j] = dists[j][i] = d;
 244                 }
 245         }
 246         // then the box
 247         for(; i < m; ++i)
 248         {
 249                 for(j = 0; j < n; ++j)
 250                 {
 251                         int d = dist(c[i], c[j]);
 252                         dists[i][j] = d;
 253                 }
 254         }
 255         // then the two extra rows
 256         for(j = 0; j < n; ++j)
 257         {
 258                 int d = dist(fix0, c[j]);
 259                 dists[m][j] = d;
 260         }
 261         for(j = 0; j < n; ++j)
 262         {
 263                 int d = dist(fix1, c[j]);
 264                 dists[m+1][j] = d;
 265         }
 266         for(i = 0; i < m; ++i)
 267                 for(j = i+1; j < m; ++j)
 268                 {
 269                         int sum = 0;
 270                         for(k = 0; k < n; ++k)
 271                         {
 272                                 int di = dists[i][k];
 273                                 int dj = dists[j][k];
 274                                 int d0 = dists[m][k];
 275                                 int d1 = dists[m+1][k];
 276                                 int m  = min(min(di, dj), min(d0, d1));
 277                                 sum += m;
 278                         }
 279                         if(bestsum < 0 || sum < bestsum)
 280                         {
 281                                 bestsum = sum;
 282                                 besti = i;
 283                                 bestj = j;
 284                         }
 285                 }
 286         if(besti != 0)
 287                 c[0] = c[besti];
 288         if(bestj != 1)
 289                 c[1] = c[bestj];
 290 }
 291
 292 inline int diffuse(float *diff, float src)
 293 {
 294         int ret;
 295         src += *diff;
 296         ret = src;
 297         *diff = (src - ret);
 298         return ret;
 299 }
 300
 301 void rgb565_image(unsigned char *out, const unsigned char *rgba, int w, int h, int alpharange)
 302 {
 303         int x, y;
 304         float diffuse_r = 0;
 305         float diffuse_g = 0;
 306         float diffuse_b = 0;
 307         float diffuse_a = 0;
 308         for(y = 0; y < h; ++y)
 309                 for(x = 0; x < w; ++x)
 310                 {
 311                         out[(x + y * w) * 4 + 2] = diffuse(&diffuse_r, rgba[(x + y * w) * 4 + 2] * 31.0 / 255.0);
 312                         out[(x + y * w) * 4 + 1] = diffuse(&diffuse_g, rgba[(x + y * w) * 4 + 1] * 63.0 / 255.0);
 313                         out[(x + y * w) * 4 + 0] = diffuse(&diffuse_b, rgba[(x + y * w) * 4 + 0] * 31.0 / 255.0);
 314                         out[(x + y * w) * 4 + 3] = diffuse(&diffuse_a, rgba[(x + y * w) * 4 + 3] * (alpharange / 255.0));
 315                 }
 316 }
 317
 318 template<DxtMode dxt, ColorDistFunc ColorDist, bool userandom>
 319 void s2tc_encode_block(unsigned char *out, const unsigned char *rgba, int iw, int w, int h, int nrandom)
 320 {
 321         color_t c[16 + (userandom ? nrandom : 0)];
 322
 323         unsigned char ca[16];
 324         int n = 0, m = 0;
 325         int x, y;
 326
 327         for(x = 0; x < w; ++x)
 328                 for(y = 0; y < h; ++y)
 329                 {
 330                         c[n].r = rgba[(x + y * iw) * 4 + 2];
 331                         c[n].g = rgba[(x + y * iw) * 4 + 1];
 332                         c[n].b = rgba[(x + y * iw) * 4 + 0];
 333                         if(dxt == DXT5)
 334                                 ca[n]  = rgba[(x + y * iw) * 4 + 3];
 335                         ++n;
 336                 }
 337
 338         m = n;
 339
 340         if(userandom)
 341         {
 342                 color_t mins = c[0];
 343                 color_t maxs = c[0];
 344                 for(x = 1; x < n; ++x)
 345                 {
 346                         mins.r = min(mins.r, c[x].r);
 347                         mins.g = min(mins.g, c[x].g);
 348                         mins.b = min(mins.b, c[x].b);
 349                         maxs.r = max(maxs.r, c[x].r);
 350                         maxs.g = max(maxs.g, c[x].g);
 351                         maxs.b = max(maxs.b, c[x].b);
 352                 }
 353                 color_t len = { maxs.r - mins.r + 1, maxs.g - mins.g + 1, maxs.b - mins.b + 1 };
 354                 for(x = 0; x < nrandom; ++x)
 355                 {
 356                         c[m].r = mins.r + rand() % len.r;
 357                         c[m].g = mins.g + rand() % len.g;
 358                         c[m].b = mins.b + rand() % len.b;
 359                         ++m;
 360                 }
 361         }
 362
 363         reduce_colors_inplace(c, n, m, ColorDist);
 364         if(dxt == DXT5)
 365         {
 366                 reduce_colors_inplace_2fixpoints(ca, n, n, alpha_dist, (unsigned char) 0, (unsigned char) 255);
 367                 if(ca[1] < ca[0])
 368                 {
 369                         ca[2] = ca[0];
 370                         ca[0] = ca[1];
 371                         ca[1] = ca[2];
 372                 }
 373         }
 374         if(c[1] < c[0])
 375         {
 376                 c[2] = c[0];
 377                 c[0] = c[1];
 378                 c[1] = c[2];
 379         }
 380
 381         memset(out, 0, 16);
 382         switch(dxt)
 383         {
 384                 case DXT5:
 385                         out[0] = ca[0];
 386                         out[1] = ca[1];
 387                 case DXT3:
 388                         out[8] = ((c[0].g & 0x07) << 5) | c[0].b;
 389                         out[9] = (c[0].r << 3) | (c[0].g >> 3);
 390                         out[10] = ((c[1].g & 0x07) << 5) | c[1].b;
 391                         out[11] = (c[1].r << 3) | (c[1].g >> 3);
 392                         break;
 393                 case DXT1:
 394                         out[0] = ((c[0].g & 0x07) << 5) | c[0].b;
 395                         out[1] = (c[0].r << 3) | (c[0].g >> 3);
 396                         out[2] = ((c[1].g & 0x07) << 5) | c[1].b;
 397                         out[3] = (c[1].r << 3) | (c[1].g >> 3);
 398                         break;
 399         }
 400         for(x = 0; x < w; ++x)
 401                 for(y = 0; y < h; ++y)
 402                 {
 403                         int pindex = (x+y*4);
 404                         c[2].r = rgba[(x + y * iw) * 4 + 2];
 405                         c[2].g = rgba[(x + y * iw) * 4 + 1];
 406                         c[2].b = rgba[(x + y * iw) * 4 + 0];
 407                         ca[2]  = rgba[(x + y * iw) * 4 + 3];
 408                         switch(dxt)
 409                         {
 410                                 case DXT5:
 411                                         {
 412                                                 int da[4];
 413                                                 int bitindex = pindex * 3;
 414                                                 da[0] = alpha_dist(ca[0], ca[2]);
 415                                                 da[1] = alpha_dist(ca[1], ca[2]);
 416                                                 da[2] = alpha_dist(0, ca[2]);
 417                                                 da[3] = alpha_dist(255, ca[2]);
 418                                                 if(da[2] <= da[0] && da[2] <= da[1] && da[2] <= da[3])
 419                                                 {
 420                                                         // 6
 421                                                         ++bitindex;
 422                                                         out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
 423                                                         ++bitindex;
 424                                                         out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
 425                                                 }
 426                                                 else if(da[3] <= da[0] && da[3] <= da[1])
 427                                                 {
 428                                                         // 7
 429                                                         out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
 430                                                         ++bitindex;
 431                                                         out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
 432                                                         ++bitindex;
 433                                                         out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
 434                                                 }
 435                                                 else if(da[0] <= da[1])
 436                                                 {
 437                                                         // 0
 438                                                 }
 439                                                 else
 440                                                 {
 441                                                         // 1
 442                                                         out[bitindex / 8 + 2] |= (1 << (bitindex % 8));
 443                                                 }
 444                                         }
 445                                         if(ColorDist(c[0], c[2]) > ColorDist(c[1], c[2]))
 446                                         {
 447                                                 int bitindex = pindex * 2;
 448                                                 out[bitindex / 8 + 12] |= (1 << (bitindex % 8));
 449                                         }
 450                                         break;
 451                                 case DXT3:
 452                                         {
 453                                                 int bitindex = pindex * 4;
 454                                                 out[bitindex / 8 + 0] |= (ca[2] << (bitindex % 8));
 455                                         }
 456                                         if(ColorDist(c[0], c[2]) > ColorDist(c[1], c[2]))
 457                                         {
 458                                                 int bitindex = pindex * 2;
 459                                                 out[bitindex / 8 + 12] |= (1 << (bitindex % 8));
 460                                         }
 461                                         break;
 462                                 case DXT1:
 463                                         {
 464                                                 int bitindex = pindex * 2;
 465                                                 if(!ca[2])
 466                                                         out[bitindex / 8 + 4] |= (3 << (bitindex % 8));
 467                                                 else if(ColorDist(c[0], c[2]) > ColorDist(c[1], c[2]))
 468                                                         out[bitindex / 8 + 4] |= (1 << (bitindex % 8));
 469                                         }
 470                                         break;
 471                         }
 472                 }
 473 }
 474
 475 // compile time dispatch magic
 476 template<DxtMode dxt, ColorDistFunc ColorDist>
 477 void s2tc_encode_block(unsigned char *out, const unsigned char *rgba, int iw, int w, int h, int nrandom)
 478 {
 479         if(nrandom)
 480                 s2tc_encode_block<dxt, ColorDist, true>(out, rgba, iw, w, h, nrandom);
 481         else
 482                 s2tc_encode_block<dxt, ColorDist, false>(out, rgba, iw, w, h, nrandom);
 483 }
 484
 485 template<ColorDistFunc ColorDist>
 486 void s2tc_encode_block(unsigned char *out, const unsigned char *rgba, int iw, int w, int h, DxtMode dxt, int nrandom)
 487 {
 488         switch(dxt)
 489         {
 490                 case DXT1:
 491                         s2tc_encode_block<DXT1, ColorDist>(out, rgba, iw, w, h, nrandom);
 492                         break;
 493                 case DXT3:
 494                         s2tc_encode_block<DXT3, ColorDist>(out, rgba, iw, w, h, nrandom);
 495                         break;
 496                 default:
 497                 case DXT5:
 498                         s2tc_encode_block<DXT5, ColorDist>(out, rgba, iw, w, h, nrandom);
 499                         break;
 500         }
 501 }
 502
 503 void s2tc_encode_block(unsigned char *out, const unsigned char *rgba, int iw, int w, int h, DxtMode dxt, ColorDistMode cd, int nrandom)
 504 {
 505         switch(cd)
 506         {
 507                 case RGB:
 508                         s2tc_encode_block<color_dist_rgb>(out, rgba, iw, w, h, dxt, nrandom);
 509                         break;
 510                 case YUV:
 511                         s2tc_encode_block<color_dist_yuv>(out, rgba, iw, w, h, dxt, nrandom);
 512                         break;
 513                 case SRGB:
 514                         s2tc_encode_block<color_dist_srgb>(out, rgba, iw, w, h, dxt, nrandom);
 515                         break;
 516                 case SRGB_MIXED:
 517                         s2tc_encode_block<color_dist_srgb_mixed>(out, rgba, iw, w, h, dxt, nrandom);
 518                         break;
 519                 case LAB:
 520                         s2tc_encode_block<color_dist_lab_srgb>(out, rgba, iw, w, h, dxt, nrandom);
 521                         break;
 522                 case AVG:
 523                         s2tc_encode_block<color_dist_avg>(out, rgba, iw, w, h, dxt, nrandom);
 524                         break;
 525                 case NORMALMAP:
 526                         s2tc_encode_block<color_dist_normalmap>(out, rgba, iw, w, h, dxt, nrandom);
 527                         break;
 528         }
 529 }