/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

/*

 * Copyright (c) 2008 University of Washington

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License version 2 as

 * published by the Free Software Foundation;

 *

 * 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, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 */

#include <list>

#include "ns3/abort.h"

#include "ns3/assert.h"

#include "ns3/log.h"

#include "ns3/simulation-singleton.h"

#include "ipv4-address-generator.h"

namespace ns3 {

NS_LOG_COMPONENT_DEFINE ("Ipv4AddressGenerator");

/**

 * \internal

 * \ingroup address

 *

 * \brief Implementation class of Ipv4AddressGenerator

 * This generator assigns addresses sequentially from a provided

 * network address; used in topology code. It also keeps track of all

 * addresses assigned to perform duplicate detection.

 */

class Ipv4AddressGeneratorImpl

{

public:

  Ipv4AddressGeneratorImpl ();

  virtual ~Ipv4AddressGeneratorImpl ();

  /**

   * \internal

   * \brief Initialise the base network, mask and address for the generator

   *

   * The first call to NextAddress() or GetAddress() will return the

   * value passed in.

   *

   * \param net The network for the base Ipv4Address

   * \param mask The network mask of the base Ipv4Address

   * \param addr The base address used for initialization

   */

  void Init (const Ipv4Address net, const Ipv4Mask mask, 

             const Ipv4Address addr);

  /**

   * \internal

   * \brief Get the current network of the given Ipv4Mask

   *

   * Does not change the internal state; this just peeks at the current

   * network

   *

   * \param mask The Ipv4Mask for the current network

   * \returns the IPv4 address of the current network

   */

  Ipv4Address GetNetwork (const Ipv4Mask mask) const;

  /**

   * \internal

   * \brief Get the next network according to the given Ipv4Mask

   *

   * This operation is a pre-increment, meaning that the internal state

   * is changed before returning the new network address.

   *

   * This also resets the address to the base address that was

   * used for initialization.

   *

   * \param mask The Ipv4Mask used to set the next network

   * \returns the IPv4 address of the next network

   */

  Ipv4Address NextNetwork (const Ipv4Mask mask);

  /**

   * \internal

   * \brief Set the address for the given mask

   *

   * \param addr The address to set for the current mask

   * \param mask The Ipv4Mask whose address is to be set

   */

  void InitAddress (const Ipv4Address addr, const Ipv4Mask mask);

  /**

   * \internal

   * \brief Allocate the next Ipv4Address for the configured network and mask

   *

   * This operation is a post-increment, meaning that the first address

   * allocated will be the one that was initially configured.

   *

   * \param mask The Ipv4Mask for the current network

   * \returns the IPv4 address

   */

  Ipv4Address NextAddress (const Ipv4Mask mask);

  /**

   * \internal

   * \brief Get the Ipv4Address that will be allocated upon NextAddress ()

   *

   * Does not change the internal state; just is used to peek the next

   * address that will be allocated upon NextAddress ()

   *

   * \param mask The Ipv4Mask for the current network

   * \returns the IPv4 address

   */

  Ipv4Address GetAddress (const Ipv4Mask mask) const;

  /**

   * \internal

   * \brief Reset the networks and Ipv4Address to zero

   */

  void Reset (void);

  /**

   * \internal

   * \brief Add the Ipv4Address to the list of IPv4 entries

   *

   * Typically, this is used by external address allocators that want

   * to make use of this class's ability to track duplicates.  AddAllocated

   * is always called internally for any address generated by NextAddress ()

   *

   * \param addr The Ipv4Address to be added to the list of Ipv4 entries

   * \returns true on success

   */

  bool AddAllocated (const Ipv4Address addr);

  /**

   * \internal

   * \brief Used to turn off fatal errors and assertions, for testing

   */

  void TestMode (void);

private:

  static const uint32_t N_BITS = 32;  //!< /internal the number of bits in the address

  static const uint32_t MOST_SIGNIFICANT_BIT = 0x80000000; //!< /internal MSB set to 1

  /**

   * \internal

   * \brief Create an index number for the network mask

   * \param mask the mask to index

   * \returns an index

   */

  uint32_t MaskToIndex (Ipv4Mask mask) const;

  /**

   * \internal

   * \brief This class holds the state for a given network

   */

  class NetworkState

  {

public:

    uint32_t mask;      //!< /internal the network mask

    uint32_t shift;     //!< /internal a shift

    uint32_t network;   //!< /internal the network

    uint32_t addr;      //!< /internal the address

    uint32_t addrMax;   //!< /internal the maximum address

  };

  NetworkState m_netTable[N_BITS]; //!< /internal the available networks

  /**

   * \internal

   * \brief This class holds the allocated addresses

   */

  class Entry

  {

public:

    uint32_t addrLow;  //!< /internal the lowest allocated address

    uint32_t addrHigh; //!< /internal the highest allocated address

  };

  std::list<Entry> m_entries; //!< /internal contained of allocated addresses

  bool m_test; //!< /internal test mode (if true)

};

Ipv4AddressGeneratorImpl::Ipv4AddressGeneratorImpl () 

  : m_entries (), m_test (false)

{

  NS_LOG_FUNCTION (this);

  Reset ();

}

void

Ipv4AddressGeneratorImpl::Reset (void)

{

  NS_LOG_FUNCTION (this);

  uint32_t mask = 0;

//

// There are 32 possible masks in a 32-bit integer.  Two of these are illegal

// for a network mask (0x00000000 and 0xffffffff).  Valid network masks

// correspond to some nonzero number of high order bits set to one followed by 

// some nonzero number of lower order bits set to zero.

//

// We look at a network number as an n-bit number where n is defined as the 

// number of bits in each mask.  Allocating a new network number is simply 

// incrementing this number.

//

// In order to combine an allocated network number with an IP address, we have

// to shift the network into the correct alignment with respect to its mask.

// For example, a network mask of 0xff000000 admits the possibility of 256

// different network numbers since there are eight bits available.  To create

// IP addresses, we need to shift the network number counter left by 24 bits

// to put it in correct alignment.  This leaves 24 bits left for addresses.

// We make sure we don't overflow by saving a maximum address number which is

// just the inverse of the mask (~mask).

//

  for (uint32_t i = 0; i < N_BITS; ++i)

    {

      m_netTable[i].mask = mask;

      mask >>= 1;

      mask |= MOST_SIGNIFICANT_BIT;

      m_netTable[i].network = 1;

      m_netTable[i].addr = 1;

      m_netTable[i].addrMax = ~mask;

      m_netTable[i].shift = N_BITS - i;

    }

  m_entries.clear ();

  m_test = false;

}

Ipv4AddressGeneratorImpl::~Ipv4AddressGeneratorImpl ()

{

  NS_LOG_FUNCTION (this);

}

void

Ipv4AddressGeneratorImpl::Init (

  const Ipv4Address net,

  const Ipv4Mask mask,

  const Ipv4Address addr)

{

  NS_LOG_FUNCTION (this << net << mask << addr);

//

// We're going to be playing with the actual bits in the network and mask so

// pull them out into ints.

//

  uint32_t maskBits = mask.Get ();

  uint32_t netBits = net.Get ();

  uint32_t addrBits = addr.Get ();

//

// Some quick reasonableness testing.

//

  NS_ABORT_MSG_UNLESS ((netBits & ~maskBits) == 0, "Ipv4AddressGeneratorImpl::Init (): Inconsistent network and mask");

  NS_ABORT_MSG_UNLESS ((addrBits & maskBits) == 0, "Ipv4AddressGeneratorImpl::Init (): Inconsistent address and mask");

//

// Convert the network mask into an index into the network number table.

// The network number comes in to us properly aligned for the mask and so

// needs to be shifted right into the normalized position (lowest bit of the

// network number at bit zero of the int that holds it).

//

  uint32_t index = MaskToIndex (mask);

  m_netTable[index].network = netBits >> m_netTable[index].shift;

  NS_ABORT_MSG_UNLESS (addrBits <= m_netTable[index].addrMax, "Ipv4AddressGeneratorImpl::Init(): Address overflow");

  m_netTable[index].addr = addrBits;

  return;

}

Ipv4Address

Ipv4AddressGeneratorImpl::GetNetwork (

  const Ipv4Mask mask) const

{

  NS_LOG_FUNCTION (this << mask);

  uint32_t index = MaskToIndex (mask);

  return Ipv4Address (m_netTable[index].network << m_netTable[index].shift);

}

Ipv4Address

Ipv4AddressGeneratorImpl::NextNetwork (

  const Ipv4Mask mask)

{

  NS_LOG_FUNCTION (this << mask);

//

// The way this is expected to be used is that an address and network prefix

// are initialized, and then NextAddress() is called repeatedly to set the

// addresses on a given subnet.  The client will expect that the first 

// addresses will use the network prefix she used to initialize the generator

// with.  After a subnet is assigned, the client will call NextNetwork to 

// get the network number of the next subnet.  This implies that that this

// operation is a pre-increment.

//

  uint32_t index = MaskToIndex (mask);

  ++m_netTable[index].network;

  return Ipv4Address (m_netTable[index].network << m_netTable[index].shift);

}

void

Ipv4AddressGeneratorImpl::InitAddress (

  const Ipv4Address addr,

  const Ipv4Mask mask)

{

  NS_LOG_FUNCTION (this << addr << mask);

  uint32_t index = MaskToIndex (mask);

  uint32_t addrBits = addr.Get ();

  NS_ABORT_MSG_UNLESS (addrBits <= m_netTable[index].addrMax, "Ipv4AddressGeneratorImpl::InitAddress(): Address overflow");

  m_netTable[index].addr = addrBits;

}

Ipv4Address

Ipv4AddressGeneratorImpl::GetAddress (

  const Ipv4Mask mask) const

{

  NS_LOG_FUNCTION (this << mask);

  uint32_t index = MaskToIndex (mask);

  return Ipv4Address (

           (m_netTable[index].network << m_netTable[index].shift) |

           m_netTable[index].addr);

}

Ipv4Address

Ipv4AddressGeneratorImpl::NextAddress (const Ipv4Mask mask)

{

  NS_LOG_FUNCTION (this << mask);

//

// The way this is expected to be used is that an address and network prefix

// are initialized, and then NextAddress() is called repeatedly to set the

// addresses on a given subnet.  The client will expect that the first address

// she gets back is the one she used to initialize the generator with.  This

// implies that this operation is a post-increment.

//

  uint32_t index = MaskToIndex (mask);

  NS_ABORT_MSG_UNLESS (m_netTable[index].addr <= m_netTable[index].addrMax,

                       "Ipv4AddressGeneratorImpl::NextAddress(): Address overflow");

  Ipv4Address addr = Ipv4Address (

      (m_netTable[index].network << m_netTable[index].shift) |

      m_netTable[index].addr);

  ++m_netTable[index].addr;

//

// Make a note that we've allocated this address -- used for address collision

// detection.

//

  AddAllocated (addr);

  return addr;

}

bool

Ipv4AddressGeneratorImpl::AddAllocated (const Ipv4Address address)

{

  NS_LOG_FUNCTION (this << address);

  uint32_t addr = address.Get ();

  NS_ABORT_MSG_UNLESS (addr, "Ipv4AddressGeneratorImpl::Add(): Allocating the broadcast address is not a good idea"); 

  std::list<Entry>::iterator i;

  for (i = m_entries.begin (); i != m_entries.end (); ++i)

    {

      NS_LOG_LOGIC ("examine entry: " << Ipv4Address ((*i).addrLow) << 

                    " to " << Ipv4Address ((*i).addrHigh));

//

// First things first.  Is there an address collision -- that is, does the

// new address fall in a previously allocated block of addresses.

//

      if (addr >= (*i).addrLow && addr <= (*i).addrHigh)

        {

          NS_LOG_LOGIC ("Ipv4AddressGeneratorImpl::Add(): Address Collision: " << Ipv4Address (addr)); 

          if (!m_test) 

            {

              NS_FATAL_ERROR ("Ipv4AddressGeneratorImpl::Add(): Address Collision: " << Ipv4Address (addr));

            }

          return false;

        }

//

// If the new address is less than the lowest address in the current block,

// and can't be merged into to the current block, then insert it as a new

// block before the current block.

//

      if (addr < (*i).addrLow - 1)

        {

          break;

        }

//

// If the new address fits at the end of the block, look ahead to the next 

// block and make sure it's not a collision there.  If we won't overlap, then

// just extend the current block by one address.  We expect that completely

// filled network ranges will be a fairly rare occurrence, so we don't worry

// about collapsing address range blocks.

// 

      if (addr == (*i).addrHigh + 1)

        {

          std::list<Entry>::iterator j = i;

          ++j;

          if (j != m_entries.end ())

            {

              if (addr == (*j).addrLow)

                {

                  NS_LOG_LOGIC ("Ipv4AddressGeneratorImpl::Add(): "

                                "Address Collision: " << Ipv4Address (addr));

                  if (!m_test)

                    {

                      NS_FATAL_ERROR ("Ipv4AddressGeneratorImpl::Add(): Address Collision: " << Ipv4Address (addr));

                    }

                  return false;

                }

            }

          NS_LOG_LOGIC ("New addrHigh = " << Ipv4Address (addr));

          (*i).addrHigh = addr;

          return true;

        }

//

// If we get here, we know that the next lower block of addresses couldn't 

// have been extended to include this new address since the code immediately 

// above would have been executed and that next lower block extended upward.

// So we know it's safe to extend the current block down to includ the new

// address.

//

      if (addr == (*i).addrLow - 1)

        {

          NS_LOG_LOGIC ("New addrLow = " << Ipv4Address (addr));

          (*i).addrLow = addr;

          return true;

        }

    }

  Entry entry;

  entry.addrLow = entry.addrHigh = addr;

  m_entries.insert (i, entry);

  return true;

}

void

Ipv4AddressGeneratorImpl::TestMode (void)

{

  NS_LOG_FUNCTION (this);

  m_test = true;

}

uint32_t

Ipv4AddressGeneratorImpl::MaskToIndex (Ipv4Mask mask) const

{

  NS_LOG_FUNCTION (this << mask);

//

// We've been given a mask that has a higher order bit set for each bit of the

// network number.  In order to translate this mask into an index, we just need

// to count the number of zero bits in the mask.  We do this in a loop in which

// we shift the mask right until we find the first nonzero bit.  This tells us

// the number of zero bits, and from this we infer the number of nonzero bits

// which is the number of bits in the mask.

//

// We use the number of bits in the mask as the number of bits in the network

// number and as the index into the network number state table.

//

  uint32_t maskBits = mask.Get ();

  for (uint32_t i = 0; i < N_BITS; ++i)

    {

      if (maskBits & 1)

        {

          uint32_t index = N_BITS - i;

          NS_ABORT_MSG_UNLESS (index > 0 && index < N_BITS, "Ipv4AddressGenerator::MaskToIndex(): Illegal Mask");

          return index;

        }

      maskBits >>= 1;

    }

  NS_ASSERT_MSG (false, "Ipv4AddressGenerator::MaskToIndex(): Impossible");

  return 0;

}

void

Ipv4AddressGenerator::Init (

  const Ipv4Address net,

  const Ipv4Mask mask,

  const Ipv4Address addr)

{

  NS_LOG_FUNCTION_NOARGS ();

  SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()

  ->Init (net, mask, addr);

}

Ipv4Address

Ipv4AddressGenerator::NextNetwork (const Ipv4Mask mask)

{

  NS_LOG_FUNCTION_NOARGS ();

  return SimulationSingleton<Ipv4AddressGeneratorImpl>::Get ()

         ->NextNetwork (mask);

}

Ipv4Address

Ipv4AddressGenerator::GetNetwork (const Ipv4Mask mask)