#![allow(dead_code)]
pub const ENQUEUE_TRAP: u16 = 0xA96F;
pub const ENQUEUE_TRAP_OFFSET: u16 = 0x016F;
pub const DEQUEUE_TRAP: u16 = 0xA96E;
pub const DEQUEUE_TRAP_OFFSET: u16 = 0x016E;
pub const Q_FLAGS_OFFSET: u32 = 0;
pub const Q_HEAD_OFFSET: u32 = 2;
pub const Q_TAIL_OFFSET: u32 = 6;
pub const Q_HDR_SIZE: u32 = 10;
pub const Q_LINK_OFFSET: u32 = 0;
pub const Q_TYPE_OFFSET: u32 = 4;
pub const Q_ELEM_HEADER_SIZE: u32 = 6;
pub const NO_ERR: i16 = 0;
pub const Q_ERR: i16 = -1;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct QueueHeader {
pub flags: u16,
pub head: u32,
pub tail: u32,
}
impl QueueHeader {
#[inline]
pub fn is_empty(&self) -> bool {
self.head == 0
}
pub fn from_bytes(bytes: &[u8; 10]) -> Self {
let flags = u16::from_be_bytes([bytes[0], bytes[1]]);
let head = u32::from_be_bytes([bytes[2], bytes[3], bytes[4], bytes[5]]);
let tail = u32::from_be_bytes([bytes[6], bytes[7], bytes[8], bytes[9]]);
Self { flags, head, tail }
}
pub fn to_bytes(&self) -> [u8; 10] {
let mut bytes = [0u8; 10];
bytes[0..2].copy_from_slice(&self.flags.to_be_bytes());
bytes[2..6].copy_from_slice(&self.head.to_be_bytes());
bytes[6..10].copy_from_slice(&self.tail.to_be_bytes());
bytes
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EnqueueEvaluation {
pub writes: Vec<(u32, u32)>,
}
pub fn evaluate_enqueue(
element: u32,
header: u32,
head: u32,
tail: u32,
mut read_link: impl FnMut(u32) -> u32,
) -> EnqueueEvaluation {
if element == 0 || header == 0 {
return EnqueueEvaluation { writes: Vec::new() };
}
let mut writes = Vec::with_capacity(3);
writes.push((element + Q_LINK_OFFSET, 0));
if head == 0 {
writes.push((header + Q_HEAD_OFFSET, element));
writes.push((header + Q_TAIL_OFFSET, element));
return EnqueueEvaluation { writes };
}
let current_tail = if tail != 0 {
tail
} else {
let mut cursor = head;
let mut loop_count = 0;
loop {
let next = read_link(cursor);
if next == 0 || loop_count > 100_000 {
break cursor;
}
cursor = next;
loop_count += 1;
}
};
writes.push((current_tail + Q_LINK_OFFSET, element));
writes.push((header + Q_TAIL_OFFSET, element));
EnqueueEvaluation { writes }
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DequeueEvaluation {
pub result: i16,
pub writes: Vec<(u32, u32)>,
}
pub fn evaluate_dequeue(
element: u32,
header: u32,
head: u32,
tail: u32,
mut read_link: impl FnMut(u32) -> u32,
) -> DequeueEvaluation {
if element == 0 || header == 0 || head == 0 {
return DequeueEvaluation {
result: Q_ERR,
writes: Vec::new(),
};
}
let mut prev = 0;
let mut current = head;
let mut loop_count = 0;
while current != 0 && loop_count <= 100_000 {
let next = read_link(current);
if current == element {
let mut writes = Vec::with_capacity(3);
if prev == 0 {
writes.push((header + Q_HEAD_OFFSET, next));
} else {
writes.push((prev + Q_LINK_OFFSET, next));
}
if tail == current {
writes.push((header + Q_TAIL_OFFSET, prev));
}
return DequeueEvaluation {
result: NO_ERR,
writes,
};
}
prev = current;
current = next;
loop_count += 1;
}
DequeueEvaluation {
result: Q_ERR,
writes: Vec::new(),
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashMap;
#[test]
fn test_trap_constants() {
assert_eq!(ENQUEUE_TRAP, 0xA96F);
assert_eq!(ENQUEUE_TRAP_OFFSET, 0x016F);
assert_eq!(DEQUEUE_TRAP, 0xA96E);
assert_eq!(DEQUEUE_TRAP_OFFSET, 0x016E);
assert_eq!(0xA800 | ENQUEUE_TRAP_OFFSET, ENQUEUE_TRAP);
assert_eq!(0xA800 | DEQUEUE_TRAP_OFFSET, DEQUEUE_TRAP);
}
#[test]
fn test_queue_header_round_trip() {
let qhdr = QueueHeader {
flags: 0x1234,
head: 0x0010_0000,
tail: 0x0020_0000,
};
let bytes = qhdr.to_bytes();
let decoded = QueueHeader::from_bytes(&bytes);
assert_eq!(decoded, qhdr);
assert!(!decoded.is_empty());
let empty = QueueHeader::default();
assert!(empty.is_empty());
}
#[test]
fn test_evaluate_enqueue_empty_queue() {
let eval = evaluate_enqueue(0x2000, 0x1000, 0, 0, |_| 0);
assert_eq!(
eval.writes,
vec![
(0x2000 + Q_LINK_OFFSET, 0),
(0x1000 + Q_HEAD_OFFSET, 0x2000),
(0x1000 + Q_TAIL_OFFSET, 0x2000),
]
);
}
#[test]
fn test_evaluate_enqueue_non_empty_queue() {
let eval = evaluate_enqueue(0x3000, 0x1000, 0x2000, 0x2000, |_| 0);
assert_eq!(
eval.writes,
vec![
(0x3000 + Q_LINK_OFFSET, 0),
(0x2000 + Q_LINK_OFFSET, 0x3000),
(0x1000 + Q_TAIL_OFFSET, 0x3000),
]
);
}
#[test]
fn test_evaluate_dequeue_head_element() {
let links: HashMap<u32, u32> = HashMap::from([(0x2000, 0x3000), (0x3000, 0)]);
let eval = evaluate_dequeue(0x2000, 0x1000, 0x2000, 0x3000, |ptr| {
links.get(&ptr).copied().unwrap_or(0)
});
assert_eq!(eval.result, NO_ERR);
assert_eq!(eval.writes, vec![(0x1000 + Q_HEAD_OFFSET, 0x3000)]);
}
#[test]
fn test_evaluate_dequeue_tail_element() {
let links: HashMap<u32, u32> = HashMap::from([(0x2000, 0x3000), (0x3000, 0)]);
let eval = evaluate_dequeue(0x3000, 0x1000, 0x2000, 0x3000, |ptr| {
links.get(&ptr).copied().unwrap_or(0)
});
assert_eq!(eval.result, NO_ERR);
assert_eq!(
eval.writes,
vec![
(0x2000 + Q_LINK_OFFSET, 0),
(0x1000 + Q_TAIL_OFFSET, 0x2000),
]
);
}
#[test]
fn test_evaluate_dequeue_sole_element() {
let links: HashMap<u32, u32> = HashMap::from([(0x2000, 0)]);
let eval = evaluate_dequeue(0x2000, 0x1000, 0x2000, 0x2000, |ptr| {
links.get(&ptr).copied().unwrap_or(0)
});
assert_eq!(eval.result, NO_ERR);
assert_eq!(
eval.writes,
vec![
(0x1000 + Q_HEAD_OFFSET, 0),
(0x1000 + Q_TAIL_OFFSET, 0),
]
);
}
#[test]
fn test_evaluate_dequeue_missing_element() {
let links: HashMap<u32, u32> = HashMap::from([(0x2000, 0x3000), (0x3000, 0)]);
let eval = evaluate_dequeue(0x9999, 0x1000, 0x2000, 0x3000, |ptr| {
links.get(&ptr).copied().unwrap_or(0)
});
assert_eq!(eval.result, Q_ERR);
assert!(eval.writes.is_empty());
}
#[test]
fn test_evaluate_null_parameters() {
let eval_enq = evaluate_enqueue(0, 0x1000, 0, 0, |_| 0);
assert!(eval_enq.writes.is_empty());
let eval_deq = evaluate_dequeue(0, 0x1000, 0x2000, 0x2000, |_| 0);
assert_eq!(eval_deq.result, Q_ERR);
assert!(eval_deq.writes.is_empty());
}
}