peat_mesh/
geohash.rs

1//! Vendored geohash implementation for supply chain security.
2//!
3//! This is a reviewed copy of the geohash algorithm from the `geohash` crate (v0.13.1),
4//! with external dependencies (`geo_types`, `libm`) removed. The algorithm is the public
5//! [Geohash](https://en.wikipedia.org/wiki/Geohash) specification.
6//!
7//! Vendored as part of supply chain audit (2026-03-26) to eliminate dependency on a
8//! crate whose primary maintainer is based in a US-sensitive country. The algorithm
9//! itself is a well-known, deterministic geographic encoding with no security implications.
10//!
11//! Source: <https://github.com/georust/geohash.rs> (v0.13.1)
12//! Original authors: Ning Sun, contributors
13//!
14//! ## License
15//!
16//! The original `geohash` crate is dual-licensed under MIT and Apache-2.0.
17//! This vendored copy is used under the MIT license:
18//!
19//! ```text
20//! Copyright (c) 2016 Ning Sun
21//!
22//! Permission is hereby granted, free of charge, to any person obtaining a copy
23//! of this software and associated documentation files (the "Software"), to deal
24//! in the Software without restriction, including without limitation the rights
25//! to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
26//! copies of the Software, and to permit persons to whom the Software is
27//! furnished to do so, subject to the following conditions:
28//!
29//! The above copyright notice and this permission notice shall be included in
30//! all copies or substantial portions of the Software.
31//!
32//! THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
33//! IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
34//! FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
35//! AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
36//! LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
37//! OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
38//! SOFTWARE.
39//! ```
40
41use std::error::Error;
42use std::fmt;
43
44// --- Error types ---
45
46#[derive(Debug)]
47#[allow(clippy::enum_variant_names)]
48pub enum GeohashError {
49    InvalidHashCharacter(char),
50    InvalidCoordinateRange { lon: f64, lat: f64 },
51    InvalidLength(usize),
52    InvalidHash(String),
53}
54
55impl fmt::Display for GeohashError {
56    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
57        match self {
58            GeohashError::InvalidHashCharacter(c) => write!(f, "invalid hash character: {c}"),
59            GeohashError::InvalidCoordinateRange { lon, lat } => {
60                write!(f, "invalid coordinate range: lon={lon}, lat={lat}")
61            }
62            GeohashError::InvalidLength(len) => write!(
63                f,
64                "invalid length: {len}. Must be between 1 and 12 inclusive",
65            ),
66            GeohashError::InvalidHash(msg) => write!(f, "invalid hash: {msg}"),
67        }
68    }
69}
70
71impl Error for GeohashError {}
72
73// --- Direction & Neighbors ---
74
75#[derive(Clone, Copy, Debug, PartialEq, Eq)]
76pub enum Direction {
77    N,
78    NE,
79    E,
80    SE,
81    S,
82    SW,
83    W,
84    NW,
85}
86
87impl Direction {
88    pub fn to_tuple(self) -> (f64, f64) {
89        match self {
90            Direction::SW => (-1.0, -1.0),
91            Direction::S => (-1.0, 0.0),
92            Direction::SE => (-1.0, 1.0),
93            Direction::W => (0.0, -1.0),
94            Direction::E => (0.0, 1.0),
95            Direction::NW => (1.0, -1.0),
96            Direction::N => (1.0, 0.0),
97            Direction::NE => (1.0, 1.0),
98        }
99    }
100}
101
102#[derive(Debug, Clone, PartialEq)]
103pub struct Neighbors {
104    pub sw: String,
105    pub s: String,
106    pub se: String,
107    pub w: String,
108    pub e: String,
109    pub nw: String,
110    pub n: String,
111    pub ne: String,
112}
113
114// --- Base32 tables ---
115
116#[rustfmt::skip]
117const BASE32_CODES: [char; 32] = [
118    '0', '1', '2', '3', '4', '5', '6', '7',
119    '8', '9', 'b', 'c', 'd', 'e', 'f', 'g',
120    'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r',
121    's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
122];
123
124#[rustfmt::skip]
125const DECODER: [u8; 256] = [
126    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
127    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
128    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
129    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
130    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
131    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
132    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
133    0x08, 0x09, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
134    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
135    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
136    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
137    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
138    0xff, 0xff, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
139    0x10, 0xff, 0x11, 0x12, 0xff, 0x13, 0x14, 0xff,
140    0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c,
141    0x1d, 0x1e, 0x1f, 0xff, 0xff, 0xff, 0xff, 0xff,
142    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
143    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
144    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
145    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
146    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
147    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
148    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
149    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
150    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
151    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
152    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
153    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
154    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
155    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
156    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
157    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
158];
159
160// --- Bit interleaving ---
161
162#[inline]
163fn spread(x: u32) -> u64 {
164    let mut v = x as u64;
165    v = (v | (v << 16)) & 0x0000ffff0000ffff;
166    v = (v | (v << 8)) & 0x00ff00ff00ff00ff;
167    v = (v | (v << 4)) & 0x0f0f0f0f0f0f0f0f;
168    v = (v | (v << 2)) & 0x3333333333333333;
169    v = (v | (v << 1)) & 0x5555555555555555;
170    v
171}
172
173#[inline]
174fn interleave(x: u32, y: u32) -> u64 {
175    spread(x) | (spread(y) << 1)
176}
177
178#[inline]
179fn squash(x: u64) -> u32 {
180    let mut v = x & 0x5555555555555555;
181    v = (v | (v >> 1)) & 0x3333333333333333;
182    v = (v | (v >> 2)) & 0x0f0f0f0f0f0f0f0f;
183    v = (v | (v >> 4)) & 0x00ff00ff00ff00ff;
184    v = (v | (v >> 8)) & 0x0000ffff0000ffff;
185    v = (v | (v >> 16)) & 0x00000000ffffffff;
186    v as u32
187}
188
189#[inline]
190fn deinterleave(x: u64) -> (u32, u32) {
191    (squash(x), squash(x >> 1))
192}
193
194// --- Core functions ---
195
196/// Encode a (lon, lat) coordinate to a geohash string of the given length.
197pub fn encode(lon: f64, lat: f64, len: usize) -> Result<String, GeohashError> {
198    if !(-180.0..=180.0).contains(&lon) || !(-90.0..=90.0).contains(&lat) {
199        return Err(GeohashError::InvalidCoordinateRange { lon, lat });
200    }
201    if !(1..=12).contains(&len) {
202        return Err(GeohashError::InvalidLength(len));
203    }
204
205    let lat32 = ((lat * 0.005555555555555556 + 1.5).to_bits() >> 20) as u32;
206    let lon32 = ((lon * 0.002777777777777778 + 1.5).to_bits() >> 20) as u32;
207
208    let mut interleaved = interleave(lat32, lon32);
209    let mut out = String::with_capacity(len);
210    for _ in 0..len {
211        let code = (interleaved >> 59) as usize & 0x1f;
212        out.push(BASE32_CODES[code]);
213        interleaved <<= 5;
214    }
215    Ok(out)
216}
217
218fn decode_range(x: u32, r: f64) -> f64 {
219    let p = f64::from_bits(((x as u64) << 20) | (1023 << 52));
220    2.0 * r * (p - 1.0) - r
221}
222
223fn error_with_precision(bits: u32) -> (f64, f64) {
224    let lat_bits = bits / 2;
225    let lon_bits = bits - lat_bits;
226    // ldexp(x, n) = x * 2^n
227    let lat_err = 180.0 * 2f64.powi(-(lat_bits as i32));
228    let lon_err = 360.0 * 2f64.powi(-(lon_bits as i32));
229    (lat_err, lon_err)
230}
231
232/// Decode a geohash string to ((lon, lat), lon_error, lat_error).
233pub fn decode(hash_str: &str) -> Result<((f64, f64), f64, f64), GeohashError> {
234    let bits = hash_str.len() * 5;
235    if hash_str.len() > 12 {
236        return Err(GeohashError::InvalidHash(
237            "hash length exceeds maximum of 12".to_string(),
238        ));
239    }
240
241    let mut int_hash: u64 = 0;
242    for c in hash_str.bytes() {
243        let val = DECODER[c as usize];
244        if val == 0xff {
245            return Err(GeohashError::InvalidHashCharacter(c as char));
246        }
247        int_hash <<= 5;
248        int_hash |= val as u64;
249    }
250
251    let full_hash = int_hash << (64 - bits);
252    let (lat_int, lon_int) = deinterleave(full_hash);
253    let lat = decode_range(lat_int, 90.0);
254    let lon = decode_range(lon_int, 180.0);
255    let (lat_err, lon_err) = error_with_precision(bits as u32);
256
257    Ok((
258        ((lon + lon_err / 2.0), (lat + lat_err / 2.0)),
259        lon_err / 2.0,
260        lat_err / 2.0,
261    ))
262}
263
264/// Find a neighboring geohash in the given direction.
265pub fn neighbor(hash_str: &str, direction: Direction) -> Result<String, GeohashError> {
266    let ((lon, lat), lon_err, lat_err) = decode(hash_str)?;
267    let (dlat, dlon) = direction.to_tuple();
268    let neighbor_lon = ((lon + 2.0 * lon_err.abs() * dlon) + 180.0).rem_euclid(360.0) - 180.0;
269    let neighbor_lat = ((lat + 2.0 * lat_err.abs() * dlat) + 90.0).rem_euclid(180.0) - 90.0;
270    encode(neighbor_lon, neighbor_lat, hash_str.len())
271}
272
273/// Find all 8 neighboring geohashes.
274pub fn neighbors(hash_str: &str) -> Result<Neighbors, GeohashError> {
275    Ok(Neighbors {
276        sw: neighbor(hash_str, Direction::SW)?,
277        s: neighbor(hash_str, Direction::S)?,
278        se: neighbor(hash_str, Direction::SE)?,
279        w: neighbor(hash_str, Direction::W)?,
280        e: neighbor(hash_str, Direction::E)?,
281        nw: neighbor(hash_str, Direction::NW)?,
282        n: neighbor(hash_str, Direction::N)?,
283        ne: neighbor(hash_str, Direction::NE)?,
284    })
285}
286
287#[cfg(test)]
288mod tests {
289    use super::*;
290
291    #[test]
292    fn test_encode() {
293        let hash = encode(-120.6623, 35.3003, 5).unwrap();
294        assert_eq!(hash, "9q60y");
295    }
296
297    #[test]
298    fn test_encode_long() {
299        let hash = encode(-120.6623, 35.3003, 10).unwrap();
300        assert_eq!(hash, "9q60y60rhs");
301    }
302
303    #[test]
304    fn test_decode() {
305        let ((lon, lat), _, _) = decode("9q60y").unwrap();
306        assert!((lon - (-120.65185546875)).abs() < 1e-10);
307        assert!((lat - 35.31005859375).abs() < 1e-10);
308    }
309
310    #[test]
311    fn test_roundtrip() {
312        let original_lon = -122.4194;
313        let original_lat = 37.7749;
314        let hash = encode(original_lon, original_lat, 7).unwrap();
315        let ((lon, lat), _, _) = decode(&hash).unwrap();
316        assert!((lon - original_lon).abs() < 0.001);
317        assert!((lat - original_lat).abs() < 0.001);
318    }
319
320    #[test]
321    fn test_neighbor() {
322        let n = neighbor("9q60y60rhs", Direction::N).unwrap();
323        assert_eq!(n, "9q60y60rht");
324    }
325
326    #[test]
327    fn test_neighbors() {
328        let n = neighbors("9q60y60rhs").unwrap();
329        assert_eq!(n.n, "9q60y60rht");
330        assert_eq!(n.ne, "9q60y60rhv");
331        assert_eq!(n.e, "9q60y60rhu");
332        assert_eq!(n.se, "9q60y60rhg");
333        assert_eq!(n.s, "9q60y60rhe");
334        assert_eq!(n.sw, "9q60y60rh7");
335        assert_eq!(n.w, "9q60y60rhk");
336        assert_eq!(n.nw, "9q60y60rhm");
337    }
338
339    #[test]
340    fn test_invalid_coordinate() {
341        assert!(encode(200.0, 0.0, 5).is_err());
342        assert!(encode(0.0, 100.0, 5).is_err());
343    }
344
345    #[test]
346    fn test_invalid_hash() {
347        assert!(decode("invalid!").is_err());
348    }
349
350    #[test]
351    fn test_sf_geohash() {
352        let hash = encode(-122.4194, 37.7749, 7).unwrap();
353        assert!(hash.starts_with("9q8yy"));
354    }
355}
peat_mesh/geohash.rs

peat_mesh/
geohash.rs
