HDCSTORAGE: hyperdimensional computer, webOS and agentic MCP layer (stdlib-only Python)

ad474c9 verified 5 days ago

16 kB

"""Binary hypervector algebra for HDCSTORAGE.
Everything in this machine is a *bit-packed hypervector*: a Python ``int``
interpreted as ``d`` bits, bit 0 being the least significant.  Representation
choices, and why:
* **No numpy.**  Dense HDC is normally an array of +/-1 floats or of packed
  uint64 words.  A Python ``int`` of 10 000 bits is one object whose bitwise
  ops run in C over whole machine words, so ``bind`` is a single ``^`` and
  ``popcount`` is ``int.bit_count()``.  Memory per vector is d/8 bytes plus
  object overhead, no dependency, and no per-element Python loop.
* **Binary spatter codes (BSC).**  bind = XOR (self-inverse, so unbind ==
  bind), bundle = per-bit majority, permute = rotate within the d-bit mask.
Algebraic facts this module relies on, used everywhere downstream:
    bind(a, b) ^ b == a                       (self-inverse)
    sim(bind(a, x), bind(b, x)) ~= sim(a, b)  (binding preserves similarity)
    sim(permute(a, k), permute(b, k)) == sim(a, b)
    sim(bundle(S), x) ~ sqrt(1/|S|)	for x in S  -> cleanup recovers members
    E[sim(a, b)] == 0 for independent random a, b (sd ~ 1/sqrt(d))
The last line is the reason d is large: it sets the noise floor that cleanup
memory and the instruction decoder have to beat.
"""

from __future__ import annotations

import hashlib
import math
from typing import Iterable, Sequence

__all__ = [
    "DEFAULT_DIM",
    "mask",
    "popcount",
    "hamming",
    "random_hv",
    "hvc",
    "bind",
    "unbind",
    "bundle",
    "permute",
    "permute_inv",
    "sim",
    "sim_matrix",
    "int_to_hv",
    "hv_to_int",
    "hv_bits_of_int",
    "hv_from_bits",
    "hv_to_bits",
    "bit_probe",
    "shift",
    "CODEC_THRESHOLD",
    "MAX_INT_BITS",
    "density",
    "bits",
    "bitplanes",
    "role",
    "ROLES",
    "clear_cache",
]

#: Default dimensionality.  10 000 bits is the classic Kanerva/VSA size: the
#: noise floor 1/sqrt(d) ~ 0.01 is far below the ~0.4 signal of a bundle
#: member, so 4-6 field records decode reliably while 1 250 bytes per vector
#: still fits a program image in a few hundred kilobytes.
DEFAULT_DIM = 10_000


# --------------------------------------------------------------------------
# primitive bit operations
# --------------------------------------------------------------------------
def mask(d: int = DEFAULT_DIM) -> int:
    """The all-ones mask covering ``d`` bits."""
    return (1 << d) - 1


def popcount(x: int) -> int:
    """Number of set bits."""
    return x.bit_count()


def hamming(a: int, b: int) -> int:
    """Hamming distance between two hypervectors."""
    return (a ^ b).bit_count()


def density(v: int, d: int = DEFAULT_DIM) -> float:
    """Fraction of set bits (should hover near 0.5 for random vectors)."""
    return popcount(v & mask(d)) / d


def bits(v: int, d: int = DEFAULT_DIM) -> str:
    """Bit string, most-significant bit first (the usual left-to-right view)."""
    return format(v & mask(d), "0%db" % d)


def bitplanes(v: int, d: int = DEFAULT_DIM, width: int = 64) -> list[str]:
    """Split a vector into fixed-width bit planes, WSB first."""
    s = bits(v, d)
    return [s[i : i + width] for i in range(0, len(s), width)]


# --------------------------------------------------------------------------
# deterministic symbol -> hypervector
# --------------------------------------------------------------------------
_CACHE: dict[tuple[str, int], int] = {}


def clear_cache() -> None:
    _CACHE.clear()


def hvc(name: str, d: int = DEFAULT_DIM) -> int:
    """Deterministic hypervector for a symbol name.
    The same name always maps to the same vector, in-process and across runs,
    on any machine.  That is what makes a stored program image portable: the
    symbolic layer (opcodes, register names, literals, tool names) is
    *regenerated* from names rather than serialised, and only the composed
    instruction vectors live in the storage file.
    Uses BLAKE2b expanded over a 4-byte block counter, then masked to d bits.
    """
    key = (name, d)
    cached = _CACHE.get(key)
    if cached is not None:
        return cached
    out = 0
    block = 0
    h = hashlib.blake2b(name.encode("utf-8"), digest_size=64)
    seed = h.digest()
    while out.bit_length() < d:
        chunk = hashlib.blake2b(
            seed + block.to_bytes(4, "little"), digest_size=64
        ).digest()
        out = (out << 512) | int.from_bytes(chunk, "big")
        block += 1
    out &= mask(d)
    _CACHE[key] = out
    return out


def random_hv(d: int = DEFAULT_DIM, rng=None) -> int:
    """Random balanced hypervector (about d/2 set bits)."""
    if rng is None:
        import random

        rng = random
    return rng.getrandbits(d) & mask(d)


# Roles: named slots used to build records.  BSC's canonical record is
#   record = bundle([bind(role_i, value_i) for i in fields])
# and a field is read back with bind(record, role_i) -> noisy value_i.
ROLES: dict[str, str] = {
    "op": "role/operation",
    "ra": "role/dest-register",
    "rb": "role/source-register-b",
    "rc": "role/source-register-c",
    "imm": "role/immediate",
    "tgt": "role/target-pc",
    "addr": "role/address",
    "val": "role/value",
    "name": "role/name",
    "cap": "role/capability",
    "doc": "role/documentation",
    "arity": "role/arity",
    "tool": "role/tool",
    "arg": "role/argument",
    "tag": "role/tag",
    "kind": "role/kind",
}


def role(name: str, d: int = DEFAULT_DIM) -> int:
    """Hypervector for a role slot (``"op"``, ``"ra"``, ...)."""
    return hvc(ROLES.get(name, name), d)


# --------------------------------------------------------------------------
# the algebra
# --------------------------------------------------------------------------
def bind(a: int, b: int, d: int | None = None) -> int:
    """Binding = XOR.  Involutive: ``bind(bind(a, b), b) == a``."""
    v = a ^ b
    return v & mask(d) if d is not None else v


def unbind(record: int, key: int, d: int | None = None) -> int:
    """Unbinding is binding (XOR is self-inverse); named for readability."""
    return bind(record, key, d)


def permute(v: int, k: int = 1, d: int = DEFAULT_DIM) -> int:
    """Cyclic bit rotation left by ``k`` (a rotation, so no bits are lost).
    Permutation is how this machine encodes *order*: position p of a sequence
    is ``permute(item, p)``, which keeps items near-orthogonal while making
    "same item, different position" a different address.
    """
    m = mask(d)
    v &= m
    k %= d
    if k == 0:
        return v
    return ((v << k) | (v >> (d - k))) & m


def permute_inv(v: int, k: int = 1, d: int = DEFAULT_DIM) -> int:
    """Inverse rotation (rotate right by ``k``)."""
    return permute(v, -k, d)


def _add_bitplane(plates: list[int], v: int) -> None:
    """Ripple-carry add of one bit-plane into a binary counter."""
    i = 0
    carry = v
    while carry:
        if i == len(plates):
            plates.append(carry)
            return
        nxt = plates[i] & carry
        plates[i] ^= carry
        carry = nxt
        i += 1


def _plane_ge(plates: Sequence[int], threshold: int, d: int) -> int:
    """Bit-sliced ``count >= threshold`` over the counter planes.
    Walks planes from most to least significant holding one predicate, ``eq``
    ("equal to the threshold so far"), and one accumulator, ``gt`` ("already
    greater, therefore certainly >= threshold").  Lanes that fall below the
    threshold at some position are dropped from ``eq`` and die there, which is
    exactly a ripple comparator built from AND/NOT — the same gate logic a
    hardware majority element uses, widened to d lanes at once.
    """
    m = mask(d)
    nbits = max(len(plates), threshold.bit_length()) or 1
    eq = m
    gt = 0
    for i in range(nbits - 1, -1, -1):
        p = plates[i] if i < len(plates) else 0
        if (threshold >> i) & 1:
            eq &= p  # count bit 0 where threshold bit is 1  ->  too small
        else:
            gt |= eq & p  # count bit 1 where threshold bit is 0  ->  greater
            eq &= ~p & m
        if eq == 0:
            break
    return (gt | eq) & m


def bundle(vecs: Iterable[int], d: int = DEFAULT_DIM) -> int:
    """Majority bundling: per-bit vote, ties resolve to 0.
    Implemented bit-sliced: every vector is added into a d-lane binary
    counter (one Python int per bit position of the count), then a single
    vectorised comparator thresholds it at ``floor(n/2)+1``.  Cost is
    O(n * log n) big-int operations rather than O(n * d) element visits,
    which is what keeps a 10 000-bit bundle at tens of microseconds.
    """
    items = list(vecs)
    if not items:
        return 0
    if len(items) == 1:
        return items[0] & mask(d)
    plates: list[int] = []
    for v in items:
        _add_bitplane(plates, v & mask(d))
    return _plane_ge(plates, len(items) // 2 + 1, d)


def sim(a: int, b: int, d: int = DEFAULT_DIM) -> float:
    """Cosine-style similarity in [-1, 1]: agreement of bits, rescaled.
    ``sim = (d - 2*hamming) / d``; +1 identical, 0 orthogonal, -1 complement.
    """
    if d <= 0:
        raise ValueError("d must be positive")
    return (d - 2 * (a ^ b).bit_count()) / d


def sim_matrix(vecs: Sequence[int], d: int = DEFAULT_DIM) -> list[list[float]]:
    """All-pairs similarity matrix."""
    return [[sim(a, b, d) for b in vecs] for a in vecs]


# --------------------------------------------------------------------------
# integers stored *as* hypervectors
# --------------------------------------------------------------------------
# A scalar is represented by superposition of bit-position atoms:
#   int_to_hv(n) = bundle([bind(NUM, permute(BITBASE, i)) for i where n has bit i])
# so an integer occupies a vector like every other value and can be recovered
# by cleanup (one similarity probe per bit position).  This is the pixel that
# makes "all state is hyperdimensional" true rather than decorative.
#
# The layout is **two's complement**, 32 bits: bit MAX_INT_BITS-1 is the sign,
# and a negative value is dense where a sign-magnitude encoding would be
# sparse.  That choice is what lets arithmetic happen as a ripple-carry
# circuit over the bit atoms (see hdc/adder.py): two's complement makes
# addition a pure function of the bits, with no sign case analysis anywhere.
_NUM = hvc("codec/integer")
_BITBASE = hvc("codec/bit-position")

#: Width of the integer payload, in bits, two's complement.
MAX_INT_BITS = 32

#: Similarity above which a bit atom counts as present in a bundle.
#:
#: Measured on this implementation (40 random atom subsets per size, both
#: dimensions): a member of a k-atom bundle recovers at 1/sqrt(k) — 0.35 at
#: k=4 down to 0.136 at k=32 — while a non-member stays below 0.044 at
#: d=10 000 and below 0.093 at d=2 000.  0.10 is the value that separates all
#: of those cases and round-trips 415/415 sampled 32-bit values at both
#: dimensions; d=2 000 is therefore the supported floor for the codec.
CODEC_THRESHOLD = 0.10

#: Smallest dimension at which the integer codec round-trips reliably.
#:
#: Measured over all 256 byte values plus 200 random bytes: 0 errors at
#: d=1500, 2000 and 3000; **60 errors at d=1000** and 401 at d=500, with a
#: worst delta of 512.  Below this floor the bit atoms crosstalk enough that a
#: decode silently returns a neighbouring value, which would corrupt every
#: threshold and shift downstream, so the codec refuses instead.
MIN_CODEC_DIM = 1500


def _check_dim(d: int) -> None:
    if d < MIN_CODEC_DIM:
        raise ValueError(
            "integer codec needs d >= %d (got %d): bit atoms crosstalk below that "
            "and values decode wrong" % (MIN_CODEC_DIM, d)
        )


def _bit_probe(i: int, d: int) -> int:
    return bind(_NUM, permute(_BITBASE, i, d), d)


def bit_probe(i: int, d: int = DEFAULT_DIM) -> int:
    """The atom for bit position ``i``, for probing a coded value directly.
    Exposed because other layers (the shader) need single-bit tests — sign,
    ordering — without decoding the whole integer.
    """
    return _bit_probe(i, d)


def int_to_hv(n: int, d: int = DEFAULT_DIM) -> int:
    """Encode a signed 32-bit integer as a hypervector (two's complement).
    Zero encodes to the all-zero vector (the empty bundle), so a cleared
    register is literally a vector with no atoms in it.
    This codec is *symbolic, not similarity-preserving*: two integers that
    share set bits share bit-position atoms, so ``sim(int_to_hv(5),
    int_to_hv(37))`` is high even though 5 and 37 have nothing to do with each
    other.  That is deliberate — decode needs the atoms to be shared and
    probeable, exactly like a bit field.  Do not read a distance between two
    encoded integers as a semantic relationship, and do not expect binding two
    of them to decorrelate the way binding two random vectors does.
    """
    _check_dim(d)
    lo, hi = -(1 << (MAX_INT_BITS - 1)), (1 << (MAX_INT_BITS - 1)) - 1
    if not lo <= n <= hi:
        raise ValueError("integer outside the %d-bit codec range: %r" % (MAX_INT_BITS, n))
    return hv_from_bits(hv_bits_of_int(n), d)


def hv_bits_of_int(n: int) -> list[int]:
    """The two's complement bit pattern of an integer, least significant first."""
    pattern = n & ((1 << MAX_INT_BITS) - 1)
    return [(pattern >> i) & 1 for i in range(MAX_INT_BITS)]


def hv_from_bits(bits: Sequence[int], d: int = DEFAULT_DIM) -> int:
    """Assemble a hypervector from bit values, purely by bundling atoms.
    No integer arithmetic is involved: each set position contributes its atom
    to a majority bundle.  Two's complement sign extension is the caller's
    concern, exactly as it is in hardware.
    """
    parts = [_bit_probe(i, d) for i, bit in enumerate(bits) if bit]
    return bundle(parts, d) if parts else 0


def hv_to_bits(v: int, d: int = DEFAULT_DIM, threshold: float = CODEC_THRESHOLD) -> list[int]:
    """Read the bit pattern back with one similarity probe per position."""
    return [1 if sim(v, _bit_probe(i, d), d) >= threshold else 0 for i in range(MAX_INT_BITS)]


def shift(v: int, k: int, d: int = DEFAULT_DIM) -> int:
    """Multiply or divide a coded integer by 2**k, without decoding it.
    This works only because the bit atoms are a *permutation orbit*:
    ``atom(i) = NUM ^ perm(BITBASE, i)``, so rotating the whole vector by k
    rotates every atom's index by k.  Rotation commutes with bundling (it is a
    bit permutation, and majority is per-bit), so
        rotate(hv, k) = bundle_i( perm(NUM,k) ^ atom(i+k) )
    and binding away the ``perm(NUM,k) ^ NUM`` offset leaves exactly the
    encoding of the shifted value.  Two XORs and two rotations, no similarity
    probe, no threshold, no decode.
    Positive ``k`` shifts left (multiply), negative shifts right (divide).
    Exact for non-negative values; for negative values the shift is logical,
    so the sign bit is not extended.
    """
    if k == 0:
        return v
    return bind(permute(v, k, d), permute(_NUM, k, d) ^ _NUM, d)


def hv_to_int(v: int, d: int = DEFAULT_DIM, threshold: float = CODEC_THRESHOLD) -> int:
    """Decode an integer hypervector by per-bit cleanup (two's complement)."""
    _check_dim(d)
    m = 0
    for i, bit in enumerate(hv_to_bits(v, d, threshold)):
        if bit:
            m |= 1 << i
    if m & (1 << (MAX_INT_BITS - 1)):
        m -= 1 << MAX_INT_BITS
    return m


# --------------------------------------------------------------------------
# diagnostics
# --------------------------------------------------------------------------
def capacity_bits(d: int = DEFAULT_DIM) -> float:
    """Information content of one vector, in bits (log2 of sign patterns)."""
    return float(d)


def orthogonal_capacity(d: int = DEFAULT_DIM, noise: float = 0.35) -> float:
    """Rough count of distinguishable near-orthogonal items (~ d / (2 log d))."""
    return d / (2.0 * math.log2(d))

	"""Binary hypervector algebra for HDCSTORAGE.

	Everything in this machine is a bit-packed hypervector: a Python ``int``
	interpreted as ``d`` bits, bit 0 being the least significant. Representation
	choices, and why:

	* No numpy. Dense HDC is normally an array of +/-1 floats or of packed
	uint64 words. A Python ``int`` of 10 000 bits is one object whose bitwise
	ops run in C over whole machine words, so ``bind`` is a single ``^`` and
	``popcount`` is ``int.bit_count()``. Memory per vector is d/8 bytes plus
	object overhead, no dependency, and no per-element Python loop.
	* Binary spatter codes (BSC). bind = XOR (self-inverse, so unbind ==
	bind), bundle = per-bit majority, permute = rotate within the d-bit mask.

	Algebraic facts this module relies on, used everywhere downstream:

	bind(a, b) ^ b == a (self-inverse)
	sim(bind(a, x), bind(b, x)) ~= sim(a, b) (binding preserves similarity)
	sim(permute(a, k), permute(b, k)) == sim(a, b)
	sim(bundle(S), x) ~ sqrt(1/\|S\|) for x in S -> cleanup recovers members
	E[sim(a, b)] == 0 for independent random a, b (sd ~ 1/sqrt(d))

	The last line is the reason d is large: it sets the noise floor that cleanup
	memory and the instruction decoder have to beat.
	"""

	from __future__ import annotations

	import hashlib
	import math
	from typing import Iterable, Sequence

	__all__ = [
	"DEFAULT_DIM",
	"mask",
	"popcount",
	"hamming",
	"random_hv",
	"hvc",
	"bind",
	"unbind",
	"bundle",
	"permute",
	"permute_inv",
	"sim",
	"sim_matrix",
	"int_to_hv",
	"hv_to_int",
	"hv_bits_of_int",
	"hv_from_bits",
	"hv_to_bits",
	"bit_probe",
	"shift",
	"CODEC_THRESHOLD",
	"MAX_INT_BITS",
	"density",
	"bits",
	"bitplanes",
	"role",
	"ROLES",
	"clear_cache",
	]

	#: Default dimensionality. 10 000 bits is the classic Kanerva/VSA size: the
	#: noise floor 1/sqrt(d) ~ 0.01 is far below the ~0.4 signal of a bundle
	#: member, so 4-6 field records decode reliably while 1 250 bytes per vector
	#: still fits a program image in a few hundred kilobytes.
	DEFAULT_DIM = 10_000


	# --------------------------------------------------------------------------
	# primitive bit operations
	# --------------------------------------------------------------------------
	def mask(d: int = DEFAULT_DIM) -> int:
	"""The all-ones mask covering ``d`` bits."""
	return (1 << d) - 1


	def popcount(x: int) -> int:
	"""Number of set bits."""
	return x.bit_count()


	def hamming(a: int, b: int) -> int:
	"""Hamming distance between two hypervectors."""
	return (a ^ b).bit_count()


	def density(v: int, d: int = DEFAULT_DIM) -> float:
	"""Fraction of set bits (should hover near 0.5 for random vectors)."""
	return popcount(v & mask(d)) / d


	def bits(v: int, d: int = DEFAULT_DIM) -> str:
	"""Bit string, most-significant bit first (the usual left-to-right view)."""
	return format(v & mask(d), "0%db" % d)


	def bitplanes(v: int, d: int = DEFAULT_DIM, width: int = 64) -> list[str]:
	"""Split a vector into fixed-width bit planes, WSB first."""
	s = bits(v, d)
	return [s[i : i + width] for i in range(0, len(s), width)]


	# --------------------------------------------------------------------------
	# deterministic symbol -> hypervector
	# --------------------------------------------------------------------------
	_CACHE: dict[tuple[str, int], int] = {}


	def clear_cache() -> None:
	_CACHE.clear()


	def hvc(name: str, d: int = DEFAULT_DIM) -> int:
	"""Deterministic hypervector for a symbol name.

	The same name always maps to the same vector, in-process and across runs,
	on any machine. That is what makes a stored program image portable: the
	symbolic layer (opcodes, register names, literals, tool names) is
	regenerated from names rather than serialised, and only the composed
	instruction vectors live in the storage file.

	Uses BLAKE2b expanded over a 4-byte block counter, then masked to d bits.
	"""
	key = (name, d)
	cached = _CACHE.get(key)
	if cached is not None:
	return cached
	out = 0
	block = 0
	h = hashlib.blake2b(name.encode("utf-8"), digest_size=64)
	seed = h.digest()
	while out.bit_length() < d:
	chunk = hashlib.blake2b(
	seed + block.to_bytes(4, "little"), digest_size=64
	).digest()
	out = (out << 512) \| int.from_bytes(chunk, "big")
	block += 1
	out &= mask(d)
	_CACHE[key] = out
	return out


	def random_hv(d: int = DEFAULT_DIM, rng=None) -> int:
	"""Random balanced hypervector (about d/2 set bits)."""
	if rng is None:
	import random

	rng = random
	return rng.getrandbits(d) & mask(d)


	# Roles: named slots used to build records. BSC's canonical record is
	# record = bundle([bind(role_i, value_i) for i in fields])
	# and a field is read back with bind(record, role_i) -> noisy value_i.
	ROLES: dict[str, str] = {
	"op": "role/operation",
	"ra": "role/dest-register",
	"rb": "role/source-register-b",
	"rc": "role/source-register-c",
	"imm": "role/immediate",
	"tgt": "role/target-pc",
	"addr": "role/address",
	"val": "role/value",
	"name": "role/name",
	"cap": "role/capability",
	"doc": "role/documentation",
	"arity": "role/arity",
	"tool": "role/tool",
	"arg": "role/argument",
	"tag": "role/tag",
	"kind": "role/kind",
	}


	def role(name: str, d: int = DEFAULT_DIM) -> int:
	"""Hypervector for a role slot (``"op"``, ``"ra"``, ...)."""
	return hvc(ROLES.get(name, name), d)


	# --------------------------------------------------------------------------
	# the algebra
	# --------------------------------------------------------------------------
	def bind(a: int, b: int, d: int \| None = None) -> int:
	"""Binding = XOR. Involutive: ``bind(bind(a, b), b) == a``."""
	v = a ^ b
	return v & mask(d) if d is not None else v


	def unbind(record: int, key: int, d: int \| None = None) -> int:
	"""Unbinding is binding (XOR is self-inverse); named for readability."""
	return bind(record, key, d)


	def permute(v: int, k: int = 1, d: int = DEFAULT_DIM) -> int:
	"""Cyclic bit rotation left by ``k`` (a rotation, so no bits are lost).

	Permutation is how this machine encodes order: position p of a sequence
	is ``permute(item, p)``, which keeps items near-orthogonal while making
	"same item, different position" a different address.
	"""
	m = mask(d)
	v &= m
	k %= d
	if k == 0:
	return v
	return ((v << k) \| (v >> (d - k))) & m


	def permute_inv(v: int, k: int = 1, d: int = DEFAULT_DIM) -> int:
	"""Inverse rotation (rotate right by ``k``)."""
	return permute(v, -k, d)


	def _add_bitplane(plates: list[int], v: int) -> None:
	"""Ripple-carry add of one bit-plane into a binary counter."""
	i = 0
	carry = v
	while carry:
	if i == len(plates):
	plates.append(carry)
	return
	nxt = plates[i] & carry
	plates[i] ^= carry
	carry = nxt
	i += 1


	def _plane_ge(plates: Sequence[int], threshold: int, d: int) -> int:
	"""Bit-sliced ``count >= threshold`` over the counter planes.

	Walks planes from most to least significant holding one predicate, ``eq``
	("equal to the threshold so far"), and one accumulator, ``gt`` ("already
	greater, therefore certainly >= threshold"). Lanes that fall below the
	threshold at some position are dropped from ``eq`` and die there, which is
	exactly a ripple comparator built from AND/NOT — the same gate logic a
	hardware majority element uses, widened to d lanes at once.
	"""
	m = mask(d)
	nbits = max(len(plates), threshold.bit_length()) or 1
	eq = m
	gt = 0
	for i in range(nbits - 1, -1, -1):
	p = plates[i] if i < len(plates) else 0
	if (threshold >> i) & 1:
	eq &= p # count bit 0 where threshold bit is 1 -> too small
	else:
	gt \|= eq & p # count bit 1 where threshold bit is 0 -> greater
	eq &= ~p & m
	if eq == 0:
	break
	return (gt \| eq) & m


	def bundle(vecs: Iterable[int], d: int = DEFAULT_DIM) -> int:
	"""Majority bundling: per-bit vote, ties resolve to 0.

	Implemented bit-sliced: every vector is added into a d-lane binary
	counter (one Python int per bit position of the count), then a single
	vectorised comparator thresholds it at ``floor(n/2)+1``. Cost is
	O(n * log n) big-int operations rather than O(n * d) element visits,
	which is what keeps a 10 000-bit bundle at tens of microseconds.
	"""
	items = list(vecs)
	if not items:
	return 0
	if len(items) == 1:
	return items[0] & mask(d)
	plates: list[int] = []
	for v in items:
	_add_bitplane(plates, v & mask(d))
	return _plane_ge(plates, len(items) // 2 + 1, d)


	def sim(a: int, b: int, d: int = DEFAULT_DIM) -> float:
	"""Cosine-style similarity in [-1, 1]: agreement of bits, rescaled.

	``sim = (d - 2*hamming) / d``; +1 identical, 0 orthogonal, -1 complement.
	"""
	if d <= 0:
	raise ValueError("d must be positive")
	return (d - 2 * (a ^ b).bit_count()) / d


	def sim_matrix(vecs: Sequence[int], d: int = DEFAULT_DIM) -> list[list[float]]:
	"""All-pairs similarity matrix."""
	return [[sim(a, b, d) for b in vecs] for a in vecs]


	# --------------------------------------------------------------------------
	# integers stored as hypervectors
	# --------------------------------------------------------------------------
	# A scalar is represented by superposition of bit-position atoms:
	# int_to_hv(n) = bundle([bind(NUM, permute(BITBASE, i)) for i where n has bit i])
	# so an integer occupies a vector like every other value and can be recovered
	# by cleanup (one similarity probe per bit position). This is the pixel that
	# makes "all state is hyperdimensional" true rather than decorative.
	#
	# The layout is two's complement, 32 bits: bit MAX_INT_BITS-1 is the sign,
	# and a negative value is dense where a sign-magnitude encoding would be
	# sparse. That choice is what lets arithmetic happen as a ripple-carry
	# circuit over the bit atoms (see hdc/adder.py): two's complement makes
	# addition a pure function of the bits, with no sign case analysis anywhere.
	_NUM = hvc("codec/integer")
	_BITBASE = hvc("codec/bit-position")

	#: Width of the integer payload, in bits, two's complement.
	MAX_INT_BITS = 32

	#: Similarity above which a bit atom counts as present in a bundle.
	#:
	#: Measured on this implementation (40 random atom subsets per size, both
	#: dimensions): a member of a k-atom bundle recovers at 1/sqrt(k) — 0.35 at
	#: k=4 down to 0.136 at k=32 — while a non-member stays below 0.044 at
	#: d=10 000 and below 0.093 at d=2 000. 0.10 is the value that separates all
	#: of those cases and round-trips 415/415 sampled 32-bit values at both
	#: dimensions; d=2 000 is therefore the supported floor for the codec.
	CODEC_THRESHOLD = 0.10

	#: Smallest dimension at which the integer codec round-trips reliably.
	#:
	#: Measured over all 256 byte values plus 200 random bytes: 0 errors at
	#: d=1500, 2000 and 3000; 60 errors at d=1000 and 401 at d=500, with a
	#: worst delta of 512. Below this floor the bit atoms crosstalk enough that a
	#: decode silently returns a neighbouring value, which would corrupt every
	#: threshold and shift downstream, so the codec refuses instead.
	MIN_CODEC_DIM = 1500


	def _check_dim(d: int) -> None:
	if d < MIN_CODEC_DIM:
	raise ValueError(
	"integer codec needs d >= %d (got %d): bit atoms crosstalk below that "
	"and values decode wrong" % (MIN_CODEC_DIM, d)
	)


	def _bit_probe(i: int, d: int) -> int:
	return bind(_NUM, permute(_BITBASE, i, d), d)


	def bit_probe(i: int, d: int = DEFAULT_DIM) -> int:
	"""The atom for bit position ``i``, for probing a coded value directly.

	Exposed because other layers (the shader) need single-bit tests — sign,
	ordering — without decoding the whole integer.
	"""
	return _bit_probe(i, d)


	def int_to_hv(n: int, d: int = DEFAULT_DIM) -> int:
	"""Encode a signed 32-bit integer as a hypervector (two's complement).

	Zero encodes to the all-zero vector (the empty bundle), so a cleared
	register is literally a vector with no atoms in it.

	This codec is symbolic, not similarity-preserving: two integers that
	share set bits share bit-position atoms, so ``sim(int_to_hv(5),
	int_to_hv(37))`` is high even though 5 and 37 have nothing to do with each
	other. That is deliberate — decode needs the atoms to be shared and
	probeable, exactly like a bit field. Do not read a distance between two
	encoded integers as a semantic relationship, and do not expect binding two
	of them to decorrelate the way binding two random vectors does.
	"""
	_check_dim(d)
	lo, hi = -(1 << (MAX_INT_BITS - 1)), (1 << (MAX_INT_BITS - 1)) - 1
	if not lo <= n <= hi:
	raise ValueError("integer outside the %d-bit codec range: %r" % (MAX_INT_BITS, n))
	return hv_from_bits(hv_bits_of_int(n), d)


	def hv_bits_of_int(n: int) -> list[int]:
	"""The two's complement bit pattern of an integer, least significant first."""
	pattern = n & ((1 << MAX_INT_BITS) - 1)
	return [(pattern >> i) & 1 for i in range(MAX_INT_BITS)]


	def hv_from_bits(bits: Sequence[int], d: int = DEFAULT_DIM) -> int:
	"""Assemble a hypervector from bit values, purely by bundling atoms.

	No integer arithmetic is involved: each set position contributes its atom
	to a majority bundle. Two's complement sign extension is the caller's
	concern, exactly as it is in hardware.
	"""
	parts = [_bit_probe(i, d) for i, bit in enumerate(bits) if bit]
	return bundle(parts, d) if parts else 0


	def hv_to_bits(v: int, d: int = DEFAULT_DIM, threshold: float = CODEC_THRESHOLD) -> list[int]:
	"""Read the bit pattern back with one similarity probe per position."""
	return [1 if sim(v, _bit_probe(i, d), d) >= threshold else 0 for i in range(MAX_INT_BITS)]


	def shift(v: int, k: int, d: int = DEFAULT_DIM) -> int:
	"""Multiply or divide a coded integer by 2**k, without decoding it.

	This works only because the bit atoms are a permutation orbit:
	``atom(i) = NUM ^ perm(BITBASE, i)``, so rotating the whole vector by k
	rotates every atom's index by k. Rotation commutes with bundling (it is a
	bit permutation, and majority is per-bit), so

	rotate(hv, k) = bundle_i( perm(NUM,k) ^ atom(i+k) )

	and binding away the ``perm(NUM,k) ^ NUM`` offset leaves exactly the
	encoding of the shifted value. Two XORs and two rotations, no similarity
	probe, no threshold, no decode.

	Positive ``k`` shifts left (multiply), negative shifts right (divide).
	Exact for non-negative values; for negative values the shift is logical,
	so the sign bit is not extended.
	"""
	if k == 0:
	return v
	return bind(permute(v, k, d), permute(_NUM, k, d) ^ _NUM, d)


	def hv_to_int(v: int, d: int = DEFAULT_DIM, threshold: float = CODEC_THRESHOLD) -> int:
	"""Decode an integer hypervector by per-bit cleanup (two's complement)."""
	_check_dim(d)
	m = 0
	for i, bit in enumerate(hv_to_bits(v, d, threshold)):
	if bit:
	m \|= 1 << i
	if m & (1 << (MAX_INT_BITS - 1)):
	m -= 1 << MAX_INT_BITS
	return m


	# --------------------------------------------------------------------------
	# diagnostics
	# --------------------------------------------------------------------------
	def capacity_bits(d: int = DEFAULT_DIM) -> float:
	"""Information content of one vector, in bits (log2 of sign patterns)."""
	return float(d)


	def orthogonal_capacity(d: int = DEFAULT_DIM, noise: float = 0.35) -> float:
	"""Rough count of distinguishable near-orthogonal items (~ d / (2 log d))."""
	return d / (2.0 * math.log2(d))