use.std::word
# CONSTANTS
# =================================================================================================
const.LOWERBOUND_ARRAY_EVENT=event("stdlib::collections::sorted_array::lowerbound_array")
const.LOWERBOUND_KEY_VALUE_EVENT=event("stdlib::collections::sorted_array::lowerbound_key_value")
# ===== ARRAY UTILITIES ============================================================================
#! Finds a value in a sorted array of words.
#!
#! This function will crash if the following conditions aren't met:
#! - words must be sorted in non-decreasing order,
#! - start_ptr, end_ptr are word-aligned
#! - `start_ptr <= end_ptr`
#!
#! Input: [VALUE, start_ptr, end_ptr]
#! Output: [is_value_found, value_ptr, 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
export.find_word
# Call the non-deterministic lowerbound advisor (5 cycles)
emit.LOWERBOUND_ARRAY_EVENT
adv_push.2
#=> [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 < start_ptr"
dup dup.7 u32assert2.err="maybe_value_ptr is not u32"
u32lt assert.err="lowerbound_array invariant: maybe_value_ptr >= end_ptr"
#=> [maybe_value_ptr, VALUE, start_ptr, end_ptr]
# dereference maybe_value_ptr (8 cycles)
dup movdn.5 padw movup.4 mem_loadw_be
#=> [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 not pointing 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_be
#=> [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 not 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_be
#=> [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 not 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:
# - `the value at maybe_value_ptr-1 < VALUE`, and
# - `the value at maybe_value_ptr > VALUE`
#=> [maybe_value_ptr, VALUE, start_ptr, 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_be
#=> [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 not greater than VALUE"
# dereference `maybe_value_ptr-4` (11 cycles)
padw dup.8 sub.4 mem_loadw_be
#=> [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) not 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.
#!
#! Inputs: [KEY, start_ptr, end_ptr]
#! Outputs: [is_key_found, key_ptr, start_ptr, end_ptr]
#!
#! # Panics
#!
#! Panics if:
#! - keys are not sorted in non-decreasing order,
#! - 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`
#!
#! Inputs: [KEY, start_ptr, end_ptr]
#! Output: [is_key_found, key_ptr, start_ptr, end_ptr]
export.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.
#!
#! Inputs: [key_prefix, key_suffix, start_ptr, end_ptr]
#! Output: [is_key_found, key_ptr, start_ptr, end_ptr]
#!
#! # Panics
#!
#! Panics if:
#! - keys are not sorted in non-decreasing order,
#! - 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`
export.find_half_key_value
push.0 movdn.2 push.0 movdn.2
# => [key_prefix, key_suffix, 0, 0, start_ptr, end_ptr]
# => [KEY, start_ptr, end_ptr]
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.
#!
#! Input: [KEY, start_ptr, end_ptr, use_full_key]
#! Output: [is_key_found, key_ptr, start_ptr, end_ptr]
#!
#! # Panics
#!
#! Panics if:
#! - keys are not sorted in non-decreasing order,
#! - 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
proc.find_partial_key_value.1
# 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.2
#=> [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 < start_ptr"
dup dup.7 u32assert2.err="maybe_key_ptr is not u32"
u32lt assert.err="lowerbound_key_value invariant: maybe_key_ptr >= 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 not pointing 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_value_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 not 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_value_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 not 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:
# - `the key at maybe_key_ptr-1 < KEY`, and
# - `the key at maybe_key_ptr > KEY`
#=> [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 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 not 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 not 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 set to zero,
#! e.g.: [key3, key2, 0, 0], while if it is 1, the full key [key3, key2, key1, key0] is loaded.
#!
#! 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_be
# => [FULL_KEY, use_full_key]
# multiply the two least significant elements by use_full_key
movup.3 dup.4 mul
movup.3 movup.4 mul
movup.3 movup.3
# => [KEY]
end