hn.today

Reverse-Engineering Kevin J. Lang's Lost OCaml Code in Apache DataSketches

tisonkun.io4 points0 comments
Screenshot of Reverse-Engineering Kevin J. Lang's Lost OCaml Code in Apache DataSketches

Apache DataSketches’ CPC sketch is a compact, mergeable alternative to HyperLogLog for estimating distinct counts. Its design retains a matrix of observed hash “coupons” and combines streaming and mergeable estimators; adaptive compression helps it use roughly 30-40% less space than HLL at comparable accuracy. While porting CPC to Rust for ScopeDB, the author found that its implementation depended on hardcoded tables whose original OCaml generators had disappeared with researcher Kevin J. Lang, who died in 2019. The tables include Huffman codes, column permutations, polynomial coefficients for the ICON estimator, and confidence-interval quantiles. Since the published paper did not document the later compression method, reproducing the tables required reverse-engineering from code and numerical clues.

The author used the checked-in values and detailed comments as executable tests, with multiple AI models proposing and challenging explanations. The strongest confirmed result is a reconstruction of all 5,697 Huffman codewords: probabilities for bytes in an eight-column sliding window feed the length-limited package-merge algorithm, after which canonical codes are bit-reversed for CPC’s least-significant-bit-first stream. The 12-bit decoder limit helps constrain the reconstruction. Further model-led scrutiny eliminated a plausible but incorrect explanation, exposed floating-point cancellation and limits on identifying polynomial fits, and caught tautological tests and overstatements. The surviving derivations and checks were added to the Rust project, preserving not just the tables but a way to verify how they were generated - and showing why AI-assisted mathematical reverse engineering depends on adversarial, executable validation.

Read on tisonkun.io0 comments on Hacker News

Summary generated by AI from the linked article. hn.today is not affiliated with Hacker News or Y Combinator.

More in Programming

The daily digest

Today's best Hacker News stories, summarized and screenshotted, one email a day.