summaryrefslogtreecommitdiffhomepage
path: root/ir/adt/bitfiddle.h
blob: bba3ccfef8debb3c7c46ba29a8d91de2314ac089 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @date    28.9.2004
 * @brief   Functions from hackers delight.
 * @author  Sebastian Hack, Matthias Braun
 */
#ifndef FIRM_ADT_BITFIDDLE_H
#define FIRM_ADT_BITFIDDLE_H

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>

#include "compiler.h"

/**
 * Compute the count of set bits in a 32-bit word.
 * @param x A 32-bit word.
 * @return The number of bits set in x.
 */
static inline uint32_t popcount(uint32_t x)
{
#if defined(__GNUC__) && __GNUC__ >= 4
	return __builtin_popcount(x);
#else
	x -= ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x + (x >> 4)) & 0x0f0f0f0f;
	x += x >> 8;
	x += x >> 16;
	return x & 0x3f;
#endif
}

/**
 * Compute the number of leading zeros in a word.
 * @param x The word.
 * @return The number of leading (from the most significant bit) zeros.
 */
static inline unsigned nlz(uint32_t x)
{
#if defined(__GNUC__) && __GNUC__ >= 4
	if (x == 0)
		return 32;
	return __builtin_clz(x);
#else

   unsigned y;
   unsigned n = 32;
   y = x >>16;  if (y != 0) { n -= 16;  x = y; }
   y = x >> 8;  if (y != 0) { n -=  8;  x = y; }
   y = x >> 4;  if (y != 0) { n -=  4;  x = y; }
   y = x >> 2;  if (y != 0) { n -=  2;  x = y; }
   y = x >> 1;  if (y != 0) return n - 2;
   return n - x;
#endif
}

/**
 * Compute the number of trailing zeros in a word.
 * @param x The word.
 * @return The number of trailing zeros.
 */
static inline unsigned ntz(uint32_t x)
{
#if defined(__GNUC__) && __GNUC__ >= 4
	if (x == 0)
		return 32;
	return __builtin_ctz(x);
#else
	return 32 - nlz(~x & (x - 1));
#endif
}

/**
 * Compute the greatest power of 2 smaller or equal to a value.
 * This is also known as the binary logarithm.
 * @param x The value.
 * @return The power of two.
 */
static inline uint32_t log2_floor(uint32_t x)
{
	return 32 - 1 - nlz(x);
}

/**
 * Compute the smallest power of 2 greater or equal to a value.
 * This is also known as the binary logarithm.
 * @param x The value.
 * @return The power of two.
 */
static inline uint32_t log2_ceil(uint32_t x)
{
	return 32 - nlz(x - 1);
}

/**
 * Returns the biggest power of 2 that is equal or smaller than @p x
 * (see hackers delight power-of-2 boundaries, page 48)
 */
static inline uint32_t floor_po2(uint32_t x)
{
#if defined(__GNUC__) && __GNUC__ >= 4 /* in this case nlz is fast */
	if (x == 0)
		return 0;
	/* note that x != 0 here, so nlz(x) < 32! */
	return 0x80000000U >> nlz(x);
#else
	x |= x >> 1;
	x |= x >> 2;
	x |= x >> 4;
	x |= x >> 8;
	x |= x >> 16;
	return x - (x >> 1);
#endif
}

/**
 * Returns the smallest power of 2 that is equal or greater than x
 * @remark x has to be <= 0x8000000 of course
 * @note see hackers delight power-of-2 boundaries, page 48
 */
static inline uint32_t ceil_po2(uint32_t x)
{
	if (x == 0)
		return 0;
	assert(x < (1U << 31));

#if defined(__GNUC__) && __GNUC__ >= 4 /* in this case nlz is fast */
	/* note that x != 0 here! */
	return 0x80000000U >> (nlz(x-1) - 1);
#else
	x = x - 1;
	x |= x >> 1;
	x |= x >> 2;
	x |= x >> 4;
	x |= x >> 8;
	x |= x >> 16;
	return x + 1;
#endif
}

/**
 * Returns true if \p x is a power of two or zero.
 */
static inline bool is_po2_or_zero(unsigned x)
{
	return (x & (x-1)) == 0;
}

/**
 * Round up to the next multiple of a power of two.
 * @param x A value.
 * @param pot A power of two.
 * @return x rounded up to the next multiple of pot.
 */
static inline unsigned round_up2(unsigned x, unsigned po2)
{
	assert(is_po2_or_zero(po2) && po2 > 0);
	unsigned const po2_minus_one = po2-1;
	unsigned const po2_mask      = ~po2_minus_one;
	return (x + po2_minus_one) & po2_mask;
}

#endif