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 | 7c8faa1 | 2019-10-28 22:26:28 -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 | 7c8faa1 | 2019-10-28 22:26:28 -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 | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 104 | |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame] | 105 | uint8_t bf_l = *relAddr; |
| 106 | bf_l >>= bf_l_shift; |
| 107 | bf_l <<= bf_l_shift; |
Zane Shelley | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 108 | |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame] | 109 | uint8_t bf_r = *relAddr; |
| 110 | bf_r <<= bf_r_shift; |
| 111 | bf_r >>= bf_r_shift; |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 112 | |
| 113 | // Combine all three parts of the byte and write it out to memory. |
| 114 | *relAddr = bf_l | bf | bf_r; |
| 115 | |
| 116 | // Check for any remaining bits after this target byte. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 117 | if (0 != remain_len) |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 118 | { |
| 119 | // Recursively call this function on the remaining bits. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 120 | setFieldLeft(i_pos + bf_len, remain_len, i_val << bf_len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 121 | } |
| 122 | } |
| 123 | |
| 124 | //------------------------------------------------------------------------------ |
| 125 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 126 | void BitString::setPattern(uint64_t i_sPos, uint64_t i_sLen, uint64_t i_pattern, |
| 127 | uint64_t i_pLen) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 128 | { |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 129 | |
| 130 | HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address |
| 131 | HEI_ASSERT(0 < i_sLen); // must have at least one bit |
| 132 | HEI_ASSERT(i_sPos + i_sLen <= getBitLen()); // field must be within range |
| 133 | HEI_ASSERT(0 < i_pLen); // must have at least one bit |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 134 | 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] | 135 | |
| 136 | // Get a bit string for the pattern subset (right justified). |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 137 | // Note that we cannot use a BitStringBuffer here because this function |
| 138 | // could be used in the constructor of BitStringBuffer, which could causes |
| 139 | // an infinite loop. |
| 140 | uint8_t a[sizeof(i_pattern)] = {}; |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 141 | BitString bs{sizeof(i_pattern) * 8, a}; |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 142 | bs.setFieldRight(0, i_pLen, i_pattern); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 143 | |
| 144 | // Iterate the range in chunks the size of i_pLen. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 145 | uint64_t endPos = i_sPos + i_sLen; |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 146 | for (uint64_t pos = i_sPos; pos < endPos; pos += i_pLen) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 147 | { |
| 148 | // 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] | 149 | uint64_t len = std::min(i_pLen, endPos - pos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 150 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 151 | // Get this chunk's pattern value, truncate (right justified) if needed. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 152 | uint64_t pattern = bs.getFieldRight(0, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 153 | |
| 154 | // Set the pattern in this string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 155 | setFieldRight(pos, len, pattern); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 156 | } |
| 157 | } |
| 158 | |
| 159 | //------------------------------------------------------------------------------ |
| 160 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 161 | void BitString::setString(const BitString& i_sStr, uint64_t i_sPos, |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 162 | uint64_t i_sLen, uint64_t i_dPos) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 163 | { |
| 164 | // Ensure the source parameters are valid. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 165 | HEI_ASSERT(nullptr != i_sStr.getBufAddr()); |
| 166 | HEI_ASSERT(0 < i_sLen); // at least one bit to copy |
| 167 | HEI_ASSERT(i_sPos + i_sLen <= i_sStr.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 168 | |
| 169 | // Ensure the destination has at least one bit available to copy. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 170 | HEI_ASSERT(nullptr != getBufAddr()); |
| 171 | HEI_ASSERT(i_dPos < getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 172 | |
| 173 | // If the source length is greater than the destination length than the |
| 174 | // extra source bits are ignored. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 175 | uint64_t actLen = std::min(i_sLen, getBitLen() - i_dPos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 176 | |
| 177 | // The bit strings may be in overlapping memory spaces. So we need to copy |
| 178 | // the data in the correct direction to prevent overlapping. |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 179 | uint64_t sRelOffset = 0, dRelOffset = 0; |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 180 | uint8_t* sRelAddr = i_sStr.getRelativePosition(sRelOffset, i_sPos); |
Zane Shelley | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 181 | uint8_t* dRelAddr = getRelativePosition(dRelOffset, i_dPos); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 182 | |
| 183 | // Copy the data. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 184 | if ((dRelAddr == sRelAddr) && (dRelOffset == sRelOffset)) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 185 | { |
| 186 | // Do nothing. The source and destination are the same. |
| 187 | } |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 188 | else if ((dRelAddr < sRelAddr) || |
| 189 | ((dRelAddr == sRelAddr) && (dRelOffset < sRelOffset))) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 190 | { |
| 191 | // Copy the data forward. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 192 | for (uint64_t pos = 0; pos < 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 len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 195 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 196 | uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len); |
| 197 | setFieldRight(i_dPos + pos, len, value); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 198 | } |
| 199 | } |
| 200 | else // Copy the data backwards. |
| 201 | { |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 202 | // Get the first position of the last chunk (byte aligned). |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 203 | uint64_t lastPos = ((actLen - 1) / UINT64_BIT_LEN) * UINT64_BIT_LEN; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 204 | |
| 205 | // Start with the last chunk and work backwards. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 206 | for (int32_t pos = lastPos; 0 <= pos; pos -= UINT64_BIT_LEN) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 207 | { |
Zane Shelley | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 208 | uint64_t len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 209 | uint64_t value = i_sStr.getFieldRight(i_sPos + pos, len); |
| 210 | setFieldRight(i_dPos + pos, len, value); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 211 | } |
| 212 | } |
| 213 | } |
| 214 | |
| 215 | //------------------------------------------------------------------------------ |
| 216 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 217 | void BitString::maskString(const BitString& i_mask) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 218 | { |
| 219 | // Get the length of the smallest string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 220 | uint64_t actLen = std::min(getBitLen(), i_mask.getBitLen()); |
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 | for (uint64_t pos = 0; pos < 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 len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 225 | |
Zane Shelley | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 226 | uint64_t dVal = getFieldRight(pos, len); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 227 | uint64_t sVal = i_mask.getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 228 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 229 | setFieldRight(pos, len, dVal & ~sVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 230 | } |
| 231 | } |
| 232 | |
| 233 | //------------------------------------------------------------------------------ |
| 234 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 235 | bool BitString::isEqual(const BitString& i_str) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 236 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 237 | if (getBitLen() != i_str.getBitLen()) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 238 | return false; // size not equal |
| 239 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 240 | for (uint64_t pos = 0; pos < 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 | uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 243 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 244 | if (getFieldRight(pos, len) != i_str.getFieldRight(pos, len)) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 245 | return false; // bit strings do not match |
| 246 | } |
| 247 | |
| 248 | return true; // bit strings match |
| 249 | } |
| 250 | |
| 251 | //------------------------------------------------------------------------------ |
| 252 | |
| 253 | bool BitString::isZero() const |
| 254 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 255 | for (uint64_t pos = 0; pos < 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 | uint64_t len = std::min(getBitLen() - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 258 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 259 | if (0 != getFieldRight(pos, len)) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 260 | return false; // something is non-zero |
| 261 | } |
| 262 | |
| 263 | return true; // everything was zero |
| 264 | } |
| 265 | |
| 266 | //------------------------------------------------------------------------------ |
| 267 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 268 | 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] | 269 | { |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 270 | uint64_t endPos = i_pos + i_len; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 271 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 272 | HEI_ASSERT(endPos <= getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 273 | |
Zane Shelley | d0af358 | 2019-09-19 10:48:59 -0500 | [diff] [blame] | 274 | uint64_t count = 0; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 275 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 276 | for (uint64_t i = i_pos; i < endPos; i++) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 277 | { |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame] | 278 | if (isBitSet(i)) |
| 279 | count++; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 280 | } |
| 281 | |
| 282 | return count; |
| 283 | } |
| 284 | |
| 285 | //------------------------------------------------------------------------------ |
| 286 | |
| 287 | BitStringBuffer BitString::operator~() const |
| 288 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 289 | BitStringBuffer bsb(getBitLen()); |
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 | for (uint64_t pos = 0; pos < 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 len = std::min(getBitLen() - pos, UINT64_BIT_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 | uint64_t dVal = getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 296 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 297 | bsb.setFieldRight(pos, len, ~dVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 298 | } |
| 299 | |
| 300 | return bsb; |
| 301 | } |
| 302 | |
| 303 | //------------------------------------------------------------------------------ |
| 304 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 305 | BitStringBuffer BitString::operator&(const BitString& i_bs) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 306 | { |
| 307 | // Get the length of the smallest string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 308 | uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen()); |
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 | BitStringBuffer bsb(actLen); |
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 | for (uint64_t pos = 0; pos < 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 len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 315 | |
Zane Shelley | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 316 | uint64_t dVal = getFieldRight(pos, len); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 317 | uint64_t sVal = i_bs.getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 318 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 319 | bsb.setFieldRight(pos, len, dVal & sVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 320 | } |
| 321 | |
| 322 | return bsb; |
| 323 | } |
| 324 | |
| 325 | //------------------------------------------------------------------------------ |
| 326 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 327 | BitStringBuffer BitString::operator|(const BitString& i_bs) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 328 | { |
| 329 | // Get the length of the smallest string. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 330 | uint64_t actLen = std::min(getBitLen(), i_bs.getBitLen()); |
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 | BitStringBuffer bsb(actLen); |
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 | for (uint64_t pos = 0; pos < 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 len = std::min(actLen - pos, UINT64_BIT_LEN); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 337 | |
Zane Shelley | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 338 | uint64_t dVal = getFieldRight(pos, len); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 339 | uint64_t sVal = i_bs.getFieldRight(pos, len); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 340 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 341 | bsb.setFieldRight(pos, len, dVal | sVal); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 342 | } |
| 343 | |
| 344 | return bsb; |
| 345 | } |
| 346 | |
| 347 | //------------------------------------------------------------------------------ |
| 348 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 349 | BitStringBuffer BitString::operator>>(uint64_t i_shift) const |
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 | BitStringBuffer bsb(getBitLen()); // default all zeros |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 352 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 353 | if (i_shift < getBitLen()) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 354 | { |
| 355 | // bso overlays bsb, containing the shifted offset. |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 356 | BitString bso(bsb.getBitLen() - i_shift, bsb.getBufAddr(), i_shift); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 357 | |
| 358 | // Copy this into bso. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 359 | bso.setString(*this); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 360 | } |
| 361 | |
| 362 | return bsb; |
| 363 | } |
| 364 | |
| 365 | //------------------------------------------------------------------------------ |
| 366 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 367 | BitStringBuffer BitString::operator<<(uint64_t i_shift) const |
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 | BitStringBuffer bsb(getBitLen()); // default all zeros |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 370 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 371 | if (i_shift < getBitLen()) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 372 | { |
| 373 | // bso overlays *this, containing the shifted offset. |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 374 | BitString bso(this->getBitLen() - i_shift, this->getBufAddr(), i_shift); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 375 | |
| 376 | // Copy bso into bsb. |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 377 | bsb.setString(bso); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 378 | } |
| 379 | |
| 380 | return bsb; |
| 381 | } |
| 382 | |
| 383 | //------------------------------------------------------------------------------ |
| 384 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 385 | uint8_t* BitString::getRelativePosition(uint64_t& o_relPos, |
Zane Shelley | 7c8faa1 | 2019-10-28 22:26:28 -0500 | [diff] [blame^] | 386 | uint64_t i_absPos) const |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 387 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 388 | HEI_ASSERT(nullptr != getBufAddr()); // must to have a valid address |
| 389 | HEI_ASSERT(i_absPos < getBitLen()); // must be a valid position |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 390 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 391 | o_relPos = (i_absPos + iv_offset) % UINT8_BIT_LEN; |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 392 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 393 | return ((uint8_t*)iv_bufAddr + ((i_absPos + iv_offset) / UINT8_BIT_LEN)); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 394 | } |
| 395 | |
| 396 | //############################################################################## |
| 397 | // BitStringBuffer class |
| 398 | //############################################################################## |
| 399 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 400 | BitStringBuffer::BitStringBuffer(uint64_t i_bitLen) : |
| 401 | BitString(i_bitLen, nullptr) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 402 | { |
| 403 | initBuffer(); |
| 404 | } |
| 405 | |
| 406 | //------------------------------------------------------------------------------ |
| 407 | |
| 408 | BitStringBuffer::~BitStringBuffer() |
| 409 | { |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 410 | delete[](uint8_t*) getBufAddr(); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 411 | } |
| 412 | |
| 413 | //------------------------------------------------------------------------------ |
| 414 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 415 | BitStringBuffer::BitStringBuffer(const BitString& i_bs) : |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 416 | BitString(i_bs.getBitLen(), nullptr) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 417 | { |
| 418 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame] | 419 | if (!i_bs.isZero()) |
| 420 | { |
| 421 | setString(i_bs); |
| 422 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 423 | } |
| 424 | |
| 425 | //------------------------------------------------------------------------------ |
| 426 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 427 | BitStringBuffer::BitStringBuffer(const BitStringBuffer& i_bsb) : |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 428 | BitString(i_bsb.getBitLen(), nullptr) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 429 | { |
| 430 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame] | 431 | if (!i_bsb.isZero()) |
| 432 | { |
| 433 | setString(i_bsb); |
| 434 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 435 | } |
| 436 | |
| 437 | //------------------------------------------------------------------------------ |
| 438 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 439 | BitStringBuffer& BitStringBuffer::operator=(const BitString& i_bs) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 440 | { |
| 441 | // The initBuffer() function will deallocate the buffer as well, however we |
| 442 | // also need to deallocate the buffer here before we set the length. |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 443 | delete[](uint8_t*) getBufAddr(); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 444 | setBufAddr(nullptr); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 445 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 446 | setBitLen(i_bs.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 447 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame] | 448 | if (!i_bs.isZero()) |
| 449 | { |
| 450 | setString(i_bs); |
| 451 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 452 | |
| 453 | return *this; |
| 454 | } |
| 455 | |
| 456 | //------------------------------------------------------------------------------ |
| 457 | |
Zane Shelley | fe27b65 | 2019-10-28 11:33:07 -0500 | [diff] [blame] | 458 | BitStringBuffer& BitStringBuffer::operator=(const BitStringBuffer& i_bsb) |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 459 | { |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 460 | if (this != &i_bsb) // Check for assignment to self |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 461 | { |
| 462 | // The initBuffer() function will deallocate the buffer as well, however |
| 463 | // we also need to deallocate the buffer here before we set the length. |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 464 | delete[](uint8_t*) getBufAddr(); |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 465 | setBufAddr(nullptr); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 466 | |
Zane Shelley | 83da245 | 2019-10-25 15:45:34 -0500 | [diff] [blame] | 467 | setBitLen(i_bsb.getBitLen()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 468 | initBuffer(); |
Zane Shelley | 7f7a42d | 2019-10-28 13:28:31 -0500 | [diff] [blame] | 469 | if (!i_bsb.isZero()) |
| 470 | { |
| 471 | setString(i_bsb); |
| 472 | } |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 473 | } |
| 474 | |
| 475 | return *this; |
| 476 | } |
| 477 | |
| 478 | //------------------------------------------------------------------------------ |
| 479 | |
| 480 | void BitStringBuffer::initBuffer() |
| 481 | { |
| 482 | // Deallocate the current buffer. |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 483 | delete[](uint8_t*) getBufAddr(); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 484 | |
Ben Tyner | a8126fd | 2019-08-01 19:40:07 -0500 | [diff] [blame] | 485 | // create new buffer, initialized to 0's |
Zane Shelley | c477199 | 2019-10-28 22:01:49 -0500 | [diff] [blame] | 486 | setBufAddr(new uint8_t[getMinBytes(getBitLen())]()); |
Zane Shelley | fd3f9cc | 2019-07-29 15:02:24 -0500 | [diff] [blame] | 487 | } |
| 488 | |
Zane Shelley | 871adec | 2019-07-30 11:01:39 -0500 | [diff] [blame] | 489 | } // end namespace libhei |