nostr-rs-relay

My dev fork of nostr-rs-relay
git clone git://jb55.com/nostr-rs-relay
Log | Files | Refs | README | LICENSE

hexrange.rs (4500B)


      1 //! Utilities for searching hexadecimal
      2 use crate::utils::is_hex;
      3 use hex;
      4 
      5 /// Types of hexadecimal queries.
      6 #[derive(PartialEq, Eq, Debug, Clone)]
      7 pub enum HexSearch {
      8     // when no range is needed, exact 32-byte
      9     Exact(Vec<u8>),
     10     // lower (inclusive) and upper range (exclusive)
     11     Range(Vec<u8>, Vec<u8>),
     12     // lower bound only, upper bound is MAX inclusive
     13     LowerOnly(Vec<u8>),
     14 }
     15 
     16 /// Check if a string contains only f chars
     17 fn is_all_fs(s: &str) -> bool {
     18     s.chars().all(|x| x == 'f' || x == 'F')
     19 }
     20 
     21 /// Find the next hex sequence greater than the argument.
     22 pub fn hex_range(s: &str) -> Option<HexSearch> {
     23     // handle special cases
     24     if !is_hex(s) || s.len() > 64 {
     25         return None;
     26     }
     27     if s.len() == 64 {
     28         return Some(HexSearch::Exact(hex::decode(s).ok()?));
     29     }
     30     // if s is odd, add a zero
     31     let mut hash_base = s.to_owned();
     32     let mut odd = hash_base.len() % 2 != 0;
     33     if odd {
     34         // extend the string to make it even
     35         hash_base.push('0');
     36     }
     37     let base = hex::decode(hash_base).ok()?;
     38     // check for all ff's
     39     if is_all_fs(s) {
     40         // there is no higher bound, we only want to search for blobs greater than this.
     41         return Some(HexSearch::LowerOnly(base));
     42     }
     43 
     44     // return a range
     45     let mut upper = base.clone();
     46     let mut byte_len = upper.len();
     47 
     48     // for odd strings, we made them longer, but we want to increment the upper char (+16).
     49     // we know we can do this without overflowing because we explicitly set the bottom half to 0's.
     50     while byte_len > 0 {
     51         byte_len -= 1;
     52         // check if byte can be incremented, or if we need to carry.
     53         let b = upper[byte_len];
     54         if b == u8::MAX {
     55             // reset and carry
     56             upper[byte_len] = 0;
     57         } else if odd {
     58             // check if first char in this byte is NOT 'f'
     59             if b < 240 {
     60                 upper[byte_len] = b + 16; // bump up the first character in this byte
     61                                           // increment done, stop iterating through the vec
     62                 break;
     63             }
     64             // if it is 'f', reset the byte to 0 and do a carry
     65             // reset and carry
     66             upper[byte_len] = 0;
     67             // done with odd logic, so don't repeat this
     68             odd = false;
     69         } else {
     70             // bump up the first character in this byte
     71             upper[byte_len] = b + 1;
     72             // increment done, stop iterating
     73             break;
     74         }
     75     }
     76     Some(HexSearch::Range(base, upper))
     77 }
     78 
     79 #[cfg(test)]
     80 mod tests {
     81     use super::*;
     82     use crate::error::Result;
     83 
     84     #[test]
     85     fn hex_range_exact() -> Result<()> {
     86         let hex = "abcdef00abcdef00abcdef00abcdef00abcdef00abcdef00abcdef00abcdef00";
     87         let r = hex_range(hex);
     88         assert_eq!(
     89             r,
     90             Some(HexSearch::Exact(hex::decode(hex).expect("invalid hex")))
     91         );
     92         Ok(())
     93     }
     94     #[test]
     95     fn hex_full_range() -> Result<()> {
     96         let hex = "aaaa";
     97         let hex_upper = "aaab";
     98         let r = hex_range(hex);
     99         assert_eq!(
    100             r,
    101             Some(HexSearch::Range(
    102                 hex::decode(hex).expect("invalid hex"),
    103                 hex::decode(hex_upper).expect("invalid hex")
    104             ))
    105         );
    106         Ok(())
    107     }
    108 
    109     #[test]
    110     fn hex_full_range_odd() -> Result<()> {
    111         let r = hex_range("abc");
    112         assert_eq!(
    113             r,
    114             Some(HexSearch::Range(
    115                 hex::decode("abc0").expect("invalid hex"),
    116                 hex::decode("abd0").expect("invalid hex")
    117             ))
    118         );
    119         Ok(())
    120     }
    121 
    122     #[test]
    123     fn hex_full_range_odd_end_f() -> Result<()> {
    124         let r = hex_range("abf");
    125         assert_eq!(
    126             r,
    127             Some(HexSearch::Range(
    128                 hex::decode("abf0").expect("invalid hex"),
    129                 hex::decode("ac00").expect("invalid hex")
    130             ))
    131         );
    132         Ok(())
    133     }
    134 
    135     #[test]
    136     fn hex_no_upper() -> Result<()> {
    137         let r = hex_range("ffff");
    138         assert_eq!(
    139             r,
    140             Some(HexSearch::LowerOnly(
    141                 hex::decode("ffff").expect("invalid hex")
    142             ))
    143         );
    144         Ok(())
    145     }
    146 
    147     #[test]
    148     fn hex_no_upper_odd() -> Result<()> {
    149         let r = hex_range("fff");
    150         assert_eq!(
    151             r,
    152             Some(HexSearch::LowerOnly(
    153                 hex::decode("fff0").expect("invalid hex")
    154             ))
    155         );
    156         Ok(())
    157     }
    158 }