pintos-os.org Git - openvswitch/blob - lib/hash.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2012 Nicira, Inc.
   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 #include "unaligned.h"
  20
  21 /* Returns the hash of the 'n' 32-bit words at 'p', starting from 'basis'.
  22  * 'p' must be properly aligned. */
  23 uint32_t
  24 hash_words(const uint32_t *p, size_t n, uint32_t basis)
  25 {
  26     uint32_t a, b, c;
  27
  28     a = b = c = 0xdeadbeef + (((uint32_t) n) << 2) + basis;
  29
  30     while (n > 3) {
  31         a += p[0];
  32         b += p[1];
  33         c += p[2];
  34         hash_mix(&a, &b, &c);
  35         n -= 3;
  36         p += 3;
  37     }
  38
  39     switch (n) {
  40     case 3:
  41         c += p[2];
  42         /* fall through */
  43     case 2:
  44         b += p[1];
  45         /* fall through */
  46     case 1:
  47         a += p[0];
  48         hash_final(&a, &b, &c);
  49         /* fall through */
  50     case 0:
  51         break;
  52     }
  53     return c;
  54 }
  55
  56 /* Returns the hash of 'a', 'b', and 'c'. */
  57 uint32_t
  58 hash_3words(uint32_t a, uint32_t b, uint32_t c)
  59 {
  60     a += 0xdeadbeef;
  61     b += 0xdeadbeef;
  62     c += 0xdeadbeef;
  63     hash_final(&a, &b, &c);
  64     return c;
  65 }
  66
  67 /* Returns the hash of 'a' and 'b'. */
  68 uint32_t
  69 hash_2words(uint32_t a, uint32_t b)
  70 {
  71     return hash_3words(a, b, 0);
  72 }
  73
  74 /* Returns the hash of the 'n' bytes at 'p', starting from 'basis'. */
  75 uint32_t
  76 hash_bytes(const void *p_, size_t n, uint32_t basis)
  77 {
  78     const uint8_t *p = p_;
  79     uint32_t a, b, c;
  80
  81     a = b = c = 0xdeadbeef + n + basis;
  82
  83     while (n >= 12) {
  84         a += get_unaligned_u32((uint32_t *) p);
  85         b += get_unaligned_u32((uint32_t *) (p + 4));
  86         c += get_unaligned_u32((uint32_t *) (p + 8));
  87         hash_mix(&a, &b, &c);
  88         n -= 12;
  89         p += 12;
  90     }
  91
  92     if (n) {
  93         uint32_t tmp[3];
  94
  95         tmp[0] = tmp[1] = tmp[2] = 0;
  96         memcpy(tmp, p, n);
  97         a += tmp[0];
  98         b += tmp[1];
  99         c += tmp[2];
 100         hash_final(&a, &b, &c);
 101     }
 102
 103     return c;
 104 }