hash8-bitfastled

Hash function for 8 / 16 bit "graphics" on 8 bit processor

For an implementation of coherent noise (similar to Perlin noise), I'm looking for a hash function suitable for graphics.

I don't need it to be in any way cryptographic, and really, I don't even need it to be a super brilliant hash.

I just want to to combine two 16 bit numbers and output an 8 bit hash. As random as possible is good, but also, fast on a AVR processor (8 bit, as used by Arduino) is good.

Currently I'm using an implementation here:

const uint32_t hash(uint32_t a)
{
    a -= (a<<6);
    a ^= (a>>17);
    a -= (a<<9);
    a ^= (a<<4);
    a -= (a<<3);
    a ^= (a<<10);
    a ^= (a>>15);
    return a;
}

But given that I'm truncating all but 8 bits, and I don't need anything spectacular, can I get away with something using fewer instructions?

… I'm inspired in this search by the lib8tion library that's packaged with FastLED. It has specific functions to, for example, multiple two uint8_t numbers to give a uint16_t number in the fewest possible clock cycles.

Solution

  • Check out Pearson hashing:

    unsigned char hash(unsigned short a, unsigned short b) {
    static const unsigned char t[256] = {...};
    return t[t[t[t[a & 0xFF] ^ (b & 0xFF)] ^ (a >> 8)] ^ (b >> 8)];
}