Hashes

Article by:
Date Published:
Last Modified:
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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* * * * 
 * 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;
}

Authors

Geoffrey Hunter

Dude making stuff.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License .

Related Content

Tags

comments powered by Disqus