1 /*
2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU)
3 * Licensed under the Mulan PSL v2.
4 * You can use this software according to the terms and conditions of the Mulan PSL v2.
5 * You may obtain a copy of Mulan PSL v2 at:
6 * http://license.coscl.org.cn/MulanPSL2
7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
9 * PURPOSE.
10 * See the Mulan PSL v2 for more details.
11 */
12 #ifndef COMMON_BITOPS_H
13 #define COMMON_BITOPS_H
14
15 #define BITS_PER_BYTE 8
16 #define BITS_PER_INT (sizeof(unsigned int) * BITS_PER_BYTE)
17 #define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)
18 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG)
19 #define GENMASK_ULL(h, l) \
20 (((~0ULL) - (1ULL << (l)) + 1) & (~0ULL >> (64 - 1 - (h))))
21
22 #define get_bit_in_slot(u64slot, bit) ((u64slot) & (1UL << (bit)))
23
24 #define clear_bit_in_slot(u64slot, bit) \
25 ((u64slot) = (u64slot) & ~(1UL << (bit)))
26
27 #define set_bit_in_slot(u64slot, bit) ((u64slot) = (u64slot) | (1UL << (bit)))
28
29 /* set No'nr bit to 1 in slot pointed by p */
set_bit(unsigned int nr,volatile unsigned long * p)30 static inline void set_bit(unsigned int nr, volatile unsigned long *p)
31 {
32 unsigned nlongs = nr / BITS_PER_LONG;
33 unsigned ilongs = nr % BITS_PER_LONG;
34 p[nlongs] |= 1UL << ilongs;
35 }
36
37 /* get No'nr bit in slot pointed by p */
get_bit(unsigned int nr,volatile unsigned long * p)38 static inline int get_bit(unsigned int nr, volatile unsigned long *p)
39 {
40 unsigned nlongs = nr / BITS_PER_LONG;
41 unsigned ilongs = nr % BITS_PER_LONG;
42 return (p[nlongs] >> ilongs) & 0x1;
43 }
44
45 /* clear No'nr bit in slot pointed by p */
clear_bit(unsigned int nr,volatile unsigned long * p)46 static inline void clear_bit(unsigned int nr, volatile unsigned long *p)
47 {
48 unsigned nlongs = nr / BITS_PER_LONG;
49 unsigned ilongs = nr % BITS_PER_LONG;
50 p[nlongs] &= ~(1UL << ilongs);
51 }
52
53 /* return the first one bit start from the lowest bit */
ctzl(unsigned long x)54 static inline int ctzl(unsigned long x)
55 {
56 return x == 0 ? BITS_PER_LONG : __builtin_ctzl(x);
57 }
58
59 /* return the first one bit start from the highest bit */
bsr(unsigned int x)60 static inline int bsr(unsigned int x)
61 {
62 #ifndef CHCORE_ARCH_RISCV64
63 return BITS_PER_INT - 1 - __builtin_clz(x);
64 #else
65
66 int i;
67 for (i = BITS_PER_INT - 1; !(x & BIT(i)); i--)
68 ;
69 return i;
70 #endif
71 }
72
find_next_bit_helper(unsigned long * p,unsigned long size,unsigned long start,int invert)73 static inline int find_next_bit_helper(unsigned long *p, unsigned long size,
74 unsigned long start, int invert)
75 {
76 long cur_elem_index, cur_bit, max_elem_index, max_bit, cur_bit_value,
77 res = 0;
78
79 max_elem_index = (size - 1) / BITS_PER_LONG;
80 cur_elem_index = start / BITS_PER_LONG;
81 cur_bit = start % BITS_PER_LONG;
82 res = start;
83
84 while (cur_elem_index <= max_elem_index) {
85 if (cur_elem_index < max_elem_index)
86 max_bit = BITS_PER_LONG - 1;
87 else
88 max_bit = (size - 1) % BITS_PER_LONG;
89 for (; cur_bit <= max_bit; cur_bit++, res++) {
90 cur_bit_value = get_bit_in_slot(p[cur_elem_index], cur_bit);
91 if (invert ? !cur_bit_value : cur_bit_value)
92 return res;
93 }
94 cur_elem_index++;
95 cur_bit = 0;
96 }
97 return size;
98 }
99
100 /*
101 * From lowest bit side, starting from 'start',
102 * this function find the first zero bit of the slot pointed by p.
103 */
find_next_zero_bit(unsigned long * p,unsigned long size,unsigned long start)104 static inline int find_next_zero_bit(unsigned long *p, unsigned long size,
105 unsigned long start)
106 {
107 return find_next_bit_helper(p, size, start, 1);
108 }
109
110 /*
111 * From lowest bit side, starting from 'start',
112 * this function find the first bit of the slot pointed by p.
113 */
find_next_bit(unsigned long * p,unsigned long size,unsigned long start)114 static inline int find_next_bit(unsigned long *p, unsigned long size,
115 unsigned long start)
116 {
117 return find_next_bit_helper(p, size, start, 0);
118 }
119
120 /* From the first 1 bit to the last 1 bit in slot pointed by addr */
121 #define for_each_set_bit(pos, addr, size) \
122 for ((pos) = find_next_bit((addr), (size), 0); (pos) < (size); \
123 (pos) = find_next_bit((addr), (size), (pos) + 1))
124
125 #endif /* COMMON_BITOPS_H */