util.hpp

[詳解]

#ifndef MTTOOLBOX_UTIL_HPP
#define MTTOOLBOX_UTIL_HPP

//#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <inttypes.h>
#include <stdint.h>
#include <stdexcept>
#include <NTL/GF2X.h>

#if defined(USE_SHA)
#include <openssl/sha.h>
#endif

namespace MTToolBox {
    inline static int count_bit(uint16_t x);
    inline static int count_bit(uint32_t x);
    inline static int count_bit(uint64_t x);
    inline static uint32_t reverse_bit(uint32_t x);
    inline static uint64_t reverse_bit(uint64_t x);

    template<typename T>
    int bit_size() {
        return static_cast<int>(sizeof(T) * 8);
    }

    inline static void UNUSED_VARIABLE(void * x) {
        (void)x;
    }

    template<typename T>
    T floor2p(T n) {
        if (n == 1) {
            return 1;
        } else {
            return 2 * floor2p<T>(n / 2);
        }
    }

    inline static void print_binary(std::ostream& os,
                                    NTL::GF2X& poly,
                                    bool breakline = true) {
        using namespace NTL;
        if (deg(poly) < 0) {
            os << "0deg=-1" << std::endl;
            return;
        }
        for(int i = 0; i <= deg(poly); i++) {
            if(rep(coeff(poly, i)) == 1) {
                os << '1';
            } else {
                os << '0';
            }
            if (breakline && ((i % 32) == 31)) {
                os << std::endl;
            }
        }
        os << "deg=" << deg(poly) << std::endl;
    }

    template<typename T>
    int get_range(T input, int start, int end) {
        if (end < start) {
            //printf("get_range:%d, %d\n", start, end);
            std::cout << "get_range:" << start << ", " << end << std::endl;
            exit(0);
        }
        return input % (end - start + 1) + start;
    }

    template<typename T>
    void fill_table(T dist_tbl[], T src_tbl[], int size) {
        for(int i = 1; i < size; i++) {
            for(int j = 1, k = 0; j <= i; j <<= 1, k++) {
                if (i & j) {
                    dist_tbl[i] ^= src_tbl[k];
                }
            }
        }
    }

#if defined(USE_SHA)

    inline static void poly_sha1(std::string& str, const NTL::GF2X& poly) {
        using namespace NTL;
        using namespace std;
        SHA_CTX ctx;
        SHA1_Init(&ctx);
        if (deg(poly) < 0) {
            SHA1_Update(&ctx, "-1", 2);
        }
        for(int i = 0; i <= deg(poly); i++) {
            if(rep(coeff(poly, i)) == 1) {
                SHA1_Update(&ctx, "1", 1);
            } else {
                SHA1_Update(&ctx, "0", 1);
            }
        }
        unsigned char md[SHA_DIGEST_LENGTH];
        SHA1_Final(md, &ctx);
        stringstream ss;
        for (int i = 0; i < SHA_DIGEST_LENGTH; i++) {
            ss << setfill('0') << setw(2) << hex
               << static_cast<int>(md[i]);
        }
        ss >> str;
    }
#endif

    static inline int calc_1pos(uint16_t x)
    {
        if (x == 0) {
            return -1;
        }
        int16_t y = (int16_t)x;
        y = count_bit((uint16_t)((y & -y) - 1));
        return 15 - y;
    }

    static inline int calc_1pos(uint32_t x)
    {
        if (x == 0) {
            return -1;
        }
        int32_t y = (int32_t)x;
        y = count_bit((uint32_t)(y & -y) - 1);
        return 31 - y;
    }

    static inline int calc_1pos(uint64_t x)
    {
        if (x == 0) {
            return -1;
        }
        int64_t y = (int64_t)x;
        y = count_bit((uint64_t)(y & -y) - 1);
        return 63 - y;
    }

    inline static int count_bit(uint16_t x) {
        x -= (x >> 1) & UINT16_C(0x5555);
        x = ((x >> 2) & UINT16_C(0x3333)) + (x & UINT16_C(0x3333));
        x = ((x >> 4) + x) & UINT16_C(0x0f0f);
        x += (x >> 8);
        return (int)(x & 0x1f);
    }

    inline static int count_bit(uint32_t x) {
        x -= (x >> 1) & UINT32_C(0x55555555);
        x = ((x >> 2) & UINT32_C(0x33333333)) + (x & UINT32_C(0x33333333));
        x = ((x >> 4) + x) & UINT32_C(0x0f0f0f0f);
        x += (x >> 8);
        x += (x >> 16);
        return (int)(x & 0x3f);
    }

    inline static int count_bit(uint64_t x) {
        x -= (x >> 1) & UINT64_C(0x5555555555555555);
        x = ((x >> 2) & UINT64_C(0x3333333333333333))
            + (x & UINT64_C(0x3333333333333333));
        x = ((x >> 4) + x) & UINT64_C(0x0f0f0f0f0f0f0f0f);
        x += (x >> 8);
        x += (x >> 16);
        x += (x >> 32);
        return (int)(x & 0x7f);
    }

    inline static uint32_t reverse_bit(uint32_t x)
    {
        uint32_t y = 0x55555555;
        x = (((x >> 1) & y) | ((x & y) << 1));
        y = 0x33333333;
        x = (((x >> 2) & y) | ((x & y) << 2));
        y = 0x0f0f0f0f;
        x = (((x >> 4) & y) | ((x & y) << 4));
        y = 0x00ff00ff;
        x = (((x >> 8) & y) | ((x & y) << 8));
        return((x >> 16) | (x << 16));
    }

    inline static uint64_t reverse_bit(uint64_t x)
    {
        uint64_t y = UINT64_C(0x5555555555555555);
        x = (((x >> 1) & y) | ((x & y) << 1));
        y = UINT64_C(0x3333333333333333);
        x = (((x >> 2) & y) | ((x & y) << 2));
        y = UINT64_C(0x0f0f0f0f0f0f0f0f);
        x = (((x >> 4) & y) | ((x & y) << 4));
        y = UINT64_C(0x00ff00ff00ff00ff);
        x = (((x >> 8) & y) | ((x & y) << 8));
        y = UINT64_C(0x0000ffff0000ffff);
        x = (((x >> 16) & y) | ((x & y) << 16));
        return((x >> 32) | (x << 32));
    }

    inline static void LCM(NTL::GF2X& lcm, const NTL::GF2X& x,
                           const NTL::GF2X& y) {
        using namespace NTL;
        GF2X gcd;
        GCD(gcd, x, y);
        mul(lcm, x, y);
        lcm /= gcd;
    }

    template<typename U>
    inline static void toGF2Vec(NTL::vec_GF2& result, U value) {
        U mask = 1;
        int bitSize = bit_size<U>();
        result.SetLength(bitSize);
        mask = mask << (bitSize - 1);
        for (int i = 0; i < bitSize; i++) {
            if (value & mask) {
                result.put(i, 1);
            } else {
                result.put(i, 0);
            }
            mask = mask >> 1;
        }
    }


    template<typename U>
    inline U getOne() {
        return static_cast<U>(1);
    }

    template<typename U>
    inline void setZero(U& x) {
        x = 0;
    }

    template<typename U>
    inline unsigned int getBitOfPos(U bits, int pos) {
        return (bits >> pos) & 1;
    }

    template<typename U>
    inline void setBitOfPos(U *bits, int pos, unsigned int b) {
        b = b & 1;
        U mask = ~(static_cast<U>(1) << pos);
        *bits &= mask;
        *bits |= static_cast<U>(b) << pos;
    }

    template<typename U>
    inline static U fromGF2Vec(NTL::vec_GF2& value) {
        U result;
        setZero(result);
        U mask;
        setZero(mask);
        int bitSize = bit_size<U>();
        int pos = bitSize - 1;
        setBitOfPos(&mask, pos, 1);
        for (int i = 0; i < bitSize; i++) {
            if (!IsZero(value[i])) {
                result |= mask;
            }
            pos--;
            setZero(mask);
            setBitOfPos(&mask, pos, 1);
        }
        return result;
    }

    template<typename U>
    inline bool isZero(U x) {
        return x == 0;
    }

    template<typename U, typename V>
    inline U convert(V x) {
        return static_cast<U>(x);
    }
}
#endif //MTTOOLBOX_UTIL_HPP