Show HN: Discohash – a fast and quality hash in 120 lines
Disochash is a simple prime-multiplication ARX (addition rotation XOR) hash that&#x27;s high-quality and fast. It&#x27;s only 120 lines of code.<p>There&#x27;s lots of great hash functions out there: some are super fast, like xxhash and highly optimized, others are also super fast like umash and based on interesting math ideas from finite fields^1, while maintaining high quality (according to SMHasher). Others are also fast and interesting (tabulation hash, that may sometimes be seemingly universal): one of the main originators of tabulation hash ideas is Mikkel Thorup^2.<p>Anyway, a couple of years ago I also tried my hand at building hashes and created a few that passed SMHasher (tifuhash ~ a floating point hash, beamsplitter - a seemingly-universal tabulation style hash, and this one discohash - a &quot;more traditional&quot; ARX-based design (addition rotation xor)^3 ).<p>0: <a href="https:&#x2F;&#x2F;github.com&#x2F;rurban&#x2F;smhasher&#x2F;blob&#x2F;master&#x2F;xxh3.h">https:&#x2F;&#x2F;github.com&#x2F;rurban&#x2F;smhasher&#x2F;blob&#x2F;master&#x2F;xxh3.h</a><p>1: <a href="https:&#x2F;&#x2F;pvk.ca&#x2F;Blog&#x2F;2022&#x2F;12&#x2F;29&#x2F;fixing-hashing-modulo-alpha-equivalence&#x2F;" rel="nofollow noreferrer">https:&#x2F;&#x2F;pvk.ca&#x2F;Blog&#x2F;2022&#x2F;12&#x2F;29&#x2F;fixing-hashing-modulo-alpha-e...</a><p>2: <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1505.01523" rel="nofollow noreferrer">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1505.01523</a><p>3: <a href="https:&#x2F;&#x2F;eprint.iacr.org&#x2F;2018&#x2F;898.pdf" rel="nofollow noreferrer">https:&#x2F;&#x2F;eprint.iacr.org&#x2F;2018&#x2F;898.pdf</a> <a href="https:&#x2F;&#x2F;crypto.polito.it&#x2F;content&#x2F;download&#x2F;480&#x2F;2850&#x2F;file&#x2F;document.pdf" rel="nofollow noreferrer">https:&#x2F;&#x2F;crypto.polito.it&#x2F;content&#x2F;download&#x2F;480&#x2F;2850&#x2F;file&#x2F;docu...</a><p>4: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;BLAKE_(hash_function)" rel="nofollow noreferrer">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;BLAKE_(hash_function)</a><p>Discohash (posted here) is the fastest one I made, it&#x27;s simple and doesn&#x27;t rely on any arch-specific optimizations or vector instructions (AVX etc ~ tho I suppose...they could be added? I&#x27;m definitely no expert in them, I barely get away with doing the C&#x2F;C++ implementations!)<p>The main mixing round function is:<p><pre><code>  mix(const int A) {
      const int B = A + 1;

      ds[A] *= P;
      ds[A] = rot(ds[A], 23);
      ds[A] *= Q;

      ds[B] ^= ds[A];

      ds[B] *= P;
      ds[B] = rot(ds[B], 23);
      ds[B] *= Q;
  }
</code></pre>
where P and Q are two randomly chosen 64-bit primes (P is actually the largest unsigned 64-bit prime!), and A is an index into the 256-bit internal state.<p>I love it because of its simplicity (and because I Created it :) ha), but I think it has some room to grow. An interesting design feature is the internal state is actually variable, it can be larger than 32-bytes.<p>Some future directions (for anyone who is interested and wants to extend it):<p>- add a sponge construction to create an infinite output stream &#x2F; keystream generator<p>- add AVX instructions (or other optimizations to squeeze more out of a serial implementation)<p>- figure out how to use a Merkle construction on discohash (like the Blake hashes^4 use to improve their not-that-impressive serial speed using parallelization), hard for discohash I think because state operations are essentially &quot;chained together&quot;<p>- see if it can be parameterized with other pairs of primes (perhaps into a &quot;universal&quot; family of functions). P &amp; Q in discohash have the interesting and quite rare property that P - Q = P ^ Q (their difference equals their XOR), I surmise that may required for other P and Q to work in discohash.<p>I just added a PR to Smhasher^5 to update the hash to a faster version and fix some implementation issues related to memory alignment that after much fuffing about with ChatGPT I was thankfully able to resolve! Relief!<p>I&#x27;m no math expert, nor an expert in optimization, nor cryptanalysis, I basically just developed these hashes intuitively, flying by the seat of my pants! But they worked, hoo rah! :)<p>5: <a href="https:&#x2F;&#x2F;github.com&#x2F;rurban&#x2F;smhasher&#x2F;pull&#x2F;268">https:&#x2F;&#x2F;github.com&#x2F;rurban&#x2F;smhasher&#x2F;pull&#x2F;268</a>