use miden::core::word
# CONSTANTS
# =================================================================================================
const LOWERBOUND_ARRAY_EVENT = event("miden::core::collections::sorted_array::lowerbound_array")
const LOWERBOUND_KEY_VALUE_EVENT = event("miden::core::collections::sorted_array::lowerbound_key_value")
# ===== ARRAY UTILITIES ============================================================================
#! Finds a value in a sorted array of words.
#!
#! **The input array must be sorted in non-decreasing lexicographic order.** The host event handler validates this and will return an error if the array is not sorted.
#!
#! Input: [VALUE, start_ptr, end_ptr]
#! Output: [is_value_found, value_ptr, start_ptr, end_ptr]
#!
#! # Panics
#!
#! Panics if:
#! - start_ptr, end_ptr are not word-aligned
#! - `start_ptr > end_ptr`
#!
#! Cycles:
#! Value exists: 46 cycles
#! Value doesn't exist and the array is empty: 25 cycles
#! Value doesn't exist and is smaller than all elements: 151 cycles
#! Value doesn't exist and is larger than all elements: 149 cycles
#! Value doesn't exist: 286 cycles
pub proc find_word
# Call the non-deterministic lowerbound advisor (5 cycles)
emit.LOWERBOUND_ARRAY_EVENT
adv_push adv_push
#=> [was_value_found, maybe_value_ptr, VALUE, start_ptr, end_ptr]
if.true
# assert `start_ptr <= maybe_value_ptr < end_ptr` (15 cycles)
dup dup.6 u32assert2.err="maybe_value_ptr is not u32"
u32gte assert.err="lowerbound_array invariant: maybe_value_ptr must be >= start_ptr"
dup dup.7 u32assert2.err="maybe_value_ptr is not u32"
u32lt assert.err="lowerbound_array invariant: maybe_value_ptr must be < end_ptr"
#=> [maybe_value_ptr, VALUE, start_ptr, end_ptr]
# dereference maybe_value_ptr (8 cycles)
dup movdn.5 padw movup.4 mem_loadw_le
#=> [MAYBE_VALUE, VALUE, maybe_value_ptr, start_ptr, end_ptr]
# check if it matches the requested VALUE (15 cycles)
exec.word::eq
dup assert.err="lowerbound_array invariant: value_ptr must point to VALUE"
#=> [is_value_found, maybe_value_ptr, start_ptr, end_ptr]
else
# the value was not found
# pre-compute is_start_ptr, is_end_ptr to reduce the depth of the generated MAST
# (6 cycles)
dup.6 dup.1 eq
#=> [is_end_ptr, maybe_value_ptr, VALUE, start_ptr, end_ptr]
dup.6 dup.2 eq
#=> [is_start_ptr, is_end_ptr, maybe_value_ptr, VALUE, start_ptr, end_ptr]
if.true
# the value was not found, and `maybe_value_ptr = start_ptr`
if.true
# the list is empty and `start_ptr = end_ptr` (both are equal to `maybe_value_ptr`)
#=> [maybe_value_ptr = start_ptr = end_ptr, VALUE, start_ptr, end_ptr]
# Prepare output (6 cycles)
movdn.4 dropw push.0
#=> [is_value_found = 0, value_ptr = start_ptr, start_ptr, end_ptr]
else
# the value was not found, `maybe_value_ptr = start_ptr`, and the list is not empty
# assert `the value at start_ptr > VALUE`
#=> [maybe_value_ptr = start_ptr, VALUE, start_ptr, end_ptr]
movdn.4
#=> [VALUE, maybe_value_ptr, start_ptr, end_ptr]
# dereference maybe_value_ptr (7 cycles)
dup.4 padw movup.4 mem_loadw_le
#=> [FIRST_WORD, VALUE, maybe_value_ptr = start_ptr, start_ptr, end_ptr]
# there was no match, the first array element must be larger than VALUE
# (123 cycles)
exec.word::lt
assert.err="lowerbound_array invariant: start_ptr must point to a word greater than VALUE"
# No value was found (1 cycle)
push.0
#=> [is_value_found = 0, maybe_value_ptr = start_ptr, start_ptr, end_ptr]
end
else
if.true
# the value was not found, `maybe_value_ptr = end_ptr`
# the list is not empty, otherwise `maybe_value_ptr = start_ptr` and handled above
# assert `the value before end_ptr < VALUE`
#=> [maybe_value_ptr = end_ptr, VALUE, start_ptr, end_ptr]
# fetch the last word in the array (10 cycles)
dup movdn.5 sub.4 padw movup.4 mem_loadw_le
#=> [LAST_WORD, VALUE, maybe_value_ptr = end_ptr, start_ptr, end_ptr]
# there was no match, the last array element must be smaller than VALUE
# (119 cycles)
exec.word::gt
assert.err="lowerbound_array invariant: last word must be smaller than VALUE"
# No value was found (1 cycle)
push.0
#=> [is_value_found = 0, maybe_value_ptr = end_ptr, start_ptr, end_ptr]
else
# The value was not found, and the maybe_value_ptr is neither the start nor the end
# of the list. Make sure that:
# - `start_ptr <= maybe_value_ptr < end_ptr`, and
# - `the value at maybe_value_ptr-1 < VALUE`, and
# - `the value at maybe_value_ptr > VALUE`.
# `maybe_value_ptr` must already be word aligned to allow reading values.
#=> [maybe_value_ptr, VALUE, start_ptr, end_ptr]
# `maybe_value_ptr` bounds check
dup dup.6 u32assert2.err="maybe_value_ptr is not u32"
u32gte assert.err="lowerbound_array invariant: maybe_value_ptr must be >= start_ptr"
dup dup.7 u32assert2.err="maybe_value_ptr is not u32"
u32lt assert.err="lowerbound_array invariant: maybe_value_ptr must be < end_ptr"
# Duplicate VALUE word (5 cycles)
movdn.4 dupw
#=> [VALUE, VALUE, maybe_value_ptr, start_ptr, end_ptr]
# dereference maybe_value_ptr (8 cycles)
padw dup.12 mem_loadw_le
#=> [MAYBE_VALUE, VALUE, VALUE, maybe_value_ptr, start_ptr, end_ptr]
# there was no match, MAYBE_VALUE must be larger than VALUE (123 cycles)
exec.word::lt
assert.err="lowerbound_array invariant: *maybe_value_ptr must be greater than VALUE"
# dereference `maybe_value_ptr-4` (11 cycles)
padw dup.8 sub.4 mem_loadw_le
#=> [MAYBE_VALUE_PREV, VALUE, maybe_value_ptr, start_ptr, end_ptr]
# there was no match, MAYBE_VALUE_PREV must be smaller than VALUE (119 cycles)
exec.word::gt
assert.err="lowerbound_array invariant: *(maybe_value_ptr-4) must be smaller than VALUE"
# No value was found (1 cycle)
push.0
#=> [is_value_found = 0, maybe_value_ptr, start_ptr, end_ptr]
end
end
end
end
# ===== KEY-VALUE UTILITIES ============================================================================
#! Finds a key in a sorted array of (key, value) word tuples.
#!
#! **The keys in the array must be sorted in non-decreasing lexicographic order.** The host event handler validates this and will return an error if the keys are not sorted.
#!
#! Inputs: [KEY, start_ptr, end_ptr]
#! Outputs: [is_key_found, key_ptr, start_ptr, end_ptr]
#!
#! # Panics
#!
#! Panics if:
#! - start_ptr is not word-aligned
#! - end_ptr is not double-word-aligned with the start_ptr:
#! - `(end_ptr - start_ptr)` must be divisible by 8
#! - `start_ptr > end_ptr`
pub proc find_key_value
push.1
# => [use_full_key = 1, KEY, start_ptr, end_ptr]
movdn.6
# => [KEY, start_ptr, end_ptr, use_full_key]
exec.find_partial_key_value
# => [is_key_found, key_ptr, start_ptr, end_ptr]
end
#! Finds a half-key in a sorted array of (key, value) word tuples.
#!
#! Half-key means that, out of the keys in the array, only half of the key - the most significant
#! element (prefix) and the second most significant element (suffix) - need to match.
#!
#! **The half-keys in the array must be sorted in non-decreasing lexicographic order.** The host event handler validates this and will return an error if the half-keys are not sorted.
#!
#! Inputs: [key_suffix, key_prefix, start_ptr, end_ptr]
#! Output: [is_key_found, key_ptr, start_ptr, end_ptr]
#!
#! # Panics
#!
#! Panics if:
#! - start_ptr is not word-aligned
#! - end_ptr is not double-word-aligned with the start_ptr:
#! - `(end_ptr - start_ptr)` must be divisible by 8
#! - `start_ptr > end_ptr`
pub proc find_half_key_value
# Build KEY with key_prefix at word[3] (most significant in BE) and key_suffix at word[2]
# word[0] and word[1] are 0 (will be zeroed in half-key comparison anyway)
push.0 push.0
# => [0, 0, key_suffix, key_prefix, start_ptr, end_ptr]
# KEY = [0, 0, key_suffix, key_prefix] with w0=0 on top, w3=key_prefix
push.0
# => [use_full_key = 0, KEY, start_ptr, end_ptr]
movdn.6
# => [KEY, start_ptr, end_ptr, use_full_key]
exec.find_partial_key_value
# => [is_key_found, key_ptr, start_ptr, end_ptr]
end
#! Finds a key in a sorted array of (key, value) word tuples.
#!
#! - If use_full_key = 1, then a match on the entire KEY is required.
#! - If use_full_key = 0, then the KEY's two least significant elements *must* be zeroes and
#! upon loading the key for comparison, its two least significant elements are zeroized.
#! This effectively means that only a match on the two most significant elements is required.
#!
#! **The keys in the array must be sorted in non-decreasing lexicographic order.** The host event handler validates this and will return an error if the keys are not sorted.
#!
#! Input: [KEY, start_ptr, end_ptr, use_full_key]
#! Output: [is_key_found, key_ptr, start_ptr, end_ptr]
#!
#! # Panics
#!
#! Panics if:
#! - start_ptr is not word-aligned
#! - end_ptr is not double-word-aligned with the start_ptr:
#! - `(end_ptr - start_ptr)` must be divisible by 8
#! - `start_ptr > end_ptr`
#!
#! Cycles:
#! Key exists: 70 cycles
#! Key doesn't exist and the array is empty: 25 cycles
#! Key doesn't exist and is smaller than all stored keys: 166 cycles
#! Key doesn't exist and is larger than all stored keys: 162 cycles
#! Key doesn't exist: 322 cycles
@locals(1)
proc find_partial_key_value
# Call the non-deterministic lowerbound advisor (5 cycles)
emit.LOWERBOUND_KEY_VALUE_EVENT
# => [KEY, start_ptr, end_ptr, use_full_key]
# store use_full_key for later
movup.6 loc_store.0
# => [KEY, start_ptr, end_ptr]
adv_push adv_push
#=> [was_key_found, maybe_key_ptr, KEY, start_ptr, end_ptr]
if.true
# assert `start_ptr <= maybe_key_ptr < end_ptr` (15 cycles)
dup dup.6 u32assert2.err="maybe_key_ptr is not u32"
u32gte assert.err="lowerbound_key_value invariant: maybe_key_ptr must be >= start_ptr"
dup dup.7 u32assert2.err="maybe_key_ptr is not u32"
u32lt assert.err="lowerbound_key_value invariant: maybe_key_ptr must be < end_ptr"
#=> [maybe_key_ptr, KEY, start_ptr, end_ptr]
# make sure maybe_key_ptr is pointing to a key, not value (10 cycles)
dup dup.6 sub u32mod.8 assertz.err="lowerbound_key_value invariant: key_ptr must be double-word aligned with start_ptr"
#=> [maybe_key_ptr, KEY, start_ptr, end_ptr]
# dereference maybe_key_ptr (22 cycles)
dup movdn.5
#=> [maybe_key_ptr, KEY, maybe_key_ptr, start_ptr, end_ptr]
loc_load.0 exec.load_key
#=> [MAYBE_KEY, KEY, maybe_key_ptr, start_ptr, end_ptr]
# check if it matches the requested KEY (15 cycles)
exec.word::eq
dup assert.err="lowerbound_key_value invariant: key_ptr must point to KEY"
#=> [is_key_found, maybe_key_ptr, start_ptr, end_ptr]
else
# pre-compute is_start_ptr, is_end_ptr to reduce the depth of the
# generated MAST (6 cycles)
dup.6 dup.1 eq
#=> [is_end_ptr, maybe_key_ptr, KEY, start_ptr, end_ptr]
dup.6 dup.2 eq
#=> [is_start_ptr, is_end_ptr, maybe_key_ptr, KEY, start_ptr, end_ptr]
if.true
# the key was not found, `maybe_key_ptr = start_ptr`
if.true
# the list is empty and `start_ptr = end_ptr` (both are equal to `maybe_key_ptr`)
#=> [maybe_key_ptr = start_ptr = end_ptr, KEY, start_ptr, end_ptr]
# Prepare output (6 cycles)
movdn.4 dropw push.0
#=> [is_key_found = 0, key_ptr = start_ptr, start_ptr, end_ptr]
else
# the key was not found, `maybe_key_ptr = start_ptr` and the list is not empty
# assert `the key at start_ptr > KEY`
#=> [maybe_key_ptr = start_ptr, KEY, start_ptr, end_ptr]
# load key (22 cycles)
dup movdn.5
#=> [maybe_key_ptr, KEY, maybe_key_ptr, start_ptr, end_ptr]
loc_load.0 exec.load_key
#=> [FIRST_KEY, KEY, maybe_key_ptr = start_ptr, start_ptr, end_ptr]
# there was no match, the first map element must be larger than KEY
# (123 cycles)
exec.word::lt
assert.err="lowerbound_key_value invariant: start_ptr must point to a key greater than KEY"
# No value was found (1 cycle)
push.0
#=> [is_key_found = 0, maybe_key_ptr = start_ptr, start_ptr, end_ptr]
end
else
if.true
# the key was not found, `maybe_key_ptr = end_ptr`
# the list is not empty, otherwise `maybe_key_ptr = start_ptr` and handled above
# assert `the key before end_ptr < KEY`
#=> [maybe_key_ptr = end_ptr, KEY, start_ptr, end_ptr]
# fetch the last key in the array (23 cycles)
dup movdn.5 sub.8
#=> [maybe_key_ptr-8, KEY, maybe_key_ptr, start_ptr, end_ptr]
loc_load.0 exec.load_key
#=> [LAST_KEY, KEY, maybe_key_ptr = end_ptr, start_ptr, end_ptr]
# there was no match, the last map element must be smaller than KEY
# (119 cycles)
exec.word::gt
assert.err="lowerbound_key_value invariant: last key-value pair must be smaller than KEY"
# No value was found (1 cycle)
push.0
#=> [is_key_found = 0, maybe_key_ptr = end_ptr, start_ptr, end_ptr]
else
# The key was not found, and the maybe_key_ptr is neither the start nor the end
# of the list. Make sure that:
# - `start_ptr <= maybe_key_ptr < end_ptr`, and
# - `maybe_key_ptr` is word aligned with `start_ptr`, and
# - `the key at maybe_key_ptr-1 < KEY`, and
# - `the key at maybe_key_ptr > KEY`
#=> [maybe_key_ptr, KEY, start_ptr, end_ptr]
# `maybe_key_ptr` bounds check
dup dup.6 u32assert2.err="maybe_key_ptr is not u32"
u32gte assert.err="lowerbound_key_value invariant: maybe_key_ptr must be >= start_ptr"
dup dup.7 u32assert2.err="maybe_key_ptr is not u32"
u32lt assert.err="lowerbound_key_value invariant: maybe_key_ptr must be < end_ptr"
# make sure maybe_key_ptr is pointing to a key, not value (10 cycles)
dup dup.6 sub u32assert2.err="maybe_key_ptr is not u32"
u32mod.8 assertz.err="lowerbound_key_value invariant: key_ptr must be double-word aligned with start_ptr"
# Duplicate KEY word (5 cycles)
movdn.4 dupw
#=> [KEY, KEY, maybe_key_ptr, start_ptr, end_ptr]
# load key (21 cycles)
dup.8 loc_load.0 exec.load_key
#=> [MAYBE_KEY, KEY, KEY, maybe_key_ptr, start_ptr, end_ptr]
# there was no match, `*maybe_key_ptr` must be larger than KEY (123 cycles)
exec.word::lt
assert.err="lowerbound_key_value invariant: MAYBE_KEY must be greater than KEY"
#=> [KEY, maybe_key_ptr, start_ptr, end_ptr]
# dereference `maybe_key_ptr-8` (previous key) (22 cycles)
dup.4 sub.8
#=> [maybe_key_ptr-8, KEY, maybe_key_ptr, start_ptr, end_ptr]
loc_load.0 exec.load_key
#=> [MAYBE_KEY_PREV, KEY, maybe_key_ptr, start_ptr, end_ptr]
# there was no match, `*(maybe_key_ptr-8)` must be smaller than KEY (119 cycles)
exec.word::gt
assert.err="lowerbound_key_value invariant: MAYBE_KEY_PREV must be smaller than KEY"
# No value was found (1 cycle)
push.0
#=> [is_key_found = 0, maybe_key_ptr, start_ptr, end_ptr]
end
end
end
end
#! Loads a key from the pointer.
#!
#! If use_full_key is 0, the key is loaded with the two least significant elements (word[0] and
#! word[1]) set to zero, keeping only word[2] and word[3] for half-key comparison.
#! If use_full_key is 1, the full key is loaded unchanged.
#!
#! This procedure avoids branches as an optimization.
#!
#! Inputs: [use_full_key, key_ptr]
#! Outputs: [KEY]
#!
#! Cycles: 16
proc load_key
padw movup.5 mem_loadw_le
# => [w0, w1, w2, w3, use_full_key]
# For half-key comparison (use_full_key=0), zero w0 and w1 (the BE least significant elements)
# keeping w2 and w3 for comparison
dup.4 mul
# => [w0', w1, w2, w3, use_full_key] where w0' = w0 * use_full_key
swap dup.4 mul swap
# => [w0', w1', w2, w3, use_full_key] where w1' = w1 * use_full_key
movup.4 drop
# => [w0', w1', w2, w3]
end