source: pwntcha/trunk/src/slashdot/decoder.c @ 2317

Last change on this file since 2317 was 2317, checked in by Sam Hocevar, 12 years ago
  • Preparing a huge PWNtcha reorganisation. First step: put each decoder in its own subdirectory.
  • Property svn:keywords set to Id
File size: 7.7 KB
Line 
1/*
2 * slashdot.c: decode Slashdot captchas
3 * $Id: decoder.c 2317 2008-04-26 08:41:35Z sam $
4 *
5 * Copyright: (c) 2004 Sam Hocevar <sam@zoy.org>
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 <stdio.h>
14#include <stdlib.h>
15#include <string.h>
16#include <limits.h>
17#include <math.h>
18
19#include "config.h"
20#include "common.h"
21
22static void count_objects(struct image *img);
23static void rotate(struct image *img);
24static void find_glyphs(struct image *img);
25
26/* Global stuff */
27struct { int xmin, ymin, xmax, ymax; } objlist[100];
28int objects, first, last;
29char *result;
30
31/* Main function */
32char *decode_slashdot(struct image *img)
33{
34    struct image *tmp1, *tmp2;
35
36    /* Initialise local data */
37    objects = 0;
38    first = -1;
39    last = -1;
40
41    /* Slashdot captchas have 7 characters */
42    result = malloc(8 * sizeof(char));
43    strcpy(result, "       ");
44
45    /* Clean image a bit */
46    tmp1 = image_dup(img);
47    filter_detect_lines(tmp1);
48    filter_fill_holes(tmp1);
49
50    /* Detect small objects to guess image orientation */
51    tmp2 = image_dup(tmp1);
52    filter_median(tmp2);
53    filter_threshold(tmp2, 200);
54    count_objects(tmp2);
55
56    /* Invert rotation and find glyphs */
57    rotate(tmp1);
58    filter_median(tmp1);
59    find_glyphs(tmp1);
60
61    /* Clean up our mess */
62    image_free(tmp1);
63    image_free(tmp2);
64
65    /* aaaaaaa means decoding failed */
66    if(!strcmp(result, "aaaaaaa"))
67        result[0] = '\0';
68
69    return result;
70}
71
72/* The following functions are local */
73
74static void count_objects(struct image *img)
75{
76    struct image *tmp;
77    int gotblack = 1;
78    int x, y, i;
79    int r, g, b;
80
81    tmp = image_new(img->width, img->height);
82
83    for(y = 0; y < img->height; y++)
84        for(x = 0; x < img->width; x++)
85        {
86            getpixel(img, x, y, &r, &g, &b);
87            setpixel(tmp, x, y, r, g, b);
88        }
89
90    while(gotblack)
91    {
92        gotblack = 0;
93        for(y = 0; y < tmp->height; y++)
94            for(x = 0; x < tmp->width; x++)
95            {
96                getpixel(tmp, x, y, &r, &g, &b);
97                if(r == 0 && g == 0 && b == 0)
98                {
99                    gotblack = 1;
100                    filter_flood_fill(tmp, x, y, 254 - objects, 0, 0);
101                    objects++;
102                }
103            }
104    }
105
106    //printf("%i objects\n", objects);
107
108    for(i = 0; i < objects; i++)
109    {
110        objlist[i].ymin = tmp->height;
111        objlist[i].ymax = 0;
112
113        for(y = 0; y < tmp->height; y++)
114            for(x = 0; x < tmp->width; x++)
115            {
116                getpixel(tmp, x, y, &r, &g, &b);
117                if(r == 255 - i && g == 0 && b == 0)
118                {
119                    if(y < objlist[i].ymin) { objlist[i].ymin = y; objlist[i].xmin = x; }
120                    if(y > objlist[i].ymax) { objlist[i].ymax = y; objlist[i].xmax = x; }
121                }
122            }
123        //printf("y min-max: %i %i (size %i)\n", objlist[i].ymin, objlist[i].ymax, objlist[i].ymax - objlist[i].ymin + 1);
124        if(objlist[i].ymax - objlist[i].ymin > 18 && objlist[i].ymax - objlist[i].ymin < 27)
125        {
126            if(first == -1)
127                first = i;
128            last = i;
129            filter_flood_fill(tmp, objlist[i].xmin, objlist[i].ymin, 0, 0, 255);
130        }
131    }
132
133    image_swap(img, tmp);
134    image_free(tmp);
135}
136
137static void rotate(struct image *img)
138{
139    struct image *tmp;
140    int x, y, xdest, ydest;
141    int r, g, b;
142    //int R, G, B;
143    int X = objlist[first].xmin - objlist[last].xmin;
144    int Y = objlist[first].ymin - objlist[last].ymin;
145    float xtmp, ytmp;
146    float sina = (1.0 * Y) / sqrt(1.0 * X * X + Y * Y);
147    float cosa = (1.0 * X) / sqrt(1.0 * X * X + Y * Y);
148    if(sina * cosa > 0)
149    {
150        sina = -sina;
151        cosa = -cosa;
152    }
153
154    tmp = image_new(img->width, img->height);
155
156    for(y = 0; y < img->height; y++)
157        for(x = 0; x < img->width; x++)
158        {
159            xtmp = 1.0 * (x - img->width / 2);
160            ytmp = 1.0 * (y - img->height / 2);
161            xdest = xtmp * cosa - ytmp * sina + 0.5 * img->width;
162            ydest = ytmp * cosa + xtmp * sina + 0.5 * img->height;
163            //R = G = B = 0;
164            getpixel(img, xdest, ydest, &r, &g, &b);
165            //R += r; G += g; B += b;
166            //getpixel(img, xdest+1, ydest, &r, &g, &b);
167            //R += r; G += g; B += b;
168            //getpixel(img, xdest, ydest+1, &r, &g, &b);
169            //R += r; G += g; B += b;
170            //getpixel(img, xdest+1, ydest+1, &r, &g, &b);
171            //R += r; G += g; B += b;
172            //r = R / 4; g = G / 4; b = B / 4;
173            if(r == 255 && g == 0 && b == 255)
174                g = 255;
175            setpixel(tmp, x, y, r, g, b);
176        }
177
178    image_swap(img, tmp);
179    image_free(tmp);
180}
181
182static void find_glyphs(struct image *img)
183{
184    static struct font *font = NULL;
185    struct image *tmp;
186    int x, y, i = 0;
187    int r, g, b;
188    int xmin, xmax, ymin, ymax, startx = 0, cur = 0;
189    int distmin, distx, disty, distch;
190
191    if(!font)
192    {
193        font = font_load_variable("font_slashdot.png", "abcdefgijkmnpqrstvwxyz");
194        if(!font)
195            exit(1);
196    }
197
198    tmp = image_new(img->width, img->height);
199
200    for(y = 0; y < img->height; y++)
201        for(x = 0; x < img->width; x++)
202        {
203            getpixel(img, x, y, &r, &g, &b);
204            setpixel(tmp, x, y, 255, g, 255);
205        }
206
207    while(cur < 7)
208    {
209        /* Try to find 1st letter */
210        distmin = INT_MAX;
211        for(i = 0; i < font->size; i++)
212        {
213            int localmin = INT_MAX, localx, localy;
214            xmin = font->glyphs[i].xmin;
215            ymin = font->glyphs[i].ymin;
216            xmax = font->glyphs[i].xmax;
217            ymax = font->glyphs[i].ymax;
218            for(y = -5; y < 5; y++)
219                for(x = startx - 5; x < startx + 5; x++)
220                {
221                    int z, t, dist;
222                    dist = 0;
223                    for(t = 0; t < ymax - ymin; t++)
224                        for(z = 0; z < xmax - xmin; z++)
225                        {
226                            int r2;
227                            getgray(font->img, xmin + z, ymin + t, &r);
228                            getgray(img, x + z, y + t, &r2);
229                            dist += abs(r - r2);
230                        }
231    //                printf("%i %i -> %i\n", x, y, dist);
232                    //dist /= sqrt(xmax - xmin);
233                    dist = dist * 128 / font->glyphs[i].count;
234                    if(dist < localmin)
235                    {
236                        localmin = dist;
237                        localx = x;
238                        localy = y;
239                    }
240                }
241            //fprintf(stderr, "%i (%i,%i)\n", localmin, localx - startx, localy);
242            if(localmin < distmin)
243            {
244                distmin = localmin;
245                distx = localx;
246                disty = localy;
247                distch = i;
248            }
249        }
250
251        /* Draw best glyph in picture (debugging purposes) */
252        xmin = font->glyphs[distch].xmin;
253        ymin = font->glyphs[distch].ymin;
254        xmax = font->glyphs[distch].xmax;
255        ymax = font->glyphs[distch].ymax;
256        for(y = 0; y < ymax - ymin; y++)
257            for(x = 0; x < xmax - xmin; x++)
258            {
259                getpixel(font->img, xmin + x, ymin + y, &r, &g, &b);
260                if(r > 128) continue;
261                setpixel(tmp, distx + x, disty + y, r, g, b);
262            }
263
264        startx = distx + xmax - xmin;
265        result[cur++] = font->glyphs[distch].c;
266    }
267
268    image_swap(img, tmp);
269    image_free(tmp);
270}
271
Note: See TracBrowser for help on using the repository browser.