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

Last change on this file since 445 was 445, checked in by Sam Hocevar, 18 years ago
  • don't duplicate picture in filter functions.
  • removed OLE code; it doesn't work and won't be needed.
  • Property svn:keywords set to Id
File size: 10.9 KB
Line 
1/*
2 * slashdot.c: decode Slashdot captchas
3 * $Id: slashdot.c 445 2005-01-10 11:23:38Z 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 void count_objects(struct image *img);
22static void rotate(struct image *img);
23static void cut_cells(struct image *img);
24static void find_glyphs(struct image *img);
25
26/* Our macros */
27#define FACTOR 1
28#define FONTNAME "font_slashdot.png" // use with FACTOR = 1
29//#define FONTNAME "font.png" // use with FACTOR = 2
30//#define FONTNAME "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;
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 = image_dup(img);
54    filter_detect_lines(tmp1);
55    filter_fill_holes(tmp1);
56
57    /* Detect small objects to guess image orientation */
58    tmp2 = image_dup(tmp1);
59    filter_median(tmp2);
60    filter_equalize(tmp2, 200);
61    count_objects(tmp2);
62
63    /* Invert rotation and find glyphs */
64    rotate(tmp1);
65    filter_median(tmp1);
66    find_glyphs(tmp1);
67
68    /* Clean up our mess */
69    image_free(tmp1);
70    image_free(tmp2);
71
72    /* aaaaaaa means decoding failed */
73    if(!strcmp(result, "aaaaaaa"))
74        result[0] = '\0';
75
76    return result;
77}
78
79/* The following functions are local */
80
81static void count_objects(struct image *img)
82{
83    struct image *tmp;
84    int gotblack = 1;
85    int x, y, i;
86    int r, g, b;
87
88    tmp = image_new(img->width, img->height);
89
90    for(y = 0; y < img->height; y++)
91        for(x = 0; x < img->width; x++)
92        {
93            getpixel(img, x, y, &r, &g, &b);
94            setpixel(tmp, x, y, r, g, b);
95        }
96
97    while(gotblack)
98    {
99        gotblack = 0;
100        for(y = 0; y < tmp->height; y++)
101            for(x = 0; x < tmp->width; x++)
102            {
103                getpixel(tmp, x, y, &r, &g, &b);
104                if(r == 0 && g == 0 && b == 0)
105                {
106                    gotblack = 1;
107                    filter_flood_fill(tmp, x, y, 254 - objects, 0, 0);
108                    objects++;
109                }
110            }
111    }
112
113    //printf("%i objects\n", objects);
114
115    for(i = 0; i < objects; i++)
116    {
117        objlist[i].ymin = tmp->height;
118        objlist[i].ymax = 0;
119
120        for(y = 0; y < tmp->height; y++)
121            for(x = 0; x < tmp->width; x++)
122            {
123                getpixel(tmp, x, y, &r, &g, &b);
124                if(r == 255 - i && g == 0 && b == 0)
125                {
126                    if(y < objlist[i].ymin) { objlist[i].ymin = y; objlist[i].xmin = x; }
127                    if(y > objlist[i].ymax) { objlist[i].ymax = y; objlist[i].xmax = x; }
128                }
129            }
130        //printf("y min-max: %i %i (size %i)\n", objlist[i].ymin, objlist[i].ymax, objlist[i].ymax - objlist[i].ymin + 1);
131        if(objlist[i].ymax - objlist[i].ymin > 18 && objlist[i].ymax - objlist[i].ymin < 27)
132        {
133            if(first == -1)
134                first = i;
135            last = i;
136            filter_flood_fill(tmp, objlist[i].xmin, objlist[i].ymin, 0, 0, 255);
137        }
138    }
139
140#if 0
141    { CvPoint A, B;
142      A.x = (objlist[first].xmin + objlist[first].xmax) / 2;
143      A.y = (objlist[first].ymin + objlist[first].ymax) / 2;
144      B.x = (objlist[last].xmin + objlist[last].xmax) / 2;
145      B.y = (objlist[last].ymin + objlist[last].ymax) / 2;
146      cvLine(tmp, A, B, 0, 2.0, 0);
147    }
148#endif
149
150    image_swap(img, tmp);
151    image_free(tmp);
152}
153
154static void rotate(struct image *img)
155{
156    struct image *tmp;
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    tmp = 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(tmp, x, y, r, g, b);
193        }
194
195    image_swap(img, tmp);
196    image_free(tmp);
197}
198
199static void cut_cells(struct image *img)
200{
201    struct image *tmp;
202    int x, y;
203    int r, g, b;
204
205    tmp = image_new(img->width, img->height);
206
207    for(y = 0; y < img->height; y++)
208        for(x = 0; x < img->width; x++)
209        {
210            getpixel(img, x, y, &r, &g, &b);
211            setpixel(tmp, x, y, r, g, b);
212        }
213
214    for(x = 0; x < img->width; x++)
215    {
216        setpixel(tmp, x, 0, 255, 255, 255);
217        setpixel(tmp, x, img->height - 1, 255, 255, 255);
218    }
219
220    for(y = 0; y < img->height; y++)
221        for(x = 0; x < 7; x++)
222        {
223            setpixel(tmp, x * img->width / 7, y, 255, 255, 255);
224            setpixel(tmp, (x + 1) * img->width / 7 - 1, y, 255, 255, 255);
225        }
226
227    image_swap(img, tmp);
228    image_free(tmp);
229}
230
231static void 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 *tmp;
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        char fontname[BUFSIZ];
249        sprintf(fontname, "%s/%s", share, FONTNAME);
250        font = image_load(fontname);
251        if(!font)
252        {
253            fprintf(stderr, "cannot load font %s\n", fontname);
254            exit(-1);
255        }
256    }
257
258    tmp = image_new(img->width, img->height);
259
260    for(y = 0; y < img->height; y++)
261        for(x = 0; x < img->width; x++)
262        {
263            getpixel(img, x, y, &r, &g, &b);
264            setpixel(tmp, x, y, 255, g, 255);
265        }
266
267    for(x = 0; x < font->width; x++)
268    {
269        int found = 0;
270        for(y = 0; y < font->height; y++)
271        {
272            getpixel(font, x, y, &r, &g, &b);
273            if(r < 128)
274            {
275                found = 1;
276                count += (255 - r);
277            }
278        }
279        if(found && !incell)
280        {
281            incell = 1;
282            xmin = x;
283        }
284        else if(!found && incell)
285        {
286            incell = 0;
287            xmax = x;
288#if 0
289            ymin = font->height;
290            ymax = 0;
291            for(y = 0; y < font->height; y++)
292            {
293                int newx;
294                int gotit = 0;
295                for(newx = xmin; newx < xmax; newx++)
296                {
297                    getpixel(font, newx, y, &r, &g, &b);
298                    if(r < 128)
299                    {
300                        gotit = 1;
301                        break;
302                    }
303                }
304                if(gotit)
305                {
306                    if(ymin > y) ymin = y;
307                    if(ymax <= y) ymax = y + 1;
308                }
309            }
310#else
311            ymin = 0;
312            ymax = font->height;
313#endif
314            glyphs[i].xmin = xmin;
315            glyphs[i].xmax = xmax;
316            glyphs[i].ymin = ymin;
317            glyphs[i].ymax = ymax;
318            glyphs[i].count = count;
319            count = 0;
320            i++;
321        }
322    }
323
324    if(i != 22)
325    {
326        printf("error: could not find 22 glyphs in font\n");
327        exit(-1);
328    }
329
330    while(cur < 7)
331    {
332        /* Try to find 1st letter */
333        distmin = INT_MAX;
334        for(i = 0; i < 22; i++)
335        {
336            int localmin = INT_MAX, localx, localy;
337//if(all[i] == 'i') continue;
338            xmin = glyphs[i].xmin;
339            ymin = glyphs[i].ymin;
340            xmax = glyphs[i].xmax;
341            ymax = glyphs[i].ymax;
342            //printf("trying to find %c (%i×%i) - ", all[i], xmax - xmin, ymax - ymin);
343            for(y = -5 * FACTOR; y < 5 * FACTOR; y++)
344                for(x = startx - 5 * FACTOR; x < startx + 5 * FACTOR; x++)
345                {
346                    int z, t, dist;
347                    dist = 0;
348                    for(t = 0; t < ymax - ymin; t++)
349                        for(z = 0; z < xmax - xmin; z++)
350                        {
351                            int r2;
352                            getgray(font, xmin + z, ymin + t, &r);
353                            getgray(img, x + z, y + t, &r2);
354                            dist += abs(r - r2);
355                        }
356    //                printf("%i %i -> %i\n", x, y, dist);
357                    //dist /= sqrt(xmax - xmin);
358                    dist = dist * 128 / glyphs[i].count;
359                    if(dist < localmin)
360                    {
361                        localmin = dist;
362                        localx = x;
363                        localy = y;
364                    }
365                }
366            //fprintf(stderr, "%i (%i,%i)\n", localmin, localx - startx, localy);
367            if(localmin < distmin)
368            {
369                distmin = localmin;
370                distx = localx;
371                disty = localy;
372                distch = i;
373            }
374        }
375
376        //fprintf(stderr, "%i (%i,%i)\n", distmin, distx - startx, disty);
377        //printf("min diff: %c - %i (%i, %i)\n", all[distch], distmin, distx, disty);
378
379        /* Print min glyph */
380        xmin = glyphs[distch].xmin;
381        ymin = glyphs[distch].ymin;
382        xmax = glyphs[distch].xmax;
383        ymax = glyphs[distch].ymax;
384        for(y = 0; y < ymax - ymin; y++)
385            for(x = 0; x < xmax - xmin; x++)
386            {
387                getpixel(font, xmin + x, ymin + y, &r, &g, &b);
388                if(r > 128) continue;
389                setpixel(tmp, distx + x, disty + y, r, g, b);
390            }
391
392        startx = distx + xmax - xmin;
393        result[cur++] = all[distch];
394    }
395
396    image_swap(img, tmp);
397    image_free(tmp);
398}
399
Note: See TracBrowser for help on using the repository browser.