1use std::collections::HashMap;
4use std::fs;
5use std::path::{Path, PathBuf};
6
7use crate::Error;
8
9const UHL_SIZE: usize = 80;
10const DSI_SIZE: usize = 648;
11const ACC_SIZE: usize = 2700;
12const DATA_OFFSET: usize = UHL_SIZE + DSI_SIZE + ACC_SIZE;
13const DATA_SENTINEL: u8 = 0xAA;
14const DTED_SUFFIX: &str = concat!("_1arc_v3.d", "t", "2");
15const MIN_LOOKUP_LATITUDE_DEG: f64 = -90.0;
16const MAX_LOOKUP_LATITUDE_DEG: f64 = 90.0;
17const MIN_LOOKUP_LONGITUDE_DEG: f64 = -180.0;
18const MAX_LOOKUP_LONGITUDE_DEG: f64 = 180.0;
19
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum DtedInterpolation {
22 NearestPosting,
23 Bilinear,
24}
25
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub struct DtedLookupOptions {
28 pub interpolation: DtedInterpolation,
29}
30
31impl Default for DtedLookupOptions {
32 fn default() -> Self {
33 Self {
34 interpolation: DtedInterpolation::Bilinear,
35 }
36 }
37}
38
39#[derive(Debug)]
40pub struct DtedTerrain {
41 root: PathBuf,
42 tiles: HashMap<(i32, i32), DtedTile>,
43}
44
45impl DtedTerrain {
46 pub fn new(root: impl Into<PathBuf>) -> Self {
47 Self {
48 root: root.into(),
49 tiles: HashMap::new(),
50 }
51 }
52
53 pub fn height_m(&mut self, longitude_deg: f64, latitude_deg: f64) -> crate::Result<f64> {
54 self.height_m_with_options(longitude_deg, latitude_deg, DtedLookupOptions::default())
55 }
56
57 pub fn height_m_with_options(
58 &mut self,
59 longitude_deg: f64,
60 latitude_deg: f64,
61 options: DtedLookupOptions,
62 ) -> crate::Result<f64> {
63 validate_lookup_coordinates(longitude_deg, latitude_deg)?;
64 let Some(tile) = self.load_tile(longitude_deg, latitude_deg)? else {
65 return Ok(0.0);
66 };
67 if options.interpolation == DtedInterpolation::NearestPosting {
68 return tile
69 .get_elevation(longitude_deg, latitude_deg)
70 .map(|v| v as f64)
71 .map_err(Error::Parse);
72 }
73
74 let postings_per_deg_lon = tile.lon_count - 1;
75 let postings_per_deg_lat = tile.lat_count - 1;
76
77 let lon_idx = (longitude_deg - tile.origin_longitude) * postings_per_deg_lon as f64;
78 let lat_idx = (latitude_deg - tile.origin_latitude) * postings_per_deg_lat as f64;
79 let lon_lo = lon_idx.floor() as i64;
80 let lat_lo = lat_idx.floor() as i64;
81 let fx = lon_idx - lon_lo as f64;
82 let fy = lat_idx - lat_lo as f64;
83
84 let mut z = 0.0;
85 for (di, wx) in [(0i64, 1.0 - fx), (1i64, fx)] {
86 for (dj, wy) in [(0i64, 1.0 - fy), (1i64, fy)] {
87 let w = wx * wy;
88 if w == 0.0 {
89 continue;
90 }
91 let posting_lon =
92 tile.origin_longitude + (lon_lo + di) as f64 / postings_per_deg_lon as f64;
93 let posting_lat =
94 tile.origin_latitude + (lat_lo + dj) as f64 / postings_per_deg_lat as f64;
95 z += w * f64::from(
96 tile.get_elevation(posting_lon, posting_lat)
97 .map_err(Error::Parse)?,
98 );
99 }
100 }
101 Ok(z)
102 }
103
104 fn load_tile(&mut self, longitude: f64, latitude: f64) -> crate::Result<Option<&DtedTile>> {
105 let mut selected = None;
106 for grid_idx in terrain_grid_candidates(longitude, latitude) {
107 if !self.tiles.contains_key(&grid_idx) {
108 let Some(path) = self.terrain_path_for_grid(grid_idx.0, grid_idx.1) else {
109 continue;
110 };
111 if !path.is_file() {
112 continue;
113 }
114 let tile = DtedTile::from_path(path).map_err(Error::Parse)?;
115 self.tiles.insert(grid_idx, tile);
116 }
117 if let Some(tile) = self.tiles.get(&grid_idx) {
118 if tile.contains(longitude, latitude) {
119 selected = Some(grid_idx);
120 break;
121 }
122 }
123 }
124 Ok(selected.and_then(|grid_idx| self.tiles.get(&grid_idx)))
125 }
126
127 fn terrain_path_for_grid(&self, latitude_index: i32, longitude_index: i32) -> Option<PathBuf> {
128 let tile_name = format!(
129 "{}_{}{}",
130 format_lat(latitude_index),
131 format_lon(longitude_index),
132 DTED_SUFFIX
133 );
134
135 let direct = self.root.join(&tile_name);
136 if direct.is_file() {
137 return Some(direct);
138 }
139
140 let block_dir = terrain_block_dir(latitude_index, longitude_index);
141 let nested = self.root.join(&block_dir).join(&tile_name);
142 if nested.is_file() {
143 return Some(nested);
144 }
145
146 let sibling = self.root.parent()?.join(&block_dir).join(&tile_name);
147 sibling.is_file().then_some(sibling)
148 }
149}
150
151fn validate_lookup_coordinates(longitude_deg: f64, latitude_deg: f64) -> crate::Result<()> {
152 if !longitude_deg.is_finite() {
153 return Err(Error::InvalidInput(
154 "longitude_deg must be finite".to_string(),
155 ));
156 }
157 if !latitude_deg.is_finite() {
158 return Err(Error::InvalidInput(
159 "latitude_deg must be finite".to_string(),
160 ));
161 }
162 if !(MIN_LOOKUP_LONGITUDE_DEG..=MAX_LOOKUP_LONGITUDE_DEG).contains(&longitude_deg) {
163 return Err(Error::InvalidInput(
164 "longitude_deg must be within [-180, 180]".to_string(),
165 ));
166 }
167 if !(MIN_LOOKUP_LATITUDE_DEG..=MAX_LOOKUP_LATITUDE_DEG).contains(&latitude_deg) {
168 return Err(Error::InvalidInput(
169 "latitude_deg must be within [-90, 90]".to_string(),
170 ));
171 }
172 Ok(())
173}
174
175#[derive(Debug)]
176pub struct DtedTile {
177 origin_latitude: f64,
178 origin_longitude: f64,
179 lon_count: usize,
180 lat_count: usize,
181 data_block_length: usize,
182 bytes: Vec<u8>,
183}
184
185impl DtedTile {
186 pub fn from_path(path: impl AsRef<Path>) -> Result<Self, String> {
187 let bytes =
188 fs::read(path.as_ref()).map_err(|e| format!("{}: {e}", path.as_ref().display()))?;
189 if bytes.len() < DATA_OFFSET {
190 return Err(format!(
191 "{} is too short for DTED headers",
192 path.as_ref().display()
193 ));
194 }
195 if &bytes[0..4] != b"UHL1" {
196 return Err(format!("{} missing UHL1 header", path.as_ref().display()));
197 }
198
199 let origin_longitude =
200 parse_dted_coord(std::str::from_utf8(&bytes[4..12]).map_err(|e| e.to_string())?)?;
201 let origin_latitude =
202 parse_dted_coord(std::str::from_utf8(&bytes[12..20]).map_err(|e| e.to_string())?)?;
203 let lon_count = parse_ascii_usize(&bytes[47..51])?;
204 let lat_count = parse_ascii_usize(&bytes[51..55])?;
205 if lon_count < 2 || lat_count < 2 {
206 return Err(format!(
207 "{} has invalid DTED dimensions lon_count={} lat_count={}; both must be at least 2",
208 path.as_ref().display(),
209 lon_count,
210 lat_count
211 ));
212 }
213 let data_block_length = 12 + 2 * lat_count;
214 let expected_len = DATA_OFFSET + lon_count * data_block_length;
215 if bytes.len() < expected_len {
216 return Err(format!(
217 "{} has {} bytes but expected at least {}",
218 path.as_ref().display(),
219 bytes.len(),
220 expected_len
221 ));
222 }
223
224 Ok(Self {
225 origin_latitude,
226 origin_longitude,
227 lon_count,
228 lat_count,
229 data_block_length,
230 bytes,
231 })
232 }
233
234 pub fn get_elevation(&self, longitude: f64, latitude: f64) -> Result<i16, String> {
235 if !self.contains(longitude, latitude) {
236 return Err(format!(
237 "point ({longitude},{latitude}) is outside DTED tile ({},{})",
238 self.origin_longitude, self.origin_latitude
239 ));
240 }
241
242 let latitude_index =
243 py_round_to_usize((latitude - self.origin_latitude) * (self.lat_count - 1) as f64)?;
244 let longitude_index =
245 py_round_to_usize((longitude - self.origin_longitude) * (self.lon_count - 1) as f64)?;
246 if latitude_index >= self.lat_count || longitude_index >= self.lon_count {
247 return Err(format!(
248 "posting index out of bounds lon={} lat={}",
249 longitude_index, latitude_index
250 ));
251 }
252
253 let block_start = DATA_OFFSET + longitude_index * self.data_block_length;
254 let block_end = block_start + self.data_block_length;
255 let block = &self.bytes[block_start..block_end];
256 if block[0] != DATA_SENTINEL {
257 return Err(format!(
258 "DTED block {longitude_index} missing data sentinel"
259 ));
260 }
261 let checksum = i32::from_be_bytes([
262 block[block.len() - 4],
263 block[block.len() - 3],
264 block[block.len() - 2],
265 block[block.len() - 1],
266 ]);
267 let sum = block[..block.len() - 4]
268 .iter()
269 .fold(0i32, |acc, b| acc + i32::from(*b));
270 if sum != checksum {
271 return Err(format!(
272 "DTED checksum failed for block {longitude_index}: expected {checksum}, found {sum}"
273 ));
274 }
275
276 let sample_start = 8 + latitude_index * 2;
277 let raw = i16::from_be_bytes([block[sample_start], block[sample_start + 1]]);
278 Ok(convert_signed_magnitude(raw))
279 }
280
281 fn contains(&self, longitude: f64, latitude: f64) -> bool {
282 latitude >= self.origin_latitude
283 && latitude <= self.origin_latitude + 1.0
284 && longitude >= self.origin_longitude
285 && longitude <= self.origin_longitude + 1.0
286 }
287}
288
289fn terrain_grid(longitude: f64, latitude: f64) -> (i32, i32) {
290 (latitude.floor() as i32, longitude.floor() as i32)
291}
292
293fn terrain_grid_candidates(longitude: f64, latitude: f64) -> Vec<(i32, i32)> {
294 let (lat, lon) = terrain_grid(longitude, latitude);
295 let mut out = vec![(lat, lon)];
296 let on_lat_edge = latitude == latitude.floor();
297 let on_lon_edge = longitude == longitude.floor();
298 if on_lat_edge {
299 out.push((lat - 1, lon));
300 }
301 if on_lon_edge {
302 out.push((lat, lon - 1));
303 }
304 if on_lat_edge && on_lon_edge {
305 out.push((lat - 1, lon - 1));
306 }
307 out
308}
309
310fn format_lat(latitude_index: i32) -> String {
311 if latitude_index >= 0 {
312 format!("n{:02}", latitude_index)
313 } else {
314 format!("s{:02}", -latitude_index)
315 }
316}
317
318fn format_lon(longitude_index: i32) -> String {
319 if longitude_index >= 0 {
320 format!("e{:03}", longitude_index)
321 } else {
322 format!("w{:03}", -longitude_index)
323 }
324}
325
326fn terrain_block_dir(latitude_index: i32, longitude_index: i32) -> String {
327 format!(
328 "{}_{}",
329 format_lat(block_origin(latitude_index)),
330 format_lon(block_origin(longitude_index))
331 )
332}
333
334fn block_origin(index: i32) -> i32 {
335 index.div_euclid(10) * 10
336}
337
338fn parse_ascii_usize(bytes: &[u8]) -> Result<usize, String> {
339 std::str::from_utf8(bytes)
340 .map_err(|e| e.to_string())?
341 .trim()
342 .parse::<usize>()
343 .map_err(|e| e.to_string())
344}
345
346fn parse_dted_coord(input: &str) -> Result<f64, String> {
347 let hemi = input
348 .chars()
349 .last()
350 .ok_or_else(|| "empty DTED coordinate".to_string())?;
351 let sign = match hemi {
352 'S' | 'W' => -1.0,
353 'N' | 'E' => 1.0,
354 _ => return Err(format!("invalid DTED hemisphere {hemi}")),
355 };
356 let coord = &input[..input.len() - 1];
357 let seconds_index = if coord.as_bytes().get(coord.len().saturating_sub(2)) == Some(&b'.') {
358 coord.len() - 4
359 } else {
360 coord.len() - 2
361 };
362 let minutes_index = seconds_index - 2;
363 let degree = coord[..minutes_index]
364 .parse::<i32>()
365 .map_err(|e| e.to_string())?;
366 let minute = coord[minutes_index..seconds_index]
367 .parse::<i32>()
368 .map_err(|e| e.to_string())?;
369 let second = coord[seconds_index..]
370 .parse::<f64>()
371 .map_err(|e| e.to_string())?;
372 Ok(sign * (degree as f64 + ((minute as f64 + second / 60.0) / 60.0)))
373}
374
375fn py_round_to_usize(value: f64) -> Result<usize, String> {
376 if value < 0.0 {
377 return Err(format!("cannot round negative posting index {value}"));
378 }
379 let lo = value.floor();
380 let frac = value - lo;
381 let rounded = if frac < 0.5 {
382 lo
383 } else if frac > 0.5 {
384 lo + 1.0
385 } else {
386 let lo_i = lo as u64;
387 if lo_i.is_multiple_of(2) {
388 lo
389 } else {
390 lo + 1.0
391 }
392 };
393 Ok(rounded as usize)
394}
395
396fn convert_signed_magnitude(raw: i16) -> i16 {
397 if raw < 0 {
398 (-32768i32 - i32::from(raw)) as i16
399 } else {
400 raw
401 }
402}
403
404#[cfg(all(test, sidereon_repo_tests))]
405mod tests {
406 use std::fs;
407 use std::path::Path;
408 use std::path::PathBuf;
409 use std::time::{SystemTime, UNIX_EPOCH};
410
411 use serde_json::Value;
412
413 use crate::test_parity::f64_from_hex;
414 use crate::Error;
415
416 use super::{
417 terrain_block_dir, DtedInterpolation, DtedLookupOptions, DtedTerrain, DtedTile,
418 DATA_OFFSET, DATA_SENTINEL,
419 };
420
421 #[test]
422 fn terrain_block_dir_matches_reference_bucket_names() {
423 assert_eq!(terrain_block_dir(36, -107), "n30_w110");
424 assert_eq!(terrain_block_dir(32, -117), "n30_w120");
425 assert_eq!(terrain_block_dir(43, -112), "n40_w120");
426 assert_eq!(terrain_block_dir(20, -103), "n20_w110");
427 assert_eq!(terrain_block_dir(36, 107), "n30_e100");
428 assert_eq!(terrain_block_dir(-1, -1), "s10_w010");
429 }
430
431 #[test]
432 fn negative_tile_indices_resolve_to_negative_block_dir() {
433 let nonce = SystemTime::now()
434 .duration_since(UNIX_EPOCH)
435 .expect("system time after epoch")
436 .as_nanos();
437 let root = std::env::temp_dir().join(format!(
438 "sidereon-dted-negative-block-{}-{nonce}",
439 std::process::id()
440 ));
441 let tile_dir = root.join("s10_w010");
442 let tile_path = tile_dir.join("s01_w001_1arc_v3.dt2");
443 fs::create_dir_all(&tile_dir).expect("create nested DTED block dir");
444 fs::write(&tile_path, []).expect("create nested DTED tile path");
445
446 let terrain = DtedTerrain::new(&root);
447 let got = terrain
448 .terrain_path_for_grid(-1, -1)
449 .expect("negative nested tile path");
450 assert_eq!(got, tile_path);
451
452 fs::remove_dir_all(root).expect("remove temp DTED block dir");
453 }
454
455 fn fixture_path(name: &str) -> PathBuf {
456 PathBuf::from(env!("CARGO_MANIFEST_DIR"))
457 .join("tests")
458 .join("fixtures")
459 .join("dted")
460 .join(name)
461 }
462
463 fn bits(v: &Value) -> f64 {
464 f64_from_hex(v.as_str().expect("hex-bit string")).expect("valid f64 bits")
465 }
466
467 fn temp_path(name: &str) -> PathBuf {
468 let nonce = SystemTime::now()
469 .duration_since(UNIX_EPOCH)
470 .expect("system time after epoch")
471 .as_nanos();
472 std::env::temp_dir().join(format!("sidereon-{name}-{}-{nonce}", std::process::id()))
473 }
474
475 fn write_synthetic_dted_tile(
476 path: &Path,
477 lon_count: usize,
478 lat_count: usize,
479 sample: impl Fn(usize, usize) -> i16,
480 ) {
481 let data_block_length = 12 + 2 * lat_count;
482 let mut bytes = vec![b' '; DATA_OFFSET];
483 bytes[0..4].copy_from_slice(b"UHL1");
484 bytes[4..12].copy_from_slice(b"1070000W");
485 bytes[12..20].copy_from_slice(b"0360000N");
486 bytes[47..51].copy_from_slice(format!("{lon_count:04}").as_bytes());
487 bytes[51..55].copy_from_slice(format!("{lat_count:04}").as_bytes());
488
489 for lon_index in 0..lon_count {
490 let mut block = vec![0u8; data_block_length];
491 block[0] = DATA_SENTINEL;
492 for lat_index in 0..lat_count {
493 let sample_start = 8 + lat_index * 2;
494 block[sample_start..sample_start + 2]
495 .copy_from_slice(&sample(lon_index, lat_index).to_be_bytes());
496 }
497 let checksum = block[..block.len() - 4]
498 .iter()
499 .fold(0i32, |acc, b| acc + i32::from(*b));
500 let checksum_start = block.len() - 4;
501 block[checksum_start..].copy_from_slice(&checksum.to_be_bytes());
502 bytes.extend(block);
503 }
504
505 fs::write(path, bytes).expect("write synthetic DTED tile");
506 }
507
508 #[test]
509 fn dted_rejects_degenerate_header_counts() {
510 let root = temp_path("dted-degenerate-counts");
511 fs::create_dir_all(&root).expect("create temp DTED dir");
512
513 for (lon_count, lat_count) in [(0, 2), (1, 2), (2, 0), (2, 1)] {
514 let tile_path = root.join(format!("tile-{lon_count}-{lat_count}.dt2"));
515 write_synthetic_dted_tile(&tile_path, lon_count, lat_count, |_, _| 0);
516
517 let err = DtedTile::from_path(&tile_path).expect_err("degenerate counts must error");
518 assert!(
519 err.contains("invalid DTED dimensions"),
520 "unexpected error for lon_count={lon_count} lat_count={lat_count}: {err}"
521 );
522 }
523
524 fs::remove_dir_all(root).expect("remove temp DTED dir");
525 }
526
527 #[test]
528 fn dted_lookup_rejects_nonfinite_coordinates() {
529 let root = temp_path("dted-nonfinite-coordinates");
530 let mut terrain = DtedTerrain::new(&root);
531
532 for (lon, lat, field) in [
533 (f64::NAN, 36.5, "longitude_deg"),
534 (f64::INFINITY, 36.5, "longitude_deg"),
535 (f64::NEG_INFINITY, 36.5, "longitude_deg"),
536 (-106.5, f64::NAN, "latitude_deg"),
537 (-106.5, f64::INFINITY, "latitude_deg"),
538 (-106.5, f64::NEG_INFINITY, "latitude_deg"),
539 ] {
540 assert_eq!(
541 terrain
542 .height_m_with_options(lon, lat, DtedLookupOptions::default())
543 .expect_err("non-finite DTED coordinate must error"),
544 Error::InvalidInput(format!("{field} must be finite"))
545 );
546 }
547
548 assert_eq!(
549 terrain
550 .height_m(f64::NAN, 36.5)
551 .expect_err("height_m must also reject non-finite coordinates"),
552 Error::InvalidInput("longitude_deg must be finite".to_string())
553 );
554 }
555
556 #[test]
557 fn dted_lookup_rejects_out_of_range_coordinates() {
558 let root = temp_path("dted-out-of-range-coordinates");
559 let mut terrain = DtedTerrain::new(&root);
560
561 for (lon, lat, error) in [
562 (
563 -106.5,
564 91.0,
565 Error::InvalidInput("latitude_deg must be within [-90, 90]".to_string()),
566 ),
567 (
568 -106.5,
569 -90.5,
570 Error::InvalidInput("latitude_deg must be within [-90, 90]".to_string()),
571 ),
572 (
573 200.0,
574 36.5,
575 Error::InvalidInput("longitude_deg must be within [-180, 180]".to_string()),
576 ),
577 (
578 -180.5,
579 36.5,
580 Error::InvalidInput("longitude_deg must be within [-180, 180]".to_string()),
581 ),
582 ] {
583 assert_eq!(
584 terrain
585 .height_m_with_options(lon, lat, DtedLookupOptions::default())
586 .expect_err("out-of-range DTED coordinate must error"),
587 error
588 );
589 }
590
591 assert_eq!(
592 terrain
593 .height_m(-106.5, 36.5)
594 .expect("missing in-range tile keeps sea-level fallback"),
595 0.0
596 );
597 }
598
599 #[test]
600 fn dted_valid_minimum_tile_parses_and_interpolates() {
601 let root = temp_path("dted-valid-minimum");
602 fs::create_dir_all(&root).expect("create temp DTED dir");
603 let tile_path = root.join("n36_w107_1arc_v3.dt2");
604 write_synthetic_dted_tile(&tile_path, 2, 2, |lon_index, lat_index| {
605 match (lon_index, lat_index) {
606 (0, 0) => 10,
607 (0, 1) => 30,
608 (1, 0) => 50,
609 (1, 1) => 70,
610 _ => unreachable!("2x2 synthetic tile"),
611 }
612 });
613
614 DtedTile::from_path(&tile_path).expect("valid 2x2 DTED tile");
615 let mut terrain = DtedTerrain::new(&root);
616 assert_eq!(
617 terrain
618 .height_m_with_options(
619 -106.5,
620 36.5,
621 DtedLookupOptions {
622 interpolation: DtedInterpolation::Bilinear,
623 },
624 )
625 .expect("bilinear height"),
626 40.0
627 );
628
629 fs::remove_dir_all(root).expect("remove temp DTED dir");
630 }
631
632 #[test]
633 fn dted_lookup_matches_generated_fixture_bits() {
634 let raw =
635 std::fs::read_to_string(fixture_path("dted_points.json")).expect("read dted fixture");
636 let doc: Value = serde_json::from_str(&raw).expect("parse dted fixture");
637 assert_eq!(doc["schema"], "gnss-dted-points-v1");
638
639 let mut terrain = DtedTerrain::new(fixture_path("tiles"));
640 let nearest = DtedLookupOptions {
641 interpolation: DtedInterpolation::NearestPosting,
642 };
643 let bilinear = DtedLookupOptions {
644 interpolation: DtedInterpolation::Bilinear,
645 };
646
647 let mut checked = 0usize;
648 for case in doc["nearest_cases"].as_array().expect("nearest_cases") {
649 let lon = bits(&case["longitude_bits"]);
650 let lat = bits(&case["latitude_bits"]);
651 let got = terrain
652 .height_m_with_options(lon, lat, nearest)
653 .expect("nearest DTED height");
654 let want = bits(&case["elevation_bits"]);
655 assert_eq!(
656 got.to_bits(),
657 want.to_bits(),
658 "nearest DTED {},{}",
659 lon,
660 lat
661 );
662 checked += 1;
663 }
664
665 for case in doc["bilinear_cases"].as_array().expect("bilinear_cases") {
666 let lon = bits(&case["longitude_bits"]);
667 let lat = bits(&case["latitude_bits"]);
668 let got = terrain
669 .height_m_with_options(lon, lat, bilinear)
670 .expect("bilinear DTED height");
671 let want = bits(&case["elevation_bits"]);
672 assert_eq!(
673 got.to_bits(),
674 want.to_bits(),
675 "bilinear DTED {},{}",
676 lon,
677 lat
678 );
679 checked += 1;
680 }
681 assert!(checked > 0, "empty DTED fixture");
682 }
683}