bhcli

A TUI for chatting on LE PHP Chats (onion)
git clone https://git.dasho.dev/n0tr1v/bhcli.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 }