include/xcb/xcb_bitops.h

0001 #ifndef __XCB_BITOPS_H__
0002 #define __XCB_BITOPS_H__
0003
0004 /* Copyright (C) 2007 Bart Massey
0005  *
0006  * Permission is hereby granted, free of charge, to any person obtaining a
0007  * copy of this software and associated documentation files (the "Software"),
0008  * to deal in the Software without restriction, including without limitation
0009  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
0010  * and/or sell copies of the Software, and to permit persons to whom the
0011  * Software is furnished to do so, subject to the following conditions:
0012  *
0013  * The above copyright notice and this permission notice shall be included in
0014  * all copies or substantial portions of the Software.
0015  *
0016  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0017  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0018  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0019  * AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
0020  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
0021  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
0022  *
0023  * Except as contained in this notice, the names of the authors or their
0024  * institutions shall not be used in advertising or otherwise to promote the
0025  * sale, use or other dealings in this Software without prior written
0026  * authorization from the authors.
0027  */
0028
0029 #include <assert.h>
0030 #include <inttypes.h>
0031 #include <X11/Xfuncproto.h>
0032
0033 /**
0034  * @defgroup xcb__bitops XCB Bit Operations
0035  *
0036  * Inline functions for common bit ops used in XCB and elsewhere.
0037  *
0038  * @{
0039  */
0040
0041
0042 /**
0043  * Create a low-order bitmask.
0044  * @param n Mask size.
0045  * @return Mask.
0046  *
0047  * Create a bitmask with the lower @p n bits set and the
0048  * rest of the word clear.
0049  * @ingroup xcb__bitops
0050  */
0051 _X_INLINE static uint32_t
0052 xcb_mask(uint32_t n)
0053 {
0054     return n == 32 ? ~0 : (1 << n) - 1;
0055 }
0056
0057
0058 /**
0059  * Population count.
0060  * @param n Integer representing a bitset.
0061  * @return Number of 1 bits in the bitset.
0062  *
0063  * This is a reasonably fast algorithm for counting the bits
0064  * in a 32-bit word.  Currently a classic binary
0065  * divide-and-conquer popcount: popcount_2() from
0066  * http://en.wikipedia.org/wiki/Hamming_weight.
0067  * @ingroup xcb__bitops
0068  */
0069
0070
0071 /* 15 ops, 3 long immediates, 14 stages, 9 alu ops, 9 alu stages */
0072 _X_INLINE static uint32_t
0073 xcb_popcount(uint32_t x)
0074 {
0075     uint32_t m1 = 0x55555555;
0076     uint32_t m2 = 0x33333333;
0077     uint32_t m4 = 0x0f0f0f0f;
0078     x -= (x >> 1) & m1;
0079     x = (x & m2) + ((x >> 2) & m2);
0080     x = (x + (x >> 4)) & m4;
0081     x += x >> 8;
0082     return (x + (x >> 16)) & 0x3f;
0083 }
0084
0085
0086 /**
0087  * Round up to the next power-of-two unit size.
0088  * @param base Number to be rounded up.
0089  * @param pad Multiple to be rounded to; must be a power of two.
0090  * @return Rounded-up number.
0091  *
0092  * Rounds @p base up to a multiple of @p pad, where @p pad
0093  * is a power of two.  The more general case is handled by
0094  * xcb_roundup().
0095  * @ingroup xcb__bitops
0096  */
0097 _X_INLINE static uint32_t
0098 xcb_roundup_2 (uint32_t base, uint32_t pad)
0099 {
0100     return (base + pad - 1) & -pad;
0101 }
0102
0103 /**
0104  * Round down to the next power-of-two unit size.
0105  * @param base Number to be rounded down.
0106  * @param pad Multiple to be rounded to; must be a power of two.
0107  * @return Rounded-down number.
0108  *
0109  * Rounds @p base down to a multiple of @p pad, where @p pad
0110  * is a power of two.  The more general case is handled by
0111  * xcb_rounddown().
0112  * @ingroup xcb__bitops
0113  */
0114 _X_INLINE static uint32_t
0115 xcb_rounddown_2 (uint32_t base, uint32_t pad)
0116 {
0117     return base & -pad;
0118 }
0119
0120 /**
0121  * Round up to the next unit size.
0122  * @param base Number to be rounded up.
0123  * @param pad Multiple to be rounded to.
0124  * @return Rounded-up number.
0125  *
0126  * This is a general routine for rounding @p base up
0127  * to a multiple of @p pad.  If you know that @p pad
0128  * is a power of two, you should probably call xcb_roundup_2()
0129  * instead.
0130  * @ingroup xcb__bitops
0131  */
0132 _X_INLINE static uint32_t
0133 xcb_roundup (uint32_t base, uint32_t pad)
0134 {
0135     uint32_t b = base + pad - 1;
0136     /* faster if pad is a power of two */
0137     if (((pad - 1) & pad) == 0)
0138     return b & -pad;
0139     return b - b % pad;
0140 }
0141
0142
0143 /**
0144  * Round down to the next unit size.
0145  * @param base Number to be rounded down.
0146  * @param pad Multiple to be rounded to.
0147  * @return Rounded-down number.
0148  *
0149  * This is a general routine for rounding @p base down
0150  * to a multiple of @p pad.  If you know that @p pad
0151  * is a power of two, you should probably call xcb_rounddown_2()
0152  * instead.
0153  * @ingroup xcb__bitops
0154  */
0155 _X_INLINE static uint32_t
0156 xcb_rounddown (uint32_t base, uint32_t pad)
0157 {
0158     /* faster if pad is a power of two */
0159     if (((pad - 1) & pad) == 0)
0160     return base & -pad;
0161     return base - base % pad;
0162 }
0163
0164
0165 /**
0166  * Reverse bits of word.
0167  * @param x Target word.
0168  * @param n Number of low-order bits to reverse.
0169  * @return Word with low @p n bits reversed, all others 0.
0170  *
0171  * Reverses the bottom @p n bits of @p x.
0172  * @ingroup xcb__bitops
0173  */
0174 _X_INLINE static uint32_t
0175 xcb_bit_reverse(uint32_t x, uint8_t n) {
0176     uint32_t m1 = 0x00ff00ff;
0177     uint32_t m2 = 0x0f0f0f0f;
0178     uint32_t m3 = 0x33333333;
0179     uint32_t m4 = 0x55555555;
0180     x = ((x << 16) | (x >> 16));
0181     x = ((x & m1) << 8) | ((x >> 8) & m1);
0182     x = ((x & m2) << 4) | ((x >> 4) & m2);
0183     x = ((x & m3) << 2) | ((x >> 2) & m3);
0184     x = ((x & m4) << 1) | ((x >> 1) & m4);
0185     x >>= 32 - n;
0186     return x;
0187 }
0188
0189
0190 /**
0191  * Host byte order.
0192  * @return The byte order of the host.
0193  *
0194  * Tests the host's byte order and returns either
0195  * XCB_IMAGE_ORDER_MSB_FIRST or XCB_IMAGE_ORDER_LSB_FIRST
0196  * as appropriate.
0197  * @ingroup xcb__bitops
0198  */
0199 _X_INLINE static xcb_image_order_t
0200 xcb_host_byte_order(void) {
0201   uint32_t           endian_test = 0x01020304;
0202
0203   switch (*(char *)&endian_test) {
0204   case 0x01:
0205       return XCB_IMAGE_ORDER_MSB_FIRST;
0206   case 0x04:
0207       return XCB_IMAGE_ORDER_LSB_FIRST;
0208   }
0209   assert(0);
0210 }
0211
0212 #endif /* __XCB_BITOPS_H__ */