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

Last change on this file since 2318 was 2318, checked in by Sam Hocevar, 12 years ago
  • Step 2 of the code reorganisation: move each font to its corresponding decoder's subdirectory.
  • Property svn:keywords set to Id
File size: 7.7 KB
Line 
1/*
2 * slashdot.c: decode Slashdot captchas
3 * $Id: decoder.c 2318 2008-04-26 08:41:43Z 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(DECODER, "font.png",
194                                  "abcdefgijkmnpqrstvwxyz");
195        if(!font)
196            exit(1);
197    }
198
199    tmp = image_new(img->width, img->height);
200
201    for(y = 0; y < img->height; y++)
202        for(x = 0; x < img->width; x++)
203        {
204            getpixel(img, x, y, &r, &g, &b);
205            setpixel(tmp, x, y, 255, g, 255);
206        }
207
208    while(cur < 7)
209    {
210        /* Try to find 1st letter */
211        distmin = INT_MAX;
212        for(i = 0; i < font->size; i++)
213        {
214            int localmin = INT_MAX, localx, localy;
215            xmin = font->glyphs[i].xmin;
216            ymin = font->glyphs[i].ymin;
217            xmax = font->glyphs[i].xmax;
218            ymax = font->glyphs[i].ymax;
219            for(y = -5; y < 5; y++)
220                for(x = startx - 5; x < startx + 5; x++)
221                {
222                    int z, t, dist;
223                    dist = 0;
224                    for(t = 0; t < ymax - ymin; t++)
225                        for(z = 0; z < xmax - xmin; z++)
226                        {
227                            int r2;
228                            getgray(font->img, xmin + z, ymin + t, &r);
229                            getgray(img, x + z, y + t, &r2);
230                            dist += abs(r - r2);
231                        }
232    //                printf("%i %i -> %i\n", x, y, dist);
233                    //dist /= sqrt(xmax - xmin);
234                    dist = dist * 128 / font->glyphs[i].count;
235                    if(dist < localmin)
236                    {
237                        localmin = dist;
238                        localx = x;
239                        localy = y;
240                    }
241                }
242            //fprintf(stderr, "%i (%i,%i)\n", localmin, localx - startx, localy);
243            if(localmin < distmin)
244            {
245                distmin = localmin;
246                distx = localx;
247                disty = localy;
248                distch = i;
249            }
250        }
251
252        /* Draw best glyph in picture (debugging purposes) */
253        xmin = font->glyphs[distch].xmin;
254        ymin = font->glyphs[distch].ymin;
255        xmax = font->glyphs[distch].xmax;
256        ymax = font->glyphs[distch].ymax;
257        for(y = 0; y < ymax - ymin; y++)
258            for(x = 0; x < xmax - xmin; x++)
259            {
260                getpixel(font->img, xmin + x, ymin + y, &r, &g, &b);
261                if(r > 128) continue;
262                setpixel(tmp, distx + x, disty + y, r, g, b);
263            }
264
265        startx = distx + xmax - xmin;
266        result[cur++] = font->glyphs[distch].c;
267    }
268
269    image_swap(img, tmp);
270    image_free(tmp);
271}
272
Note: See TracBrowser for help on using the repository browser.