dymokomi/luce-browser-foundation
Source of release 0.6.0
0.6.0 / src / ak / circular_buffer_2.lucb
#==============================================================================================
#
# circular_buffer_2 - SearchableCircularBuffer: seekback search with a chunk-hash index
#
# DESCRIPTION:
# Port of AK/CircularBuffer.cpp (lines 278-587). SearchableCircularBuffer embeds its
# CircularBuffer base (`circular_buffer`); the base's members are called on it. The
# chunk hash is StringView::hash of the chunk's bytes, which is string_hash of them.
#
#==============================================================================================
# The length of an optional match (only read when it is present).
func searchable_match_length(match_: SearchableCircularBufferMatch?) -> usize:
let found = match_ else return 0
return found.length
# StringView { bytes }.hash(): string_hash of the bytes (0 for none).
func searchable_chunk_hash(bytes: const u8[]) -> u32:
if bytes.length == 0:
return 0
return string_hash(bytes.data, bytes.length)
## Ported from AK/CircularBuffer.cpp:280 AK::SearchableCircularBuffer::SearchableCircularBuffer.
pub func searchable_circular_buffer_construct(this: SearchableCircularBuffer*, buffer: ByteBuffer):
circular_buffer_construct(&this.circular_buffer, buffer)
## Ported from AK/CircularBuffer.cpp:285 AK::SearchableCircularBuffer::create_empty.
pub func searchable_circular_buffer_create_empty(size: usize) -> SearchableCircularBuffer!:
let temporary_buffer = try byte_buffer_create_uninitialized(size)
var circular_buffer: SearchableCircularBuffer
searchable_circular_buffer_construct(&circular_buffer, temporary_buffer)
return circular_buffer
## Ported from AK/CircularBuffer.cpp:294 AK::SearchableCircularBuffer::create_initialized.
pub func searchable_circular_buffer_create_initialized(buffer: ByteBuffer) -> SearchableCircularBuffer!:
var circular_buffer: SearchableCircularBuffer
searchable_circular_buffer_construct(&circular_buffer, buffer)
circular_buffer.circular_buffer.m_used_space = byte_buffer_size(&circular_buffer.circular_buffer.m_buffer)
var i: usize = 0
while i + searchable_circular_buffer_hash_chunk_size <= byte_buffer_size(&circular_buffer.circular_buffer.m_buffer):
let chunk = byte_buffer_span(&circular_buffer.circular_buffer.m_buffer)[i..<(i + searchable_circular_buffer_hash_chunk_size)]
try searchable_circular_buffer_insert_location_hash(&circular_buffer, chunk, i)
i += 1
return circular_buffer
## Ported from AK/CircularBuffer.cpp:306 AK::SearchableCircularBuffer::read.
# These functions update the read pointer, so we need to hash any data that we have processed.
pub func searchable_circular_buffer_read(this: SearchableCircularBuffer*, bytes: u8[]) -> u8[]!:
let read_bytes_span = circular_buffer_read(&this.circular_buffer, bytes)
try searchable_circular_buffer_hash_last_bytes(this, read_bytes_span.length)
return read_bytes_span
## Ported from AK/CircularBuffer.cpp:313 AK::SearchableCircularBuffer::discard.
pub func searchable_circular_buffer_discard(this: SearchableCircularBuffer*, discarded_bytes: usize) -> !:
try circular_buffer_discard(&this.circular_buffer, discarded_bytes)
try searchable_circular_buffer_hash_last_bytes(this, discarded_bytes)
## Ported from AK/CircularBuffer.cpp:320 AK::SearchableCircularBuffer::flush_to_stream.
pub func searchable_circular_buffer_flush_to_stream(this: SearchableCircularBuffer*, stream: Stream*) -> usize!:
let flushed_byte_count = try circular_buffer_flush_to_stream(&this.circular_buffer, stream)
try searchable_circular_buffer_hash_last_bytes(this, flushed_byte_count)
return flushed_byte_count
## Ported from AK/CircularBuffer.cpp:327 AK::SearchableCircularBuffer::find_copy_in_seekback.
# This searches the seekback buffer (between read head and limit) for occurrences where it matches the next `length` bytes from the read buffer.
# Note that, since we only start searching at the read head, the length between read head and write head is excluded from the distance.
pub func searchable_circular_buffer_find_copy_in_seekback_usize(this: SearchableCircularBuffer*, maximum_length: usize, minimum_length: usize = 2) -> SearchableCircularBufferMatch?:
assert(minimum_length > 0)
let base = &this.circular_buffer
# Clip the maximum length to the amount of data that we actually store.
var max_length = maximum_length
if max_length > base.m_used_space:
max_length = base.m_used_space
if max_length < minimum_length:
return none
var best_match: SearchableCircularBufferMatch?
var needle_storage: u8[3]
let needle = needle_storage[0..<min(searchable_circular_buffer_hash_chunk_size, max_length)]
let needle_read_bytes = circular_buffer_read_with_seekback(base, needle, circular_buffer_used_space(base)) else trap("MUST: read_with_seekback")
assert(needle_read_bytes.length == needle.length)
# Try an efficient hash-based search first.
if needle.length >= searchable_circular_buffer_hash_chunk_size:
let needle_hash = searchable_chunk_hash(needle)
let maybe_starting_offset = hash_map_get_k(&this.m_hash_location_map, needle_hash)
if let starting_offset = maybe_starting_offset:
var previous_buffer_offset: usize?
var current_buffer_offset = *starting_offset
while true:
let current_search_offset = (circular_buffer_capacity(base) + base.m_reading_head - current_buffer_offset) % circular_buffer_capacity(base)
# Validate the hash. In case it is invalid, we can discard the rest of the chain, as the data (and everything older) got updated.
var hash_chunk_at_offset: u8[3]
let hash_chunk_at_offset_span = circular_buffer_read_with_seekback(base, hash_chunk_at_offset, current_search_offset + circular_buffer_used_space(base)) else trap("MUST: read_with_seekback")
assert(hash_chunk_at_offset_span.length == searchable_circular_buffer_hash_chunk_size)
let found_chunk_hash = searchable_chunk_hash(hash_chunk_at_offset)
if needle_hash != found_chunk_hash:
if let previous = previous_buffer_offset:
_ = hash_map_remove_k(&this.m_location_chain_map, previous)
else:
_ = hash_map_remove_k(&this.m_hash_location_map, needle_hash)
break
# Validate the match through the set-distance-based implementation.
let distances: usize[1] = [current_search_offset]
let maybe_new_match = searchable_circular_buffer_find_copy_in_seekback_span_u64(this, distances, max_length, searchable_circular_buffer_hash_chunk_size)
# If we found a match, record it.
# If we haven't found a match, we simply got a hash collision, so skip.
if let new_match = maybe_new_match:
let best_length = searchable_match_length(best_match)
if best_match == none or best_length < new_match.length:
best_match = new_match
# If we already found a result with the best possible length, then stop searching.
if new_match.length >= max_length:
break
# Get the next location with the same hash from the location chain.
let maybe_next_buffer_offset = hash_map_get_k(&this.m_location_chain_map, current_buffer_offset)
# End of the chain, nothing more to check.
let next_buffer_offset = maybe_next_buffer_offset else break
previous_buffer_offset = current_buffer_offset
current_buffer_offset = *next_buffer_offset
# If we found a match, return it now.
if best_match != none:
return best_match
# Try a plain memory search for smaller values.
# Note: This overlaps with the hash search for chunks of size HASH_CHUNK_SIZE for the purpose of validation.
if minimum_length <= searchable_circular_buffer_hash_chunk_size:
var haystack_offset_from_start: usize = 0
var haystack: Vector[const u8[]]
let search_limit = searchable_circular_buffer_search_limit(this)
vector_append_t(&haystack, searchable_circular_buffer_next_search_span(this, search_limit))
if vector_at(&haystack, 0).length < search_limit:
vector_append_t(&haystack, searchable_circular_buffer_next_search_span(this, search_limit - vector_at(&haystack, 0).length))
# TODO: `memmem` searches the memory in "natural" order, which means that it finds matches with a greater distance first.
# Hash-based searching finds the shortest distances first, which is most likely better for encoding and memory efficiency.
# Look into creating a `memmem_reverse`, which starts searching from the end.
var memmem_match = memmem_spans(vector_span(&haystack), needle)
while let match_offset = memmem_match:
let corrected_match_distance = search_limit - haystack_offset_from_start - match_offset
# Validate the match through the set-distance-based implementation and extend it to the largest size possible.
let distances: usize[1] = [corrected_match_distance]
let maybe_new_match = searchable_circular_buffer_find_copy_in_seekback_span_u64(this, distances, min(max_length, searchable_circular_buffer_hash_chunk_size), minimum_length)
# If we weren't able to validate the match at all, either our memmem search returned garbage or our validation function is incorrect. Investigate.
let new_match = maybe_new_match else trap("VERIFY: memmem match did not validate")
let best_length = searchable_match_length(best_match)
if best_match == none or best_length < new_match.length:
best_match = new_match
# If we already found a result with the best possible length, then stop searching.
if new_match.length >= max_length:
break
var size_to_discard = match_offset + 1
# Trim away the already processed bytes from the haystack.
haystack_offset_from_start += size_to_discard
while size_to_discard > 0:
let first = vector_at(&haystack, 0)
if first.length < size_to_discard:
size_to_discard -= first.length
vector_remove(&haystack, 0)
else:
*first = (*first)[size_to_discard..]
break
if vector_size(&haystack) == 0:
break
# Try and find the next match.
memmem_match = memmem_spans(vector_span(&haystack), needle)
# If we found a match of size HASH_CHUNK_SIZE, we should have already found that using the hash search. Investigate.
if let best = best_match:
assert(best.length < searchable_circular_buffer_hash_chunk_size)
return best_match
## Ported from AK/CircularBuffer.cpp:469 AK::SearchableCircularBuffer::find_copy_in_seekback(distances).
# Supplying any hints will only consider those distances, in case existing offsets need to be validated.
pub func searchable_circular_buffer_find_copy_in_seekback_span_u64(this: const SearchableCircularBuffer*, distances: const usize[], maximum_length: usize, minimum_length: usize = 2) -> SearchableCircularBufferMatch?:
assert(minimum_length > 0)
let base = &this.circular_buffer
# Clip the maximum length to the amount of data that we actually store.
var max_length = maximum_length
if max_length > base.m_used_space:
max_length = base.m_used_space
if max_length < minimum_length:
return none
var best_match: SearchableCircularBufferMatch?
for distance in distances:
# Discard distances outside the valid range.
if distance > searchable_circular_buffer_search_limit(this) or distance <= 0:
continue
# TODO: This does not yet support looping repetitions.
if distance < minimum_length:
continue
var current_match_length: usize = 0
while current_match_length < max_length:
let haystack_span = searchable_circular_buffer_next_search_span(this, distance - current_match_length)
let haystack = haystack_span[0..<min(haystack_span.length, max_length - current_match_length)]
let needle_span = circular_buffer_next_read_span(base, current_match_length)
let needle = needle_span[0..<min(needle_span.length, max_length - current_match_length)]
let submatch_length = bytes_matching_prefix_length(haystack, needle)
if submatch_length == 0:
break
current_match_length += submatch_length
# Discard matches that don't reach the minimum length.
if current_match_length < minimum_length:
continue
let best_length = searchable_match_length(best_match)
if best_match == none or best_length < current_match_length:
best_match = SearchableCircularBufferMatch(distance = distance, length = current_match_length)
return best_match
## Ported from AK/CircularBuffer.cpp:516 AK::SearchableCircularBuffer::insert_location_hash.
pub func searchable_circular_buffer_insert_location_hash(this: SearchableCircularBuffer*, value: const u8[], raw_offset: usize) -> !:
assert(value.length == searchable_circular_buffer_hash_chunk_size)
let value_hash = searchable_chunk_hash(value)
# Discard any old entries for this offset first. This should eliminate accidental loops by breaking the chain.
# The actual cleanup is done on access, since we can only remove invalid references when actually walking the chain.
_ = hash_map_remove_k(&this.m_location_chain_map, raw_offset)
# Check if we have any existing entries for this hash.
# If so, we need to add it to the location chain map instead, as we will soon replace the entry in the hash location map.
let existing_entry = hash_map_get_k(&this.m_hash_location_map, value_hash)
if let existing = existing_entry:
_ = try hash_map_try_set(&this.m_location_chain_map, raw_offset, *existing)
_ = try hash_map_try_set(&this.m_hash_location_map, value_hash, raw_offset)
## Ported from AK/CircularBuffer.cpp:538 AK::SearchableCircularBuffer::hash_last_bytes.
pub func searchable_circular_buffer_hash_last_bytes(this: SearchableCircularBuffer*, count: usize) -> !:
# Stop early if we don't have enough data overall to hash a full chunk.
if searchable_circular_buffer_search_limit(this) < searchable_circular_buffer_hash_chunk_size:
return
let buffer_data = byte_buffer_data(&this.circular_buffer.m_buffer) else trap("VERIFY: no buffer")
var remaining_recalculations = count
while remaining_recalculations > 0:
# Note: We offset everything by HASH_CHUNK_SIZE because we have up to HASH_CHUNK_SIZE - 1 bytes that we couldn't hash before (as we had missing data).
# The number of recalculations stays the same, since we now have up to HASH_CHUNK_SIZE - 1 bytes that we can't hash now.
var recalculation_span = searchable_circular_buffer_next_search_span(this, min(remaining_recalculations + searchable_circular_buffer_hash_chunk_size - 1, searchable_circular_buffer_search_limit(this)))
# If the span is smaller than a hash chunk, we need to manually craft some consecutive data to do the hashing.
if recalculation_span.length < searchable_circular_buffer_hash_chunk_size:
let auxiliary_span = circular_buffer_next_seekback_span(&this.circular_buffer, remaining_recalculations)
# Ensure that our math is correct and that both spans are "adjacent".
assert(recalculation_span.data + recalculation_span.length == buffer_data + byte_buffer_size(&this.circular_buffer.m_buffer))
assert(auxiliary_span.data == buffer_data)
while recalculation_span.length > 0 and recalculation_span.length + auxiliary_span.length >= searchable_circular_buffer_hash_chunk_size:
var temporary_hash_chunk: u8[3]
let copied_from_recalculation_span = bytes_copy_trimmed_to(recalculation_span, temporary_hash_chunk)
assert(copied_from_recalculation_span == recalculation_span.length)
let copied_from_auxiliary_span = bytes_copy_trimmed_to(auxiliary_span, temporary_hash_chunk[copied_from_recalculation_span..])
assert(copied_from_recalculation_span + copied_from_auxiliary_span == searchable_circular_buffer_hash_chunk_size)
try searchable_circular_buffer_insert_location_hash(this, temporary_hash_chunk, (usize)(recalculation_span.data - buffer_data))
recalculation_span = recalculation_span[1..]
remaining_recalculations -= 1
continue
var i: usize = 0
while i + searchable_circular_buffer_hash_chunk_size <= recalculation_span.length:
let value = recalculation_span[i..<(i + searchable_circular_buffer_hash_chunk_size)]
let raw_offset = (usize)(value.data - buffer_data)
try searchable_circular_buffer_insert_location_hash(this, value, raw_offset)
remaining_recalculations -= 1
i += 1