Hashes

Geoffrey Hunter

mbedded.ninja Author

warning

This page is in notes format, and may not be of the same quality as other pages on this site.

Overview

Simple Hash Algorithms For Microcontrollers

The following code example comes from the GitHub repo canzero-driver-firmware.

/* * * * 
 * The pseudo hash below is loosely based on MD5.
 * It aims the create a unique 8 byte ID from a 12 byte unique ID
 * with low probability of collision.
 * The previous approach of selecting certain bits for the 12 byte
 * ID to create an 8 byte ID had an 2-3% collissions, which is not
 * very big but could still become problematic.
 */

uint16_t K[24] = {
    0xa478, 0x0faf, 0x98d8, 0x1122,
    0x2562, 0x105d, 0xcde6, 0xe905,
    0x3942, 0xea44, 0x7ec6, 0xd039,
    0x2244, 0x59c3, 0x7e4f, 0x7e82,
    0xb756, 0xc62a, 0xf7af, 0x7193,
    0xb340, 0x1453, 0x07d6, 0xa3f8
};

int s[16] = { 7, 12,  1, 6,
              5,  9, 14, 2,
              4, 11,  0, 3,
              8, 10, 15, 13 };

static uint16_t lrot(uint16_t v, int r)
{
    return (v<<r) | (v>>(16-r));
}

static void pseudo_hash(uint16_t *src, uint16_t *dst)
{
    uint16_t A, B, C, D;

    A = 0x2301;
    B = 0xab89;
    C = 0xdcfe;
    D = 0x5476;


    for (int i=0; i<16; i++)
    {
        uint16_t R, p;

        if (i<6) {
            R = (B & C) | ((~B) & D);
            p = i;
        }

        else if (i<8) {
            R = (B & D) | (C & (~D));
            p = (5*i+1)%6;
        }

        else if (i<12) {
            R = B ^ C ^ D;
            p = (3*i+5)%6;
        }

        else {
            R = C ^ (B | (~D));
            p = (2*i)%6;
        }

        R = R + A + K[i] + src[p];
        A = D;
        D = C;
        C = B;
        B = B + lrot(R, s[i]);
    }

    dst[0] = A;
    dst[1] = B;
    dst[2] = C;
    dst[3] = D;
}