rmmh · July 1, 2026 15:43
diff --git a/crosspoint_dict_benchmarks.md b/crosspoint_dict_benchmarks.md
diff --git a/dict_index_benchmark.go b/dict_index_benchmark.go
 package main

 import (
 	"bytes"
 	"compress/gzip"
 	"encoding/binary"
 	"errors"
 	"flag"
 	"fmt"
 	"io"
 	"os"
 	"path/filepath"
 	"regexp"
 	"runtime/debug"
 	"sort"
 	"strings"
 	"text/tabwriter"
 )

 const (
 	blockSize       = 512
 	oftHeaderSize   = 38
 	oftStride       = 32
 	csptHeaderSize  = 12
 	base26HeaderLen = 8
 	csptPrefixLen   = 16
 	csptSubStride   = 16
 	sectorHeaderLen = 8
 	maxPreviewWords = 3
 )

 type dictFiles struct {
 	stem   string
 	idx    string
 	dict   string
 	dictGz string
 	dictDz string
 }

 type idxEntry struct {
 	word      string
 	offset    uint32
 	size      uint32
 	idxOffset uint32
 }

 type csptEntry struct {
 	prefix string
 	offset uint32
 }

 type sectorFence struct {
 	firstWord   string
 	firstOffset uint32
 }

 type tabEntry struct {
 	prefix string
 }

 type blockReader struct {
 	label      string
 	data       []byte
 	cacheBlock int
 	reads      int
 }

 type rangeReader interface {
 	TouchRange(uint32, int) error
 	Reads() int
 }

 type cacheBlockReader struct {
 	label string
 	data  []byte
 	slots []int
 	next  int
 	reads int
 }

 type methodStat struct {
 	name      string
 	extraSize int
 	counts    []int
 	misses    int
 	examples  map[int]string
 	missWord  string
 }

 type benchmarkMethod struct {
 	name      string
 	extraSize int
 	run       func(string) (uint32, uint32, bool, int, error)
 }

 type tabStat struct {
 	name       string
 	entries    int
 	identical  int
 	unique     int
 	maxRun     int
 	firstBytes int
 }

 var (
 	plainFencePCPattern  = regexp.MustCompile(`^fencepc_\d+$`)
 	fencePCBase26Pattern = regexp.MustCompile(`^fencepc_.*-base26_`)
 	traceWord            string
 	traceMethodRE        *regexp.Regexp
 	traceActive          bool
 	traceMethodName      string
 	traceStackEnabled    bool
 )

 type tabSpec struct {
 	name    string
 	entries []tabEntry
 	data    []byte
 }

 type fencePCSpec struct {
 	prefixLen int
 	data      []byte
 }

 type fencePCBlockEntry struct {
 	sector int
 	prefix []byte
 	start  uint32
 }

 func newBlockReader(data []byte) *blockReader {
 	return newNamedBlockReader("", data)
 }

 func newCacheBlockReader(data []byte, blocks int) *cacheBlockReader {
 	return newNamedCacheBlockReader("", data, blocks)
 }

 func newNamedBlockReader(label string, data []byte) *blockReader {
 	return &blockReader{label: label, data: data, cacheBlock: -1}
 }

 func newNamedCacheBlockReader(label string, data []byte, blocks int) *cacheBlockReader {
 	slots := make([]int, blocks)
 	for i := range slots {
 		slots[i] = -1
 	}
 	return &cacheBlockReader{label: label, data: data, slots: slots}
 }

 func (r *blockReader) touch(offset uint32) error {
 	if int(offset) >= len(r.data) {
 		return io.EOF
 	}
 	block := int(offset) / blockSize
 	if block != r.cacheBlock {
 		r.cacheBlock = block
 		r.reads++
 		traceBlockRead(r.label, offset)
 	}
 	return nil
 }

 func (r *blockReader) ReadByteAt(offset uint32) (byte, error) {
 	if err := r.touch(offset); err != nil {
 		return 0, err
 	}
 	return r.data[offset], nil
 }

 func (r *blockReader) TouchRange(offset uint32, n int) error {
 	for i := 0; i < n; i++ {
 		if err := r.touch(offset + uint32(i)); err != nil {
 			return err
 		}
 	}
 	return nil
 }

 func (r *blockReader) Reads() int {
 	return r.reads
 }

 func (r *cacheBlockReader) touch(offset uint32) error {
 	if int(offset) >= len(r.data) {
 		return io.EOF
 	}
 	block := int(offset) / blockSize
 	for _, cached := range r.slots {
 		if cached == block {
 			return nil
 		}
 	}
 	r.slots[r.next] = block
 	r.next = (r.next + 1) % len(r.slots)
 	r.reads++
 	traceBlockRead(r.label, offset)
 	return nil
 }

 func (r *cacheBlockReader) TouchRange(offset uint32, n int) error {
 	for i := 0; i < n; i++ {
 		if err := r.touch(offset + uint32(i)); err != nil {
 			return err
 		}
 	}
 	return nil
 }

 func (r *cacheBlockReader) Reads() int {
 	return r.reads
 }

 func main() {
 	var path string
 	var showAll bool
 	var runPattern string
 	var traceMethodPattern string
 	var showExamples bool
 	var traceStackFlag bool
 	flag.StringVar(&path, "dict", "fs_/.dictionaries/gcide", "dictionary directory or base stem path")
 	flag.BoolVar(&showAll, "all", false, "show all benchmark rows")
 	flag.StringVar(&runPattern, "run", "", "run only benchmark methods whose names match this regexp")
 	flag.StringVar(&traceWord, "trace-word", "", "trace one lookup word")
 	flag.StringVar(&traceMethodPattern, "trace-method", "", "trace only methods whose names match this regexp")
 	flag.BoolVar(&showExamples, "example", false, "show example words for reported page-read counts")
 	flag.BoolVar(&traceStackFlag, "trace-stack", false, "include stacks in traced block-read logs")
 	flag.Parse()
 	traceStackEnabled = traceStackFlag

 	var runRE *regexp.Regexp
 	if runPattern != "" {
 		var err error
 		runRE, err = regexp.Compile(runPattern)
 		if err != nil {
 			die(fmt.Errorf("compile -run regexp: %w", err))
 		}
 	}
 	if traceMethodPattern != "" {
 		var err error
 		traceMethodRE, err = regexp.Compile(traceMethodPattern)
 		if err != nil {
 			die(fmt.Errorf("compile -trace-method regexp: %w", err))
 		}
 	}

 	files, err := resolveDictFiles(path)
 	if err != nil {
 		die(err)
 	}

 	idxData, err := os.ReadFile(files.idx)
 	if err != nil {
 		die(fmt.Errorf("read idx: %w", err))
 	}
 	dictData, err := loadDict(files)
 	if err != nil {
 		die(fmt.Errorf("load dict: %w", err))
 	}

 	entries, err := parseIdx(idxData)
 	if err != nil {
 		die(fmt.Errorf("parse idx: %w", err))
 	}
 	if len(entries) == 0 {
 		die(errors.New("idx contains no entries"))
 	}

 	if err := validateDefinitions(entries, dictData); err != nil {
 		die(fmt.Errorf("validate dict offsets: %w", err))
 	}

 	oftData := buildOftBytes(entries, len(idxData))
 	csptData := buildCsptBytes(entries)
 	base26_3Data := buildBase26Bytes(entries, len(idxData), 3)
 	base26_4Data := buildBase26Bytes(entries, len(idxData), 4)
 	fences := buildSectorFences(entries, len(idxData))
 	fenceData := buildFenceBytes(fences)
 	fencePCSpecs := []fencePCSpec{}
 	for prefixLen := 3; prefixLen <= 10; prefixLen++ {
 		fencePCSpecs = append(fencePCSpecs, fencePCSpec{
 			prefixLen: prefixLen,
 			data:      buildFencePCBytes(fences, prefixLen),
 		})
 	}
 	var tabs []tabSpec
 	var tabStats []tabStat
 	for _, spec := range []struct {
 		k         int
 		prefixLen int
 	}{
 		{1, 2},
 		{1, 3},
 		{1, 4},
 		{2, 3},
 		{2, 4},
 		{8, 3},
 		{8, 4},
 	} {
 		name := fmt.Sprintf("tab%d_%d", spec.k, spec.prefixLen)
 		tabEntries, tabData := buildTabEntries(fences, spec.k, spec.prefixLen)
 		tabs = append(tabs, tabSpec{name: name, entries: tabEntries, data: tabData})
 		tabStats = append(tabStats, buildTabStat(name, tabEntries, spec.prefixLen))
 	}

 	methods := buildMethods(idxData, oftData, csptData, base26_3Data, base26_4Data, fenceData, fences, fencePCSpecs, tabs)

 	stats := make([]methodStat, 0, len(methods))
 	for _, method := range methods {
 		if !shouldRunMethod(method.name, showAll, runRE) {
 			continue
 		}
 		counts := make([]int, 0, len(entries))
 		misses := 0
 		var examples map[int]string
 		missWord := ""
 		if showExamples {
 			examples = make(map[int]string)
 		}
 		for _, ent := range entries {
 			off, size, found, reads, err := method.run(ent.word)
 			if err != nil {
 				die(fmt.Errorf("%s lookup failed for %q: %w", method.name, ent.word, err))
 			}
 			if !found || off != ent.offset || size != ent.size {
 				misses++
 				if showExamples && missWord == "" {
 					missWord = ent.word
 				}
 				continue
 			}
 			counts = append(counts, reads)
 			if showExamples {
 				if _, ok := examples[reads]; !ok {
 					examples[reads] = ent.word
 				}
 			}
 		}
 		stats = append(stats, methodStat{name: method.name, extraSize: method.extraSize, counts: counts, misses: misses, examples: examples, missWord: missWord})
 	}

 	printSummary(files, idxData, dictData, entries, stats, tabStats, showAll, showExamples)
 }

 func buildMethods(idxData, oftData, csptData, base26_3Data, base26_4Data, fenceData []byte, fences []sectorFence, fencePCs []fencePCSpec, tabs []tabSpec) []benchmarkMethod {
 	methods := []benchmarkMethod{
 		makeSingleIndexMethod("oft", len(oftData), idxData, oftData, func(idxReader, sidecarReader *blockReader, word string) (uint32, uint32, bool, error) {
 			return locateOft(idxReader, sidecarReader, idxData, oftData, word)
 		}),
 		makeSingleIndexMethod("cspt", len(oftData)+len(csptData), idxData, csptData, func(idxReader, sidecarReader *blockReader, word string) (uint32, uint32, bool, error) {
 			return locateCspt(idxReader, sidecarReader, idxData, csptData, word)
 		}),
 		makeSingleIndexMethod("base26_3", len(base26_3Data), idxData, base26_3Data, func(idxReader, sidecarReader *blockReader, word string) (uint32, uint32, bool, error) {
 			return locateBase26(idxReader, sidecarReader, idxData, base26_3Data, word, 3)
 		}),
 		makeSingleIndexMethod("base26_4", len(base26_4Data), idxData, base26_4Data, func(idxReader, sidecarReader *blockReader, word string) (uint32, uint32, bool, error) {
 			return locateBase26(idxReader, sidecarReader, idxData, base26_4Data, word, 4)
 		}),
 		makeFenceBase26Method("fencec-base26_3", len(fenceData)+len(base26_3Data), idxData, fenceData, fences, base26_3Data),
 		makeFenceMethod("fence", len(fenceData), idxData, fenceData, fences, false, nil),
 	}

 	tabByName := make(map[string]tabSpec, len(tabs))
 	for _, tab := range tabs {
 		tabCopy := tab
 		tabByName[tabCopy.name] = tabCopy
 		methods = append(methods,
 			makeFenceMethod("fence-"+tabCopy.name, len(fenceData)+len(tabCopy.data), idxData, fenceData, fences, false, &tabCopy),
 			makeFenceMethod("fencec-"+tabCopy.name, len(fenceData)+len(tabCopy.data), idxData, fenceData, fences, true, &tabCopy),
 		)
 	}

 	for _, pc := range fencePCs {
 		pcCopy := pc
 		prefix := fmt.Sprintf("fencep_%d", pcCopy.prefixLen)
 		methods = append(methods, makeFencePCMethod(prefix, len(pcCopy.data), idxData, pcCopy.data, fences, pcCopy.prefixLen, nil, nil))
 		for _, name := range []string{"tab1_2", "tab1_3", "tab1_4"} {
 			tab := tabByName[name]
 			methods = append(methods, makeFencePCMethod(prefix+"-"+name, len(pcCopy.data)+len(tab.data), idxData, pcCopy.data, fences, pcCopy.prefixLen, &tab, nil))
 		}
 		methods = append(methods, makeFencePCMethod(prefix+"-base26_3", len(pcCopy.data)+len(base26_3Data), idxData, pcCopy.data, fences, pcCopy.prefixLen, nil, base26_3Data))
 	}

 	return methods
 }

 func makeSingleIndexMethod(name string, extraSize int, idxData, sidecarData []byte, locate func(*blockReader, *blockReader, string) (uint32, uint32, bool, error)) benchmarkMethod {
 	return benchmarkMethod{
 		name:      name,
 		extraSize: extraSize,
 		run: func(word string) (uint32, uint32, bool, int, error) {
 			idxReader := newNamedBlockReader("idx", idxData)
 			sidecarReader := newNamedBlockReader(name, sidecarData)
 			off, size, found, err := locate(idxReader, sidecarReader, word)
 			return off, size, found, idxReader.Reads() + sidecarReader.Reads(), err
 		},
 	}
 }

 func makeFenceMethod(name string, extraSize int, idxData, fenceData []byte, fences []sectorFence, cached bool, tab *tabSpec) benchmarkMethod {
 	return benchmarkMethod{
 		name:      name,
 		extraSize: extraSize,
 		run: func(word string) (uint32, uint32, bool, int, error) {
 			idxReader := newNamedBlockReader("idx", idxData)
 			var fenceReader rangeReader
 			var fenceReads func() int
 			if cached {
 				reader := newNamedCacheBlockReader("fence", fenceData, 8)
 				fenceReader = reader
 				fenceReads = reader.Reads
 			} else {
 				reader := newNamedBlockReader("fence", fenceData)
 				fenceReader = reader
 				fenceReads = reader.Reads
 			}

 			lo, hi, tabReads, err := fenceBounds(word, fences, tab, cached)
 			if err != nil {
 				return 0, 0, false, 0, err
 			}
 			off, size, found, err := locateFence(idxReader, fenceReader, fenceData, idxData, fences, lo, hi, word)
 			return off, size, found, idxReader.Reads() + fenceReads() + tabReads, err
 		},
 	}
 }

 func makeFenceBase26Method(name string, extraSize int, idxData, fenceData []byte, fences []sectorFence, tableData []byte) benchmarkMethod {
 	return benchmarkMethod{
 		name:      name,
 		extraSize: extraSize,
 		run: func(word string) (uint32, uint32, bool, int, error) {
 			idxReader := newNamedBlockReader("idx", idxData)
 			tableReader := newNamedBlockReader("base26", tableData)
 			fenceReader := newNamedCacheBlockReader("fence", fenceData, 8)
 			start, end, lo, hi, err := locateBase26FenceBounds(tableReader, tableData, idxData, word, 3, len(fences))
 			if err != nil {
 				return 0, 0, false, 0, err
 			}
 			off, size, found, err := locateFenceAdaptive(idxReader, fenceReader, fenceData, idxData, fences, lo, hi, start, end, word)
 			return off, size, found, idxReader.Reads() + tableReader.Reads() + fenceReader.Reads(), err
 		},
 	}
 }

 func makeFencePCMethod(name string, extraSize int, idxData, pcData []byte, fences []sectorFence, prefixLen int, tab *tabSpec, base26Data []byte) benchmarkMethod {
 	return benchmarkMethod{
 		name:      name,
 		extraSize: extraSize,
 		run: func(word string) (uint32, uint32, bool, int, error) {
 			restoreTrace := beginTrace(name, word)
 			defer restoreTrace()
 			pcLabel := "fencepc"
 			if strings.HasPrefix(name, "fencep_") {
 				pcLabel = "fencep"
 			}
 			idxReader := newNamedBlockReader("idx", idxData)
 			pcReader := newNamedBlockReader(pcLabel, pcData)
 			pcReads := pcReader.Reads

 			lo, hi, tabReads, err := fenceBounds(word, fences, tab, false)
 			if err != nil {
 				return 0, 0, false, 0, err
 			}

 			// Derive initial byte range from fence sector bounds so that tab
 			// constrains start/end, not just lo/hi.
 			start := uint32(0)
 			end := uint32(len(idxData))
 			if lo >= 0 && lo < len(fences) && fences[lo].firstWord != "" {
 				start = fences[lo].firstOffset
 			}
 			if hi+1 < len(fences) && fences[hi+1].firstWord != "" {
 				end = fences[hi+1].firstOffset
 			}
 			if tab != nil {
 				tracef("#TAB lo=%d hi=%d start=%d end=%d", lo, hi, start, end)
 			}
 			base26Reads := 0
 			if base26Data != nil {
 				tableReader := newNamedBlockReader("base26", base26Data)
 				start, end, lo, hi, err = locateBase26FenceBounds(tableReader, base26Data, idxData, word, 3, len(fences))
 				if err != nil {
 					return 0, 0, false, 0, err
 				}
 				base26Reads = tableReader.Reads()
 			}

 			off, size, found, err := locateFencePC(idxReader, pcReader, pcData, idxData, fences, prefixLen, start, end, word)
 			return off, size, found, idxReader.Reads() + pcReads() + tabReads + base26Reads, err
 		},
 	}
 }

 func fenceBounds(word string, fences []sectorFence, tab *tabSpec, cached bool) (int, int, int, error) {
 	if tab == nil {
 		return 0, len(fences) - 1, 0, nil
 	}
 	if cached {
 		lo, hi := locateTabBoundsCold(tab.entries, word, len(fences))
 		return lo, hi, blockCount(len(tab.data)), nil
 	}
 	tabReader := newNamedBlockReader("tab", tab.data)
 	lo, hi, err := locateTabBounds(tabReader, tab.entries, word, len(fences))
 	if err != nil {
 		return 0, 0, 0, err
 	}
 	return lo, hi, tabReader.Reads(), nil
 }

 func die(err error) {
 	fmt.Fprintln(os.Stderr, "error:", err)
 	os.Exit(1)
 }

 func resolveDictFiles(path string) (dictFiles, error) {
 	info, err := os.Stat(path)
 	if err == nil && info.IsDir() {
 		matches, err := filepath.Glob(filepath.Join(path, "*.idx"))
 		if err != nil {
 			return dictFiles{}, err
 		}
 		if len(matches) != 1 {
 			return dictFiles{}, fmt.Errorf("expected exactly 1 .idx in %s, found %d", path, len(matches))
 		}
 		stem := strings.TrimSuffix(matches[0], ".idx")
 		return dictFiles{
 			stem:   stem,
 			idx:    stem + ".idx",
 			dict:   stem + ".dict",
 			dictGz: stem + ".dict.gz",
 			dictDz: stem + ".dict.dz",
 		}, nil
 	}

 	stem := strings.TrimSuffix(path, filepath.Ext(path))
 	return dictFiles{
 		stem:   stem,
 		idx:    stem + ".idx",
 		dict:   stem + ".dict",
 		dictGz: stem + ".dict.gz",
 		dictDz: stem + ".dict.dz",
 	}, nil
 }

 func loadDict(files dictFiles) ([]byte, error) {
 	if data, err := os.ReadFile(files.dict); err == nil {
 		return data, nil
 	}

 	archivePath := files.dictGz
 	f, err := os.Open(archivePath)
 	if err != nil {
 		archivePath = files.dictDz
 		f, err = os.Open(archivePath)
 		if err != nil {
 			return nil, fmt.Errorf("open %s or %s: %w", files.dictGz, files.dictDz, err)
 		}
 	}
 	defer f.Close()

 	gzr, err := gzip.NewReader(f)
 	if err != nil {
 		return nil, fmt.Errorf("gzip reader: %w", err)
 	}
 	defer gzr.Close()

 	data, err := io.ReadAll(gzr)
 	if err != nil {
 		return nil, fmt.Errorf("decompress %s: %w", archivePath, err)
 	}
 	return data, nil
 }

 func parseIdx(data []byte) ([]idxEntry, error) {
 	var entries []idxEntry
 	pos := 0
 	for pos < len(data) {
 		null := bytes.IndexByte(data[pos:], 0)
 		if null < 0 {
 			return nil, fmt.Errorf("unterminated word at byte %d", pos)
 		}
 		null += pos
 		if null+9 > len(data) {
 			return nil, fmt.Errorf("truncated idx payload at byte %d", pos)
 		}
 		word := string(data[pos:null])
 		offset := binary.BigEndian.Uint32(data[null+1 : null+5])
 		size := binary.BigEndian.Uint32(data[null+5 : null+9])
 		entries = append(entries, idxEntry{
 			word:      word,
 			offset:    offset,
 			size:      size,
 			idxOffset: uint32(pos),
 		})
 		pos = null + 9
 	}
 	return entries, nil
 }

 func validateDefinitions(entries []idxEntry, dictData []byte) error {
 	limit := uint32(len(dictData))
 	for _, ent := range entries {
 		if ent.offset > limit || ent.size > limit-ent.offset {
 			return fmt.Errorf("entry %q points outside dict (off=%d size=%d dict=%d)", ent.word, ent.offset, ent.size, limit)
 		}
 	}
 	return nil
 }

 func buildOftOffsets(entries []idxEntry) []uint32 {
 	offsets := []uint32{0}
 	for i := oftStride; i < len(entries); i += oftStride {
 		offsets = append(offsets, entries[i].idxOffset)
 	}
 	return offsets
 }

 func buildOftBytes(entries []idxEntry, idxSize int) []byte {
 	offsets := buildOftOffsets(entries)
 	out := make([]byte, oftHeaderSize, oftHeaderSize+4*(len(offsets)))
 	for _, off := range offsets[1:] {
 		var buf [4]byte
 		binary.LittleEndian.PutUint32(buf[:], off)
 		out = append(out, buf[:]...)
 	}
 	var sentinel [4]byte
 	binary.LittleEndian.PutUint32(sentinel[:], uint32(idxSize))
 	out = append(out, sentinel[:]...)
 	return out
 }

 func buildCspt(entries []idxEntry) []csptEntry {
 	pageStarts := buildOftOffsets(entries)
 	out := make([]csptEntry, 0, len(pageStarts)*2)
 	for _, pageOffset := range pageStarts {
 		pageIdx := sort.Search(len(entries), func(i int) bool { return entries[i].idxOffset >= pageOffset })
 		if pageIdx >= len(entries) {
 			break
 		}
 		out = append(out, csptEntry{
 			prefix: lowerASCII(prefix(entries[pageIdx].word, csptPrefixLen)),
 			offset: entries[pageIdx].idxOffset,
 		})
 		midIdx := pageIdx + csptSubStride
 		if midIdx < len(entries) {
 			out = append(out, csptEntry{
 				prefix: lowerASCII(prefix(entries[midIdx].word, csptPrefixLen)),
 				offset: entries[midIdx].idxOffset,
 			})
 		}
 	}
 	return out
 }

 func buildCsptBytes(entries []idxEntry) []byte {
 	items := buildCspt(entries)
 	out := make([]byte, csptHeaderSize, csptHeaderSize+len(items)*(csptPrefixLen+4))
 	copy(out[:4], []byte("CSPT"))
 	out[4] = 1
 	out[5] = csptPrefixLen
 	binary.LittleEndian.PutUint16(out[6:8], csptSubStride)
 	binary.LittleEndian.PutUint32(out[8:12], uint32(len(items)))
 	for _, item := range items {
 		pfx := []byte(prefix(lowerASCII(item.prefix), csptPrefixLen))
 		entry := make([]byte, csptPrefixLen+4)
 		copy(entry[:csptPrefixLen], pfx)
 		binary.LittleEndian.PutUint32(entry[csptPrefixLen:], item.offset)
 		out = append(out, entry...)
 	}
 	return out
 }

 func buildBase26Bytes(entries []idxEntry, idxSize, prefixLen int) []byte {
 	return buildBaseNBytes(entries, idxSize, prefixLen, 26)
 }

 func buildBaseNBytes(entries []idxEntry, idxSize, prefixLen, radix int) []byte {
 	entryCount := 1
 	for i := 0; i < prefixLen; i++ {
 		entryCount *= radix
 	}
 	out := make([]byte, base26HeaderLen, base26HeaderLen+(entryCount+1)*4)
 	copy(out[:4], []byte("B26T"))
 	out[4] = byte(prefixLen)
 	out[5] = byte(radix)
 	binary.LittleEndian.PutUint32(out[base26HeaderLen-4:base26HeaderLen], uint32(entryCount+1))
 	table := make([]uint32, entryCount+1)
 	for i := range table {
 		table[i] = uint32(idxSize)
 	}
 	pos := 0
 	for code := 0; code < entryCount; code++ {
 		for pos < len(entries) && baseNCode(entries[pos].word, prefixLen, radix) < code {
 			pos++
 		}
 		if pos < len(entries) {
 			table[code] = entries[pos].idxOffset
 		}
 	}
 	table[entryCount] = uint32(idxSize)
 	for _, off := range table {
 		var buf [4]byte
 		binary.LittleEndian.PutUint32(buf[:], off)
 		out = append(out, buf[:]...)
 	}
 	return out
 }

 func buildSectorFences(entries []idxEntry, idxSize int) []sectorFence {
 	numSectors := (idxSize + blockSize - 1) / blockSize
 	fences := make([]sectorFence, numSectors)
 	for sector := 0; sector < numSectors; sector++ {
 		start := uint32(sector * blockSize)
 		i := sort.Search(len(entries), func(i int) bool { return entries[i].idxOffset >= start })
 		if i >= len(entries) {
 			break
 		}
 		fences[sector] = sectorFence{
 			firstWord:   entries[i].word,
 			firstOffset: entries[i].idxOffset,
 		}
 	}
 	return fences
 }

 func buildFenceBytes(fences []sectorFence) []byte {
 	lowCount := len(fences)
 	highCount := (len(fences) + 7) / 8
 	out := make([]byte, sectorHeaderLen, sectorHeaderLen+lowCount+highCount)
 	copy(out[:4], []byte("FNC1"))
 	binary.LittleEndian.PutUint32(out[4:8], uint32(len(fences)))
 	highBits := make([]byte, highCount)
 	for sector := range fences {
 		rel := 0
 		if fences[sector].firstWord != "" {
 			rel = int(fences[sector].firstOffset) - sector*blockSize
 		}
 		out = append(out, byte(rel&0xff))
 		if rel&0x100 != 0 {
 			highBits[sector/8] |= 1 << uint(sector%8)
 		}
 	}
 	out = append(out, highBits...)
 	return out
 }

 func buildFencePCBytes(fences []sectorFence, prefixLen int) []byte {
 	groupCount := (len(fences) + 7) / 8
 	groupSize := fencePCGroupSize(prefixLen)
 	groupsPerSector := fencePCGroupsPerSector(prefixLen)
 	sidecarSectors := (groupCount + groupsPerSector - 1) / groupsPerSector
 	out := make([]byte, sidecarSectors*blockSize)
 	for group := 0; group < groupCount; group++ {
 		sidecarSector := group / groupsPerSector
 		groupInSector := group % groupsPerSector
 		groupOffset := sidecarSector*blockSize + groupInSector*groupSize
 		base := out[groupOffset : groupOffset+groupSize]
 		var highBits byte
 		var prev []byte
 		for local := 0; local < 8; local++ {
 			sector := group*8 + local
 			if sector >= len(fences) {
 				break
 			}
 			rel := 0
 			if fences[sector].firstWord != "" {
 				rel = int(fences[sector].firstOffset) - sector*blockSize
 			}
 			base[local] = byte(rel & 0xff)
 			if rel&0x100 != 0 {
 				highBits |= 1 << uint(local)
 			}
 			word := lowerASCII(fences[sector].firstWord)
 			pfx := paddedPrefixBytes(word, prefixLen)
 			slot := base[9+local*prefixLen : 9+(local+1)*prefixLen]
 			if local == 0 {
 				copy(slot, pfx)
 				prev = append(prev[:0], pfx...)
 			} else {
 				common := commonPrefixLenString(string(prev), word)
 				if common > 127 {
 					common = 127
 				}
 				if common > 0 {
 					slot[0] = byte(0x80 | common)
 					suffix := suffixBytes(word, common, prefixLen-1)
 					copy(slot[1:], suffix)
 					prev = append(prev[:common], suffix...)
 				} else {
 					copy(slot, pfx)
 					prev = append(prev[:0], pfx...)
 				}
 			}
 		}
 		base[8] = highBits
 	}
 	return out
 }

 func buildTabEntries(fences []sectorFence, tableSectors, prefixLen int) ([]tabEntry, []byte) {
 	payloadBytes := tableSectors * blockSize
 	entryCount := payloadBytes / prefixLen
 	if entryCount < 2 {
 		return nil, nil
 	}
 	if len(fences) == 0 {
 		return nil, nil
 	}
 	if entryCount > len(fences) {
 		entryCount = len(fences)
 	}
 	entries := make([]tabEntry, 0, entryCount)
 	out := make([]byte, 0, entryCount*prefixLen)
 	for i := 0; i < entryCount; i++ {
 		sectorIdx := sampledSector(i, entryCount, len(fences))
 		pfx := prefix(lowerASCII(fences[sectorIdx].firstWord), prefixLen)
 		entries = append(entries, tabEntry{prefix: pfx})
 		entry := make([]byte, prefixLen)
 		copy(entry, []byte(pfx))
 		out = append(out, entry...)
 	}
 	return entries, out
 }

 func locateLinear(reader *blockReader, idxData []byte, word string) (uint32, uint32, bool, error) {
 	return scanEntries(reader, idxData, 0, uint32(len(idxData)), word)
 }

 func locateOft(idxReader, oftReader *blockReader, idxData, oftData []byte, word string) (uint32, uint32, bool, error) {
 	pageCount := oftPageCount(oftData)
 	if pageCount == 0 {
 		return locateLinear(idxReader, idxData, word)
 	}
 	target := lowerASCII(word)
 	lo, hi := 0, pageCount-1
 	for lo < hi {
 		mid := lo + (hi-lo+1)/2
 		pageOffset, err := readOftPageOffset(oftReader, oftData, mid)
 		if err != nil {
 			return 0, 0, false, err
 		}
 		pageWord, err := readWordAt(idxReader, idxData, pageOffset)
 		if err != nil {
 			return 0, 0, false, err
 		}
 		if asciiCmp(pageWord, target) > 0 {
 			hi = mid - 1
 		} else {
 			lo = mid
 		}
 	}
 	start, err := readOftPageOffset(oftReader, oftData, lo)
 	if err != nil {
 		return 0, 0, false, err
 	}
 	end, err := readOftPageEnd(oftReader, oftData, lo, uint32(len(idxData)))
 	if err != nil {
 		return 0, 0, false, err
 	}
 	return scanEntries(idxReader, idxData, start, end, word)
 }

 func locateCspt(idxReader, csptReader *blockReader, idxData, csptData []byte, word string) (uint32, uint32, bool, error) {
 	entryCount, err := readCsptHeader(csptReader, csptData)
 	if err != nil {
 		return 0, 0, false, err
 	}
 	if entryCount == 0 {
 		return locateLinear(idxReader, idxData, word)
 	}
 	target := lowerASCII(word)
 	lo, hi := 0, int(entryCount)-1
 	for lo < hi {
 		mid := lo + (hi-lo+1)/2
 		pfx, _, err := readCsptEntry(csptReader, csptData, mid)
 		if err != nil {
 			return 0, 0, false, err
 		}
 		if asciiCmp(pfx, target) > 0 {
 			hi = mid - 1
 		} else {
 			lo = mid
 		}
 	}
 	_, start, err := readCsptEntry(csptReader, csptData, lo)
 	if err != nil {
 		return 0, 0, false, err
 	}
 	end := uint32(len(idxData))
 	if lo+1 < int(entryCount) {
 		_, end, err = readCsptEntry(csptReader, csptData, lo+1)
 		if err != nil {
 			return 0, 0, false, err
 		}
 	}
 	return scanEntries(idxReader, idxData, start, end, word)
 }

 func locateBase26(idxReader, tableReader *blockReader, idxData, tableData []byte, word string, prefixLen int) (uint32, uint32, bool, error) {
 	return locateBaseN(idxReader, tableReader, idxData, tableData, word, prefixLen, 26)
 }

 func locateBaseN(idxReader, tableReader *blockReader, idxData, tableData []byte, word string, prefixLen, radix int) (uint32, uint32, bool, error) {
 	code := baseNCode(word, prefixLen, radix)
 	start, err := readBase26Offset(tableReader, tableData, code)
 	if err != nil {
 		return 0, 0, false, err
 	}
 	end, err := readBase26Offset(tableReader, tableData, code+1)
 	if err != nil {
 		return 0, 0, false, err
 	}
 	if start >= uint32(len(idxData)) {
 		return 0, 0, false, nil
 	}
 	if end <= start {
 		end = uint32(len(idxData))
 	}
 	return scanEntries(idxReader, idxData, start, end, word)
 }

 func locateBase26FenceBounds(tableReader *blockReader, tableData, idxData []byte, word string, prefixLen, sectorCount int) (uint32, uint32, int, int, error) {
 	code := baseNCode(word, prefixLen, 26)
 	start, err := readBase26Offset(tableReader, tableData, code)
 	if err != nil {
 		return 0, 0, 0, 0, err
 	}
 	end, err := readBase26Offset(tableReader, tableData, code+1)
 	if err != nil {
 		return 0, 0, 0, 0, err
 	}
 	if start >= uint32(len(idxData)) {
 		return start, end, 0, sectorCount - 1, nil
 	}
 	lo := int(start) / blockSize
 	hi := sectorCount - 1
 	if end < uint32(len(idxData)) {
 		hi = int(end) / blockSize
 	}
 	if lo < 0 {
 		lo = 0
 	}
 	if hi < lo {
 		hi = lo
 	}
 	if hi >= sectorCount {
 		hi = sectorCount - 1
 	}
 	return start, end, lo, hi, nil
 }

 func locateFence(idxReader *blockReader, fenceReader rangeReader, fenceData, idxData []byte, fences []sectorFence, lo, hi int, word string) (uint32, uint32, bool, error) {
 	return locateFenceRange(idxReader, fenceReader, fenceData, idxData, fences, lo, hi, 0, uint32(len(idxData)), word)
 }

 func locateFenceAdaptive(idxReader *blockReader, fenceReader rangeReader, fenceData, idxData []byte, fences []sectorFence, lo, hi int, exactStart, exactEnd uint32, word string) (uint32, uint32, bool, error) {
 	sectorSpan := hi - lo + 1
 	blockSpan := blocksBetween(exactStart, exactEnd)
 	if blockSpan <= 0 {
 		return 0, 0, false, nil
 	}
 	if 1+ceilLog2(sectorSpan)+2 >= blockSpan {
 		return scanEntries(idxReader, idxData, exactStart, exactEnd, word)
 	}
 	return locateFenceRange(idxReader, fenceReader, fenceData, idxData, fences, lo, hi, exactStart, exactEnd, word)
 }

 func locateFenceRange(idxReader *blockReader, fenceReader rangeReader, fenceData, idxData []byte, fences []sectorFence, lo, hi int, exactStart, exactEnd uint32, word string) (uint32, uint32, bool, error) {
 	if len(fences) == 0 {
 		return locateLinear(idxReader, idxData, word)
 	}
 	if lo < 0 {
 		lo = 0
 	}
 	if hi >= len(fences) {
 		hi = len(fences) - 1
 	}
 	target := lowerASCII(word)
 	for lo < hi {
 		mid := lo + (hi-lo+1)/2
 		midWord, _, ok, err := readFenceWord(idxReader, fenceReader, fenceData, idxData, len(fences), mid)
 		if err != nil {
 			return 0, 0, false, err
 		}
 		if !ok || asciiCmp(midWord, target) > 0 {
 			hi = mid - 1
 		} else {
 			lo = mid
 		}
 	}
 	_, start, ok, err := readFenceWord(idxReader, fenceReader, fenceData, idxData, len(fences), lo)
 	if err != nil {
 		return 0, 0, false, err
 	}
 	if !ok {
 		return 0, 0, false, nil
 	}
 	end := uint32(len(idxData))
 	if lo+1 < len(fences) {
 		_, nextStart, nextOK, err := readFenceWord(idxReader, fenceReader, fenceData, idxData, len(fences), lo+1)
 		if err != nil {
 			return 0, 0, false, err
 		}
 		if nextOK {
 			end = nextStart
 		}
 	}
 	if start < exactStart {
 		start = exactStart
 	}
 	if exactEnd > 0 && end > exactEnd {
 		end = exactEnd
 	}
 	if end <= start {
 		return 0, 0, false, nil
 	}
 	return scanEntries(idxReader, idxData, start, end, word)
 }

 func locateFencePC(idxReader *blockReader, pcReader rangeReader, pcData, idxData []byte, fences []sectorFence, prefixLen int, exactStart, exactEnd uint32, word string) (uint32, uint32, bool, error) {
 	if len(fences) == 0 {
 		return locateLinear(idxReader, idxData, word)
 	}
 	start, end, err := narrowFencePCBounds(pcReader, pcData, idxData, prefixLen, exactStart, exactEnd, word)
 	if err != nil {
 		return 0, 0, false, err
 	}
 	if end <= start {
 		return 0, 0, false, nil
 	}
 	return scanEntries(idxReader, idxData, start, end, word)
 }

 func narrowFencePCBounds(pcReader rangeReader, pcData, idxData []byte, prefixLen int, start, end uint32, word string) (uint32, uint32, error) {
 	sectorsPerSidecar := fencePCSectorsPerBlock(prefixLen)
 	if end == 0 {
 		end = uint32(len(idxData))
 	}

 	tracef("#FENCEP prefixLen=%d sectorsPerSidecar=%d", prefixLen, sectorsPerSidecar)

 	for {
 		lo := int(start / blockSize)
 		hi := int((end - 1) / blockSize)
 		if lo >= hi {
 			break
 		}

 		oldStart, oldEnd := start, end
 		mid := lo + (hi-lo+1)/2
 		sidecarSector := mid / sectorsPerSidecar
 		sectorCount := (len(idxData) + blockSize - 1) / blockSize
 		entries, err := readFencePCBlock(pcReader, pcData, sectorCount, prefixLen, sidecarSector)
 		if err != nil {
 			return 0, 0, err
 		}
 		if len(entries) == 0 {
 			limit := uint32(sidecarSector * sectorsPerSidecar * blockSize)
 			if limit < end {
 				end = limit
 			}
 			if start == oldStart && end == oldEnd {
 				break
 			}
 			continue
 		}

 		if traceActive {
 			parts := make([]string, 0, len(entries))
 			for _, entry := range entries {
 				pfx := string(entry.prefix)
 				if idx := strings.IndexByte(pfx, 0); idx >= 0 {
 					pfx = pfx[:idx] + "$"
 				}
 				parts = append(parts, fmt.Sprintf("%d:%q@%d", int(entry.start/blockSize), pfx, entry.start))
 			}
 			tracef(" sectors: %s", strings.Join(parts, " "))
 		}

 		// Distinguish confirmed equality (entry prefix has null bytes — the fence
 		// word terminates within the prefix window) from ambiguous equality
 		// (full-width prefix, no nulls to confirm). Ambiguous entries are >= target
 		// but might be strictly greater, so they must not advance start.
 		lastLe := -1
 		firstGt := -1
 		for i, entry := range entries {
 			idx := bytes.IndexByte(entry.prefix, 0)
 			fenceWord := string(entry.prefix)
 			if idx >= 0 {
 				// Complete fence word
 				// Exact match logic: "prefer\x00" must be <= word
 				if fenceWord[:idx] <= word {
 					lastLe = i
 				} else {
 					firstGt = i
 					break
 				}
 			} else {
 				// Incomplete fence word (at least len(entry.prefix) bytes)
 				// Prefix match logic: "prefer" matches anything starting with "prefer"
 				if strings.HasPrefix(word, fenceWord) {
 					// Word starts with the fence, so fence is an "incomplete" prefix.
 					// The original code explicitly falls through here (does nothing).
 				} else if fenceWord < word {
 					lastLe = i
 				} else {
 					firstGt = i
 					break
 				}
 			}
 		}

 		// Advance start only via confirmed-safe entries; an ambiguous >= entry
 		// might be a fence word strictly greater than the target, which would
 		// cause us to skip the target sector.
 		if lastLe >= 0 {
 			start = max(start, entries[lastLe].start)
 		}
 		if firstGt >= 0 {
 			end = min(end, entries[firstGt].start)
 		}

 		tracef(
 			" probe mid=%d start:%d->%d end:%d->%d",
 			mid,
 			oldStart,
 			start,
 			oldEnd,
 			end,
 		)

 		if start == oldStart && end == oldEnd {
 			break
 		}
 		if int(start/blockSize)/sectorsPerSidecar == sidecarSector && int((end-1)/blockSize)/sectorsPerSidecar == sidecarSector {
 			break
 		}
 	}

 	return start, end, nil
 }

 func oftPageCount(oftData []byte) int {
 	if len(oftData) < oftHeaderSize+4 {
 		return 0
 	}
 	return (len(oftData) - oftHeaderSize) / 4
 }

 func readOftPageOffset(reader *blockReader, oftData []byte, page int) (uint32, error) {
 	if page == 0 {
 		return 0, nil
 	}
 	offset := uint32(oftHeaderSize + (page-1)*4)
 	if err := reader.TouchRange(offset, 4); err != nil {
 		return 0, err
 	}
 	return binary.LittleEndian.Uint32(oftData[offset : offset+4]), nil
 }

 func readOftPageEnd(reader *blockReader, oftData []byte, page int, idxSize uint32) (uint32, error) {
 	pageCount := oftPageCount(oftData)
 	if page+1 < pageCount {
 		return readOftPageOffset(reader, oftData, page+1)
 	}
 	offset := uint32(oftHeaderSize + (pageCount-1)*4)
 	if err := reader.TouchRange(offset, 4); err != nil {
 		return 0, err
 	}
 	end := binary.LittleEndian.Uint32(oftData[offset : offset+4])
 	if end == 0 {
 		return idxSize, nil
 	}
 	return end, nil
 }

 func readCsptHeader(reader *blockReader, csptData []byte) (uint32, error) {
 	if len(csptData) < csptHeaderSize {
 		return 0, nil
 	}
 	if err := reader.TouchRange(0, csptHeaderSize); err != nil {
 		return 0, err
 	}
 	return binary.LittleEndian.Uint32(csptData[8:12]), nil
 }

 func readCsptEntry(reader *blockReader, csptData []byte, idx int) (string, uint32, error) {
 	offset := uint32(csptHeaderSize + idx*(csptPrefixLen+4))
 	if err := reader.TouchRange(offset, csptPrefixLen+4); err != nil {
 		return "", 0, err
 	}
 	pfx := strings.TrimRight(string(csptData[offset:offset+csptPrefixLen]), "\x00")
 	start := binary.LittleEndian.Uint32(csptData[offset+csptPrefixLen : offset+csptPrefixLen+4])
 	return lowerASCII(pfx), start, nil
 }

 func readBase26Offset(reader *blockReader, data []byte, idx int) (uint32, error) {
 	offset := uint32(base26HeaderLen + idx*4)
 	if err := reader.TouchRange(offset, 4); err != nil {
 		return 0, err
 	}
 	return binary.LittleEndian.Uint32(data[offset : offset+4]), nil
 }

 func readFenceOffset(reader rangeReader, data []byte, idx int, sectorCount int) (uint16, error) {
 	lowOffset := uint32(sectorHeaderLen + idx)
 	if err := reader.TouchRange(lowOffset, 1); err != nil {
 		return 0, err
 	}
 	highOffset := uint32(sectorHeaderLen + sectorCount + idx/8)
 	if err := reader.TouchRange(highOffset, 1); err != nil {
 		return 0, err
 	}
 	rel := uint16(data[lowOffset])
 	high := data[highOffset]
 	if ((high >> uint(idx%8)) & 1) != 0 {
 		rel |= 0x100
 	}
 	return rel, nil
 }

 func readFenceWord(idxReader *blockReader, fenceReader rangeReader, fenceData, idxData []byte, sectorCount, sector int) (string, uint32, bool, error) {
 	start, ok, err := resolveFenceStart(idxReader, fenceReader, fenceData, idxData, sectorCount, sector)
 	if err != nil || !ok {
 		return "", 0, ok, err
 	}
 	word, err := readWordAt(idxReader, idxData, start)
 	if err != nil {
 		return "", 0, false, err
 	}
 	return word, start, true, nil
 }

 func resolveFenceStart(idxReader *blockReader, fenceReader rangeReader, fenceData, idxData []byte, sectorCount, sector int) (uint32, bool, error) {
 	if sector < 0 {
 		return 0, false, nil
 	}
 	sectorBase := uint32(sector * blockSize)
 	if sectorBase >= uint32(len(idxData)) {
 		return 0, false, nil
 	}
 	rel, err := readFenceOffset(fenceReader, fenceData, sector, sectorCount)
 	if err != nil {
 		return 0, false, err
 	}
 	start := sectorBase + uint32(rel)
 	if start >= uint32(len(idxData)) {
 		return 0, false, fmt.Errorf("fence offset out of range for sector %d", sector)
 	}
 	if _, err := readWordAt(idxReader, idxData, start); err != nil {
 		return 0, false, err
 	}
 	return start, true, nil
 }

 func readFencePCEntry(reader rangeReader, data []byte, sectorCount, prefixLen, sector int) ([]byte, uint32, bool, error) {
 	if sector < 0 || sector >= sectorCount {
 		return nil, 0, false, nil
 	}
 	group := sector / 8
 	local := sector % 8
 	groupSize := fencePCGroupSize(prefixLen)
 	groupsPerSector := fencePCGroupsPerSector(prefixLen)
 	sidecarSector := group / groupsPerSector
 	groupInSector := group % groupsPerSector
 	groupOffset := sidecarSector*blockSize + groupInSector*groupSize
 	if groupOffset+groupSize > len(data) {
 		return nil, 0, false, nil
 	}
 	if err := reader.TouchRange(uint32(groupOffset), groupSize); err != nil {
 		return nil, 0, false, err
 	}
 	block := data[groupOffset : groupOffset+groupSize]
 	rel := uint16(block[local])
 	if ((block[8] >> uint(local)) & 1) != 0 {
 		rel |= 0x100
 	}
 	start := uint32(sector*blockSize) + uint32(rel)
 	prev := make([]byte, 0, prefixLen)
 	prefixPos := 9
 	for i := 0; i <= local; i++ {
 		slot := block[prefixPos : prefixPos+prefixLen]
 		prefixPos += prefixLen
 		var cur []byte
 		if i == 0 || slot[0]&0x80 == 0 {
 			cur = trimZeros(slot)
 		} else {
 			common := int(slot[0] & 0x7f)
 			cur = make([]byte, 0, common+prefixLen-1)
 			if common > len(prev) {
 				common = len(prev)
 			}
 			cur = append(cur, prev[:common]...)
 			cur = append(cur, trimZeros(slot[1:])...)
 		}
 		prev = append(prev[:0], cur...)
 		if i == local {
 			return append([]byte(nil), cur...), start, true, nil
 		}
 	}
 	return nil, 0, false, nil
 }

 func fencePCGroupSize(prefixLen int) int {
 	return 9 + 8*prefixLen
 }

 func fencePCGroupsPerSector(prefixLen int) int {
 	groups := blockSize / fencePCGroupSize(prefixLen)
 	if groups < 1 {
 		return 1
 	}
 	return groups
 }

 func fencePCSectorsPerBlock(prefixLen int) int {
 	return fencePCGroupsPerSector(prefixLen) * 8
 }

 func readFencePCBlock(reader rangeReader, data []byte, sectorCount, prefixLen, pcSector int) ([]fencePCBlockEntry, error) {
 	groupSize := fencePCGroupSize(prefixLen)
 	groupsPerSector := fencePCGroupsPerSector(prefixLen)
 	sectorOffset := pcSector * blockSize
 	if sectorOffset >= len(data) {
 		return nil, nil
 	}
 	touchLen := blockSize
 	if sectorOffset+touchLen > len(data) {
 		touchLen = len(data) - sectorOffset
 	}
 	if err := reader.TouchRange(uint32(sectorOffset), touchLen); err != nil {
 		return nil, err
 	}
 	firstGroup := pcSector * groupsPerSector
 	entries := make([]fencePCBlockEntry, 0, groupsPerSector*8)
 	for group := 0; group < groupsPerSector; group++ {
 		groupIndex := firstGroup + group
 		groupOffset := sectorOffset + group*groupSize
 		if groupOffset+groupSize > len(data) {
 			break
 		}
 		block := data[groupOffset : groupOffset+groupSize]
 		prev := make([]byte, 0, prefixLen)
 		for local := 0; local < 8; local++ {
 			sector := groupIndex*8 + local
 			if sector >= sectorCount {
 				break
 			}
 			rel := uint16(block[local])
 			if ((block[8] >> uint(local)) & 1) != 0 {
 				rel |= 0x100
 			}
 			slot := block[9+local*prefixLen : 9+(local+1)*prefixLen]
 			var cur []byte
 			if local == 0 || slot[0]&0x80 == 0 {
 				cur = slot
 			} else {
 				common := int(slot[0] & 0x7f)
 				if common > len(prev) {
 					common = len(prev)
 				}
 				cur = make([]byte, 0, common+prefixLen-1)
 				cur = append(cur, prev[:common]...)
 				cur = append(cur, slot[1:]...)
 			}
 			prev = append(prev[:0], cur...)
 			entries = append(entries, fencePCBlockEntry{
 				sector: sector,
 				prefix: append([]byte(nil), cur...),
 				start:  uint32(sector*blockSize) + uint32(rel),
 			})
 		}
 	}
 	return entries, nil
 }

 func locateTabBounds(reader rangeReader, entries []tabEntry, word string, sectorCount int) (int, int, error) {
 	if len(entries) == 0 {
 		return 0, sectorCount - 1, nil
 	}
 	target := lowerASCII(word)
 	targetPrefix := prefix(target, len(entries[0].prefix))
 	lo, hi := 0, len(entries)-1
 	prefixLen := len(entries[0].prefix)
 	for lo < hi {
 		mid := lo + (hi-lo+1)/2
 		if _, err := readTabEntry(reader, entries, mid, prefixLen); err != nil {
 			return 0, 0, err
 		}
 		if tabPrefixCmp(entries[mid].prefix, targetPrefix) > 0 {
 			hi = mid - 1
 		} else {
 			lo = mid
 		}
 	}
 	groupLo := lo
 	for groupLo > 0 && tabPrefixCmp(entries[groupLo-1].prefix, targetPrefix) == 0 {
 		if _, err := readTabEntry(reader, entries, groupLo-1, prefixLen); err != nil {
 			return 0, 0, err
 		}
 		groupLo--
 	}
 	groupHi := lo
 	for groupHi+1 < len(entries) && tabPrefixCmp(entries[groupHi+1].prefix, targetPrefix) == 0 {
 		if _, err := readTabEntry(reader, entries, groupHi+1, prefixLen); err != nil {
 			return 0, 0, err
 		}
 		groupHi++
 	}
 	lower := 0
 	if groupLo > 0 {
 		lower = sampledSector(groupLo-1, len(entries), sectorCount)
 	}
 	upper := sectorCount - 1
 	if groupHi+1 < len(entries) {
 		if _, err := readTabEntry(reader, entries, groupHi+1, prefixLen); err != nil {
 			return 0, 0, err
 		}
 		upper = sampledSector(groupHi+1, len(entries), sectorCount)
 	}
 	if lower < 0 {
 		lower = 0
 	}
 	if upper < lower {
 		upper = lower
 	}
 	if upper >= sectorCount {
 		upper = sectorCount - 1
 	}
 	return lower, upper, nil
 }

 func paddedPrefixBytes(word string, prefixLen int) []byte {
 	out := make([]byte, prefixLen)
 	target := lowerASCII(word)
 	for i := 0; i < prefixLen && i < len(target); i++ {
 		out[i] = target[i]
 	}
 	return out
 }

 func commonPrefixLen(a, b []byte) int {
 	n := len(a)
 	if len(b) < n {
 		n = len(b)
 	}
 	for i := 0; i < n; i++ {
 		if a[i] != b[i] {
 			return i
 		}
 	}
 	return n
 }

 func commonPrefixLenString(a, b string) int {
 	n := len(a)
 	if len(b) < n {
 		n = len(b)
 	}
 	for i := 0; i < n; i++ {
 		if a[i] != b[i] {
 			return i
 		}
 	}
 	return n
 }

 func suffixBytes(word string, start, n int) []byte {
 	out := make([]byte, n)
 	if start >= len(word) {
 		return out
 	}
 	end := start + n
 	if end > len(word) {
 		end = len(word)
 	}
 	copy(out, []byte(word[start:end]))
 	return out
 }

 func trimZeros(b []byte) []byte {
 	end := len(b)
 	for end > 0 && b[end-1] == 0 {
 		end--
 	}
 	return append([]byte(nil), b[:end]...)
 }

 func readTabEntry(reader rangeReader, entries []tabEntry, idx, prefixLen int) (string, error) {
 	offset := uint32(idx * prefixLen)
 	if err := reader.TouchRange(offset, prefixLen); err != nil {
 		return "", err
 	}
 	return entries[idx].prefix, nil
 }

 func locateTabBoundsCold(entries []tabEntry, word string, sectorCount int) (int, int) {
 	if len(entries) == 0 {
 		return 0, sectorCount - 1
 	}
 	target := lowerASCII(word)
 	targetPrefix := prefix(target, len(entries[0].prefix))
 	lo, hi := 0, len(entries)-1
 	for lo < hi {
 		mid := lo + (hi-lo+1)/2
 		if tabPrefixCmp(entries[mid].prefix, targetPrefix) > 0 {
 			hi = mid - 1
 		} else {
 			lo = mid
 		}
 	}
 	groupLo := lo
 	for groupLo > 0 && tabPrefixCmp(entries[groupLo-1].prefix, targetPrefix) == 0 {
 		groupLo--
 	}
 	groupHi := lo
 	for groupHi+1 < len(entries) && tabPrefixCmp(entries[groupHi+1].prefix, targetPrefix) == 0 {
 		groupHi++
 	}
 	lower := 0
 	if groupLo > 0 {
 		lower = sampledSector(groupLo-1, len(entries), sectorCount)
 	}
 	upper := sectorCount - 1
 	if groupHi+1 < len(entries) {
 		upper = sampledSector(groupHi+1, len(entries), sectorCount)
 	}
 	if upper < lower {
 		upper = lower
 	}
 	if upper >= sectorCount {
 		upper = sectorCount - 1
 	}
 	return lower, upper
 }

 func buildTabStat(name string, entries []tabEntry, prefixLen int) tabStat {
 	if len(entries) == 0 {
 		return tabStat{name: name, firstBytes: prefixLen}
 	}
 	identical := 0
 	unique := 1
 	maxRun := 1
 	run := 1
 	for i := 1; i < len(entries); i++ {
 		if entries[i].prefix == entries[i-1].prefix {
 			identical++
 			run++
 			if run > maxRun {
 				maxRun = run
 			}
 			continue
 		}
 		unique++
 		run = 1
 	}
 	return tabStat{
 		name:       name,
 		entries:    len(entries),
 		identical:  identical,
 		unique:     unique,
 		maxRun:     maxRun,
 		firstBytes: prefixLen,
 	}
 }

 func sampledSector(i, entryCount, sectorCount int) int {
 	if entryCount <= 1 || sectorCount <= 1 {
 		return 0
 	}
 	return (i * (sectorCount - 1)) / (entryCount - 1)
 }

 func blockCount(n int) int {
 	if n <= 0 {
 		return 0
 	}
 	return (n + blockSize - 1) / blockSize
 }

 func blocksBetween(start, end uint32) int {
 	if end <= start {
 		return 0
 	}
 	return int((end-1)/blockSize - start/blockSize + 1)
 }

 func ceilLog2(n int) int {
 	if n <= 1 {
 		return 0
 	}
 	out := 0
 	v := 1
 	for v < n {
 		v <<= 1
 		out++
 	}
 	return out
 }

 func tabPrefixCmp(tabPrefix, targetPrefix string) int {
 	if len(targetPrefix) < len(tabPrefix) && strings.HasPrefix(tabPrefix, targetPrefix) {
 		return 0
 	}
 	return asciiCmp(tabPrefix, targetPrefix)
 }

 func baseNCode(word string, prefixLen, radix int) int {
 	target := lowerASCII(word)
 	code := 0
 	clampedLow := false
 	clampedHigh := false
 	for i := 0; i < prefixLen; i++ {
 		code *= radix
 		if clampedLow {
 			continue
 		}
 		if clampedHigh {
 			code += radix - 1
 			continue
 		}
 		var b byte
 		if i < len(target) {
 			b = target[i]
 		}
 		switch {
 		case b < 'a':
 			clampedLow = true
 		case b > 'z':
 			clampedHigh = true
 			code += radix - 1
 		default:
 			code += int(b-'a') * radix / 26
 		}
 	}
 	return code
 }

 func scanEntries(reader *blockReader, idxData []byte, start, end uint32, word string) (uint32, uint32, bool, error) {
 	pos := start
 	target := lowerASCII(word)

 	tracef("#SCAN linear start=%d end=%d", start, end)

 	for pos < end {
 		entryWord, nextPos, err := readEntryWord(reader, idxData, pos)
 		if err != nil {
 			return 0, 0, false, err
 		}
 		if nextPos > uint32(len(idxData)) {
 			return 0, 0, false, fmt.Errorf("entry at %d overran idx bounds", pos)
 		}
 		payloadStart := nextPos - 8
 		if payloadStart+8 > uint32(len(idxData)) {
 			return 0, 0, false, fmt.Errorf("payload at %d out of bounds", payloadStart)
 		}
 		cmp := asciiCmp(entryWord, target)
 		if cmp == 0 {
 			offset := binary.BigEndian.Uint32(idxData[payloadStart : payloadStart+4])
 			size := binary.BigEndian.Uint32(idxData[payloadStart+4 : payloadStart+8])
 			return offset, size, true, nil
 		}
 		if cmp > 0 {
 			tracef("SCAN FAILED")
 			return 0, 0, false, nil
 		}
 		pos = nextPos
 	}
 	return 0, 0, false, nil
 }

 func readWordAt(reader *blockReader, idxData []byte, pos uint32) (string, error) {
 	word, _, err := readEntryWord(reader, idxData, pos)
 	return word, err
 }

 func readEntryWord(reader *blockReader, idxData []byte, pos uint32) (string, uint32, error) {
 	buf := make([]byte, 0, 32)
 	for {
 		b, err := reader.ReadByteAt(pos)
 		if err != nil {
 			return "", 0, err
 		}
 		pos++
 		if b == 0 {
 			break
 		}
 		buf = append(buf, b)
 	}
 	for i := 0; i < 8; i++ {
 		if _, err := reader.ReadByteAt(pos + uint32(i)); err != nil {
 			return "", 0, err
 		}
 	}
 	return lowerASCII(string(buf)), pos + 8, nil
 }

 func asciiCmp(a, b string) int {
 	la := len(a)
 	lb := len(b)
 	n := la
 	if lb < n {
 		n = lb
 	}
 	for i := 0; i < n; i++ {
 		aa := lowerASCIIB(a[i])
 		bb := lowerASCIIB(b[i])
 		if aa < bb {
 			return -1
 		}
 		if aa > bb {
 			return 1
 		}
 	}
 	switch {
 	case la < lb:
 		return -1
 	case la > lb:
 		return 1
 	default:
 		return 0
 	}
 }

 func lowerASCII(s string) string {
 	buf := []byte(s)
 	for i := range buf {
 		buf[i] = lowerASCIIB(buf[i])
 	}
 	return string(buf)
 }

 func lowerASCIIB(b byte) byte {
 	if 'A' <= b && b <= 'Z' {
 		return b + ('a' - 'A')
 	}
 	return b
 }

 func prefix(s string, n int) string {
 	if len(s) <= n {
 		return s
 	}
 	return s[:n]
 }

 func printSummary(files dictFiles, idxData, dictData []byte, entries []idxEntry, stats []methodStat, tabStats []tabStat, showAll, showExamples bool) {
 	fmt.Printf("dictionary\t%s\n", files.stem)
 	fmt.Printf("entries\t%d\n", len(entries))
 	fmt.Printf("idx_bytes\t%d\n", len(idxData))
 	fmt.Printf("dict_bytes\t%d\n", len(dictData))
 	fmt.Printf("sample_words\t%s\n\n", previewWords(entries))
 	fmt.Printf("stats track the number of 512B sector reads (SPI SD) to determine the exact offset of a dictionary word entry\n\n")

 	w := tabwriter.NewWriter(os.Stdout, 0, 2, 2, ' ', 0)
 	if showExamples {
 		fmt.Fprintln(w, "method\tbytes\tmiss\t \tmin\t \tmedian\t \tp95\t \tmax\t \tavg")
 	} else {
 		fmt.Fprintln(w, "method\tbytes\tmiss\tmin\tmedian\tp95\tmax\tavg")
 	}
 	for _, stat := range stats {
 		if len(stat.counts) == 0 {
 			if showExamples {
 				fmt.Fprintf(w, "%s\t%d\t%d\t%s\t-\t-\t-\t-\t-\t-\t-\t-\t-\n", stat.name, stat.extraSize, stat.misses, stat.missWord)
 			} else {
 				fmt.Fprintf(w, "%s\t%d\t%d\t-\t-\t-\t-\t-\n", stat.name, stat.extraSize, stat.misses)
 			}
 			continue
 		}
 		sortedCounts := append([]int(nil), stat.counts...)
 		sort.Ints(sortedCounts)
 		minCount := sortedCounts[0]
 		med := median(sortedCounts)
 		p95Count := percentile(sortedCounts, 95)
 		maxCount := sortedCounts[len(sortedCounts)-1]
 		if showExamples {
 			fmt.Fprintf(w, "%s\t%d\t%d\t%s\t%d\t%s\t%g\t%s\t%d\t%s\t%d\t%s\t%.2f\n",
 				stat.name,
 				stat.extraSize,
 				stat.misses,
 				stat.missWord,
 				minCount,
 				stat.examples[minCount],
 				med,
 				stat.examples[int(med)],
 				p95Count,
 				stat.examples[p95Count],
 				maxCount,
 				stat.examples[maxCount],
 				average(sortedCounts),
 			)
 		} else {
 			fmt.Fprintf(w, "%s\t%d\t%d\t%d\t%g\t%d\t%d\t%.2f\n",
 				stat.name,
 				stat.extraSize,
 				stat.misses,
 				minCount,
 				med,
 				p95Count,
 				maxCount,
 				average(sortedCounts),
 			)
 		}
 	}
 	_ = w.Flush()

 	if !showAll || len(tabStats) == 0 {
 		return
 	}
 	fmt.Printf("\n")
 	tw := tabwriter.NewWriter(os.Stdout, 0, 2, 2, ' ', 0)
 	fmt.Fprintln(tw, "tab\tprefix_bytes\tentries\tadj_identical\tunique\tmax_run")
 	for _, stat := range tabStats {
 		fmt.Fprintf(tw, "%s\t%d\t%d\t%d\t%d\t%d\n",
 			stat.name,
 			stat.firstBytes,
 			stat.entries,
 			stat.identical,
 			stat.unique,
 			stat.maxRun,
 		)
 	}
 	_ = tw.Flush()
 }

 func showMethod(name string) bool {
 	if strings.HasPrefix(name, "fence-") {
 		return false
 	}
 	if strings.HasPrefix(name, "fencep_") {
 		return false
 	}
 	if plainFencePCPattern.MatchString(name) {
 		return false
 	}
 	return !fencePCBase26Pattern.MatchString(name)
 }

 func shouldRunMethod(name string, showAll bool, runRE *regexp.Regexp) bool {
 	if runRE != nil {
 		return runRE.MatchString(name)
 	}
 	if showAll {
 		return true
 	}
 	return showMethod(name)
 }

 func beginTrace(methodName, word string) func() {
 	if traceWord == "" || traceWord != word {
 		return func() {}
 	}
 	if traceMethodRE != nil && !traceMethodRE.MatchString(methodName) {
 		return func() {}
 	}
 	prevActive := traceActive
 	prevMethod := traceMethodName
 	traceActive = true
 	traceMethodName = methodName
 	fmt.Fprintf(os.Stderr, "TRACE method=%s word=%q\n", methodName, word)
 	return func() {
 		traceActive = prevActive
 		traceMethodName = prevMethod
 	}
 }

 func tracef(format string, args ...any) {
 	if !traceActive {
 		return
 	}
 	fmt.Fprintf(os.Stderr, "TRACE %s\n", fmt.Sprintf(format, args...))
 }

 func traceBlockRead(label string, offset uint32) {
 	if !traceActive {
 		return
 	}
 	if label == "" {
 		label = "unknown"
 	}
 	tracef("   read-%s offset=%d block=%d", label, offset, int(offset)/blockSize)
 	if traceStackEnabled {
 		fmt.Fprint(os.Stderr, traceStack())
 	}
 }

 func traceStack() string {
 	stack := string(debug.Stack())
 	lines := strings.Split(strings.TrimRight(stack, "\n"), "\n")
 	if len(lines) <= 7 {
 		return stack
 	}
 	lines = lines[7:] // drop header + three helper frames (1 + 3*2 lines)
 	cut := len(lines)
 	for i := 0; i+1 < len(lines); i += 2 {
 		if strings.Contains(lines[i], "main.main(") {
 			cut = i
 			if cut >= 2 {
 				cut -= 2 // also drop the method builder closure frame above main.main
 			}
 			break
 		}
 	}
 	if cut < 0 {
 		cut = 0
 	}
 	return strings.Join(lines[:cut], "\n") + "\n"
 }

 func previewWords(entries []idxEntry) string {
 	limit := maxPreviewWords
 	if len(entries) < limit {
 		limit = len(entries)
 	}
 	parts := make([]string, 0, limit)
 	for i := 0; i < limit; i++ {
 		parts = append(parts, entries[i].word)
 	}
 	return strings.Join(parts, ", ")
 }

 func median(sortedVals []int) float64 {
 	n := len(sortedVals)
 	if n%2 == 1 {
 		return float64(sortedVals[n/2])
 	}
 	return float64(sortedVals[n/2-1]+sortedVals[n/2]) / 2.0
 }

 func percentile(sortedVals []int, p int) int {
 	if len(sortedVals) == 0 {
 		return 0
 	}
 	if p <= 0 {
 		return sortedVals[0]
 	}
 	if p >= 100 {
 		return sortedVals[len(sortedVals)-1]
 	}
 	idx := (p*(len(sortedVals)-1) + 99) / 100
 	if idx >= len(sortedVals) {
 		idx = len(sortedVals) - 1
 	}
 	return sortedVals[idx]
 }

 func average(vals []int) float64 {
 	if len(vals) == 0 {
 		return 0
 	}
 	total := 0
 	for _, v := range vals {
 		total += v
 	}
 	return float64(total) / float64(len(vals))
 }
No results found