/* -*- 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");

namespace ns3 {

bool PacketHistory::m_enable = false;

uint32_t PacketHistory::m_maxSize = 0;

uint16_t PacketHistory::m_chunkUid = 0;

PacketHistory::DataFreeList PacketHistory::m_freeList;

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

    }

  else 

    {

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

      ReserveCopy (size);

    }

}

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

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

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;

      *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

PacketHistory::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);

  m_used += written;

  m_data->m_dirtyEnd = m_used;

}

void

PacketHistory::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);

  m_used += written;

  m_data->m_dirtyEnd = m_used;

}

uint16_t

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

{

  NS_ASSERT (m_data != 0);

 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);

          return written;

        }

    }

  uint32_t n = GetUleb128Size (item->typeUid);

  n += GetUleb128Size (item->size);

  n += 2;

  n += 2 + 2;

  Reserve (n);

  goto append;

}

uint16_t

PacketHistory::AddBig (uint32_t next, uint32_t prev, 

                       const PacketHistory::SmallItem *item, 

                       const PacketHistory::ExtraItem *extraItem)

{

  NS_ASSERT (m_data != 0);

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

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

       m_data->m_count == 1 ||

       m_used == m_data->m_dirtyEnd))

    {

      uint8_t *buffer = start;

      Append16 (next, buffer);

      buffer += 2;

      Append16 (prev, buffer);

      buffer += 2;

      if (TryToAppend (typeUid, &buffer, end) &&

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

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

          TryToAppend (extraItem->fragmentStart, &buffer, end) &&

          TryToAppend (extraItem->fragmentEnd, &buffer, end) &&

          TryToAppend32 (extraItem->packetUid, &buffer, end))

        {

          uintptr_t written = buffer - start;

          NS_ASSERT (written <= 0xffff);

          return written;

        }

    }

  uint32_t n = GetUleb128Size (typeUid);

  n += GetUleb128Size (item->size);

  n += 2;

  n += GetUleb128Size (extraItem->fragmentStart);

  n += GetUleb128Size (extraItem->fragmentEnd);

  n += 4;

  n += 2 + 2;

  ReserveCopy (n);

  goto append;

}

void

PacketHistory::ReplaceTail (PacketHistory::SmallItem *item, 

                            PacketHistory::ExtraItem *extraItem,

                            uint32_t available)

{

  NS_ASSERT (m_data != 0);  

  if (available >= 14 &&

      m_data->m_count == 1)

    {

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

      uint8_t *end = buffer + available;

      Append16 (item->next, buffer);

      buffer += 2;

      Append16 (item->prev, buffer);

      buffer += 2;

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

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

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

          TryToAppend (extraItem->fragmentStart, &buffer, end) &&

          TryToAppend (extraItem->fragmentEnd, &buffer, end) &&

          TryToAppend32 (extraItem->packetUid, &buffer, end))

        {

          m_used = buffer - &m_data->m_data[0];

          m_data->m_dirtyEnd = m_used;

          return;

        }

    }

  // create a copy of the packet.

  PacketHistory h (m_packetUid, 0);

  uint16_t current = m_head;

  while (current != 0xffff && current != m_tail)

    {

      struct PacketHistory::SmallItem tmpItem;

      PacketHistory::ExtraItem tmpExtraItem;

      ReadItems (current, &tmpItem, &tmpExtraItem);

      uint16_t written = h.AddBig (0xffff, h.m_tail, 

                                   &tmpItem, &tmpExtraItem);

      h.UpdateTail (written);

    }

  // append new tail.

  uint16_t written = h.AddBig (0xffff, h.m_tail, item, extraItem);

  h.UpdateTail (written);

  *this = h;

}

uint32_t

PacketHistory::ReadItems (uint16_t current, 

                          struct PacketHistory::SmallItem *item,

                          struct PacketHistory::ExtraItem *extraItem) const

{

  const uint8_t *buffer = &m_data->m_data[current];

  item->next = buffer[0];

  item->next |= (buffer[1]) << 8;

  item->prev = buffer[2];

  item->prev |= (buffer[3]) << 8;

  buffer += 4;

  item->typeUid = ReadUleb128 (&buffer);

  item->size = ReadUleb128 (&buffer);

  item->chunkUid = buffer[0];

  item->chunkUid |= (buffer[1]) << 8;

  buffer += 2;

  bool isExtra = (item->typeUid & 0x1) == 0x1;

  if (isExtra)

    {

      extraItem->fragmentStart = ReadUleb128 (&buffer);

      extraItem->fragmentEnd = ReadUleb128 (&buffer);

      extraItem->packetUid = buffer[0];

      extraItem->packetUid |= buffer[1] << 8;

      extraItem->packetUid |= buffer[2] << 16;

      extraItem->packetUid |= buffer[3] << 24;

      buffer += 4;

    }

  else

    {

      extraItem->fragmentStart = 0;

      extraItem->fragmentEnd = item->size;

      extraItem->packetUid = m_packetUid;