powerio-tx 0.10.0

//! Read substation coordinates from PowerWorld `.pwd` display files
//! (read only).
//!
//! A `.pwd` contains drawing records associated with a case: buses,
//! branches, substations, and field labels. This reader decodes the one
//! subset with a differential oracle, the substation symbols, and leaves
//! every other drawing object undecoded. Files without the substation table
//! still return display metadata with an empty substation list. The evidence
//! (seven files across
//! the 2016 through 2022 writer eras, each matched 1-1 against the
//! latitude/longitude its same vintage aux carries per substation, except
//! the v19 resave, which matches 1248/1250 against the published case
//! across a vintage skew) is in
//! `powerio/src/format/powerworld/FORMAT.md`.
//!
//! Two structures carry the data, both present in every probed save:
//!
//! - The substation identity table, behind the only `ff ff ff ff 3d 0f`
//!   byte sequence in the file (sentinel plus table tag 0x0f3d): records of
//!   `u32 number, u32 number (exact duplicate), u32 length, name, 0x02`,
//!   terminated exactly by the next `ff ff ff ff`. The order is display
//!   order, not case order.
//! - The DisplaySubstation drawing records: each repeats the file's header
//!   stamp (the u32 at offset 22) at +18, stores the position as f64 x/y at
//!   +22/+30 with an f32 echo of both at +2/+6, and links its substation
//!   number behind a marker byte (0x03 or 0x07 by writer era) in the style
//!   tail. The record's type tag (the u16 at +0) varies per save, so the
//!   reader keys on this structure instead: stamp echo, dual encoded
//!   coordinates, and a link to every identity row in table order. Decoy
//!   groups exist (field label records with the same count and plausible
//!   coordinates) and fail the link gauntlet; if more than one group ever
//!   passes, the reader rejects rather than guesses.
//!
//! The coordinates are diagram positions (y north positive), not
//! geography: no probed file stores latitude or longitude directly. The
//! auto generated TAMU and Hawaii layouts equal a Mercator projection
//! (`x = k * longitude`, `y = k * merc(latitude)`, k = 535.81608... on the
//! never edited Hawaii40 file, bit exact), but hand moved symbols and the
//! June 2016 era deviate, so the values are exposed as stored and any
//! projection is the consumer's choice. Consumers wanting geography should
//! read the aux.

use std::collections::{BTreeMap, HashSet};
use std::path::Path;

use crate::{Error, Result};

const FMT: &str = "PowerWorld .pwd";

/// The identity table tag behind the `ff ff ff ff` sentinel.
const IDENTITY_TAG: [u8; 6] = [0xff, 0xff, 0xff, 0xff, 0x3d, 0x0f];

/// Cap on identity record steps across every anchor in one parse. A step is one
/// record examined; each consumes at least 13 bytes, so the largest real table
/// is far below this. Bounds the anchors × records blowup a crafted file could
/// otherwise force. Matches the probe-budget idiom of the `.pwb` reader.
const IDENTITY_WALK_BUDGET: u64 = 128_000_000;

/// Cap on identity rows retained across every candidate walk in one parse.
/// The step budget above bounds the reader's *work*; this bounds what a
/// densely packed file can make it *hold*: each retained row owns a name
/// String, so without a retention cap a GB-scale file of valid-looking
/// records could drive several GB of held rows before the walk finishes
/// (#274). The vendored ACTIVSg200 display retains 200 rows; a display for
/// the largest interconnection-scale case stays in the tens of thousands, so
/// one million rows and 64 MiB of name bytes are far above any real layout
/// while capping amplification near the input's own size. Exceeding either
/// is a coded refusal, never a silent omission.
const IDENTITY_ROW_BUDGET: usize = 1_000_000;
const IDENTITY_NAME_BYTE_BUDGET: usize = 64 << 20;

/// One substation symbol from a display file: the identity row joined with
/// its drawing record, in identity table (display) order. `x` and `y` are
/// diagram coordinates as stored, y north positive (see the module docs).
#[derive(Debug, Clone, PartialEq)]
pub struct PwdSubstation {
    pub number: u32,
    pub name: String,
    pub x: f64,
    pub y: f64,
}

/// Decoded PowerWorld display file content.
///
/// A `.pwd` is not a case file and does not carry a [`BalancedNetwork`](crate::BalancedNetwork).
/// This structure exposes the display metadata the reader validates plus the
/// supported drawing object subset.
#[derive(Debug, Clone, PartialEq)]
pub struct PwdDisplay {
    pub canvas_width: u16,
    pub canvas_height: u16,
    pub stamp: u32,
    pub substations: Vec<PwdSubstation>,
}

/// Read and parse a `.pwd` display file.
///
/// # Errors
/// [`Error::Io`] when the file cannot be read, or [`Error::FormatRead`] when
/// the display bytes are not a supported PowerWorld `.pwd` shape.
pub fn parse_pwd_file(path: impl AsRef<Path>) -> Result<PwdDisplay> {
    let bytes = std::fs::read(path)?;
    parse_pwd_display(&bytes)
}

/// Parse a `.pwd` display file, returning metadata and decoded substations.
///
/// # Errors
/// [`Error::FormatRead`] when the header is not the known display shape,
/// or no unique drawing record group links to the identity rows.
pub fn parse_pwd_display(bytes: &[u8]) -> Result<PwdDisplay> {
    parse_pwd_inner(bytes)
}

/// Parse the substation coordinates out of `.pwd` bytes.
///
/// # Errors
/// [`Error::FormatRead`] when the header is not the known display shape,
/// or no unique drawing record group links to the identity rows.
pub fn parse_pwd(bytes: &[u8]) -> Result<Vec<PwdSubstation>> {
    parse_pwd_display(bytes).map(|display| display.substations)
}

fn pwd_err(message: impl Into<String>) -> Error {
    Error::FormatRead {
        format: FMT,
        message: message.into(),
    }
}

fn parse_pwd_header(bytes: &[u8]) -> Result<(u16, u16, u32)> {
    let (Some(header), Some(canvas_width), Some(canvas_height)) =
        (u32_at(bytes, 0), u16_at(bytes, 4), u16_at(bytes, 6))
    else {
        let header = u32_at(bytes, 0).unwrap_or(0);
        return Err(pwd_err(format!(
            "not a recognized PowerWorld display file (header word {header}; the probed saves all \
             carry 50)",
        )));
    };
    if bytes.len() < 0x40 || header != 50 {
        return Err(pwd_err(format!(
            "not a recognized PowerWorld display file (header word {header}; the probed saves all \
             carry 50)",
        )));
    }
    if canvas_width == 0 || canvas_height == 0 {
        return Err(pwd_err("display header canvas dimensions are zero"));
    }
    let stamp = u32_at(bytes, 22).unwrap_or(0);
    if stamp == 0 {
        return Err(pwd_err(
            "display header stamp is zero; every validated save carries a nonzero stamp the \
             drawing records repeat",
        ));
    }
    Ok((canvas_width, canvas_height, stamp))
}

fn parse_pwd_inner(bytes: &[u8]) -> Result<PwdDisplay> {
    let (canvas_width, canvas_height, stamp) = parse_pwd_header(bytes)?;

    let identity = find_identity_table(bytes)?;
    if identity.is_empty() {
        return Ok(PwdDisplay {
            canvas_width,
            canvas_height,
            stamp,
            substations: Vec::new(),
        });
    }

    // Every drawing object record repeats the header stamp at +18 and dual
    // encodes its position (f64 at +22/+30, f32 echo at +2/+6); the scan
    // collects every offset with that shape and groups by the u16 type tag.
    // Keyed by type tag so grouping is O(log tags) per record: a crafted file
    // can spread gate-passing records across up to 65536 distinct tags, and a
    // linear scan per record would be quadratic in the file size.
    let mut groups: BTreeMap<u16, Vec<DrawRecord>> = BTreeMap::new();
    for i in 0..bytes.len().saturating_sub(38) {
        if u32_at(bytes, i + 18) != Some(stamp) {
            continue;
        }
        let (Some(x), Some(y)) = (f64_at(bytes, i + 22), f64_at(bytes, i + 30)) else {
            continue;
        };
        if !x.is_finite() || !y.is_finite() {
            continue;
        }
        #[allow(clippy::cast_possible_truncation)] // the echo is the f32 rounding by design
        let (rx, ry) = (x as f32, y as f32);
        // Bit equality: the magnitude gate below excludes zero, so the only
        // value the echo can hold is the rounded f64 itself.
        if f32_at(bytes, i + 2).map(f32::to_bits) != Some(rx.to_bits())
            || f32_at(bytes, i + 6).map(f32::to_bits) != Some(ry.to_bits())
        {
            continue;
        }
        let magnitude = x.abs().max(y.abs());
        if !(1.0..1.0e7).contains(&magnitude) {
            continue;
        }
        let Some(tag) = u16_at(bytes, i) else {
            continue;
        };
        let rec = DrawRecord { at: i, x, y };
        groups.entry(tag).or_default().push(rec);
    }

    // The substation group is the one whose records, in stream order, link
    // every identity row in table order: a marker byte (0x03 or 0x07 by
    // era) followed by the row's u32 number, somewhere in the style tail.
    // Field label decoys carry other markers (0x05 observed) or another
    // order and fail; ambiguity is a loud error, never a pick.
    let matches: Vec<(&u16, &Vec<DrawRecord>)> = groups
        .iter()
        .filter(|(_, records)| {
            records.len() == identity.len()
                && records
                    .iter()
                    .zip(&identity)
                    .all(|(rec, (number, _))| links_number(bytes, rec.at, *number))
        })
        .collect();
    let (_, records) = match matches.as_slice() {
        [one] => *one,
        [] => {
            return Err(pwd_err(format!(
                "no drawing record group links the {} substation identity rows; the \
                 DisplaySubstation layout of this save is not the validated one",
                identity.len()
            )));
        }
        several => {
            return Err(pwd_err(format!(
                "{} drawing record groups link the substation identity rows; refusing to guess \
                 between them",
                several.len()
            )));
        }
    };

    let substations = records
        .iter()
        .zip(identity)
        .map(|(rec, (number, name))| PwdSubstation {
            number,
            name,
            x: rec.x,
            y: rec.y,
        })
        .collect();
    Ok(PwdDisplay {
        canvas_width,
        canvas_height,
        stamp,
        substations,
    })
}

/// A drawing record that passed the shape gate: its stream offset (for the
/// identity link check) and the decoded coordinates, kept so the final mapping
/// never re-reads the bytes.
struct DrawRecord {
    at: usize,
    x: f64,
    y: f64,
}

/// The substation identity table: exactly one valid walk behind a
/// `ff ff ff ff 3d 0f` anchor. A missing table means there are no decoded
/// substation symbols. Several tables are a loud error.
fn find_identity_table(b: &[u8]) -> Result<Vec<(u32, String)>> {
    // A crafted file can plant many IDENTITY_TAG anchors, each starting a walk
    // that runs to a sentinel, so the total work is anchors × records. One
    // shared budget over every record step across every anchor keeps that
    // bounded; the largest real identity table is orders of magnitude below it.
    let mut budget = 0u64;
    let mut retained = Retention::default();
    let mut tables = Vec::new();
    for at in memmem(b, &IDENTITY_TAG) {
        if let Some(rows) = identity_walk(b, at + IDENTITY_TAG.len(), &mut budget, &mut retained) {
            tables.push(rows);
        }
        if budget > IDENTITY_WALK_BUDGET {
            return Err(Error::FormatRead {
                format: FMT,
                message: "substation identity search exceeded its probe budget; the file is \
                          not a decodable DisplaySubstation layout"
                    .into(),
            });
        }
        if retained.exceeded {
            return Err(Error::FormatRead {
                format: FMT,
                message: "substation identity search exceeded its retention budget; the file \
                          packs more identity rows than any decodable DisplaySubstation \
                          layout states"
                    .into(),
            });
        }
    }
    match tables.len() {
        1 => Ok(tables.pop().unwrap()),
        0 => Ok(Vec::new()),
        n => Err(Error::FormatRead {
            format: FMT,
            message: format!(
                "{n} byte ranges walk as a substation identity table; refusing to guess \
                 between them"
            ),
        }),
    }
}

/// Walk identity records (`u32 number, u32 duplicate, u32 length, name,
/// 0x02`) from `at` until the next `ff ff ff ff` sentinel, which must
/// arrive exactly at a record boundary. At least one record, numbers
/// unique and plausible, names printable.
/// Rows and name bytes retained across every walk of one parse, with the
/// flag that turns exhaustion into the coded refusal rather than a silently
/// shorter table (#274).
#[derive(Default)]
struct Retention {
    rows: usize,
    name_bytes: usize,
    exceeded: bool,
}

fn identity_walk(
    b: &[u8],
    mut at: usize,
    budget: &mut u64,
    retained: &mut Retention,
) -> Option<Vec<(u32, String)>> {
    let mut rows = Vec::new();
    let mut seen = HashSet::new();
    loop {
        // One record step; abandon the walk once the shared budget is spent so
        // a file packed with anchors cannot force quadratic work.
        *budget = budget.saturating_add(1);
        if *budget > IDENTITY_WALK_BUDGET {
            return None;
        }
        if b.get(at..).and_then(|s| s.get(..4)) == Some([0xff; 4].as_slice()) {
            return (!rows.is_empty()).then_some(rows);
        }
        let number = u32_at(b, at)?;
        let duplicate_at = at.checked_add(4)?;
        if number == 0 || number > 99_999_999 || u32_at(b, duplicate_at) != Some(number) {
            return None;
        }
        let len_at = at.checked_add(8)?;
        let len = u32_at(b, len_at)? as usize;
        if len == 0 || len >= 64 {
            return None;
        }
        let name_start = at.checked_add(12)?;
        let name_end = name_start.checked_add(len)?;
        let name = b.get(name_start..name_end)?;
        if !name.iter().all(|&c| (0x20..0x7f).contains(&c)) || b.get(name_end) != Some(&0x02) {
            return None;
        }
        if !seen.insert(number) {
            return None;
        }
        retained.rows += 1;
        retained.name_bytes += name.len();
        if retained.rows > IDENTITY_ROW_BUDGET || retained.name_bytes > IDENTITY_NAME_BYTE_BUDGET {
            retained.exceeded = true;
            return None;
        }
        rows.push((number, String::from_utf8_lossy(name).into_owned()));
        at = name_end.checked_add(1)?;
    }
}

/// Whether the drawing record at `i` links `number`: a marker byte 0x03 or
/// 0x07 (the substation symbol markers of the two observed eras) directly
/// followed by the number, inside the style tail window. The window is
/// variable because a digit string of 1 to 4 characters precedes the link
/// in some saves.
fn links_number(b: &[u8], i: usize, number: u32) -> bool {
    (40..140).any(|d| {
        let Some(marker_at) = i.checked_add(d) else {
            return false;
        };
        let Some(number_at) = marker_at.checked_add(1) else {
            return false;
        };
        matches!(b.get(marker_at), Some(0x03 | 0x07)) && u32_at(b, number_at) == Some(number)
    })
}

/// Every start of `needle` in `haystack`.
fn memmem<'a>(haystack: &'a [u8], needle: &'a [u8]) -> impl Iterator<Item = usize> + 'a {
    haystack
        .windows(needle.len())
        .enumerate()
        .filter_map(move |(i, w)| (w == needle).then_some(i))
}

// Total little endian reads: `None` past the end of the buffer, no index
// arithmetic that can panic or wrap. Every offset in this reader derives
// from untrusted file bytes, so the accessors carry the bounds check.

fn u16_at(b: &[u8], i: usize) -> Option<u16> {
    Some(u16::from_le_bytes(*b.get(i..)?.first_chunk()?))
}

fn u32_at(b: &[u8], i: usize) -> Option<u32> {
    Some(u32::from_le_bytes(*b.get(i..)?.first_chunk()?))
}

fn f32_at(b: &[u8], i: usize) -> Option<f32> {
    Some(f32::from_le_bytes(*b.get(i..)?.first_chunk()?))
}

fn f64_at(b: &[u8], i: usize) -> Option<f64> {
    Some(f64::from_le_bytes(*b.get(i..)?.first_chunk()?))
}

#[cfg(test)]
mod retention_tests {
    use super::*;

    /// #274: the retention budget refuses a file densely packed with valid
    /// identity rows, with a coded error rather than a silently shorter
    /// table or GB-scale held rows.
    #[test]
    fn packed_identity_rows_hit_the_retention_budget() {
        // Header word 50, nonzero canvas, then one anchor followed by more
        // valid-looking rows than any decodable layout states.
        let mut b = vec![0u8; 0x40];
        b[0] = 50;
        b[4] = 1; // canvas width
        b[6] = 1; // canvas height
        b[22] = 7; // nonzero stamp
        b.extend_from_slice(&IDENTITY_TAG);
        let name = b"S";
        for number in 1..=(IDENTITY_ROW_BUDGET as u32 + 2) {
            b.extend_from_slice(&number.to_le_bytes());
            b.extend_from_slice(&number.to_le_bytes());
            b.extend_from_slice(&(name.len() as u32).to_le_bytes());
            b.extend_from_slice(name);
            b.push(0x02);
        }
        b.extend_from_slice(&[0xff; 4]);
        let error = parse_pwd(&b).unwrap_err().to_string();
        assert!(error.contains("retention budget"), "{error}");
    }
}