vj_sim/
strings.rs

1//! SV `string` values (LRM 1800-2023 §6.16).
2//!
3//! A string is stored -- in STATE, a frame slot, or a register -- as a
4//! 64-bit id naming an immutable, interned byte string; id 0 is `""`.
5//! Interning makes equal contents share one id, so `==`/`!=` (and `case`
6//! matching) compare ids; every other operation goes through [`apply`].
7//! Interned strings live for the rest of the process (bounded by the number
8//! of distinct strings a simulation creates). Each is stored NUL-terminated,
9//! so [`c_str`] can hand it to C (DPI, `%s` formatting) without copying.
10//!
11//! An SV string never contains a NUL character: storing one is ignored
12//! (§6.16), which [`intern`] implements by dropping NUL bytes.
13
14use std::collections::HashMap;
15use std::sync::{OnceLock, RwLock};
16
17struct Table {
18    /// Contents by id, each NUL-terminated.
19    by_id: Vec<&'static [u8]>,
20    /// id by contents (without the NUL).
21    by_bytes: HashMap<&'static [u8], u64>,
22}
23
24fn table() -> &'static RwLock<Table> {
25    static T: OnceLock<RwLock<Table>> = OnceLock::new();
26    T.get_or_init(|| {
27        let empty: &'static [u8] = b"\0";
28        let mut by_bytes = HashMap::new();
29        by_bytes.insert(&empty[..0], 0);
30        RwLock::new(Table {
31            by_id: vec![empty],
32            by_bytes,
33        })
34    })
35}
36
37/// The id of the string `bytes` (NUL bytes dropped).
38pub fn intern(bytes: &[u8]) -> u64 {
39    let owned;
40    let bytes = if bytes.contains(&0) {
41        owned = bytes
42            .iter()
43            .copied()
44            .filter(|b| *b != 0)
45            .collect::<Vec<u8>>();
46        &owned[..]
47    } else {
48        bytes
49    };
50    if let Some(&id) = table()
51        .read()
52        .unwrap_or_else(|e| e.into_inner())
53        .by_bytes
54        .get(bytes)
55    {
56        return id;
57    }
58    let mut t = table().write().unwrap_or_else(|e| e.into_inner());
59    if let Some(&id) = t.by_bytes.get(bytes) {
60        return id;
61    }
62    let mut stored = Vec::with_capacity(bytes.len() + 1);
63    stored.extend_from_slice(bytes);
64    stored.push(0);
65    let stored: &'static [u8] = Box::leak(stored.into_boxed_slice());
66    let id = t.by_id.len() as u64;
67    t.by_id.push(stored);
68    t.by_bytes.insert(&stored[..stored.len() - 1], id);
69    id
70}
71
72/// Every interned string but `""`, in id order (id 1 first): what a design
73/// built ahead of time carries so a fresh process can give each string its
74/// build-time id ([`preload`]) -- ids are baked into machine code and into
75/// the initial values of the design's cells.
76pub fn snapshot() -> Vec<Vec<u8>> {
77    let t = table().read().unwrap_or_else(|e| e.into_inner());
78    t.by_id[1..]
79        .iter()
80        .map(|s| s[..s.len() - 1].to_vec())
81        .collect()
82}
83
84/// Makes `strings` (a [`snapshot`]) ids `1..` of this process's table.
85///
86/// Fails if the table already holds a different string under one of those
87/// ids (a process that interned something of its own first); a table that
88/// already starts with exactly `strings` is left as it is, so a second call
89/// is harmless.
90pub fn preload(strings: &[Vec<u8>]) -> Result<(), String> {
91    for (i, s) in strings.iter().enumerate() {
92        let want = (i + 1) as u64;
93        let got = intern(s);
94        if got != want {
95            return Err(format!(
96                "string {want} of the design cannot take its id: this process already \
97                 interned `{}` as {got}",
98                String::from_utf8_lossy(s)
99            ));
100        }
101    }
102    Ok(())
103}
104
105/// The contents of string `id` (an unknown id reads as `""`).
106pub fn bytes(id: u64) -> &'static [u8] {
107    let t = table().read().unwrap_or_else(|e| e.into_inner());
108    let s = t.by_id.get(id as usize).copied().unwrap_or(b"\0");
109    &s[..s.len() - 1]
110}
111
112/// String `id` as a NUL-terminated C string.
113pub fn c_str(id: u64) -> *const u8 {
114    let t = table().read().unwrap_or_else(|e| e.into_inner());
115    t.by_id.get(id as usize).copied().unwrap_or(b"\0").as_ptr()
116}
117
118/// A string operation, by the code codegen passes to `sv_rt_str_op`.
119#[repr(u32)]
120#[derive(Debug, Clone, Copy, PartialEq, Eq)]
121pub enum StrOp {
122    /// `{a, b}`.
123    Concat = 0,
124    /// `{b{a}}`.
125    Replicate = 1,
126    /// `a.len()`.
127    Len = 2,
128    /// `a.getc(b)` (0 out of range).
129    Getc = 3,
130    /// `a` with `a.putc(b, c)` applied (unchanged out of range or for 0).
131    Putc = 4,
132    ToUpper = 5,
133    ToLower = 6,
134    /// `a.compare(b)`: C `strcmp`'s result.
135    Compare = 7,
136    /// `a.icompare(b)`: case-insensitive `compare`.
137    ICompare = 8,
138    /// `a.substr(b, c)` (`""` out of range).
139    Substr = 9,
140    /// `a.atoi()` / `atohex` / `atooct` / `atobin`: the leading number
141    /// (underscores ignored), as a 32-bit integer.
142    AToI = 10,
143    AToHex = 11,
144    AToOct = 12,
145    AToBin = 13,
146    /// The string of integer `a`: `itoa` (signed decimal of the
147    /// `c & 0xff`-bit value, sign-extended when `c & 0x100`), `hextoa`,
148    /// `octtoa`, `bintoa`.
149    IToA = 14,
150    HexToA = 15,
151    OctToA = 16,
152    BinToA = 17,
153    /// The string of the `c`-bit integral value `b:a` (high:low 64 bits):
154    /// its bytes, most significant first, NUL bytes dropped (§6.16).
155    FromBits = 18,
156    /// The low / high 64 bits of string `a` as a `b`-bit integral value
157    /// (its last character in the least significant byte).
158    ToBitsLo = 19,
159    ToBitsHi = 20,
160    /// 64-bit word `c` (0 least significant) of string `a` as a `b`-bit
161    /// integral value, for any width.
162    ToBitsWord = 21,
163}
164
165impl StrOp {
166    pub fn from_u32(v: u32) -> Option<StrOp> {
167        use StrOp::*;
168        Some(match v {
169            0 => Concat,
170            1 => Replicate,
171            2 => Len,
172            3 => Getc,
173            4 => Putc,
174            5 => ToUpper,
175            6 => ToLower,
176            7 => Compare,
177            8 => ICompare,
178            9 => Substr,
179            10 => AToI,
180            11 => AToHex,
181            12 => AToOct,
182            13 => AToBin,
183            14 => IToA,
184            15 => HexToA,
185            16 => OctToA,
186            17 => BinToA,
187            18 => FromBits,
188            19 => ToBitsLo,
189            20 => ToBitsHi,
190            21 => ToBitsWord,
191            _ => return None,
192        })
193    }
194}
195
196/// C `strcmp`'s result (LRM 6.16.8 defines `compare` by it): the
197/// difference of the first differing characters, a string's end reading as
198/// NUL.
199fn strcmp(x: &[u8], y: &[u8]) -> u64 {
200    let n = x.len().max(y.len());
201    for i in 0..n {
202        let (p, q) = (
203            i64::from(x.get(i).copied().unwrap_or(0)),
204            i64::from(y.get(i).copied().unwrap_or(0)),
205        );
206        if p != q {
207            return (p - q) as u64;
208        }
209    }
210    0
211}
212
213/// The leading number of `s` in `radix` (LRM 6.16.9): the scan covers
214/// leading digits and `_` characters and stops at any other character, so
215/// leading whitespace or a sign ends it at once (the LRM: it "does not
216/// parse the full syntax for integer literals (sign, size, apostrophe,
217/// base)"); no digits gives zero. Truncated to 32 bits.
218fn parse_leading(s: &[u8], radix: u32) -> u64 {
219    let mut i = 0;
220    let mut v: u64 = 0;
221    while i < s.len() {
222        let c = s[i];
223        if c == b'_' {
224            i += 1;
225            continue;
226        }
227        match (c as char).to_digit(radix) {
228            Some(d) => v = v.wrapping_mul(u64::from(radix)).wrapping_add(u64::from(d)),
229            None => break,
230        }
231        i += 1;
232    }
233    // A 32-bit `integer` result, sign-extended into the 64-bit return.
234    (v as u32 as i32) as i64 as u64
235}
236
237/// Applies `op` to `(a, b, c)` (see [`StrOp`] for each operation's operands
238/// and result: a string id or an integer).
239pub fn apply(op: StrOp, a: u64, b: u64, c: u64) -> u64 {
240    let s = || bytes(a);
241    match op {
242        StrOp::Concat => {
243            let (x, y) = (bytes(a), bytes(b));
244            if y.is_empty() {
245                return a;
246            }
247            if x.is_empty() {
248                return b;
249            }
250            intern(&[x, y].concat())
251        }
252        StrOp::Replicate => intern(&s().repeat(b.min(1 << 24) as usize)),
253        StrOp::Len => s().len() as u64,
254        StrOp::Getc => s().get(b as usize).copied().map_or(0, u64::from),
255        StrOp::Putc => {
256            let mut v = s().to_vec();
257            match v.get_mut(b as usize) {
258                Some(slot) if c as u8 != 0 => {
259                    *slot = c as u8;
260                    intern(&v)
261                }
262                _ => a,
263            }
264        }
265        StrOp::ToUpper => intern(&s().to_ascii_uppercase()),
266        StrOp::ToLower => intern(&s().to_ascii_lowercase()),
267        StrOp::Compare => strcmp(bytes(a), bytes(b)),
268        StrOp::ICompare => strcmp(
269            &bytes(a).to_ascii_lowercase(),
270            &bytes(b).to_ascii_lowercase(),
271        ),
272        StrOp::Substr => {
273            let v = s();
274            let (i, j) = (b as i64, c as i64);
275            if i < 0 || j < i || j as usize >= v.len() {
276                0
277            } else {
278                intern(&v[i as usize..=j as usize])
279            }
280        }
281        StrOp::AToI => parse_leading(s(), 10),
282        StrOp::AToHex => parse_leading(s(), 16),
283        StrOp::AToOct => parse_leading(s(), 8),
284        StrOp::AToBin => parse_leading(s(), 2),
285        StrOp::IToA | StrOp::HexToA | StrOp::OctToA | StrOp::BinToA => {
286            let width = (c & 0xff) as u32;
287            let signed = c & 0x100 != 0;
288            let mask = if width >= 64 {
289                u64::MAX
290            } else {
291                (1u64 << width) - 1
292            };
293            let v = a & mask;
294            // A negative signed value prints as `-` and its magnitude in
295            // the method's radix (itoa's §6.16.x rule, which the LRM
296            // leaves implicit for hextoa/octtoa/bintoa; iverilog and the
297            // ivtest `sv_string6` agree).
298            let negative = signed && width > 0 && (v >> (width - 1)) & 1 == 1;
299            let (sign, mag) = if negative {
300                ("-", (v | !mask).wrapping_neg())
301            } else {
302                ("", v)
303            };
304            let text = match op {
305                StrOp::IToA => format!("{sign}{mag}"),
306                StrOp::HexToA => format!("{sign}{mag:x}"),
307                StrOp::OctToA => format!("{sign}{mag:o}"),
308                _ => format!("{sign}{mag:b}"),
309            };
310            intern(text.as_bytes())
311        }
312        StrOp::FromBits => {
313            let width = c.min(128) as u32;
314            let v = (u128::from(b) << 64) | u128::from(a);
315            let v = if width >= 128 {
316                v
317            } else {
318                v & ((1u128 << width) - 1)
319            };
320            let n = width.div_ceil(8);
321            let out: Vec<u8> = (0..n)
322                .rev()
323                .map(|k| (v >> (8 * k)) as u8)
324                .filter(|byte| *byte != 0)
325                .collect();
326            intern(&out)
327        }
328        StrOp::ToBitsWord => {
329            // The last character is the least significant byte.
330            let rev: Vec<u8> = s().iter().rev().copied().collect();
331            let (width, k) = (b, c);
332            let mut w: u64 = 0;
333            for j in 0..8u64 {
334                let byte = u64::from(rev.get((8 * k + j) as usize).copied().unwrap_or(0));
335                w |= byte << (8 * j);
336            }
337            let lo = 64 * k;
338            if lo >= width {
339                0
340            } else if width - lo < 64 {
341                w & ((1u64 << (width - lo)) - 1)
342            } else {
343                w
344            }
345        }
346        StrOp::ToBitsLo | StrOp::ToBitsHi => {
347            let width = b.min(128) as u32;
348            let mut v: u128 = 0;
349            for byte in s() {
350                v = (v << 8) | u128::from(*byte);
351            }
352            let v = if width >= 128 {
353                v
354            } else {
355                v & ((1u128 << width) - 1)
356            };
357            if op == StrOp::ToBitsLo {
358                v as u64
359            } else {
360                (v >> 64) as u64
361            }
362        }
363    }
364}
365
366#[cfg(test)]
367mod tests {
368    use super::*;
369
370    #[test]
371    fn interning_gives_equal_contents_one_id() {
372        assert_eq!(intern(b""), 0);
373        let a = intern(b"hello");
374        assert_eq!(intern(b"hello"), a);
375        assert_ne!(intern(b"hellO"), a);
376        assert_eq!(bytes(a), b"hello");
377        assert_eq!(intern(b"a\0b"), intern(b"ab"), "NUL characters are dropped");
378    }
379
380    #[test]
381    fn operations_follow_lrm_6_16() {
382        let hi = intern(b"Hello");
383        assert_eq!(
384            bytes(apply(StrOp::Concat, hi, intern(b" W"), 0)),
385            b"Hello W"
386        );
387        assert_eq!(apply(StrOp::Len, hi, 0, 0), 5);
388        assert_eq!(apply(StrOp::Getc, hi, 1, 0), u64::from(b'e'));
389        assert_eq!(apply(StrOp::Getc, hi, 9, 0), 0);
390        assert_eq!(bytes(apply(StrOp::Putc, hi, 0, u64::from(b'J'))), b"Jello");
391        assert_eq!(
392            apply(StrOp::Putc, hi, 0, 0),
393            hi,
394            "putc of 0 changes nothing"
395        );
396        assert_eq!(bytes(apply(StrOp::ToUpper, hi, 0, 0)), b"HELLO");
397        assert_eq!(
398            apply(StrOp::Compare, intern(b"a"), intern(b"b"), 0) as i64,
399            -1
400        );
401        assert_eq!(apply(StrOp::ICompare, intern(b"ABC"), intern(b"abc"), 0), 0);
402        assert_eq!(bytes(apply(StrOp::Substr, hi, 1, 3)), b"ell");
403        assert_eq!(apply(StrOp::Substr, hi, 3, 9), 0);
404        assert_eq!(apply(StrOp::AToI, intern(b"1_234x"), 0, 0) as i64, 1234);
405        // LRM 6.16.9: whitespace and a sign end the scan before any digit.
406        assert_eq!(apply(StrOp::AToI, intern(b" 12"), 0, 0), 0);
407        assert_eq!(apply(StrOp::AToI, intern(b"-5"), 0, 0), 0);
408        assert_eq!(apply(StrOp::AToHex, intern(b"ff_zz"), 0, 0), 255);
409        assert_eq!(
410            bytes(apply(StrOp::IToA, (-5i64) as u64, 0, 32 | 0x100)),
411            b"-5"
412        );
413        assert_eq!(bytes(apply(StrOp::HexToA, 255, 0, 32)), b"ff");
414        assert_eq!(bytes(apply(StrOp::FromBits, 0x4142, 0, 32)), b"AB");
415        assert_eq!(apply(StrOp::ToBitsLo, intern(b"AB"), 16, 0), 0x4142);
416        assert_eq!(apply(StrOp::ToBitsLo, intern(b"ABC"), 16, 0), 0x4243);
417        let long = intern(b"0123456789ABCDEFGH");
418        assert_eq!(
419            apply(StrOp::ToBitsWord, long, 144, 0),
420            u64::from_be_bytes(*b"ABCDEFGH")
421        );
422        assert_eq!(apply(StrOp::ToBitsWord, long, 144, 2), 0x3031);
423        assert_eq!(apply(StrOp::ToBitsWord, long, 140, 2), 0x031);
424    }
425}
vj_sim/strings.rs

vj_sim/
strings.rs
