source: source/ariba/utility/types/Identifier.h@ 5665

// [License]
// The Ariba-Underlay Copyright
//
// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)
//
// Institute of Telematics
// UniversitÀt Karlsruhe (TH)
// Zirkel 2, 76128 Karlsruhe
// Germany
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ARIBA PROJECT OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// The views and conclusions contained in the software and documentation
// are those of the authors and should not be interpreted as representing
// official policies, either expressed or implied, of the Institute of
// Telematics.
// [License]

#ifndef IDENTIFIER_H_
#define IDENTIFIER_H_

#include <memory>
#include <string>
#include <cassert>
#include <iostream>
#include <gmp.h>
#include <boost/cstdint.hpp>
#include "ariba/utility/logging/Logging.h"
#include "ariba/utility/types/Address.h"
#include "ariba/utility/serialization.h"

/**< maximum length of the key */
#define MAX_KEYLENGTH 192

namespace ariba {
namespace utility {

using_serialization;

class IdentifierBit;

/**
 * An abstract address class for identifier.<br/>
 *
 * This class is the base for all identifier classes.
 */
class Identifier: public Address {
        VSERIALIZEABLE;
        use_logging_h( Identifier );
public:

        //-------------------------------------------------------------------------
        // virtual function from Address
        //-------------------------------------------------------------------------

        virtual void clearAddress();
        virtual bool setAddress(string address);
        virtual string getAddress() const;

        //-------------------------------------------------------------------------
        // constants
        //-------------------------------------------------------------------------

        static const Identifier UNSPECIFIED_KEY; /**< Identifier without defined key */
        static const Identifier ZERO; /**< Identifier with key initialized as 0 */
        static const Identifier ONE; /**< Identifier with key initialized as 1 */

        //-------------------------------------------------------------------------
        // construction and destruction
        //-------------------------------------------------------------------------

        /**
         * Default constructor
         *
         * Contructs an unspecified overlay key
         */
        Identifier();

        /**
         * Constructs an overlay key initialized with a common integer
         *
         * @param num The integer to initialize this key with
         */
        Identifier(uint32_t num);

        /**
         * Constructs a key out of a buffer
         * @param buffer Source buffer
         * @param size Buffer size (in bytes)
         */
        Identifier(const unsigned char* buffer, uint size);

        /**
         * Constructs a key out of a string number.
         */
        Identifier(const std::string& str, uint base = 16);

        /**
         * Copy constructor.
         *
         * @param rhs The key to copy.
         */
        Identifier(const Identifier& rhs);

        /**
         * Default destructor.
         *
         * Does nothing ATM.
         */
        virtual ~Identifier();

        //-------------------------------------------------------------------------
        // string representations & node key attributes
        //-------------------------------------------------------------------------

        /**
         * Returns a string representation of this key
         *
         * @return String representation of this key
         */
        virtual std::string toString(uint base = 16) const;

        /**
         * Common stdc++ console output method
         */
        friend std::ostream& operator<<(std::ostream& os, const Identifier& c);

        /**
         * Returns true, if the key is unspecified
         *
         * @return Returns true, if key is unspecified
         */
        bool isUnspecified() const;

        //-------------------------------------------------------------------------
        // operators
        //-------------------------------------------------------------------------

        /**
         * compares this to a given Identifier
         *
         * @param compKey the the Identifier to compare this to
         * @return true if compKey->key is smaller than this->key, else false
         */
        bool operator<(const Identifier& compKey) const;

        /**
         * compares this to a given Identifier
         *
         * @param compKey the the Identifier to compare this to
         * @return true if compKey->key is greater than this->key, else false
         */
        bool operator>(const Identifier& compKey) const;

        /**
         * compares this to a given Identifier
         *
         * @param compKey the the Identifier to compare this to
         * @return true if compKey->key is smaller than or equal to this->key, else false
         */
        bool operator<=(const Identifier& compKey) const;

        /**
         * compares this to a given Identifier
         *
         * @param compKey the the Identifier to compare this to
         * @return true if compKey->key is greater than or equal to this->key, else false
         */
        bool operator>=(const Identifier& compKey) const;

        /**
         * compares this to a given Identifier
         *
         * @param compKey the the Identifier to compare this to
         * @return true if compKey->key is equal to this->key, else false
         */
        bool operator==(const Identifier& compKey) const;

        /**
         * compares this to a given Identifier
         *
         * @param compKey the the Identifier to compare this to
         * @return true if compKey->key is not equal to this->key, else false
         */
        bool operator!=(const Identifier& compKey) const;

        /**
         * Unifies all compare operations in one method
         *
         * @param compKey key to compare with
         * @return int -1 if smaller, 0 if equal, 1 if greater
         */
        int compareTo(const Identifier& compKey) const;

        /**
         * assigns Identifier of rhs to this->key
         *
         * @param rhs the Identifier with the defined key
         * @return this Identifier object
         */
        Identifier& operator=(const Identifier& rhs);

        /**
         * substracts 1 from this->key
         *
         * @return this Identifier object
         */
        Identifier& operator--();

        /**
         * adds 1 to this->key
         *
         * @return this Identifier object
         */
        Identifier& operator++();

        /**
         * adds rhs->key to this->key
         *
         * @param rhs the Identifier with the defined key
         * @return this Identifier object
         */
        Identifier& operator+=(const Identifier& rhs);

        /**
         * substracts rhs->key from this->key
         *
         * @param rhs the Identifier with the defined key
         * @return this Identifier object
         */
        Identifier& operator-=(const Identifier& rhs);

        /**
         * adds rhs->key to this->key
         *
         * @param rhs the Identifier with the defined key
         * @return this Identifier object
         */
        Identifier operator+(const Identifier& rhs) const;

        /**
         * substracts rhs->key from this->key
         *
         * @param rhs the Identifier with the defined key
         * @return this Identifier object
         */
        Identifier operator-(const Identifier& rhs) const;

        /**
         * substracts 1 from this->key
         *
         * @return this Identifier object
         */
        Identifier operator--(int);

        /**
         * adds 1 to this->key
         *
         * @return this Identifier object
         */
        Identifier operator++(int);

        /**
         * bitwise shift right
         *
         * @param num number of bits to shift
         * @return this Identifier object
         */
        Identifier operator>>(uint num) const;

        /**
         * bitwise shift left
         *
         * @param num number of bits to shift
         * @return this Identifier object
         */
        Identifier operator<<(uint num) const;

        /**
         * bitwise AND of rhs->key and this->key
         *
         * @param rhs the Identifier AND is calculated with
         * @return this Identifier object
         */
        Identifier operator&(const Identifier& rhs) const;

        /**
         * bitwise OR of rhs->key and this->key
         *
         * @param rhs the Identifier OR is calculated with
         * @return this Identifier object
         */
        Identifier operator|(const Identifier& rhs) const;

        /**
         * bitwise XOR of rhs->key and this->key
         *
         * @param rhs the Identifier XOR is calculated with
         * @return this Identifier object
         */
        Identifier operator^(const Identifier& rhs) const;

        /**
         * bitwise NOT of this->key
         *
         * @return this Identifier object
         */
        Identifier operator~() const;

        /**
         * returns the n-th bit of this->key
         *
         * @param n the position of the returned bit
         * @return the bit on position n in this->key
         */
        IdentifierBit operator[](uint n);

        /**
         * sets a bit of this->key
         *
         * @param pos the position of the bit to set
         * @param value new value for bit at position pos
         * @return *this
         */
        Identifier& setBitAt(uint pos, bool value);

        //-------------------------------------------------------------------------
        // additional math
        //-------------------------------------------------------------------------

        /**
         * Returns a sub integer at position p with n-bits. p is counted starting
         * from the least significant bit of the key as bit 0. Bit p of the key
         * becomes bit 0 of the returned integer.
         *
         * @param p the position of the sub-integer
         * @param n the number of bits to be returned (max.32)
         * @return The sub-integer.
         */
        uint32_t get(uint p, uint n) const;

        /**
         * Returns a hash value for the key
         *
         * @return size_t The hash value
         */
        size_t hash() const;

        /**
         * Returns the position of the msb in this key, which represents
         * just the logarithm to base 2.
         *
         * @return The logarithm to base 2 of this key.
         */
        int log_2() const;

        /**
         * Fills the suffix starting at pos with random bits to lsb.
         *
         * @param pos
         * @return Identifier
         */
        Identifier randomSuffix(uint pos) const;

        /**
         * Fills the prefix starting at pos with random bits to msb.
         *
         * @param pos
         * @return Identifier
         */
        Identifier randomPrefix(uint pos) const;

        /**
         * Calculates the number of equal bits from the left with another
         * Key (shared prefix length)
         *
         * @param compKey the Key to compare with
         * @return length of shared prefix
         */
        uint sharedPrefixLength(const Identifier& compKey) const;

        /**
         * Returns true, if this key is element of the interval (keyA, keyB)
         * on the ring.
         *
         * @param keyA The left border of the interval
         * @param keyB The right border of the interval
         * @return True, if the key is element of the interval (keyA, keyB)
         */
        bool isBetween(const Identifier& keyA, const Identifier& keyB) const;

        /**
         * Returns true, if this key is element of the interval (keyA, keyB]
         * on the ring.
         *
         * @param keyA The left border of the interval
         * @param keyB The right border of the interval
         * @return True, if the key is element of the interval (keyA, keyB]
         */
        bool isBetweenR(const Identifier& keyA, const Identifier& keyB) const;

        /**
         * Returns true, if this key is element of the interval [keyA, keyB)
         * on the ring.
         *
         * @param keyA The left border of the interval
         * @param keyB The right border of the interval
         * @return True, if the key is element of the interval [keyA, keyB)
         */
        bool isBetweenL(const Identifier& keyA, const Identifier& keyB) const;

        /**
         * Returns true, if this key is element of the interval [keyA, keyB]
         * on the ring.
         *
         * @param keyA The left border of the interval
         * @param keyB The right border of the interval
         * @return True, if the key is element of the interval [keyA, keyB]
         */
        bool isBetweenLR(const Identifier& keyA, const Identifier& keyB) const;

        //-------------------------------------------------------------------------
        // static methods
        //-------------------------------------------------------------------------

        /**
         * Set the length of an Identifier
         *
         * @param length keylength in bits
         */
        static void setKeyLength(uint length);

        /**
         * Returns the length in number of bits.
         *
         * @return The length in number of bits.
         */
        static uint getLength();

        /**
         * Returns a random key.
         *
         * @return A random key.
         */
        static Identifier random();

        /**
         * Returns the maximum key, i.e. a key filled with bit 1
         *
         * @return The maximum key, i.e. a key filled with bit 1
         */
        static Identifier max();


        // README: due to some problems with serialization the keylength
        // was changed to 192 bit! As none of the hashing functions
        // can provide 192 bit output, and we currently don't use any
        // hashing for identifiers in the demo at all ... this is all commented out!!
        /**
         * Returns a key with the SHA1 cryptographic hash of a
         * string
         *
         * @param value A string value.
         * @return SHA1 of value
         */
        static Identifier sha1(const string& value);

        static Identifier sha1(const uint8_t* value, size_t length );

        /**
         * Returns a key 2^exponent.
         *
         * @param exponent The exponent.
         * @return Key=2^exponent.
         */
        static Identifier pow2(uint exponent);

private:
        // private constants

        static uint keyLength; /**< actual length of the key */
        static uint aSize; /**< number of needed machine words to hold the key*/
        static mp_limb_t GMP_MSB_MASK; /**< bits to fill up if key does not
         exactly fit in one or more machine words */

        // private fields
        bool isUnspec; /**< is this->key unspecified? */

        void seed();

        static const size_t array_size = MAX_KEYLENGTH / (8 * sizeof(mp_limb_t))
                        + (MAX_KEYLENGTH % (8 * sizeof(mp_limb_t)) != 0 ? 1 : 0);

        /** the overlay key this object represents */
        mp_limb_t key[array_size + 1];

        // private "helper" methods
        /**
         * trims key after key operations
         */
        void trim();

        /**
         * set this->key to 0 and isUnspec to false
         */
        void clear();
};

/**
 * An auxiliary class for single bits in OverlayKey
 *
 * Allows statements like "key[n] = true"
 */
class IdentifierBit {
public:

        IdentifierBit(bool value, uint pos, Identifier* key) :
                bit(value), pos(pos), key(key) {
        }

        /** Converts to a boolean value */
        inline operator bool() {
                return bit;
        }

        /** Sets the corresponding bit to a boolean value
         * @param value value to set to
         */
        inline IdentifierBit& operator=(bool value) {
                key->setBitAt(pos, value);
                return *this;
        }

        inline IdentifierBit& operator^=(bool value) {
                key->setBitAt(pos, (*key)[pos] ^ value);
                return *this;
        }

private:

        bool bit;
        uint pos;
        Identifier* key;
};

}
} // namespace ariba, common

/* serializers */
sznBeginDefault( ariba::utility::Identifier, X ) {

        // calculate length of key
        uint16_t len = array_size*sizeof(mp_limb_t);
        uint8_t unspec = isUnspec;

        // only serialize the lower 16 bits of keyLength
        X && unspec && len;

        // serialize the identifier
        for (int i=array_size-1; i>=0; i--) X && key[i];

        // when deserializing set unspec flag
        if (X.isDeserializer()){
                isUnspec = unspec;
        }

} sznEnd();

#endif /* IDENTIFIER_H_ */