![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to _tricks.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / f / usr / include / common|
Return to _tricks.h CVS log | Up to [MW Coherent from dump] / coherent / f / usr / include / common |
1.1 root 1: #ifndef __COMMON__TRICKS_H__
2: #define __COMMON__TRICKS_H__
3:
4: /*
5: * This file contains macro-definitions for a number of frequently-
6: * rediscovered fundamental tricks from the field of radix-2 arithmetic
7: * and the properties of Standard C.
8: *
9: * These include: discovering whether a number is a power of two, finding
10: * the number of the least-significant set bit in an integer, finding the
11: * number of the most-significant set bit in an integer, positive-integer
12: * division that rounds upward, and so forth.
13: *
14: * The majority of the hacks given here are only defined on unsigned
15: * arguments. Wherever appropriate, factors such as 0U or 1U are used to
16: * encourage the system to coerce the result to an unsigned type. However,
17: * while using 0UL or 1UL would guarantee this, we use 0U and 1U to allow
18: * the operation to potentially be performed in as narrow an arithmetic
19: * mode as possible.
20: *
21: * We have some special motives for using integral operand conversions in
22: * this way rather than casts; not only can we be polymorphic, but we gain
23: * the even greater advantage of keeping the expansions as integral constant
24: * expressions suitable for evaluation in #if-expressions.
25: *
26: * In order to be flexible in the way we deal with the non-polymorphic
27: * macros, we need data like that in <limits.h>. We get this information
28: * from <common/_limits.h> so that we don't export stuff into the user
29: * namespace.
30: */
31:
32: #include <common/feature.h>
33: #include <common/_limits.h>
34:
35: /*
36: * Since many of these hacks only work for special operand ranges, we allow
37: * users the ability to selectively enable paranoid debugging; if a macro with
38: * the name _TRICKS_ASSERT () is defined, we call it up with an argument that
39: * is a predicate we insist on being true; don't forget that like the real-
40: * life assert () in <assert.h>, this must evaluate to a void expression!
41: *
42: * Note that many compilers won't accept expressions with commas, casts, or
43: * function calls in the unevaluated arm of a ternary with constant condition
44: * in a place where an integral constant expression is valid. To satisfy them,
45: * you can skip the assertions in places where the constants are by using the
46: * ..._CONST () versions of the tricks. Not many compilers do that, but you
47: * can get unlucky.
48: *
49: * Making the distinction between true-constant and possibly non-constant
50: * versions of the tricks may permit some special hacks in some cases for the
51: * non-constant versions.
52: */
53:
54: #ifndef _TRICKS_ASSERT
55: # define _TRICKS_ASSERT(pred) ((void) 0)
56: #endif
57:
58:
59: /*
60: * Is a number a power of two? This macro determines this, and should work
61: * for numbers of any unsigned type. Users are cautioned to avoid passing
62: * values of signed type to this macro, because then the result may depend
63: * on the underlying machine representation of negative numbers. While twos-
64: * complement machines are very common, they are not universal!
65: */
66:
67: #define __IS_POWER_OF_TWO(an_integer) \
68: ((((an_integer) - 1U) & (an_integer)) == 0)
69:
70:
71: /*
72: * Divide, with any non-zero remainder causing the result to be rounded to
73: * the next highest integer, as opposed to the default unsigned rounding
74: * mode of round-towards-zero. Users are cautioned that this technique does
75: * not apply to signed integers, because implementations have the freedom to
76: * use a rounding mode there that suits the properties of their signed-
77: * integer representation.
78: *
79: * Furthermore, users should be aware that this technique can fail in a most
80: * disastrous manner if (numerator - 1U + denominator) overflows the chosen
81: * representation. In this case, users should use div () or ldiv () and
82: * inspect the remainder to perform the rounding.
83: */
84:
85: #define __DIVIDE_ROUNDUP_CONST(numerator, denominator) \
86: (((numerator) - 1U + (denominator)) / (denominator))
87:
88: #define __DIVIDE_ROUNDUP(numerator, denominator) \
89: (_TRICKS_ASSERT ((numerator) - 1U + (denominator) >= (numerator)), \
90: __DIVIDE_ROUNDUP_CONST (numerator, denominator))
91:
92:
93: /*
94: * Round a number up to being the nearest multiple of some other number. Here
95: * we are careful to avoid overflow wherever possible, but as above overflow
96: * can happen if (n - 1U + mult) overflows. The number we want to reach a
97: * multiple of is almost always an integral constant, so we could look for
98: * that special case to simplify the arithmetic performed in a machine-
99: * independent way... however, GCC is smart enough to do this by itself, so
100: * if you have a dumb compiler add in
101: * __IS_POWER_OF_TWO (mult) ? ((n) - 1U + (mult) & ~ (mult)) :
102: * to the macros below.
103: */
104:
105: #define __ROUND_UP_TO_MULTIPLE_CONST(n,mult) \
106: (__DIVIDE_ROUNDUP_CONST (n, mult) * (mult))
107:
108: #define __ROUND_UP_TO_MULTIPLE(n,mult) \
109: (__DIVIDE_ROUNDUP (n, mult) * (mult))
110:
111:
112: /*
113: * Locate the least-significant bit set within an integer, assuming that one
114: * exists. The existence test has been left out because it is trivial and it
115: * may be more efficently coded elsewhere... the other problem is the choice
116: * of what value to return in this case. Since these macros are aimed at
117: * speed, we punt this problem up to the caller.
118: *
119: * Since these macros involve lots of fixed constants, we provide a version
120: * parameterised for each unsigned type.
121: *
122: * Note that for the portable versions, extra bits outside the defined size
123: * are not considered; be warned that this is not part of the specification,
124: * so our paranoia checks look to see that the extra bits are all zero, so
125: * that maximum freedom is given to the assembly-language versions to be
126: * fast.
127: */
128:
129: #define __LEAST_BIT_8_CONST(bit_mask) \
130: ((((bit_mask) & 0x0FU) == 0 ? 4 : 0) + \
131: (((bit_mask) & 0x33U) == 0 ? 2 : 0) + \
132: (((bit_mask) & 0x55U) == 0 ? 1 : 0))
133:
134: #define __LEAST_BIT_16_CONST(bit_mask) \
135: ((((bit_mask) & 0x00FFU) == 0 ? 8 : 0) + \
136: (((bit_mask) & 0x0F0FU) == 0 ? 4 : 0) + \
137: (((bit_mask) & 0x3333U) == 0 ? 2 : 0) + \
138: (((bit_mask) & 0x5555U) == 0 ? 1 : 0))
139:
140: #define __LEAST_BIT_32_CONST(bit_mask) \
141: ((((bit_mask) & 0x0000FFFFUL) == 0 ? 16 : 0) + \
142: (((bit_mask) & 0x00FF00FFUL) == 0 ? 8 : 0) + \
143: (((bit_mask) & 0x0F0F0F0FUL) == 0 ? 4 : 0) + \
144: (((bit_mask) & 0x33333333UL) == 0 ? 2 : 0) + \
145: (((bit_mask) & 0x55555555UL) == 0 ? 1 : 0))
146:
147: #define __MOST_BIT_8_CONST(bit_mask) \
148: ((((bit_mask) & 0xF0U) != 0 ? 4 : 0) + \
149: (((bit_mask) & 0xCCU) != 0 ? 2 : 0) + \
150: (((bit_mask) & 0xAAU) != 0 ? 1 : 0))
151:
152: #define __MOST_BIT_16_CONST(bit_mask) \
153: ((((bit_mask) & 0xFF00U) != 0 ? 8 : 0) + \
154: (((bit_mask) & 0xF0F0U) != 0 ? 4 : 0) + \
155: (((bit_mask) & 0xCCCCU) != 0 ? 2 : 0) + \
156: (((bit_mask) & 0xAAAAU) != 0 ? 1 : 0))
157:
158: #define __MOST_BIT_32_CONST(bit_mask) \
159: ((((bit_mask) & 0xFFFF0000UL) != 0 ? 16 : 0) + \
160: (((bit_mask) & 0xFF00FF00UL) != 0 ? 8 : 0) + \
161: (((bit_mask) & 0xF0F0F0F0UL) != 0 ? 4 : 0) + \
162: (((bit_mask) & 0xCCCCCCCCUL) != 0 ? 2 : 0) + \
163: (((bit_mask) & 0xAAAAAAAAUL) != 0 ? 1 : 0))
164:
165: #define __LEAST_BIT_8(bit_mask) \
166: (_TRICKS_ASSERT (((bit_mask) & 0xFFU) != 0), \
167: _TRICKS_ASSERT (((bit_mask) & ~ 0xFFU) == 0), \
168: __LEAST_BIT_8_CONST (bit_mask))
169:
170: #define __LEAST_BIT_16(bit_mask) \
171: (_TRICKS_ASSERT (((bit_mask) & 0xFFFFU) != 0), \
172: _TRICKS_ASSERT (((bit_mask) & ~ 0xFFFFU) == 0), \
173: __LEAST_BIT_16_CONST (bit_mask))
174:
175: #define __LEAST_BIT_32(bit_mask) \
176: (_TRICKS_ASSERT ((bit_mask) != 0), \
177: __LEAST_BIT_32_CONST (bit_mask))
178:
179: #define __MOST_BIT_8(bit_mask) \
180: (_TRICKS_ASSERT (((bit_mask) & 0xFFU) != 0), \
181: _TRICKS_ASSERT (((bit_mask) & ~ 0xFFU) == 0), \
182: __MOST_BIT_8_CONST (bit_mask))
183:
184: #define __MOST_BIT_16(bit_mask) \
185: (_TRICKS_ASSERT (((bit_mask) & 0xFFFFU) != 0), \
186: _TRICKS_ASSERT (((bit_mask) & ~ 0xFFFFU) == 0), \
187: __MOST_BIT_16_CONST (bit_mask))
188:
189: #define __MOST_BIT_32(bit_mask) \
190: (_TRICKS_ASSERT ((bit_mask) != 0), \
191: __MOST_BIT_32_CONST (bit_mask))
192:
193: #if __GNUC__ && _I386
194:
195: /*
196: * For the speed-obsessed, here are in-line versions for GCC on Intel i386/
197: * i486 processors.
198: */
199:
200: #if __CHAR_BIT != 8 || __SHRT_BIT != 16 || __INT_BIT != 32 || \
201: __LONG_BIT != 32
202: # error Do you *really* have an i386/i486 system?
203: #endif
204:
205: #include <common/ccompat.h>
206: #include <common/xdebug.h>
207: #include <common/__types.h>
208:
209: __LOCAL__ __INLINE__ __uint_t (__LEAST_BIT_8) (__ulong_t _bit_mask) {
210: int _result;
211: _TRICKS_ASSERT ((_bit_mask & 0xFFU) != 0);
212: _TRICKS_ASSERT ((_bit_mask & ~ 0xFFU) == 0);
213: __NON_ISO (asm) ("bsf %1,%0" : "=r" (_result) :
214: "g" (_bit_mask));
215: return _result;
216: }
217:
218: __LOCAL__ __INLINE__ __uint_t (__LEAST_BIT_16) (__ulong_t _bit_mask) {
219: int _result;
220: _TRICKS_ASSERT ((_bit_mask & 0xFFFFU) != 0);
221: _TRICKS_ASSERT ((_bit_mask & ~ 0xFFFFU) == 0);
222: __NON_ISO (asm) ("bsf %1,%0" : "=r" (_result) :
223: "g" (_bit_mask));
224: return _result;
225: }
226:
227: __LOCAL__ __INLINE__ __uint_t (__LEAST_BIT_32) (__ulong_t _bit_mask) {
228: int _result;
229: _TRICKS_ASSERT (_bit_mask != 0);
230: __NON_ISO (asm) ("bsf %1,%0" : "=r" (_result) :
231: "g" (_bit_mask));
232: return _result;
233: }
234:
235: __LOCAL__ __INLINE__ __uint_t (__MOST_BIT_8) (__ulong_t _bit_mask) {
236: int _result;
237: _TRICKS_ASSERT ((_bit_mask & 0xFFU) != 0);
238: _TRICKS_ASSERT ((_bit_mask & ~ 0xFFU) == 0);
239: __NON_ISO (asm) ("bsr %1,%0" : "=r" (_result) :
240: "g" (_bit_mask));
241: return _result;
242: }
243:
244: __LOCAL__ __INLINE__ __uint_t (__MOST_BIT_16) (__ulong_t _bit_mask) {
245: int _result;
246: _TRICKS_ASSERT ((_bit_mask & 0xFFFFU) != 0);
247: _TRICKS_ASSERT ((_bit_mask & ~ 0xFFFFU) == 0);
248: __NON_ISO (asm) ("bsr %1,%0" : "=r" (_result) :
249: "g" (_bit_mask));
250: return _result;
251: }
252:
253: __LOCAL__ __INLINE__ __uint_t (__MOST_BIT_32) (__ulong_t _bit_mask) {
254: int _result;
255: _TRICKS_ASSERT (_bit_mask != 0);
256: __NON_ISO (asm) ("bsr %1,%0" : "=r" (_result) :
257: "g" (_bit_mask));
258: return _result;
259: }
260:
261: /*
262: * Make the portable versions go away... we leave them around up to this point
263: * for those people that want to check that the fast versions really work :-)
264: */
265:
266: #undef __LEAST_BIT_8
267: #undef __LEAST_BIT_16
268: #undef __LEAST_BIT_32
269: #undef __MOST_BIT_8
270: #undef __MOST_BIT_16
271: #undef __MOST_BIT_32
272:
273: #endif /* __GNUC__ && _I386 */
274:
275:
276: /*
277: * Use the combined abilities of __CONCAT () and rescanning with the type ->
278: * size macros from <common/_limits.h> to simplify the creation of different
279: * versions of the scanning macros.
280: */
281:
282: #define __SCAN_BIT_CONST(bit_mask, direction, type) \
283: __CONCAT5 (__, direction,_BIT_, type, _CONST) (bit_mask)
284:
285: #define __SCAN_BIT(bit_mask, direction, type) \
286: __CONCAT4 (__, direction,_BIT_, type) (bit_mask)
287:
288: #define __LEAST_BIT_UCHAR_CONST(bit_mask) \
289: __SCAN_BIT_CONST (bit_mask, LEAST, __CHAR)
290: #define __LEAST_BIT_USHRT_CONST(bit_mask) \
291: __SCAN_BIT_CONST (bit_mask, LEAST, __SHORT)
292: #define __LEAST_BIT_UINT_CONST(bit_mask) \
293: __SCAN_BIT_CONST (bit_mask, LEAST, __INT)
294: #define __LEAST_BIT_ULONG_CONST(bit_mask) \
295: __SCAN_BIT_CONST (bit_mask, LEAST, __LONG)
296:
297: #define __MOST_BIT_UCHAR_CONST(bit_mask) \
298: __SCAN_BIT_CONST (bit_mask, MOST, __CHAR)
299: #define __MOST_BIT_USHRT_CONST(bit_mask) \
300: __SCAN_BIT_CONST (bit_mask, MOST, __SHORT)
301: #define __MOST_BIT_UINT_CONST(bit_mask) \
302: __SCAN_BIT_CONST (bit_mask, MOST, __INT)
303: #define __MOST_BIT_ULONG_CONST(bit_mask) \
304: __SCAN_BIT_CONST (bit_mask, MOST, __LONG)
305:
306: #define __LEAST_BIT_UCHAR(bit_mask) __SCAN_BIT (bit_mask, LEAST, __CHAR)
307: #define __LEAST_BIT_USHRT(bit_mask) __SCAN_BIT (bit_mask, LEAST, __SHORT)
308: #define __LEAST_BIT_UINT(bit_mask) __SCAN_BIT (bit_mask, LEAST, __INT)
309: #define __LEAST_BIT_ULONG(bit_mask) __SCAN_BIT (bit_mask, LEAST, __LONG)
310:
311: #define __MOST_BIT_UCHAR(bit_mask) __SCAN_BIT (bit_mask, MOST, __CHAR)
312: #define __MOST_BIT_USHRT(bit_mask) __SCAN_BIT (bit_mask, MOST, __SHORT)
313: #define __MOST_BIT_UINT(bit_mask) __SCAN_BIT (bit_mask, MOST, __INT)
314: #define __MOST_BIT_ULONG(bit_mask) __SCAN_BIT (bit_mask, MOST, __LONG)
315:
316:
317: /*
318: * This is not really a trick, it's too obvious. However, it is so frequently
319: * used that we keep it around.
320: */
321:
322: #define __ARRAY_LENGTH(array_type_or_object) \
323: (sizeof (array_type_or_object) / \
324: sizeof ((array_type_or_object) [0]))
325:
326:
327: /*
328: * Add one unsigned integer to another, producing an unsigned result that does
329: * not overflow normally but which pegs itself at the value of UINT_MAX. Plus,
330: * we define subtraction of one unsigned integer from another with no
331: * underflow, the result sticking at 0.
332: */
333:
334: #define __ADD_UINT_WITH_MAX(addend,augend) \
335: ((addend) + 0U + (augend) < (addend) ? __UINT_MAX : \
336: (addend) + 0U + (augend))
337:
338: #define __SUB_UINT_WITH_MIN(minuend,subtrahend) \
339: ((minuend) + 0U - (subtrahend) > (minuend) ? 0U : \
340: (minuend) + 0U - (subtrahend))
341:
342: #if __GNUC__ && _I386
343:
344: /*
345: * As above, but we cheat by using "subtract with borrow" when we know the
346: * carry flag is set as a very cheap way of getting a -1 into the result.
347: */
348:
349: __LOCAL__ __INLINE__
350: __uint_t (__ADD_UINT_WITH_MAX) (__uint_t _addend, __uint_t _augend) {
351: __uint_t _result;
352: __NON_ISO (asm) ("addl %2, %0\n"
353: "jnc Ltricks_addu\n"
354: "sbbl %0, %0\n"
355: "Ltricks_addu:\n" :
356: "=r" (_result) : "0" (_addend), "g" (_augend));
357: return _result;
358: }
359:
360: __LOCAL__ __INLINE__
361: __uint_t (__SUB_UINT_WITH_MIN) (__uint_t _minuend, __uint_t _subtrahend) {
362: __uint_t _result;
363: __NON_ISO (asm) ("subl %2, %0\n"
364: "jnc Ltricks_subu\n"
365: "subl %0, %0\n"
366: "Ltricks_subu:" :
367: "=r" (_result) : "0" (_minuend), "g" (_subtrahend));
368: return _result;
369: }
370:
371: #undef __ADD_UINT_WITH_MAX
372: #undef __SUB_UINT_WITH_MIN
373:
374: #endif /* __GNUC__ && _I386 */
375:
376: #endif /* ! defined (__COMMON__TRICKS_H__) */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.