/* -*- 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-metadata.h"

#include "chunk.h"

#include "buffer.h"

NS_DEBUG_COMPONENT_DEFINE ("PacketMetadata");

namespace ns3 {

bool PacketMetadata::m_enable = false;

uint32_t PacketMetadata::m_maxSize = 0;

uint16_t PacketMetadata::m_chunkUid = 0;

PacketMetadata::DataFreeList PacketMetadata::m_freeList;

bool g_optOne = false;

PacketMetadata::DataFreeList::~DataFreeList ()

{

  for (iterator i = begin (); i != end (); i++)

    {

      PacketMetadata::Deallocate (*i);

    }

}

void 

PacketMetadata::Enable (void)

{

  m_enable = true;

}

void 

PacketMetadata::SetOptOne (bool optOne)

{

  g_optOne = optOne;

}

void

PacketMetadata::ReserveCopy (uint32_t size)

{

  struct PacketMetadata::Data *newData = PacketMetadata::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) 

    {

      PacketMetadata::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

PacketMetadata::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. */

    }

  else 

    {

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

      ReserveCopy (size);

    }

}

uint32_t 

PacketMetadata::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

PacketMetadata::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

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

{

  buffer[0] = value & 0xff;

  value >>= 8;

  buffer[1] = value;

}

bool

PacketMetadata::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

PacketMetadata::TryToAppend16 (uint16_t value,  uint8_t **pBuffer, uint8_t *end)

{

  uint8_t *start = *pBuffer;

  if (start + 1 < end)

    {

      start[0] = value & 0xff;

      start[1] = value >> 8;

      *pBuffer = start + 2;

      return true;

    }

  return false;

}

bool

PacketMetadata::TryToAppend32 (uint32_t value,  uint8_t **pBuffer, uint8_t *end)

{

  uint8_t *start = *pBuffer;

  if (start + 3 < end)

    {

      start[0] = value & 0xff;

      start[1] = (value >> 8) & 0xff;

      start[2] = (value >> 16) & 0xff;

      start[3] = (value >> 24) & 0xff;

      *pBuffer = start + 4;

      return true;

    }

  return false;

}

bool

PacketMetadata::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;

      *pBuffer = start + 3;

      return true;

    }

  if (value < 0x10000000 && start + 3 < 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] = 0x80 | byte;

      value >>= 7;

      start[3] = value;

      *pBuffer = start + 4;

      return true;

    }

  if (start + 4 < 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] = 0x80 | byte;

      value >>= 7;

      byte = value & (~0x80);

      start[3] = 0x80 | byte;

      value >>= 7;

      start[4] = value;

      *pBuffer = start + 5;

      return true;

    }

  return false;

}

void

PacketMetadata::AppendValueExtra (uint32_t value, uint8_t *buffer)

{

  if (value < 0x200000)

    {

      uint8_t byte = value & (~0x80);

      buffer[0] = 0x80 | byte;

      value >>= 7;

      byte = value & (~0x80);

      buffer[1] = 0x80 | byte;

      value >>= 7;

      byte = value & (~0x80);

      buffer[2] = value;

      return;

    }

  if (value < 0x10000000)

    {

      uint8_t byte = value & (~0x80);

      buffer[0] = 0x80 | byte;

      value >>= 7;

      byte = value & (~0x80);

      buffer[1] = 0x80 | byte;

      value >>= 7;

      byte = value & (~0x80);

      buffer[2] = 0x80 | byte;

      value >>= 7;

      buffer[3] = value;

      return;

    }

  {

    uint8_t byte = value & (~0x80);

    buffer[0] = 0x80 | byte;

    value >>= 7;

    byte = value & (~0x80);

    buffer[1] = 0x80 | byte;

    value >>= 7;

    byte = value & (~0x80);

    buffer[2] = 0x80 | byte;

    value >>= 7;

    byte = value & (~0x80);

    buffer[3] = 0x80 | byte;

    value >>= 7;

    buffer[4] = value;

  }

}

void

PacketMetadata::AppendValue (uint32_t value, uint8_t *buffer)

{

  if (value < 0x80)

    {

      buffer[0] = value;

      return;

    }

  if (value < 0x4000)

    {

      uint8_t byte = value & (~0x80);

      buffer[0] = 0x80 | byte;

      value >>= 7;

      buffer[1] = value;

      return;

    }

  AppendValueExtra (value, buffer);

}

void

PacketMetadata::UpdateTail (uint16_t written)

{

  if (m_head == 0xffff)

    {

      NS_ASSERT (m_tail == 0xffff);

      m_head = m_used;

      m_tail = m_used;

    } 

  else

    {

      NS_ASSERT (m_tail != 0xffff);

      // overwrite the next field of the previous tail of the list.

      uint8_t *previousTail = &m_data->m_data[m_tail];

      Append16 (m_used, previousTail);

      // update the tail of the list to the new node.

      m_tail = m_used;

    }

  NS_ASSERT (m_tail != 0xffff);

  NS_ASSERT (m_head != 0xffff);

  NS_ASSERT (written >= 8);

  m_used += written;

  m_data->m_dirtyEnd = m_used;

}

void

PacketMetadata::UpdateHead (uint16_t written)

{

  if (m_head == 0xffff)

    {

      NS_ASSERT (m_tail == 0xffff);

      m_head = m_used;

      m_tail = m_used;

    } 

  else

    {

      NS_ASSERT (m_head != 0xffff);

      // overwrite the prev field of the previous head of the list.

      uint8_t *previousHead = &m_data->m_data[m_head + 2];

      Append16 (m_used, previousHead);

      // update the head of list to the new node.

      m_head = m_used;

    }

  NS_ASSERT (m_tail != 0xffff);

  NS_ASSERT (m_head != 0xffff);

  NS_ASSERT (written >= 8);

  m_used += written;

  m_data->m_dirtyEnd = m_used;

}

uint16_t

PacketMetadata::AddSmall (const struct PacketMetadata::SmallItem *item)

{

  NS_ASSERT (m_data != 0);

  NS_ASSERT (m_used != item->prev && m_used != item->next);

  if (g_optOne)

    {

      uint32_t typeUidSize = GetUleb128Size (item->typeUid);

      uint32_t sizeSize = GetUleb128Size (item->size);

      uint32_t n = typeUidSize + sizeSize + 2 + 2 + 2;

    restart:

      if (m_used + n <= m_data->m_size &&

      (m_head == 0xffff ||

       m_data->m_count == 1 ||

       m_used == m_data->m_dirtyEnd))

        {

          uint8_t *buffer = &m_data->m_data[m_used];

          Append16 (item->next, buffer);

          buffer += 2;

          Append16 (item->prev, buffer);

          buffer += 2;

          AppendValue (item->typeUid, buffer);

          buffer += typeUidSize;

          AppendValue (item->size, buffer);

          buffer += sizeSize;

          Append16 (item->chunkUid, buffer);

        }

      else

        {

          ReserveCopy (n);

          goto restart;

        }

      return n;

    }

 append:

  uint8_t *start = &m_data->m_data[m_used];

  uint8_t *end = &m_data->m_data[m_data->m_size];

  if (end - start >= 8 &&

      (m_head == 0xffff ||

       m_data->m_count == 1 ||

       m_used == m_data->m_dirtyEnd))

    {

      uint8_t *buffer = start;

      Append16 (item->next, buffer);

      buffer += 2;

      Append16 (item->prev, buffer);

      buffer += 2;

      if (TryToAppendFast (item->typeUid, &buffer, end) &&

          TryToAppendFast (item->size, &buffer, end) &&

          TryToAppend16 (item->chunkUid, &buffer, end))

        {

          uintptr_t written = buffer - start;

          NS_ASSERT (written <= 0xffff);

          NS_ASSERT (written >= 8);

          return written;

        }

    }

  uint32_t n = GetUleb128Size (item->typeUid);

  n += GetUleb128Size (item->size);

  n += 2;

  n += 2 + 2;

  Reserve (n);

  goto append;

}

uint16_t

PacketMetadata::AddBig (uint32_t next, uint32_t prev, 

                       const PacketMetadata::SmallItem *item, 

                       const PacketMetadata::ExtraItem *extraItem)

{

  NS_ASSERT (m_data != 0);

  uint32_t typeUid = ((item->typeUid & 0x1) == 0x1)?item->typeUid:item->typeUid+1;

  NS_ASSERT (m_used != prev && m_used != next);

 append:

  uint8_t *start = &m_data->m_data[m_used];

  uint8_t *end = &m_data->m_data[m_data->m_size];

  if (end - start >= 14 &&

      (m_head == 0xffff ||