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