A paged KV store identifies cached blocks by a hash chain: each 128-token block's key depends on its own tokens and on the key of the block before it, so a block hash only matches when the whole prefix matches. A hybrid model also needs the sliding-window state at the hit boundary, which is stored separately and only at some positions. Implement the hashing and the hit policy.
block_hashes(tokens, block=128)
h = 0; for each token of the block in order, h = (h * 131 + token + 1) % (2**61 - 1); the first token of every block folds into the previous block's hash (0 before the first block). Partial trailing blocks are ignored.store_prefix(store, tokens, swa_positions=(), block=128)
store is a dict {"blocks": set(), "swa": set()}. Add every block hash of tokens to blocks. For each p in swa_positions (multiples of block, at most len(tokens) rounded down to a block), add the hash of the block ending at p to swa.hit_length(store, tokens, block=128, window=128, backtrack=6)
len(tokens) - (window + backtrack); if it is below block, return {"cap": cap, "block_hit": 0, "hit": 0} (with cap as computed, possibly negative).block_hit is the length of the longest run of leading blocks whose hashes are all in blocks, times block, but never more than cap // block blocks.block_hit is 0, hit is 0. Otherwise hit is block_hit if the sliding-window state exists at block_hit or at block_hit - block (the state at position 0 always exists), and block_hit - block otherwise.{"cap": ..., "block_hit": ..., "hit": ...}.