vj-sim 0.3.0

//! SV `string` values (LRM 1800-2023 §6.16).
//!
//! A string is stored -- in STATE, a frame slot, or a register -- as a
//! 64-bit id naming an immutable, interned byte string; id 0 is `""`.
//! Interning makes equal contents share one id, so `==`/`!=` (and `case`
//! matching) compare ids; every other operation goes through [`apply`].
//! Interned strings live for the rest of the process (bounded by the number
//! of distinct strings a simulation creates). Each is stored NUL-terminated,
//! so [`c_str`] can hand it to C (DPI, `%s` formatting) without copying.
//!
//! An SV string never contains a NUL character: storing one is ignored
//! (§6.16), which [`intern`] implements by dropping NUL bytes.

use std::collections::HashMap;
use std::sync::{OnceLock, RwLock};

struct Table {
    /// Contents by id, each NUL-terminated.
    by_id: Vec<&'static [u8]>,
    /// id by contents (without the NUL).
    by_bytes: HashMap<&'static [u8], u64>,
}

fn table() -> &'static RwLock<Table> {
    static T: OnceLock<RwLock<Table>> = OnceLock::new();
    T.get_or_init(|| {
        let empty: &'static [u8] = b"\0";
        let mut by_bytes = HashMap::new();
        by_bytes.insert(&empty[..0], 0);
        RwLock::new(Table {
            by_id: vec![empty],
            by_bytes,
        })
    })
}

/// The id of the string `bytes` (NUL bytes dropped).
pub fn intern(bytes: &[u8]) -> u64 {
    let owned;
    let bytes = if bytes.contains(&0) {
        owned = bytes
            .iter()
            .copied()
            .filter(|b| *b != 0)
            .collect::<Vec<u8>>();
        &owned[..]
    } else {
        bytes
    };
    if let Some(&id) = table()
        .read()
        .unwrap_or_else(|e| e.into_inner())
        .by_bytes
        .get(bytes)
    {
        return id;
    }
    let mut t = table().write().unwrap_or_else(|e| e.into_inner());
    if let Some(&id) = t.by_bytes.get(bytes) {
        return id;
    }
    let mut stored = Vec::with_capacity(bytes.len() + 1);
    stored.extend_from_slice(bytes);
    stored.push(0);
    let stored: &'static [u8] = Box::leak(stored.into_boxed_slice());
    let id = t.by_id.len() as u64;
    t.by_id.push(stored);
    t.by_bytes.insert(&stored[..stored.len() - 1], id);
    id
}

/// Every interned string but `""`, in id order (id 1 first): what a design
/// built ahead of time carries so a fresh process can give each string its
/// build-time id ([`preload`]) -- ids are baked into machine code and into
/// the initial values of the design's cells.
pub fn snapshot() -> Vec<Vec<u8>> {
    let t = table().read().unwrap_or_else(|e| e.into_inner());
    t.by_id[1..]
        .iter()
        .map(|s| s[..s.len() - 1].to_vec())
        .collect()
}

/// Makes `strings` (a [`snapshot`]) ids `1..` of this process's table.
///
/// Fails if the table already holds a different string under one of those
/// ids (a process that interned something of its own first); a table that
/// already starts with exactly `strings` is left as it is, so a second call
/// is harmless.
pub fn preload(strings: &[Vec<u8>]) -> Result<(), String> {
    for (i, s) in strings.iter().enumerate() {
        let want = (i + 1) as u64;
        let got = intern(s);
        if got != want {
            return Err(format!(
                "string {want} of the design cannot take its id: this process already \
                 interned `{}` as {got}",
                String::from_utf8_lossy(s)
            ));
        }
    }
    Ok(())
}

/// The contents of string `id` (an unknown id reads as `""`).
pub fn bytes(id: u64) -> &'static [u8] {
    let t = table().read().unwrap_or_else(|e| e.into_inner());
    let s = t.by_id.get(id as usize).copied().unwrap_or(b"\0");
    &s[..s.len() - 1]
}

/// String `id` as a NUL-terminated C string.
pub fn c_str(id: u64) -> *const u8 {
    let t = table().read().unwrap_or_else(|e| e.into_inner());
    t.by_id.get(id as usize).copied().unwrap_or(b"\0").as_ptr()
}

/// A string operation, by the code codegen passes to `sv_rt_str_op`.
#[repr(u32)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum StrOp {
    /// `{a, b}`.
    Concat = 0,
    /// `{b{a}}`.
    Replicate = 1,
    /// `a.len()`.
    Len = 2,
    /// `a.getc(b)` (0 out of range).
    Getc = 3,
    /// `a` with `a.putc(b, c)` applied (unchanged out of range or for 0).
    Putc = 4,
    ToUpper = 5,
    ToLower = 6,
    /// `a.compare(b)`: C `strcmp`'s result.
    Compare = 7,
    /// `a.icompare(b)`: case-insensitive `compare`.
    ICompare = 8,
    /// `a.substr(b, c)` (`""` out of range).
    Substr = 9,
    /// `a.atoi()` / `atohex` / `atooct` / `atobin`: the leading number
    /// (underscores ignored), as a 32-bit integer.
    AToI = 10,
    AToHex = 11,
    AToOct = 12,
    AToBin = 13,
    /// The string of integer `a`: `itoa` (signed decimal of the
    /// `c & 0xff`-bit value, sign-extended when `c & 0x100`), `hextoa`,
    /// `octtoa`, `bintoa`.
    IToA = 14,
    HexToA = 15,
    OctToA = 16,
    BinToA = 17,
    /// The string of the `c`-bit integral value `b:a` (high:low 64 bits):
    /// its bytes, most significant first, NUL bytes dropped (§6.16).
    FromBits = 18,
    /// The low / high 64 bits of string `a` as a `b`-bit integral value
    /// (its last character in the least significant byte).
    ToBitsLo = 19,
    ToBitsHi = 20,
    /// 64-bit word `c` (0 least significant) of string `a` as a `b`-bit
    /// integral value, for any width.
    ToBitsWord = 21,
}

impl StrOp {
    pub fn from_u32(v: u32) -> Option<StrOp> {
        use StrOp::*;
        Some(match v {
            0 => Concat,
            1 => Replicate,
            2 => Len,
            3 => Getc,
            4 => Putc,
            5 => ToUpper,
            6 => ToLower,
            7 => Compare,
            8 => ICompare,
            9 => Substr,
            10 => AToI,
            11 => AToHex,
            12 => AToOct,
            13 => AToBin,
            14 => IToA,
            15 => HexToA,
            16 => OctToA,
            17 => BinToA,
            18 => FromBits,
            19 => ToBitsLo,
            20 => ToBitsHi,
            21 => ToBitsWord,
            _ => return None,
        })
    }
}

/// C `strcmp`'s result (LRM 6.16.8 defines `compare` by it): the
/// difference of the first differing characters, a string's end reading as
/// NUL.
fn strcmp(x: &[u8], y: &[u8]) -> u64 {
    let n = x.len().max(y.len());
    for i in 0..n {
        let (p, q) = (
            i64::from(x.get(i).copied().unwrap_or(0)),
            i64::from(y.get(i).copied().unwrap_or(0)),
        );
        if p != q {
            return (p - q) as u64;
        }
    }
    0
}

/// The leading number of `s` in `radix` (LRM 6.16.9): the scan covers
/// leading digits and `_` characters and stops at any other character, so
/// leading whitespace or a sign ends it at once (the LRM: it "does not
/// parse the full syntax for integer literals (sign, size, apostrophe,
/// base)"); no digits gives zero. Truncated to 32 bits.
fn parse_leading(s: &[u8], radix: u32) -> u64 {
    let mut i = 0;
    let mut v: u64 = 0;
    while i < s.len() {
        let c = s[i];
        if c == b'_' {
            i += 1;
            continue;
        }
        match (c as char).to_digit(radix) {
            Some(d) => v = v.wrapping_mul(u64::from(radix)).wrapping_add(u64::from(d)),
            None => break,
        }
        i += 1;
    }
    // A 32-bit `integer` result, sign-extended into the 64-bit return.
    (v as u32 as i32) as i64 as u64
}

/// Applies `op` to `(a, b, c)` (see [`StrOp`] for each operation's operands
/// and result: a string id or an integer).
pub fn apply(op: StrOp, a: u64, b: u64, c: u64) -> u64 {
    let s = || bytes(a);
    match op {
        StrOp::Concat => {
            let (x, y) = (bytes(a), bytes(b));
            if y.is_empty() {
                return a;
            }
            if x.is_empty() {
                return b;
            }
            intern(&[x, y].concat())
        }
        StrOp::Replicate => intern(&s().repeat(b.min(1 << 24) as usize)),
        StrOp::Len => s().len() as u64,
        StrOp::Getc => s().get(b as usize).copied().map_or(0, u64::from),
        StrOp::Putc => {
            let mut v = s().to_vec();
            match v.get_mut(b as usize) {
                Some(slot) if c as u8 != 0 => {
                    *slot = c as u8;
                    intern(&v)
                }
                _ => a,
            }
        }
        StrOp::ToUpper => intern(&s().to_ascii_uppercase()),
        StrOp::ToLower => intern(&s().to_ascii_lowercase()),
        StrOp::Compare => strcmp(bytes(a), bytes(b)),
        StrOp::ICompare => strcmp(
            &bytes(a).to_ascii_lowercase(),
            &bytes(b).to_ascii_lowercase(),
        ),
        StrOp::Substr => {
            let v = s();
            let (i, j) = (b as i64, c as i64);
            if i < 0 || j < i || j as usize >= v.len() {
                0
            } else {
                intern(&v[i as usize..=j as usize])
            }
        }
        StrOp::AToI => parse_leading(s(), 10),
        StrOp::AToHex => parse_leading(s(), 16),
        StrOp::AToOct => parse_leading(s(), 8),
        StrOp::AToBin => parse_leading(s(), 2),
        StrOp::IToA | StrOp::HexToA | StrOp::OctToA | StrOp::BinToA => {
            let width = (c & 0xff) as u32;
            let signed = c & 0x100 != 0;
            let mask = if width >= 64 {
                u64::MAX
            } else {
                (1u64 << width) - 1
            };
            let v = a & mask;
            // A negative signed value prints as `-` and its magnitude in
            // the method's radix (itoa's §6.16.x rule, which the LRM
            // leaves implicit for hextoa/octtoa/bintoa; iverilog and the
            // ivtest `sv_string6` agree).
            let negative = signed && width > 0 && (v >> (width - 1)) & 1 == 1;
            let (sign, mag) = if negative {
                ("-", (v | !mask).wrapping_neg())
            } else {
                ("", v)
            };
            let text = match op {
                StrOp::IToA => format!("{sign}{mag}"),
                StrOp::HexToA => format!("{sign}{mag:x}"),
                StrOp::OctToA => format!("{sign}{mag:o}"),
                _ => format!("{sign}{mag:b}"),
            };
            intern(text.as_bytes())
        }
        StrOp::FromBits => {
            let width = c.min(128) as u32;
            let v = (u128::from(b) << 64) | u128::from(a);
            let v = if width >= 128 {
                v
            } else {
                v & ((1u128 << width) - 1)
            };
            let n = width.div_ceil(8);
            let out: Vec<u8> = (0..n)
                .rev()
                .map(|k| (v >> (8 * k)) as u8)
                .filter(|byte| *byte != 0)
                .collect();
            intern(&out)
        }
        StrOp::ToBitsWord => {
            // The last character is the least significant byte.
            let rev: Vec<u8> = s().iter().rev().copied().collect();
            let (width, k) = (b, c);
            let mut w: u64 = 0;
            for j in 0..8u64 {
                let byte = u64::from(rev.get((8 * k + j) as usize).copied().unwrap_or(0));
                w |= byte << (8 * j);
            }
            let lo = 64 * k;
            if lo >= width {
                0
            } else if width - lo < 64 {
                w & ((1u64 << (width - lo)) - 1)
            } else {
                w
            }
        }
        StrOp::ToBitsLo | StrOp::ToBitsHi => {
            let width = b.min(128) as u32;
            let mut v: u128 = 0;
            for byte in s() {
                v = (v << 8) | u128::from(*byte);
            }
            let v = if width >= 128 {
                v
            } else {
                v & ((1u128 << width) - 1)
            };
            if op == StrOp::ToBitsLo {
                v as u64
            } else {
                (v >> 64) as u64
            }
        }
    }
}

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

    #[test]
    fn interning_gives_equal_contents_one_id() {
        assert_eq!(intern(b""), 0);
        let a = intern(b"hello");
        assert_eq!(intern(b"hello"), a);
        assert_ne!(intern(b"hellO"), a);
        assert_eq!(bytes(a), b"hello");
        assert_eq!(intern(b"a\0b"), intern(b"ab"), "NUL characters are dropped");
    }

    #[test]
    fn operations_follow_lrm_6_16() {
        let hi = intern(b"Hello");
        assert_eq!(
            bytes(apply(StrOp::Concat, hi, intern(b" W"), 0)),
            b"Hello W"
        );
        assert_eq!(apply(StrOp::Len, hi, 0, 0), 5);
        assert_eq!(apply(StrOp::Getc, hi, 1, 0), u64::from(b'e'));
        assert_eq!(apply(StrOp::Getc, hi, 9, 0), 0);
        assert_eq!(bytes(apply(StrOp::Putc, hi, 0, u64::from(b'J'))), b"Jello");
        assert_eq!(
            apply(StrOp::Putc, hi, 0, 0),
            hi,
            "putc of 0 changes nothing"
        );
        assert_eq!(bytes(apply(StrOp::ToUpper, hi, 0, 0)), b"HELLO");
        assert_eq!(
            apply(StrOp::Compare, intern(b"a"), intern(b"b"), 0) as i64,
            -1
        );
        assert_eq!(apply(StrOp::ICompare, intern(b"ABC"), intern(b"abc"), 0), 0);
        assert_eq!(bytes(apply(StrOp::Substr, hi, 1, 3)), b"ell");
        assert_eq!(apply(StrOp::Substr, hi, 3, 9), 0);
        assert_eq!(apply(StrOp::AToI, intern(b"1_234x"), 0, 0) as i64, 1234);
        // LRM 6.16.9: whitespace and a sign end the scan before any digit.
        assert_eq!(apply(StrOp::AToI, intern(b" 12"), 0, 0), 0);
        assert_eq!(apply(StrOp::AToI, intern(b"-5"), 0, 0), 0);
        assert_eq!(apply(StrOp::AToHex, intern(b"ff_zz"), 0, 0), 255);
        assert_eq!(
            bytes(apply(StrOp::IToA, (-5i64) as u64, 0, 32 | 0x100)),
            b"-5"
        );
        assert_eq!(bytes(apply(StrOp::HexToA, 255, 0, 32)), b"ff");
        assert_eq!(bytes(apply(StrOp::FromBits, 0x4142, 0, 32)), b"AB");
        assert_eq!(apply(StrOp::ToBitsLo, intern(b"AB"), 16, 0), 0x4142);
        assert_eq!(apply(StrOp::ToBitsLo, intern(b"ABC"), 16, 0), 0x4243);
        let long = intern(b"0123456789ABCDEFGH");
        assert_eq!(
            apply(StrOp::ToBitsWord, long, 144, 0),
            u64::from_be_bytes(*b"ABCDEFGH")
        );
        assert_eq!(apply(StrOp::ToBitsWord, long, 144, 2), 0x3031);
        assert_eq!(apply(StrOp::ToBitsWord, long, 140, 2), 0x031);
    }
}