NumCpp  2.10.1
A Templatized Header Only C++ Implementation of the Python NumPy Library
hammingEncode.hpp
Go to the documentation of this file.
1 
29 #pragma once
30 
31 #ifndef NUMCPP_NO_USE_BOOST
32 
33 #include <bitset>
34 #include <cmath>
35 #include <cstdlib>
36 #include <numeric>
37 #include <stdexcept>
38 #include <type_traits>
39 #include <vector>
40 
41 #include "boost/dynamic_bitset.hpp"
42 
44 
45 namespace nc::edac
46 {
47  namespace detail
48  {
49  //============================================================================
50  // Method Description:
56  template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
57  constexpr bool isPowerOfTwo(IntType n) noexcept
58  {
59  // Returns true if the given non-negative integer n is a power of two.
60  return n != 0 && (n & (n - 1)) == 0;
61  }
62 
63  //============================================================================
64  // Method Description:
75  template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
76  std::size_t nextPowerOfTwo(IntType n)
77  {
78  if (n < 0)
79  {
80  throw std::invalid_argument("Input value must be greater than or equal to zero.");
81  }
82 
83  if (isPowerOfTwo(n))
84  {
85  return static_cast<std::size_t>(n) << 1;
86  }
87 
88  return static_cast<std::size_t>(std::pow(2, std::ceil(std::log2(n))));
89  }
90 
91  //============================================================================
92  // Method Description:
99  template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
100  std::vector<std::size_t> powersOfTwo(IntType n)
101  {
102  auto i = std::size_t{ 0 };
103  auto power = std::size_t{ 1 };
104  auto powers = std::vector<std::size_t>();
105  powers.reserve(n);
106 
107  while (i < static_cast<std::size_t>(n))
108  {
109  powers.push_back(power);
110  power <<= 1;
111  ++i;
112  }
113 
114  return powers;
115  }
116 
117  //============================================================================
118  // Method Description:
126  template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
127  std::size_t numSecdedParityBitsNeeded(IntType numDataBits)
128  {
129  const auto n = nextPowerOfTwo(numDataBits);
130  const auto lowerBin = static_cast<std::size_t>(std::floor(std::log2(n)));
131  const auto upperBin = lowerBin + 1;
132  const auto dataBitBoundary = n - lowerBin - 1;
133  const auto numParityBits = numDataBits <= dataBitBoundary ? lowerBin + 1 : upperBin + 1;
134 
135  if (!isPowerOfTwo(numParityBits + numDataBits))
136  {
137  throw std::runtime_error("input number of data bits is not a valid Hamming SECDED code configuration.");
138  }
139 
140  return numParityBits;
141  }
142 
143  //============================================================================
144  // Method Description:
155  template<typename IntType1,
156  typename IntType2,
157  std::enable_if_t<std::is_integral_v<IntType1>, int> = 0,
158  std::enable_if_t<std::is_integral_v<IntType2>, int> = 0>
159  std::vector<std::size_t> dataBitsCovered(IntType1 numDataBits, IntType2 parityBit)
160  {
161  if (!isPowerOfTwo(parityBit))
162  {
163  throw std::invalid_argument("All hamming parity bits are indexed by powers of two.");
164  }
165 
166  std::size_t dataIndex = 1; // bit we're currently at in the DATA bitstring
167  std::size_t totalIndex = 3; // bit we're currently at in the OVERALL bitstring
168  auto parityBit_ = static_cast<std::size_t>(parityBit);
169 
170  auto indices = std::vector<std::size_t>();
171  indices.reserve(numDataBits); // worst case
172 
173  while (dataIndex <= static_cast<std::size_t>(numDataBits))
174  {
175  const auto currentBitIsData = !isPowerOfTwo(totalIndex);
176  if (currentBitIsData && (totalIndex % (parityBit_ << 1)) >= parityBit_)
177  {
178  indices.push_back(dataIndex - 1); // adjust output to be zero indexed
179  }
180 
181  dataIndex += currentBitIsData ? 1 : 0;
182  ++totalIndex;
183  }
184 
185  return indices;
186  }
187 
188  //============================================================================
189  // Method Description:
195  template<std::size_t DataBits>
196  constexpr bool calculateParity(const std::bitset<DataBits>& data) noexcept
197  {
198  bool parity = false;
199  for (std::size_t i = 0; i < DataBits - 1; ++i)
200  {
201  parity ^= data[i];
202  }
203 
204  return parity;
205  }
206 
207  //============================================================================
208  // Method Description:
214  inline bool calculateParity(const boost::dynamic_bitset<>& data) noexcept
215  {
216  bool parity = false;
217  for (std::size_t i = 0; i < data.size() - 1; ++i)
218  {
219  parity ^= data[i];
220  }
221 
222  return parity;
223  }
224 
225  //============================================================================
226  // Method Description:
236  template<std::size_t DataBits, typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
237  bool calculateParity(const std::bitset<DataBits>& data, IntType parityBit)
238  {
239  const auto bitsCovered = dataBitsCovered(DataBits, parityBit);
240  return std::accumulate(bitsCovered.begin(),
241  bitsCovered.end(),
242  false,
243  [&data](bool parity, const auto value) noexcept -> bool { return parity ^= value; });
244  }
245 
246  //============================================================================
247  // Method Description:
254  template<std::size_t DataBits,
255  std::size_t EncodedBits,
256  std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0>
257  std::size_t checkBitsConsistent()
258  {
259  const auto numParityBits = detail::numSecdedParityBitsNeeded(DataBits);
260  if (numParityBits + DataBits != EncodedBits)
261  {
262  throw std::runtime_error("DataBits and EncodedBits are not consistent");
263  }
264 
265  return numParityBits;
266  }
267 
268  //============================================================================
269  // Method Description:
276  template<std::size_t DataBits,
277  std::size_t EncodedBits,
278  std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0>
279  std::bitset<DataBits> extractData(const std::bitset<EncodedBits>& encodedBits) noexcept
280  {
281  auto dataBits = std::bitset<DataBits>();
282 
283  std::size_t dataIndex = 0;
284  for (std::size_t encodedIndex = 0; encodedIndex < EncodedBits; ++encodedIndex)
285  {
286  if (!isPowerOfTwo(encodedIndex + 1))
287  {
288  dataBits[dataIndex++] = encodedBits[encodedIndex];
289  if (dataIndex == DataBits)
290  {
291  break;
292  }
293  }
294  }
295 
296  return dataBits;
297  }
298  } // namespace detail
299 
300  //============================================================================
301  // Method Description:
308  template<std::size_t DataBits>
309  boost::dynamic_bitset<> encode(const std::bitset<DataBits>& dataBits)
310  {
311  const auto numParityBits = detail::numSecdedParityBitsNeeded(DataBits);
312  const auto numEncodedBits = numParityBits + DataBits;
313 
314  auto encodedBits = boost::dynamic_bitset<>(numEncodedBits); // NOLINT(google-readability-casting)
315 
316  // set the parity bits
317  for (const auto parityBit :
318  detail::powersOfTwo(numParityBits - 1)) // -1 because overall parity will be calculated seperately later
319  {
320  encodedBits[parityBit - 1] = detail::calculateParity(dataBits, parityBit);
321  }
322 
323  // set the data bits, switch to 1 based to make things easier for isPowerOfTwo
324  std::size_t dataBitIndex = 0;
325  for (std::size_t bitIndex = 1; bitIndex <= numEncodedBits - 1;
326  ++bitIndex) // -1 to account for the overall parity bit
327  {
328  if (!detail::isPowerOfTwo(bitIndex))
329  {
330  encodedBits[bitIndex - 1] = dataBits[dataBitIndex++];
331  }
332  }
333 
334  // compute and set overall parity for the entire encoded data (not including the overall parity bit itself)
335  encodedBits[numEncodedBits - 1] = detail::calculateParity(encodedBits); // overall parity at the end
336 
337  // all done!
338  return encodedBits;
339  }
340 
341  //============================================================================
342  // Method Description:
352  template<std::size_t DataBits,
353  std::size_t EncodedBits,
354  std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0>
355  int decode(std::bitset<EncodedBits> encodedBits, std::bitset<DataBits>& decodedBits)
356  {
357  const auto numParityBits = detail::checkBitsConsistent<DataBits, EncodedBits>();
358 
359  // the data bits, which may be corrupted
360  decodedBits = detail::extractData<DataBits>(encodedBits);
361 
362  // check the overall parity bit
363  const auto overallExpected = detail::calculateParity(encodedBits);
364  const auto overallActual = encodedBits[EncodedBits - 1];
365  const auto overallCorrect = overallExpected == overallActual;
366 
367  // check individual parities - each parity bit's index (besides overall parity) is a power of two
368  std::size_t indexOfError = 0;
369  for (const auto parityBit : detail::powersOfTwo(numParityBits - 1))
370  {
371  const auto expected = detail::calculateParity(decodedBits, parityBit);
372  const auto actual = encodedBits[parityBit - 1]; // -1 because parityBit is 1 based
373  if (expected != actual)
374  {
375  indexOfError += parityBit;
376  }
377  }
378 
379  // attempt to repair a single flipped bit or throw exception if more than one
380  if (overallCorrect && indexOfError != 0)
381  {
382  // two errors found
383  return 2;
384  }
385  else if (!overallCorrect && indexOfError != 0)
386  {
387  // one error found, flip the bit in error and we're good
388  encodedBits.flip(indexOfError - 1);
389  decodedBits = detail::extractData<DataBits>(encodedBits);
390  return 1;
391  }
392 
393  return 0;
394  }
395 } // namespace nc::edac
396 #endif // #ifndef NUMCPP_NO_USE_BOOST
std::bitset< DataBits > extractData(const std::bitset< EncodedBits > &encodedBits) noexcept
Definition: hammingEncode.hpp:279
std::size_t nextPowerOfTwo(IntType n)
Definition: hammingEncode.hpp:76
std::size_t numSecdedParityBitsNeeded(IntType numDataBits)
Definition: hammingEncode.hpp:127
constexpr bool isPowerOfTwo(IntType n) noexcept
Tests if value is a power of two.
Definition: hammingEncode.hpp:57
std::vector< std::size_t > dataBitsCovered(IntType1 numDataBits, IntType2 parityBit)
Definition: hammingEncode.hpp:159
constexpr bool calculateParity(const std::bitset< DataBits > &data) noexcept
Definition: hammingEncode.hpp:196
std::vector< std::size_t > powersOfTwo(IntType n)
Definition: hammingEncode.hpp:100
std::size_t checkBitsConsistent()
Definition: hammingEncode.hpp:257
Definition: hammingEncode.hpp:46
int decode(std::bitset< EncodedBits > encodedBits, std::bitset< DataBits > &decodedBits)
Definition: hammingEncode.hpp:355
boost::dynamic_bitset encode(const std::bitset< DataBits > &dataBits)
Definition: hammingEncode.hpp:309
constexpr dtype power(dtype inValue, uint8 inExponent) noexcept
Definition: Functions/power.hpp:52
dtype ceil(dtype inValue) noexcept
Definition: ceil.hpp:48
auto log2(dtype inValue) noexcept
Definition: log2.hpp:49
dtype floor(dtype inValue) noexcept
Definition: floor.hpp:48