lib/hash-aarch64.h

   1 /*
   2  * Copyright (c) 2019 Arm Limited
   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
  17 /* This header implements HASH operation primitives on aarch64. */
  18 #ifndef HASH_AARCH64_H
  19 #define HASH_AARCH64_H 1
  20
  21 #ifndef HASH_H
  22 #error "This header should only be included indirectly via hash.h."
  23 #endif
  24
  25 #ifdef __cplusplus
  26 extern "C" {
  27 #endif
  28
  29 #include <arm_acle.h>
  30
  31 static inline uint32_t hash_add(uint32_t hash, uint32_t data)
  32 {
  33     return __crc32cw(hash, data);
  34 }
  35
  36 /* Add the halves of 'data' in the memory order. */
  37 static inline uint32_t hash_add64(uint32_t hash, uint64_t data)
  38 {
  39     return __crc32cd(hash, data);
  40 }
  41
  42 static inline uint32_t hash_finish(uint32_t hash, uint64_t final)
  43 {
  44     /* The finishing multiplier 0x805204f3 has been experimentally
  45      * derived to pass the testsuite hash tests. */
  46     hash = __crc32cd(hash, final) * 0x805204f3;
  47     return hash ^ hash >> 16; /* Increase entropy in LSBs. */
  48 }
  49
  50 /* Returns the hash of the 'n' 32-bit words at 'p_', starting from 'basis'.
  51  * We access 'p_' as a uint64_t pointer.
  52  *
  53  * This is inlined for the compiler to have access to the 'n_words', which
  54  * in many cases is a constant. */
  55 static inline uint32_t
  56 hash_words_inline(const uint32_t p_[], size_t n_words, uint32_t basis)
  57 {
  58     const uint64_t *p = (const void *)p_;
  59     uint32_t hash1 = basis;
  60     uint32_t hash2 = 0;
  61     uint32_t hash3 = n_words;
  62     const uint32_t *endp = (const uint32_t *)p + n_words;
  63     const uint64_t *limit = p + n_words / 2 - 3;
  64
  65     while (p <= limit) {
  66         hash1 = __crc32cd(hash1, p[0]);
  67         hash2 = __crc32cd(hash2, p[1]);
  68         hash3 = __crc32cd(hash3, p[2]);
  69         p += 3;
  70     }
  71     switch (endp - (const uint32_t *)p) {
  72     case 1:
  73         hash1 = __crc32cw(hash1, *(const uint32_t *)&p[0]);
  74         break;
  75     case 2:
  76         hash1 = __crc32cd(hash1, p[0]);
  77         break;
  78     case 3:
  79         hash1 = __crc32cd(hash1, p[0]);
  80         hash2 = __crc32cw(hash2, *(const uint32_t *)&p[1]);
  81         break;
  82     case 4:
  83         hash1 = __crc32cd(hash1, p[0]);
  84         hash2 = __crc32cd(hash2, p[1]);
  85         break;
  86     case 5:
  87         hash1 = __crc32cd(hash1, p[0]);
  88         hash2 = __crc32cd(hash2, p[1]);
  89         hash3 = __crc32cw(hash3, *(const uint32_t *)&p[2]);
  90         break;
  91     }
  92     return hash_finish(hash1, (uint64_t)hash2 << 32 | hash3);
  93 }
  94
  95 /* A simpler version for 64-bit data.
  96  * 'n_words' is the count of 64-bit words, basis is 64 bits. */
  97 static inline uint32_t
  98 hash_words64_inline(const uint64_t p[], size_t n_words, uint32_t basis)
  99 {
 100     uint32_t hash1 = basis;
 101     uint32_t hash2 = 0;
 102     uint32_t hash3 = n_words;
 103     const uint64_t *endp = p + n_words;
 104     const uint64_t *limit = endp - 3;
 105
 106     while (p <= limit) {
 107         hash1 = __crc32cd(hash1, p[0]);
 108         hash2 = __crc32cd(hash2, p[1]);
 109         hash3 = __crc32cd(hash3, p[2]);
 110         p += 3;
 111     }
 112     switch (endp - p) {
 113     case 1:
 114         hash1 = __crc32cd(hash1, p[0]);
 115         break;
 116     case 2:
 117         hash1 = __crc32cd(hash1, p[0]);
 118         hash2 = __crc32cd(hash2, p[1]);
 119         break;
 120     }
 121     return hash_finish(hash1, (uint64_t)hash2 << 32 | hash3);
 122 }
 123
 124 static inline uint32_t hash_uint64_basis(const uint64_t x,
 125                                          const uint32_t basis)
 126 {
 127     /* '23' chosen to mix bits enough for the test-hash to pass. */
 128     return hash_finish(hash_add64(basis, x), 23);
 129 }
 130
 131 static inline uint32_t hash_uint64(const uint64_t x)
 132 {
 133     return hash_uint64_basis(x, 0);
 134 }
 135
 136 static inline uint32_t hash_2words(uint32_t x, uint32_t y)
 137 {
 138     return hash_uint64((uint64_t)y << 32 | x);
 139 }
 140
 141 static inline uint32_t hash_pointer(const void *p, uint32_t basis)
 142 {
 143     return hash_uint64_basis((uint64_t) (uintptr_t) p, basis);
 144 }
 145
 146 #ifdef __cplusplus
 147 }
 148 #endif
 149
 150 #endif /* hash-aarch64.h */