cove_ir/bytecode/
decode.rs

1//! Sixteen bytes back to `Inst`.
2//!
3//! ADR 0041 makes the encoding 1:1, so this is a genuine inverse and not a
4//! best effort: `decode(encode(i, pc), pc) == i` for every instruction, and
5//! `encode(decode(b, pc), pc) == b` for every byte pattern this accepts.
6//!
7//! # It is strict, and that is what makes the encoding canonical
8//!
9//! A field an opcode does not use must be zero, `flags` must be zero, and a
10//! `const.bool` payload must be `0` or `1`. Bytes that say the same thing in
11//! two ways are refused rather than normalised, which is what gives the second
12//! half of the round trip: a program has exactly one encoding, so two
13//! encodings of it are byte-identical and a diff over encoded code means
14//! something.
15//!
16//! # What it is for
17//!
18//! Tests, the debugger, and [`disasm`](super::disasm) — never the dispatch
19//! loop. A verified program is executed from its bytes; this is how a human
20//! reads them back.
21
22use crate::inst::{Inst, Len, Pc, Slot};
23use crate::layout::LayoutId;
24use crate::{ArgsId, BuiltinId, FunctionId, HostOpId, StrId, TableId};
25
26use super::op::{Half, Op, Operand, Payload};
27use super::EncodedInst;
28
29/// Why sixteen bytes are not an instruction.
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
31pub enum Malformed {
32    /// The opcode byte names no defined operation.
33    Opcode(u8),
34    /// `flags` is reserved and must be zero.
35    Flags(u8),
36    /// A field the opcode does not use, and it is not zero.
37    NotCanonical {
38        /// `a`, `b`, `c`, `payload`, `payload.low` or `payload.high`.
39        field: &'static str,
40        value: u64,
41    },
42    /// A `const.bool` whose payload is neither `0` nor `1`.
43    Bool(u64),
44    /// A branch whose target is not a program counter at all — before the
45    /// first instruction, or past what a [`Pc`] can name.
46    ///
47    /// Whether it is inside *this function* is [`verify`](super::verify())'s
48    /// question, because only the function knows how long it is.
49    Target { pc: Pc, displacement: i64 },
50}
51
52impl std::fmt::Display for Malformed {
53    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
54        match self {
55            Malformed::Opcode(byte) => write!(f, "opcode {byte} names no operation"),
56            Malformed::Flags(flags) => {
57                write!(f, "flags is {flags}, and it is reserved and must be zero")
58            }
59            Malformed::NotCanonical { field, value } => write!(
60                f,
61                "this opcode does not use {field}, and it holds {value} rather than zero"
62            ),
63            Malformed::Bool(value) => {
64                write!(f, "a bool constant holds {value}, which is neither 0 nor 1")
65            }
66            Malformed::Target { pc, displacement } => write!(
67                f,
68                "a branch at {pc} displaced by {displacement} lands on no program counter"
69            ),
70        }
71    }
72}
73
74/// Reads one encoded instruction back.
75///
76/// `pc` is where it sits, and only a branch reads it: the displacement in the
77/// payload is relative to the instruction after this one.
78pub fn decode(code: EncodedInst, pc: Pc) -> Result<Inst, Malformed> {
79    if code.flags() != 0 {
80        return Err(Malformed::Flags(code.flags()));
81    }
82    let Some(op) = Op::from_number(code.opcode()) else {
83        return Err(Malformed::Opcode(code.opcode()));
84    };
85    canonical(code, op)?;
86
87    let a = code.a() as Slot;
88    let b = code.b() as Slot;
89    let c = code.c() as Slot;
90    let lo = code.lo();
91    let hi = code.hi();
92    let layout = LayoutId(lo);
93    Ok(match op {
94        Op::ConstUnit => Inst::Unit { dst: a },
95        Op::ConstBool => Inst::Bool {
96            dst: a,
97            value: match code.payload() {
98                0 => false,
99                1 => true,
100                held => return Err(Malformed::Bool(held)),
101            },
102        },
103        Op::ConstInt => Inst::Int {
104            dst: a,
105            value: code.payload() as i64,
106        },
107        Op::FuncRef => Inst::FuncRef {
108            dst: a,
109            callee: FunctionId(lo),
110        },
111        Op::ConstTag => Inst::Tag {
112            dst: a,
113            layout: LayoutId(hi),
114            case: crate::CaseId(lo),
115        },
116        Op::ConstFloat => Inst::Float {
117            dst: a,
118            bits: code.payload(),
119        },
120        Op::Str => Inst::Str {
121            dst: a,
122            text: StrId(lo),
123        },
124        Op::Copy => Inst::Copy {
125            dst: a,
126            src: b,
127            layout,
128        },
129        Op::Clear => Inst::Clear { slot: a, layout },
130        Op::Neg(num) => Inst::Neg { num, dst: a, a: b },
131        Op::Arith(num, op) => Inst::Arith {
132            num,
133            op,
134            dst: a,
135            a: b,
136            b: c,
137        },
138        Op::Cmp(on, op) => Inst::Cmp {
139            on,
140            op,
141            dst: a,
142            a: b,
143            b: c,
144        },
145        Op::ArithImm(op) => Inst::ArithImm {
146            op,
147            dst: a,
148            a: b,
149            value: code.payload() as i64,
150        },
151        Op::CmpImm(op) => Inst::CmpImm {
152            op,
153            dst: a,
154            a: b,
155            value: code.payload() as i64,
156        },
157        Op::Not => Inst::Not { dst: a, a: b },
158        Op::Convert(to) => Inst::Convert { to, dst: a, a: b },
159        Op::Jump => Inst::Jump {
160            to: target(pc, code.payload() as i64)?,
161        },
162        Op::BranchFalse => Inst::BranchFalse {
163            cond: a,
164            to: target(pc, code.payload() as i64)?,
165        },
166        Op::Switch => Inst::Switch {
167            on: a,
168            table: TableId(lo),
169        },
170        Op::Return => Inst::Return { src: a },
171        Op::Call => Inst::Call {
172            dst: a,
173            callee: FunctionId(lo),
174            args: ArgsId(hi),
175        },
176        Op::CallClosure => Inst::CallClosure {
177            dst: a,
178            closure: b,
179            args: ArgsId(lo),
180            result: LayoutId(hi),
181        },
182        Op::CallHost => Inst::CallHost {
183            dst: a,
184            op: HostOpId(lo),
185            args: ArgsId(hi),
186        },
187        Op::CallResource => Inst::CallResource {
188            dst: a,
189            receiver: b,
190            op: HostOpId(lo),
191            args: ArgsId(hi),
192        },
193        Op::CallBuiltin => Inst::CallBuiltin {
194            dst: a,
195            builtin: BuiltinId(lo),
196            args: ArgsId(hi),
197        },
198        Op::AllocFixed => Inst::Alloc {
199            dst: a,
200            layout,
201            len: Len::Fixed,
202        },
203        Op::AllocImm => Inst::Alloc {
204            dst: a,
205            layout,
206            len: Len::Count(hi),
207        },
208        Op::AllocSlot => Inst::Alloc {
209            dst: a,
210            layout,
211            len: Len::Slot(b),
212        },
213        Op::LoadField => Inst::LoadField {
214            dst: a,
215            obj: b,
216            at: lo,
217            layout: LayoutId(hi),
218        },
219        Op::StoreField => Inst::StoreField {
220            obj: a,
221            at: lo,
222            src: b,
223            layout: LayoutId(hi),
224        },
225        Op::LoadElem => Inst::LoadElem {
226            dst: a,
227            obj: b,
228            index: c,
229            layout,
230        },
231        Op::StoreElem => Inst::StoreElem {
232            obj: a,
233            index: b,
234            src: c,
235            layout,
236        },
237        Op::ByteAt => Inst::ByteAt {
238            dst: a,
239            obj: b,
240            at: c,
241        },
242        Op::AllocBytes => Inst::AllocBytes { dst: a, len: b },
243        Op::WriteByte => Inst::WriteByte {
244            bytes: a,
245            at: b,
246            value: c,
247        },
248        Op::CopyBytes => Inst::CopyBytes { args: ArgsId(lo) },
249        Op::FinishString => Inst::FinishString { dst: a, bytes: b },
250        Op::AllocBuffer => Inst::AllocBuffer {
251            dst: a,
252            capacity: b,
253        },
254        Op::AppendByte => Inst::AppendByte {
255            buffer: a,
256            value: b,
257        },
258        Op::AppendBytes => Inst::AppendBytes { args: ArgsId(lo) },
259        Op::FinishBuffer => Inst::FinishBuffer { dst: a, buffer: b },
260        Op::Len => Inst::Len { dst: a, obj: b },
261        Op::LayoutOf => Inst::LayoutOf { dst: a, obj: b },
262        Op::AddrOfSlot => Inst::AddrOfSlot { dst: a, slot: b },
263        Op::AddrOfField => Inst::AddrOfField {
264            dst: a,
265            obj: b,
266            at: lo,
267        },
268        Op::AddrOfElem => Inst::AddrOfElem {
269            dst: a,
270            obj: b,
271            index: c,
272            layout,
273        },
274        Op::AddrOfPart => Inst::AddrOfPart {
275            dst: a,
276            addr: b,
277            at: lo,
278        },
279        Op::Load => Inst::Load {
280            dst: a,
281            addr: b,
282            layout,
283        },
284        Op::Store => Inst::Store {
285            addr: a,
286            src: b,
287            layout,
288        },
289        Op::Box => Inst::Box {
290            dst: a,
291            src: b,
292            layout,
293        },
294        Op::Unbox => Inst::Unbox {
295            dst: a,
296            src: b,
297            layout,
298        },
299        Op::ScopeEnter => Inst::ScopeEnter {
300            dst: a,
301            name: StrId(lo),
302        },
303        Op::ScopeLeave => Inst::ScopeLeave {
304            scope: a,
305            failed: b,
306            error: c,
307            layout,
308        },
309        Op::ScopeCancel => Inst::ScopeCancel { scope: a },
310        Op::Spawn => Inst::Spawn {
311            dst: a,
312            scope: b,
313            closure: c,
314            answer: layout,
315        },
316        Op::Await => Inst::Await {
317            dst: a,
318            task: b,
319            answer: layout,
320        },
321        Op::Cancel => Inst::Cancel { task: a },
322        Op::Settled => Inst::Settled {
323            dst: a,
324            src: b,
325            answer: layout,
326        },
327        Op::SharedLock => Inst::SharedLock { cell: a },
328        Op::SharedUnlock => Inst::SharedUnlock { cell: a },
329        Op::Trap => Inst::Trap { message: StrId(lo) },
330        Op::AssertFailed => Inst::AssertFailed { message: a },
331    })
332}
333
334/// Every field the opcode does not use is zero.
335///
336/// One rule over the same table [`verify`](super::verify) reads, so that
337/// "canonical" is a property of the format rather than of whichever reader
338/// remembered to check it.
339fn canonical(code: EncodedInst, op: Op) -> Result<(), Malformed> {
340    let fields = op.fields();
341    for (operand, (name, held)) in
342        fields
343            .operands()
344            .into_iter()
345            .zip([("a", code.a()), ("b", code.b()), ("c", code.c())])
346    {
347        if operand == Operand::Unused && held != 0 {
348            return Err(Malformed::NotCanonical {
349                field: name,
350                value: u64::from(held),
351            });
352        }
353    }
354    match fields.payload {
355        Payload::Empty => {
356            if code.payload() != 0 {
357                return Err(Malformed::NotCanonical {
358                    field: "payload",
359                    value: code.payload(),
360                });
361            }
362        }
363        // A `Bool` payload's own range is checked where it is read, so that
364        // the fault names the constant rather than the field.
365        Payload::Bool | Payload::Imm | Payload::Displacement => {}
366        Payload::Halves(lo, hi) => {
367            for (half, (name, held)) in [lo, hi]
368                .into_iter()
369                .zip([("payload.low", code.lo()), ("payload.high", code.hi())])
370            {
371                if half == Half::Unused && held != 0 {
372                    return Err(Malformed::NotCanonical {
373                        field: name,
374                        value: u64::from(held),
375                    });
376                }
377            }
378        }
379    }
380    Ok(())
381}
382
383/// Where a displacement points, as a program counter.
384fn target(pc: Pc, displacement: i64) -> Result<Pc, Malformed> {
385    let refused = Malformed::Target { pc, displacement };
386    let to = (i64::from(pc) + 1)
387        .checked_add(displacement)
388        .ok_or(refused)?;
389    Pc::try_from(to).map_err(|_| refused)
390}
391
392#[cfg(test)]
393mod tests {
394    use super::*;
395    use crate::bytecode::encode::encode;
396    use crate::inst::Num;
397
398    /// The bytes of `const.int s1 = 7`, as a starting point for bending one
399    /// field at a time.
400    fn int() -> EncodedInst {
401        encode(&Inst::Int { dst: 1, value: 7 }, 0).expect("encodes")
402    }
403
404    /// Sets one byte, which is how a test writes bytes no encoder produced.
405    fn with(code: EncodedInst, at: usize, byte: u8) -> EncodedInst {
406        let mut bytes = *code.bytes();
407        bytes[at] = byte;
408        EncodedInst::from_bytes(bytes)
409    }
410
411    /// A byte that names no operation is refused rather than indexed with.
412    /// A hundred and one opcodes are defined out of 256, so more than half of
413    /// all bytes reach this.
414    #[test]
415    fn an_opcode_no_encoder_produced_is_refused() {
416        for byte in crate::bytecode::op::OPCODES as u8..=255 {
417            assert_eq!(
418                decode(with(int(), 0, byte), 0),
419                Err(Malformed::Opcode(byte))
420            );
421        }
422    }
423
424    /// `flags` is reserved and carries nothing, so a nonzero one is bytes
425    /// that mean something this format does not define.
426    #[test]
427    fn a_nonzero_flags_byte_is_refused() {
428        assert_eq!(decode(int(), 0), Ok(Inst::Int { dst: 1, value: 7 }));
429        assert_eq!(decode(with(int(), 1, 1), 0), Err(Malformed::Flags(1)));
430        assert_eq!(decode(with(int(), 1, 0x80), 0), Err(Malformed::Flags(0x80)));
431    }
432
433    /// A field the opcode does not use must be zero. That is what makes the
434    /// encoding canonical: one program, one byte string, and a diff over
435    /// encoded code that means something.
436    #[test]
437    fn a_field_the_opcode_does_not_use_must_be_zero() {
438        // `const.int` uses `a` and the payload, and neither `b` nor `c`.
439        assert_eq!(
440            decode(with(int(), 4, 1), 0),
441            Err(Malformed::NotCanonical {
442                field: "b",
443                value: 1
444            })
445        );
446        assert_eq!(
447            decode(with(int(), 6, 3), 0),
448            Err(Malformed::NotCanonical {
449                field: "c",
450                value: 3
451            })
452        );
453        // `neg.int` uses no payload at all.
454        let neg = encode(
455            &Inst::Neg {
456                num: Num::Int,
457                dst: 1,
458                a: 2,
459            },
460            0,
461        )
462        .expect("encodes");
463        assert_eq!(
464            decode(with(neg, 8, 1), 0),
465            Err(Malformed::NotCanonical {
466                field: "payload",
467                value: 1
468            })
469        );
470        // `str` uses the low half and not the high one.
471        let text = encode(
472            &Inst::Str {
473                dst: 1,
474                text: crate::StrId(2),
475            },
476            0,
477        )
478        .expect("encodes");
479        assert_eq!(
480            decode(with(text, 12, 1), 0),
481            Err(Malformed::NotCanonical {
482                field: "payload.high",
483                value: 1
484            })
485        );
486    }
487
488    /// A `Bool` is one bit in sixty-four, and every other value of the
489    /// payload is bytes that decode to no instruction — not to `true`.
490    #[test]
491    fn a_bool_constant_holds_zero_or_one_and_nothing_else() {
492        let held = |value: u64| {
493            let base = encode(
494                &Inst::Bool {
495                    dst: 1,
496                    value: false,
497                },
498                0,
499            )
500            .expect("encodes");
501            let mut bytes = *base.bytes();
502            bytes[8..16].copy_from_slice(&value.to_le_bytes());
503            decode(EncodedInst::from_bytes(bytes), 0)
504        };
505        assert_eq!(
506            held(0),
507            Ok(Inst::Bool {
508                dst: 1,
509                value: false
510            })
511        );
512        assert_eq!(
513            held(1),
514            Ok(Inst::Bool {
515                dst: 1,
516                value: true
517            })
518        );
519        assert_eq!(held(2), Err(Malformed::Bool(2)));
520        assert_eq!(held(u64::MAX), Err(Malformed::Bool(u64::MAX)));
521    }
522
523    /// A displacement that lands before the first instruction, or past what a
524    /// program counter can name, is not a program counter — which is a
525    /// different question from whether it is inside *this* function, and that
526    /// one is the verifier's.
527    #[test]
528    fn a_displacement_that_names_no_program_counter_is_refused() {
529        let jump = |pc: Pc, displacement: i64| {
530            let base = encode(&Inst::Jump { to: 0 }, 0).expect("encodes");
531            let mut bytes = *base.bytes();
532            bytes[8..16].copy_from_slice(&displacement.to_le_bytes());
533            decode(EncodedInst::from_bytes(bytes), pc)
534        };
535        assert_eq!(jump(0, -1), Ok(Inst::Jump { to: 0 }));
536        assert_eq!(
537            jump(0, -2),
538            Err(Malformed::Target {
539                pc: 0,
540                displacement: -2
541            })
542        );
543        assert_eq!(
544            jump(0, i64::MAX),
545            Err(Malformed::Target {
546                pc: 0,
547                displacement: i64::MAX
548            })
549        );
550        assert_eq!(
551            jump(Pc::MAX, i64::MIN),
552            Err(Malformed::Target {
553                pc: Pc::MAX,
554                displacement: i64::MIN
555            })
556        );
557    }
558
559    /// Nothing in the decoder panics, whatever the sixteen bytes are. The
560    /// format is internal, and a reader of it is still a reader of input.
561    #[test]
562    fn arbitrary_bytes_answer_rather_than_panic() {
563        let mut bytes = [0u8; EncodedInst::BYTES];
564        for seed in 0u32..4_000 {
565            for (at, byte) in bytes.iter_mut().enumerate() {
566                *byte = (seed.wrapping_mul(2_654_435_761).rotate_left(at as u32 * 3)) as u8;
567            }
568            let _ = decode(EncodedInst::from_bytes(bytes), seed);
569        }
570    }
571}
cove_ir/bytecode/decode.rs

cove_ir/bytecode/
decode.rs
