4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync/* $Id$ */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync/** @file
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * IPRT - Internal header containing inline string hashing functions.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync/*
c58f1213e628a545081c70e26c6b67a841cff880vboxsync * Copyright (C) 2006-2012 Oracle Corporation
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync *
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * available from http://www.virtualbox.org. This file is free software;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * you can redistribute it and/or modify it under the terms of the GNU
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * General Public License (GPL) as published by the Free Software
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync *
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * The contents of this file may alternatively be used under the terms
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * of the Common Development and Distribution License Version 1.0
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * VirtualBox OSE distribution, in which case the provisions of the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * CDDL are applicable instead of those of the GPL.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync *
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * You may elect to license modified versions of this file under the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * terms and conditions of either the GPL or the CDDL or both.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync#ifndef ___internal_strhash_h
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync#define ___internal_strhash_h
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync#include <iprt/types.h>
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync/* sdbm:
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync This algorithm was created for sdbm (a public-domain reimplementation of
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync ndbm) database library. it was found to do well in scrambling bits,
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync causing better distribution of the keys and fewer splits. it also happens
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync to be a good general hashing function with good distribution. the actual
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync is the faster version used in gawk. [there is even a faster, duff-device
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync version] the magic constant 65599 was picked out of thin air while
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync experimenting with different constants, and turns out to be a prime.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync this is one of the algorithms used in berkeley db (see sleepycat) and
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync elsewhere. */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync/**
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Hash string, return hash + length.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsyncDECLINLINE(uint32_t) sdbm(const char *str, size_t *pcch)
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync{
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync uint8_t *pu8 = (uint8_t *)str;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync uint32_t hash = 0;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync int c;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync while ((c = *pu8++))
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync hash = c + (hash << 6) + (hash << 16) - hash;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync *pcch = (uintptr_t)pu8 - (uintptr_t)str - 1;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync return hash;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync}
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync/**
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Hash up to N bytes, return hash + hashed length.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsyncDECLINLINE(uint32_t) sdbmN(const char *str, size_t cchMax, size_t *pcch)
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync{
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync uint8_t *pu8 = (uint8_t *)str;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync uint32_t hash = 0;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync int c;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync while ((c = *pu8++) && cchMax-- > 0)
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync hash = c + (hash << 6) + (hash << 16) - hash;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync *pcch = (uintptr_t)pu8 - (uintptr_t)str - 1;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync return hash;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync}
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync/**
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Incremental hashing.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsyncDECLINLINE(uint32_t) sdbmInc(const char *str, uint32_t hash)
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync{
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync uint8_t *pu8 = (uint8_t *)str;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync int c;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync while ((c = *pu8++))
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync hash = c + (hash << 6) + (hash << 16) - hash;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync return hash;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync}
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync/**
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync * Incremental hashing with length limitation.
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync */
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsyncDECLINLINE(uint32_t) sdbmIncN(const char *psz, size_t cchMax, uint32_t uHash)
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync{
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync uint8_t *pu8 = (uint8_t *)psz;
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync int c;
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync while ((c = *pu8++) && cchMax-- > 0)
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync uHash = c + (uHash << 6) + (uHash << 16) - uHash;
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync return uHash;
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync}
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync#endif
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync