1 /*
2  * Copyright (C) 2015-2017 Alibaba Group Holding Limited
3  */
4 
5 #ifndef K_BITMAP_H
6 #define K_BITMAP_H
7 
8 #ifdef __cplusplus
9 extern "C" {
10 #endif
11 
12 /** @addtogroup aos_rhino bitmap
13  *  Bit operation.
14  *
15  *  @{
16  */
17 
18 #define BITMAP_UNIT_SIZE    32U
19 #define BITMAP_UNIT_MASK    (BITMAP_UNIT_SIZE - 1)
20 #define BITMAP_UNIT_BITS    5U
21 
22 #define BITMAP_MASK(nr)     (1UL << (BITMAP_UNIT_MASK - ((nr) & BITMAP_UNIT_MASK)))
23 #define BITMAP_WORD(nr)     ((nr) >> BITMAP_UNIT_BITS)
24 
25 /**
26  * Count Leading Zeros (clz).
27  * Counts the number of zero bits preceding the most significant one bit.
28  *
29  * @param[in]  x  input unsigned int
30  *
31  * @return  0~32
32  */
krhino_clz32(uint32_t x)33 RHINO_INLINE uint8_t krhino_clz32(uint32_t x)
34 {
35     uint8_t n = 0;
36 
37     if (x == 0) {
38         return 32;
39     }
40 
41 #ifdef RHINO_BIT_CLZ
42     n = RHINO_BIT_CLZ(x);
43 #else
44     if ((x & 0XFFFF0000) == 0) {
45         x <<= 16;
46         n += 16;
47     }
48     if ((x & 0XFF000000) == 0) {
49         x <<= 8;
50         n += 8;
51     }
52     if ((x & 0XF0000000) == 0) {
53         x <<= 4;
54         n += 4;
55     }
56     if ((x & 0XC0000000) == 0) {
57         x <<= 2;
58         n += 2;
59     }
60     if ((x & 0X80000000) == 0) {
61         n += 1;
62     }
63 #endif
64 
65     return n;
66 }
67 
68 /**
69  * Count Trailing Zeros (ctz).
70  * Counts the number of zero bits succeeding the least significant one bit.
71  *
72  * @param[in]  x  input unsigned int
73  *
74  * @return  0~32
75  */
krhino_ctz32(uint32_t x)76 RHINO_INLINE uint8_t krhino_ctz32(uint32_t x)
77 {
78     uint8_t n = 0;
79 
80     if (x == 0) {
81         return 32;
82     }
83 
84 #ifdef RHINO_BIT_CTZ
85     n = RHINO_BIT_CTZ(x);
86 #else
87     if ((x & 0X0000FFFF) == 0) {
88         x >>= 16;
89         n += 16;
90     }
91     if ((x & 0X000000FF) == 0) {
92         x >>= 8;
93         n += 8;
94     }
95     if ((x & 0X0000000F) == 0) {
96         x >>= 4;
97         n += 4;
98     }
99     if ((x & 0X00000003) == 0) {
100         x >>= 2;
101         n += 2;
102     }
103     if ((x & 0X00000001) == 0) {
104         n += 1;
105     }
106 #endif
107 
108     return n;
109 }
110 
111 /**
112  * Set a bit of the bitmap for task priority.
113  *
114  * @param[in]  bitmap  pointer to the bitmap
115  * @param[in]  nr      position of the bitmap to set, from msb to lsb
116  *
117  * @return  no return
118  */
krhino_bitmap_set(uint32_t * bitmap,int32_t nr)119 RHINO_INLINE void krhino_bitmap_set(uint32_t *bitmap, int32_t nr)
120 {
121     bitmap[BITMAP_WORD(nr)] |= BITMAP_MASK(nr);
122 }
123 
124 /**
125  * Clear a bit of the bitmap for task priority.
126  *
127  * @param[in]  bitmap  pointer to the bitmap
128  * @param[in]  nr      position of the bitmap to clear
129  *
130  * @return  no return
131  */
krhino_bitmap_clear(uint32_t * bitmap,int32_t nr)132 RHINO_INLINE void krhino_bitmap_clear(uint32_t *bitmap, int32_t nr)
133 {
134     bitmap[BITMAP_WORD(nr)] &= ~BITMAP_MASK(nr);
135 }
136 
137 /**
138  * Find the first bit(1) of the bitmap.
139  *
140  * @param[in]  bitmap  pointer to the bitmap
141  *
142  * @return  the first bit position
143  */
krhino_bitmap_first(uint32_t * bitmap)144 RHINO_INLINE int32_t krhino_bitmap_first(uint32_t *bitmap)
145 {
146     int32_t  nr  = 0;
147 
148     while (*bitmap == 0UL) {
149         nr += BITMAP_UNIT_SIZE;
150         bitmap++;
151     }
152 
153     nr += krhino_clz32(*bitmap);
154 
155     return nr;
156 }
157 
158 /** @} */
159 
160 #ifdef __cplusplus
161 }
162 #endif
163 
164 #endif /* K_BITMAP_H */
165 
166