diff options
Diffstat (limited to 'arch/arm/mvp/mvpkm/mvp_math.h')
-rw-r--r-- | arch/arm/mvp/mvpkm/mvp_math.h | 133 |
1 files changed, 133 insertions, 0 deletions
diff --git a/arch/arm/mvp/mvpkm/mvp_math.h b/arch/arm/mvp/mvpkm/mvp_math.h new file mode 100644 index 0000000..7017bc8 --- /dev/null +++ b/arch/arm/mvp/mvpkm/mvp_math.h @@ -0,0 +1,133 @@ +/* + * Linux 2.6.32 and later Kernel module for VMware MVP Hypervisor Support + * + * Copyright (C) 2010-2012 VMware, Inc. All rights reserved. + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; see the file COPYING. If not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ +#line 5 + +/** + * @file + * + * @brief Math library. + */ + +#ifndef _MVP_MATH_H_ +#define _MVP_MATH_H_ + +#define INCLUDE_ALLOW_VMX +#define INCLUDE_ALLOW_PV +#define INCLUDE_ALLOW_MODULE +#define INCLUDE_ALLOW_MONITOR +#define INCLUDE_ALLOW_GPL +#define INCLUDE_ALLOW_HOSTUSER +#include "include_check.h" + +#include "mvp_compiler_gcc.h" + +/** + * @brief Compute floor log2 of a given 32-bit unsigned integer. + * + * @param n 32-bit unsigned integer, n > 0. + * + * @return floor(log2(n)). + */ +#define LOG2(n) \ +( \ + __builtin_constant_p(n) ? ( \ + (n) & (1UL << 31) ? 31 : \ + (n) & (1UL << 30) ? 30 : \ + (n) & (1UL << 29) ? 29 : \ + (n) & (1UL << 28) ? 28 : \ + (n) & (1UL << 27) ? 27 : \ + (n) & (1UL << 26) ? 26 : \ + (n) & (1UL << 25) ? 25 : \ + (n) & (1UL << 24) ? 24 : \ + (n) & (1UL << 23) ? 23 : \ + (n) & (1UL << 22) ? 22 : \ + (n) & (1UL << 21) ? 21 : \ + (n) & (1UL << 20) ? 20 : \ + (n) & (1UL << 19) ? 19 : \ + (n) & (1UL << 18) ? 18 : \ + (n) & (1UL << 17) ? 17 : \ + (n) & (1UL << 16) ? 16 : \ + (n) & (1UL << 15) ? 15 : \ + (n) & (1UL << 14) ? 14 : \ + (n) & (1UL << 13) ? 13 : \ + (n) & (1UL << 12) ? 12 : \ + (n) & (1UL << 11) ? 11 : \ + (n) & (1UL << 10) ? 10 : \ + (n) & (1UL << 9) ? 9 : \ + (n) & (1UL << 8) ? 8 : \ + (n) & (1UL << 7) ? 7 : \ + (n) & (1UL << 6) ? 6 : \ + (n) & (1UL << 5) ? 5 : \ + (n) & (1UL << 4) ? 4 : \ + (n) & (1UL << 3) ? 3 : \ + (n) & (1UL << 2) ? 2 : \ + (n) & (1UL << 1) ? 1 : \ + (n) & (1UL << 0) ? 0 : \ + 0xffffffff \ + ) : (uint32)(CLZ(1) - CLZ(n)) \ +) + +/** + * @brief Multiplicative hash function for 32-bit key and p-bit range. See p229 + * Introduction to Algorithms, Cormen, Leiserson and Rivest, 1996. + * + * @param key 32-bit key. + * @param p range order, <= 32. + * + * @return hash value in range [0..2^p) + */ +static inline uint32 +Math_MultiplicativeHash(uint32 key, uint32 p) +{ + return (key * 2654435769UL) >> (32 - p); +} + +/** + * @brief Compute ceiling log2 of a given 32-bit unsigned integer. + * + * @param n 32-bit unsigned integer, n > 0. + * + * @return ceiling(log2(n)). + */ +static inline uint32 CLOG2(uint32 n) +{ + return LOG2(n) + ((n & -n) != n); +} + + +/** + * @brief djb2 String hashing function by Dan Bernstein, see + * http://www.cse.yorku.ca/~oz/hash.html + * @param str String to hash + * @return 32-bit hash value + */ +static inline +uint32 Math_Djb2Hash(uint8 *str) +{ + uint32 hash = 5381; + int32 c; + + while ((c = *str++)) { + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + } + + return hash; +} + +#endif // ifndef _MVP_MATH_H_ |