NumCpp  2.8.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
47  {
48  namespace detail
49  {
50  //============================================================================
51  // Method Description:
57  template<typename IntType, enable_if_t<is_integral_v<IntType>, int> = 0>
58  constexpr bool isPowerOfTwo(IntType n) noexcept
59  {
60  // Returns true if the given non-negative integer n is a power of two.
61  return n != 0 && (n & (n - 1)) == 0;
62  }
63 
64  //============================================================================
65  // Method Description:
76  template<typename IntType, enable_if_t<is_integral_v<IntType>, int> = 0>
77  std::size_t nextPowerOfTwo(IntType n)
78  {
79  if (n < 0)
80  {
81  throw std::invalid_argument("Input value must be greater than or equal to zero.");
82  }
83 
84  if (isPowerOfTwo(n))
85  {
86  return static_cast<std::size_t>(n) << 1;
87  }
88 
89  return static_cast<std::size_t>(std::pow(2, std::ceil(std::log2(n))));
90  }
91 
92  //============================================================================
93  // Method Description:
100  template<typename IntType, enable_if_t<is_integral_v<IntType>, int> = 0>
101  std::vector<std::size_t> powersOfTwo(IntType n)
102  {
103  auto i = std::size_t{ 0 };
104  auto power = std::size_t{ 1 };
105  auto powers = std::vector<std::size_t>();
106  powers.reserve(n);
107 
108  while (i < static_cast<std::size_t>(n))
109  {
110  powers.push_back(power);
111  power <<= 1;
112  ++i;
113  }
114 
115  return powers;
116  }
117 
118  //============================================================================
119  // Method Description:
127  template<typename IntType, enable_if_t<is_integral_v<IntType>, int> = 0>
128  std::size_t numSecdedParityBitsNeeded(IntType numDataBits)
129  {
130  const auto n = nextPowerOfTwo(numDataBits);
131  const auto lowerBin = static_cast<std::size_t>(std::floor(std::log2(n)));
132  const auto upperBin = lowerBin + 1;
133  const auto dataBitBoundary = n - lowerBin - 1;
134  const auto numParityBits = numDataBits <= dataBitBoundary ? lowerBin + 1 : upperBin + 1;
135 
136  if (!isPowerOfTwo(numParityBits + numDataBits))
137  {
138  throw std::runtime_error(
139  "input number of data bits is not a valid Hamming SECDED code configuration.");
140  }
141 
142  return numParityBits;
143  }
144 
145  //============================================================================
146  // Method Description:
157  template<typename IntType1,
158  typename IntType2,
161  std::vector<std::size_t> dataBitsCovered(IntType1 numDataBits, IntType2 parityBit)
162  {
163  if (!isPowerOfTwo(parityBit))
164  {
165  throw std::invalid_argument("All hamming parity bits are indexed by powers of two.");
166  }
167 
168  std::size_t dataIndex = 1; // bit we're currently at in the DATA bitstring
169  std::size_t totalIndex = 3; // bit we're currently at in the OVERALL bitstring
170  auto parityBit_ = static_cast<std::size_t>(parityBit);
171 
172  auto indices = std::vector<std::size_t>();
173  indices.reserve(numDataBits); // worst case
174 
175  while (dataIndex <= static_cast<std::size_t>(numDataBits))
176  {
177  const auto currentBitIsData = !isPowerOfTwo(totalIndex);
178  if (currentBitIsData && (totalIndex % (parityBit_ << 1)) >= parityBit_)
179  {
180  indices.push_back(dataIndex - 1); // adjust output to be zero indexed
181  }
182 
183  dataIndex += currentBitIsData ? 1 : 0;
184  ++totalIndex;
185  }
186 
187  return indices;
188  }
189 
190  //============================================================================
191  // Method Description:
197  template<std::size_t DataBits>
198  constexpr bool calculateParity(const std::bitset<DataBits>& data) noexcept
199  {
200  bool parity = false;
201  for (std::size_t i = 0; i < DataBits - 1; ++i)
202  {
203  parity ^= data[i];
204  }
205 
206  return parity;
207  }
208 
209  //============================================================================
210  // Method Description:
216  inline bool calculateParity(const boost::dynamic_bitset<>& data) noexcept
217  {
218  bool parity = false;
219  for (std::size_t i = 0; i < data.size() - 1; ++i)
220  {
221  parity ^= data[i];
222  }
223 
224  return parity;
225  }
226 
227  //============================================================================
228  // Method Description:
238  template<std::size_t DataBits, typename IntType, enable_if_t<is_integral_v<IntType>, int> = 0>
239  bool calculateParity(const std::bitset<DataBits>& data, IntType parityBit)
240  {
241  bool parity = false;
242  for (const auto i : dataBitsCovered(DataBits, parityBit))
243  {
244  parity ^= data[i];
245  }
246 
247  return parity;
248  }
249 
250  //============================================================================
251  // Method Description:
258  template<std::size_t DataBits,
259  std::size_t EncodedBits,
261  std::size_t checkBitsConsistent()
262  {
263  const auto numParityBits = detail::numSecdedParityBitsNeeded(DataBits);
264  if (numParityBits + DataBits != EncodedBits)
265  {
266  throw std::runtime_error("DataBits and EncodedBits are not consistent");
267  }
268 
269  return numParityBits;
270  }
271 
272  //============================================================================
273  // Method Description:
280  template<std::size_t DataBits,
281  std::size_t EncodedBits,
283  std::bitset<DataBits> extractData(const std::bitset<EncodedBits>& encodedBits) noexcept
284  {
285  auto dataBits = std::bitset<DataBits>();
286 
287  std::size_t dataIndex = 0;
288  for (std::size_t encodedIndex = 0; encodedIndex < EncodedBits; ++encodedIndex)
289  {
290  if (!isPowerOfTwo(encodedIndex + 1))
291  {
292  dataBits[dataIndex++] = encodedBits[encodedIndex];
293  if (dataIndex == DataBits)
294  {
295  break;
296  }
297  }
298  }
299 
300  return dataBits;
301  }
302  } // namespace detail
303 
304  //============================================================================
305  // Method Description:
312  template<std::size_t DataBits>
313  boost::dynamic_bitset<> encode(const std::bitset<DataBits>& dataBits)
314  {
315  const auto numParityBits = detail::numSecdedParityBitsNeeded(DataBits);
316  const auto numEncodedBits = numParityBits + DataBits;
317 
318  auto encodedBits = boost::dynamic_bitset<>(numEncodedBits);
319 
320  // set the parity bits
321  for (const auto parityBit : detail::powersOfTwo(
322  numParityBits - 1)) // -1 because overall parity will be calculated seperately later
323  {
324  encodedBits[parityBit - 1] = detail::calculateParity(dataBits, parityBit);
325  }
326 
327  // set the data bits, switch to 1 based to make things easier for isPowerOfTwo
328  std::size_t dataBitIndex = 0;
329  for (std::size_t bitIndex = 1; bitIndex <= numEncodedBits - 1;
330  ++bitIndex) // -1 to account for the overall parity bit
331  {
332  if (!detail::isPowerOfTwo(bitIndex))
333  {
334  encodedBits[bitIndex - 1] = dataBits[dataBitIndex++];
335  }
336  }
337 
338  // compute and set overall parity for the entire encoded data (not including the overall parity bit itself)
339  encodedBits[numEncodedBits - 1] = detail::calculateParity(encodedBits); // overall parity at the end
340 
341  // all done!
342  return encodedBits;
343  }
344 
345  //============================================================================
346  // Method Description:
356  template<std::size_t DataBits,
357  std::size_t EncodedBits,
359  int decode(std::bitset<EncodedBits> encodedBits, std::bitset<DataBits>& decodedBits)
360  {
361  const auto numParityBits = detail::checkBitsConsistent<DataBits, EncodedBits>();
362 
363  // the data bits, which may be corrupted
364  decodedBits = detail::extractData<DataBits>(encodedBits);
365 
366  // check the overall parity bit
367  const auto overallExpected = detail::calculateParity(encodedBits);
368  const auto overallActual = encodedBits[EncodedBits - 1];
369  const auto overallCorrect = overallExpected == overallActual;
370 
371  // check individual parities - each parity bit's index (besides overall parity) is a power of two
372  std::size_t indexOfError = 0;
373  for (const auto parityBit : detail::powersOfTwo(numParityBits - 1))
374  {
375  const auto expected = detail::calculateParity(decodedBits, parityBit);
376  const auto actual = encodedBits[parityBit - 1]; // -1 because parityBit is 1 based
377  if (expected != actual)
378  {
379  indexOfError += parityBit;
380  }
381  }
382 
383  // attempt to repair a single flipped bit or throw exception if more than one
384  if (overallCorrect && indexOfError != 0)
385  {
386  // two errors found
387  return 2;
388  }
389  else if (!overallCorrect && indexOfError != 0)
390  {
391  // one error found, flip the bit in error and we're good
392  encodedBits.flip(indexOfError - 1);
393  decodedBits = detail::extractData<DataBits>(encodedBits);
394  return 1;
395  }
396 
397  return 0;
398  }
399  } // namespace edac
400 } // namespace nc
401 #endif // #ifndef NUMCPP_NO_USE_BOOST
std::bitset< DataBits > extractData(const std::bitset< EncodedBits > &encodedBits) noexcept
Definition: hammingEncode.hpp:283
std::size_t nextPowerOfTwo(IntType n)
Definition: hammingEncode.hpp:77
std::size_t numSecdedParityBitsNeeded(IntType numDataBits)
Definition: hammingEncode.hpp:128
constexpr bool isPowerOfTwo(IntType n) noexcept
Tests if value is a power of two.
Definition: hammingEncode.hpp:58
std::vector< std::size_t > dataBitsCovered(IntType1 numDataBits, IntType2 parityBit)
Definition: hammingEncode.hpp:161
constexpr bool calculateParity(const std::bitset< DataBits > &data) noexcept
Definition: hammingEncode.hpp:198
std::vector< std::size_t > powersOfTwo(IntType n)
Definition: hammingEncode.hpp:101
std::size_t checkBitsConsistent()
Definition: hammingEncode.hpp:261
int decode(std::bitset< EncodedBits > encodedBits, std::bitset< DataBits > &decodedBits)
Definition: hammingEncode.hpp:359
boost::dynamic_bitset encode(const std::bitset< DataBits > &dataBits)
Definition: hammingEncode.hpp:313
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
typename std::enable_if< B, T >::type enable_if_t
Definition: TypeTraits.hpp:40