title: Why does this hash calculating bit hack work?
body: <p>For practice I've implemented the <a href="https://qoiformat.org/qoi-specification.pdf" rel="nofollow noreferrer">qoi specification</a> in rust. In it there is a small hash function to store recently used pixels:</p>
  <blockquote>
  <p>index_position = (r * 3 + g * 5 + b * 7 + a * 11) % 64</p>
  </blockquote>
  <p>where r, g, b, and a are the red, green, blue and alpha channels respectively.</p>
  <p>I assume this works as a hash because it creates a unique prime factorization for the numbers with the mod to limit the number of bytes. Anyways I implemented it naively in my code.</p>
  <p>While looking at other implementations I came across this bit hack to optimize the hash calculation:</p>
  <pre class="lang-rust prettyprint-override"><code>fn hash(rgba:[u8:4]) -&gt; u8 {
          let v = u32::from_ne_bytes(rgba);
          let s = (((v as u64) &lt;&lt; 32) | (v as u64)) &amp; 0xFF00FF0000FF00FF;
  
          s.wrapping_mul(0x030007000005000Bu64.to_le()).swap_bytes() as u8 &amp; 63
      }
  </code></pre>
  <p>I think I understand most of what's going on but I'm confused about the magic number (the multiplicand). To my understanding it should be flipped. As a step by step example:</p>
  <ol>
  <li><code>let rgba = [0x12, 0x34, 0x56, 0x78]</code>.</li>
  <li>On my machine (little endian) this gives <code>v</code> the value <code>0x78563412</code>.</li>
  <li>The bit shifting spreads the values, giving <code>s = 0x7800340000560012</code>.</li>
  <li>Now here's where I get confused. The magic number has the values that should be multiplied aligned in a 64 bit field (3, 5, 7, 11), spaced the same way that the original values are. However they seem to be in reverse order from the values:</li>
  </ol>
  <pre><code>0x7800340000560012
  0x030007000005000B
  </code></pre>
  <p>When multiplying it would seem that the highest value, the alpha channel (0x78), is being multiplied by 3, while the lowest value, the red channel (0x12), is being multiplied by 11. I'm also not entirely sure why this multiplication works anyway, after multiplying the values by various powers of 2.</p>
  <p>I understand that the bytes are then swapped to big endian and trimmed, but that's not until after the multiplication step which loses me.</p>
  <p>I know that the code produces the correct hash, but I don't understand why that's the case. Can anyone explain to me what I'm missing?</p>