NumCpp  2.7.0
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 <stdexcept>
37 #include <type_traits>
38 #include <vector>
39 
40 #include "boost/dynamic_bitset.hpp"
41 
43 
44 namespace nc
45 {
46  namespace edac::detail
47  {
48  //============================================================================
49  // Method Description:
55  template<
56  typename IntType,
57  std::enable_if_t<std::is_integral_v<IntType>, int> = 0
58  >
59  constexpr bool isPowerOfTwo(IntType n) noexcept
60  {
61  // Returns true if the given non-negative integer n is a power of two.
62  return n != 0 && (n & (n - 1)) == 0;
63  }
64 
65  //============================================================================
66  // Method Description:
77  template<
78  typename IntType,
79  std::enable_if_t<std::is_integral_v<IntType>, int> = 0
80  >
81  std::size_t nextPowerOfTwo(IntType n)
82  {
83  if (n < 0)
84  {
85  throw std::invalid_argument("Input value must be greater than or equal to zero.");
86  }
87 
88  if (isPowerOfTwo(n))
89  {
90  return static_cast<std::size_t>(n) << 1;
91  }
92 
93  return static_cast<std::size_t>(std::pow(2, std::ceil(std::log2(n))));
94  }
95 
96  //============================================================================
97  // Method Description:
104  template<
105  typename IntType,
106  std::enable_if_t<std::is_integral_v<IntType>, int> = 0
107  >
108  std::vector<std::size_t> powersOfTwo(IntType n)
109  {
110  auto i = std::size_t{ 0 };
111  auto power = std::size_t{ 1 };
112  auto powers = std::vector<std::size_t>();
113  powers.reserve(n);
114 
115  while (i < static_cast<std::size_t>(n))
116  {
117  powers.push_back(power);
118  power <<= 1;
119  ++i;
120  }
121 
122  return powers;
123  }
124 
125  //============================================================================
126  // Method Description:
134  template<
135  typename IntType,
136  std::enable_if_t<std::is_integral_v<IntType>, int> = 0
137  >
138  std::size_t numSecdedParityBitsNeeded(IntType numDataBits)
139  {
140  const auto n = nextPowerOfTwo(numDataBits);
141  const auto lowerBin = static_cast<std::size_t>(std::floor(std::log2(n)));
142  const auto upperBin = lowerBin + 1;
143  const auto dataBitBoundary = n - lowerBin - 1;
144  const auto numParityBits = numDataBits <= dataBitBoundary ? lowerBin + 1 : upperBin + 1;
145 
146  if (!isPowerOfTwo(numParityBits + numDataBits))
147  {
148  throw std::runtime_error("input number of data bits is not a valid Hamming SECDED code configuration.");
149  }
150 
151  return numParityBits;
152  }
153 
154  //============================================================================
155  // Method Description:
166  template<
167  typename IntType1,
168  typename IntType2,
169  std::enable_if_t<std::is_integral_v<IntType1>, int> = 0,
170  std::enable_if_t<std::is_integral_v<IntType2>, int> = 0
171  >
172  std::vector<std::size_t> dataBitsCovered(IntType1 numDataBits, IntType2 parityBit)
173  {
174  if (!isPowerOfTwo(parityBit))
175  {
176  throw std::invalid_argument("All hamming parity bits are indexed by powers of two.");
177  }
178 
179  std::size_t dataIndex = 1; // bit we're currently at in the DATA bitstring
180  std::size_t totalIndex = 3; // bit we're currently at in the OVERALL bitstring
181  auto parityBit_ = static_cast<std::size_t>(parityBit);
182 
183  auto indices = std::vector<std::size_t>();
184  indices.reserve(numDataBits); // worst case
185 
186  while (dataIndex <= static_cast<std::size_t>(numDataBits))
187  {
188  const auto currentBitIsData = !isPowerOfTwo(totalIndex);
189  if (currentBitIsData && (totalIndex % (parityBit_ << 1)) >= parityBit_)
190  {
191  indices.push_back(dataIndex - 1); // adjust output to be zero indexed
192  }
193 
194  dataIndex += currentBitIsData ? 1 : 0;
195  ++totalIndex;
196  }
197 
198  return indices;
199  }
200 
201  //============================================================================
202  // Method Description:
208  template<std::size_t DataBits>
209  constexpr bool calculateParity(const std::bitset<DataBits>& data) noexcept
210  {
211  bool parity = false;
212  for (std::size_t i = 0; i < DataBits - 1; ++i)
213  {
214  parity ^= data[i];
215  }
216 
217  return parity;
218  }
219 
220  //============================================================================
221  // Method Description:
227  inline bool calculateParity(const boost::dynamic_bitset<>& data) noexcept
228  {
229  bool parity = false;
230  for (std::size_t i = 0; i < data.size() - 1; ++i)
231  {
232  parity ^= data[i];
233  }
234 
235  return parity;
236  }
237 
238  //============================================================================
239  // Method Description:
249  template<
250  std::size_t DataBits,
251  typename IntType,
252  std::enable_if_t<std::is_integral_v<IntType>, int> = 0
253  >
254  bool calculateParity(const std::bitset<DataBits>& data, IntType parityBit)
255  {
256  bool parity = false;
257  for (const auto i : dataBitsCovered(DataBits, parityBit))
258  {
259  parity ^= data[i];
260  }
261 
262  return parity;
263  }
264 
265  //============================================================================
266  // Method Description:
273  template<
274  std::size_t DataBits,
275  std::size_t EncodedBits,
276  std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0
277  >
278  std::size_t checkBitsConsistent()
279  {
280  const auto numParityBits = detail::numSecdedParityBitsNeeded(DataBits);
281  if (numParityBits + DataBits != EncodedBits)
282  {
283  throw std::runtime_error("DataBits and EncodedBits are not consistent");
284  }
285 
286  return numParityBits;
287  }
288 
289  //============================================================================
290  // Method Description:
297  template<
298  std::size_t DataBits,
299  std::size_t EncodedBits,
300  std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0
301  >
302  std::bitset<DataBits> extractData(const std::bitset<EncodedBits>& encodedBits) noexcept
303  {
304  auto dataBits = std::bitset<DataBits>();
305 
306  std::size_t dataIndex = 0;
307  for (std::size_t encodedIndex = 0; encodedIndex < EncodedBits; ++encodedIndex)
308  {
309  if (!isPowerOfTwo(encodedIndex + 1))
310  {
311  dataBits[dataIndex++] = encodedBits[encodedIndex];
312  if (dataIndex == DataBits)
313  {
314  break;
315  }
316  }
317  }
318 
319  return dataBits;
320  }
321  } // namespace edac::detail
322 
323  namespace edac
324  {
325  //============================================================================
326  // Method Description:
333  template<std::size_t DataBits>
334  boost::dynamic_bitset<> encode(const std::bitset<DataBits>& dataBits)
335  {
336  const auto numParityBits = detail::numSecdedParityBitsNeeded(DataBits);
337  const auto numEncodedBits = numParityBits + DataBits;
338 
339  auto encodedBits = boost::dynamic_bitset<>(numEncodedBits);
340 
341  // set the parity bits
342  for (const auto parityBit : detail::powersOfTwo(numParityBits - 1)) // -1 because overall parity will be calculated seperately later
343  {
344  encodedBits[parityBit - 1] = detail::calculateParity(dataBits, parityBit);
345  }
346 
347  // set the data bits, switch to 1 based to make things easier for isPowerOfTwo
348  std::size_t dataBitIndex = 0;
349  for (std::size_t bitIndex = 1; bitIndex <= numEncodedBits - 1; ++bitIndex) // -1 to account for the overall parity bit
350  {
351  if (!detail::isPowerOfTwo(bitIndex))
352  {
353  encodedBits[bitIndex - 1] = dataBits[dataBitIndex++];
354  }
355  }
356 
357  // compute and set overall parity for the entire encoded data (not including the overall parity bit itself)
358  encodedBits[numEncodedBits - 1] = detail::calculateParity(encodedBits); // overall parity at the end
359 
360  // all done!
361  return encodedBits;
362  }
363 
364  //============================================================================
365  // Method Description:
375  template<
376  std::size_t DataBits,
377  std::size_t EncodedBits,
378  std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0
379  >
380  int decode(std::bitset<EncodedBits> encodedBits, std::bitset<DataBits>& decodedBits)
381  {
382  const auto numParityBits = detail::checkBitsConsistent<DataBits, EncodedBits>();
383 
384  // the data bits, which may be corrupted
385  decodedBits = detail::extractData<DataBits>(encodedBits);
386 
387  // check the overall parity bit
388  const auto overallExpected = detail::calculateParity(encodedBits);
389  const auto overallActual = encodedBits[EncodedBits - 1];
390  const auto overallCorrect = overallExpected == overallActual;
391 
392  // check individual parities - each parity bit's index (besides overall parity) is a power of two
393  std::size_t indexOfError = 0;
394  for (const auto parityBit : detail::powersOfTwo(numParityBits - 1))
395  {
396  const auto expected = detail::calculateParity(decodedBits, parityBit);
397  const auto actual = encodedBits[parityBit - 1]; // -1 because parityBit is 1 based
398  if (expected != actual)
399  {
400  indexOfError += parityBit;
401  }
402  }
403 
404  // attempt to repair a single flipped bit or throw exception if more than one
405  if (overallCorrect && indexOfError != 0)
406  {
407  // two errors found
408  return 2;
409  }
410  else if (!overallCorrect && indexOfError != 0)
411  {
412  // one error found, flip the bit in error and we're good
413  encodedBits.flip(indexOfError - 1);
414  decodedBits = detail::extractData<DataBits>(encodedBits);
415  return 1;
416  }
417 
418  return 0;
419  }
420  } // namespace edac
421 } // namespace nc
422 #endif // #ifndef NUMCPP_NO_USE_BOOST
std::bitset< DataBits > extractData(const std::bitset< EncodedBits > &encodedBits) noexcept
Definition: hammingEncode.hpp:302
std::size_t nextPowerOfTwo(IntType n)
Definition: hammingEncode.hpp:81
std::size_t numSecdedParityBitsNeeded(IntType numDataBits)
Definition: hammingEncode.hpp:138
constexpr bool isPowerOfTwo(IntType n) noexcept
Tests if value is a power of two.
Definition: hammingEncode.hpp:59
std::vector< std::size_t > dataBitsCovered(IntType1 numDataBits, IntType2 parityBit)
Definition: hammingEncode.hpp:172
constexpr bool calculateParity(const std::bitset< DataBits > &data) noexcept
Definition: hammingEncode.hpp:209
std::vector< std::size_t > powersOfTwo(IntType n)
Definition: hammingEncode.hpp:108
std::size_t checkBitsConsistent()
Definition: hammingEncode.hpp:278
int decode(std::bitset< EncodedBits > encodedBits, std::bitset< DataBits > &decodedBits)
Definition: hammingEncode.hpp:380
boost::dynamic_bitset encode(const std::bitset< DataBits > &dataBits)
Definition: hammingEncode.hpp:334
Definition: Coordinate.hpp:45
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