1b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien/* 2b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * Copyright (C) 2012 The Android Open Source Project 3b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * 4b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * Licensed under the Apache License, Version 2.0 (the "License"); 5b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * you may not use this file except in compliance with the License. 6b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * You may obtain a copy of the License at 7b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * 8b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * http://www.apache.org/licenses/LICENSE-2.0 9b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * 10b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * Unless required by applicable law or agreed to in writing, software 11b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * distributed under the License is distributed on an "AS IS" BASIS, 12b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * See the License for the specific language governing permissions and 14b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * limitations under the License. 15b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien */ 16b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 17b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien/* Implementation of Jenkins one-at-a-time hash function. These choices are 18b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * optimized for code size and portability, rather than raw speed. But speed 19b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * should still be quite good. 20b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien **/ 21b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 22b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien#include <utils/JenkinsHash.h> 23b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 24b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Leviennamespace android { 25b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 26b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienhash_t JenkinsHashWhiten(uint32_t hash) { 27b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash += (hash << 3); 28b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash ^= (hash >> 11); 29b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash += (hash << 15); 30b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien return hash; 31b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 32b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 33b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienuint32_t JenkinsHashMixBytes(uint32_t hash, const uint8_t* bytes, size_t size) { 34b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash = JenkinsHashMix(hash, (uint32_t)size); 35b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien size_t i; 36b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien for (i = 0; i < (size & -4); i += 4) { 37b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien uint32_t data = bytes[i] | (bytes[i+1] << 8) | (bytes[i+2] << 16) | (bytes[i+3] << 24); 38b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash = JenkinsHashMix(hash, data); 39b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 40b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien if (size & 3) { 41b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien uint32_t data = bytes[i]; 42b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien data |= ((size & 3) > 1) ? (bytes[i+1] << 8) : 0; 43b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien data |= ((size & 3) > 2) ? (bytes[i+2] << 16) : 0; 44b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash = JenkinsHashMix(hash, data); 45b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 46b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien return hash; 47b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 48b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 49b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienuint32_t JenkinsHashMixShorts(uint32_t hash, const uint16_t* shorts, size_t size) { 50b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash = JenkinsHashMix(hash, (uint32_t)size); 51b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien size_t i; 52b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien for (i = 0; i < (size & -2); i += 2) { 53b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien uint32_t data = shorts[i] | (shorts[i+1] << 16); 54b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash = JenkinsHashMix(hash, data); 55b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 56b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien if (size & 1) { 57b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien uint32_t data = shorts[i]; 58b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hash = JenkinsHashMix(hash, data); 59b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 60b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien return hash; 61b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 62b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 63b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 64b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 65