1 /* 2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * All rights reserved. Distributed under the terms of the MIT license. 4 */ 5 #ifndef MISC_H 6 #define MISC_H 7 8 #include <SupportDefs.h> 9 10 #include "String.h" 11 12 // min and max 13 // We don't want to include <algobase.h> otherwise we also get <iostream.h> 14 // and other undesired things. 15 template<typename C> 16 static inline C min(const C &a, const C &b) { return (a < b ? a : b); } 17 template<typename C> 18 static inline C max(const C &a, const C &b) { return (a > b ? a : b); } 19 20 // find last (most significant) set bit 21 static inline 22 int 23 fls(uint32 value) 24 { 25 if (!value) 26 return -1; 27 int index = 0; 28 #define HAND_OPTIMIZED_FLS 1 29 #if !HAND_OPTIMIZED_FLS 30 // This is the algorithm in its pure form. 31 const uint32 masks[] = { 32 0xffff0000, 33 0xff00ff00, 34 0xf0f0f0f0, 35 0xcccccccc, 36 0xaaaaaaaa, 37 }; 38 int range = 16; 39 for (int i = 0; i < 5; i++) { 40 if (value & masks[i]) { 41 index += range; 42 value &= masks[i]; 43 } 44 range /= 2; 45 } 46 #else // HAND_OPTIMIZED_FLS 47 // This is how the compiler should optimize it for us: Unroll the loop and 48 // inline the masks. 49 // 0: 0xffff0000 50 if (value & 0xffff0000) { 51 index += 16; 52 value &= 0xffff0000; 53 } 54 // 1: 0xff00ff00 55 if (value & 0xff00ff00) { 56 index += 8; 57 value &= 0xff00ff00; 58 } 59 // 2: 0xf0f0f0f0 60 if (value & 0xf0f0f0f0) { 61 index += 4; 62 value &= 0xf0f0f0f0; 63 } 64 // 3: 0xcccccccc 65 if (value & 0xcccccccc) { 66 index += 2; 67 value &= 0xcccccccc; 68 } 69 // 4: 0xaaaaaaaa 70 if (value & 0xaaaaaaaa) 71 index++; 72 #endif // HAND_OPTIMIZED_FLS 73 return index; 74 } 75 76 // node_child_hash 77 static inline 78 uint32 79 node_child_hash(uint64 id, const char *name) 80 { 81 return uint32(id & 0xffffffff) ^ string_hash(name); 82 } 83 84 #endif // MISC_H 85