lib/hash.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #include <config.h>
  17 #include "hash.h"
  18 #include <string.h>
  19
  20 /* Returns the hash of the 'n' 32-bit words at 'p', starting from 'basis'.
  21  * 'p' must be properly aligned. */
  22 uint32_t
  23 hash_words(const uint32_t *p, size_t n, uint32_t basis)
  24 {
  25     uint32_t a, b, c;
  26
  27     a = b = c = 0xdeadbeef + (((uint32_t) n) << 2) + basis;
  28
  29     while (n > 3) {
  30         a += p[0];
  31         b += p[1];
  32         c += p[2];
  33         HASH_MIX(a, b, c);
  34         n -= 3;
  35         p += 3;
  36     }
  37
  38     switch (n) {
  39     case 3:
  40         c += p[2];
  41         /* fall through */
  42     case 2:
  43         b += p[1];
  44         /* fall through */
  45     case 1:
  46         a += p[0];
  47         HASH_FINAL(a, b, c);
  48         /* fall through */
  49     case 0:
  50         break;
  51     }
  52     return c;
  53 }
  54
  55 /* Returns the hash of 'a', 'b', and 'c'. */
  56 uint32_t
  57 hash_3words(uint32_t a, uint32_t b, uint32_t c)
  58 {
  59     a += 0xdeadbeef;
  60     b += 0xdeadbeef;
  61     c += 0xdeadbeef;
  62     HASH_FINAL(a, b, c);
  63     return c;
  64 }
  65
  66 /* Returns the hash of 'a' and 'b'. */
  67 uint32_t
  68 hash_2words(uint32_t a, uint32_t b)
  69 {
  70     return hash_3words(a, b, 0);
  71 }
  72
  73 /* Returns the hash of the 'n' bytes at 'p', starting from 'basis'. */
  74 uint32_t
  75 hash_bytes(const void *p_, size_t n, uint32_t basis)
  76 {
  77     const uint8_t *p = p_;
  78     uint32_t a, b, c;
  79     uint32_t tmp[3];
  80
  81     a = b = c = 0xdeadbeef + n + basis;
  82
  83     while (n >= sizeof tmp) {
  84         memcpy(tmp, p, sizeof tmp);
  85         a += tmp[0];
  86         b += tmp[1];
  87         c += tmp[2];
  88         HASH_MIX(a, b, c);
  89         n -= sizeof tmp;
  90         p += sizeof tmp;
  91     }
  92
  93     if (n) {
  94         tmp[0] = tmp[1] = tmp[2] = 0;
  95         memcpy(tmp, p, n);
  96         a += tmp[0];
  97         b += tmp[1];
  98         c += tmp[2];
  99         HASH_FINAL(a, b, c);
 100     }
 101
 102     return c;
 103 }