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 std::collections::HashMap;
48use zerocopy::IntoBytes;
49
50/// Error type indicating that the reserved register (255) was used
51#[derive(thiserror::Error, Debug, PartialEq)]
52#[error("register 255 is reserved")]
53pub struct ReservedRegister;
54
55/// Operations in the bytecode tape
56#[derive(
57    Copy,
58    Clone,
59    Debug,
60    PartialEq,
61    serde::Serialize,
62    serde::Deserialize,
63    strum::EnumIter,
64    strum::EnumCount,
65    strum::IntoStaticStr,
66    strum::FromRepr,
67)]
68#[expect(missing_docs)]
69#[repr(u8)]
70pub enum BytecodeOp {
71    Output,
72    Input,
73    Copy,
74    Neg,
75    Abs,
76    Recip,
77    Sqrt,
78    Square,
79    Floor,
80    Ceil,
81    Round,
82    Not,
83    Rand,
84    Sin,
85    Cos,
86    Tan,
87    Asin,
88    Acos,
89    Atan,
90    Exp,
91    Ln,
92    Add,
93    Sub,
94    Mul,
95    Div,
96    Atan2,
97    Compare,
98    Mix,
99    Mod,
100    Min,
101    Max,
102    And,
103    Or,
104    Mem,
105}
106
107impl From<RegOp> for BytecodeOp {
108    fn from(op: RegOp) -> Self {
109        match op {
110            RegOp::Input(..) => BytecodeOp::Input,
111            RegOp::Output(..) => BytecodeOp::Output,
112            RegOp::NegReg(..) => BytecodeOp::Neg,
113            RegOp::AbsReg(..) => BytecodeOp::Abs,
114            RegOp::RecipReg(..) => BytecodeOp::Recip,
115            RegOp::SqrtReg(..) => BytecodeOp::Sqrt,
116            RegOp::SquareReg(..) => BytecodeOp::Square,
117            RegOp::FloorReg(..) => BytecodeOp::Floor,
118            RegOp::CeilReg(..) => BytecodeOp::Ceil,
119            RegOp::RoundReg(..) => BytecodeOp::Round,
120            RegOp::SinReg(..) => BytecodeOp::Sin,
121            RegOp::CosReg(..) => BytecodeOp::Cos,
122            RegOp::TanReg(..) => BytecodeOp::Tan,
123            RegOp::AsinReg(..) => BytecodeOp::Asin,
124            RegOp::AcosReg(..) => BytecodeOp::Acos,
125            RegOp::AtanReg(..) => BytecodeOp::Atan,
126            RegOp::ExpReg(..) => BytecodeOp::Exp,
127            RegOp::LnReg(..) => BytecodeOp::Ln,
128            RegOp::NotReg(..) => BytecodeOp::Not,
129            RegOp::RandReg(..) => BytecodeOp::Rand,
130            RegOp::Load(..) | RegOp::Store(..) => BytecodeOp::Mem,
131            RegOp::CopyImm(..) | RegOp::CopyReg(..) => BytecodeOp::Copy,
132
133            RegOp::AddRegReg(..) | RegOp::AddRegImm(..) => BytecodeOp::Add,
134            RegOp::MulRegReg(..) | RegOp::MulRegImm(..) => BytecodeOp::Mul,
135            RegOp::DivRegReg(..)
136            | RegOp::DivRegImm(..)
137            | RegOp::DivImmReg(..) => BytecodeOp::Div,
138            RegOp::SubRegReg(..)
139            | RegOp::SubRegImm(..)
140            | RegOp::SubImmReg(..) => BytecodeOp::Sub,
141            RegOp::AtanRegReg(..)
142            | RegOp::AtanRegImm(..)
143            | RegOp::AtanImmReg(..) => BytecodeOp::Atan2,
144            RegOp::MinRegReg(..) | RegOp::MinRegImm(..) => BytecodeOp::Min,
145            RegOp::MaxRegReg(..) | RegOp::MaxRegImm(..) => BytecodeOp::Max,
146            RegOp::CompareRegReg(..)
147            | RegOp::CompareRegImm(..)
148            | RegOp::CompareImmReg(..) => BytecodeOp::Compare,
149            RegOp::MixRegReg(..)
150            | RegOp::MixRegImm(..)
151            | RegOp::MixImmReg(..) => BytecodeOp::Mix,
152            RegOp::ModRegReg(..)
153            | RegOp::ModRegImm(..)
154            | RegOp::ModImmReg(..) => BytecodeOp::Mod,
155            RegOp::AndRegReg(..) | RegOp::AndRegImm(..) => BytecodeOp::And,
156            RegOp::OrRegReg(..) | RegOp::OrRegImm(..) => BytecodeOp::Or,
157        }
158    }
159}
160
161/// Serialized bytecode for external evaluation
162pub struct Bytecode {
163    reg_count: u8,
164    mem_count: u32,
165    data: Vec<u32>,
166}
167
168impl Bytecode {
169    /// Returns the length of the bytecode data (in `u32` words)
170    #[allow(clippy::len_without_is_empty)]
171    pub fn len(&self) -> usize {
172        self.data.len()
173    }
174
175    /// Raw serialized operations
176    pub fn data(&self) -> &[u32] {
177        &self.data
178    }
179
180    /// Number of registers (0-indexed) used by the tape
181    ///
182    /// This does not include the virtual register `0xFF` used for immediates
183    pub fn reg_count(&self) -> u8 {
184        self.reg_count
185    }
186
187    /// Number of memory slots (0-indexed) used for `Load` / `Store` operations
188    pub fn mem_count(&self) -> u32 {
189        self.mem_count
190    }
191
192    /// Returns a view of the byte slice
193    pub fn as_bytes(&self) -> &[u8] {
194        self.data.as_bytes()
195    }
196
197    /// Builds a new bytecode object from VM data
198    ///
199    /// Registers are reordered by frequency of use, e.g. the most frequently
200    /// used register becomes register 0.
201    ///
202    /// Returns an error if the reserved register (255) is in use, which should
203    /// only happen if the incoming tape has 256 active registers.
204    pub fn new<const N: usize>(
205        t: &VmData<N>,
206    ) -> Result<Self, ReservedRegister> {
207        Self::new_with_input_map(t, &HashMap::new())
208    }
209
210    /// Builds a new bytecode object from VM data, with input remapping
211    ///
212    /// This is helpful if you want multiple bytecode tapes to share the same
213    /// input indexing order.
214    ///
215    /// If a [`RegOp::Input`] is present in `input_map`, then the index from
216    /// `input_map` is used instead of the original index.  Expected patterns
217    /// are to remap either all or none of the inputs (the latter is done by the
218    /// plain [`new`](Self::new) function); it's hard to imagine a map which
219    /// remaps only _some_ inputs being useful, but don't let me stop you from
220    /// living out your dreams.
221    ///
222    /// Registers are reordered by frequency of use, e.g. the most frequently
223    /// used register becomes register 0.
224    ///
225    /// Returns an error if the reserved register (255) is in use, which should
226    /// only happen if the incoming tape has 256 active registers.
227    pub fn new_with_input_map<const N: usize>(
228        t: &VmData<N>,
229        input_map: &HashMap<u32, u32>,
230    ) -> Result<Self, ReservedRegister> {
231        // Build a map for repacking registers by frequency
232        let map = t.asm().repack_map();
233        // The initial opcode is `OP_JUMP 0x0000_0000`
234        let mut data = vec![u32::MAX, 0u32];
235        let mut reg_count = 0u8;
236        let mut mem_count = 0u32;
237        let mem_offset = u32::try_from(N).unwrap();
238        for op in t.iter_asm() {
239            let mut word = [0xFF; 4];
240            let mut imm = None;
241            let mut store_reg = |i, r| {
242                let r = map[&r];
243                if r == u8::MAX {
244                    Err(ReservedRegister)
245                } else {
246                    reg_count = reg_count.max(r + 1);
247                    word[i] = r;
248                    Ok(())
249                }
250            };
251            match op {
252                RegOp::Input(reg, slot) => {
253                    store_reg(1, reg)?;
254                    imm = Some(input_map.get(&slot).cloned().unwrap_or(slot));
255                }
256                RegOp::Output(reg, slot) => {
257                    store_reg(1, reg)?;
258                    imm = Some(slot);
259                }
260
261                RegOp::Load(reg, slot) => {
262                    store_reg(1, reg)?;
263                    word[2] = u8::MAX;
264                    mem_count = mem_count.max(slot + 1 - mem_offset);
265                    imm = Some(slot - mem_offset);
266                }
267                RegOp::Store(reg, slot) => {
268                    store_reg(2, reg)?;
269                    word[1] = u8::MAX;
270                    mem_count = mem_count.max(slot + 1 - mem_offset);
271                    imm = Some(slot - mem_offset);
272                }
273
274                RegOp::CopyImm(out, imm_f32) => {
275                    store_reg(1, out)?;
276                    word[2] = u8::MAX;
277                    imm = Some(imm_f32.to_bits());
278                }
279                RegOp::NegReg(out, reg)
280                | RegOp::AbsReg(out, reg)
281                | RegOp::RecipReg(out, reg)
282                | RegOp::SqrtReg(out, reg)
283                | RegOp::SquareReg(out, reg)
284                | RegOp::FloorReg(out, reg)
285                | RegOp::CeilReg(out, reg)
286                | RegOp::RoundReg(out, reg)
287                | RegOp::CopyReg(out, reg)
288                | RegOp::SinReg(out, reg)
289                | RegOp::CosReg(out, reg)
290                | RegOp::TanReg(out, reg)
291                | RegOp::AsinReg(out, reg)
292                | RegOp::AcosReg(out, reg)
293                | RegOp::AtanReg(out, reg)
294                | RegOp::ExpReg(out, reg)
295                | RegOp::LnReg(out, reg)
296                | RegOp::NotReg(out, reg)
297                | RegOp::RandReg(out, reg) => {
298                    store_reg(1, out)?;
299                    store_reg(2, reg)?;
300                }
301
302                RegOp::AddRegImm(out, reg, imm_f32)
303                | RegOp::MulRegImm(out, reg, imm_f32)
304                | RegOp::DivRegImm(out, reg, imm_f32)
305                | RegOp::SubRegImm(out, reg, imm_f32)
306                | RegOp::AtanRegImm(out, reg, imm_f32)
307                | RegOp::MinRegImm(out, reg, imm_f32)
308                | RegOp::MaxRegImm(out, reg, imm_f32)
309                | RegOp::CompareRegImm(out, reg, imm_f32)
310                | RegOp::MixRegImm(out, reg, imm_f32)
311                | RegOp::ModRegImm(out, reg, imm_f32)
312                | RegOp::AndRegImm(out, reg, imm_f32)
313                | RegOp::OrRegImm(out, reg, imm_f32) => {
314                    store_reg(1, out)?;
315                    store_reg(2, reg)?;
316                    word[3] = u8::MAX;
317                    imm = Some(imm_f32.to_bits());
318                }
319
320                RegOp::DivImmReg(out, reg, imm_f32)
321                | RegOp::SubImmReg(out, reg, imm_f32)
322                | RegOp::AtanImmReg(out, reg, imm_f32)
323                | RegOp::CompareImmReg(out, reg, imm_f32)
324                | RegOp::MixImmReg(out, reg, imm_f32)
325                | RegOp::ModImmReg(out, reg, imm_f32) => {
326                    store_reg(1, out)?;
327                    store_reg(3, reg)?;
328                    word[2] = u8::MAX;
329                    imm = Some(imm_f32.to_bits());
330                }
331
332                RegOp::AddRegReg(out, lhs, rhs)
333                | RegOp::MulRegReg(out, lhs, rhs)
334                | RegOp::DivRegReg(out, lhs, rhs)
335                | RegOp::SubRegReg(out, lhs, rhs)
336                | RegOp::AtanRegReg(out, lhs, rhs)
337                | RegOp::MinRegReg(out, lhs, rhs)
338                | RegOp::MaxRegReg(out, lhs, rhs)
339                | RegOp::CompareRegReg(out, lhs, rhs)
340                | RegOp::MixRegReg(out, lhs, rhs)
341                | RegOp::ModRegReg(out, lhs, rhs)
342                | RegOp::AndRegReg(out, lhs, rhs)
343                | RegOp::OrRegReg(out, lhs, rhs) => {
344                    store_reg(1, out)?;
345                    store_reg(2, lhs)?;
346                    store_reg(3, rhs)?;
347                }
348            };
349            word[0] = BytecodeOp::from(op) as u8;
350            data.push(u32::from_le_bytes(word));
351            data.push(imm.unwrap_or(0xFF000000));
352        }
353        // Add the final `OP_JUMP 0xFFFF_FFFF`
354        data.extend([u32::MAX, u32::MAX]);
355
356        Ok(Bytecode {
357            data,
358            mem_count,
359            reg_count,
360        })
361    }
362}
363
364/// Iterates over opcode `(names, value)` tuples, with names in `CamelCase`
365///
366/// This is a helper function for defining constants in a VM interpreter
367pub fn iter_ops<'a>() -> impl Iterator<Item = (&'a str, u8)> {
368    use strum::IntoEnumIterator;
369
370    BytecodeOp::iter().enumerate().map(|(i, op)| {
371        let s: &'static str = op.into();
372        (s, i as u8)
373    })
374}
375
376#[cfg(test)]
377mod test {
378    use super::*;
379
380    #[test]
381    fn simple_bytecode() {
382        let mut ctx = fidget_core::Context::new();
383        let x = ctx.x();
384        let c = ctx.constant(1.0);
385        let out = ctx.add(x, c).unwrap();
386        let data = VmData::<255>::new(&ctx, &[out]).unwrap();
387        let bc = Bytecode::new(&data).unwrap();
388        let mut iter = bc.data.iter();
389        let mut next = || *iter.next().unwrap();
390        assert_eq!(next(), 0xFFFFFFFF); // start marker
391        assert_eq!(next(), 0);
392        assert_eq!(
393            next().to_le_bytes(),
394            [BytecodeOp::Input as u8, 0, 0xFF, 0xFF]
395        );
396        assert_eq!(next(), 0); // input slot 0
397        assert_eq!(next().to_le_bytes(), [BytecodeOp::Add as u8, 0, 0, 0xFF]);
398        assert_eq!(f32::from_bits(next()), 1.0);
399        assert_eq!(
400            next().to_le_bytes(),
401            [BytecodeOp::Output as u8, 0, 0xFF, 0xFF]
402        );
403        assert_eq!(next(), 0); // output slot 0
404        assert_eq!(next(), 0xFFFFFFFF); // end marker
405        assert_eq!(next(), 0xFFFFFFFF);
406        assert!(iter.next().is_none());
407    }
408
409    #[test]
410    fn load_store() {
411        // Build a bytecode tape with only 2 registers to test load and store
412        let mut ctx = fidget_core::Context::new();
413        let x = ctx.x();
414        let y = ctx.y();
415        let z = ctx.z();
416        let xy = ctx.max(x, y).unwrap();
417        let out = ctx.max(xy, z).unwrap();
418        let data = VmData::<2>::new(&ctx, &[out]).unwrap();
419        let bc = Bytecode::new(&data).unwrap();
420        assert_eq!(bc.reg_count(), 2);
421        assert_eq!(bc.mem_count(), 1);
422        let mut iter = bc.data.iter();
423        let mut next = || *iter.next().unwrap();
424        assert_eq!(next(), 0xFFFFFFFF); // start marker
425        assert_eq!(next(), 0);
426
427        // Input(1, Z)
428        assert_eq!(
429            next().to_le_bytes(),
430            [BytecodeOp::Input as u8, 1, 0xFF, 0xFF]
431        );
432        assert_eq!(next(), 2); // Z
433
434        // Copy from reg[1] -> mem[0]
435        assert_eq!(
436            next().to_le_bytes(),
437            [BytecodeOp::Mem as u8, 0xFF, 1, 0xFF]
438        );
439        assert_eq!(next(), 0);
440
441        // Input(1, Y)
442        assert_eq!(
443            next().to_le_bytes(),
444            [BytecodeOp::Input as u8, 1, 0xFF, 0xFF]
445        );
446        assert_eq!(next(), 1); // Y
447
448        // Input(0, X)
449        assert_eq!(
450            next().to_le_bytes(),
451            [BytecodeOp::Input as u8, 0, 0xFF, 0xFF]
452        );
453        assert_eq!(next(), 0); // X
454
455        // r1 = max(1, 0)
456        assert_eq!(next().to_le_bytes(), [BytecodeOp::Max as u8, 1, 1, 0]);
457        assert_eq!(next(), 0xFF000000);
458
459        // Copy from mem[0] -> reg[0]
460        assert_eq!(
461            next().to_le_bytes(),
462            [BytecodeOp::Mem as u8, 0, 0xFF, 0xFF]
463        );
464        assert_eq!(next(), 0);
465
466        // r0 = max(0, 1)
467        assert_eq!(next().to_le_bytes(), [BytecodeOp::Max as u8, 0, 0, 1]);
468        assert_eq!(next(), 0xFF000000);
469
470        // output(0) = r0
471        assert_eq!(
472            next().to_le_bytes(),
473            [BytecodeOp::Output as u8, 0, 0xFF, 0xFF]
474        );
475        assert_eq!(next(), 0);
476
477        assert_eq!(next(), 0xFFFFFFFF); // end marker
478        assert_eq!(next(), 0xFFFFFFFF);
479        assert!(iter.next().is_none());
480    }
481}
fidget_bytecode/lib.rs

fidget_bytecode/
lib.rs
