source: pwntcha/trunk/src/slashdot.c @ 421

Last change on this file since 421 was 421, checked in by Sam Hocevar, 16 years ago
  • keep the font loaded across decodings.
  • Property svn:keywords set to Id
File size: 11.0 KB
Line 
1/*
2 * slashdot.c: decode Slashdot captchas
3 * $Id: slashdot.c 421 2005-01-05 00:18:49Z sam $
4 *
5 * Copyright: (c) 2004 Sam Hocevar <sam@zoy.org>
6 *   This program is free software; you can redistribute it and/or
7 *   modify it under the terms of the Do What The Fuck You Want To
8 *   Public License as published by Banlu Kemiyatorn. See
9 *   http://sam.zoy.org/projects/COPYING.WTFPL for more details.
10 */
11
12#include <stdio.h>
13#include <stdlib.h>
14#include <string.h>
15#include <limits.h>
16#include <math.h>
17
18#include "config.h"
19#include "common.h"
20
21static struct image *count_objects(struct image *img);
22static struct image *rotate(struct image *img);
23static struct image *cut_cells(struct image *img);
24static struct image *find_glyphs(struct image *img);
25
26/* Our macros */
27#define FACTOR 1
28#define FONTNAME "share/font_slashdot.png" // use with FACTOR = 1
29//#define FONTNAME "share/font.png" // use with FACTOR = 2
30//#define FONTNAME "share/font_dilated.png" // use with FACTOR = 2
31static struct image *font = NULL;
32
33/* Global stuff */
34struct { int xmin, ymin, xmax, ymax; } objlist[100];
35int objects, first, last;
36char *result;
37
38/* Main function */
39char *decode_slashdot(struct image *img)
40{
41    struct image *tmp1, *tmp2, *tmp3, *tmp4, *tmp5, *tmp6, *tmp7;
42
43    /* Initialise local data */
44    objects = 0;
45    first = -1;
46    last = -1;
47
48    /* Slashdot captchas have 7 characters */
49    result = malloc(8 * sizeof(char));
50    strcpy(result, "       ");
51
52    /* Clean image a bit */
53    tmp1 = filter_detect_lines(img);
54    tmp2 = filter_fill_holes(tmp1);
55
56    /* Detect small objects to guess image orientation */
57    tmp3 = filter_median(tmp2);
58    tmp4 = filter_equalize(tmp3, 200);
59    count_objects(tmp4);
60
61    /* Invert rotation and find glyphs */
62    tmp5 = rotate(tmp2);
63    tmp6 = filter_median(tmp5);
64    tmp7 = find_glyphs(tmp6);
65
66    /* Clean up our mess */
67    image_free(tmp1);
68    image_free(tmp2);
69    image_free(tmp3);
70    image_free(tmp4);
71    image_free(tmp5);
72    image_free(tmp6);
73    image_free(tmp7);
74
75    /* aaaaaaa means decoding failed */
76    if(!strcmp(result, "aaaaaaa"))
77        result[0] = '\0';
78
79    return result;
80}
81
82/* The following functions are local */
83
84static struct image *count_objects(struct image *img)
85{
86    struct image *dst;
87    int gotblack = 1;
88    int x, y, i;
89    int r, g, b;
90
91    dst = image_new(img->width, img->height);
92
93    for(y = 0; y < img->height; y++)
94        for(x = 0; x < img->width; x++)
95        {
96            getpixel(img, x, y, &r, &g, &b);
97            setpixel(dst, x, y, r, g, b);
98        }
99
100    while(gotblack)
101    {
102        gotblack = 0;
103        for(y = 0; y < dst->height; y++)
104            for(x = 0; x < dst->width; x++)
105            {
106                getpixel(dst, x, y, &r, &g, &b);
107                if(r == 0 && g == 0 && b == 0)
108                {
109                    gotblack = 1;
110                    filter_flood_fill(dst, x, y, 254 - objects, 0, 0);
111                    objects++;
112                }
113            }
114    }
115
116    //printf("%i objects\n", objects);
117
118    for(i = 0; i < objects; i++)
119    {
120        objlist[i].ymin = dst->height;
121        objlist[i].ymax = 0;
122
123        for(y = 0; y < dst->height; y++)
124            for(x = 0; x < dst->width; x++)
125            {
126                getpixel(dst, x, y, &r, &g, &b);
127                if(r == 255 - i && g == 0 && b == 0)
128                {
129                    if(y < objlist[i].ymin) { objlist[i].ymin = y; objlist[i].xmin = x; }
130                    if(y > objlist[i].ymax) { objlist[i].ymax = y; objlist[i].xmax = x; }
131                }
132            }
133        //printf("y min-max: %i %i (size %i)\n", objlist[i].ymin, objlist[i].ymax, objlist[i].ymax - objlist[i].ymin + 1);
134        if(objlist[i].ymax - objlist[i].ymin > 18 && objlist[i].ymax - objlist[i].ymin < 27)
135        {
136            if(first == -1)
137                first = i;
138            last = i;
139            filter_flood_fill(dst, objlist[i].xmin, objlist[i].ymin, 0, 0, 255);
140        }
141    }
142
143#if 0
144    { CvPoint A, B;
145      A.x = (objlist[first].xmin + objlist[first].xmax) / 2;
146      A.y = (objlist[first].ymin + objlist[first].ymax) / 2;
147      B.x = (objlist[last].xmin + objlist[last].xmax) / 2;
148      B.y = (objlist[last].ymin + objlist[last].ymax) / 2;
149      cvLine(dst, A, B, 0, 2.0, 0);
150    }
151#endif
152
153    return dst;
154}
155
156static struct image *rotate(struct image *img)
157{
158    struct image *dst;
159    int x, y, xdest, ydest;
160    int r, g, b;
161    //int R, G, B;
162    int X = objlist[first].xmin - objlist[last].xmin;
163    int Y = objlist[first].ymin - objlist[last].ymin;
164    float xtmp, ytmp;
165    float sina = (1.0 * Y) / sqrt(1.0 * X * X + Y * Y);
166    float cosa = (1.0 * X) / sqrt(1.0 * X * X + Y * Y);
167    if(sina * cosa > 0)
168    {
169        sina = -sina;
170        cosa = -cosa;
171    }
172
173    dst = image_new(img->width * FACTOR, img->height * FACTOR);
174
175    for(y = 0; y < img->height * FACTOR; y++)
176        for(x = 0; x < img->width * FACTOR; x++)
177        {
178            xtmp = 1.0 * (x - img->width * FACTOR / 2) / FACTOR;
179            ytmp = 1.0 * (y - img->height * FACTOR / 2) / FACTOR;
180            xdest = xtmp * cosa - ytmp * sina + 0.5 * img->width;
181            ydest = ytmp * cosa + xtmp * sina + 0.5 * img->height;
182            //R = G = B = 0;
183            getpixel(img, xdest, ydest, &r, &g, &b);
184            //R += r; G += g; B += b;
185            //getpixel(img, xdest+1, ydest, &r, &g, &b);
186            //R += r; G += g; B += b;
187            //getpixel(img, xdest, ydest+1, &r, &g, &b);
188            //R += r; G += g; B += b;
189            //getpixel(img, xdest+1, ydest+1, &r, &g, &b);
190            //R += r; G += g; B += b;
191            //r = R / 4; g = G / 4; b = B / 4;
192            if(r == 255 && g == 0 && b == 255)
193                g = 255;
194            setpixel(dst, x, y, r, g, b);
195        }
196
197    return dst;
198}
199
200static struct image *cut_cells(struct image *img)
201{
202    struct image *dst;
203    int x, y;
204    int r, g, b;
205
206    dst = image_new(img->width, img->height);
207
208    for(y = 0; y < img->height; y++)
209        for(x = 0; x < img->width; x++)
210        {
211            getpixel(img, x, y, &r, &g, &b);
212            setpixel(dst, x, y, r, g, b);
213        }
214
215    for(x = 0; x < img->width; x++)
216    {
217        setpixel(dst, x, 0, 255, 255, 255);
218        setpixel(dst, x, img->height - 1, 255, 255, 255);
219    }
220
221    for(y = 0; y < img->height; y++)
222        for(x = 0; x < 7; x++)
223        {
224            setpixel(dst, x * img->width / 7, y, 255, 255, 255);
225            setpixel(dst, (x + 1) * img->width / 7 - 1, y, 255, 255, 255);
226        }
227
228    return dst;
229}
230
231static struct image *find_glyphs(struct image *img)
232{
233    char all[] = "abcdefgijkmnpqrstvwxyz";
234    struct
235    {
236        int xmin, xmax, ymin, ymax;
237        int count;
238    }
239    glyphs[22];
240    struct image *dst;
241    int x, y, i = 0;
242    int r, g, b;
243    int xmin, xmax, ymin, ymax, incell = 0, count = 0, startx = 0, cur = 0;
244    int distmin, distx, disty, distch;
245
246    if(!font)
247    {
248        font = image_load(FONTNAME);
249        if(!font)
250        {
251            fprintf(stderr, "cannot load font %s\n", FONTNAME);
252            exit(-1);
253        }
254    }
255
256    dst = image_new(img->width, img->height);
257
258    for(y = 0; y < img->height; y++)
259        for(x = 0; x < img->width; x++)
260        {
261            getpixel(img, x, y, &r, &g, &b);
262            setpixel(dst, x, y, 255, g, 255);
263        }
264
265    for(x = 0; x < font->width; x++)
266    {
267        int found = 0;
268        for(y = 0; y < font->height; y++)
269        {
270            getpixel(font, x, y, &r, &g, &b);
271            if(r < 128)
272            {
273                found = 1;
274                count += (255 - r);
275            }
276        }
277        if(found && !incell)
278        {
279            incell = 1;
280            xmin = x;
281        }
282        else if(!found && incell)
283        {
284            incell = 0;
285            xmax = x;
286#if 0
287            ymin = font->height;
288            ymax = 0;
289            for(y = 0; y < font->height; y++)
290            {
291                int newx;
292                int gotit = 0;
293                for(newx = xmin; newx < xmax; newx++)
294                {
295                    getpixel(font, newx, y, &r, &g, &b);
296                    if(r < 128)
297                    {
298                        gotit = 1;
299                        break;
300                    }
301                }
302                if(gotit)
303                {
304                    if(ymin > y) ymin = y;
305                    if(ymax <= y) ymax = y + 1;
306                }
307            }
308#else
309            ymin = 0;
310            ymax = font->height;
311#endif
312            glyphs[i].xmin = xmin;
313            glyphs[i].xmax = xmax;
314            glyphs[i].ymin = ymin;
315            glyphs[i].ymax = ymax;
316            glyphs[i].count = count;
317            count = 0;
318            i++;
319        }
320    }
321
322    if(i != 22)
323    {
324        printf("error: could not find 22 glyphs in font\n");
325        exit(-1);
326    }
327
328    while(cur < 7)
329    {
330        /* Try to find 1st letter */
331        distmin = INT_MAX;
332        for(i = 0; i < 22; i++)
333        {
334            int localmin = INT_MAX, localx, localy;
335//if(all[i] == 'i') continue;
336            xmin = glyphs[i].xmin;
337            ymin = glyphs[i].ymin;
338            xmax = glyphs[i].xmax;
339            ymax = glyphs[i].ymax;
340            //printf("trying to find %c (%i×%i) - ", all[i], xmax - xmin, ymax - ymin);
341            for(y = -5 * FACTOR; y < 5 * FACTOR; y++)
342                for(x = startx - 5 * FACTOR; x < startx + 5 * FACTOR; x++)
343                {
344                    int z, t, dist;
345                    dist = 0;
346                    for(t = 0; t < ymax - ymin; t++)
347                        for(z = 0; z < xmax - xmin; z++)
348                        {
349                            int r2;
350                            getgray(font, xmin + z, ymin + t, &r);
351                            getgray(img, x + z, y + t, &r2);
352                            dist += abs(r - r2);
353                        }
354    //                printf("%i %i -> %i\n", x, y, dist);
355                    //dist /= sqrt(xmax - xmin);
356                    dist = dist * 128 / glyphs[i].count;
357                    if(dist < localmin)
358                    {
359                        localmin = dist;
360                        localx = x;
361                        localy = y;
362                    }
363                }
364            //fprintf(stderr, "%i (%i,%i)\n", localmin, localx - startx, localy);
365            if(localmin < distmin)
366            {
367                distmin = localmin;
368                distx = localx;
369                disty = localy;
370                distch = i;
371            }
372        }
373
374        //fprintf(stderr, "%i (%i,%i)\n", distmin, distx - startx, disty);
375        //printf("min diff: %c - %i (%i, %i)\n", all[distch], distmin, distx, disty);
376
377        /* Print min glyph */
378        xmin = glyphs[distch].xmin;
379        ymin = glyphs[distch].ymin;
380        xmax = glyphs[distch].xmax;
381        ymax = glyphs[distch].ymax;
382        for(y = 0; y < ymax - ymin; y++)
383            for(x = 0; x < xmax - xmin; x++)
384            {
385                getpixel(font, xmin + x, ymin + y, &r, &g, &b);
386                if(r > 128) continue;
387                setpixel(dst, distx + x, disty + y, r, g, b);
388            }
389
390        startx = distx + xmax - xmin;
391        result[cur++] = all[distch];
392    }
393
394    return dst;
395}
396
Note: See TracBrowser for help on using the repository browser.