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