hashx/program.rs
1//! Define the internal hash program representation used by HashX.
2
3use crate::generator::Generator;
4use crate::register::{RegisterFile, RegisterId};
5use crate::Error;
6use fixed_capacity_vec::FixedCapacityVec;
7use rand_core::RngCore;
8use std::fmt;
9use std::ops::BitXor;
10
11/// Maximum number of instructions in the program
12///
13/// Programs with fewer instructions may be generated (for example, after
14/// a timing stall when register allocation fails) but they will not pass
15/// whole-program constraint tests.
16pub(crate) const NUM_INSTRUCTIONS: usize = 512;
17
18/// Type alias for a full-size array of [`Instruction`]s
19pub(crate) type InstructionArray = [Instruction; NUM_INSTRUCTIONS];
20
21/// Type alias for a [`FixedCapacityVec`] that can build [`InstructionArray`]s
22pub(crate) type InstructionVec = FixedCapacityVec<Instruction, NUM_INSTRUCTIONS>;
23
24/// Define the HashX virtual instruction set
25#[derive(Debug, Clone, Eq, PartialEq)]
26pub(crate) enum Instruction {
27 /// 64-bit multiply of two registers, discarding overflow.
28 Mul {
29 /// Destination register
30 dst: RegisterId,
31 /// Source register
32 src: RegisterId,
33 },
34
35 /// Unsigned 64x64 to 128-bit multiply, saving only the upper half.
36 ///
37 /// Result is written to dst, and the low 32 bits are saved for the
38 /// next Branch test.
39 UMulH {
40 /// Destination register
41 dst: RegisterId,
42 /// Source register
43 src: RegisterId,
44 },
45
46 /// Signed 64x64 to 128-bit multiply, saving only the upper half.
47 ///
48 /// Result is written to dst, and the low 32 bits are saved for the
49 /// next Branch test.
50 SMulH {
51 /// Destination register
52 dst: RegisterId,
53 /// Source register
54 src: RegisterId,
55 },
56
57 /// Shift source register left by a constant amount, add, discard overflow.
58 AddShift {
59 /// Destination register
60 dst: RegisterId,
61 /// Source register
62 src: RegisterId,
63 /// Number of bits to left shift by (0..=3 only)
64 left_shift: u8,
65 },
66
67 /// 64-bit addition by a sign-extended 32-bit constant.
68 AddConst {
69 /// Destination register
70 dst: RegisterId,
71 /// Source immediate, sign-extended from 32-bit to 64-bit
72 src: i32,
73 },
74
75 /// 64-bit subtraction (dst - src), discarding overflow.
76 Sub {
77 /// Destination register
78 dst: RegisterId,
79 /// Source register
80 src: RegisterId,
81 },
82
83 /// 64-bit XOR of two registers.
84 Xor {
85 /// Destination register
86 dst: RegisterId,
87 /// Source register
88 src: RegisterId,
89 },
90
91 /// XOR a 64-bit register with a sign-extended 32-bit constant.
92 XorConst {
93 /// Destination register
94 dst: RegisterId,
95 /// Source immediate, sign-extended from 32-bit to 64-bit
96 src: i32,
97 },
98
99 /// Rotate a 64-bit register right by a constant amount.
100 Rotate {
101 /// Destination register
102 dst: RegisterId,
103 /// Number of bits to rotate right by (0..=63 only)
104 right_rotate: u8,
105 },
106
107 /// Become the target for the next taken branch, if any.
108 Target,
109
110 /// One-shot conditional branch to the last Target.
111 Branch {
112 /// 32-bit branch condition mask
113 ///
114 /// This is tested against the last `UMulH`/`SMulH` result. (The low 32
115 /// bits of the instruction result, which itself is the upper 64 bits
116 /// of the multiplication result.)
117 ///
118 /// If `(result & mask)` is zero and no branches have been previously
119 /// taken, we jump back to the Target and remember not to take any
120 /// future branches. A well formed program will always have a `Target`
121 /// prior to any `Branch`.
122 mask: u32,
123 },
124}
125
126/// An instruction operation, without any of its arguments
127#[derive(Debug, Clone, Copy, Eq, PartialEq)]
128pub(crate) enum Opcode {
129 /// Opcode for [`Instruction::Mul`]
130 Mul,
131 /// Opcode for [`Instruction::UMulH`]
132 UMulH,
133 /// Opcode for [`Instruction::SMulH`]
134 SMulH,
135 /// Opcode for [`Instruction::AddShift`]
136 AddShift,
137 /// Opcode for [`Instruction::AddConst`]
138 AddConst,
139 /// Opcode for [`Instruction::Sub`]
140 Sub,
141 /// Opcode for [`Instruction::Xor`]
142 Xor,
143 /// Opcode for [`Instruction::XorConst`]
144 XorConst,
145 /// Opcode for [`Instruction::Rotate`]
146 Rotate,
147 /// Opcode for [`Instruction::Target`]
148 Target,
149 /// Opcode for [`Instruction::Branch`]
150 Branch,
151}
152
153impl Instruction {
154 /// Get this instruction's [`Opcode`].
155 #[inline(always)]
156 pub(crate) fn opcode(&self) -> Opcode {
157 match self {
158 Instruction::AddConst { .. } => Opcode::AddConst,
159 Instruction::AddShift { .. } => Opcode::AddShift,
160 Instruction::Branch { .. } => Opcode::Branch,
161 Instruction::Mul { .. } => Opcode::Mul,
162 Instruction::Rotate { .. } => Opcode::Rotate,
163 Instruction::SMulH { .. } => Opcode::SMulH,
164 Instruction::Sub { .. } => Opcode::Sub,
165 Instruction::Target => Opcode::Target,
166 Instruction::UMulH { .. } => Opcode::UMulH,
167 Instruction::Xor { .. } => Opcode::Xor,
168 Instruction::XorConst { .. } => Opcode::XorConst,
169 }
170 }
171
172 /// Get this instruction's destination register, if any.
173 #[inline(always)]
174 pub(crate) fn destination(&self) -> Option<RegisterId> {
175 match self {
176 Instruction::AddConst { dst, .. } => Some(*dst),
177 Instruction::AddShift { dst, .. } => Some(*dst),
178 Instruction::Branch { .. } => None,
179 Instruction::Mul { dst, .. } => Some(*dst),
180 Instruction::Rotate { dst, .. } => Some(*dst),
181 Instruction::SMulH { dst, .. } => Some(*dst),
182 Instruction::Sub { dst, .. } => Some(*dst),
183 Instruction::Target => None,
184 Instruction::UMulH { dst, .. } => Some(*dst),
185 Instruction::Xor { dst, .. } => Some(*dst),
186 Instruction::XorConst { dst, .. } => Some(*dst),
187 }
188 }
189}
190
191/// Generated `HashX` program, as a boxed array of instructions
192#[derive(Clone)]
193pub struct Program(Box<InstructionArray>);
194
195impl fmt::Debug for Program {
196 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
197 writeln!(f, "Program {{")?;
198 for (addr, inst) in self.0.iter().enumerate() {
199 writeln!(f, " [{:3}]: {:?}", addr, inst)?;
200 }
201 write!(f, "}}")
202 }
203}
204
205impl Program {
206 /// Generate a new `Program` from an arbitrary [`RngCore`] implementer
207 ///
208 /// This can return [`Error::ProgramConstraints`] if the HashX
209 /// post-generation program verification fails. During normal use this
210 /// will happen once per several thousand random seeds, and the caller
211 /// should skip to another seed.
212 pub(crate) fn generate<T: RngCore>(rng: &mut T) -> Result<Self, Error> {
213 let mut instructions = FixedCapacityVec::new();
214 Generator::new(rng).generate_program(&mut instructions)?;
215 Ok(Program(
216 instructions
217 .try_into()
218 .map_err(|_| ())
219 .expect("wrong length!"),
220 ))
221 }
222
223 /// Reference implementation for `Program` behavior
224 ///
225 /// Run the program from start to finish, with up to one branch,
226 /// in the provided register file.
227 pub(crate) fn interpret(&self, regs: &mut RegisterFile) {
228 let mut program_counter = 0;
229 let mut allow_branch = true;
230 let mut branch_target = None;
231 let mut mulh_result: u32 = 0;
232
233 /// Common implementation for binary operations on registers
234 macro_rules! binary_reg_op {
235 ($dst:ident, $src:ident, $fn:ident, $pc:ident) => {{
236 let a = regs.load(*$dst);
237 let b = regs.load(*$src);
238 regs.store(*$dst, a.$fn(b));
239 $pc
240 }};
241 }
242
243 /// Common implementation for binary operations with a const operand
244 macro_rules! binary_const_op {
245 ($dst:ident, $src:ident, $fn:ident, $pc:ident) => {{
246 let a = regs.load(*$dst);
247 let b_sign_extended = i64::from(*$src) as u64;
248 regs.store(*$dst, a.$fn(b_sign_extended));
249 $pc
250 }};
251 }
252
253 /// Common implementation for wide multiply operations
254 ///
255 /// This stores the low 32 bits of its result for later branch tests.
256 macro_rules! mulh_op {
257 ($dst:ident, $src:ident, $sign:ty, $wide:ty, $pc:ident) => {{
258 let a = <$wide>::from(regs.load(*$dst) as $sign);
259 let b = <$wide>::from(regs.load(*$src) as $sign);
260 let r = (a.wrapping_mul(b) >> 64) as u64;
261 mulh_result = r as u32;
262 regs.store(*$dst, r);
263 $pc
264 }};
265 }
266
267 while program_counter < self.0.len() {
268 let next_pc = program_counter + 1;
269 program_counter = match &self.0[program_counter] {
270 Instruction::Target => {
271 branch_target = Some(program_counter);
272 next_pc
273 }
274
275 Instruction::Branch { mask } => {
276 if allow_branch && (mask & mulh_result) == 0 {
277 allow_branch = false;
278 branch_target
279 .expect("generated programs always have a target before branch")
280 } else {
281 next_pc
282 }
283 }
284
285 Instruction::AddShift {
286 dst,
287 src,
288 left_shift,
289 } => {
290 let a = regs.load(*dst);
291 let b = regs.load(*src);
292 let r = a.wrapping_add(b.wrapping_shl((*left_shift).into()));
293 regs.store(*dst, r);
294 next_pc
295 }
296
297 Instruction::Rotate { dst, right_rotate } => {
298 let a = regs.load(*dst);
299 let r = a.rotate_right((*right_rotate).into());
300 regs.store(*dst, r);
301 next_pc
302 }
303
304 Instruction::Mul { dst, src } => binary_reg_op!(dst, src, wrapping_mul, next_pc),
305 Instruction::Sub { dst, src } => binary_reg_op!(dst, src, wrapping_sub, next_pc),
306 Instruction::Xor { dst, src } => binary_reg_op!(dst, src, bitxor, next_pc),
307 Instruction::UMulH { dst, src } => mulh_op!(dst, src, u64, u128, next_pc),
308 Instruction::SMulH { dst, src } => mulh_op!(dst, src, i64, i128, next_pc),
309 Instruction::XorConst { dst, src } => binary_const_op!(dst, src, bitxor, next_pc),
310 Instruction::AddConst { dst, src } => {
311 binary_const_op!(dst, src, wrapping_add, next_pc)
312 }
313 }
314 }
315 }
316}
317
318impl<'a> From<&'a Program> for &'a InstructionArray {
319 #[inline(always)]
320 fn from(prog: &'a Program) -> Self {
321 &prog.0
322 }
323}