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.
15template<typename C>
16static inline C min(const C &a, const C &b) { return (a < b ? a : b); }
17template<typename C>
18static inline C max(const C &a, const C &b) { return (a > b ? a : b); }
19
20// find last (most significant) set bit
21static inline
22int
23fls(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
77static inline
78uint32
79node_child_hash(uint64 id, const char *name)
80{
81	return uint32(id & 0xffffffff) ^ string_hash(name);
82}
83
84#endif	// MISC_H
85