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

/*

 * Copyright (c) 2006,2007 INRIA

 * All rights reserved.

 *

 * 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

 *

 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>

 */

#include <utility>

#include <list>

#include "ns3/assert.h"

#include "ns3/fatal-error.h"

#include "ns3/debug.h"

#include "packet-history.h"

#include "chunk.h"

#include "buffer.h"

NS_DEBUG_COMPONENT_DEFINE ("PacketHistory");

#define USE_ULEB 1

namespace {

class ItemList

{

public:

  void InitPayload (uint32_t packetUid, uint32_t size);

  void AddHeader (uint32_t type, uint32_t size);

  void AddTrailer (uint32_t type, uint32_t size);

  void RemHeader (uint32_t type, uint32_t size);

  void RemTrailer (uint32_t type, uint32_t size);

  void RemAtStart (uint32_t toRemove);

  void RemAtEnd (uint32_t toRemove);

  void AddAtEnd (ItemList const *other);

  void Print (std::ostream &os, ns3::Buffer buffer, const ns3::PacketPrinter &printer) const;

private:

  enum Type {

    PAYLOAD,

    HEADER,

    TRAILER,

  };

  struct Item

  {

    enum ItemList::Type m_type;

    uint32_t m_size;

    uint32_t m_chunkType;

    uint32_t m_fragmentStart;

    uint32_t m_fragmentEnd;

    uint32_t m_packetUid;

    uint32_t m_chunkUid;

  };

  std::list<Item> m_itemList;

  uint32_t m_packetUid;

  uint32_t m_chunkUid;

};

void 

ItemList::InitPayload (uint32_t packetUid, uint32_t size)

{

  NS_ASSERT (m_itemList.empty ());

  m_packetUid = packetUid;

  m_chunkUid = 1;

  if (size > 0)

    {

      struct Item item;

      item.m_type = ItemList::PAYLOAD;

      item.m_chunkType = 0;

      item.m_size = size;

      item.m_fragmentStart = 0;

      item.m_fragmentEnd = item.m_size;

      item.m_packetUid = m_packetUid;

      item.m_chunkUid = m_chunkUid;

      m_itemList.push_back (item);

    }

}

void 

ItemList::AddHeader (uint32_t type, uint32_t size)

{

  struct Item item;

  item.m_type = ItemList::HEADER;

  item.m_chunkType = type;

  item.m_size = size;

  item.m_fragmentStart = 0;

  item.m_fragmentEnd = size;

  item.m_packetUid = m_packetUid;

  item.m_chunkUid = m_chunkUid;

  m_itemList.push_front (item);

  m_chunkUid++;

}

void 

ItemList::AddTrailer (uint32_t type, uint32_t size)

{

  struct Item item;

  item.m_type = ItemList::TRAILER;

  item.m_chunkType = type;

  item.m_size = size;

  item.m_fragmentStart = 0;

  item.m_fragmentEnd = size;

  item.m_packetUid = m_packetUid;

  item.m_chunkUid = m_chunkUid;

  m_itemList.push_back (item);

  m_chunkUid++;

}

void 

ItemList::RemHeader (uint32_t type, uint32_t size)

{

  struct Item item = m_itemList.front ();

  if (item.m_type != ItemList::HEADER ||

      item.m_size != size ||

      item.m_chunkType != type)

    {

      NS_FATAL_ERROR ("Removing Unexpected header");

    }

  else if (item.m_fragmentStart != 0 ||

           item.m_fragmentEnd != item.m_size)

    {

      NS_FATAL_ERROR ("Removing non-complete header");

    }

  m_itemList.pop_front ();

}

void 

ItemList::RemTrailer (uint32_t type, uint32_t size)

{

  struct Item item = m_itemList.back ();

  if (item.m_type != ItemList::TRAILER ||

      item.m_size != size ||

      item.m_chunkType != type)

    {

      NS_FATAL_ERROR ("Removing Unexpected trailer");

    }

  else if (item.m_fragmentStart != 0 ||

           item.m_fragmentEnd != item.m_size)

    {

      NS_FATAL_ERROR ("Removing non-complete trailer");

    }

  m_itemList.pop_back ();

}

void 

ItemList::RemAtStart (uint32_t toRemove)

{

  uint32_t leftToRemove = toRemove;

  while (!m_itemList.empty () && leftToRemove > 0)

    {

      struct Item &item = m_itemList.front ();

      uint32_t itemRealSize = item.m_fragmentEnd - item.m_fragmentStart;

      if (itemRealSize <= leftToRemove)

        {

          m_itemList.pop_front ();

          leftToRemove -= itemRealSize;

        }

      else

        {

          item.m_fragmentStart += leftToRemove;

          leftToRemove = 0;

          NS_ASSERT (item.m_size >= item.m_fragmentEnd - item.m_fragmentStart &&

                     item.m_fragmentStart <= item.m_fragmentEnd);

        }

    }

  NS_ASSERT (leftToRemove == 0);

}

void 

ItemList::RemAtEnd (uint32_t toRemove)

{

  uint32_t leftToRemove = toRemove;

  while (!m_itemList.empty () && leftToRemove > 0)

    {

      struct Item &item = m_itemList.back ();

      uint32_t itemRealSize = item.m_fragmentEnd - item.m_fragmentStart;

      if (itemRealSize <= leftToRemove)

        {

          m_itemList.pop_back ();

          leftToRemove -= itemRealSize;

        }

      else

        {

          item.m_fragmentEnd -= leftToRemove;

          leftToRemove = 0;

        }

      NS_ASSERT (item.m_size >= item.m_fragmentEnd - item.m_fragmentStart &&

                 item.m_fragmentStart <= item.m_fragmentEnd &&

                 item.m_fragmentEnd <= item.m_size);

    }

  NS_ASSERT (leftToRemove == 0);

}

void 

ItemList::AddAtEnd (ItemList const *other)

{

  ItemList::Item &last = m_itemList.back ();

  for (std::list<ItemList::Item>::const_iterator i = other->m_itemList.begin (); 

       i != other->m_itemList.end (); i++)

    {

      const ItemList::Item &item = *i;

      if (item.m_packetUid == last.m_packetUid &&

          item.m_type == last.m_type &&

          item.m_chunkType == last.m_chunkType &&

          item.m_size == last.m_size &&

          last.m_fragmentEnd != last.m_size && 

          item.m_fragmentStart == last.m_fragmentEnd &&

          item.m_chunkUid == last.m_chunkUid)

        {

          last.m_fragmentEnd = item.m_fragmentEnd;

        }

      else

        {

          m_itemList.push_back (item);

        }

    }

}

void 

ItemList::Print (std::ostream &os, ns3::Buffer buffer, const ns3::PacketPrinter &printer) const

{

  uint32_t totalSize = 0;

  for (std::list<ItemList::Item>::const_iterator i = m_itemList.begin (); 

       i != m_itemList.end (); i++)

    {

      ItemList::Item item = *i;

      totalSize += item.m_fragmentEnd - item.m_fragmentStart;

    }

  NS_ASSERT (totalSize == buffer.GetSize ());

  uint32_t offset = 0;

  for (std::list<ItemList::Item>::const_iterator i = m_itemList.begin (); 

       i != m_itemList.end (); i++)

    {

      ItemList::Item item = *i;

      if (item.m_type == ItemList::PAYLOAD)

        {

          printer.PrintPayload (os, item.m_packetUid, item.m_size, item.m_fragmentStart, item.m_fragmentEnd);

        }

      else if (item.m_fragmentStart != 0 || 

               item.m_fragmentEnd != item.m_size)

        {

          printer.PrintChunkFragment (item.m_chunkType, os, item.m_packetUid, item.m_size, 

                                      item.m_fragmentStart, item.m_fragmentEnd);

        }

      else if (item.m_type == ItemList::HEADER)

        {

          ns3::Buffer::Iterator j = buffer.Begin ();

          j.Next (offset);

          printer.PrintChunk (item.m_chunkType, j, os, item.m_packetUid, item.m_size);

        }

      else if (item.m_type == ItemList::TRAILER)

        {

          ns3::Buffer::Iterator j = buffer.End ();

          j.Prev (totalSize - (offset + item.m_size));

          printer.PrintChunk (item.m_chunkType, j, os, item.m_packetUid, item.m_size);

        }

      else 

        {

          NS_ASSERT (false);

        }

      offset += item.m_fragmentEnd - item.m_fragmentStart;

    }

}

} // anonymous namespace

namespace ns3 {

bool PacketHistory::m_enable = false;

uint32_t PacketHistory::m_maxSize = 0;

uint16_t PacketHistory::m_chunkUid = 0;

PacketHistory::DataFreeList PacketHistory::m_freeList;

uint32_t g_nAllocs = 0;

uint32_t g_nDeAllocs = 0;

uint32_t g_nRecycle = 0;

uint32_t g_nCreate = 0;

  uint32_t g_one = 0;

  uint32_t g_two = 0;

  uint32_t g_three = 0;

  uint32_t g_four = 0;

  uint32_t g_five = 0;

void 

PacketHistory::PrintStats (void)

{

  std::cout << "allocs="<<g_nAllocs<<", deallocs="<<g_nDeAllocs

            <<", recycle="<<g_nRecycle<<", create="<<g_nCreate<<std::endl;

  //std::cout << "one="<<g_one<<", two="<<g_two<<", three="<<g_three<<std::endl;

  std::cout << "four="<<g_four<<", five="<<g_five<<std::endl;

  g_nAllocs = 0;

  g_nDeAllocs = 0;

  g_nRecycle = 0;

  g_nCreate = 0;

  g_one = 0;

  g_two = 0;

  g_three = 0;

  g_four = 0;

  g_five = 0;

}

void 

PacketHistory::Enable (void)

{

  m_enable = true;

}

void

PacketHistory::ReserveCopy (uint32_t size)

{

  struct PacketHistory::Data *newData = PacketHistory::Create (m_used + size);

  memcpy (newData->m_data, m_data->m_data, m_used);

  newData->m_dirtyEnd = m_used;

  m_data->m_count--;

  if (m_data->m_count == 0) 

    {

      PacketHistory::Recycle (m_data);

    }

  m_data = newData;

  if (m_head != 0xffff)

    {

      uint8_t *start;

      NS_ASSERT (m_tail != 0xffff);

      // clear the next field of the tail

      start = &m_data->m_data[m_tail];

      Append16 (0xffff, start);

      // clear the prev field of the head

      start = &m_data->m_data[m_head] + 2;

      Append16 (0xffff, start);

    }

}

void

PacketHistory::Reserve (uint32_t size)

{

  NS_ASSERT (m_data != 0);

  if (m_data->m_size >= m_used + size &&

      (m_head == 0xffff ||

       m_data->m_count == 1 ||

       m_data->m_dirtyEnd == m_used))

    {

      /* enough room, not dirty. */

      g_four++;

    }

  else 

    {

      /* (enough room and dirty) or (not enough room) */

      ReserveCopy (size);

      g_five++;

    }

}

uint32_t 

PacketHistory::GetUleb128Size (uint32_t value) const

{

  if (value < 0x80)

    {

      return 1;

    }

  if (value < 0x4000)

    {

      return 2;

    }

  if (value < 0x200000)

    {

      return 3;

    }

  if (value < 0x10000000)

    {

      return 4;

    }

  return 5;

}

uint32_t

PacketHistory::ReadUleb128 (const uint8_t **pBuffer) const

{

  const uint8_t *buffer = *pBuffer;

  uint32_t result = 0;

  uint8_t byte;

  result = 0;

  byte = buffer[0];

  result = (byte & (~0x80));

  if (!(byte & 0x80))

    {

      *pBuffer = buffer + 1;

      return result;

    }

  byte = buffer[1];

  result = (byte & (~0x80)) << 7;

  if (!(byte & 0x80))

    {

      *pBuffer = buffer + 2;

      return result;

    }

  byte = buffer[2];

  result = (byte & (~0x80)) << 14;

  if (!(byte & 0x80))

    {

      *pBuffer = buffer + 3;

      return result;

    }

  byte = buffer[3];

  result = (byte & (~0x80)) << 21;

  if (!(byte & 0x80))

    {

      *pBuffer = buffer + 4;

      return result;

    }

  byte = buffer[4];

  result = (byte & (~0x80)) << 28;

  if (!(byte & 0x80))

    {

      *pBuffer = buffer + 5;

      return result;

    }

  /* This means that the LEB128 number was not valid.

   * ie: the last (5th) byte did not have the high-order bit zeroed.

   */

  NS_ASSERT (false);

  return 0;

}

void

PacketHistory::Append16 (uint16_t value, uint8_t *buffer)

{

  buffer[0] = value & 0xff;

  value >>= 8;

  buffer[1] = value;

}

bool

PacketHistory::TryToAppendFast (uint32_t value, uint8_t **pBuffer, uint8_t *end)

{

  uint8_t *start = *pBuffer;

  if (value < 0x80 && start < end)

    {

      start[0] = value;

      *pBuffer = start + 1;

      return true;

    }

  if (value < 0x4000 && start + 1 < end)

    {

      uint8_t byte = value & (~0x80);

      start[0] = 0x80 | byte;

      value >>= 7;

      start[1] = value;

      *pBuffer = start + 2;

      return true;

    }

  return false;

}

bool

PacketHistory::TryToAppend (uint32_t value, uint8_t **pBuffer, uint8_t *end)

{

  uint8_t *start = *pBuffer;

  if (value < 0x80 && start < end)

    {

      start[0] = value;

      *pBuffer = start + 1;

      return true;

    }

  if (value < 0x4000 && start + 1 < end)

    {

      uint8_t byte = value & (~0x80);

      start[0] = 0x80 | byte;

      value >>= 7;

      start[1] = value;

      *pBuffer = start + 2;

      return true;

    }

  if (value < 0x200000 && start + 2 < end)

    {

      uint8_t byte = value & (~0x80);

      start[0] = 0x80 | byte;

      value >>= 7;

      byte = value & (~0x80);

      start[1] = 0x80 | byte;

      value >>= 7;

      byte = value & (~0x80);

      start[2] = value;