fasterthanlime / stringsearch

Collection of techniques for (binary) string searching

suffixsearch

A collection of SACAs (suffix array construction algorithms) and other methods of indexing and searching for substrings in all suffixes of a given input.

Crates

• divsufsort is Rust version of Yuta Mori's libdivsufsort, ported by hand
• cdivsfusort is Yuta Mori's original libdivsufsort, built with the cc crate
• divsuftest is a test executable that allows comparing against the above crates.
• dc3 is a naive work-in-progress implementation of DC3 (Differential Cover, v=3)

See the crates' README files for more information on their status, expected performance and licensing.

stringsearch's Issues

`divsufsort` useful for `bsdiff`. (Not an issue, just a note.)

Today I learned about the bsdiff and bspatch, by Colin Percival. His description is in his https://www.daemonology.net/papers/bsdiff.pdf.

He has an old page that summarizes how it's been useful for various OS distributions here and here's a man page.

There were some Rust ports some time ago. I picked up bsdiff-rs.

I found the bsdiff inventor/author had become an important contributor to FreeBSD and wondered how his bsdiff was used by FreeBSD now. Turns out around 2016, they swapped out an initial call to a hand written qsufsort with the Google developed divsufsort claiming it was much faster.

Found your port of the library to rust, dropped it into a local bsdiff-rs and can confirm it is much much faster. On 4MB rust binaries I tested, bsdiff times dropped from 1.1s to 0.3s. Same binary source difference algorithm, just a different way to create the suffix array that it uses. Amazing.

Thanks for the hand port and all that fuzz testing!