1 /* -*-c++-*- */
2 /* $Id$ */
3
4 /*
5 *
6 * Copyright (C) 1998 David Mazieres (dm@uun.org)
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License as
10 * published by the Free Software Foundation; either version 2, or (at
11 * your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
21 * USA
22 *
23 */
24
25 #ifndef _MSB_H_
26 #define _MSB_H_ 1
27
28 #include "sysconf.h"
29
30 #ifdef __cplusplus
31 #define EXTERN_C extern "C"
32 #else /* !__cplusplus */
33 #define EXTERN_C extern
34 #endif /* !__cplusplus */
35
36 /*
37 * Routines for calculating the most significant bit of an integer.
38 */
39
40 EXTERN_C const char bytemsb[];
41
42 /* Find last set (most significant bit) */
43 static inline u_int fls32 (u_int32_t) __attribute__ ((const));
44 static inline u_int
fls32(u_int32_t v)45 fls32 (u_int32_t v)
46 {
47 if (v & 0xffff0000) {
48 if (v & 0xff000000)
49 return 24 + bytemsb[v>>24];
50 else
51 return 16 + bytemsb[v>>16];
52 }
53 if (v & 0x0000ff00)
54 return 8 + bytemsb[v>>8];
55 else
56 return bytemsb[v];
57 }
58
59 /* Ceiling of log base 2 */
60 static inline int log2c32 (u_int32_t) __attribute__ ((const));
61 static inline int
log2c32(u_int32_t v)62 log2c32 (u_int32_t v)
63 {
64 return v ? (int) fls32 (v - 1) : -1;
65 }
66
67 static inline u_int fls64 (u_int64_t) __attribute__ ((const));
68 static inline u_int
fls64(u_int64_t v)69 fls64 (u_int64_t v)
70 {
71 u_int32_t h;
72 if ((h = v >> 32))
73 return 32 + fls32 (h);
74 else
75 return fls32 ((u_int32_t) v);
76 }
77
78 static inline int log2c64 (u_int64_t) __attribute__ ((const));
79 static inline int
log2c64(u_int64_t v)80 log2c64 (u_int64_t v)
81 {
82 return v ? (int) fls64 (v - 1) : -1;
83 }
84
85 #define fls(v) (sizeof (v) > 4 ? fls64 (v) : fls32 (v))
86 #define log2c(v) (sizeof (v) > 4 ? log2c64 (v) : log2c32 (v))
87
88 /*
89 * For symmetry, a 64-bit find first set, "ffs," that finds the least
90 * significant 1 bit in a word.
91 */
92
93 EXTERN_C const char bytelsb[];
94
95 static inline u_int
ffs32(u_int32_t v)96 ffs32 (u_int32_t v)
97 {
98 if (v & 0xffff) {
99 if (int vv = v & 0xff)
100 return bytelsb[vv];
101 else
102 return 8 + bytelsb[v >> 8 & 0xff];
103 }
104 else if (int vv = v & 0xff0000)
105 return 16 + bytelsb[vv >> 16];
106 else if (v)
107 return 24 + bytelsb[v >> 24 & 0xff];
108 else
109 return 0;
110 }
111
112 static inline u_int
ffs64(u_int64_t v)113 ffs64 (u_int64_t v)
114 {
115 u_int32_t l;
116 if ((l = v & 0xffffffff))
117 return fls32 (l);
118 else if ((l = v >> 32))
119 return 32 + fls32 (l);
120 else
121 return 0;
122 }
123
124 #define ffs(v) (sizeof (v) > 4 ? ffs64 (v) : ffs32 (v))
125
126 #undef EXTERN_C
127
128 #endif /* _MSB_H_ */
129