1 // Copyright (c) 2015-2016 The Khronos Group Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef SOURCE_UTIL_BITUTILS_H_
16 #define SOURCE_UTIL_BITUTILS_H_
17
18 #include <cassert>
19 #include <cstdint>
20 #include <cstring>
21 #include <type_traits>
22
23 namespace spvtools {
24 namespace utils {
25
26 // Performs a bitwise copy of source to the destination type Dest.
27 template <typename Dest, typename Src>
BitwiseCast(Src source)28 Dest BitwiseCast(Src source) {
29 Dest dest;
30 static_assert(sizeof(source) == sizeof(dest),
31 "BitwiseCast: Source and destination must have the same size");
32 std::memcpy(&dest, &source, sizeof(dest));
33 return dest;
34 }
35
36 // Calculates the bit width of the integer type |T|.
37 template <typename T>
38 struct IntegerBitWidth {
39 static_assert(std::is_integral<T>::value, "Integer type required");
40 static const size_t kBitsPerByte = 8;
41 static const size_t get = sizeof(T) * kBitsPerByte;
42 };
43
44 // SetBits<T, First, Num> returns an integer of type <T> with bits set
45 // for position <First> through <First + Num - 1>, counting from the least
46 // significant bit. In particular when Num == 0, no positions are set to 1.
47 // A static assert will be triggered if First + Num > sizeof(T) * 8, that is,
48 // a bit that will not fit in the underlying type is set.
49 template <typename T, size_t First = 0, size_t Num = 0>
50 struct SetBits {
51 static_assert(First < IntegerBitWidth<T>::get,
52 "Tried to set a bit that is shifted too far.");
53 const static T get = (T(1) << First) | SetBits<T, First + 1, Num - 1>::get;
54 };
55
56 template <typename T, size_t Last>
57 struct SetBits<T, Last, 0> {
58 const static T get = T(0);
59 };
60
61 // This is all compile-time so we can put our tests right here.
62 static_assert(IntegerBitWidth<uint32_t>::get == 32, "IntegerBitWidth mismatch");
63 static_assert(IntegerBitWidth<int32_t>::get == 32, "IntegerBitWidth mismatch");
64 static_assert(IntegerBitWidth<uint64_t>::get == 64, "IntegerBitWidth mismatch");
65 static_assert(IntegerBitWidth<uint8_t>::get == 8, "IntegerBitWidth mismatch");
66
67 static_assert(SetBits<uint32_t, 0, 0>::get == uint32_t(0x00000000),
68 "SetBits failed");
69 static_assert(SetBits<uint32_t, 0, 1>::get == uint32_t(0x00000001),
70 "SetBits failed");
71 static_assert(SetBits<uint32_t, 31, 1>::get == uint32_t(0x80000000),
72 "SetBits failed");
73 static_assert(SetBits<uint32_t, 1, 2>::get == uint32_t(0x00000006),
74 "SetBits failed");
75 static_assert(SetBits<uint32_t, 30, 2>::get == uint32_t(0xc0000000),
76 "SetBits failed");
77 static_assert(SetBits<uint32_t, 0, 31>::get == uint32_t(0x7FFFFFFF),
78 "SetBits failed");
79 static_assert(SetBits<uint32_t, 0, 32>::get == uint32_t(0xFFFFFFFF),
80 "SetBits failed");
81 static_assert(SetBits<uint32_t, 16, 16>::get == uint32_t(0xFFFF0000),
82 "SetBits failed");
83
84 static_assert(SetBits<uint64_t, 0, 1>::get == uint64_t(0x0000000000000001LL),
85 "SetBits failed");
86 static_assert(SetBits<uint64_t, 63, 1>::get == uint64_t(0x8000000000000000LL),
87 "SetBits failed");
88 static_assert(SetBits<uint64_t, 62, 2>::get == uint64_t(0xc000000000000000LL),
89 "SetBits failed");
90 static_assert(SetBits<uint64_t, 31, 1>::get == uint64_t(0x0000000080000000LL),
91 "SetBits failed");
92 static_assert(SetBits<uint64_t, 16, 16>::get == uint64_t(0x00000000FFFF0000LL),
93 "SetBits failed");
94
95 // Returns number of '1' bits in a word.
96 template <typename T>
97 size_t CountSetBits(T word) {
98 static_assert(std::is_integral<T>::value,
99 "CountSetBits requires integer type");
100 size_t count = 0;
101 while (word) {
102 word &= word - 1;
103 ++count;
104 }
105 return count;
106 }
107
108 // Checks if the bit at the |position| is set to '1'.
109 // Bits zero-indexed starting at the least significant bit.
110 // |position| must be within the bit width of |T|.
111 template <typename T>
112 bool IsBitAtPositionSet(T word, size_t position) {
113 static_assert(std::is_integral<T>::value, "Integer type required");
114 static_assert(std::is_unsigned<T>::value, "Unsigned type required");
115 assert(position < IntegerBitWidth<T>::get &&
116 "position must be less than the bit width");
117 return word & T(T(1) << position);
118 }
119
120 // Returns a value obtained by setting a range of adjacent bits of |word| to
121 // |value|. Affected bits are within the range:
122 // [first_position, first_position + num_bits_to_mutate),
123 // assuming zero-based indexing starting at the least
124 // significant bit. Bits to mutate must be within the bit width of |T|.
125 template <typename T>
126 T MutateBits(T word, size_t first_position, size_t num_bits_to_mutate,
127 bool value) {
128 static_assert(std::is_integral<T>::value, "Integer type required");
129 static_assert(std::is_unsigned<T>::value, "Unsigned type required");
130 static const size_t word_bit_width = IntegerBitWidth<T>::get;
131 assert(first_position < word_bit_width &&
132 "Mutated bits must be within bit width");
133 assert(first_position + num_bits_to_mutate <= word_bit_width &&
134 "Mutated bits must be within bit width");
135 if (num_bits_to_mutate == 0) {
136 return word;
137 }
138
139 const T all_ones = ~T(0);
140 const size_t num_unaffected_low_bits = first_position;
141 const T unaffected_low_mask =
142 T(T(all_ones >> num_unaffected_low_bits) << num_unaffected_low_bits);
143
144 const size_t num_unaffected_high_bits =
145 word_bit_width - (first_position + num_bits_to_mutate);
146 const T unaffected_high_mask =
147 T(T(all_ones << num_unaffected_high_bits) >> num_unaffected_high_bits);
148
149 const T mutation_mask = unaffected_low_mask & unaffected_high_mask;
150 if (value) {
151 return word | mutation_mask;
152 }
153 return word & T(~mutation_mask);
154 }
155
156 // Returns a value obtained by setting the |num_bits_to_set| highest bits to
157 // '1'. |num_bits_to_set| must be not be greater than the bit width of |T|.
158 template <typename T>
159 T SetHighBits(T word, size_t num_bits_to_set) {
160 if (num_bits_to_set == 0) {
161 return word;
162 }
163 const size_t word_bit_width = IntegerBitWidth<T>::get;
164 assert(num_bits_to_set <= word_bit_width &&
165 "Can't set more bits than bit width");
166 return MutateBits(word, word_bit_width - num_bits_to_set, num_bits_to_set,
167 true);
168 }
169
170 // Returns a value obtained by setting the |num_bits_to_set| highest bits to
171 // '0'. |num_bits_to_set| must be not be greater than the bit width of |T|.
172 template <typename T>
173 T ClearHighBits(T word, size_t num_bits_to_set) {
174 if (num_bits_to_set == 0) {
175 return word;
176 }
177 const size_t word_bit_width = IntegerBitWidth<T>::get;
178 assert(num_bits_to_set <= word_bit_width &&
179 "Can't clear more bits than bit width");
180 return MutateBits(word, word_bit_width - num_bits_to_set, num_bits_to_set,
181 false);
182 }
183
184 } // namespace utils
185 } // namespace spvtools
186
187 #endif // SOURCE_UTIL_BITUTILS_H_
188