1 /*@ Bit operations. TODO asm optimizations
2 *
3 * Copyright (c) 2001 - 2020 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
4 * SPDX-License-Identifier: ISC
5 *
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18 #ifndef su_BITS_H
19 #define su_BITS_H
20 #include <su/code.h>
21 #define su_HEADER
22 #include <su/code-in.h>
23 C_DECL_BEGIN
24 #define su_BITS_ROUNDUP(BITS) (((BITS) + (su_UZ_BITS - 1)) & ~(su_UZ_BITS - 1))
25 #define su_BITS_TO_UZ(BITS) (su_BITS_ROUNDUP(BITS) / su_UZ_BITS)
26 #define su_BITS_WHICH_OFF(BIT) ((BIT) / su_UZ_BITS)
27 #define su_BITS_WHICH_BIT(BIT) ((BIT) & (su_UZ_BITS - 1))
28 #define su_BITS_TOP_OFF(BITS) (su_BITS_TO_UZ(BITS) - 1)
29 #define su_BITS_TOP_BITNO(BITS) (su_UZ_BITS - (su_BITS_ROUNDUP(BITS) - (BITS)))
30 #define su_BITS_TOP_MASK(BITS) (su_UZ_MAX >> (su_BITS_ROUNDUP(BITS) - (BITS)))
31 #define su_BITS_RANGE_MASK(LO,HI) su_BITENUM_MASK(LO, HI)
su_bits_test(uz x,uz bit)32 INLINE boole su_bits_test(uz x, uz bit){
33 ASSERT_RET(bit < UZ_BITS, FAL0);
34 return ((x & (1lu << bit)) != 0);
35 }
su_bits_set(uz x,uz bit)36 INLINE uz su_bits_set(uz x, uz bit){
37 ASSERT_RET(bit < UZ_BITS, x);
38 return (x | (1lu << bit));
39 }
su_bits_flip(uz x,uz bit)40 INLINE uz su_bits_flip(uz x, uz bit){
41 ASSERT_RET(bit < UZ_BITS, x);
42 return (x ^ (1lu << bit));
43 }
su_bits_clear(uz x,uz bit)44 INLINE uz su_bits_clear(uz x, uz bit){
45 ASSERT_RET(bit < UZ_BITS, x);
46 return (x & ~(1lu << bit));
47 }
su_bits_test_and_set(uz * xp,uz bit)48 INLINE boole su_bits_test_and_set(uz *xp, uz bit){
49 boole rv;
50 ASSERT_RET(xp != NIL, FAL0);
51 ASSERT_RET(bit < UZ_BITS, FAL0);
52 bit = 1lu << bit;
53 rv = ((*xp & bit) != 0);
54 *xp |= bit;
55 return rv;
56 }
su_bits_test_and_flip(uz * xp,uz bit)57 INLINE boole su_bits_test_and_flip(uz *xp, uz bit){
58 boole rv;
59 ASSERT_RET(xp != NIL, FAL0);
60 ASSERT_RET(bit < UZ_BITS, FAL0);
61 bit = 1lu << bit;
62 rv = ((*xp & bit) != 0);
63 *xp ^= bit;
64 return rv;
65 }
su_bits_test_and_clear(uz * xp,uz bit)66 INLINE boole su_bits_test_and_clear(uz *xp, uz bit){
67 boole rv;
68 ASSERT_RET(xp != NIL, FAL0);
69 ASSERT_RET(bit < UZ_BITS, FAL0);
70 bit = 1lu << bit;
71 rv = ((*xp & bit) != 0);
72 *xp &= ~bit;
73 return rv;
74 }
su_bits_find_first_set(uz x)75 INLINE uz su_bits_find_first_set(uz x){
76 uz i = 0;
77 if(x != 0)
78 do if(x & 1)
79 return i;
80 while((++i, x >>= 1));
81 return UZ_MAX;
82 }
su_bits_find_last_set(uz x)83 INLINE uz su_bits_find_last_set(uz x){
84 if(x != 0){
85 uz i = UZ_BITS - 1;
86 do if(x & (1lu << i))
87 return i;
88 while(i--);
89 }
90 return UZ_MAX;
91 }
su_bits_rotate_left(uz x,uz bits)92 INLINE uz su_bits_rotate_left(uz x, uz bits){
93 ASSERT_RET(bits < UZ_BITS, x);
94 return ((x << bits) | (x >> (UZ_BITS - bits)));
95 }
su_bits_rotate_right(uz x,uz bits)96 INLINE uz su_bits_rotate_right(uz x, uz bits){
97 ASSERT_RET(bits < UZ_BITS, x);
98 return ((x >> bits) | (x << (UZ_BITS - bits)));
99 }
su_bits_array_test(uz const * xap,uz bit)100 INLINE boole su_bits_array_test(uz const *xap, uz bit){
101 ASSERT_RET(xap != NIL, FAL0);
102 return su_bits_test(xap[su_BITS_WHICH_OFF(bit)], su_BITS_WHICH_BIT(bit));
103 }
su_bits_array_set(uz * xap,uz bit)104 INLINE void su_bits_array_set(uz *xap, uz bit){
105 ASSERT_RET_VOID(xap != NIL);
106 xap += su_BITS_WHICH_OFF(bit);
107 *xap = su_bits_set(*xap, su_BITS_WHICH_BIT(bit));
108 }
su_bits_array_flip(uz * xap,uz bit)109 INLINE void su_bits_array_flip(uz *xap, uz bit){
110 ASSERT_RET_VOID(xap != NIL);
111 xap += su_BITS_WHICH_OFF(bit);
112 *xap = su_bits_flip(*xap, su_BITS_WHICH_BIT(bit));
113 }
su_bits_array_clear(uz * xap,uz bit)114 INLINE void su_bits_array_clear(uz *xap, uz bit){
115 ASSERT_RET_VOID(xap != NIL);
116 xap += su_BITS_WHICH_OFF(bit);
117 *xap = su_bits_clear(*xap, su_BITS_WHICH_BIT(bit));
118 }
su_bits_array_test_and_set(uz * xap,uz bit)119 INLINE boole su_bits_array_test_and_set(uz *xap, uz bit){
120 ASSERT_RET(xap != NIL, FAL0);
121 xap += su_BITS_WHICH_OFF(bit);
122 return su_bits_test_and_set(xap, su_BITS_WHICH_BIT(bit));
123 }
su_bits_array_test_and_flip(uz * xap,uz bit)124 INLINE boole su_bits_array_test_and_flip(uz *xap, uz bit){
125 ASSERT_RET(xap != NIL, FAL0);
126 xap += su_BITS_WHICH_OFF(bit);
127 return su_bits_test_and_flip(xap, su_BITS_WHICH_BIT(bit));
128 }
su_bits_array_test_and_clear(uz * xap,uz bit)129 INLINE boole su_bits_array_test_and_clear(uz *xap, uz bit){
130 ASSERT_RET(xap != NIL, FAL0);
131 xap += su_BITS_WHICH_OFF(bit);
132 return su_bits_test_and_clear(xap, su_BITS_WHICH_BIT(bit));
133 }
134 #if 0 /* TODO port array_find_first() */
135 EXTERN uz su_bits_array_find_first_set(uz const *xap, uz xaplen);
136 EXTERN uz su_bits_array_find_last_set(uz const *xap, uz xaplen);
137 EXTERN uz su_bits_array_find_first_set_after(uz const *xap, uz xaplen,
138 uz startbit);
139 #endif
140 C_DECL_END
141 #include <su/code-ou.h>
142 #endif /* su_BITS_H */
143 /* s-it-mode */
144