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. 38 template<typename C> 39 static inline C min(const C &a, const C &b) { return (a < b ? a : b); } 40 template<typename C> 41 static inline C max(const C &a, const C &b) { return (a > b ? a : b); } 42 43 // find last (most significant) set bit 44 static inline 45 int 46 fls(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 100 static inline 101 uint32 102 node_child_hash(uint64 id, const char *name) 103 { 104 return uint32(id & 0xffffffff) ^ string_hash(name); 105 } 106 107 #endif // MISC_H 108