fidget_bytecode/
lib.rs

1//! Tape bytecode format
2//!
3//! Fidget's bytecode is a packed representation of a
4//! [`RegTape`](fidget_core::compiler::RegTape).  It may be used as the
5//! evaluation tape for non-Rust VMs, e.g. an interpreter running on a GPU.
6//!
7//! The format is **not stable**; it may change without notice.  It would be
8//! wise to dynamically check any interpreter against [`iter_ops`], which
9//! associates opcode integers with their names.
10//!
11//! The bytecode format is a list of little-endian `u32` words, representing
12//! tape operations in forward-evaluation order. Each operation in the tape maps
13//! to two words, though the second word is not always used.  Having a
14//! fixed-length representation makes it easier to iterate both forwards (for
15//! evaluation) and backwards (for simplification).
16//!
17//! The first two words are always `0xFFFF_FFFF 0x0000_0000`, and the last two
18//! words are always `0xFFFF_FFFF 0xFFFF_FFFF`.  Note that this is equivalent to
19//! an operation with opcode `0xFF`; this special opcode may also be used with
20//! user-defined semantics, as long as the immediate is not either reserved
21//! value.
22//!
23//! Operations are packed into the first `u32` as follows:
24//!
25//! | Byte | Value                                       |
26//! |------|---------------------------------------------|
27//! | 0    | opcode                                      |
28//! | 1    | output register                             |
29//! | 2    | first input register                        |
30//! | 3    | second input register                       |
31//!
32//! The opcode byte is generated automatically from [`BytecodeOp`] tags.
33//!
34//! Depending on the opcode, the input register bytes may not be used.
35//!
36//! An input register byte of `0xFF` indicates that the second word should be
37//! used as an immediate value; the `u32` should be bitcast to an `f32`.
38//!
39//! [`Load`](RegOp::Load) and [`Store`](RegOp::Store) are implemented with
40//! [`BytecodeOp::Mem`], using the immediate flag `0xFF` to indicate whether the
41//! operation reads or writes to memory.  The second word is the `u32` immediate
42//! representing a memory slot.
43
44#![warn(missing_docs)]
45
46use fidget_core::{compiler::RegOp, vm::VmData};
47use zerocopy::IntoBytes;
48
49/// Error type indicating that the reserved register (255) was used
50#[derive(thiserror::Error, Debug, PartialEq)]
51#[error("register 255 is reserved")]
52pub struct ReservedRegister;
53
54/// Operations in the bytecode tape
55#[derive(
56    Copy,
57    Clone,
58    Debug,
59    PartialEq,
60    serde::Serialize,
61    serde::Deserialize,
62    strum::EnumIter,
63    strum::EnumCount,
64    strum::IntoStaticStr,
65    strum::FromRepr,
66)]
67#[expect(missing_docs)]
68#[repr(u8)]
69pub enum BytecodeOp {
70    Output,
71    Input,
72    Copy,
73    Neg,
74    Abs,
75    Recip,
76    Sqrt,
77    Square,
78    Floor,
79    Ceil,
80    Round,
81    Not,
82    Sin,
83    Cos,
84    Tan,
85    Asin,
86    Acos,
87    Atan,
88    Exp,
89    Ln,
90    Add,
91    Sub,
92    Mul,
93    Div,
94    Atan2,
95    Compare,
96    Mod,
97    Min,
98    Max,
99    And,
100    Or,
101    Mem,
102}
103
104impl From<RegOp> for BytecodeOp {
105    fn from(op: RegOp) -> Self {
106        match op {
107            RegOp::Input(..) => BytecodeOp::Input,
108            RegOp::Output(..) => BytecodeOp::Output,
109            RegOp::NegReg(..) => BytecodeOp::Neg,
110            RegOp::AbsReg(..) => BytecodeOp::Abs,
111            RegOp::RecipReg(..) => BytecodeOp::Recip,
112            RegOp::SqrtReg(..) => BytecodeOp::Sqrt,
113            RegOp::SquareReg(..) => BytecodeOp::Square,
114            RegOp::FloorReg(..) => BytecodeOp::Floor,
115            RegOp::CeilReg(..) => BytecodeOp::Ceil,
116            RegOp::RoundReg(..) => BytecodeOp::Round,
117            RegOp::SinReg(..) => BytecodeOp::Sin,
118            RegOp::CosReg(..) => BytecodeOp::Cos,
119            RegOp::TanReg(..) => BytecodeOp::Tan,
120            RegOp::AsinReg(..) => BytecodeOp::Asin,
121            RegOp::AcosReg(..) => BytecodeOp::Acos,
122            RegOp::AtanReg(..) => BytecodeOp::Atan,
123            RegOp::ExpReg(..) => BytecodeOp::Exp,
124            RegOp::LnReg(..) => BytecodeOp::Ln,
125            RegOp::NotReg(..) => BytecodeOp::Not,
126            RegOp::Load(..) | RegOp::Store(..) => BytecodeOp::Mem,
127            RegOp::CopyImm(..) | RegOp::CopyReg(..) => BytecodeOp::Copy,
128
129            RegOp::AddRegReg(..) | RegOp::AddRegImm(..) => BytecodeOp::Add,
130            RegOp::MulRegReg(..) | RegOp::MulRegImm(..) => BytecodeOp::Mul,
131            RegOp::DivRegReg(..)
132            | RegOp::DivRegImm(..)
133            | RegOp::DivImmReg(..) => BytecodeOp::Div,
134            RegOp::SubRegReg(..)
135            | RegOp::SubRegImm(..)
136            | RegOp::SubImmReg(..) => BytecodeOp::Sub,
137            RegOp::AtanRegReg(..)
138            | RegOp::AtanRegImm(..)
139            | RegOp::AtanImmReg(..) => BytecodeOp::Atan2,
140            RegOp::MinRegReg(..) | RegOp::MinRegImm(..) => BytecodeOp::Min,
141            RegOp::MaxRegReg(..) | RegOp::MaxRegImm(..) => BytecodeOp::Max,
142            RegOp::CompareRegReg(..)
143            | RegOp::CompareRegImm(..)
144            | RegOp::CompareImmReg(..) => BytecodeOp::Compare,
145            RegOp::ModRegReg(..)
146            | RegOp::ModRegImm(..)
147            | RegOp::ModImmReg(..) => BytecodeOp::Mod,
148            RegOp::AndRegReg(..) | RegOp::AndRegImm(..) => BytecodeOp::And,
149            RegOp::OrRegReg(..) | RegOp::OrRegImm(..) => BytecodeOp::Or,
150        }
151    }
152}
153
154/// Serialized bytecode for external evaluation
155pub struct Bytecode {
156    reg_count: u8,
157    mem_count: u32,
158    data: Vec<u32>,
159}
160
161impl Bytecode {
162    /// Returns the length of the bytecode data (in `u32` words)
163    #[allow(clippy::len_without_is_empty)]
164    pub fn len(&self) -> usize {
165        self.data.len()
166    }
167
168    /// Raw serialized operations
169    pub fn data(&self) -> &[u32] {
170        &self.data
171    }
172
173    /// Number of registers (0-indexed) used by the tape
174    ///
175    /// This does not include the virtual register `0xFF` used for immediates
176    pub fn reg_count(&self) -> u8 {
177        self.reg_count
178    }
179
180    /// Number of memory slots (0-indexed) used for `Load` / `Store` operations
181    pub fn mem_count(&self) -> u32 {
182        self.mem_count
183    }
184
185    /// Returns a view of the byte slice
186    pub fn as_bytes(&self) -> &[u8] {
187        self.data.as_bytes()
188    }
189
190    /// Builds a new bytecode object from VM data
191    ///
192    /// Registers are reordered by frequency of use, e.g. the most frequently
193    /// used register becomes register 0.
194    ///
195    /// Returns an error if the reserved register (255) is in use, which should
196    /// only happen if the incoming tape has 256 active registers.
197    pub fn new<const N: usize>(
198        t: &VmData<N>,
199    ) -> Result<Self, ReservedRegister> {
200        // Build a map for repacking registers by frequency
201        let map = t.asm().repack_map();
202        // The initial opcode is `OP_JUMP 0x0000_0000`
203        let mut data = vec![u32::MAX, 0u32];
204        let mut reg_count = 0u8;
205        let mut mem_count = 0u32;
206        let mem_offset = u32::try_from(N).unwrap();
207        for op in t.iter_asm() {
208            let mut word = [0xFF; 4];
209            let mut imm = None;
210            let mut store_reg = |i, r| {
211                let r = map[&r];
212                if r == u8::MAX {
213                    Err(ReservedRegister)
214                } else {
215                    reg_count = reg_count.max(r + 1);
216                    word[i] = r;
217                    Ok(())
218                }
219            };
220            match op {
221                RegOp::Input(reg, slot) | RegOp::Output(reg, slot) => {
222                    store_reg(1, reg)?;
223                    imm = Some(slot);
224                }
225
226                RegOp::Load(reg, slot) => {
227                    store_reg(1, reg)?;
228                    word[2] = u8::MAX;
229                    mem_count = mem_count.max(slot + 1 - mem_offset);
230                    imm = Some(slot - mem_offset);
231                }
232                RegOp::Store(reg, slot) => {
233                    store_reg(2, reg)?;
234                    word[1] = u8::MAX;
235                    mem_count = mem_count.max(slot + 1 - mem_offset);
236                    imm = Some(slot - mem_offset);
237                }
238
239                RegOp::CopyImm(out, imm_f32) => {
240                    store_reg(1, out)?;
241                    word[2] = u8::MAX;
242                    imm = Some(imm_f32.to_bits());
243                }
244                RegOp::NegReg(out, reg)
245                | RegOp::AbsReg(out, reg)
246                | RegOp::RecipReg(out, reg)
247                | RegOp::SqrtReg(out, reg)
248                | RegOp::SquareReg(out, reg)
249                | RegOp::FloorReg(out, reg)
250                | RegOp::CeilReg(out, reg)
251                | RegOp::RoundReg(out, reg)
252                | RegOp::CopyReg(out, reg)
253                | RegOp::SinReg(out, reg)
254                | RegOp::CosReg(out, reg)
255                | RegOp::TanReg(out, reg)
256                | RegOp::AsinReg(out, reg)
257                | RegOp::AcosReg(out, reg)
258                | RegOp::AtanReg(out, reg)
259                | RegOp::ExpReg(out, reg)
260                | RegOp::LnReg(out, reg)
261                | RegOp::NotReg(out, reg) => {
262                    store_reg(1, out)?;
263                    store_reg(2, reg)?;
264                }
265
266                RegOp::AddRegImm(out, reg, imm_f32)
267                | RegOp::MulRegImm(out, reg, imm_f32)
268                | RegOp::DivRegImm(out, reg, imm_f32)
269                | RegOp::SubRegImm(out, reg, imm_f32)
270                | RegOp::AtanRegImm(out, reg, imm_f32)
271                | RegOp::MinRegImm(out, reg, imm_f32)
272                | RegOp::MaxRegImm(out, reg, imm_f32)
273                | RegOp::CompareRegImm(out, reg, imm_f32)
274                | RegOp::ModRegImm(out, reg, imm_f32)
275                | RegOp::AndRegImm(out, reg, imm_f32)
276                | RegOp::OrRegImm(out, reg, imm_f32) => {
277                    store_reg(1, out)?;
278                    store_reg(2, reg)?;
279                    word[3] = u8::MAX;
280                    imm = Some(imm_f32.to_bits());
281                }
282
283                RegOp::DivImmReg(out, reg, imm_f32)
284                | RegOp::SubImmReg(out, reg, imm_f32)
285                | RegOp::AtanImmReg(out, reg, imm_f32)
286                | RegOp::CompareImmReg(out, reg, imm_f32)
287                | RegOp::ModImmReg(out, reg, imm_f32) => {
288                    store_reg(1, out)?;
289                    store_reg(3, reg)?;
290                    word[2] = u8::MAX;
291                    imm = Some(imm_f32.to_bits());
292                }
293
294                RegOp::AddRegReg(out, lhs, rhs)
295                | RegOp::MulRegReg(out, lhs, rhs)
296                | RegOp::DivRegReg(out, lhs, rhs)
297                | RegOp::SubRegReg(out, lhs, rhs)
298                | RegOp::AtanRegReg(out, lhs, rhs)
299                | RegOp::MinRegReg(out, lhs, rhs)
300                | RegOp::MaxRegReg(out, lhs, rhs)
301                | RegOp::CompareRegReg(out, lhs, rhs)
302                | RegOp::ModRegReg(out, lhs, rhs)
303                | RegOp::AndRegReg(out, lhs, rhs)
304                | RegOp::OrRegReg(out, lhs, rhs) => {
305                    store_reg(1, out)?;
306                    store_reg(2, lhs)?;
307                    store_reg(3, rhs)?;
308                }
309            };
310            word[0] = BytecodeOp::from(op) as u8;
311            data.push(u32::from_le_bytes(word));
312            data.push(imm.unwrap_or(0xFF000000));
313        }
314        // Add the final `OP_JUMP 0xFFFF_FFFF`
315        data.extend([u32::MAX, u32::MAX]);
316
317        Ok(Bytecode {
318            data,
319            mem_count,
320            reg_count,
321        })
322    }
323}
324
325/// Iterates over opcode `(names, value)` tuples, with names in `CamelCase`
326///
327/// This is a helper function for defining constants in a VM interpreter
328pub fn iter_ops<'a>() -> impl Iterator<Item = (&'a str, u8)> {
329    use strum::IntoEnumIterator;
330
331    BytecodeOp::iter().enumerate().map(|(i, op)| {
332        let s: &'static str = op.into();
333        (s, i as u8)
334    })
335}
336
337#[cfg(test)]
338mod test {
339    use super::*;
340
341    #[test]
342    fn simple_bytecode() {
343        let mut ctx = fidget_core::Context::new();
344        let x = ctx.x();
345        let c = ctx.constant(1.0);
346        let out = ctx.add(x, c).unwrap();
347        let data = VmData::<255>::new(&ctx, &[out]).unwrap();
348        let bc = Bytecode::new(&data).unwrap();
349        let mut iter = bc.data.iter();
350        let mut next = || *iter.next().unwrap();
351        assert_eq!(next(), 0xFFFFFFFF); // start marker
352        assert_eq!(next(), 0);
353        assert_eq!(
354            next().to_le_bytes(),
355            [BytecodeOp::Input as u8, 0, 0xFF, 0xFF]
356        );
357        assert_eq!(next(), 0); // input slot 0
358        assert_eq!(next().to_le_bytes(), [BytecodeOp::Add as u8, 0, 0, 0xFF]);
359        assert_eq!(f32::from_bits(next()), 1.0);
360        assert_eq!(
361            next().to_le_bytes(),
362            [BytecodeOp::Output as u8, 0, 0xFF, 0xFF]
363        );
364        assert_eq!(next(), 0); // output slot 0
365        assert_eq!(next(), 0xFFFFFFFF); // end marker
366        assert_eq!(next(), 0xFFFFFFFF);
367        assert!(iter.next().is_none());
368    }
369
370    #[test]
371    fn load_store() {
372        // Build a bytecode tape with only 2 registers to test load and store
373        let mut ctx = fidget_core::Context::new();
374        let x = ctx.x();
375        let y = ctx.y();
376        let z = ctx.z();
377        let xy = ctx.max(x, y).unwrap();
378        let out = ctx.max(xy, z).unwrap();
379        let data = VmData::<2>::new(&ctx, &[out]).unwrap();
380        let bc = Bytecode::new(&data).unwrap();
381        assert_eq!(bc.reg_count(), 2);
382        assert_eq!(bc.mem_count(), 1);
383        let mut iter = bc.data.iter();
384        let mut next = || *iter.next().unwrap();
385        assert_eq!(next(), 0xFFFFFFFF); // start marker
386        assert_eq!(next(), 0);
387
388        // Input(1, Z)
389        assert_eq!(
390            next().to_le_bytes(),
391            [BytecodeOp::Input as u8, 1, 0xFF, 0xFF]
392        );
393        assert_eq!(next(), 2); // Z
394
395        // Copy from reg[1] -> mem[0]
396        assert_eq!(
397            next().to_le_bytes(),
398            [BytecodeOp::Mem as u8, 0xFF, 1, 0xFF]
399        );
400        assert_eq!(next(), 0);
401
402        // Input(1, Y)
403        assert_eq!(
404            next().to_le_bytes(),
405            [BytecodeOp::Input as u8, 1, 0xFF, 0xFF]
406        );
407        assert_eq!(next(), 1); // Y
408
409        // Input(0, X)
410        assert_eq!(
411            next().to_le_bytes(),
412            [BytecodeOp::Input as u8, 0, 0xFF, 0xFF]
413        );
414        assert_eq!(next(), 0); // X
415
416        // r1 = max(1, 0)
417        assert_eq!(next().to_le_bytes(), [BytecodeOp::Max as u8, 1, 1, 0]);
418        assert_eq!(next(), 0xFF000000);
419
420        // Copy from mem[0] -> reg[0]
421        assert_eq!(
422            next().to_le_bytes(),
423            [BytecodeOp::Mem as u8, 0, 0xFF, 0xFF]
424        );
425        assert_eq!(next(), 0);
426
427        // r0 = max(0, 1)
428        assert_eq!(next().to_le_bytes(), [BytecodeOp::Max as u8, 0, 0, 1]);
429        assert_eq!(next(), 0xFF000000);
430
431        // output(0) = r0
432        assert_eq!(
433            next().to_le_bytes(),
434            [BytecodeOp::Output as u8, 0, 0xFF, 0xFF]
435        );
436        assert_eq!(next(), 0);
437
438        assert_eq!(next(), 0xFFFFFFFF); // end marker
439        assert_eq!(next(), 0xFFFFFFFF);
440        assert!(iter.next().is_none());
441    }
442}
fidget_bytecode/lib.rs

fidget_bytecode/
lib.rs
