bitstring.h

Go to the documentation of this file.

/*
    BITSTRING.H
    -----------
    Copyright (c) 2016 Andrew Trotman
    Released under the 2-clause BSD license (See:https://en.wikipedia.org/wiki/BSD_licenses)

    Originally from the ATIRE codebase (where it was also written by Andrew Trotman)
*/
#pragma once

#include <stdint.h>

#include <vector>

namespace JASS
    {
    /*
        CLASS BITSTRING
        ---------------
    */
    class bitstring
        {
        /*
            CONSTANTS
            ---------
        */
        protected:
            /*
                BITSTRING::ACTION
                -----------------
            */
            enum action
                {
                OR,             
                XOR,                
                AND,                
                AND_NOT         
                };
            
        /*
            TYPES
            -----
        */
        protected:
            typedef uint64_t bitstring_word;        // this is the size of word used for Boolean operatons (and so storage is rounded up to units of this)

        /*
            MEMBERS
            -------
        */
        protected:
            std::vector<uint8_t> bits;              
            
            size_t bits_long;                           

        /*
            METHODS
            -------
        */
        protected:
            /*
                BITSTRING::OPERATION()
                ----------------------
            */
            virtual void operation(action op, bitstring &a, bitstring &b, bitstring &c);

        public:
            /*
                BITSTRING::BITSTRING()
                ----------------------
            */
            bitstring() : bits_long(0)
                {
                // nothing
                }
            /*
                BITSTRING::~BITSTRING()
                ----------------------
            */
            virtual ~bitstring()
                {
                // nothing
                }
            
            /*
                BITSTRING::POPCOUNT()
                ---------------------
            */
            inline static size_t popcount(uint64_t value)
                {
                value = value - ((value >> 1) & 0x5555555555555555);
                value = (value & 0x3333333333333333) + ((value >> 2) & 0x3333333333333333);
                return (((value + (value >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56;
                }

            /*
                BITSTRING::POPCOUNT()
                ---------------------
            */
            inline static size_t popcount(uint32_t value)
                {
                value = value - ((value >> 1) & 0x55555555);
                value = (value & 0x33333333) + ((value >> 2) & 0x33333333);
                return (((value + (value >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
                }

            /*
                BITSTRING::POPCOUNT()
                ---------------------
            */
            inline static size_t popcount(uint16_t value)
                {
                value = value - ((value >> 1) & 0x5555);
                value = (value & 0x3333) + ((value >> 2) & 0x3333);
                /*
                    Is this a compiler bug?  we can't do a single line return and must instead do a two line return on Xcode 8.3.3
                */
//              return (((value + (value >> 4)) & 0xF0F) * 0x101) >> 8;
                value = (((value + (value >> 4)) & 0xF0F) * 0x101);
                return value >> 8;
                }

            /*
                BITSTRING::POPCOUNT()
                ---------------------
            */
            inline static size_t popcount(uint8_t value)
                {
                value = value - ((value >> 1) & 0x55u);
                value = (value & 0x33u) + ((value >> 2) & 0x33u);
                return (((value + (value >> 4)) & 0xFu) * 0x1);
                }

            /*
                BITSTRING::RESIZE()
                -------------------
            */
            void resize(size_t length_in_bits);

            /*
                BITSTRING::SIZE()
                -----------------
            */
            size_t size(void) const
                {
                return bits_long;
                }

            /*
                BITSTRING::UNSAFE_SETBIT()
                --------------------------
            */
            inline void unsafe_setbit(size_t position)
                {
                bits[position >> 3] |= 1 << (position & 7);
                }
            
            /*
                BITSTRING::UNSAFE_UNSETBIT()
                ----------------------------
            */
            inline void unsafe_unsetbit(size_t position)
                {
                bits[position >> 3] &= ~(1 << (position & 7));
                }
            
            /*
                BITSTRING::UNSAFE_GETBIT()
                --------------------------
                Return the value of the bit at position (either 0 or 1)
            */
            bool unsafe_getbit(size_t position) const
                {
                return (bits[position >> 3] >> (position & 7)) & 0x01;
                }


            /*
                BITSTRING::SETBIT()
                -------------------
            */
            inline void setbit(size_t position)
                {
                if (position < bits_long)
                    unsafe_setbit(position);
                }
            
            /*
                BITSTRING::UNSETBIT()
                ---------------------
            */
            inline void unsetbit(size_t position)
                {
                if (position < bits_long)
                    unsafe_unsetbit(position);
                }
            
            /*
                BITSTRING::GETBIT()
                -------------------
                Return the value of the bit at position (either 0 or 1)
            */
            bool getbit(size_t position) const
                {
                return position < bits_long ? unsafe_getbit(position) : 0;
                }

            /*
                BITSTRING::BIT_OR()
                -------------------
            */
            inline void bit_or(bitstring &answer, bitstring &with)
                {
                operation(OR, answer, *this, with);
                }
            
            /*
                BITSTRING::BIT_XOR()
                --------------------
            */
            inline void bit_xor(bitstring &answer, bitstring &with)
                {
                operation(XOR, answer, *this, with);
                }
            
            
            /*
                BITSTRING::BIT_AND()
                --------------------
            */
            inline void bit_and(bitstring &answer, bitstring &with)
                {
                operation(AND, answer, *this, with);
                }
            

            /*
                BITSTRING::BIT_AND_NOT()
                ------------------------
            */
            inline void bit_and_not(bitstring &answer, bitstring &with)
                {
                operation(AND_NOT, answer, *this, with);
                }

            /*
                BITSTRING::POPCOUNT()
                ---------------------
            */
            
            size_t popcount(void) const;

            /*
                BITSTRING::INDEX()
                ------------------
            */
            size_t index(size_t which);

            /*
                BITSTRING::ZERO()
                -----------------
            */
            void zero(void);

            /*
                BITSTRING::ONE()
                ----------------
            */
            void one(void);
            
            /*
                BITSTRING::SERIALISE()
                ----------------------
            */
            uint8_t *serialise(size_t &length)
                {
                length = bits.size();
                return &bits[0];
                }
            
            /*
                BITSTRING::UNITTEST()
                ---------------------
            */
            static void unittest(void);
        };
}