1// NIP-45 HyperLogLog sketch of the pubkeys behind a count.2import { sha256 } from "@noble/hashes/sha2.js";3import { bytesToHex, hexToBytes } from "./negentropy.ts";4import type { Filter } from "./filter.ts";56// hllOffset derives the register offset from a filter, or -1 if ineligible7// (exactly one tag attribute with at least one value).8export function hllOffset(f: Filter): number {9 const names = Object.keys(f.tags);10 if (names.length !== 1) return -1;11 let v = f.tags[names[0]][0];12 if (v === undefined) return -1;13 const parts = v.split(":");14 if (parts.length === 3 && parts[1].length === 64) v = parts[1];15 if (!/^[0-9a-f]{64}$/.test(v)) v = bytesToHex(sha256(new TextEncoder().encode(v)));16 return parseInt(v[32], 16) + 8;17}1819export class HLL {20 regs = new Uint8Array(256);21 constructor(private offset: number) {}2223 add(pubkeyHex: string) {24 if (pubkeyHex.length !== 64) return;25 const pk = hexToBytes(pubkeyHex);26 const ri = pk[this.offset];27 let zeros = 0;28 for (let i = this.offset + 1; i < 32; i++) {29 const b = pk[i];30 if (b === 0) {31 zeros += 8;32 continue;33 }34 zeros += Math.clz32(b) - 24;35 break;36 }37 const v = zeros + 1;38 if (v > this.regs[ri]) this.regs[ri] = v;39 }4041 hex() {42 return bytesToHex(this.regs);43 }44}