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