TsDB2/DB/core/xxhash32.go

package core

import "encoding/binary"

// XXH32 纯 Go 实现 (xxHash 32-bit, seed=0), 用于 HeaderPage 整页校验。
//
// 选 XXH32 而不是 CRC32 的理由: 一样的 4 字节开销, 但 xxHash 是为
// "小输入也高速"设计的现代非加密散列 —— 雪崩效应好得多 (单比特翻转
// 影响约半数输出位, CRC32 的单比特错误检测在其设计长度内可靠, 但对
// 多比特 burst/交换型损坏的混淆能力弱于 xxHash), 且 4 个累加器并行
// 条纹处理对 4KB 头页的速度优于逐字节表驱动的 CRC32。
//
// 算法参照 xxHash 规范 (xxhash.github.io), 与参考实现逐位一致:
//   - len >= 16: 四个累加器吃 16 字节条纹, round(acc,v) = rotl(acc+v*P2,13)*P1
//   - 尾部: 4 字节块与单字节轮流混入
//   - 收尾: 标准雪崩 (异或-乘-异或-乘-异或)
// 测试向量 (见 xxhash32_test.go): XXH32("")=0x02CC5D05, XXH32("a")=0x550D7456,
// XXH32("abc")=0x32D153FF。
//
// 引擎零依赖是卖点, 所以不引 github.com/cespare/xxhash —— 此实现约 60 行,
// 且输入长度固定 4096, 性能差异 irrelevant。

// 用 var 而非 const: 素数之和 (P1+P2) 超出 uint32 上限, 常量表达式会在编译期
// 直接报错; 变量则按规范要求的无符号回绕语义在运行期求值。
var (
	xxhPrime32_1 uint32 = 2654435761
	xxhPrime32_2 uint32 = 2246822519
	xxhPrime32_3 uint32 = 3266489917
	xxhPrime32_4 uint32 = 668265263
	xxhPrime32_5 uint32 = 374761393
)

// xxh32Round 条纹轮: 唯一的累加器更新原语。
func xxh32Round(acc, lane uint32) uint32 {
	acc += lane * xxhPrime32_2
	acc = bitsRotl32(acc, 13)
	acc *= xxhPrime32_1
	return acc
}

func bitsRotl32(x uint32, r uint) uint32 { return (x << r) | (x >> (32 - r)) }

// XXH32 计算 data 的 xxHash-32 (seed=0)。输入长度无要求 (空输入合法)。
func XXH32(data []byte) uint32 {
	n := len(data)
	p := 0
	var h uint32

	// 条纹阶段: 四个独立累加器消除串行依赖, 16 字节一步。
	if n >= 16 {
		v1 := xxhPrime32_1 + xxhPrime32_2
		v2 := xxhPrime32_2
		v3 := uint32(0)
		v4 := -xxhPrime32_1 // seed(0) - PRIME32_1, 无符号回绕即规范语义
		for p <= n-16 {
			v1 = xxh32Round(v1, binary.LittleEndian.Uint32(data[p:p+4]))
			v2 = xxh32Round(v2, binary.LittleEndian.Uint32(data[p+4:p+8]))
			v3 = xxh32Round(v3, binary.LittleEndian.Uint32(data[p+8:p+12]))
			v4 = xxh32Round(v4, binary.LittleEndian.Uint32(data[p+12:p+16]))
			p += 16
		}
		h = bitsRotl32(v1, 1) + bitsRotl32(v2, 7) + bitsRotl32(v3, 12) + bitsRotl32(v4, 18)
	} else {
		h = xxhPrime32_5
	}

	h += uint32(n)

	// 尾部: 先 4 字节块, 再单字节。
	for ; p+4 <= n; p += 4 {
		h += binary.LittleEndian.Uint32(data[p:p+4]) * xxhPrime32_3
		h = bitsRotl32(h, 17) * xxhPrime32_4
	}
	for ; p < n; p++ {
		h += uint32(data[p]) * xxhPrime32_5
		h = bitsRotl32(h, 11) * xxhPrime32_1
	}

	// 雪崩: 让所有输入位充分影响所有输出位。
	h ^= h >> 15
	h *= xxhPrime32_2
	h ^= h >> 13
	h *= xxhPrime32_3
	h ^= h >> 16
	return h
}