1 /*
2 * Copyright (c) 2008-2014 Travis Geiselbrecht
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files
6 * (the "Software"), to deal in the Software without restriction,
7 * including without limitation the rights to use, copy, modify, merge,
8 * publish, distribute, sublicense, and/or sell copies of the Software,
9 * and to permit persons to whom the Software is furnished to do so,
10 * subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 */
23 #ifndef __POW2_H
24 #define __POW2_H
25
26 #include <sys/types.h>
27 #include <stdbool.h>
28 #include <stdint.h>
29 #include <lk/compiler.h>
30
31 __BEGIN_CDECLS;
32
33 /* routines for dealing with power of 2 values for efficiency */
ispow2(uint val)34 static inline __ALWAYS_INLINE bool ispow2(uint val)
35 {
36 return ((val - 1) & val) == 0;
37 }
38
log2_uint(uint val)39 static inline __ALWAYS_INLINE uint log2_uint(uint val)
40 {
41 if (val == 0)
42 return 0; // undefined
43
44 return (sizeof(val) * 8) - 1 - __builtin_clz(val);
45 }
46
valpow2(uint valp2)47 static inline __ALWAYS_INLINE uint valpow2(uint valp2)
48 {
49 return 1U << valp2;
50 }
51
divpow2(uint val,uint divp2)52 static inline __ALWAYS_INLINE uint divpow2(uint val, uint divp2)
53 {
54 return val >> divp2;
55 }
56
modpow2(uint val,uint modp2)57 static inline __ALWAYS_INLINE uint modpow2(uint val, uint modp2)
58 {
59 return val & ((1UL << modp2) - 1);
60 }
61
62 // Cribbed from:
63 // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
round_up_pow2_u32(uint32_t v)64 static inline __ALWAYS_INLINE uint32_t round_up_pow2_u32(uint32_t v)
65 {
66 v--;
67 v |= v >> 1;
68 v |= v >> 2;
69 v |= v >> 4;
70 v |= v >> 8;
71 v |= v >> 16;
72 v++;
73 return v;
74 }
75
76 // expanded macro version of round_up_pow2_u32()
77 #define _ROUND_UP_POW2_U32(v) (1 + \
78 ((((((((v) | ((v) >> 16) | \
79 ((v) | ((v) >> 16) >> 8)) | \
80 (((v) | ((v) >> 16) | \
81 ((v) | ((v) >> 16) >> 8)) >> 4))) | \
82 (((((v) | ((v) >> 16) | \
83 ((v) | ((v) >> 16) >> 8)) | \
84 (((v) | ((v) >> 16) | \
85 ((v) | ((v) >> 16) >> 8)) >> 4))) >> 2))) | \
86 (((((((v) | ((v) >> 16) | \
87 ((v) | ((v) >> 16) >> 8)) | \
88 (((v) | ((v) >> 16) | \
89 ((v) | ((v) >> 16) >> 8)) >> 4))) | \
90 (((((v) | ((v) >> 16) | \
91 ((v) | ((v) >> 16) >> 8)) | \
92 (((v) | ((v) >> 16) | \
93 ((v) | ((v) >> 16) >> 8)) >> 4))) >> 2))) >> 1))))
94
95 #define ROUND_UP_POW2_U32(v) _ROUND_UP_POW2_U32((v)-1)
96
97 __END_CDECLS;
98
99 #endif
100
101