Algorithms_in_C 1.0.0
Set of algorithms implemented in C.
Loading...
Searching...
No Matches
Hash algorithms

Files

file  hash_adler32.c
 32-bit Adler hash algorithm
 
file  hash_blake2b.c
 Blake2b cryptographic hash function
 
file  hash_crc32.c
 32-bit CRC hash algorithm
 
file  hash_djb2.c
 DJB2 hash algorithm
 
file  hash_sdbm.c
 SDBM hash algorithm
 
file  hash_xor8.c
 8-bit XOR hash algorithm for ASCII characters
 

Macros

#define bb   128
 for asserts
 
#define KK_MAX   64
 max key length for BLAKE2b
 
#define NN_MAX   64
 max length of BLAKE2b digest in bytes
 
#define CEIL(a, b)   (((a) / (b)) + ((a) % (b) != 0))
 ceiling division macro without floats
 
#define MIN(a, b)   ((a) < (b) ? (a) : (b))
 returns minimum value
 
#define MAX(a, b)   ((a) > (b) ? (a) : (b))
 returns maximum value
 
#define ROTR64(n, offset)   (((n) >> (offset)) ^ ((n) << (64 - (offset))))
 macro to rotate 64-bit ints to the right Ripped from RFC 7693
 
#define U128_ZERO
 zero-value initializer for u128 type
 

Typedefs

typedef uint64_t u128[2]
 128-bit number represented as two uint64's
 
typedef uint64_t block_t[bb/sizeof(uint64_t)]
 Padded input block containing bb bytes.
 

Functions

uint32_t adler32 (const char *s)
 32-bit Adler algorithm implementation
 
void test_adler32 ()
 Test function for adler32.
 
static void u128_fill (u128 dest, size_t n)
 put value of n into dest
 
static void u128_increment (u128 dest, uint64_t n)
 increment an 128-bit number by a given amount
 
static void G (block_t v, uint8_t a, uint8_t b, uint8_t c, uint8_t d, uint64_t x, uint64_t y)
 blake2b mixing function G
 
static void F (uint64_t h[8], block_t m, u128 t, int f)
 compression function F
 
static int BLAKE2B (uint8_t *dest, block_t *d, size_t dd, u128 ll, uint8_t kk, uint8_t nn)
 driver function to perform the hashing as described in specification
 
uint8_t * blake2b (const uint8_t *message, size_t len, const uint8_t *key, uint8_t kk, uint8_t nn)
 blake2b hash function
 
uint32_t crc32 (const char *s)
 32-bit CRC algorithm implementation
 
void test_crc32 ()
 Test function for crc32.
 
uint64_t djb2 (const char *s)
 DJB2 algorithm implementation.
 
void test_djb2 (void)
 Test function for djb2.
 
uint64_t sdbm (const char *s)
 SDBM algorithm implementation.
 
void test_sdbm ()
 Test function for sdbm.
 
uint8_t xor8 (const char *s)
 8-bit XOR algorithm implementation
 
void test_xor8 ()
 Test function for xor8.
 

Variables

static const uint8_t R1 = 32
 Rotation constant 1 for mixing function G.
 
static const uint8_t R2 = 24
 Rotation constant 2 for mixing function G.
 
static const uint8_t R3 = 16
 Rotation constant 3 for mixing function G.
 
static const uint8_t R4 = 63
 Rotation constant 4 for mixing function G.
 
static const uint64_t blake2b_iv [8]
 BLAKE2b Initialization vector blake2b_iv[i] = floor(2**64 * frac(sqrt(prime(i+1)))), where prime(i) is the i:th prime number.
 
static const uint8_t blake2b_sigma [12][16]
 word schedule permutations for each round of the algorithm
 

Detailed Description

Macro Definition Documentation

◆ bb

#define bb   128

for asserts

for fixed-width integer types e.g. uint64_t and uint8_t for IO for malloc, calloc, and free. As well as size_t

the size of a data block in bytes

◆ CEIL

#define CEIL (   a,
 
)    (((a) / (b)) + ((a) % (b) != 0))

ceiling division macro without floats

Parameters
adividend
bdivisor

◆ U128_ZERO

#define U128_ZERO
Value:
{ \
0, 0 \
}

zero-value initializer for u128 type

73 { \
74 0, 0 \
75 }

Function Documentation

◆ adler32()

uint32_t adler32 ( const char *  s)

32-bit Adler algorithm implementation

Parameters
sNULL terminated ASCII string to hash
Returns
32-bit hash result
19{
20 uint32_t a = 1;
21 uint32_t b = 0;
22 const uint32_t MODADLER = 65521;
23
24 size_t i = 0;
25 while (s[i] != '\0')
26 {
27 a = (a + s[i]) % MODADLER;
28 b = (b + a) % MODADLER;
29 i++;
30 }
31 return (b << 16) | a;
32}

◆ blake2b()

uint8_t * blake2b ( const uint8_t *  message,
size_t  len,
const uint8_t *  key,
uint8_t  kk,
uint8_t  nn 
)

blake2b hash function

This is the front-end function that sets up the argument for BLAKE2B().

Parameters
messagethe message to be hashed
lenlength of message (0 <= len < 2**128) (depends on sizeof(size_t) for this implementation)
keyoptional secret key
kklength of optional secret key (0 <= kk <= 64)
nnlength of output digest (1 <= nn < 64)
Returns
NULL if heap memory couldn't be allocated. Otherwise heap allocated memory nn bytes large
356{
357 uint8_t *dest = NULL;
358 uint64_t long_hold;
359 size_t dd, has_key, i;
360 size_t block_index, word_in_block;
361 u128 ll;
362 block_t *blocks;
363
364 if (message == NULL)
365 {
366 len = 0;
367 }
368 if (key == NULL)
369 {
370 kk = 0;
371 }
372
373 kk = MIN(kk, KK_MAX);
374 nn = MIN(nn, NN_MAX);
375
376 dd = MAX(CEIL(kk, bb) + CEIL(len, bb), 1);
377
378 blocks = calloc(dd, sizeof(block_t));
379 if (blocks == NULL)
380 {
381 return NULL;
382 }
383
384 dest = malloc(nn * sizeof(uint8_t));
385 if (dest == NULL)
386 {
387 free(blocks);
388 return NULL;
389 }
390
391 /* If there is a secret key it occupies the first block */
392 for (i = 0; i < kk; i++)
393 {
394 long_hold = key[i];
395 long_hold <<= 8 * (i % 8);
396
397 word_in_block = (i % bb) / 8;
398 /* block_index will always be 0 because kk <= 64 and bb = 128*/
399 blocks[0][word_in_block] |= long_hold;
400 }
401
402 has_key = kk > 0 ? 1 : 0;
403
404 for (i = 0; i < len; i++)
405 {
406 /* long_hold exists because the bit-shifting will overflow if we don't
407 * store the value */
408 long_hold = message[i];
409 long_hold <<= 8 * (i % 8);
410
411 block_index = has_key + (i / bb);
412 word_in_block = (i % bb) / 8;
413
414 blocks[block_index][word_in_block] |= long_hold;
415 }
416
417 u128_fill(ll, len);
418
419 BLAKE2B(dest, blocks, dd, ll, kk, nn);
420
421 free(blocks);
422
423 return dest;
424}
#define KK_MAX
max key length for BLAKE2b
Definition hash_blake2b.c:38
#define NN_MAX
max length of BLAKE2b digest in bytes
Definition hash_blake2b.c:43
#define MIN(a, b)
returns minimum value
Definition hash_blake2b.c:56
static void u128_fill(u128 dest, size_t n)
put value of n into dest
Definition hash_blake2b.c:120
uint64_t u128[2]
128-bit number represented as two uint64's
Definition hash_blake2b.c:78
uint64_t block_t[bb/sizeof(uint64_t)]
Padded input block containing bb bytes.
Definition hash_blake2b.c:81
static int BLAKE2B(uint8_t *dest, block_t *d, size_t dd, u128 ll, uint8_t kk, uint8_t nn)
driver function to perform the hashing as described in specification
Definition hash_blake2b.c:286
#define CEIL(a, b)
ceiling division macro without floats
Definition hash_blake2b.c:51
#define MAX(a, b)
returns maximum value
Definition hash_blake2b.c:61
#define bb
for asserts
Definition hash_blake2b.c:33
#define malloc(bytes)
This macro replace the standard malloc function with malloc_dbg.
Definition malloc_dbg.h:18
#define free(ptr)
This macro replace the standard free function with free_dbg.
Definition malloc_dbg.h:26
#define calloc(elemCount, elemSize)
This macro replace the standard calloc function with calloc_dbg.
Definition malloc_dbg.h:22
Here is the call graph for this function:

◆ BLAKE2B()

static int BLAKE2B ( uint8_t *  dest,
block_t d,
size_t  dd,
u128  ll,
uint8_t  kk,
uint8_t  nn 
)
static

driver function to perform the hashing as described in specification

pseudocode: (credit to authors of RFC 7693 listed above) FUNCTION BLAKE2( d[0..dd-1], ll, kk, nn ) | | h[0..7] := IV[0..7] // Initialization Vector. | | // Parameter block p[0] | h[0] := h[0] ^ 0x01010000 ^ (kk << 8) ^ nn | | // Process padded key and data blocks | IF dd > 1 THEN | | FOR i = 0 TO dd - 2 DO | | | h := F( h, d[i], (i + 1) * bb, FALSE ) | | END FOR. | END IF. | | // Final block. | IF kk = 0 THEN | | h := F( h, d[dd - 1], ll, TRUE ) | ELSE | | h := F( h, d[dd - 1], ll + bb, TRUE ) | END IF. | | RETURN first "nn" bytes from little-endian word array h[]. | END FUNCTION.

Parameters
destdestination of hashing digest
dmessage blocks
ddlength of d
ll128-bit length of message
kklength of secret key
nnlength of hash digest
Returns
0 upon successful hash
288{
289 uint8_t bytes[8];
290 uint64_t i, j;
291 uint64_t h[8];
292 u128 t = U128_ZERO;
293
294 /* h[0..7] = IV[0..7] */
295 for (i = 0; i < 8; i++)
296 {
297 h[i] = blake2b_iv[i];
298 }
299
300 h[0] ^= 0x01010000 ^ (kk << 8) ^ nn;
301
302 if (dd > 1)
303 {
304 for (i = 0; i < dd - 1; i++)
305 {
306 u128_increment(t, bb);
307 F(h, d[i], t, 0);
308 }
309 }
310
311 if (kk != 0)
312 {
313 u128_increment(ll, bb);
314 }
315 F(h, d[dd - 1], ll, 1);
316
317 /* copy bytes from h to destination buffer */
318 for (i = 0; i < nn; i++)
319 {
320 if (i % sizeof(uint64_t) == 0)
321 {
322 /* copy values from uint64 to 8 u8's */
323 for (j = 0; j < sizeof(uint64_t); j++)
324 {
325 uint16_t offset = 8 * j;
326 uint64_t mask = 0xFF;
327 mask <<= offset;
328
329 bytes[j] = (h[i / 8] & (mask)) >> offset;
330 }
331 }
332
333 dest[i] = bytes[i % 8];
334 }
335
336 return 0;
337}
static void F(uint64_t h[8], block_t m, u128 t, int f)
compression function F
Definition hash_blake2b.c:203
#define U128_ZERO
zero-value initializer for u128 type
Definition hash_blake2b.c:72
static const uint64_t blake2b_iv[8]
BLAKE2b Initialization vector blake2b_iv[i] = floor(2**64 * frac(sqrt(prime(i+1)))),...
Definition hash_blake2b.c:88
static void u128_increment(u128 dest, uint64_t n)
increment an 128-bit number by a given amount
Definition hash_blake2b.c:147
Here is the call graph for this function:

◆ crc32()

uint32_t crc32 ( const char *  s)

32-bit CRC algorithm implementation

Parameters
sNULL terminated ASCII string to hash
Returns
32-bit hash result
21{
22 uint32_t crc = 0xffffffff;
23 size_t i = 0;
24 while (s[i] != '\0')
25 {
26 uint8_t byte = s[i];
27 crc = crc ^ byte;
28 for (uint8_t j = 8; j > 0; --j)
29 {
30 crc = (crc >> 1) ^ (0xEDB88320 & (-(crc & 1)));
31 }
32
33 i++;
34 }
35 return crc ^ 0xffffffff;
36}

◆ djb2()

uint64_t djb2 ( const char *  s)

DJB2 algorithm implementation.

Parameters
sNULL terminated string to hash
Returns
64-bit hash result
19{
20 uint64_t hash = 5381; /* init value */
21 size_t i = 0;
22 while (s[i] != '\0')
23 {
24 hash = ((hash << 5) + hash) + s[i];
25 i++;
26 }
27 return hash;
28}

◆ F()

static void F ( uint64_t  h[8],
block_t  m,
u128  t,
int  f 
)
static

compression function F

Securely mixes the values in block m into the state vector h. Value at v[14] is also inverted if this is the final block to be compressed.

Parameters
hthe state vector
mmessage vector to be compressed into h
t128-bit offset counter
fflag to indicate whether this is the final block
Returns
void
204{
205 int i;
206 block_t v;
207
208 /* v[0..7] := h[0..7] */
209 for (i = 0; i < 8; i++)
210 {
211 v[i] = h[i];
212 }
213 /* v[8..15] := IV[0..7] */
214 for (; i < 16; i++)
215 {
216 v[i] = blake2b_iv[i - 8];
217 }
218
219 v[12] ^= t[0]; /* v[12] ^ (t mod 2**w) */
220 v[13] ^= t[1]; /* v[13] ^ (t >> w) */
221
222 if (f)
223 {
224 v[14] = ~v[14];
225 }
226
227 for (i = 0; i < 12; i++)
228 {
229 const uint8_t *s = blake2b_sigma[i];
230
231 G(v, 0, 4, 8, 12, m[s[0]], m[s[1]]);
232 G(v, 1, 5, 9, 13, m[s[2]], m[s[3]]);
233 G(v, 2, 6, 10, 14, m[s[4]], m[s[5]]);
234 G(v, 3, 7, 11, 15, m[s[6]], m[s[7]]);
235
236 G(v, 0, 5, 10, 15, m[s[8]], m[s[9]]);
237 G(v, 1, 6, 11, 12, m[s[10]], m[s[11]]);
238 G(v, 2, 7, 8, 13, m[s[12]], m[s[13]]);
239 G(v, 3, 4, 9, 14, m[s[14]], m[s[15]]);
240 }
241
242 for (i = 0; i < 8; i++)
243 {
244 h[i] ^= v[i] ^ v[i + 8];
245 }
246}
static void G(block_t v, uint8_t a, uint8_t b, uint8_t c, uint8_t d, uint64_t x, uint64_t y)
blake2b mixing function G
Definition hash_blake2b.c:175
static const uint8_t blake2b_sigma[12][16]
word schedule permutations for each round of the algorithm
Definition hash_blake2b.c:97
Here is the call graph for this function:

◆ G()

static void G ( block_t  v,
uint8_t  a,
uint8_t  b,
uint8_t  c,
uint8_t  d,
uint64_t  x,
uint64_t  y 
)
static

blake2b mixing function G

Shuffles values in block v depending on provided indeces a, b, c, and d. x and y are also mixed into the block.

Parameters
varray of words to be mixed
afirst index
bsecond index
cthird index
dfourth index
xfirst word being mixed into v
ysecond word being mixed into y
Returns
void
177{
178 v[a] += v[b] + x;
179 v[d] = ROTR64(v[d] ^ v[a], R1);
180 v[c] += v[d];
181 v[b] = ROTR64(v[b] ^ v[c], R2);
182 v[a] += v[b] + y;
183 v[d] = ROTR64(v[d] ^ v[a], R3);
184 v[c] += v[d];
185 v[b] = ROTR64(v[b] ^ v[c], R4);
186}
#define ROTR64(n, offset)
macro to rotate 64-bit ints to the right Ripped from RFC 7693
Definition hash_blake2b.c:67
static const uint8_t R2
Rotation constant 2 for mixing function G.
Definition hash_blake2b.c:84
static const uint8_t R1
Rotation constant 1 for mixing function G.
Definition hash_blake2b.c:83
static const uint8_t R3
Rotation constant 3 for mixing function G.
Definition hash_blake2b.c:85
static const uint8_t R4
Rotation constant 4 for mixing function G.
Definition hash_blake2b.c:86

◆ sdbm()

uint64_t sdbm ( const char *  s)

SDBM algorithm implementation.

Parameters
sNULL terminated string to hash
Returns
64-bit hash result
19{
20 uint64_t hash = 0;
21 size_t i = 0;
22 while (s[i] != '\0')
23 {
24 hash = s[i] + (hash << 6) + (hash << 16) - hash;
25 i++;
26 }
27 return hash;
28}

◆ test_adler32()

void test_adler32 ( )

Test function for adler32.

Returns
None
39{
40 assert(adler32("Hello World") == 403375133);
41 assert(adler32("Hello World!") == 474547262);
42 assert(adler32("Hello world") == 413860925);
43 assert(adler32("Hello world!") == 487130206);
44 printf("Tests passed\n");
45}
uint32_t adler32(const char *s)
32-bit Adler algorithm implementation
Definition hash_adler32.c:18
Here is the call graph for this function:

◆ test_crc32()

void test_crc32 ( )

Test function for crc32.

Returns
None
43{
44 assert(crc32("Hello World") == 1243066710);
45 assert(crc32("Hello World!") == 472456355);
46 assert(crc32("Hello world") == 2346098258);
47 assert(crc32("Hello world!") == 461707669);
48 printf("Tests passed\n");
49}
uint32_t crc32(const char *s)
32-bit CRC algorithm implementation
Definition hash_crc32.c:20
Here is the call graph for this function:

◆ test_djb2()

void test_djb2 ( void  )

Test function for djb2.

Returns
none
35{
36 assert(djb2("Hello World") == 13827776004929097857);
37 assert(djb2("Hello World!") == 13594750393630990530);
38 assert(djb2("Hello world") == 13827776004967047329);
39 assert(djb2("Hello world!") == 13594750394883323106);
40 printf("Tests passed\n");
41}
uint64_t djb2(const char *s)
DJB2 algorithm implementation.
Definition hash_djb2.c:18
Here is the call graph for this function:

◆ test_sdbm()

void test_sdbm ( )

Test function for sdbm.

Returns
None
35{
36 assert(sdbm("Hello World") == 12881824461405877380U);
37 assert(sdbm("Hello World!") == 7903571203300273309);
38 assert(sdbm("Hello world") == 15154913742888948900U);
39 assert(sdbm("Hello world!") == 15254999417003201661U);
40 printf("Tests passed\n");
41}
uint64_t sdbm(const char *s)
SDBM algorithm implementation.
Definition hash_sdbm.c:18
Here is the call graph for this function:

◆ test_xor8()

void test_xor8 ( )

Test function for xor8.

Returns
None
36{
37 assert(xor8("Hello World") == 228);
38 assert(xor8("Hello World!") == 195);
39 assert(xor8("Hello world") == 196);
40 assert(xor8("Hello world!") == 163);
41 printf("Tests passed\n");
42}
uint8_t xor8(const char *s)
8-bit XOR algorithm implementation
Definition hash_xor8.c:19
Here is the call graph for this function:

◆ u128_fill()

static void u128_fill ( u128  dest,
size_t  n 
)
inlinestatic

put value of n into dest

Parameters
dest128-bit number to get copied from n
nvalue put into dest
Returns
void
121{
122 dest[0] = n & UINT64_MAX;
123
124 if (sizeof(n) > 8)
125 {
126 /* The C standard does not specify a maximum length for size_t,
127 * although most machines implement it to be the same length as
128 * uint64_t. On machines where size_t is 8 bytes long this will issue a
129 * compiler warning, which is why it is suppressed. But on a machine
130 * where size_t is greater than 8 bytes, this will work as normal. */
131 dest[1] = n >> 64;
132 }
133 else
134 {
135 dest[1] = 0;
136 }
137}

◆ u128_increment()

static void u128_increment ( u128  dest,
uint64_t  n 
)
inlinestatic

increment an 128-bit number by a given amount

Parameters
destthe value being incremented
nwhat dest is being increased by
Returns
void
148{
149 /* Check for overflow */
150 if (UINT64_MAX - dest[0] <= n)
151 {
152 dest[1]++;
153 }
154
155 dest[0] += n;
156}

◆ xor8()

uint8_t xor8 ( const char *  s)

8-bit XOR algorithm implementation

Parameters
sNULL terminated ASCII string to hash
Returns
8-bit hash result
20{
21 uint8_t hash = 0;
22 size_t i = 0;
23 while (s[i] != '\0')
24 {
25 hash = (hash + s[i]) & 0xff;
26 i++;
27 }
28 return (((hash ^ 0xff) + 1) & 0xff);
29}

Variable Documentation

◆ blake2b_iv

const uint64_t blake2b_iv[8]
static
Initial value:
= {
0x6A09E667F3BCC908, 0xBB67AE8584CAA73B, 0x3C6EF372FE94F82B,
0xA54FF53A5F1D36F1, 0x510E527FADE682D1, 0x9B05688C2B3E6C1F,
0x1F83D9ABFB41BD6B, 0x5BE0CD19137E2179}

BLAKE2b Initialization vector blake2b_iv[i] = floor(2**64 * frac(sqrt(prime(i+1)))), where prime(i) is the i:th prime number.

88 {
89 0x6A09E667F3BCC908, 0xBB67AE8584CAA73B, 0x3C6EF372FE94F82B,
90 0xA54FF53A5F1D36F1, 0x510E527FADE682D1, 0x9B05688C2B3E6C1F,
91 0x1F83D9ABFB41BD6B, 0x5BE0CD19137E2179}; ///< BLAKE2b Initialization vector

◆ blake2b_sigma

const uint8_t blake2b_sigma[12][16]
static
Initial value:
= {
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
{14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3},
{11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4},
{7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8},
{9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13},
{2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9},
{12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11},
{13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10},
{6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5},
{10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0},
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
{14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5,
3}}

word schedule permutations for each round of the algorithm

97 {
98 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
99 {14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3},
100 {11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4},
101 {7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8},
102 {9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13},
103 {2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9},
104 {12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11},
105 {13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10},
106 {6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5},
107 {10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0},
108 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
109 {14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5,
110 3}}; ///< word schedule permutations for each round of the algorithm