src/xcb_bitops.h

   1 #ifndef __XCB_BITOPS_H__
   2 #define __XCB_BITOPS_H__
   3
   4 /* Copyright (C) 2007 Bart Massey
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the "Software"),
   8  * to deal in the Software without restriction, including without limitation
   9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  10  * and/or sell copies of the Software, and to permit persons to whom the
  11  * Software is furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in
  14  * all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22  *
  23  * Except as contained in this notice, the names of the authors or their
  24  * institutions shall not be used in advertising or otherwise to promote the
  25  * sale, use or other dealings in this Software without prior written
  26  * authorization from the authors.
  27  */
  28
  29 #include <assert.h>
  30 #include <inttypes.h>
  31 #include <X11/Xfuncproto.h>
  32
  33 /**
  34  * @defgroup xcb__bitops XCB Bit Operations
  35  *
  36  * Inline functions for common bit ops used in XCB and elsewhere.
  37  *
  38  * @{
  39  */
  40
  41
  42 /**
  43  * Create a low-order bitmask.
  44  * @param n Mask size.
  45  * @return Mask.
  46  *
  47  * Create a bitmask with the lower @p n bits set and the
  48  * rest of the word clear.
  49  * @ingroup xcb__bitops
  50  */
  51 _X_INLINE static uint32_t
  52 xcb_mask(uint32_t n)
  53 {
  54     return n == 32 ? ~0 : (1 << n) - 1;
  55 }
  56
  57
  58 /**
  59  * Population count.
  60  * @param n Integer representing a bitset.
  61  * @return Number of 1 bits in the bitset.
  62  *
  63  * This is a reasonably fast algorithm for counting the bits
  64  * in a 32-bit word.  Currently a classic binary
  65  * divide-and-conquer popcount: popcount_2() from
  66  * http://en.wikipedia.org/wiki/Hamming_weight.
  67  * @ingroup xcb__bitops
  68  */
  69
  70
  71 /* 15 ops, 3 long immediates, 14 stages, 9 alu ops, 9 alu stages */
  72 _X_INLINE static uint32_t
  73 xcb_popcount(uint32_t x)
  74 {
  75     uint32_t m1 = 0x55555555;
  76     uint32_t m2 = 0x33333333;
  77     uint32_t m4 = 0x0f0f0f0f;
  78     x -= (x >> 1) & m1;
  79     x = (x & m2) + ((x >> 2) & m2);
  80     x = (x + (x >> 4)) & m4;
  81     x += x >> 8;
  82     return (x + (x >> 16)) & 0x3f;
  83 }
  84
  85
  86 /**
  87  * Round up to the next power-of-two unit size.
  88  * @param base Number to be rounded up.
  89  * @param pad Multiple to be rounded to; must be a power of two.
  90  * @return Rounded-up number.
  91  *
  92  * Rounds @p base up to a multiple of @p pad, where @p pad
  93  * is a power of two.  The more general case is handled by
  94  * xcb_roundup().
  95  * @ingroup xcb__bitops
  96  */
  97 _X_INLINE static uint32_t
  98 xcb_roundup_2 (uint32_t base, uint32_t pad)
  99 {
 100     return (base + pad - 1) & -pad;
 101 }
 102
 103 /**
 104  * Round down to the next power-of-two unit size.
 105  * @param base Number to be rounded down.
 106  * @param pad Multiple to be rounded to; must be a power of two.
 107  * @return Rounded-down number.
 108  *
 109  * Rounds @p base down to a multiple of @p pad, where @p pad
 110  * is a power of two.  The more general case is handled by
 111  * xcb_rounddown().
 112  * @ingroup xcb__bitops
 113  */
 114 _X_INLINE static uint32_t
 115 xcb_rounddown_2 (uint32_t base, uint32_t pad)
 116 {
 117     return base & -pad;
 118 }
 119
 120 /**
 121  * Round up to the next unit size.
 122  * @param base Number to be rounded up.
 123  * @param pad Multiple to be rounded to.
 124  * @return Rounded-up number.
 125  *
 126  * This is a general routine for rounding @p base up
 127  * to a multiple of @p pad.  If you know that @p pad
 128  * is a power of two, you should probably call xcb_roundup_2()
 129  * instead.
 130  * @ingroup xcb__bitops
 131  */
 132 _X_INLINE static uint32_t
 133 xcb_roundup (uint32_t base, uint32_t pad)
 134 {
 135     uint32_t b = base + pad - 1;
 136     /* faster if pad is a power of two */
 137     if (((pad - 1) & pad) == 0)
 138         return b & -pad;
 139     return b - b % pad;
 140 }
 141
 142
 143 /**
 144  * Round down to the next unit size.
 145  * @param base Number to be rounded down.
 146  * @param pad Multiple to be rounded to.
 147  * @return Rounded-down number.
 148  *
 149  * This is a general routine for rounding @p base down
 150  * to a multiple of @p pad.  If you know that @p pad
 151  * is a power of two, you should probably call xcb_rounddown_2()
 152  * instead.
 153  * @ingroup xcb__bitops
 154  */
 155 _X_INLINE static uint32_t
 156 xcb_rounddown (uint32_t base, uint32_t pad)
 157 {
 158     /* faster if pad is a power of two */
 159     if (((pad - 1) & pad) == 0)
 160         return base & -pad;
 161     return base - base % pad;
 162 }
 163
 164
 165 /**
 166  * Reverse bits of word.
 167  * @param x Target word.
 168  * @param n Number of low-order bits to reverse.
 169  * @return Word with low @p n bits reversed, all others 0.
 170  *
 171  * Reverses the bottom @p n bits of @p x.
 172  * @ingroup xcb__bitops
 173  */
 174 _X_INLINE static uint32_t
 175 xcb_bit_reverse(uint32_t x, uint8_t n) {
 176     uint32_t m1 = 0x00ff00ff;
 177     uint32_t m2 = 0x0f0f0f0f;
 178     uint32_t m3 = 0x33333333;
 179     uint32_t m4 = 0x55555555;
 180     x = ((x << 16) | (x >> 16));
 181     x = ((x & m1) << 8) | ((x >> 8) & m1);
 182     x = ((x & m2) << 4) | ((x >> 4) & m2);
 183     x = ((x & m3) << 2) | ((x >> 2) & m3);
 184     x = ((x & m4) << 1) | ((x >> 1) & m4);
 185     x >>= 32 - n;
 186     return x;
 187 }
 188
 189
 190 /**
 191  * Host byte order.
 192  * @return The byte order of the host.
 193  *
 194  * Tests the host's byte order and returns either
 195  * XCB_IMAGE_ORDER_MSB_FIRST or XCB_IMAGE_ORDER_LSB_FIRST
 196  * as appropriate.
 197  * @ingroup xcb__bitops
 198  */
 199 _X_INLINE static xcb_image_order_t
 200 xcb_host_byte_order(void) {
 201   uint32_t           endian_test = 0x01020304;
 202
 203   switch (*(char *)&endian_test) {
 204   case 0x01:
 205       return XCB_IMAGE_ORDER_MSB_FIRST;
 206   case 0x04:
 207       return XCB_IMAGE_ORDER_LSB_FIRST;
 208   }
 209   assert(0);
 210 }
 211
 212 #endif /* __XCB_BITOPS_H__ */