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