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

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