Foundry/hdc

HDC Module (fv_)

Hyperdimensional Computing operations for Foundry.

---

Overview

General-purpose Hyperdimensional Computing (HDC) library that provides binary hypervector manipulation, random projection encoding, and fast similarity search via Hamming distance.

HDC encodes information as high-dimensional binary vectors (typically 4096 bits) and performs computation using simple bitwise operations. This provides extremely fast similarity search with compact storage — a 4096-dim binary vector requires only 512 bytes.

API Reference

Types

/* Binary hypervector — bit-packed storage */
typedef struct {
    uint64_t *bits;     /* ceil(dim/64) uint64 words */
    int dim;
} fv_vector;

/* Opaque projection matrix for float→binary encoding */
typedef struct fv_projector fv_projector;

/* Configuration */
typedef struct {
    int dim;            /* Hypervector dimension (default: 4096) */
    uint64_t seed;      /* RNG seed for deterministic projection */
} fv_config;

Vector Lifecycle

Function	Description
fv_alloc(dim)	Allocate zero-initialized vector
fv_random(dim, seed)	Deterministic random vector (~50% bits set)
fv_zeros(dim)	All-zero vector
fv_clone(v)	Deep copy
fv_free(v)	Free (NULL-safe)

Core Operations

Function	HDC Name	Description
fv_xor(a, b)	Bind	Associates two concepts. Self-inverse: XOR(XOR(a,b), b) = a
fv_permute(v, shift)	Permute	Cyclic bit shift for position encoding
fv_bundle(vecs, n)	Bundle	Majority vote — creates superposition of concepts
fv_bundle_weighted(vecs, w, n)	Weighted Bundle	Weighted majority vote
fv_hamming(a, b)	Distance	Hamming distance (count differing bits)
fv_similarity(a, b)	Similarity	1.0 - hamming/dim, range [0, 1]

Random Projection

/* Create projector: maps input_dim floats → hdc_dim binary vector */
fv_projector* fv_projector_new(int input_dim, int hdc_dim, uint64_t seed);
void fv_projector_free(fv_projector *proj);

/* Project: sign(R @ x) where R is Gaussian random matrix */
fv_vector* fv_project(const fv_projector *proj, const tm_tensor *embedding);

Tensor Conversion

tm_tensor* fv_to_tensor(const fv_vector *v);     /* → [dim] float, 0.0/1.0 */
fv_vector* fv_from_tensor(const tm_tensor *t);   /* → binary, threshold > 0 */

Serialization

int fv_save(const fv_vector *v, const char *path);   /* 4 bytes dim + bit data */
fv_vector* fv_load(const char *path);

Batch Search

/* Find top-k most similar vectors. Returns count found. */
int fv_search(fv_vector **corpus, int corpus_size,
              const fv_vector *query, int top_k,
              int *indices_out, float *scores_out);

Usage Example

#include "hdc/hdc.h"
#include "tensor/tensor.h"

/* Encode float embedding to binary hypervector */
fv_projector *proj = fv_projector_new(768, 4096, 42);

int64_t shape[] = {768};
tm_tensor *emb = tm_randn(shape, 1, TM_F32);
fv_vector *hv = fv_project(proj, emb);

/* Search corpus */
int indices[5];
float scores[5];
fv_search(corpus, 1000, hv, 5, indices, scores);

/* Key-value binding: associate concept with position */
fv_vector *key_hv = fv_random(4096, key_seed);
fv_vector *bound = fv_xor(key_hv, hv);    /* bind key to value */
fv_vector *recovered = fv_xor(bound, key_hv); /* unbind to get value back */

fv_free(hv);
fv_free(bound);
fv_free(recovered);
fv_free(key_hv);
fv_projector_free(proj);
tm_free(emb);

Performance

• Hamming distance: XOR + popcountll over 64 uint64 words (4096-bit). ~nanoseconds per comparison.
• Search (brute force): Linear scan with partial sort. ~1M comparisons/second for 4096-bit vectors.
• Memory: 512 bytes per 4096-bit vector. 1M vectors = 512 MB.
• Projection: One matrix-vector multiply per encoding. Dominated by input_dim * hdc_dim multiply-adds.

Build

cd foundry
make hdc           # Build module
make test-hdc      # Run 18 tests

Dependencies

• tensor/ — For tm_tensor type used in projection and conversion