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
52xcb_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
73xcb_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
98xcb_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
115xcb_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
133xcb_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
156xcb_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
175xcb_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
200xcb_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__ */
213