hammingEncode.hpp

Go to the documentation of this file.

 
 
#pragma once
 
#ifndef NUMCPP_NO_USE_BOOST
 
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <numeric>
#include <stdexcept>
#include <type_traits>
#include <vector>
 
#include "boost/dynamic_bitset.hpp"
 
#include "NumCpp/Core/Internal/TypeTraits.hpp"
 
namespace nc::edac
{
    namespace detail
    {
        //============================================================================
        // Method Description:
        template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
        constexpr bool isPowerOfTwo(IntType n) noexcept
        {
            // Returns true if the given non-negative integer n is a power of two.
            return n != 0 && (n & (n - 1)) == 0;
        }
 
        //============================================================================
        // Method Description:
        template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
        std::size_t nextPowerOfTwo(IntType n)
        {
            if (n < 0)
            {
                throw std::invalid_argument("Input value must be greater than or equal to zero.");
            }
 
            if (isPowerOfTwo(n))
            {
                return static_cast<std::size_t>(n) << 1;
            }
 
            return static_cast<std::size_t>(std::pow(2, std::ceil(std::log2(n))));
        }
 
        //============================================================================
        // Method Description:
        template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
        std::vector<std::size_t> powersOfTwo(IntType n)
        {
            auto i      = std::size_t{ 0 };
            auto power  = std::size_t{ 1 };
            auto powers = std::vector<std::size_t>();
            powers.reserve(n);
 
            while (i < static_cast<std::size_t>(n))
            {
                powers.push_back(power);
                power <<= 1;
                ++i;
            }
 
            return powers;
        }
 
        //============================================================================
        // Method Description:
        template<typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
        std::size_t numSecdedParityBitsNeeded(IntType numDataBits)
        {
            const auto n               = nextPowerOfTwo(numDataBits);
            const auto lowerBin        = static_cast<std::size_t>(std::floor(std::log2(n)));
            const auto upperBin        = lowerBin + 1;
            const auto dataBitBoundary = n - lowerBin - 1;
            const auto numParityBits   = numDataBits <= dataBitBoundary ? lowerBin + 1 : upperBin + 1;
 
            if (!isPowerOfTwo(numParityBits + numDataBits))
            {
                throw std::runtime_error("input number of data bits is not a valid Hamming SECDED code configuration.");
            }
 
            return numParityBits;
        }
 
        //============================================================================
        // Method Description:
        template<typename IntType1,
                 typename IntType2,
                 std::enable_if_t<std::is_integral_v<IntType1>, int> = 0,
                 std::enable_if_t<std::is_integral_v<IntType2>, int> = 0>
        std::vector<std::size_t> dataBitsCovered(IntType1 numDataBits, IntType2 parityBit)
        {
            if (!isPowerOfTwo(parityBit))
            {
                throw std::invalid_argument("All hamming parity bits are indexed by powers of two.");
            }
 
            std::size_t dataIndex  = 1; // bit we're currently at in the DATA bitstring
            std::size_t totalIndex = 3; // bit we're currently at in the OVERALL bitstring
            auto        parityBit_ = static_cast<std::size_t>(parityBit);
 
            auto indices = std::vector<std::size_t>();
            indices.reserve(numDataBits); // worst case
 
            while (dataIndex <= static_cast<std::size_t>(numDataBits))
            {
                const auto currentBitIsData = !isPowerOfTwo(totalIndex);
                if (currentBitIsData && (totalIndex % (parityBit_ << 1)) >= parityBit_)
                {
                    indices.push_back(dataIndex - 1); // adjust output to be zero indexed
                }
 
                dataIndex += currentBitIsData ? 1 : 0;
                ++totalIndex;
            }
 
            return indices;
        }
 
        //============================================================================
        // Method Description:
        template<std::size_t DataBits>
        constexpr bool calculateParity(const std::bitset<DataBits>& data) noexcept
        {
            bool parity = false;
            for (std::size_t i = 0; i < DataBits - 1; ++i)
            {
                parity ^= data[i];
            }
 
            return parity;
        }
 
        //============================================================================
        // Method Description:
        inline bool calculateParity(const boost::dynamic_bitset<>& data) noexcept
        {
            bool parity = false;
            for (std::size_t i = 0; i < data.size() - 1; ++i)
            {
                parity ^= data[i];
            }
 
            return parity;
        }
 
        //============================================================================
        // Method Description:
        template<std::size_t DataBits, typename IntType, std::enable_if_t<std::is_integral_v<IntType>, int> = 0>
        bool calculateParity(const std::bitset<DataBits>& data, IntType parityBit)
        {
            const auto bitsCovered = dataBitsCovered(DataBits, parityBit);
            return std::accumulate(bitsCovered.begin(),
                                   bitsCovered.end(),
                                   false,
                                   [&data](bool parity, const auto value) noexcept -> bool { return parity ^= value; });
        }
 
        //============================================================================
        // Method Description:
        template<std::size_t DataBits,
                 std::size_t EncodedBits,
                 std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0>
        std::size_t checkBitsConsistent()
        {
            const auto numParityBits = detail::numSecdedParityBitsNeeded(DataBits);
            if (numParityBits + DataBits != EncodedBits)
            {
                throw std::runtime_error("DataBits and EncodedBits are not consistent");
            }
 
            return numParityBits;
        }
 
        //============================================================================
        // Method Description:
        template<std::size_t DataBits,
                 std::size_t EncodedBits,
                 std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0>
        std::bitset<DataBits> extractData(const std::bitset<EncodedBits>& encodedBits) noexcept
        {
            auto dataBits = std::bitset<DataBits>();
 
            std::size_t dataIndex = 0;
            for (std::size_t encodedIndex = 0; encodedIndex < EncodedBits; ++encodedIndex)
            {
                if (!isPowerOfTwo(encodedIndex + 1))
                {
                    dataBits[dataIndex++] = encodedBits[encodedIndex];
                    if (dataIndex == DataBits)
                    {
                        break;
                    }
                }
            }
 
            return dataBits;
        }
    } // namespace detail
 
    //============================================================================
    // Method Description:
    template<std::size_t DataBits>
    boost::dynamic_bitset<> encode(const std::bitset<DataBits>& dataBits)
    {
        const auto numParityBits  = detail::numSecdedParityBitsNeeded(DataBits);
        const auto numEncodedBits = numParityBits + DataBits;
 
        auto encodedBits = boost::dynamic_bitset<>(numEncodedBits); // NOLINT(google-readability-casting)
 
        // set the parity bits
        for (const auto parityBit :
             detail::powersOfTwo(numParityBits - 1)) // -1 because overall parity will be calculated seperately later
        {
            encodedBits[parityBit - 1] = detail::calculateParity(dataBits, parityBit);
        }
 
        // set the data bits, switch to 1 based to make things easier for isPowerOfTwo
        std::size_t dataBitIndex = 0;
        for (std::size_t bitIndex = 1; bitIndex <= numEncodedBits - 1;
             ++bitIndex) // -1 to account for the overall parity bit
        {
            if (!detail::isPowerOfTwo(bitIndex))
            {
                encodedBits[bitIndex - 1] = dataBits[dataBitIndex++];
            }
        }
 
        // compute and set overall parity for the entire encoded data (not including the overall parity bit itself)
        encodedBits[numEncodedBits - 1] = detail::calculateParity(encodedBits); // overall parity at the end
 
        // all done!
        return encodedBits;
    }
 
    //============================================================================
    // Method Description:
    template<std::size_t DataBits,
             std::size_t EncodedBits,
             std::enable_if_t<greaterThan_v<EncodedBits, DataBits>, int> = 0>
    int decode(std::bitset<EncodedBits> encodedBits, std::bitset<DataBits>& decodedBits)
    {
        const auto numParityBits = detail::checkBitsConsistent<DataBits, EncodedBits>();
 
        // the data bits, which may be corrupted
        decodedBits = detail::extractData<DataBits>(encodedBits);
 
        // check the overall parity bit
        const auto overallExpected = detail::calculateParity(encodedBits);
        const auto overallActual   = encodedBits[EncodedBits - 1];
        const auto overallCorrect  = overallExpected == overallActual;
 
        // check individual parities - each parity bit's index (besides overall parity) is a power of two
        std::size_t indexOfError = 0;
        for (const auto parityBit : detail::powersOfTwo(numParityBits - 1))
        {
            const auto expected = detail::calculateParity(decodedBits, parityBit);
            const auto actual   = encodedBits[parityBit - 1]; // -1 because parityBit is 1 based
            if (expected != actual)
            {
                indexOfError += parityBit;
            }
        }
 
        // attempt to repair a single flipped bit or throw exception if more than one
        if (overallCorrect && indexOfError != 0)
        {
            // two errors found
            return 2;
        }
        else if (!overallCorrect && indexOfError != 0)
        {
            // one error found, flip the bit in error and we're good
            encodedBits.flip(indexOfError - 1);
            decodedBits = detail::extractData<DataBits>(encodedBits);
            return 1;
        }
 
        return 0;
    }
} // namespace nc::edac
#endif // #ifndef NUMCPP_NO_USE_BOOST