Line data    Source code

       1             : /*
       2             :  *  hash.c
       3             :  *  Patater GUI Kit
       4             :  *
       5             :  *  Created by Jaeden Amero on 2019-05-04.
       6             :  *  Copyright 2019. SPDX-License-Identifier: AGPL-3.0-or-later
       7             :  */
       8             : 
       9             : #include "guikit/hash.h"
      10             : 
      11             : /* FNV-1a algorithm description from
      12             :  * http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param */
      13         212 : static u32 hash_fnv1a_32(const char *buf, size_t len)
      14             : {
      15             :     /* FNV-1a parameters for a 32-bit hash */
      16         212 :     const u32 PRIME_32 = 16777619UL;
      17         212 :     const u32 OFFSET_32 = 2166136261UL;
      18             : 
      19         212 :     u32 h = OFFSET_32;
      20             :     size_t i;
      21             : 
      22             :     /* Note: could be faster if we do machine-word-sized chunks. */
      23        7331 :     for (i = 0; i < len; i++)
      24             :     {
      25        7119 :         h ^= ((u8)buf[i]) & 0xFFUL;
      26        7119 :         h *= PRIME_32;
      27             :     }
      28             : 
      29         212 :     return h;
      30             : }
      31             : 
      32             : /* Set out to the 64-bit truncated result of the unsigned multiplication of a *
      33             :  * b, where a and b are 64-bit little endian and out is 64-bit. */
      34             : /* Use long multiplication with 16-bit word size, so we can store the full
      35             :  * multiplication result in a word on a 32-bit machine, per Algorithm M from
      36             :  * Knuth Vol 2. Unlike Algorithm M, cut out all calculations for the upper
      37             :  * 64-bits of the result, as we know we won't use those; this makes the
      38             :  * calculation triangly. */
      39             : /* Note that this function does not work in place. out can't be one of the
      40             :  * input parameters, a or b. */
      41        7099 : static void umul64(u16 out[], const u16 a[], const u16 b[])
      42             : {
      43             :     u32 k;
      44             :     u32 t;
      45             : 
      46        7099 :     t = a[0] * b[0];
      47        7099 :     out[0] = t;
      48        7099 :     k = t >> 16;
      49             : 
      50        7099 :     t = a[1] * b[0] + k;
      51        7099 :     out[1] = t;
      52        7099 :     k = t >> 16;
      53             : 
      54        7099 :     t = a[2] * b[0] + k;
      55        7099 :     out[2] = t;
      56        7099 :     k = t >> 16;
      57             : 
      58        7099 :     t = a[3] * b[0] + k;
      59        7099 :     out[3] = t;
      60             : 
      61        7099 :     t = a[0] * b[1] + out[1];
      62        7099 :     out[1] = t;
      63        7099 :     k = t >> 16;
      64             : 
      65        7099 :     t = a[1] * b[1] + out[2] + k;
      66        7099 :     out[2] = t;
      67        7099 :     k = t >> 16;
      68             : 
      69        7099 :     t = a[2] * b[1] + out[3] + k;
      70        7099 :     out[3] = t;
      71             : 
      72        7099 :     t = a[0] * b[2] + out[2];
      73        7099 :     out[2] = t;
      74        7099 :     k = t >> 16;
      75             : 
      76        7099 :     t = a[1] * b[2] + out[3] + k;
      77        7099 :     out[3] = t;
      78             : 
      79        7099 :     t = a[0] * b[3] + out[3];
      80        7099 :     out[3] = t;
      81        7099 : }
      82             : 
      83             : /* FNV-1a algorithm description from
      84             :  * http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param */
      85         211 : static void hash_fnv1a_64(u32 hash[], const char *buf, size_t len)
      86             : {
      87             :     /* FNV-1a parameters for a 64-bit hash:
      88             :      * 64 bit FNV_prime = 1 << 40 + 1 << 8 + 0xB3
      89             :      *                  = 1099511628211 = 0x100000001B3
      90             :      * 64 bit offset_basis = 14695981039346656037 = 0xCBF29CE484222325
      91             :      */
      92         211 :     const u16 PRIME_64[4] = {0x01B3, 0x0000, 0x0100, 0x0000};
      93             :     const u16 OFFSET_64[4] = {0x2325, 0x8422, 0x9CE4, 0xCBF2};
      94             : 
      95         211 :     u16 h[4];
      96         211 :     u16 h_next[4];
      97             :     size_t i;
      98             : 
      99         211 :     h[0] = OFFSET_64[0];
     100         211 :     h[1] = OFFSET_64[1];
     101         211 :     h[2] = OFFSET_64[2];
     102         211 :     h[3] = OFFSET_64[3];
     103             : 
     104             :     /* Note: could be faster if we do machine-word-sized chunks. */
     105        7310 :     for (i = 0; i < len; i++)
     106             :     {
     107        7099 :         h[0] ^= ((u8)buf[i]) & 0xFFUL;
     108             : 
     109             :         /* Multiply h by PRIME_64 */
     110        7099 :         umul64(h_next, h, PRIME_64);
     111        7099 :         h[0] = h_next[0];
     112        7099 :         h[1] = h_next[1];
     113        7099 :         h[2] = h_next[2];
     114        7099 :         h[3] = h_next[3];
     115             :         /* Note we are throwing away the upper 64-bits of the multiplication */
     116             :     }
     117             : 
     118         211 :     hash[0] = ((u32)h[1] << 16) | h[0];
     119         211 :     hash[1] = ((u32)h[3] << 16) | h[2];
     120         211 : }
     121             : 
     122         212 : unsigned long hash(const char *buf, size_t len)
     123             : {
     124         212 :     return hash_fnv1a_32(buf, len);
     125             : }
     126             : 
     127         211 : void hash64(u32 out[], const char *buf, size_t len)
     128             : {
     129         211 :     hash_fnv1a_64(out, buf, len);
     130         211 : }