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
|
/* -*-c++-*- */
/* $Id: msb.h,v 1.6 1998/12/26 18:21:51 dm Exp $ */
/*
*
* Copyright (C) 1998 David Mazieres (dm@uun.org)
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation; either version 2, or (at
* your option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
* USA
*
*/
#ifndef _MSB_H_
#define _MSB_H_ 1
#include "sysconf.h"
#ifdef __cplusplus
#define EXTERN_C extern "C"
#else /* !__cplusplus */
#define EXTERN_C extern
#endif /* !__cplusplus */
/*
* Routines for calculating the most significant bit of an integer.
*/
EXTERN_C const char bytemsb[];
/* Find last set (most significant bit) */
static inline u_int fls32 (u_int32_t) __attribute__ ((const));
static inline u_int
fls32 (u_int32_t v)
{
if (v & 0xffff0000) {
if (v & 0xff000000)
return 24 + bytemsb[v>>24];
else
return 16 + bytemsb[v>>16];
}
if (v & 0x0000ff00)
return 8 + bytemsb[v>>8];
else
return bytemsb[v];
}
/* Ceiling of log base 2 */
static inline int log2c32 (u_int32_t) __attribute__ ((const));
static inline int
log2c32 (u_int32_t v)
{
return v ? (int) fls32 (v - 1) : -1;
}
static inline u_int fls64 (u_int64_t) __attribute__ ((const));
static inline u_int
fls64 (u_int64_t v)
{
u_int32_t h;
if ((h = v >> 32))
return 32 + fls32 (h);
else
return fls32 ((u_int32_t) v);
}
static inline int log2c64 (u_int64_t) __attribute__ ((const));
static inline int
log2c64 (u_int64_t v)
{
return v ? (int) fls64 (v - 1) : -1;
}
#define fls(v) (sizeof (v) > 4 ? fls64 (v) : fls32 (v))
#define log2c(v) (sizeof (v) > 4 ? log2c64 (v) : log2c32 (v))
/*
* For symmetry, a 64-bit find first set, "ffs," that finds the least
* significant 1 bit in a word.
*/
EXTERN_C const char bytelsb[];
static inline u_int
ffs32 (u_int32_t v)
{
if (v & 0xffff) {
if (int vv = v & 0xff)
return bytelsb[vv];
else
return 8 + bytelsb[v >> 8 & 0xff];
}
else if (int vv = v & 0xff0000)
return 16 + bytelsb[vv >> 16];
else if (v)
return 24 + bytelsb[v >> 24 & 0xff];
else
return 0;
}
static inline u_int
ffs64 (u_int64_t v)
{
u_int32_t l;
if ((l = v & 0xffffffff))
return fls32 (l);
else if ((l = v >> 32))
return 32 + fls32 (l);
else
return 0;
}
#define ffs(v) (sizeof (v) > 4 ? ffs64 (v) : ffs32 (v))
#undef EXTERN_C
#endif /* _MSB_H_ */
|
