sdsl/include/sdsl/uint256_t.hpp

Go to the documentation of this file.

/* sdsl - succinct data structures library
    Copyright (C) 2012 Simon Gog

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see http://www.gnu.org/licenses/ .
*/
#ifndef INCLUDED_SDSL_UINT256
#define INCLUDED_SDSL_UINT256

#include <iostream>
#include "bitmagic.hpp"
#include "uint128_t.hpp"

namespace sdsl
{

class uint256_t
{
    public:
        friend std::ostream& operator << (std::ostream&, const uint256_t&);
    private:
        uint64_t m_lo;
        uint64_t m_mid;
        uint128_t m_high;

    public:
        uint256_t(uint64_t lo=0, uint64_t mid=0,
                  uint128_t high=0):m_lo(lo),
            m_mid(mid),
            m_high(high) {}

        uint256_t(const uint256_t& x):m_lo(x.m_lo), m_mid(x.m_mid), m_high(x.m_high) {}

        uint16_t popcount() {
            return ((uint16_t)bit_magic::b1Cnt(m_lo)) + bit_magic::b1Cnt(m_mid)
                   + bit_magic::b1Cnt(m_high>>64) + bit_magic::b1Cnt(m_high);
        }

        uint16_t l1BP() {
            if (m_high == 0) {
                if (m_mid) {
                    return bit_magic::l1BP(m_mid) + 64;
                } else {
                    return bit_magic::l1BP(m_lo);
                }
            } else {
                uint64_t hh = (m_high >> 64);
                if (hh) {
                    return bit_magic::l1BP(hh) + 192;
                } else {
                    return bit_magic::l1BP(m_high) + 128;
                }
            }
        }

        uint16_t select(uint32_t i) {
            uint16_t x = 0;
            if ((x=bit_magic::b1Cnt(m_lo)) >= i) {
                return bit_magic::i1BP(m_lo, i);
            }
            i -= x;
            if ((x=bit_magic::b1Cnt(m_mid)) >= i) {
                return bit_magic::i1BP(m_mid, i) + 64;
            }
            i -= x;
            uint64_t hh = m_high >> 64;
            uint64_t lh = m_high;
            if ((x=bit_magic::b1Cnt(lh)) >= i) {
                return bit_magic::i1BP(lh, i) + 128;
            }
            i -= x;
            return bit_magic::i1BP(hh, i) + 192;
        }

        uint256_t& operator+=(const uint256_t& x) {
            uint128_t lo = (uint128_t)m_lo + x.m_lo;
            uint128_t mid = (uint128_t)m_mid + x.m_mid + (lo >> 64);
            m_lo = lo; m_mid = mid;
            m_high += x.m_high + (mid >> 64);
            return *this;
//                      return uint256_t(lo, mid, m_high + x.m_high + (mid >> 64));
        }

        uint256_t operator+(uint256_t x) {
            uint128_t lo = (uint128_t)m_lo + x.m_lo;
            uint128_t mid = (uint128_t)m_mid + x.m_mid + (lo >> 64);
            return uint256_t(lo, mid, m_high + x.m_high + (mid >> 64));
        }

        uint256_t operator-(uint256_t x) {
//                      add two's complement of x
            uint128_t lo = (uint128_t)m_lo + (~x.m_lo) + 1;
            uint128_t mid = (uint128_t)m_mid + (~x.m_mid) + (lo >> 64);
            return uint256_t(lo, mid, m_high + (~x.m_high) + (mid >> 64));
        }

        uint256_t& operator-=(const uint256_t& x) {
//                      add two's complement of x
            uint128_t lo = (uint128_t)m_lo + (~x.m_lo) + 1;
            uint128_t mid = (uint128_t)m_mid + (~x.m_mid) + (lo >> 64);
            m_lo = lo;
            m_mid = mid;
            m_high += (~x.m_high) + (mid >> 64);
            return *this;
        }


        uint256_t operator|(const uint256_t& x) {
            return uint256_t(m_lo|x.m_lo, m_mid|x.m_mid, m_high|x.m_high);
        }

        uint256_t& operator|=(const uint256_t& x) {
            m_lo |= x.m_lo; m_mid |= x.m_mid; m_high |= x.m_high;
            return *this;
        }

        uint256_t operator&(const uint256_t& x) {
            return uint256_t(m_lo&x.m_lo, m_mid&x.m_mid, m_high&x.m_high);
        }
        /* // is not needed since we can convert uint256_t to uint64_t
                        uint64_t operator&(uint64_t x){
                                return m_lo & x;
                        }
        */

        uint256_t operator<<(int x) {
            if (x < 128) {
                uint128_t high = m_high << x;
                uint128_t low  = (((uint128_t)m_mid<<64) | m_lo);
                high |= (low >> (128-x));
                low = low << x;
                return uint256_t(low, low>>64, high);
            } else { // x >= 128
                uint128_t high = (((uint128_t)m_mid<<64) | m_lo) << (x-128); // TODO: check x==128
                return uint256_t(0, 0, high);
            }
        }

        uint256_t operator>>(int x) {
            if (x < 128) {
                uint128_t low  = (((uint128_t)m_mid<<64) | m_lo) >> x;
                low |= ((m_high << (127-x))<<1);
                return uint256_t(low, low>>64, m_high>>x);
            } else { // x >= 128
                uint128_t low = (m_high >> (x-128)); // TODO: check x=128
                return uint256_t(low, low>>64, 0);
            }
        }

        uint256_t& operator=(const uint64_t& x) {
            m_high = 0;
            m_mid = 0;
            m_lo = x;
            return *this;
        }

        bool operator==(const uint256_t& x) const {
            return (m_lo == x.m_lo) and (m_mid == x.m_mid) and (m_high == x.m_high);
        }

        bool operator!=(const uint256_t& x) const {
            return !(*this == x);
        }

        bool operator>=(const uint256_t& x) const {
            if (m_high != x.m_high) {
                return m_high > x.m_high;
            }
            if (m_mid != x.m_mid) {
                return m_mid > x.m_mid;
            } else {
                return m_lo >= x.m_lo;
            }
        }

        bool operator<=(const uint256_t& x) const {
            if (m_high != x.m_high) {
                return m_high < x.m_high;
            }
            if (m_mid != x.m_mid) {
                return m_mid < x.m_mid;
            } else {
                return m_lo <= x.m_lo;
            }
        }

        bool operator>(const uint256_t& x) const {
            if (m_high != x.m_high) {
                return m_high > x.m_high;
            }
            if (m_mid != x.m_mid) {
                return m_mid > x.m_mid;
            } else {
                return m_lo > x.m_lo;
            }
        }

        bool operator>(const uint64_t& x) const {
            if (m_high > 0 or m_mid > 0) {
                return true;
            }
            return m_lo > x;
        }

        bool operator<(const uint256_t& x) const {
            if (m_high != x.m_high) {
                return m_high < x.m_high;
            }
            if (m_mid != x.m_mid) {
                return m_mid < x.m_mid;
            } else {
                return m_lo < x.m_lo;
            }
        }

        operator uint64_t() {
            return m_lo;
        }
};

std::ostream& operator<<(std::ostream& os, const uint256_t& x)
{
    uint64_t X[4] = {(uint64_t)(x.m_high >> 64), (uint64_t)x.m_high, x.m_mid, x.m_lo};
    for (int j=0; j < 4; ++j) {
        for (int i=0; i < 16; ++i) {
            os << std::hex << ((X[j]>>60)&0xFULL) << std::dec;
            X[j] <<= 4;
        }
    }
    return os;
}

} // end namespace

#endif