summaryrefslogtreecommitdiff
path: root/src/static_libs/rg_etc/etc2_encoder.c
diff options
context:
space:
mode:
authorJean-Philippe Andre <jp.andre@samsung.com>2014-05-29 11:30:51 +0900
committerJean-Philippe Andre <jp.andre@samsung.com>2014-06-10 14:58:27 +0900
commit22c5632256bc15b0cc216849d436c6e5770e88e5 (patch)
tree167f0baf0ecc040313745f38db866b702a561a45 /src/static_libs/rg_etc/etc2_encoder.c
parentc8b3568f32a1b2b5bcc6c742791fee18e0af2962 (diff)
Evas ETC2: Implement T mode encoding
In this mode, two colors are encoded in RGB444, a multiplier and distance (index) are selected. Two extra colors are extrapolated from the main base color. As in ETC1 we have 4 base colors to paint our block. @feature
Diffstat (limited to 'src/static_libs/rg_etc/etc2_encoder.c')
-rw-r--r--src/static_libs/rg_etc/etc2_encoder.c496
1 files changed, 480 insertions, 16 deletions
diff --git a/src/static_libs/rg_etc/etc2_encoder.c b/src/static_libs/rg_etc/etc2_encoder.c
index f70385c745..8f3072484c 100644
--- a/src/static_libs/rg_etc/etc2_encoder.c
+++ b/src/static_libs/rg_etc/etc2_encoder.c
@@ -28,6 +28,30 @@ EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28#include <Eina.h> 28#include <Eina.h>
29#include "rg_etc1.h" 29#include "rg_etc1.h"
30 30
31// FIXME: Remove DEBUG
32#define DEBUG
33
34// Weights for the distance (perceptual mode) - sum is ~1024
35static const int R_WEIGHT = 299 * 1024 / 1000;
36static const int G_WEIGHT = 587 * 1024 / 1000;
37static const int B_WEIGHT = 114 * 1024 / 1000;
38
39static const int kTargetError[3] = {
40 5*5*16, // 34 dB
41 2*2*16, // 42 dB
42 0 // infinite dB
43};
44
45// For T and H modes
46static const int kDistances[8] = {
47 3, 6, 11, 16, 23, 32, 41, 64
48};
49
50// For differential mode
51static const int kSigned3bit[8] = {
52 0, 1, 2, 3, -4, -3, -2, -1
53};
54
31// For alpha support 55// For alpha support
32static const int kAlphaModifiers[16][8] = { 56static const int kAlphaModifiers[16][8] = {
33 { -3, -6, -9, -15, 2, 5, 8, 14}, 57 { -3, -6, -9, -15, 2, 5, 8, 14},
@@ -75,25 +99,40 @@ static const int kBlockWalk[16] = {
75// Simple min 99// Simple min
76#define MIN(a,b) ({ int _z = (a), _y = (b); ((_z <= _y) ? _z : _y); }) 100#define MIN(a,b) ({ int _z = (a), _y = (b); ((_z <= _y) ? _z : _y); })
77 101
102// Simple max
103#define MAX(a,b) ({ int __z = (a), __y = (b); ((__z > __y) ? __z : __y); })
104
105// Simple clamp between two values
106#define MINMAX(a,b,c) (MIN(c,MAX(a,b)))
107
78// Simple abs 108// Simple abs
79#define ABS(a) ({ int _a = (a); ((_a >= 0) ? _a : (-_a)); }) 109#define ABS(a) ({ int _a = (a); ((_a >= 0) ? _a : (-_a)); })
80 110
111// Write a BGRA value for output to Evas
112#define BGRA(r,g,b,a) ((a << 24) | (r << 16) | (g << 8) | b)
113
81#ifndef WORDS_BIGENDIAN 114#ifndef WORDS_BIGENDIAN
82/* x86 */ 115/* x86 */
83#define A_VAL(p) (((uint8_t *)(p))[3]) 116#define A_VAL(p) (((uint8_t *)(p))[3])
84#define R_VAL(p) (((uint8_t *)(p))[2]) 117#define R_VAL(p) (((uint8_t *)(p))[2])
85#define G_VAL(p) (((uint8_t *)(p))[1]) 118#define G_VAL(p) (((uint8_t *)(p))[1])
86#define B_VAL(p) (((uint8_t *)(p))[0]) 119#define B_VAL(p) (((uint8_t *)(p))[0])
120#define R_IDX 2
121#define G_IDX 1
122#define B_IDX 0
87#else 123#else
88/* ppc */ 124/* ppc */
89#define A_VAL(p) (((uint8_t *)(p))[0]) 125#define A_VAL(p) (((uint8_t *)(p))[0])
90#define R_VAL(p) (((uint8_t *)(p))[1]) 126#define R_VAL(p) (((uint8_t *)(p))[1])
91#define G_VAL(p) (((uint8_t *)(p))[2]) 127#define G_VAL(p) (((uint8_t *)(p))[2])
92#define B_VAL(p) (((uint8_t *)(p))[3]) 128#define B_VAL(p) (((uint8_t *)(p))[3])
129#define R_IDX 1
130#define G_IDX 2
131#define B_IDX 3
93#endif 132#endif
94 133
95#ifndef DBG 134#ifndef DBG
96# define DBG(fmt, ...) fprintf(stderr, fmt "\n", ## __VA_ARGS__) 135# define DBG(fmt, ...) fprintf(stderr, "%s:%d: " fmt "\n", __FUNCTION__, __LINE__, ## __VA_ARGS__)
97#endif 136#endif
98 137
99/** Pack alpha block given a modifier table and a multiplier 138/** Pack alpha block given a modifier table and a multiplier
@@ -163,7 +202,7 @@ _etc2_alpha_block_pack(uint8_t *etc2_alpha,
163 202
164static int 203static int
165_etc2_alpha_encode(uint8_t *etc2_alpha, const uint32_t *bgra, 204_etc2_alpha_encode(uint8_t *etc2_alpha, const uint32_t *bgra,
166 rg_etc1_pack_params *params EINA_UNUSED) 205 const rg_etc1_pack_params *params)
167{ 206{
168 int alphas[16], avg = 0, diff = 0, maxDiff = INT_MAX, minErr = INT_MAX; 207 int alphas[16], avg = 0, diff = 0, maxDiff = INT_MAX, minErr = INT_MAX;
169 int base_codeword; 208 int base_codeword;
@@ -196,24 +235,21 @@ _etc2_alpha_encode(uint8_t *etc2_alpha, const uint32_t *bgra,
196 } 235 }
197 236
198 // Bruteforce -- try all tables and all multipliers, oh my god this will be slow. 237 // Bruteforce -- try all tables and all multipliers, oh my god this will be slow.
199 238 max_error = kTargetError[params->m_quality];
200 switch (params->m_quality) 239 switch (params->m_quality)
201 { 240 {
202 // The follow parameters are completely arbitrary. 241 // The follow parameters are completely arbitrary.
203 // Need some real testing. 242 // Need some real testing.
204 case rg_etc1_high_quality: 243 case rg_etc1_high_quality:
205 base_range = 15; 244 base_range = 15;
206 base_step = 0; 245 base_step = 1;
207 max_error = 0;
208 break; 246 break;
209 case rg_etc1_medium_quality: 247 case rg_etc1_medium_quality:
210 base_range = 6; 248 base_range = 6;
211 base_step = 2; 249 base_step = 2;
212 max_error = 2 * 2 * 16; // 42dB
213 break; 250 break;
214 case rg_etc1_low_quality: 251 case rg_etc1_low_quality:
215 base_range = 0; 252 base_range = 0;
216 max_error = 5 * 5 * 16; // 34dB
217 break; 253 break;
218 } 254 }
219 255
@@ -248,27 +284,455 @@ pack_now:
248 return err; 284 return err;
249} 285}
250 286
287static Eina_Bool
288_etc2_t_mode_header_pack(uint8_t *etc2,
289 uint32_t color1, uint32_t color2, int distance)
290{
291 // 4 bit colors
292 int r1_4 = R_VAL(&color1) >> 4;
293 int g1_4 = G_VAL(&color1) >> 4;
294 int b1_4 = B_VAL(&color1) >> 4;
295 int r2_4 = R_VAL(&color2) >> 4;
296 int g2_4 = G_VAL(&color2) >> 4;
297 int b2_4 = B_VAL(&color2) >> 4;
298 int distanceIdx, R, dR;
299
300 for (distanceIdx = 0; distanceIdx < 8; distanceIdx++)
301 if (kDistances[distanceIdx] == distance) break;
302
303 if (distanceIdx >= 8)
304 return EINA_FALSE;
305
306 // R1. R + [dR] must be outside [0..31]. Scanning all values. Not smart.
307 R = r1_4 >> 2;
308 dR = r1_4 & 0x3;
309 for (int Rx = 0; Rx < 8; Rx++)
310 for (int dRx = 0; dRx < 2; dRx++)
311 {
312 int Rtry = R | (Rx << 2);
313 int dRtry = dR | (dRx << 2);
314 if ((Rtry + kSigned3bit[dRtry]) < 0 || (Rtry + kSigned3bit[dRtry] > 31))
315 {
316 R = Rtry;
317 dR = dRtry;
318 break;
319 }
320 }
321 if ((R + kSigned3bit[dR]) >= 0 && (R + kSigned3bit[dR] <= 31))
322 // this can't happen, should be an assert
323 return EINA_FALSE;
324
325 etc2[0] = ((R & 0x1F) << 3) | (dR & 0x7);
326
327 // G1, B1
328 etc2[1] = (g1_4 << 4) | b1_4;
329
330 // R2, G2
331 etc2[2] = (r2_4 << 4) | g2_4;
332
333 // B2, distance
334 etc2[3] = (b2_4 << 4) | ((distanceIdx >> 1) << 2) | (1 << 1) | (distanceIdx & 0x1);
335
336 return EINA_TRUE;
337}
338
339static inline int
340_rgb_distance_percept(uint32_t color1, uint32_t color2)
341{
342 int R = R_VAL(&color1) - R_VAL(&color2);
343 int G = G_VAL(&color1) - G_VAL(&color2);
344 int B = B_VAL(&color1) - B_VAL(&color2);
345 return (R * R * R_WEIGHT) + (G * G * G_WEIGHT) + (B * B * B_WEIGHT);
346}
347
348static inline int
349_rgb_distance_euclid(uint32_t color1, uint32_t color2)
350{
351 int R = R_VAL(&color1) - R_VAL(&color2);
352 int G = G_VAL(&color1) - G_VAL(&color2);
353 int B = B_VAL(&color1) - B_VAL(&color2);
354 return (R * R) + (G * G) + (B * B);
355}
356
357static unsigned int
358_etc2_t_mode_block_pack(uint8_t *etc2,
359 uint32_t color1, uint32_t color2, int distance,
360 const uint32_t *bgra, Eina_Bool write)
361{
362 uint8_t paint_colors[4][4];
363 int errAcc = 0;
364
365 for (int k = 0; k < 4; k++)
366 {
367 // Note: We don't really care about alpha...
368 paint_colors[0][k] = ((uint8_t *) &color1)[k];
369 paint_colors[1][k] = CLAMPDOWN(((uint8_t *) &color2)[k] + distance);
370 paint_colors[2][k] = ((uint8_t *) &color2)[k];
371 paint_colors[3][k] = CLAMPUP(((uint8_t *) &color2)[k] - distance);
372 }
373
374 if (write)
375 memset(etc2 + 4, 0, 4);
376
377 for (int k = 0; k < 16; k++)
378 {
379 uint32_t pixel = bgra[kBlockWalk[k]];
380 int bestDist = INT_MAX;
381 int bestIdx = 0;
382
383 for (int idx = 0; idx < 4; idx++)
384 {
385 int dist = _rgb_distance_euclid(pixel, *((uint32_t *) paint_colors[idx]));
386 if (dist < bestDist)
387 {
388 bestDist = dist;
389 bestIdx = idx;
390 if (!dist) break;
391 }
392 }
393
394 errAcc += bestDist;
395
396 if (write)
397 {
398 etc2[5 - (k >> 3)] |= ((bestIdx & 0x2) ? 1 : 0) << (k & 0x7);
399 etc2[7 - (k >> 3)] |= (bestIdx & 0x1) << (k & 0x7);
400 }
401 }
402
403 if (write)
404 {
405 if (!_etc2_t_mode_header_pack(etc2, color1, color2, distance))
406 return INT_MAX; // assert
407 }
408
409 return errAcc;
410}
411
412static uint32_t
413_color_reduce_444(uint32_t color)
414{
415 int R = R_VAL(&color);
416 int G = G_VAL(&color);
417 int B = B_VAL(&color);
418 int R1, R2, G1, G2, B1, B2;
419
420 R1 = (R & 0xF0) | (R >> 4);
421 R2 = ((R & 0xF0) + 0x10) | ((R >> 4) + 1);
422 G1 = (G & 0xF0) | (G >> 4);
423 G2 = ((G & 0xF0) + 0x10) | ((G >> 4) + 1);
424 B1 = (B & 0xF0) | (B >> 4);
425 B2 = ((B & 0xF0) + 0x10) | ((B >> 4) + 1);
426
427 R = (ABS(R - R1) <= ABS(R - R2)) ? R1 : R2;
428 G = (ABS(G - G1) <= ABS(G - G2)) ? G1 : G2;
429 B = (ABS(B - B1) <= ABS(B - B2)) ? B1 : B2;
430
431 return BGRA(R, G, B, 255);
432}
433
434static int
435_block_main_colors_find(uint32_t *color1_out, uint32_t *color2_out,
436 uint32_t color1, uint32_t color2, const uint32_t *bgra,
437 const rg_etc1_pack_params *params EINA_UNUSED)
438{
439 static const int kMaxIterations = 20;
440
441 int errAcc;
442
443 /* k-means complexity is O(n^(d.k+1) log n)
444 * In this case, n = 16, k = 2, d = 3 so 20 loops
445 */
446
447 if (color1 == color2)
448 {
449 // We should select another mode (planar) to encode flat colors
450 // We could also dither with two approximated colors
451 *color1_out = *color2_out = color1;
452 goto found;
453 }
454
455 if (color1 == color2)
456 {
457 // We should dither...
458 *color1_out = *color2_out = color1;
459 goto found;
460 }
461
462 for (int iter = 0; iter < kMaxIterations; iter++)
463 {
464 int r1 = 0, r2 = 0, g1 = 0, g2 = 0, b1 = 0, b2 = 0;
465 int cluster1_cnt = 0, cluster2_cnt = 0;
466 int cluster1[16], cluster2[16];
467 int maxDist1 = 0, maxDist2 = 0;
468 uint32_t c1, c2;
469
470 errAcc = 0;
471 memset(cluster1, 0, sizeof(cluster1));
472 memset(cluster2, 0, sizeof(cluster2));
473
474 // k-means assignment step
475 for (int k = 0; k < 16; k++)
476 {
477 int dist1 = _rgb_distance_euclid(color1, bgra[k]);
478 int dist2 = _rgb_distance_euclid(color2, bgra[k]);
479 if (dist1 <= dist2)
480 {
481 cluster1[cluster1_cnt++] = k;
482 if (dist1 > maxDist1)
483 maxDist1 = dist1;
484 }
485 else
486 {
487 cluster2[cluster2_cnt++] = k;
488 if (dist2 > maxDist2)
489 maxDist2 = dist2;
490 }
491 }
492
493 // k-means failed
494 if (!cluster1_cnt || !cluster2_cnt)
495 return -1;
496
497 // k-means update step
498 for (int k = 0; k < cluster1_cnt; k++)
499 {
500 r1 += R_VAL(bgra + cluster1[k]);
501 g1 += G_VAL(bgra + cluster1[k]);
502 b1 += B_VAL(bgra + cluster1[k]);
503 }
504
505 for (int k = 0; k < cluster2_cnt; k++)
506 {
507 r2 += R_VAL(bgra + cluster2[k]);
508 g2 += G_VAL(bgra + cluster2[k]);
509 b2 += B_VAL(bgra + cluster2[k]);
510 }
511
512 r1 /= cluster1_cnt;
513 g1 /= cluster1_cnt;
514 b1 /= cluster1_cnt;
515 r2 /= cluster2_cnt;
516 g2 /= cluster2_cnt;
517 b2 /= cluster2_cnt;
518
519 c1 = _color_reduce_444(BGRA(r1, g1, b1, 255));
520 c2 = _color_reduce_444(BGRA(r2, g2, b2, 255));
521 if (c1 == color1 && c2 == color2)
522 break;
523
524 if (c1 != c2)
525 {
526 color1 = c1;
527 color2 = c2;
528 }
529 else if (_rgb_distance_euclid(c1, color1) > _rgb_distance_euclid(c2, color2))
530 {
531 color1 = c1;
532 }
533 else
534 {
535 color2 = c2;
536 }
537 }
538
539 *color1_out = color1;
540 *color2_out = color2;
541
542found:
543 errAcc = 0;
544 for (int k = 0; k < 16; k++)
545 errAcc += _rgb_distance_euclid(bgra[k], color2);
546 return errAcc;
547}
548
549static unsigned int
550_etc2_t_mode_block_encode(uint8_t *etc2, const uint32_t *bgra,
551 const rg_etc1_pack_params *params)
552{
553 int err, bestDist = kDistances[0];
554 int minErr = INT_MAX;
555 uint32_t c1, c2, bestC1 = bgra[0], bestC2 = bgra[1];
556
557 Eina_Inlist *tried_pairs = NULL;
558 struct ColorPair {
559 EINA_INLIST;
560 uint32_t low;
561 uint32_t high;
562 };
563 struct ColorPair *pair;
564
565 /* Bruteforce algo:
566 * Bootstrap k-means clustering with all possible pairs of colors
567 * from the 4x4 block.
568 * TODO: Don't retry the same rgb444 pairs again
569 */
570
571 for (int pix1 = 0; pix1 < 15; pix1++)
572 for (int pix2 = pix1 + 1; pix2 < 16; pix2++)
573 {
574 Eina_Bool already_tried = EINA_FALSE;
575
576 // Bootstrap k-means. Find new pair of colors.
577 c1 = _color_reduce_444(bgra[pix1]);
578 c2 = _color_reduce_444(bgra[pix2]);
579
580 if (c2 > c1)
581 {
582 uint32_t tmp = c2;
583 c2 = c1;
584 c1 = tmp;
585 }
586
587 EINA_INLIST_FOREACH(tried_pairs, pair)
588 if (c1 == pair->high && c2 == pair->low)
589 {
590 already_tried = EINA_TRUE;
591 break;
592 }
593
594 if (already_tried)
595 continue;
596
597 pair = calloc(1, sizeof(*pair));
598 if (pair)
599 {
600 pair->high = c1;
601 pair->low = c2;
602 tried_pairs = eina_inlist_append(tried_pairs, EINA_INLIST_GET(pair));
603 }
604
605 // Run k-means
606 err = _block_main_colors_find(&c1, &c2, c1, c2, bgra, params);
607 if (err < 0)
608 continue;
609
610 for (int distIdx = 0; distIdx < 8; distIdx++)
611 {
612 for (int swap = 0; swap < 2; swap++)
613 {
614 if (swap)
615 {
616 uint32_t tmp = c2;
617 c2 = c1;
618 c1 = tmp;
619 }
620 err = _etc2_t_mode_block_pack(etc2, c1, c2, kDistances[distIdx], bgra, EINA_FALSE);
621 if (err < minErr)
622 {
623 bestDist = kDistances[distIdx];
624 minErr = err;
625 bestC1 = c1;
626 bestC2 = c2;
627 if (err <= kTargetError[params->m_quality])
628 goto found;
629 }
630 }
631 }
632 }
633
634found:
635 EINA_INLIST_FREE(tried_pairs, pair)
636 {
637 tried_pairs = eina_inlist_remove(tried_pairs, EINA_INLIST_GET(pair));
638 free(pair);
639 }
640
641 err = _etc2_t_mode_block_pack(etc2, bestC1, bestC2, bestDist, bgra, EINA_TRUE);
642
643 return err;
644}
645
646static unsigned int
647_block_error_calc(const uint32_t *enc, const uint32_t *orig, Eina_Bool perceptual)
648{
649 unsigned int errAcc = 0;
650
651 for (int k = 0; k < 16; k++)
652 {
653 if (perceptual)
654 errAcc += _rgb_distance_percept(enc[k], orig[k]);
655 else
656 errAcc += _rgb_distance_euclid(enc[k], orig[k]);
657 }
658
659 return errAcc;
660}
661
251unsigned int 662unsigned int
252etc2_rgba8_block_pack(unsigned char *etc2, const unsigned int *bgra, 663etc2_rgba8_block_pack(unsigned char *etc2, const unsigned int *bgra,
253 rg_etc1_pack_params *params) 664 rg_etc1_pack_params *params)
254{ 665{
255 unsigned int error; 666 rg_etc1_pack_params safe_params;
667 unsigned int errors[2], minErr = INT_MAX;
668 uint8_t etc2_try[2][8];
669 int bestSolution = 0;
670
671 safe_params.m_dithering = !!params->m_dithering;
672 safe_params.m_quality = MINMAX(params->m_quality, 0, 2);
673
674 // TODO: H mode, Planar mode
675
676 errors[0] = rg_etc1_pack_block(etc2_try[0], bgra, &safe_params); // 36.63dB
677 errors[1] = _etc2_t_mode_block_encode(etc2_try[1], bgra, &safe_params); // 36.69dB (+0.6dB)
678
679#ifdef DEBUG
680 if (errors[1] < INT_MAX)
681 for (unsigned k = 0; k < sizeof(errors) / sizeof(*errors); k++)
682 {
683 uint32_t decoded[16];
684 unsigned int real_errors[2];
685 rg_etc2_rgb8_decode_block(etc2_try[1], decoded);
686 real_errors[0] = _block_error_calc(decoded, bgra, EINA_FALSE);
687 real_errors[1] = _block_error_calc(decoded, bgra, EINA_TRUE);
688
689 if (real_errors[0] != errors[1])
690 {
691 DBG("Invalid error calc in T mode");
692 errors[1] = real_errors[0];
693 }
694 }
695#endif
256 696
257 // FIXME/TODO: For now, encode use rg_etc1 only! 697 for (unsigned k = 0; k < sizeof(errors) / sizeof(*errors); k++)
258 error = rg_etc1_pack_block(etc2 + 8, bgra, params); 698 if (errors[k] < minErr)
259 error += _etc2_alpha_encode(etc2, bgra, params); 699 {
700 minErr = errors[k];
701 bestSolution = k;
702 }
703
704 memcpy(etc2 + 8, etc2_try[bestSolution], 8);
705
706 minErr += _etc2_alpha_encode(etc2, bgra, &safe_params);
260 707
261 return error; 708 return minErr;
262} 709}
263 710
264unsigned int 711unsigned int
265etc2_rgb8_block_pack(unsigned char *etc2, const unsigned int *bgra, 712etc2_rgb8_block_pack(unsigned char *etc2, const unsigned int *bgra,
266 rg_etc1_pack_params *params) 713 rg_etc1_pack_params *params)
267{ 714{
268 unsigned int error; 715 rg_etc1_pack_params safe_params;
716 unsigned int errors[2], minErr = INT_MAX;
717 uint8_t etc2_try[8][2];
718 int bestSolution = 0;
719
720 safe_params.m_dithering = !!params->m_dithering;
721 safe_params.m_quality = MINMAX(params->m_quality, 0, 2);
722
723 // TODO: Planar mode
724
725 errors[0] = rg_etc1_pack_block(etc2_try[0], bgra, &safe_params);
726 errors[1] = _etc2_t_mode_block_encode(etc2_try[1], bgra, &safe_params);
727
728 for (unsigned k = 0; k < sizeof(errors) / sizeof(*errors); k++)
729 if (errors[k] < minErr)
730 {
731 minErr = errors[k];
732 bestSolution = k;
733 }
269 734
270 // FIXME/TODO: For now, encode use rg_etc1 only! 735 memcpy(etc2 + 8, etc2_try[bestSolution], 8);
271 error = rg_etc1_pack_block(etc2, bgra, params);
272 736
273 return error; 737 return minErr;
274} 738}