| 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> |
| 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_ |