bhcli

A TUI for chatting on LE PHP Chats
git clone https://git.dasho.dev/bhcli.git
Log | Files | Refs | README

captcha.rs (12093B)

      1 use base64::{engine::general_purpose, Engine as _};
      2 use bresenham::Bresenham;
      3 use image::{DynamicImage, GenericImageView, Rgba};
      4 use lazy_static::lazy_static;
      5 use std::collections::{HashMap, HashSet};
      6 use std::fmt::{Display, Formatter};
      7 use std::hash::Hash;
      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
     90        .get(&letter)
     91        .expect(format!("letter image not found for {}", letter).as_str());
     92    let img_dec = general_purpose::STANDARD
     93        .decode(format!("{}{}", B64_PREFIX, b64_suffix))
     94        .unwrap();
     95    image::load_from_memory(&img_dec).unwrap()
     96 }
     97 
     98 pub fn solve_b64(b64_str: &str) -> Option<String> {
     99    let img_dec = general_purpose::STANDARD
    100        .decode(b64_str.strip_prefix("data:image/gif;base64,")?)
    101        .ok()?;
    102    let img = image::load_from_memory(&img_dec).ok()?;
    103    if img.width() > 60 {
    104        return match solve_difficulty3(&img) {
    105            Ok(answer) => Some(answer),
    106            Err(e) => {
    107                println!("{:?}", e);
    108                None
    109            }
    110        };
    111    }
    112    solve_difficulty2(&img)
    113 }
    114 
    115 // This function can solve both difficulty 1 and 2.
    116 fn solve_difficulty2(img: &DynamicImage) -> Option<String> {
    117    let mut answer = String::new();
    118    for i in 0..NB_CHARS {
    119        let sub_img = img.crop_imm(
    120            LEFT_PADDING + ((LETTER_WIDTH + 1) * i),
    121            TOP_PADDING,
    122            LETTER_WIDTH,
    123            LETTER_HEIGHT,
    124        );
    125        for c in ALPHABET1.chars() {
    126            if img_contains_letter(&sub_img, c) {
    127                answer.push(c);
    128                break;
    129            }
    130        }
    131    }
    132    Some(answer)
    133 }
    134 
    135 #[derive(Debug, PartialEq, Eq, Hash)]
    136 struct Letter {
    137    offset: Point,
    138    character: char,
    139 }
    140 
    141 impl Letter {
    142    fn new(offset: Point, character: char) -> Self {
    143        Self { offset, character }
    144    }
    145 
    146    fn offset(&self) -> Point {
    147        self.offset.clone()
    148    }
    149 
    150    fn center(&self) -> Point {
    151        let offset = self.offset();
    152        Point::new(
    153            offset.x + LETTER_WIDTH / 2,
    154            offset.y + LETTER_HEIGHT / 2 - 1,
    155        )
    156    }
    157 }
    158 
    159 #[derive(Debug)]
    160 struct CaptchaErr(String);
    161 
    162 impl Display for CaptchaErr {
    163    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
    164        write!(f, "{}", self.0)
    165    }
    166 }
    167 
    168 impl std::error::Error for CaptchaErr {}
    169 
    170 // SolveDifficulty3 solve captcha for difficulty 3
    171 // For each pixel, verify if a match is found. If we do have a match,
    172 // verify that we have some "red" in it.
    173 //
    174 // Red circle is 17x17 (initial point)
    175 fn solve_difficulty3(img: &DynamicImage) -> Result<String, CaptchaErr> {
    176    //img.save(format!("captcha.gif")).unwrap();
    177 
    178    // Step1: Find all letters with red on the center
    179    let letters_set = find_letters(&img)?;
    180 
    181    // Step2: Find the starting letter
    182    let starting = get_starting_letter(&img, &letters_set)
    183        .ok_or(CaptchaErr("could not find starting letter".to_owned()))?;
    184 
    185    // Step3: Solve path
    186    let answer = solve_path(starting, &letters_set, &img);
    187    Ok(answer)
    188 }
    189 
    190 // Bresenham algorithm will return an iterator of all the pixels that makes a line in between two points.
    191 // From the starting letter, we trace a line to all other letters and count how many red pixels were on the line.
    192 // The next letter will be the one that had the most red pixels.
    193 // Repeat until we find the whole path.
    194 fn solve_path(starting: &Letter, letters_set: &HashSet<Letter>, img: &DynamicImage) -> String {
    195    let mut answer = String::new();
    196    let mut remaining: HashSet<_> = letters_set.iter().collect();
    197    let mut letter = remaining.take(&starting).unwrap();
    198    for _ in 0..NB_CHARS {
    199        answer.push(letter.character);
    200        let mut dest_count = HashMap::<&Letter, usize>::new();
    201        for dest in remaining.iter() {
    202            let red = Bresenham::new(letter.center().into(), dest.center().into())
    203                .filter(|(x, y)| is_red(img.get_pixel(*x as u32, *y as u32)))
    204                .count();
    205            dest_count.insert(dest, red);
    206        }
    207        if let Some((dest_max, _)) = dest_count.into_iter().max_by_key(|e| e.1) {
    208            letter = remaining.take(dest_max).unwrap();
    209        }
    210    }
    211    answer
    212 }
    213 
    214 fn find_letters(img: &DynamicImage) -> Result<HashSet<Letter>, CaptchaErr> {
    215    const IMAGE_WIDTH: u32 = 150;
    216    const IMAGE_HEIGHT: u32 = 200;
    217    const MIN_PX_FOR_LETTER: usize = 21;
    218    let mut letters_set = HashSet::new();
    219    for y in 0..IMAGE_HEIGHT - LETTER_HEIGHT {
    220        for x in 0..IMAGE_WIDTH - LETTER_WIDTH {
    221            let letter_img = img.crop_imm(x, y, LETTER_WIDTH, LETTER_HEIGHT);
    222            // We know that minimum amount of pixels on to form a letter is 21
    223            // We can skip squares that do not have this prerequisite
    224            // Check middle pixels for red, if no red pixels, we can ignore that square
    225            if count_px_on(&letter_img) < MIN_PX_FOR_LETTER || !has_red_in_center_area(&letter_img)
    226            {
    227                continue;
    228            }
    229            'alphabet_loop: for c in ALPHABET1.chars() {
    230                if !img_contains_letter(&letter_img, c) {
    231                    continue;
    232                }
    233                // "w" fits in "W". So if we find "W" 1 px bellow, discard "w"
    234                for (a, b, x, y) in vec![('w', 'W', x, y + 1), ('k', 'K', x + 1, y + 1)] {
    235                    if c == a {
    236                        let one_px_down_img = img.crop_imm(x, y, LETTER_WIDTH, LETTER_HEIGHT);
    237                        if img_contains_letter(&one_px_down_img, b) {
    238                            continue 'alphabet_loop;
    239                        }
    240                    }
    241                }
    242                letters_set.insert(Letter::new(Point::new(x, y), c));
    243                break;
    244            }
    245        }
    246    }
    247    if letters_set.len() != NB_CHARS as usize {
    248        return Err(CaptchaErr(format!(
    249            "did not find exactly 5 letters {}",
    250            letters_set.len()
    251        )));
    252    }
    253    Ok(letters_set)
    254 }
    255 
    256 fn get_starting_letter<'a>(
    257    img: &DynamicImage,
    258    letters_set: &'a HashSet<Letter>,
    259 ) -> Option<&'a Letter> {
    260    const MIN_STARTING_PT_RED_PX: usize = 50;
    261    for letter in letters_set.iter() {
    262        let square = img.crop_imm(
    263            letter.offset.x - 5,
    264            letter.offset.y - 3,
    265            LETTER_WIDTH + 5 + 6,
    266            LETTER_HEIGHT + 3 + 2,
    267        );
    268        let count_red = count_red_px(&square);
    269        if count_red > MIN_STARTING_PT_RED_PX {
    270            return Some(letter);
    271        }
    272    }
    273    None
    274 }
    275 
    276 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    277 struct Point {
    278    x: u32,
    279    y: u32,
    280 }
    281 
    282 impl Point {
    283    fn new(x: u32, y: u32) -> Self {
    284        Self { x, y }
    285    }
    286 }
    287 
    288 impl From<Point> for bresenham::Point {
    289    fn from(value: Point) -> Self {
    290        (value.x as isize, value.y as isize)
    291    }
    292 }
    293 
    294 // give an image and a valid letter image, return either or not the letter is in that image.
    295 fn img_contains_letter(img: &DynamicImage, c: char) -> bool {
    296    let letter_img = get_letter_img(c);
    297    if letter_img.dimensions() != img.dimensions() {
    298        return false;
    299    }
    300    for y in 0..LETTER_HEIGHT {
    301        for x in 0..LETTER_WIDTH {
    302            let good_letter_color = letter_img.get_pixel(x, y);
    303            let letter_img_color = img.get_pixel(x, y);
    304            // If we find an Off pixel where it's supposed to be On, skip that letter
    305            if is_on(good_letter_color) && !is_on(letter_img_color) {
    306                return false;
    307            }
    308        }
    309    }
    310    true
    311 }
    312 
    313 fn is_on(c: Rgba<u8>) -> bool {
    314    c == *ON_COLOR || c == *RED_COLOR
    315 }
    316 
    317 fn is_red(c: Rgba<u8>) -> bool {
    318    c == *RED_COLOR
    319 }
    320 
    321 fn has_red_in_center_area(letter_img: &DynamicImage) -> bool {
    322    letter_img
    323        .view(LETTER_WIDTH / 2 - 1, LETTER_HEIGHT / 2 - 1, 2, 2)
    324        .pixels()
    325        .any(|(_, _, c)| is_red(c))
    326 }
    327 
    328 // Count pixels that are On (either white or red)
    329 fn count_px_on(img: &DynamicImage) -> usize {
    330    img.pixels().filter(|(_, _, c)| is_on(*c)).count()
    331 }
    332 
    333 // Count pixels that are red
    334 fn count_red_px(img: &DynamicImage) -> usize {
    335    img.pixels().filter(|(_, _, c)| is_red(*c)).count()
    336 }