1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
use super::{
ByteWriter, Felt, OutputError, Serializable, StackTopState, StarkField, ToElements, Vec,
STACK_TOP_SIZE,
};
// STACK OUTPUTS
// ================================================================================================
/// Output container for Miden VM programs.
///
/// Miden program outputs contain the full state of the stack at the end of execution as well as the
/// addresses in the overflow table which are required to reconstruct the table (when combined with
/// the overflow values from the stack state).
///
/// `stack` is expected to be ordered as if the elements were popped off the stack one by one.
/// Thus, the value at the top of the stack is expected to be in the first position, and the order
/// of the rest of the output elements will also match the order on the stack.
///
/// `overflow_addrs` is expected to start with the `prev` address value from the first row in the
/// overflow table (the row representing the deepest element in the stack) and then be followed by
/// the address (`clk` value) of each row in the table starting from the deepest element in the
/// stack and finishing with the row which was added to the table last.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct StackOutputs {
/// The elements on the stack at the end of execution.
stack: Vec<u64>,
/// The overflow table row addresses required to reconstruct the final state of the table.
overflow_addrs: Vec<u64>,
}
impl StackOutputs {
// CONSTRUCTOR
// --------------------------------------------------------------------------------------------
/// Constructs a new [StackOutputs] struct from the provided stack elements and overflow
/// addresses.
///
/// # Errors
/// - If any of the provided stack elements are invalid field elements.
/// - If any of the provided overflow addresses are invalid field elements.
/// - If the number of stack elements is greater than `STACK_TOP_SIZE` (16) and `overflow_addrs`
/// does not contain exactly `stack.len() + 1 - STACK_TOP_SIZE` elements.
pub fn new(mut stack: Vec<u64>, overflow_addrs: Vec<u64>) -> Result<Self, OutputError> {
// Validate stack elements
if let Some(element) = find_invalid_elements(&stack) {
return Err(OutputError::InvalidStackElement(element));
}
// Validate overflow address elements
if let Some(element) = find_invalid_elements(&overflow_addrs) {
return Err(OutputError::InvalidOverflowAddress(element));
}
// pad stack to the `STACK_TOP_SIZE`
if stack.len() < STACK_TOP_SIZE {
stack.resize(STACK_TOP_SIZE, 0);
}
// validate overflow_addrs length
let expected_overflow_addrs_len = if stack.len() > STACK_TOP_SIZE {
stack.len() + 1 - STACK_TOP_SIZE
} else {
0
};
if overflow_addrs.len() != expected_overflow_addrs_len {
return Err(OutputError::InvalidOverflowAddressLength(
overflow_addrs.len(),
expected_overflow_addrs_len,
));
}
Ok(Self {
stack,
overflow_addrs,
})
}
pub fn from_elements(stack: Vec<Felt>, overflow_addrs: Vec<Felt>) -> Result<Self, OutputError> {
let stack = stack.iter().map(|&v| v.as_int()).collect::<Vec<_>>();
let overflow_addrs = overflow_addrs.iter().map(|&v| v.as_int()).collect::<Vec<_>>();
Self::new(stack, overflow_addrs)
}
// PUBLIC ACCESSORS
// --------------------------------------------------------------------------------------------
/// Returns the stack outputs, which is state of the stack at the end of execution converted to
/// integers.
pub fn stack(&self) -> &[u64] {
&self.stack
}
/// Returns the number of requested stack outputs or returns the full stack if fewer than the
/// requested number of stack values exist.
pub fn stack_truncated(&self, num_outputs: usize) -> &[u64] {
let len = self.stack.len().min(num_outputs);
&self.stack[..len]
}
/// Returns the state of the top of the stack at the end of execution.
pub fn stack_top(&self) -> StackTopState {
self.stack
.iter()
.take(STACK_TOP_SIZE)
.map(|v| Felt::new(*v))
.collect::<Vec<_>>()
.try_into()
.expect("failed to convert vector to array")
}
/// Returns the overflow address outputs, which are the addresses required to reconstruct the
/// overflow table (when combined with the stack overflow values) converted to integers.
pub fn overflow_addrs(&self) -> &[u64] {
&self.overflow_addrs
}
/// Returns true if the overflow table outputs are non-empty.
pub fn has_overflow(&self) -> bool {
!self.overflow_addrs.is_empty()
}
/// Returns the previous address `prev` for the first row in the stack overflow table
pub fn overflow_prev(&self) -> Felt {
Felt::new(self.overflow_addrs[0])
}
/// Returns (address, value) for all rows which were on the overflow table at the end of
/// execution in the order in which they were added to the table (deepest stack item first).
pub fn stack_overflow(&self) -> Vec<(Felt, Felt)> {
let mut overflow = Vec::with_capacity(self.overflow_addrs.len() - 1);
for (addr, val) in self
.overflow_addrs
.iter()
.skip(1)
.zip(self.stack.iter().skip(STACK_TOP_SIZE).rev())
{
overflow.push((Felt::new(*addr), Felt::new(*val)));
}
overflow
}
// PUBLIC MUTATORS
// --------------------------------------------------------------------------------------------
/// Returns mutable access to the stack outputs, to be used for testing or running examples.
/// TODO: this should be marked with #[cfg(test)] attribute, but that currently won't work with
/// the integration test handler util.
pub fn stack_mut(&mut self) -> &mut [u64] {
&mut self.stack
}
}
// HELPER FUNCTIONS
// ================================================================================================
/// Find and return the first invalid field element in the provided vector of elements.
fn find_invalid_elements(outputs: &[u64]) -> Option<u64> {
for val in outputs {
if *val >= Felt::MODULUS {
return Some(*val);
}
}
None
}
impl Serializable for StackOutputs {
fn write_into<W: ByteWriter>(&self, target: &mut W) {
// TODO the length of the stack, by design, will not be greater than `u32::MAX`. however,
// we must define a common serialization format as we might diverge from the implementation
// here and the one provided by default from winterfell.
// stack
debug_assert!(self.stack.len() <= u32::MAX as usize);
target.write_u32(self.stack.len() as u32);
self.stack.iter().copied().for_each(|v| target.write_u64(v));
// overflow addrs
debug_assert!(self.overflow_addrs.len() <= u32::MAX as usize);
target.write_u32(self.overflow_addrs.len() as u32);
self.overflow_addrs.iter().copied().for_each(|v| target.write_u64(v));
}
}
impl ToElements<Felt> for StackOutputs {
fn to_elements(&self) -> Vec<Felt> {
// infallible conversion from u64 to Felt is OK here because we check validity of u64
// values in the constructor
// TODO: change internal data types of self.stack and self.overflow_addrs to Felt?
self.stack
.iter()
.chain(self.overflow_addrs.iter())
.cloned()
.map(Felt::new)
.collect()
}
}