1// Misc.h 2// 3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4// 5// Permission is hereby granted, free of charge, to any person obtaining a 6// copy of this software and associated documentation files (the "Software"), 7// to deal in the Software without restriction, including without limitation 8// the rights to use, copy, modify, merge, publish, distribute, sublicense, 9// and/or sell copies of the Software, and to permit persons to whom the 10// Software is furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21// DEALINGS IN THE SOFTWARE. 22// 23// Except as contained in this notice, the name of a copyright holder shall 24// not be used in advertising or otherwise to promote the sale, use or other 25// dealings in this Software without prior written authorization of the 26// copyright holder. 27 28#ifndef MISC_H 29#define MISC_H 30 31#include <SupportDefs.h> 32 33#include "String.h" 34 35// min and max 36// We don't want to include <algobase.h> otherwise we also get <iostream.h> 37// and other undesired things. 38template<typename C> 39static inline C min(const C &a, const C &b) { return (a < b ? a : b); } 40template<typename C> 41static inline C max(const C &a, const C &b) { return (a > b ? a : b); } 42 43// find last (most significant) set bit 44static inline 45int 46fls(uint32 value) 47{ 48 if (!value) 49 return -1; 50 int index = 0; 51#define HAND_OPTIMIZED_FLS 1 52#if !HAND_OPTIMIZED_FLS 53// This is the algorithm in its pure form. 54 const uint32 masks[] = { 55 0xffff0000, 56 0xff00ff00, 57 0xf0f0f0f0, 58 0xcccccccc, 59 0xaaaaaaaa, 60 }; 61 int range = 16; 62 for (int i = 0; i < 5; i++) { 63 if (value & masks[i]) { 64 index += range; 65 value &= masks[i]; 66 } 67 range /= 2; 68 } 69#else // HAND_OPTIMIZED_FLS 70// This is how the compiler should optimize it for us: Unroll the loop and 71// inline the masks. 72 // 0: 0xffff0000 73 if (value & 0xffff0000) { 74 index += 16; 75 value &= 0xffff0000; 76 } 77 // 1: 0xff00ff00 78 if (value & 0xff00ff00) { 79 index += 8; 80 value &= 0xff00ff00; 81 } 82 // 2: 0xf0f0f0f0 83 if (value & 0xf0f0f0f0) { 84 index += 4; 85 value &= 0xf0f0f0f0; 86 } 87 // 3: 0xcccccccc 88 if (value & 0xcccccccc) { 89 index += 2; 90 value &= 0xcccccccc; 91 } 92 // 4: 0xaaaaaaaa 93 if (value & 0xaaaaaaaa) 94 index++; 95#endif // HAND_OPTIMIZED_FLS 96 return index; 97} 98 99// node_child_hash 100static inline 101uint32 102node_child_hash(uint64 id, const char *name) 103{ 104 return uint32(id & 0xffffffff) ^ string_hash(name); 105} 106 107#endif // MISC_H 108