Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 1 | /** @file hei_bit_string.cpp |
| 2 | * @brief BitString and BitStringBuffer class definitions |
| 3 | */ |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 4 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 5 | #include <hei_user_defines.hpp> |
Zane Shelley | ca9f625 | 2019-10-25 21:17:30 -0500 | [diff] [blame] | 6 | #include <util/hei_bit_string.hpp> |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 7 | |
| 8 | #include <algorithm> |
| 9 | |
Zane Shelley | 871adec | 2019-07-30 11:01:39 -0500 | [diff] [blame] | 10 | namespace libhei |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 11 | { |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 12 | |
| 13 | //############################################################################## |
| 14 | // BitString class |
| 15 | //############################################################################## |
| 16 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 17 | // number of bits in a uint64_t |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 18 | constexpr uint64_t BitString::UINT64_BIT_LEN = sizeof(uint64_t) * 8; |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 19 | // number of bits in a uint8_t |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 20 | constexpr uint64_t BitString::UINT8_BIT_LEN = sizeof(uint8_t) * 8; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 21 | |
| 22 | //------------------------------------------------------------------------------ |
| 23 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 24 | uint64_t BitString::getFieldRight(uint64_t i_pos, uint64_t i_len) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 25 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 26 | HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address |
| 27 | HEI_ASSERT(0 < i_len); // must have at least one bit |
| 28 | HEI_ASSERT(i_len <= UINT64_BIT_LEN); // i_len length must be valid |
| 29 | HEI_ASSERT(i_pos + i_len <= getBitLen()); // field must be within range |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 30 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 31 | // Get the relative address of this byte and the relative starting position |
| 32 | // within the byte. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 33 | uint64_t relPos = 0; |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 34 | uint8_t* relAddr = getRelativePosition(relPos, i_pos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 35 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 36 | // Get the length of the target bit field within this byte and the length of |
| 37 | // the bit field for any remaining bits. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 38 | uint64_t bf_len = i_len; |
| 39 | uint64_t remain_len = 0; |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 40 | if (UINT8_BIT_LEN < relPos + i_len) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 41 | { |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 42 | // The target bit field crosses a byte boundary. So truncate the bit |
| 43 | // length for this byte and update the remaining length. |
| 44 | bf_len = UINT8_BIT_LEN - relPos; |
| 45 | remain_len = i_len - bf_len; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 46 | } |
| 47 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 48 | // Get the target bit field within this byte (right justified). |
| 49 | uint8_t bf = *relAddr; |
| 50 | bf <<= relPos; // Mask off uneeded bits on the left side. |
| 51 | bf >>= UINT8_BIT_LEN - bf_len; // Right justify the value. |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 52 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 53 | // Check for any remaining bits after this target byte. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 54 | if (0 != remain_len) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 55 | { |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 56 | // Recursively call this function on the remaining bits and push them |
| 57 | // into the right side of the return value. |
| 58 | uint64_t val = static_cast<uint64_t>(bf) << remain_len; |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 59 | return val | getFieldRight(i_pos + bf_len, remain_len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 60 | } |
| 61 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 62 | // Nothing more to do. Simply return this bit field. |
| 63 | return bf; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 64 | } |
| 65 | |
| 66 | //------------------------------------------------------------------------------ |
| 67 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 68 | void BitString::setFieldLeft(uint64_t i_pos, uint64_t i_len, uint64_t i_val) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 69 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 70 | HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address |
| 71 | HEI_ASSERT(0 < i_len); // must have at least one bit |
| 72 | HEI_ASSERT(i_len <= UINT64_BIT_LEN); // i_len length must be valid |
| 73 | HEI_ASSERT(i_pos + i_len <= getBitLen()); // field must be within range |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 74 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 75 | // Get the relative address of this byte and the relative starting position |
| 76 | // within the byte. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 77 | uint64_t relPos = 0; |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 78 | uint8_t* relAddr = getRelativePosition(relPos, i_pos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 79 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 80 | // Get the length of the target bit field within this byte and the length of |
| 81 | // the bit field for any remaining bits. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 82 | uint64_t bf_len = i_len; |
| 83 | uint64_t remain_len = 0; |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 84 | if (UINT8_BIT_LEN < relPos + i_len) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 85 | { |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 86 | // The target bit field crosses a byte boundary. So truncate the bit |
| 87 | // length for this byte and update the remaining length. |
| 88 | bf_len = UINT8_BIT_LEN - relPos; |
| 89 | remain_len = i_len - bf_len; |
| 90 | } |
| 91 | |
| 92 | // It is possible there are bits in this byte on either side of the target |
| 93 | // bit field that must be preserved. Get the length of each of those bit |
| 94 | // fields. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 95 | uint64_t bf_l_len = relPos; |
| 96 | uint64_t bf_r_len = UINT8_BIT_LEN - (bf_l_len + bf_len); |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 97 | |
| 98 | // Get the target bit field from the left justified inputed value. |
| 99 | uint8_t bf = (i_val >> (UINT64_BIT_LEN - bf_len)) << bf_r_len; |
| 100 | |
| 101 | // Get the bit fields on either side of the target bit field. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 102 | uint64_t bf_l_shift = UINT8_BIT_LEN - bf_l_len; |
| 103 | uint64_t bf_r_shift = UINT8_BIT_LEN - bf_r_len; |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame^] | 104 | uint8_t bf_l = *relAddr; |
| 105 | bf_l >>= bf_l_shift; |
| 106 | bf_l <<= bf_l_shift; |
| 107 | uint8_t bf_r = *relAddr; |
| 108 | bf_r <<= bf_r_shift; |
| 109 | bf_r >>= bf_r_shift; |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 110 | |
| 111 | // Combine all three parts of the byte and write it out to memory. |
| 112 | *relAddr = bf_l | bf | bf_r; |
| 113 | |
| 114 | // Check for any remaining bits after this target byte. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 115 | if (0 != remain_len) |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 116 | { |
| 117 | // Recursively call this function on the remaining bits. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 118 | setFieldLeft(i_pos + bf_len, remain_len, i_val << bf_len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 119 | } |
| 120 | } |
| 121 | |
| 122 | //------------------------------------------------------------------------------ |
| 123 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 124 | void BitString::setPattern(uint64_t i_sPos, uint64_t i_sLen, uint64_t i_pattern, |
| 125 | uint64_t i_pLen) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 126 | { |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 127 | |
| 128 | HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address |
| 129 | HEI_ASSERT(0 < i_sLen); // must have at least one bit |
| 130 | HEI_ASSERT(i_sPos + i_sLen <= getBitLen()); // field must be within range |
| 131 | HEI_ASSERT(0 < i_pLen); // must have at least one bit |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 132 | HEI_ASSERT(i_pLen <= UINT64_BIT_LEN); // i_pLen length must be valid |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 133 | |
| 134 | // Get a bit string for the pattern subset (right justified). |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 135 | // Note that we cannot use a BitStringBuffer here because this function |
| 136 | // could be used in the constructor of BitStringBuffer, which could causes |
| 137 | // an infinite loop. |
| 138 | uint8_t a[sizeof(i_pattern)] = {}; |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 139 | BitString bs { sizeof(i_pattern) * 8, a }; |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 140 | bs.setFieldRight(0, i_pLen, i_pattern); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 141 | |
| 142 | // Iterate the range in chunks the size of i_pLen. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 143 | uint64_t endPos = i_sPos + i_sLen; |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 144 | for (uint64_t pos = i_sPos; pos < endPos; pos += i_pLen) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 145 | { |
| 146 | // The true chunk size is either i_pLen or the leftovers at the end. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 147 | uint64_t len = std::min(i_pLen, endPos - pos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 148 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 149 | // Get this chunk's pattern value, truncate (right justified) if needed. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 150 | uint64_t pattern = bs.getFieldRight(0, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 151 | |
| 152 | // Set the pattern in this string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 153 | setFieldRight(pos, len, pattern); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 154 | } |
| 155 | } |
| 156 | |
| 157 | //------------------------------------------------------------------------------ |
| 158 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 159 | void BitString::setString(const BitString& i_sStr, uint64_t i_sPos, |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 160 | uint64_t i_sLen, uint64_t i_dPos) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 161 | { |
| 162 | // Ensure the source parameters are valid. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 163 | HEI_ASSERT(nullptr != i_sStr.getBufAddr()); |
| 164 | HEI_ASSERT(0 < i_sLen); // at least one bit to copy |
| 165 | HEI_ASSERT(i_sPos + i_sLen <= i_sStr.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 166 | |
| 167 | // Ensure the destination has at least one bit available to copy. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 168 | HEI_ASSERT(nullptr != getBufAddr()); |
| 169 | HEI_ASSERT(i_dPos < getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 170 | |
| 171 | // If the source length is greater than the destination length than the |
| 172 | // extra source bits are ignored. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 173 | uint64_t actLen = std::min(i_sLen, getBitLen() - i_dPos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 174 | |
| 175 | // The bit strings may be in overlapping memory spaces. So we need to copy |
| 176 | // the data in the correct direction to prevent overlapping. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 177 | uint64_t sRelOffset = 0, dRelOffset = 0; |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 178 | uint8_t* sRelAddr = i_sStr.getRelativePosition(sRelOffset, i_sPos); |
| 179 | uint8_t* dRelAddr = getRelativePosition(dRelOffset, i_dPos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 180 | |
| 181 | // Copy the data. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 182 | if ((dRelAddr == sRelAddr) && (dRelOffset == sRelOffset)) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 183 | { |
| 184 | // Do nothing. The source and destination are the same. |
| 185 | } |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 186 | else if ((dRelAddr < sRelAddr) || |
| 187 | ((dRelAddr == sRelAddr) && (dRelOffset < sRelOffset))) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 188 | { |
| 189 | // Copy the data forward. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 190 | for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 191 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 192 | uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 193 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 194 | uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len); |
| 195 | setFieldRight(i_dPos + pos, len, value); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 196 | } |
| 197 | } |
| 198 | else // Copy the data backwards. |
| 199 | { |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 200 | // Get the first position of the last chunk (byte aligned). |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 201 | uint64_t lastPos = ((actLen - 1) / UINT64_BIT_LEN) * UINT64_BIT_LEN; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 202 | |
| 203 | // Start with the last chunk and work backwards. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 204 | for (int32_t pos = lastPos; 0 <= pos; pos -= UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 205 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 206 | uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN); |
| 207 | uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len); |
| 208 | setFieldRight(i_dPos + pos, len, value); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 209 | } |
| 210 | } |
| 211 | } |
| 212 | |
| 213 | //------------------------------------------------------------------------------ |
| 214 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 215 | void BitString::maskString(const BitString& i_mask) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 216 | { |
| 217 | // Get the length of the smallest string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 218 | uint64_t actLen = std::min(getBitLen(), i_mask.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 219 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 220 | for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 221 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 222 | uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 223 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 224 | uint64_t dVal = getFieldRight(pos, len); |
| 225 | uint64_t sVal = i_mask.getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 226 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 227 | setFieldRight(pos, len, dVal & ~sVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 228 | } |
| 229 | } |
| 230 | |
| 231 | //------------------------------------------------------------------------------ |
| 232 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 233 | bool BitString::isEqual(const BitString& i_str) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 234 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 235 | if (getBitLen() != i_str.getBitLen()) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 236 | return false; // size not equal |
| 237 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 238 | for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 239 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 240 | uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 241 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 242 | if (getFieldRight(pos, len) != i_str.getFieldRight(pos, len)) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 243 | return false; // bit strings do not match |
| 244 | } |
| 245 | |
| 246 | return true; // bit strings match |
| 247 | } |
| 248 | |
| 249 | //------------------------------------------------------------------------------ |
| 250 | |
| 251 | bool BitString::isZero() const |
| 252 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 253 | for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 254 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 255 | uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 256 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 257 | if (0 != getFieldRight(pos, len)) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 258 | return false; // something is non-zero |
| 259 | } |
| 260 | |
| 261 | return true; // everything was zero |
| 262 | } |
| 263 | |
| 264 | //------------------------------------------------------------------------------ |
| 265 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 266 | uint64_t BitString::getSetCount(uint64_t i_pos, uint64_t i_len) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 267 | { |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 268 | uint64_t endPos = i_pos + i_len; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 269 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 270 | HEI_ASSERT(endPos <= getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 271 | |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 272 | uint64_t count = 0; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 273 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 274 | for (uint64_t i = i_pos; i < endPos; i++) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 275 | { |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame^] | 276 | if (isBitSet(i)) |
| 277 | count++; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 278 | } |
| 279 | |
| 280 | return count; |
| 281 | } |
| 282 | |
| 283 | //------------------------------------------------------------------------------ |
| 284 | |
| 285 | BitStringBuffer BitString::operator~() const |
| 286 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 287 | BitStringBuffer bsb(getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 288 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 289 | for (uint64_t pos = 0; pos < getBitLen(); pos += UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 290 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 291 | uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 292 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 293 | uint64_t dVal = getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 294 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 295 | bsb.setFieldRight(pos, len, ~dVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 296 | } |
| 297 | |
| 298 | return bsb; |
| 299 | } |
| 300 | |
| 301 | //------------------------------------------------------------------------------ |
| 302 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 303 | BitStringBuffer BitString::operator&(const BitString& i_bs) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 304 | { |
| 305 | // Get the length of the smallest string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 306 | uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 307 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 308 | BitStringBuffer bsb(actLen); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 309 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 310 | for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 311 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 312 | uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 313 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 314 | uint64_t dVal = getFieldRight(pos, len); |
| 315 | uint64_t sVal = i_bs.getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 316 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 317 | bsb.setFieldRight(pos, len, dVal & sVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 318 | } |
| 319 | |
| 320 | return bsb; |
| 321 | } |
| 322 | |
| 323 | //------------------------------------------------------------------------------ |
| 324 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 325 | BitStringBuffer BitString::operator|(const BitString& i_bs) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 326 | { |
| 327 | // Get the length of the smallest string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 328 | uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 329 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 330 | BitStringBuffer bsb(actLen); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 331 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 332 | for (uint64_t pos = 0; pos < actLen; pos += UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 333 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 334 | uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 335 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 336 | uint64_t dVal = getFieldRight(pos, len); |
| 337 | uint64_t sVal = i_bs.getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 338 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 339 | bsb.setFieldRight(pos, len, dVal | sVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 340 | } |
| 341 | |
| 342 | return bsb; |
| 343 | } |
| 344 | |
| 345 | //------------------------------------------------------------------------------ |
| 346 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 347 | BitStringBuffer BitString::operator>>(uint64_t i_shift) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 348 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 349 | BitStringBuffer bsb(getBitLen()); // default all zeros |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 350 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 351 | if (i_shift < getBitLen()) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 352 | { |
| 353 | // bso overlays bsb, containing the shifted offset. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 354 | BitString bso (bsb.getBitLen() - i_shift, bsb.getBufAddr(), i_shift); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 355 | |
| 356 | // Copy this into bso. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 357 | bso.setString(*this); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 358 | } |
| 359 | |
| 360 | return bsb; |
| 361 | } |
| 362 | |
| 363 | //------------------------------------------------------------------------------ |
| 364 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 365 | BitStringBuffer BitString::operator<<(uint64_t i_shift) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 366 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 367 | BitStringBuffer bsb(getBitLen()); // default all zeros |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 368 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 369 | if (i_shift < getBitLen()) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 370 | { |
| 371 | // bso overlays *this, containing the shifted offset. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 372 | BitString bso (this->getBitLen() - i_shift, this->getBufAddr(), |
| 373 | i_shift); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 374 | |
| 375 | // Copy bso into bsb. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 376 | bsb.setString(bso); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 377 | } |
| 378 | |
| 379 | return bsb; |
| 380 | } |
| 381 | |
| 382 | //------------------------------------------------------------------------------ |
| 383 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 384 | uint8_t* BitString::getRelativePosition(uint64_t& o_relPos, |
| 385 | uint64_t i_absPos) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 386 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 387 | HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address |
| 388 | HEI_ASSERT(i_absPos < getBitLen()); // must be a valid position |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 389 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 390 | o_relPos = (i_absPos + iv_offset) % UINT8_BIT_LEN; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 391 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 392 | return ((uint8_t*)iv_bufAddr + ((i_absPos + iv_offset) / UINT8_BIT_LEN)); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 393 | } |
| 394 | |
| 395 | //############################################################################## |
| 396 | // BitStringBuffer class |
| 397 | //############################################################################## |
| 398 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 399 | BitStringBuffer::BitStringBuffer(uint64_t i_bitLen) : |
| 400 | BitString(i_bitLen, nullptr) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 401 | { |
| 402 | initBuffer(); |
| 403 | } |
| 404 | |
| 405 | //------------------------------------------------------------------------------ |
| 406 | |
| 407 | BitStringBuffer::~BitStringBuffer() |
| 408 | { |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 409 | delete [] (uint8_t*)getBufAddr(); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 410 | } |
| 411 | |
| 412 | //------------------------------------------------------------------------------ |
| 413 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 414 | BitStringBuffer::BitStringBuffer(const BitString& i_bs) : |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 415 | BitString(i_bs.getBitLen(), nullptr) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 416 | { |
| 417 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame^] | 418 | if (!i_bs.isZero()) |
| 419 | { |
| 420 | setString(i_bs); |
| 421 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 422 | } |
| 423 | |
| 424 | //------------------------------------------------------------------------------ |
| 425 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 426 | BitStringBuffer::BitStringBuffer(const BitStringBuffer& i_bsb) : |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 427 | BitString(i_bsb.getBitLen(), nullptr) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 428 | { |
| 429 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame^] | 430 | if (!i_bsb.isZero()) |
| 431 | { |
| 432 | setString(i_bsb); |
| 433 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 434 | } |
| 435 | |
| 436 | //------------------------------------------------------------------------------ |
| 437 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 438 | BitStringBuffer& BitStringBuffer::operator=(const BitString& i_bs) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 439 | { |
| 440 | // The initBuffer() function will deallocate the buffer as well, however we |
| 441 | // also need to deallocate the buffer here before we set the length. |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 442 | delete [] (uint8_t*)getBufAddr(); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 443 | setBufAddr(nullptr); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 444 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 445 | setBitLen(i_bs.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 446 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame^] | 447 | if (!i_bs.isZero()) |
| 448 | { |
| 449 | setString(i_bs); |
| 450 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 451 | |
| 452 | return *this; |
| 453 | } |
| 454 | |
| 455 | //------------------------------------------------------------------------------ |
| 456 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 457 | BitStringBuffer& BitStringBuffer::operator=(const BitStringBuffer& i_bsb) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 458 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 459 | if (this != &i_bsb) // Check for assignment to self |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 460 | { |
| 461 | // The initBuffer() function will deallocate the buffer as well, however |
| 462 | // we also need to deallocate the buffer here before we set the length. |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 463 | delete [] (uint8_t*)getBufAddr(); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 464 | setBufAddr(nullptr); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 465 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 466 | setBitLen(i_bsb.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 467 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame^] | 468 | if (!i_bsb.isZero()) |
| 469 | { |
| 470 | setString(i_bsb); |
| 471 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 472 | } |
| 473 | |
| 474 | return *this; |
| 475 | } |
| 476 | |
| 477 | //------------------------------------------------------------------------------ |
| 478 | |
| 479 | void BitStringBuffer::initBuffer() |
| 480 | { |
| 481 | // Deallocate the current buffer. |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 482 | delete [] (uint8_t*)getBufAddr(); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 483 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 484 | // create new buffer, initialized to 0's |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 485 | setBufAddr(new uint8_t[ getMinBytes(getBitLen()) ]()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 486 | } |
| 487 | |
Zane Shelley | 871adec | 2019-07-30 11:01:39 -0500 | [diff] [blame] | 488 | } // end namespace libhei |