Given a table of uint16_t whose size is mask / 2 + 1, return a pointer to the relevant entry, if any, for the given bytes. Any hash function will do, but a good hash function reduces the number of collisions and thus yields better compression for compressible input. REQUIRES: mask is 2 * (table_size - 1), and table_size is a power of two.
| 153 | // |
| 154 | // REQUIRES: mask is 2 * (table_size - 1), and table_size is a power of two. |
| 155 | inline uint16_t* TableEntry(uint16_t* table, uint32_t bytes, uint32_t mask) { |
| 156 | // Our choice is quicker-and-dirtier than the typical hash function; |
| 157 | // empirically, that seems beneficial. The upper bits of kMagic * bytes are a |
| 158 | // higher-quality hash than the lower bits, so when using kMagic * bytes we |
| 159 | // also shift right to get a higher-quality end result. There's no similar |
| 160 | // issue with a CRC because all of the output bits of a CRC are equally good |
| 161 | // "hashes." So, a CPU instruction for CRC, if available, tends to be a good |
| 162 | // choice. |
| 163 | #if SNAPPY_HAVE_NEON_CRC32 |
| 164 | // We use mask as the second arg to the CRC function, as it's about to |
| 165 | // be used anyway; it'd be equally correct to use 0 or some constant. |
| 166 | // Mathematically, _mm_crc32_u32 (or similar) is a function of the |
| 167 | // xor of its arguments. |
| 168 | const uint32_t hash = __crc32cw(bytes, mask); |
| 169 | #elif SNAPPY_HAVE_X86_CRC32 |
| 170 | const uint32_t hash = _mm_crc32_u32(bytes, mask); |
| 171 | #else |
| 172 | constexpr uint32_t kMagic = 0x1e35a7bd; |
| 173 | const uint32_t hash = (kMagic * bytes) >> (31 - kMaxHashTableBits); |
| 174 | #endif |
| 175 | return reinterpret_cast<uint16_t*>(reinterpret_cast<uintptr_t>(table) + |
| 176 | (hash & mask)); |
| 177 | } |
| 178 | |
| 179 | inline uint16_t* TableEntry4ByteMatch(uint16_t* table, uint32_t bytes, |
| 180 | uint32_t mask) { |