1// Copyright 2019+ Klaus Post. All rights reserved. 2// License information can be found in the LICENSE file. 3// Based on work by Yann Collet, released under BSD License. 4 5package zstd 6 7const ( 8 prime3bytes = 506832829 9 prime4bytes = 2654435761 10 prime5bytes = 889523592379 11 prime6bytes = 227718039650203 12 prime7bytes = 58295818150454627 13 prime8bytes = 0xcf1bbcdcb7a56463 14) 15 16// hashLen returns a hash of the lowest l bytes of u for a size size of h bytes. 17// l must be >=4 and <=8. Any other value will return hash for 4 bytes. 18// h should always be <32. 19// Preferably h and l should be a constant. 20// FIXME: This does NOT get resolved, if 'mls' is constant, 21// so this cannot be used. 22func hashLen(u uint64, hashLog, mls uint8) uint32 { 23 switch mls { 24 case 5: 25 return hash5(u, hashLog) 26 case 6: 27 return hash6(u, hashLog) 28 case 7: 29 return hash7(u, hashLog) 30 case 8: 31 return hash8(u, hashLog) 32 default: 33 return hash4x64(u, hashLog) 34 } 35} 36 37// hash3 returns the hash of the lower 3 bytes of u to fit in a hash table with h bits. 38// Preferably h should be a constant and should always be <32. 39func hash3(u uint32, h uint8) uint32 { 40 return ((u << (32 - 24)) * prime3bytes) >> ((32 - h) & 31) 41} 42 43// hash4 returns the hash of u to fit in a hash table with h bits. 44// Preferably h should be a constant and should always be <32. 45func hash4(u uint32, h uint8) uint32 { 46 return (u * prime4bytes) >> ((32 - h) & 31) 47} 48 49// hash4x64 returns the hash of the lowest 4 bytes of u to fit in a hash table with h bits. 50// Preferably h should be a constant and should always be <32. 51func hash4x64(u uint64, h uint8) uint32 { 52 return (uint32(u) * prime4bytes) >> ((32 - h) & 31) 53} 54 55// hash5 returns the hash of the lowest 5 bytes of u to fit in a hash table with h bits. 56// Preferably h should be a constant and should always be <64. 57func hash5(u uint64, h uint8) uint32 { 58 return uint32(((u << (64 - 40)) * prime5bytes) >> ((64 - h) & 63)) 59} 60 61// hash6 returns the hash of the lowest 6 bytes of u to fit in a hash table with h bits. 62// Preferably h should be a constant and should always be <64. 63func hash6(u uint64, h uint8) uint32 { 64 return uint32(((u << (64 - 48)) * prime6bytes) >> ((64 - h) & 63)) 65} 66 67// hash7 returns the hash of the lowest 7 bytes of u to fit in a hash table with h bits. 68// Preferably h should be a constant and should always be <64. 69func hash7(u uint64, h uint8) uint32 { 70 return uint32(((u << (64 - 56)) * prime7bytes) >> ((64 - h) & 63)) 71} 72 73// hash8 returns the hash of u to fit in a hash table with h bits. 74// Preferably h should be a constant and should always be <64. 75func hash8(u uint64, h uint8) uint32 { 76 return uint32((u * prime8bytes) >> ((64 - h) & 63)) 77} 78