Changeset 3536Tweet

Timestamp:

05/28/09 03:54:56 (4 years ago)

Author:

sam

Message:

Optimise img2twit's cell packing even more, gaining around 60 bits.

File:

• libpipi/trunk/examples/img2twit.cpp (modified) (18 diffs)

libpipi/trunk/examples/img2twit.cpp

@@ -74 +74 @@
  * this value breaks compatibility with other images. */
 #define POINTS_PER_CELL 2
+
+/* Start with a random image (1), or with a good estimate (0)? */
+#define RANDOM_START 0
 
 /*
@@ -116 +119 @@
 
 #define RANGE_XY (RANGE_Y*RANGE_X)
-#define RANGE_XYXY (RANGE_XY*RANGE_XY)
-//#define RANGE_XYXY (RANGE_Y*RANGE_X*(RANGE_Y*RANGE_X+1)/2)
+#define RANGE_XY2 (RANGE_Y*RANGE_X*(RANGE_Y*RANGE_X+1)/2)
 #define RANGE_RXY (RANGE_Y*RANGE_X*RANGE_R)
 #define RANGE_GRXY (RANGE_Y*RANGE_X*RANGE_R*RANGE_G)
@@ -147 +149 @@
     HEADER_BITS = logf(RANGE_W * RANGE_H) / logf(2);
     DATA_BITS = TOTAL_BITS - HEADER_BITS;
-#if POINTS_PER_CELL == 1
+#if POINTS_PER_CELL == 2
+    CELL_BITS = (2 * logf(RANGE_SBGR) + logf(RANGE_XY2)) / logf(2);
+    //CELL_BITS = 2 * logf(RANGE_SBGRXY) / logf(2);
+#else
     CELL_BITS = logf(RANGE_SBGRXY) / logf(2);
-#else
-    // TODO: implement the following shit
-    //float coord_bits = logf((RANGE_Y * RANGE_X) * (RANGE_Y * RANGE_X + 1) / 2);
-    //float other_bits = logf(RANGE_R * RANGE_G * RANGE_B * RANGE_S);
-    //CELL_BITS = (coord_bits + 2 * other_bits) / logf(2);
-    CELL_BITS = 2 * logf(RANGE_SBGRXY) / logf(2);
 #endif
     TOTAL_CELLS = (int)(DATA_BITS / CELL_BITS);
@@ -509 +508 @@
     float fy = (y - dy * RANGE_Y) / RANGE_Y;
 
-    int is = range2int(s, RANGE_S);
-
+    int iy = range2int(fy, RANGE_Y);
     int ix = range2int(fx, RANGE_X);
-    int iy = range2int(fy, RANGE_Y);
 
     int ir = range2int(r, RANGE_R);
@@ -518 +515 @@
     int ib = range2int(b, RANGE_B);
 
-    points[index] = iy + RANGE_Y * (ix + RANGE_X * (ib + RANGE_B *
-                      (ig + (RANGE_R * ir + (RANGE_S * is)))));
+    int is = range2int(s, RANGE_S);
+
+    points[index] = iy + RANGE_Y * (ix + RANGE_X * (ir + RANGE_R *
+                      (ig + (RANGE_G * ib + (RANGE_B * is)))));
 }
 
@@ -533 +532 @@
     float fx = int2midrange(pt % RANGE_X, RANGE_X); pt /= RANGE_X;
 
+    *y = (fy + dy) * RANGE_Y /*+ 0.5 * (index & 1)*/;
     *x = (fx + dx) * RANGE_X /*+ 0.5 * (index & 1)*/;
-    *y = (fy + dy) * RANGE_Y /*+ 0.5 * (index & 1)*/;
 
     if(final)
     {
-        *b = int2fullrange(pt % RANGE_R, RANGE_R); pt /= RANGE_R;
+        *r = int2fullrange(pt % RANGE_R, RANGE_R); pt /= RANGE_R;
         *g = int2fullrange(pt % RANGE_G, RANGE_G); pt /= RANGE_G;
-        *r = int2fullrange(pt % RANGE_B, RANGE_B); pt /= RANGE_B;
+        *b = int2fullrange(pt % RANGE_B, RANGE_B); pt /= RANGE_B;
     }
     else
     {
-        *b = int2midrange(pt % RANGE_R, RANGE_R); pt /= RANGE_R;
+        *r = int2midrange(pt % RANGE_R, RANGE_R); pt /= RANGE_R;
         *g = int2midrange(pt % RANGE_G, RANGE_G); pt /= RANGE_G;
-        *r = int2midrange(pt % RANGE_B, RANGE_B); pt /= RANGE_B;
+        *b = int2midrange(pt % RANGE_B, RANGE_B); pt /= RANGE_B;
     }
 
@@ -558 +557 @@
 }
 
-static uint32_t pack_coords(int x1, int y1, int x2, int y2)
-{
-    return ((y2 * RANGE_X + x2) * RANGE_Y + y1) * RANGE_X + x1;
+static uint32_t pack_coords(int x1, int y1, int x2, int y2, bool *swap)
+{
+    int k1 = y1 * RANGE_X + x1;
+    int k2 = y2 * RANGE_X + x2;
+
+    /* XXX: this should not happen */
+    if(k1 == k2)
+        k1 += (x1 > 0 ? -1 : 1);
+
+    *swap = k1 > k2;
+
+    if(*swap)
+    {
+        int tmp = k1; k1 = k2; k2 = tmp;
+    }
+
+    return k2 * (k2 + 1) / 2 + k1;
 }
 
 static void unpack_coords(uint32_t pack, int *x1, int *y1, int *x2, int *y2)
 {
-    *x1 = pack % RANGE_X; pack /= RANGE_X;
-    *y1 = pack % RANGE_Y; pack /= RANGE_Y;
-    *x2 = pack % RANGE_X; pack /= RANGE_X;
-    *y2 = pack % RANGE_Y;
-}
-
-#if 0
+    int k2 = ((int)sqrt(1.0 + 8 * pack) - 1) / 2;
+    int k1 = pack - k2 * (k2 + 1) / 2;
+
+    *x1 = k1 % RANGE_X;
+    *y1 = k1 / RANGE_X;
+    *x2 = k2 % RANGE_X;
+    *y2 = k2 / RANGE_X;
+}
+
+#if RANDOM_START == 1
 static void add_random_point()
 {
@@ -846 +862 @@
                 wmin = 0.0, wmax = 1.0;
 
-#if 0
+#if RANDOM_START == 1
+#   if POINTS_PER_CELL == 2
             add_random_point();
+#   endif
             add_random_point();
 #else
             /* 0.80 and 0.20 were chosen empirically, it gives a 10% better
              * initial distance. Definitely worth it. */
-#if POINTS_PER_CELL == 1
+#   if POINTS_PER_CELL == 1
             if(total < min + (max - min) / 2)
             {
-#endif
+#   endif
             add_point(xmin, ymin,
                       data[4 * (xmin + ymin * p->w) + 0] * 0.80 + mr * 0.20,
@@ -861 +879 @@
                       data[4 * (xmin + ymin * p->w) + 2] * 0.80 + mb * 0.20,
                       wmin);
-#if POINTS_PER_CELL == 1
+#   if POINTS_PER_CELL == 1
             }
             else
             {
-#endif
+#   endif
             add_point(xmax, ymax,
                       data[4 * (xmax + ymax * p->w) + 0] * 0.80 + mr * 0.20,
@@ -871 +889 @@
                       data[4 * (xmax + ymax * p->w) + 2] * 0.80 + mb * 0.20,
                       wmax);
-#if POINTS_PER_CELL == 1
+#   if POINTS_PER_CELL == 1
             }
-#endif
+#   endif
 #endif
         }
@@ -939 +957 @@
             if(ITERATIONS_PER_POINT < 0)
                 ITERATIONS_PER_POINT = 0;
-            else if(ITERATIONS_PER_POINT > 100)
-                ITERATIONS_PER_POINT = 100;
+            else if(ITERATIONS_PER_POINT > 200)
+                ITERATIONS_PER_POINT = 200;
             break;
         case 'd':
@@ -954 +972 @@
             printf("  -l, --length <size>       message length in characters (default 140)\n");
             printf("  -c, --charset <block>     character set to use (ascii, [cjk], symbols)\n");
-            printf("  -q, --quality <rate>      set image quality (0 - 10) (default 5)\n");
+            printf("  -q, --quality <rate>      set image quality (0 - 20) (default 5)\n");
             printf("  -d, --debug               print debug information\n");
             printf("  -h, --help                display this help and exit\n");
@@ -1096 +1114 @@
     } while(0)
 
-    for(int i = 0; i < 5; i++)
+    for(int i = 0; i < 2; i++)
     {
         TRY(RANGE_G++, RANGE_G--);
@@ -1142 +1160 @@
     {
         /* Resize and filter image to better state */
-        tmp = pipi_resize(src, dw * RANGE_X, dh * RANGE_Y);
+        tmp = pipi_gaussian_blur(src, 0.5 * dw * RANGE_X / width);
         pipi_free(src);
-        src = pipi_median_ext(tmp, 1, 1);
+        src = pipi_resize(tmp, dw * RANGE_X, dh * RANGE_Y);
         pipi_free(tmp);
 
@@ -1182 +1200 @@
             float fx, fy, fr, fg, fb, fs;
             get_point(pt, &fx, &fy, &fr, &fg, &fb, &fs);
-            int zonex = (int)fx / RANGE_X - 1;
-            int zoney = (int)fy / RANGE_Y - 1;
-            int zonew = 3;
-            int zoneh = 3;
-            if(zonex < 0) { zonex = 0; zonew--; }
-            if(zoney < 0) { zoney = 0; zoneh--; }
-            if(zonex + zonew >= (int)dw) { zonew--; }
-            if(zoney + zoneh >= (int)dh) { zoneh--; }
+            int zonex = (int)fx / RANGE_X - 2;
+            int zoney = (int)fy / RANGE_Y - 2;
+            int zonew = 4;
+            int zoneh = 4;
+            if(zonex < 0) { zonew += zonex; zonex = 0; }
+            if(zoney < 0) { zoneh += zoney; zoney = 0;; }
+            if(zonex + zonew > (int)dw) { zonew = dw - zonex; }
+            if(zoney + zoneh > (int)dh) { zoneh = dh - zoney; }
 
             /* Choose random operations and measure their effect */
@@ -1247 +1265 @@
 
                 /* Save image! */
-                //char buf[128];
-                //sprintf(buf, "twit%08i.bmp", success);
-                //if((success % 10) == 0)
-                //    pipi_save(tmp, buf);
+                char buf[128];
+                sprintf(buf, "twit%08i.bmp", success);
+                if((success % 10) == 0)
+                    pipi_save(tmp, buf);
             }
             else
@@ -1299 +1317 @@
             x2 = (points[i + 1] / RANGE_Y) % RANGE_X;
             y2 = points[i + 1] % RANGE_Y;
-            uint32_t pack = pack_coords(x1, y1, x2, y2);
-
-            b.push(points[i] / RANGE_XY, RANGE_SBGR);
-            b.push(points[i + 1] / RANGE_XY, RANGE_SBGR);
-            b.push(pack, RANGE_XYXY);
+
+            bool swap;
+            uint32_t pack = pack_coords(x1, y1, x2, y2, &swap);
+
+            b.push(points[i + (swap ? 1 : 0)] / RANGE_XY, RANGE_SBGR);
+            b.push(points[i + (swap ? 0 : 1)] / RANGE_XY, RANGE_SBGR);
+            b.push(pack, RANGE_XY2);
 #else
             b.push(points[i], RANGE_SBGRXY);
@@ -1322 +1342 @@
         {
 #if POINTS_PER_CELL == 2
-            uint32_t pack = b.pop(RANGE_XYXY);
+            uint32_t pack = b.pop(RANGE_XY2);
             uint32_t p2 = b.pop(RANGE_SBGR);
             uint32_t p1 = b.pop(RANGE_SBGR);
             int x1, y1, x2, y2;
+
             unpack_coords(pack, &x1, &y1, &x2, &y2);
             points[i * 2] = p1 * RANGE_XY + x1 * RANGE_Y + y1;