Return to _tricks.h CVS log

Up to [MW Coherent from dump] / coherent / f / usr / include / common

Annotation of coherent/f/usr/include/common/_tricks.h, revision 1.1

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.