bhcli-simple

A simplified version of bhcli
git clone https://git.dasho.dev/bhcli-simple.git
Log | Files | Refs | README

captcha.rs (11821B)

      1 use std::collections::{HashMap, HashSet};
      2 use std::fmt::{Display, Formatter};
      3 use std::hash::Hash;
      4 use base64::{engine::general_purpose, Engine as _};
      5 use bresenham::Bresenham;
      6 use image::{DynamicImage, GenericImageView, Rgba};
      7 use lazy_static::lazy_static;
      8 
      9 const B64_PREFIX: &'static str = "R0lGODlhCAAOAIAAAAAAAAAAACH5BAgAAAAALAAAAAAIAA4AgAQCBPz+/AI";
     10 // list of letters that contains other letters: (h, n) (I, l) (y, u) (Q, O) (B, 3) (E, L) (R, P)
     11 // So our alphabet needs to have "I" before "l" since "l" is contained by "I".
     12 const ALPHABET1: &'static str = "abdcefgh1ijkImnpoqrstyQuvwxzABCDEGJKMNHLORPFSTlUVWXYZ023456789";
     13 const LETTER_WIDTH: u32 = 8;
     14 const LETTER_HEIGHT: u32 = 14;
     15 const NB_CHARS: u32 = 5;
     16 const LEFT_PADDING: u32 = 5;  // left padding for difficulty 1 and 2
     17 const TOP_PADDING: u32 = 7; // top padding for difficulty 1 and 2
     18 
     19 lazy_static! {
     20    static ref B64_MAP: HashMap<char, &'static str> = HashMap::from([
     21        ('0', "VhI8Qkbv3FIvGMeiQ1fPSzSXiSAIFADs="),
     22        ('1', "UhI8QkcvnHlpJSXgNbdnO2FViVQAAOw=="),
     23        ('2', "UhI+hcWruGkMgSmrfvGnrtVDiKBYAOw=="),
     24        ('3', "UhH+hatyBEkTuzVjpldWtHIUiUgAAOw=="),
     25        ('4', "VhI8XkcvqIFiGTmbvdRFl2TzJSCYFADs="),
     26        ('5', "WhG+hG6CYGnwrygedRIw3jGlhRpZGAQA7"),
     27        ('6', "XhI+hcWruGoiJrRcha5fPTS0bQpamUQAAOw=="),
     28        ('7', "ThG+hq5jhQEPz1OeuhJT3CIZiAQA7"),
     29        ('8', "XhI+hcWruGosRLPYwxLnaqXEXQpYmUgAAOw=="),
     30        ('9', "VhI+hcWru2kosTjAjxduydyHiSBoFADs="),
     31        ('A', "VhI8Qkbv3FIvGMeiQ3RlT+X3JSBoFADs="),
     32        ('B', "VhG+hm3EK4GMtLimtntlmeHXISJYFADs="),
     33        ('C', "VhI+hatyLAIwuhSgv1edWt1TYSAIFADs="),
     34        ('D', "WhG+hm3EK4GNTNhvpdZXnvHjISJZAAQA7"),
     35        ('E', "UhG+hG6CYGnyTSYrw0RE6K3niaBQAOw=="),
     36        ('F', "ThG+hy5jhgIpsSugs0oe/CIZiAQA7"),
     37        ('G', "VhI+hatyLXgQuhbMqhfhWl13TSB4FADs="),
     38        ('H', "UhG8RqMr93Gm0xjVhlkl3BIaiUQAAOw=="),
     39        ('I', "UhH+hi4rmXmzhgZmq1JQuboUiUAAAOw=="),
     40        ('J', "UhI8QG6mdlpMRInqhpRI/64TiUQAAOw=="),
     41        ('K', "XhG8RqHruQIQrNXbfirLO2oUaQpamUQAAOw=="),
     42        ('L', "UhG8RmMvKAHwOTVvP1bmpH4UiUgAAOw=="),
     43        ('M', "WhG8RqJ0NI1DTUVgrPZg7vz3ISJZGAQA7"),
     44        ('N', "WhG8RqH3tAFTJUSgXzpvTGlXISJZGAQA7"),
     45        ('O', "VhI+hcWru2kpTxlfxBZBx/23ISJYFADs="),
     46        ('P', "ThG+hG6DI4JJsPuQavhJnD4ZiAQA7"),
     47        ('Q', "WhI+hcWru2kpTxjdhXSxeDjDISJZAAQA7"),
     48        ('R', "WhG+hG6DI4JJs1vNc07jlNHXISJZGAQA7"),
     49        ('S', "UhH+hC4obkHGywVjpw1tbC1XiiBQAOw=="),
     50        ('T', "UhG+hq9cIHpIuwGghTXn2eoXiVQAAOw=="),
     51        ('U', "UhG8RqMr93GlrQivT1UBmioTiiBQAOw=="),
     52        ('V', "VhG8RqMr9gJOLpjon1bsefiHiSIoFADs="),
     53        ('W', "UhG8RqMr93GnLUWBhplzyh4TiaBQAOw=="),
     54        ('X', "UhG8RqMrrQJQNUXvfjG5S72GiWAAAOw=="),
     55        ('Y', "UhG8RqMrrQJQNUXvtPDst/WHiiBQAOw=="),
     56        ('Z', "UhG+hG5jtVIRHIlvpcwBnpnHiWAAAOw=="),
     57        ('a', "ThI+pq+FuYAyNvitnfuB2yoRKAQA7"),
     58        ('b', "WhG8RmMvKAFSONukaPDRji4VgRJZHAQA7"),
     59        ('c', "RhI+pq+FuYHwt1CWBfJn5VAAAOw=="),
     60        ('d', "VhI8YkbD93JtMrmoutpvmeEnNSB4FADs="),
     61        ('e', "RhI+pq+FxnJEyvntXBRWzzxQAOw=="),
     62        ('f', "VhI8QG7f2VJNwoliZpQm7XSXiSBoFADs="),
     63        ('g', "VhI+pm+EO3nnQwBqDpXvRq03aFy4FADs="),
     64        ('h', "VhG8RmMvKAFSONukaPDTjrXlgRJYFADs="),
     65        ('i', "ThI8Qkcrd1kMrzlNTpldKCIZAAQA7"),
     66        ('j', "UhI8XkbANF0uPTlTxVSw/P0kZVAAAOw=="),
     67        ('k', "VhH8RaMrgWJwrQrUSRs7Sll3PSB4FADs="),
     68        ('l', "RhI+haMueAgPw1CZfjvrODxYAOw=="),
     69        ('m', "ThI+piwHh4ItUWkjn1Rl3x4RKAQA7"),
     70        ('n', "UhI+pixHgHnSG0hNljY1jvzHiUgAAOw=="),
     71        ('o', "ThI+pq+FxnJEyPvSgBbXyy4RMAQA7"),
     72        ('p', "VhI+pixHgHnSG0hNljS3vOUlXxygFADs="),
     73        ('q', "VhI+pq+HwHnTS0IBuxpLaiCXVMSIFADs="),
     74        ('r', "ShI+pixHgnInzyXTbw1uzDxoFADs="),
     75        ('s', "RhI+pm+EPHHphUanorLeyvxQAOw=="),
     76        ('t', "UhI95EcrIYlsTVuqueYD3qIQiUgAAOw=="),
     77        ('u', "ThI+pixHt3onSUOggyJvHzoRLAQA7"),
     78        ('v', "ThI+pixHt3nGAVmnt1VtOz4RLAQA7"),
     79        ('w', "UhI+pixHt3onPAXprzJliyzHiUgAAOw=="),
     80        ('x', "ThI+pixH9nJHTPZjsBVTSyoRLAQA7"),
     81        ('y', "VhI+pixHt3onSUOggyJvHXlkPxS0FADs="),
     82        ('z', "PhI+pm+GvXAuzIjkfZXwVADs="),
     83    ]);
     84    static ref RED_COLOR: Rgba<u8> = Rgba::from([204, 2, 4, 255]);
     85    static ref ON_COLOR: Rgba<u8> = Rgba::from([252, 254, 252, 255]);
     86 }
     87 
     88 fn get_letter_img(letter: char) -> DynamicImage {
     89    let b64_suffix = B64_MAP.get(&letter).expect(format!("letter image not found for {}", letter).as_str());
     90    let img_dec = general_purpose::STANDARD.decode(format!("{}{}", B64_PREFIX, b64_suffix)).unwrap();
     91    image::load_from_memory(&img_dec).unwrap()
     92 }
     93 
     94 pub fn solve_b64(b64_str: &str) -> Option<String> {
     95    let img_dec = general_purpose::STANDARD.decode(b64_str.strip_prefix("data:image/gif;base64,")?).ok()?;
     96    let img = image::load_from_memory(&img_dec).ok()?;
     97    if img.width() > 60 {
     98        return match solve_difficulty3(&img) {
     99            Ok(answer) => Some(answer),
    100            Err(e) => {
    101                println!("{:?}", e);
    102                None
    103            },
    104        };
    105    }
    106    solve_difficulty2(&img)
    107 }
    108 
    109 // This function can solve both difficulty 1 and 2.
    110 fn solve_difficulty2(img: &DynamicImage) -> Option<String> {
    111    let mut answer = String::new();
    112    for i in 0..NB_CHARS {
    113        let sub_img = img.crop_imm(LEFT_PADDING + ((LETTER_WIDTH +1)*i), TOP_PADDING, LETTER_WIDTH, LETTER_HEIGHT);
    114        for c in ALPHABET1.chars() {
    115            if img_contains_letter(&sub_img, c) {
    116                answer.push(c);
    117                break;
    118            }
    119        }
    120    }
    121    Some(answer)
    122 }
    123 
    124 #[derive(Debug, PartialEq, Eq, Hash)]
    125 struct Letter {
    126    offset: Point,
    127    character: char,
    128 }
    129 
    130 impl Letter {
    131    fn new(offset: Point, character: char) -> Self {
    132        Self { offset, character }
    133    }
    134 
    135    fn offset(&self) -> Point {
    136        self.offset.clone()
    137    }
    138 
    139    fn center(&self) -> Point {
    140        let offset = self.offset();
    141        Point::new(offset.x + LETTER_WIDTH/2, offset.y + LETTER_HEIGHT/2 - 1)
    142    }
    143 }
    144 
    145 #[derive(Debug)]
    146 struct CaptchaErr(String);
    147 
    148 impl Display for CaptchaErr {
    149    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
    150        write!(f, "{}", self.0)
    151    }
    152 }
    153 
    154 impl std::error::Error for CaptchaErr {}
    155 
    156 // SolveDifficulty3 solve captcha for difficulty 3
    157 // For each pixel, verify if a match is found. If we do have a match,
    158 // verify that we have some "red" in it.
    159 //
    160 // Red circle is 17x17 (initial point)
    161 fn solve_difficulty3(img: &DynamicImage) -> Result<String, CaptchaErr> {
    162    //img.save(format!("captcha.gif")).unwrap();
    163 
    164    // Step1: Find all letters with red on the center
    165    let letters_set = find_letters(&img)?;
    166 
    167    // Step2: Find the starting letter
    168    let starting = get_starting_letter(&img, &letters_set)
    169        .ok_or(CaptchaErr("could not find starting letter".to_owned()))?;
    170 
    171    // Step3: Solve path
    172    let answer = solve_path(starting, &letters_set, &img);
    173    Ok(answer)
    174 }
    175 
    176 // Bresenham algorithm will return an iterator of all the pixels that makes a line in between two points.
    177 // From the starting letter, we trace a line to all other letters and count how many red pixels were on the line.
    178 // The next letter will be the one that had the most red pixels.
    179 // Repeat until we find the whole path.
    180 fn solve_path(starting: &Letter, letters_set: &HashSet<Letter>, img: &DynamicImage) -> String {
    181    let mut answer = String::new();
    182    let mut remaining: HashSet<_> = letters_set.iter().collect();
    183    let mut letter = remaining.take(&starting).unwrap();
    184    for _ in 0..NB_CHARS {
    185        answer.push(letter.character);
    186        let mut dest_count = HashMap::<&Letter, usize>::new();
    187        for dest in remaining.iter() {
    188            let red = Bresenham::new(letter.center().into(), dest.center().into())
    189                .filter(|(x, y)| is_red(img.get_pixel(*x as u32, *y as u32)))
    190                .count();
    191            dest_count.insert(dest, red);
    192        }
    193        if let Some((dest_max, _)) = dest_count.into_iter().max_by_key(|e| e.1) {
    194            letter = remaining.take(dest_max).unwrap();
    195        }
    196    }
    197    answer
    198 }
    199 
    200 fn find_letters(img: &DynamicImage) -> Result<HashSet<Letter>, CaptchaErr> {
    201    const IMAGE_WIDTH: u32 = 150;
    202    const IMAGE_HEIGHT: u32 = 200;
    203    const MIN_PX_FOR_LETTER: usize = 21;
    204    let mut letters_set = HashSet::new();
    205    for y in 0..IMAGE_HEIGHT-LETTER_HEIGHT {
    206        for x in 0..IMAGE_WIDTH-LETTER_WIDTH {
    207            let letter_img = img.crop_imm(x, y, LETTER_WIDTH, LETTER_HEIGHT);
    208            // We know that minimum amount of pixels on to form a letter is 21
    209            // We can skip squares that do not have this prerequisite
    210            // Check middle pixels for red, if no red pixels, we can ignore that square
    211            if count_px_on(&letter_img) < MIN_PX_FOR_LETTER || !has_red_in_center_area(&letter_img) {
    212                continue;
    213            }
    214            'alphabet_loop: for c in ALPHABET1.chars() {
    215                if !img_contains_letter(&letter_img, c) {
    216                    continue;
    217                }
    218                // "w" fits in "W". So if we find "W" 1 px bellow, discard "w"
    219                for (a, b, x, y) in vec![('w', 'W', x, y+1), ('k', 'K', x+1, y+1)] {
    220                    if c == a {
    221                        let one_px_down_img = img.crop_imm(x, y, LETTER_WIDTH, LETTER_HEIGHT);
    222                        if img_contains_letter(&one_px_down_img, b) {
    223                            continue 'alphabet_loop;
    224                        }
    225                    }
    226                }
    227                letters_set.insert(Letter::new(Point::new(x, y), c));
    228                break;
    229            }
    230        }
    231    }
    232    if letters_set.len() != NB_CHARS as usize {
    233        return Err(CaptchaErr(format!("did not find exactly 5 letters {}", letters_set.len())));
    234    }
    235    Ok(letters_set)
    236 }
    237 
    238 fn get_starting_letter<'a>(img: &DynamicImage, letters_set: &'a HashSet<Letter>) -> Option<&'a Letter> {
    239    const MIN_STARTING_PT_RED_PX: usize = 50;
    240    for letter in letters_set.iter() {
    241        let square = img.crop_imm(letter.offset.x-5, letter.offset.y-3, LETTER_WIDTH+5+6, LETTER_HEIGHT+3+2);
    242        let count_red = count_red_px(&square);
    243        if count_red > MIN_STARTING_PT_RED_PX {
    244            return Some(letter);
    245        }
    246    }
    247    None
    248 }
    249 
    250 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    251 struct Point {
    252    x: u32,
    253    y: u32,
    254 }
    255 
    256 impl Point {
    257    fn new(x: u32, y: u32) -> Self {
    258        Self{x, y}
    259    }
    260 }
    261 
    262 impl From<Point> for bresenham::Point {
    263    fn from(value: Point) -> Self {
    264        (value.x as isize, value.y as isize)
    265    }
    266 }
    267 
    268 // give an image and a valid letter image, return either or not the letter is in that image.
    269 fn img_contains_letter(img: &DynamicImage, c: char) -> bool {
    270    let letter_img = get_letter_img(c);
    271    if letter_img.dimensions() != img.dimensions() {
    272        return false;
    273    }
    274    for y in 0..LETTER_HEIGHT {
    275        for x in 0..LETTER_WIDTH {
    276            let good_letter_color = letter_img.get_pixel(x, y);
    277            let letter_img_color = img.get_pixel(x, y);
    278            // If we find an Off pixel where it's supposed to be On, skip that letter
    279            if is_on(good_letter_color) && !is_on(letter_img_color) {
    280                return false;
    281            }
    282        }
    283    }
    284    true
    285 }
    286 
    287 fn is_on(c: Rgba<u8>) -> bool {
    288    c == *ON_COLOR || c == *RED_COLOR
    289 }
    290 
    291 fn is_red(c: Rgba<u8>) -> bool {
    292    c == *RED_COLOR
    293 }
    294 
    295 fn has_red_in_center_area(letter_img: &DynamicImage) -> bool {
    296    letter_img.view(LETTER_WIDTH/2 - 1, LETTER_HEIGHT/2 - 1, 2, 2)
    297        .pixels()
    298        .any(|(_, _, c)| is_red(c))
    299 }
    300 
    301 // Count pixels that are On (either white or red)
    302 fn count_px_on(img: &DynamicImage) -> usize {
    303    img.pixels()
    304        .filter(|(_, _, c)| is_on(*c))
    305        .count()
    306 }
    307 
    308 // Count pixels that are red
    309 fn count_red_px(img: &DynamicImage) -> usize {
    310    img.pixels()
    311        .filter(|(_, _, c)| is_red(*c))
    312        .count()
    313 }