HASHES

Hashes

Date Published:
Last Modified:

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;
}

Related Content:

Tags:

comments powered by Disqus