source: libpipi/trunk/examples/img2twit.cpp @ 3529

Last change on this file since 3529 was 3529, checked in by Sam Hocevar, 11 years ago

Fix img2twit's rendering. Apparently CGAL's Delaunay triangulation module
does not work with negative indices.

  • Property svn:keywords set to Id
File size: 36.7 KB
Line 
1/*
2 *  img2twit      Image to short text message encoder/decoder
3 *  Copyright (c) 2009 Sam Hocevar <sam@hocevar.net>
4 *                All Rights Reserved
5 *
6 *  This program is free software. It comes without any warranty, to
7 *  the extent permitted by applicable law. You can redistribute it
8 *  and/or modify it under the terms of the Do What The Fuck You Want
9 *  To Public License, Version 2, as published by Sam Hocevar. See
10 *  http://sam.zoy.org/wtfpl/COPYING for more details.
11 */
12
13#include "config.h"
14
15#include <stdio.h>
16#include <stdlib.h>
17#include <string.h>
18#include <math.h>
19
20#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
21#include <CGAL/Delaunay_triangulation_2.h>
22#include <CGAL/natural_neighbor_coordinates_2.h>
23
24#include <pipi.h>
25
26#include "../genethumb/mygetopt.h"
27
28/*
29 * Format-dependent settings. Change this and you risk making all other
30 * generated strings unusable.
31 */
32
33/* Printable ASCII (except space) */
34#define RANGE_ASCII 0x0021, 0x007f
35
36/* CJK Unified Ideographs */
37#define RANGE_CJK 0x4e00, 0x9fa6
38//0x2e80, 0x2e9a, 0x2e9b, 0x2ef4, /* CJK Radicals Supplement */
39//0x2f00, 0x2fd6, /* Kangxi Radicals */
40//0x3400, 0x4db6, /* CJK Unified Ideographs Extension A */
41//0xac00, 0xd7a4, /* Hangul Syllables -- Korean, not Chinese */
42//0xf900, 0xfa2e, 0xfa30, 0xfa6b, 0xfa70, 0xfada, /* CJK Compat. Idgphs. */
43/* TODO: there's also the U+20000 and U+2f800 planes, but they're
44 * not supported by the Twitter Javascript filter (yet?). */
45
46/* Stupid symbols and Dingbats shit */
47#define RANGE_SYMBOLS 0x25a0, 0x2600, /* Geometric Shapes */ \
48  0x2600, 0x269e, 0x26a0, 0x26bd, 0x26c0, 0x26c4, /* Misc. Symbols */ \
49  0x2701, 0x2705, 0x2706, 0x270a, 0x270c, 0x2728, 0x2729, 0x274c, \
50    0x274d, 0x274e, 0x274f, 0x2753, 0x2756, 0x2757, 0x2758, 0x275f, \
51    0x2761, 0x2795, 0x2798, 0x27b0, 0x27b1, 0x27bf /* Dingbats */
52
53/* End of list marker */
54#define RANGE_END 0x0, 0x0
55
56/* Pre-defined character ranges XXX: must be _ordered_ */
57static const uint32_t unichars_ascii[] = { RANGE_ASCII, RANGE_END };
58static const uint32_t unichars_cjk[] = { RANGE_CJK, RANGE_END };
59static const uint32_t unichars_symbols[] = { RANGE_SYMBOLS, RANGE_END };
60
61/* The Unicode characters at disposal */
62static const uint32_t *unichars;
63
64/* The maximum image size we want to support */
65#define MAX_W 4000
66#define MAX_H 4000
67
68/* How does the algorithm work: one point per cell, or two */
69#define POINTS_PER_CELL 2
70
71/*
72 * These values can be overwritten at runtime
73 */
74
75/* Debug mode */
76static bool DEBUG_MODE = false;
77
78/* The maximum message length */
79static int MAX_MSG_LEN = 140;
80
81/* Iterations per point -- larger means slower but nicer */
82static int ITERATIONS_PER_POINT = 50;
83
84/* The range value for point parameters: X Y, red/green/blue, "strength"
85 * Tested values (on Mona Lisa) are:
86 *  16 16 5 5 5 2 -> 0.06511725914
87 *  16 16 6 7 6 1 -> 0.05731491348 *
88 *  16 16 7 6 6 1 -> 0.06450513783
89 *  14 14 7 7 6 1 -> 0.0637207893
90 *  19 19 6 6 5 1 -> 0.06801999094 */
91static unsigned int RANGE_X = 16;
92static unsigned int RANGE_Y = 16;
93static unsigned int RANGE_R = 6;
94static unsigned int RANGE_G = 6;
95static unsigned int RANGE_B = 6;
96static unsigned int RANGE_S = 1;
97
98/*
99 * These values are computed at runtime
100 */
101
102static float TOTAL_BITS;
103static float HEADER_BITS;
104static float DATA_BITS;
105static float CELL_BITS;
106
107static int NUM_CHARACTERS;
108static int MAX_ITERATIONS;
109static unsigned int TOTAL_CELLS;
110
111#define RANGE_SY (RANGE_S*RANGE_Y)
112#define RANGE_SYX (RANGE_S*RANGE_Y*RANGE_X)
113#define RANGE_SYXR (RANGE_S*RANGE_Y*RANGE_X*RANGE_R)
114#define RANGE_SYXRG (RANGE_S*RANGE_Y*RANGE_X*RANGE_R*RANGE_G)
115#define RANGE_SYXRGB (RANGE_S*RANGE_Y*RANGE_X*RANGE_R*RANGE_G*RANGE_B)
116
117struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
118typedef CGAL::Delaunay_triangulation_2<K> Delaunay_triangulation;
119typedef std::vector<std::pair<K::Point_2, K::FT> > Point_coordinate_vector;
120
121/* Global aspect ratio */
122static unsigned int dw, dh;
123
124/* Global point encoding */
125static uint32_t points[4096]; /* FIXME: allocate this dynamically */
126static int npoints = 0;
127
128/* Global triangulation */
129static Delaunay_triangulation dt;
130
131/*
132 * Unicode stuff handling
133 */
134
135/* Return the number of chars in the unichars table */
136static int count_unichars(void)
137{
138    int ret = 0;
139
140    for(int u = 0; unichars[u] != unichars[u + 1]; u += 2)
141        ret += unichars[u + 1] - unichars[u];
142
143    return ret;
144}
145
146/* Get the ith Unicode character in our list */
147static uint32_t index2uni(uint32_t i)
148{
149    for(int u = 0; unichars[u] != unichars[u + 1]; u += 2)
150        if(i < unichars[u + 1] - unichars[u])
151            return unichars[u] + i;
152        else
153            i -= unichars[u + 1] - unichars[u];
154
155    return 0; /* Should not happen! */
156}
157
158/* Convert a Unicode character to its position in the compact list */
159static uint32_t uni2index(uint32_t x)
160{
161    uint32_t ret = 0;
162
163    for(int u = 0; unichars[u] != unichars[u + 1]; u += 2)
164        if(x < unichars[u + 1])
165            return ret + x - unichars[u];
166        else
167            ret += unichars[u + 1] - unichars[u];
168
169    return ret; /* Should not happen! */
170}
171
172static uint8_t const utf8_trailing[256] =
173{
174    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
175    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
176    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
177    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
178    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
179    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
180    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
181    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 3,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5
182};
183
184static uint32_t const utf8_offsets[6] =
185{
186    0x00000000UL, 0x00003080UL, 0x000E2080UL,
187    0x03C82080UL, 0xFA082080UL, 0x82082080UL
188};
189
190static uint32_t fread_utf8(FILE *f)
191{
192    int ch, i = 0, todo = -1;
193    uint32_t ret = 0;
194
195    for(;;)
196    {
197        ch = fgetc(f);
198        if(!ch)
199            return 0;
200        if(todo == -1)
201            todo = utf8_trailing[ch];
202        ret += ((uint32_t)ch) << (6 * (todo - i));
203        if(todo == i++)
204            return ret - utf8_offsets[todo];
205    }
206}
207
208static void fwrite_utf8(FILE *f, uint32_t x)
209{
210    static const uint8_t mark[7] =
211    {
212        0x00, 0x00, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC
213    };
214
215    char buf[8];
216    char *parser = buf;
217    size_t bytes;
218
219    if(x < 0x80)
220    {
221        fprintf(f, "%c", x);
222        return;
223    }
224
225    bytes = (x < 0x800) ? 2 : (x < 0x10000) ? 3 : 4;
226    parser += bytes;
227    *parser = '\0';
228
229    switch(bytes)
230    {
231        case 4: *--parser = (x | 0x80) & 0xbf; x >>= 6;
232        case 3: *--parser = (x | 0x80) & 0xbf; x >>= 6;
233        case 2: *--parser = (x | 0x80) & 0xbf; x >>= 6;
234    }
235    *--parser = x | mark[bytes];
236
237    fprintf(f, "%s", buf);
238}
239
240/*
241 * Our nifty non-power-of-two bitstack handling
242 */
243
244class bitstack
245{
246public:
247    bitstack(int max) { alloc(max); init(0); }
248
249    ~bitstack() { delete[] digits; delete[] str; }
250
251    char const *tostring()
252    {
253        int pos = sprintf(str, "0x%x", digits[msb]);
254
255        for(int i = msb - 1; i >= 0; i--)
256            pos += sprintf(str + pos, "%08x", digits[i]);
257
258        return str;
259    }
260
261    void push(uint32_t val, uint32_t range)
262    {
263        if(!range)
264            return;
265
266        mul(range);
267        add(val % range);
268    }
269
270    uint32_t pop(uint32_t range)
271    {
272        if(!range)
273            return 0;
274
275        return div(range);
276    }
277
278    bool isempty()
279    {
280        for(int i = msb; i >= 0; i--)
281            if(digits[i])
282                return false;
283
284        return true;
285    }
286
287private:
288    bitstack(int max, uint32_t x) { alloc(max); init(x); }
289
290    bitstack(bitstack &b)
291    {
292        alloc(b.max_size);
293        msb = b.msb;
294        memcpy(digits, b.digits, (max_size + 1) * sizeof(uint32_t));
295    }
296
297    bitstack(bitstack const &b)
298    {
299        alloc(b.max_size);
300        msb = b.msb;
301        memcpy(digits, b.digits, (max_size + 1) * sizeof(uint32_t));
302    }
303
304    void alloc(int max)
305    {
306        max_size = max;
307        digits = new uint32_t[max_size + 1];
308        str = new char[(max_size + 1) * 8 + 1];
309    }
310
311    void init(uint32_t i)
312    {
313        msb = 0;
314        memset(digits, 0, (max_size + 1) * sizeof(uint32_t));
315        digits[0] = i;
316    }
317
318    /* Could be done much faster, but we don't care! */
319    void add(uint32_t x) { add(bitstack(max_size, x)); }
320    void sub(uint32_t x) { sub(bitstack(max_size, x)); }
321
322    void add(bitstack const &_b)
323    {
324        /* Copy the operand in case we get added to ourselves */
325        bitstack b(_b);
326        uint64_t x = 0;
327
328        if(msb < b.msb)
329            msb = b.msb;
330
331        for(int i = 0; i <= msb; i++)
332        {
333            uint64_t tmp = (uint64_t)digits[i] + (uint64_t)b.digits[i] + x;
334            digits[i] = tmp;
335            if((uint64_t)digits[i] == tmp)
336                x = 0;
337            else
338            {
339                x = 1;
340                if(i == msb)
341                    msb++;
342            }
343        }
344    }
345
346    void sub(bitstack const &_b)
347    {
348        /* Copy the operand in case we get substracted from ourselves */
349        bitstack b(_b);
350        uint64_t x = 0;
351
352        /* We cannot substract a larger number! */
353        if(msb < b.msb)
354        {
355            init(0);
356            return;
357        }
358
359        for(int i = 0; i <= msb; i++)
360        {
361            uint64_t tmp = (uint64_t)digits[i] - (uint64_t)b.digits[i] - x;
362            digits[i] = tmp;
363            if((uint64_t)digits[i] == tmp)
364                x = 0;
365            else
366            {
367                x = 1;
368                if(i == msb)
369                {
370                    /* Error: carry into MSB! */
371                    init(0);
372                    return;
373                }
374            }
375        }
376
377        while(msb > 0 && digits[msb] == 0) msb--;
378    }
379
380    void mul(uint32_t x)
381    {
382        bitstack b(*this);
383        init(0);
384
385        while(x)
386        {
387            if(x & 1)
388                add(b);
389            x /= 2;
390            b.add(b);
391        }
392    }
393
394    uint32_t div(uint32_t x)
395    {
396        bitstack b(*this);
397
398        for(int i = msb; i >= 0; i--)
399        {
400            uint64_t tmp = b.digits[i] + (((uint64_t)b.digits[i + 1]) << 32);
401            uint32_t res = tmp / x;
402            uint32_t rem = tmp % x;
403            digits[i]= res;
404            b.digits[i + 1] = 0;
405            b.digits[i] = rem;
406        }
407
408        while(msb > 0 && digits[msb] == 0) msb--;
409
410        return b.digits[0];
411    }
412
413    int msb, max_size;
414    uint32_t *digits;
415    char *str;
416};
417
418/*
419 * Point handling
420 */
421
422static unsigned int det_rand(unsigned int mod)
423{
424    static unsigned long next = 1;
425    next = next * 1103515245 + 12345;
426    return ((unsigned)(next / 65536) % 32768) % mod;
427}
428
429static inline int range2int(float val, int range)
430{
431    int ret = (int)(val * ((float)range - 0.0001));
432    return ret < 0 ? 0 : ret > range - 1 ? range - 1 : ret;
433}
434
435static inline float int2midrange(int val, int range)
436{
437    return (float)(1 + 2 * val) / (float)(2 * range);
438}
439
440static inline float int2fullrange(int val, int range)
441{
442    return range > 1 ? (float)val / (float)(range - 1) : 0.0;
443}
444
445static inline void set_point(int index, float x, float y, float r,
446                             float g, float b, float s)
447{
448    int dx = (index / POINTS_PER_CELL) % dw;
449    int dy = (index / POINTS_PER_CELL) / dw;
450
451    float fx = (x - dx * RANGE_X) / RANGE_X;
452    float fy = (y - dy * RANGE_Y) / RANGE_Y;
453
454    int is = range2int(s, RANGE_S);
455
456    int ix = range2int(fx, RANGE_X);
457    int iy = range2int(fy, RANGE_Y);
458
459    int ir = range2int(r, RANGE_R);
460    int ig = range2int(g, RANGE_G);
461    int ib = range2int(b, RANGE_B);
462
463    points[index] = is + RANGE_S * (iy + RANGE_Y * (ix + RANGE_X *
464                               (ib + RANGE_B * (ig + (RANGE_R * ir)))));
465}
466
467static inline void get_point(int index, float *x, float *y, float *r,
468                             float *g, float *b, float *s, bool final = false)
469{
470    uint32_t pt = points[index];
471
472    unsigned int dx = (index / POINTS_PER_CELL) % dw;
473    unsigned int dy = (index / POINTS_PER_CELL) / dw;
474
475    *s = int2fullrange(pt % RANGE_S, RANGE_S); pt /= RANGE_S;
476
477    float fy = int2midrange(pt % RANGE_Y, RANGE_Y); pt /= RANGE_Y;
478    float fx = int2midrange(pt % RANGE_X, RANGE_X); pt /= RANGE_X;
479
480    *x = (fx + dx) * RANGE_X /*+ 0.5 * (index & 1)*/;
481    *y = (fy + dy) * RANGE_Y /*+ 0.5 * (index & 1)*/;
482
483    if(final)
484    {
485        *b = int2fullrange(pt % RANGE_R, RANGE_R); pt /= RANGE_R;
486        *g = int2fullrange(pt % RANGE_G, RANGE_G); pt /= RANGE_G;
487        *r = int2fullrange(pt % RANGE_B, RANGE_B); pt /= RANGE_B;
488    }
489    else
490    {
491        *b = int2midrange(pt % RANGE_R, RANGE_R); pt /= RANGE_R;
492        *g = int2midrange(pt % RANGE_G, RANGE_G); pt /= RANGE_G;
493        *r = int2midrange(pt % RANGE_B, RANGE_B); pt /= RANGE_B;
494    }
495}
496
497static inline float clip(float x, int modulo)
498{
499    float mul = (float)modulo + 0.9999;
500    int round = (int)(x * mul);
501    return (float)round / (float)modulo;
502}
503
504static void add_point(float x, float y, float r, float g, float b, float s)
505{
506    set_point(npoints, x, y, r, g, b, s);
507    npoints++;
508}
509
510#if 0
511static void add_random_point()
512{
513    points[npoints] = det_rand(RANGE_SYXRGB);
514    npoints++;
515}
516#endif
517
518#define NB_OPS 20
519
520static uint8_t rand_op(void)
521{
522    uint8_t x = det_rand(NB_OPS);
523
524    /* Randomly ignore statistically less efficient ops */
525    if(x == 0)
526        return rand_op();
527    if(x == 1 && (RANGE_S == 1 || det_rand(2)))
528        return rand_op();
529    if(x <= 5 && det_rand(2))
530        return rand_op();
531    //if((x < 10 || x > 15) && !det_rand(4)) /* Favour colour changes */
532    //    return rand_op();
533
534    return x;
535}
536
537static uint32_t apply_op(uint8_t op, uint32_t val)
538{
539    uint32_t rem, ext;
540
541    switch(op)
542    {
543    case 0: /* Flip strength value */
544    case 1:
545        /* Statistics show that this helps often, but does not reduce
546         * the error significantly. */
547        return val ^ 1;
548    case 2: /* Move up; if impossible, down */
549        rem = val % RANGE_S;
550        ext = (val / RANGE_S) % RANGE_Y;
551        ext = ext > 0 ? ext - 1 : ext + 1;
552        return (val / RANGE_SY * RANGE_Y + ext) * RANGE_S + rem;
553    case 3: /* Move down; if impossible, up */
554        rem = val % RANGE_S;
555        ext = (val / RANGE_S) % RANGE_Y;
556        ext = ext < RANGE_Y - 1 ? ext + 1 : ext - 1;
557        return (val / RANGE_SY * RANGE_Y + ext) * RANGE_S + rem;
558    case 4: /* Move left; if impossible, right */
559        rem = val % RANGE_SY;
560        ext = (val / RANGE_SY) % RANGE_X;
561        ext = ext > 0 ? ext - 1 : ext + 1;
562        return (val / RANGE_SYX * RANGE_X + ext) * RANGE_SY + rem;
563    case 5: /* Move left; if impossible, right */
564        rem = val % RANGE_SY;
565        ext = (val / RANGE_SY) % RANGE_X;
566        ext = ext < RANGE_X - 1 ? ext + 1 : ext - 1;
567        return (val / RANGE_SYX * RANGE_X + ext) * RANGE_SY + rem;
568    case 6: /* Corner 1 */
569        return apply_op(2, apply_op(4, val));
570    case 7: /* Corner 2 */
571        return apply_op(2, apply_op(5, val));
572    case 8: /* Corner 3 */
573        return apply_op(3, apply_op(5, val));
574    case 9: /* Corner 4 */
575        return apply_op(3, apply_op(4, val));
576    case 16: /* Double up */
577        return apply_op(2, apply_op(2, val));
578    case 17: /* Double down */
579        return apply_op(3, apply_op(3, val));
580    case 18: /* Double left */
581        return apply_op(4, apply_op(4, val));
582    case 19: /* Double right */
583        return apply_op(5, apply_op(5, val));
584    case 10: /* R-- (or R++) */
585        rem = val % RANGE_SYX;
586        ext = (val / RANGE_SYX) % RANGE_R;
587        ext = ext > 0 ? ext - 1 : ext + 1;
588        return (val / RANGE_SYXR * RANGE_R + ext) * RANGE_SYX + rem;
589    case 11: /* R++ (or R--) */
590        rem = val % RANGE_SYX;
591        ext = (val / RANGE_SYX) % RANGE_R;
592        ext = ext < RANGE_R - 1 ? ext + 1 : ext - 1;
593        return (val / RANGE_SYXR * RANGE_R + ext) * RANGE_SYX + rem;
594    case 12: /* G-- (or G++) */
595        rem = val % RANGE_SYXR;
596        ext = (val / RANGE_SYXR) % RANGE_G;
597        ext = ext > 0 ? ext - 1 : ext + 1;
598        return (val / RANGE_SYXRG * RANGE_G + ext) * RANGE_SYXR + rem;
599    case 13: /* G++ (or G--) */
600        rem = val % RANGE_SYXR;
601        ext = (val / RANGE_SYXR) % RANGE_G;
602        ext = ext < RANGE_G - 1 ? ext + 1 : ext - 1;
603        return (val / RANGE_SYXRG * RANGE_G + ext) * RANGE_SYXR + rem;
604    case 14: /* B-- (or B++) */
605        rem = val % RANGE_SYXRG;
606        ext = (val / RANGE_SYXRG) % RANGE_B;
607        ext = ext > 0 ? ext - 1 : ext + 1;
608        return ext * RANGE_SYXRG + rem;
609    case 15: /* B++ (or B--) */
610        rem = val % RANGE_SYXRG;
611        ext = (val / RANGE_SYXRG) % RANGE_B;
612        ext = ext < RANGE_B - 1 ? ext + 1 : ext - 1;
613        return ext * RANGE_SYXRG + rem;
614#if 0
615    case 15: /* Brightness-- */
616        return apply_op(9, apply_op(11, apply_op(13, val)));
617    case 16: /* Brightness++ */
618        return apply_op(10, apply_op(12, apply_op(14, val)));
619    case 17: /* RG-- */
620        return apply_op(9, apply_op(11, val));
621    case 18: /* RG++ */
622        return apply_op(10, apply_op(12, val));
623    case 19: /* GB-- */
624        return apply_op(11, apply_op(13, val));
625    case 20: /* GB++ */
626        return apply_op(12, apply_op(14, val));
627    case 21: /* RB-- */
628        return apply_op(9, apply_op(13, val));
629    case 22: /* RB++ */
630        return apply_op(10, apply_op(14, val));
631#endif
632    default:
633        return val;
634    }
635}
636
637static void render(pipi_image_t *dst,
638                   int rx, int ry, int rw, int rh, bool final)
639{
640    int lookup[dw * RANGE_X * 2 * dh * RANGE_Y * 2];
641    pipi_pixels_t *p = pipi_get_pixels(dst, PIPI_PIXELS_RGBA_F32);
642    float *data = (float *)p->pixels;
643    int x, y;
644
645    memset(lookup, 0, sizeof(lookup));
646    dt.clear();
647    for(int i = 0; i < npoints; i++)
648    {
649        float fx, fy, fr, fg, fb, fs;
650        get_point(i, &fx, &fy, &fr, &fg, &fb, &fs);
651        dt.insert(K::Point_2(fx + dw * RANGE_X, fy + dh * RANGE_Y));
652        /* Keep link to point */
653        lookup[(int)(fx * 2) + dw * RANGE_X * 2 * (int)(fy * 2)] = i;
654    }
655
656    /* Add fake points to close the triangulation */
657    dt.insert(K::Point_2(0, 0));
658    dt.insert(K::Point_2(3 * dw * RANGE_X, 0));
659    dt.insert(K::Point_2(0, 3 * dh * RANGE_Y));
660    dt.insert(K::Point_2(3 * dw * RANGE_X, 3 * dh * RANGE_Y));
661
662    for(y = ry; y < ry + rh; y++)
663    {
664        for(x = rx; x < rx + rw; x++)
665        {
666            K::Point_2 m((float)x * dw * RANGE_X / p->w + dw * RANGE_X,
667                         (float)y * dh * RANGE_Y / p->h + dh * RANGE_Y);
668            Point_coordinate_vector coords;
669            CGAL::Triple<
670              std::back_insert_iterator<Point_coordinate_vector>,
671              K::FT, bool> result =
672              CGAL::natural_neighbor_coordinates_2(dt, m,
673                                                   std::back_inserter(coords));
674
675            float r = 0.0f, g = 0.0f, b = 0.0f, norm = 0.000000000000001f;
676
677            Point_coordinate_vector::iterator it;
678            for(it = coords.begin(); it != coords.end(); ++it)
679            {
680                float fx, fy, fr, fg, fb, fs;
681
682                fx = (*it).first.x() - dw * RANGE_X;
683                fy = (*it).first.y() - dh * RANGE_Y;
684
685                if(fx < 0 || fy < 0
686                    || fx > dw * RANGE_X - 1 || fy > dh * RANGE_Y - 1)
687                    continue;
688
689                int index = lookup[(int)(fx * 2)
690                                    + dw * RANGE_X * 2 * (int)(fy * 2)];
691
692                get_point(index, &fx, &fy, &fr, &fg, &fb, &fs, final);
693
694                //float k = pow((*it).second * (1.0 + fs), 1.2);
695                float k = (*it).second * (1.00f + fs);
696                //float k = (*it).second * (0.60f + fs);
697                //float k = pow((*it).second, (1.0f + fs));
698
699                r += k * fr;
700                g += k * fg;
701                b += k * fb;
702                norm += k;
703            }
704
705            data[4 * (x + y * p->w) + 0] = r / norm;
706            data[4 * (x + y * p->w) + 1] = g / norm;
707            data[4 * (x + y * p->w) + 2] = b / norm;
708            data[4 * (x + y * p->w) + 3] = 0.0;
709        }
710    }
711
712    pipi_release_pixels(dst, p);
713}
714
715static void analyse(pipi_image_t *src)
716{
717    pipi_pixels_t *p = pipi_get_pixels(src, PIPI_PIXELS_RGBA_F32);
718    float *data = (float *)p->pixels;
719
720    for(unsigned int dy = 0; dy < dh; dy++)
721        for(unsigned int dx = 0; dx < dw; dx++)
722        {
723            float min = 1.1f, max = -0.1f, mr = 0.0f, mg = 0.0f, mb = 0.0f;
724            float total = 0.0;
725            int xmin = 0, xmax = 0, ymin = 0, ymax = 0;
726            int npixels = 0;
727
728            for(unsigned int iy = RANGE_Y * dy; iy < RANGE_Y * (dy + 1); iy++)
729                for(unsigned int ix = RANGE_X * dx; ix < RANGE_X * (dx + 1); ix++)
730                {
731                    float lum = 0.0f;
732
733                    lum += data[4 * (ix + iy * p->w) + 0];
734                    lum += data[4 * (ix + iy * p->w) + 1];
735                    lum += data[4 * (ix + iy * p->w) + 2];
736                    lum /= 3;
737
738                    mr += data[4 * (ix + iy * p->w) + 0];
739                    mg += data[4 * (ix + iy * p->w) + 1];
740                    mb += data[4 * (ix + iy * p->w) + 2];
741
742                    if(lum < min)
743                    {
744                        min = lum;
745                        xmin = ix;
746                        ymin = iy;
747                    }
748
749                    if(lum > max)
750                    {
751                        max = lum;
752                        xmax = ix;
753                        ymax = iy;
754                    }
755
756                    total += lum;
757                    npixels++;
758                }
759
760            total /= npixels;
761            mr /= npixels;
762            mg /= npixels;
763            mb /= npixels;
764
765            float wmin, wmax;
766
767            if(total < min + (max - min) / 4)
768                wmin = 1.0, wmax = 0.0;
769            else if(total < min + (max - min) / 4 * 3)
770                wmin = 0.0, wmax = 0.0;
771            else
772                wmin = 0.0, wmax = 1.0;
773
774#if 0
775            add_random_point();
776            add_random_point();
777#else
778            /* 0.80 and 0.20 were chosen empirically, it gives a 10% better
779             * initial distance. Definitely worth it. */
780#if POINTS_PER_CELL == 1
781            if(total < min + (max - min) / 2)
782            {
783#endif
784            add_point(xmin, ymin,
785                      data[4 * (xmin + ymin * p->w) + 0] * 0.80 + mr * 0.20,
786                      data[4 * (xmin + ymin * p->w) + 1] * 0.80 + mg * 0.20,
787                      data[4 * (xmin + ymin * p->w) + 2] * 0.80 + mb * 0.20,
788                      wmin);
789#if POINTS_PER_CELL == 1
790            }
791            else
792            {
793#endif
794            add_point(xmax, ymax,
795                      data[4 * (xmax + ymax * p->w) + 0] * 0.80 + mr * 0.20,
796                      data[4 * (xmax + ymax * p->w) + 1] * 0.80 + mg * 0.20,
797                      data[4 * (xmax + ymax * p->w) + 2] * 0.80 + mb * 0.20,
798                      wmax);
799#if POINTS_PER_CELL == 1
800            }
801#endif
802#endif
803        }
804}
805
806#define MOREINFO "Try `%s --help' for more information.\n"
807
808int main(int argc, char *argv[])
809{
810    uint32_t unicode_data[2048];
811    int opstats[2 * NB_OPS];
812    char const *srcname = NULL, *dstname = NULL;
813    pipi_image_t *src, *tmp, *dst;
814    double error = 1.0;
815    int width, height;
816
817    /* Parse command-line options */
818    for(;;)
819    {
820        int option_index = 0;
821        static struct myoption long_options[] =
822        {
823            { "output",      1, NULL, 'o' },
824            { "length",      1, NULL, 'l' },
825            { "charset",     1, NULL, 'c' },
826            { "quality",     1, NULL, 'q' },
827            { "debug",       0, NULL, 'd' },
828            { "help",        0, NULL, 'h' },
829            { NULL,          0, NULL, 0   },
830        };
831        int c = mygetopt(argc, argv, "o:l:c:q:dh", long_options, &option_index);
832
833        if(c == -1)
834            break;
835
836        switch(c)
837        {
838        case 'o':
839            dstname = myoptarg;
840            break;
841        case 'l':
842            MAX_MSG_LEN = atoi(myoptarg);
843            if(MAX_MSG_LEN < 16)
844            {
845                fprintf(stderr, "Warning: rounding minimum message length to 16\n");
846                MAX_MSG_LEN = 16;
847            }
848            break;
849        case 'c':
850            if(!strcmp(myoptarg, "ascii"))
851                unichars = unichars_ascii;
852            else if(!strcmp(myoptarg, "cjk"))
853                unichars = unichars_cjk;
854            else if(!strcmp(myoptarg, "symbols"))
855                unichars = unichars_symbols;
856            else
857            {
858                fprintf(stderr, "Error: invalid char block \"%s\".", myoptarg);
859                fprintf(stderr, "Valid sets are: ascii, cjk, symbols\n");
860                return EXIT_FAILURE;
861            }
862            break;
863        case 'q':
864            ITERATIONS_PER_POINT = 10 * atof(myoptarg);
865            if(ITERATIONS_PER_POINT < 0)
866                ITERATIONS_PER_POINT = 0;
867            else if(ITERATIONS_PER_POINT > 100)
868                ITERATIONS_PER_POINT = 100;
869            break;
870        case 'd':
871            DEBUG_MODE = true;
872            break;
873        case 'h':
874            printf("Usage: img2twit [OPTIONS] SOURCE\n");
875            printf("       img2twit [OPTIONS] -o DESTINATION\n");
876            printf("Encode SOURCE image to stdout or decode stdin to DESTINATION.\n");
877            printf("\n");
878            printf("Mandatory arguments to long options are mandatory for short options too.\n");
879            printf("  -o, --output <filename>   output resulting image to filename\n");
880            printf("  -l, --length <size>       message length in characters (default 140)\n");
881            printf("  -c, --charset <block>     character set to use (ascii, [cjk], symbols)\n");
882            printf("  -q, --quality <rate>      set image quality (0 - 10) (default 5)\n");
883            printf("  -d, --debug               print debug information\n");
884            printf("  -h, --help                display this help and exit\n");
885            printf("\n");
886            printf("Written by Sam Hocevar. Report bugs to <sam@hocevar.net>.\n");
887            return EXIT_SUCCESS;
888        default:
889            fprintf(stderr, "%s: invalid option -- %c\n", argv[0], c);
890            printf(MOREINFO, argv[0]);
891            return EXIT_FAILURE;
892        }
893    }
894
895    if(myoptind == argc && !dstname)
896    {
897        fprintf(stderr, "%s: too few arguments\n", argv[0]);
898        printf(MOREINFO, argv[0]);
899        return EXIT_FAILURE;
900    }
901
902    if((myoptind == argc - 1 && dstname) || myoptind < argc - 1)
903    {
904        fprintf(stderr, "%s: too many arguments\n", argv[0]);
905        printf(MOREINFO, argv[0]);
906        return EXIT_FAILURE;
907    }
908
909    if(myoptind == argc - 1)
910        srcname = argv[myoptind];
911
912    /* Decoding mode: read UTF-8 text from stdin */
913    if(dstname)
914        for(MAX_MSG_LEN = 0; ;)
915        {
916            uint32_t ch = fread_utf8(stdin);
917            if(ch == 0xffffffff || ch == '\n')
918                break;
919            if(ch <= ' ')
920                continue;
921            unicode_data[MAX_MSG_LEN++] = ch;
922
923            if(MAX_MSG_LEN >= 2048)
924            {
925                fprintf(stderr, "Error: message too long.\n");
926                return EXIT_FAILURE;
927            }
928        }
929
930    if(MAX_MSG_LEN == 0)
931    {
932        fprintf(stderr, "Error: empty message.\n");
933        return EXIT_FAILURE;
934    }
935
936    /* Autodetect charset if decoding, otherwise switch to CJK. */
937    if(dstname)
938    {
939        char const *charset;
940
941        if(unicode_data[0] >= 0x0021 && unicode_data[0] < 0x007f)
942        {
943            unichars = unichars_ascii;
944            charset = "ascii";
945        }
946        else if(unicode_data[0] >= 0x4e00 && unicode_data[0] < 0x9fa6)
947        {
948            unichars = unichars_cjk;
949            charset = "cjk";
950        }
951        else if(unicode_data[0] >= 0x25a0 && unicode_data[0] < 0x27bf)
952        {
953            unichars = unichars_symbols;
954            charset = "symbols";
955        }
956        else
957        {
958            fprintf(stderr, "Error: unable to detect charset\n");
959            return EXIT_FAILURE;
960        }
961
962        if(DEBUG_MODE)
963            fprintf(stderr, "Detected charset \"%s\"\n", charset);
964    }
965    else if(!unichars)
966        unichars = unichars_cjk;
967
968    pipi_set_gamma(1.0);
969
970    /* Precompute bit allocation */
971    NUM_CHARACTERS = count_unichars();
972    TOTAL_BITS = MAX_MSG_LEN * logf(NUM_CHARACTERS) / logf(2);
973    HEADER_BITS = logf(MAX_W * MAX_H) / logf(2);
974    DATA_BITS = TOTAL_BITS - HEADER_BITS;
975#if POINTS_PER_CELL == 1
976    CELL_BITS = logf(RANGE_SYXRGB) / logf(2);
977#else
978    // TODO: implement the following shit
979    //float coord_bits = logf((RANGE_Y * RANGE_X) * (RANGE_Y * RANGE_X + 1) / 2);
980    //float other_bits = logf(RANGE_R * RANGE_G * RANGE_B * RANGE_S);
981    //CELL_BITS = (coord_bits + 2 * other_bits) / logf(2);
982    CELL_BITS = 2 * logf(RANGE_SYXRGB) / logf(2);
983#endif
984    TOTAL_CELLS = (int)(DATA_BITS / CELL_BITS);
985    MAX_ITERATIONS = ITERATIONS_PER_POINT * POINTS_PER_CELL * TOTAL_CELLS;
986
987    bitstack b(MAX_MSG_LEN); /* We cannot declare this before, because
988                              * MAX_MSG_LEN wouldn't be defined. */
989
990    if(dstname)
991    {
992        /* Decoding mode: find each character's index in our character
993         * list, and push it to our wonderful custom bitstream. */
994        for(int i = MAX_MSG_LEN; i--; )
995            b.push(uni2index(unicode_data[i]), NUM_CHARACTERS);
996
997        /* Read width and height from bitstream */
998        src = NULL;
999        width = b.pop(MAX_W);
1000        height = b.pop(MAX_H);
1001    }
1002    else
1003    {
1004        /* Argument given: open image for encoding */
1005        src = pipi_load(srcname);
1006
1007        if(!src)
1008        {
1009            fprintf(stderr, "Error loading %s\n", srcname);
1010            return EXIT_FAILURE;
1011        }
1012
1013        width = pipi_get_image_width(src);
1014        height = pipi_get_image_height(src);
1015    }
1016
1017    /* Compute "best" w/h ratio */
1018    dw = 1; dh = TOTAL_CELLS;
1019    for(unsigned int i = 1; i <= TOTAL_CELLS; i++)
1020    {
1021        int j = TOTAL_CELLS / i;
1022
1023        float r = (float)width / (float)height;
1024        float ir = (float)i / (float)j;
1025        float dwr = (float)dw / (float)dh;
1026
1027        if(fabs(logf(r / ir)) < fabs(logf(r / dwr)))
1028        {
1029            dw = i;
1030            dh = TOTAL_CELLS / dw;
1031        }
1032    }
1033    while((dh + 1) * dw <= TOTAL_CELLS) dh++;
1034    while(dh * (dw + 1) <= TOTAL_CELLS) dw++;
1035
1036    /* Print debug information */
1037    if(DEBUG_MODE)
1038    {
1039        fprintf(stderr, "Message size: %i\n", MAX_MSG_LEN);
1040        fprintf(stderr, "Available characters: %i\n", NUM_CHARACTERS);
1041        fprintf(stderr, "Available bits: %f\n", TOTAL_BITS);
1042        fprintf(stderr, "Maximum image resolution: %ix%i\n", MAX_W, MAX_H);
1043        fprintf(stderr, "Image resolution: %ix%i\n", width, height);
1044        fprintf(stderr, "Header bits: %f\n", HEADER_BITS);
1045        fprintf(stderr, "Bits available for data: %f\n", DATA_BITS);
1046        fprintf(stderr, "Cell bits: %f\n", CELL_BITS);
1047        fprintf(stderr, "Available cells: %i\n", TOTAL_CELLS);
1048        fprintf(stderr, "Wasted bits: %f\n",
1049                DATA_BITS - CELL_BITS * TOTAL_CELLS);
1050        fprintf(stderr, "Chosen image ratio: %i:%i (wasting %i point cells)\n",
1051                dw, dh, TOTAL_CELLS - dw * dh);
1052        fprintf(stderr, "Total wasted bits: %f\n",
1053                DATA_BITS - CELL_BITS * dw * dh);
1054    }
1055
1056    if(srcname)
1057    {
1058        /* Resize and filter image to better state */
1059        tmp = pipi_resize(src, dw * RANGE_X, dh * RANGE_Y);
1060        pipi_free(src);
1061        src = pipi_median_ext(tmp, 1, 1);
1062        pipi_free(tmp);
1063
1064        /* Analyse image */
1065        analyse(src);
1066
1067        /* Render what we just computed */
1068        tmp = pipi_new(dw * RANGE_X, dh * RANGE_Y);
1069        render(tmp, 0, 0, dw * RANGE_X, dh * RANGE_Y, false);
1070        error = pipi_measure_rmsd(src, tmp);
1071
1072        if(DEBUG_MODE)
1073            fprintf(stderr, "Initial distance: %2.10g\n", error);
1074
1075        memset(opstats, 0, sizeof(opstats));
1076        for(int iter = 0, stuck = 0, failures = 0, success = 0;
1077            iter < MAX_ITERATIONS /* && stuck < 5 && */;
1078            iter++)
1079        {
1080            if(failures > 500)
1081            {
1082                stuck++;
1083                failures = 0;
1084            }
1085
1086            if(!DEBUG_MODE && !(iter % 16))
1087                fprintf(stderr, "\rEncoding... %i%%",
1088                        iter * 100 / MAX_ITERATIONS);
1089
1090            pipi_image_t *scrap = pipi_copy(tmp);
1091
1092            /* Choose a point at random */
1093            int pt = det_rand(npoints);
1094            uint32_t oldval = points[pt];
1095
1096            /* Compute the affected image zone */
1097            float fx, fy, fr, fg, fb, fs;
1098            get_point(pt, &fx, &fy, &fr, &fg, &fb, &fs);
1099            int zonex = (int)fx / RANGE_X - 1;
1100            int zoney = (int)fy / RANGE_Y - 1;
1101            int zonew = 3;
1102            int zoneh = 3;
1103            if(zonex < 0) { zonex = 0; zonew--; }
1104            if(zoney < 0) { zoney = 0; zoneh--; }
1105            if(zonex + zonew >= (int)dw) { zonew--; }
1106            if(zoney + zoneh >= (int)dh) { zoneh--; }
1107
1108            /* Choose random operations and measure their effect */
1109            uint8_t op1 = rand_op();
1110            //uint8_t op2 = rand_op();
1111
1112            uint32_t candidates[3];
1113            double besterr = error + 1.0;
1114            int bestop = -1;
1115            candidates[0] = apply_op(op1, oldval);
1116            //candidates[1] = apply_op(op2, oldval);
1117            //candidates[2] = apply_op(op1, apply_op(op2, oldval));
1118
1119            for(int i = 0; i < 1; i++)
1120            //for(int i = 0; i < 3; i++)
1121            {
1122                if(oldval == candidates[i])
1123                    continue;
1124
1125                points[pt] = candidates[i];
1126
1127                render(scrap, zonex * RANGE_X, zoney * RANGE_Y,
1128                       zonew * RANGE_X, zoneh * RANGE_Y, false);
1129
1130                double newerr = pipi_measure_rmsd(src, scrap);
1131                if(newerr < besterr)
1132                {
1133                    besterr = newerr;
1134                    bestop = i;
1135                }
1136            }
1137
1138            opstats[op1 * 2]++;
1139            //opstats[op2 * 2]++;
1140
1141            if(besterr < error)
1142            {
1143                points[pt] = candidates[bestop];
1144                /* Redraw image if the last check wasn't the best one */
1145                if(bestop != 0)
1146                    render(scrap, zonex * RANGE_X, zoney * RANGE_Y,
1147                           zonew * RANGE_X, zoneh * RANGE_Y, false);
1148
1149                pipi_free(tmp);
1150                tmp = scrap;
1151
1152                if(DEBUG_MODE)
1153                    fprintf(stderr, "%08i -.%08i %2.010g after op%i(%i)\n",
1154                            iter, (int)((error - besterr) * 100000000), error,
1155                            op1, pt);
1156
1157                error = besterr;
1158                opstats[op1 * 2 + 1]++;
1159                //opstats[op2 * 2 + 1]++;
1160                failures = 0;
1161                success++;
1162
1163                /* Save image! */
1164                //char buf[128];
1165                //sprintf(buf, "twit%08i.bmp", success);
1166                //if((success % 10) == 0)
1167                //    pipi_save(tmp, buf);
1168            }
1169            else
1170            {
1171                pipi_free(scrap);
1172                points[pt] = oldval;
1173                failures++;
1174            }
1175        }
1176
1177        if(DEBUG_MODE)
1178        {
1179            for(int j = 0; j < 2; j++)
1180            {
1181                fprintf(stderr,   "operation: ");
1182                for(int i = NB_OPS / 2 * j; i < NB_OPS / 2 * (j + 1); i++)
1183                    fprintf(stderr, "%4i ", i);
1184                fprintf(stderr, "\nattempts:  ");
1185                for(int i = NB_OPS / 2 * j; i < NB_OPS / 2 * (j + 1); i++)
1186                    fprintf(stderr, "%4i ", opstats[i * 2]);
1187                fprintf(stderr, "\nsuccesses: ");
1188                for(int i = NB_OPS / 2 * j; i < NB_OPS / 2 * (j + 1); i++)
1189                    fprintf(stderr, "%4i ", opstats[i * 2 + 1]);
1190                fprintf(stderr, "\n");
1191            }
1192
1193            fprintf(stderr, "Distance: %2.10g\n", error);
1194        }
1195        else
1196            fprintf(stderr, "\r                    \r");
1197
1198#if 0
1199        dst = pipi_resize(tmp, width, height);
1200        pipi_free(tmp);
1201
1202        /* Save image and bail out */
1203        pipi_save(dst, "lol.bmp");
1204        pipi_free(dst);
1205#endif
1206
1207        /* Push our points to the bitstream */
1208        for(int i = 0; i < npoints; i++)
1209            b.push(points[i], RANGE_SYXRGB);
1210        b.push(height, MAX_H);
1211        b.push(width, MAX_W);
1212
1213        /* Pop Unicode characters from the bitstream and print them */
1214        for(int i = 0; i < MAX_MSG_LEN; i++)
1215            fwrite_utf8(stdout, index2uni(b.pop(NUM_CHARACTERS)));
1216        fprintf(stdout, "\n");
1217    }
1218    else
1219    {
1220        /* Pop points from the bitstream */
1221        for(int i = dw * dh; i--; )
1222        {
1223#if POINTS_PER_CELL == 2
1224            points[i * 2 + 1] = b.pop(RANGE_SYXRGB);
1225            points[i * 2] = b.pop(RANGE_SYXRGB);
1226#else
1227            points[i] = b.pop(RANGE_SYXRGB);
1228#endif
1229        }
1230        npoints = dw * dh * POINTS_PER_CELL;
1231
1232        /* Render these points to a new image */
1233        dst = pipi_new(width, height);
1234        render(dst, 0, 0, width, height, true);
1235
1236        /* Save image and bail out */
1237        pipi_save(dst, dstname);
1238        pipi_free(dst);
1239    }
1240
1241    return EXIT_SUCCESS;
1242}
1243
Note: See TracBrowser for help on using the repository browser.