pdns/burtle.hh

   1 /*
   2  * This file is part of PowerDNS or dnsdist.
   3  * Copyright -- PowerDNS.COM B.V. and its contributors
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of version 2 of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * In addition, for the avoidance of any doubt, permission is granted to
  10  * link this program with OpenSSL and to (re)distribute the binaries
  11  * produced as the result of such linking.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22
  23 #pragma once
  24
  25 #include <cinttypes>
  26
  27 inline void burtlemix(uint32_t& a, uint32_t& b, uint32_t& c)
  28 {
  29   a -= b;
  30   a -= c;
  31   a ^= (c >> 13);
  32   b -= c;
  33   b -= a;
  34   b ^= (a << 8);
  35   c -= a;
  36   c -= b;
  37   c ^= (b >> 13);
  38   a -= b;
  39   a -= c;
  40   a ^= (c >> 12);
  41   b -= c;
  42   b -= a;
  43   b ^= (a << 16);
  44   c -= a;
  45   c -= b;
  46   c ^= (b >> 5);
  47   a -= b;
  48   a -= c;
  49   a ^= (c >> 3);
  50   b -= c;
  51   b -= a;
  52   b ^= (a << 10);
  53   c -= a;
  54   c -= b;
  55   c ^= (b >> 15);
  56 }
  57
  58 inline uint32_t burtle(const unsigned char* k, uint32_t length, uint32_t initval)
  59 {
  60   uint32_t a, b, c, len;
  61
  62   /* Set up the internal state */
  63   len = length;
  64   a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
  65   c = initval; /* the previous hash value */
  66
  67   /*---------------------------------------- handle most of the key */
  68   while (len >= 12) {
  69     a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16) + ((uint32_t)k[3] << 24));
  70     b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16) + ((uint32_t)k[7] << 24));
  71     c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16) + ((uint32_t)k[11] << 24));
  72     burtlemix(a, b, c);
  73     k += 12;
  74     len -= 12;
  75   }
  76
  77   /*------------------------------------- handle the last 11 bytes */
  78   c += length;
  79   switch (len) { /* all the case statements fall through */
  80   case 11:
  81     c += ((uint32_t)k[10] << 24);
  82     /* fall-through */
  83   case 10:
  84     c += ((uint32_t)k[9] << 16);
  85     /* fall-through */
  86   case 9:
  87     c += ((uint32_t)k[8] << 8);
  88     /* the first byte of c is reserved for the length */
  89     /* fall-through */
  90   case 8:
  91     b += ((uint32_t)k[7] << 24);
  92     /* fall-through */
  93   case 7:
  94     b += ((uint32_t)k[6] << 16);
  95     /* fall-through */
  96   case 6:
  97     b += ((uint32_t)k[5] << 8);
  98     /* fall-through */
  99   case 5:
 100     b += k[4];
 101     /* fall-through */
 102   case 4:
 103     a += ((uint32_t)k[3] << 24);
 104     /* fall-through */
 105   case 3:
 106     a += ((uint32_t)k[2] << 16);
 107     /* fall-through */
 108   case 2:
 109     a += ((uint32_t)k[1] << 8);
 110     /* fall-through */
 111   case 1:
 112     a += k[0];
 113     /* case 0: nothing left to add */
 114   }
 115   burtlemix(a, b, c);
 116   /*-------------------------------------------- report the result */
 117   return c;
 118 }
 119
 120 inline uint32_t burtleCI(const unsigned char* k, uint32_t length, uint32_t initval)
 121 {
 122   uint32_t a, b, c, len;
 123
 124   /* Set up the internal state */
 125   len = length;
 126   a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
 127   c = initval; /* the previous hash value */
 128
 129   /*---------------------------------------- handle most of the key */
 130   while (len >= 12) {
 131     a += (dns_tolower(k[0]) + ((uint32_t)dns_tolower(k[1]) << 8) + ((uint32_t)dns_tolower(k[2]) << 16) + ((uint32_t)dns_tolower(k[3]) << 24));
 132     b += (dns_tolower(k[4]) + ((uint32_t)dns_tolower(k[5]) << 8) + ((uint32_t)dns_tolower(k[6]) << 16) + ((uint32_t)dns_tolower(k[7]) << 24));
 133     c += (dns_tolower(k[8]) + ((uint32_t)dns_tolower(k[9]) << 8) + ((uint32_t)dns_tolower(k[10]) << 16) + ((uint32_t)dns_tolower(k[11]) << 24));
 134     burtlemix(a, b, c);
 135     k += 12;
 136     len -= 12;
 137   }
 138
 139   /*------------------------------------- handle the last 11 bytes */
 140   c += length;
 141   switch (len) { /* all the case statements fall through */
 142   case 11:
 143     c += ((uint32_t)dns_tolower(k[10]) << 24);
 144     /* fall-through */
 145   case 10:
 146     c += ((uint32_t)dns_tolower(k[9]) << 16);
 147     /* fall-through */
 148   case 9:
 149     c += ((uint32_t)dns_tolower(k[8]) << 8);
 150     /* the first byte of c is reserved for the length */
 151     /* fall-through */
 152   case 8:
 153     b += ((uint32_t)dns_tolower(k[7]) << 24);
 154     /* fall-through */
 155   case 7:
 156     b += ((uint32_t)dns_tolower(k[6]) << 16);
 157     /* fall-through */
 158   case 6:
 159     b += ((uint32_t)dns_tolower(k[5]) << 8);
 160     /* fall-through */
 161   case 5:
 162     b += dns_tolower(k[4]);
 163     /* fall-through */
 164   case 4:
 165     a += ((uint32_t)dns_tolower(k[3]) << 24);
 166     /* fall-through */
 167   case 3:
 168     a += ((uint32_t)dns_tolower(k[2]) << 16);
 169     /* fall-through */
 170   case 2:
 171     a += ((uint32_t)dns_tolower(k[1]) << 8);
 172     /* fall-through */
 173   case 1:
 174     a += dns_tolower(k[0]);
 175     /* case 0: nothing left to add */
 176   }
 177   burtlemix(a, b, c);
 178   /*-------------------------------------------- report the result */
 179   return c;
 180 }