fast-encoding: implement fast encoding for Name, NameComponent and FibManagementOptions, including test case.

refs: #1172

Change-Id: I80fa7cfbe7f9dee3c439febcc8f800c63a31eac3
diff --git a/src/encoding/buffer.hpp b/src/encoding/buffer.hpp
index 1dc8f7e..9742512 100644
--- a/src/encoding/buffer.hpp
+++ b/src/encoding/buffer.hpp
@@ -42,6 +42,15 @@
   }
 
   /**
+   * @brief Creates a buffer with pre-allocated size
+   * @param size size of the buffer to be allocated
+   */
+  Buffer (size_t size)
+    : std::vector<uint8_t> (size, 0)
+  {
+  }
+
+  /**
    * @brief Create a buffer by copying the supplied data from a const buffer
    * @param buf const pointer to buffer
    * @param length length of the buffer to copy
diff --git a/src/encoding/encoding-buffer.hpp b/src/encoding/encoding-buffer.hpp
new file mode 100644
index 0000000..b3cfa65
--- /dev/null
+++ b/src/encoding/encoding-buffer.hpp
@@ -0,0 +1,382 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Wentao Shang <wentao@cs.ucla.edu>
+ */
+
+#ifndef NDN_ENCODING_BUFFER_HPP
+#define NDN_ENCODING_BUFFER_HPP
+
+#include "../common.hpp"
+
+#include <list>
+#include <exception>
+#include <algorithm>
+
+#include "buffer.hpp"
+#include "tlv.hpp"
+
+#include <boost/lexical_cast.hpp>
+
+namespace ndn {
+
+/**
+ * @brief Class representing wire element of the NDN packet
+ */
+class EncodingBuffer
+{
+public:
+  /// @brief Error that can be thrown from the block
+  struct Error : public std::runtime_error { Error(const std::string &what) : std::runtime_error(what) {} };
+
+  enum
+    {
+      DefaultBufferSize = 8800,
+      BufferReservedSize = 400
+    };
+  
+  /**
+   * @brief Default constructor to create a fix-sized EncodingBuffer
+   */
+  EncodingBuffer ()
+    : m_buffer (new Buffer ((size_t) DefaultBufferSize))
+  {
+    m_begin = m_end = m_buffer->end () - BufferReservedSize;
+  }
+
+  /**
+   * @brief Constructor to create a EncodingBuffer with user-specified size
+   */
+  EncodingBuffer (size_t size)
+    : m_buffer (new Buffer (size))
+  {
+    if (size <= BufferReservedSize)
+      m_begin = m_end = m_buffer->end ();
+    else
+      m_begin = m_end = m_buffer->end () - BufferReservedSize;
+  }
+
+  inline size_t
+  size () const;
+
+  inline size_t
+  capacity () const;
+
+  inline uint8_t*
+  buf ();
+
+  inline const uint8_t*
+  buf () const;
+
+  inline void
+  resize (size_t sz, bool addInFront);
+
+  inline Buffer::iterator
+  begin ();
+
+  inline Buffer::iterator
+  end ();
+
+  inline Buffer::const_iterator
+  begin () const;
+
+  inline Buffer::const_iterator
+  end () const;
+
+  inline size_t
+  prependByte (uint8_t val);
+
+  inline size_t
+  prependByteArray (const uint8_t *arr, size_t len);
+
+  inline size_t
+  prependBuffer (const Buffer& arr);
+
+  inline size_t
+  prependNonNegativeInteger (uint64_t varNumber);
+
+  inline size_t
+  prependVarNumber (uint64_t varNumber);
+
+  inline size_t
+  appendByte (uint8_t val);
+
+  inline size_t
+  appendByteArray (const uint8_t *arr, size_t len);
+
+  inline size_t
+  appendBuffer (const Buffer& arr);
+
+  inline size_t
+  appendNonNegativeInteger (uint64_t varNumber);
+
+  inline size_t
+  appendVarNumber (uint64_t varNumber);
+
+private:
+  BufferPtr m_buffer;
+
+  // invariant: m_begin always points to the position of last-written byte (if prepending data)
+  Buffer::iterator m_begin;
+  // invariant: m_end always points to the position of next unwritten byte (if appending data)
+  Buffer::iterator m_end;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////
+
+inline size_t
+EncodingBuffer::size () const
+{
+  return m_end - m_begin;
+}
+
+inline size_t
+EncodingBuffer::capacity () const
+{
+  return m_buffer->size ();
+}
+
+inline uint8_t*
+EncodingBuffer::buf ()
+{
+  return &(*m_begin);
+}
+
+inline const uint8_t*
+EncodingBuffer::buf () const
+{
+  return &(*m_begin);
+}
+  
+inline void
+EncodingBuffer::resize (size_t sz, bool addInFront)
+{
+  if (addInFront)
+    {
+      size_t diff_end = m_buffer->end () - m_end;
+      size_t diff_begin = m_buffer->end () - m_begin;
+
+      Buffer* buf = new Buffer (sz);
+      std::copy_backward (m_buffer->begin (), m_buffer->end (), buf->end ());
+
+      m_buffer.reset (buf);
+
+      m_end = m_buffer->end () - diff_end;
+      m_begin = m_buffer->end () - diff_begin;
+    }
+  else
+    {
+      size_t diff_end = m_end - m_buffer->begin ();
+      size_t diff_begin = m_begin - m_buffer->begin ();
+
+      Buffer* buf = new Buffer (sz);
+      std::copy (m_buffer->begin (), m_buffer->end (), buf->begin ());
+
+      m_buffer.reset (buf);
+
+      m_end = m_buffer->begin () + diff_end;
+      m_begin = m_buffer->begin () + diff_begin;      
+    }
+}
+
+inline Buffer::iterator
+EncodingBuffer::begin ()
+{
+  return m_begin;
+}
+
+inline Buffer::iterator
+EncodingBuffer::end ()
+{
+  return m_end;
+}
+
+inline Buffer::const_iterator
+EncodingBuffer::begin () const
+{
+  return m_begin;
+}
+
+inline Buffer::const_iterator
+EncodingBuffer::end () const
+{
+  return m_end;
+}
+
+
+//////////////////////////////////////////////////////////
+// Prepend to the back of the buffer. Resize if needed. //
+//////////////////////////////////////////////////////////
+
+inline size_t
+EncodingBuffer::prependByte (uint8_t val)
+{
+  if (m_begin == m_buffer->begin ())
+    resize (m_buffer->size () * 2, true);
+
+  m_begin--;
+  *m_begin = val;
+  return 1;
+}
+
+inline size_t
+EncodingBuffer::prependByteArray (const uint8_t *arr, size_t len)
+{
+  if ((m_buffer->begin () + len) > m_begin)
+    resize (m_buffer->size () * 2 + len, true);
+
+  m_begin -= len;
+  std::copy (arr, arr + len, m_begin);
+  return len;
+}
+
+inline size_t
+EncodingBuffer::prependBuffer (const Buffer& arr)
+{
+  if ((m_buffer->begin () + arr.size ()) > m_begin)
+    resize (m_buffer->size () * 2 + arr.size (), true);
+
+  m_begin -= arr.size ();
+  std::copy (arr.begin (), arr.end (), m_begin);
+  return arr.size ();
+}
+
+inline size_t
+EncodingBuffer::prependNonNegativeInteger (uint64_t varNumber)
+{
+  if (varNumber < 253) {
+    return prependByte (static_cast<uint8_t> (varNumber));
+  }
+  else if (varNumber <= std::numeric_limits<uint16_t>::max ()) {
+    uint16_t value = htobe16 (static_cast<uint16_t> (varNumber));
+    return prependByteArray (reinterpret_cast<const uint8_t*> (&value), 2);
+  }
+  else if (varNumber <= std::numeric_limits<uint32_t>::max ()) {
+    uint32_t value = htobe32 (static_cast<uint32_t> (varNumber));
+    return prependByteArray (reinterpret_cast<const uint8_t*> (&value), 4);
+  }
+  else {
+    uint64_t value = htobe64 (varNumber);
+    return prependByteArray (reinterpret_cast<const uint8_t*> (&value), 8);
+  }
+}
+
+inline size_t
+EncodingBuffer::prependVarNumber (uint64_t varNumber)
+{
+  if (varNumber < 253) {
+    prependByte (static_cast<uint8_t> (varNumber));
+    return 1;
+  }
+  else if (varNumber <= std::numeric_limits<uint16_t>::max ()) {
+    uint16_t value = htobe16 (static_cast<uint16_t> (varNumber));
+    prependByteArray (reinterpret_cast<const uint8_t*> (&value), 2);
+    prependByte (253);
+    return 3;
+  }
+  else if (varNumber <= std::numeric_limits<uint32_t>::max ()) {
+    uint32_t value = htobe32 (static_cast<uint32_t> (varNumber));
+    prependByteArray (reinterpret_cast<const uint8_t*> (&value), 4);
+    prependByte (254);
+    return 5;
+  }
+  else {
+    uint64_t value = htobe64 (varNumber);
+    prependByteArray (reinterpret_cast<const uint8_t*> (&value), 8);
+    prependByte (255);
+    return 9;
+  }
+}
+
+/////////////////////////////////////////////////////////
+// Append to the back of the buffer. Resize if needed. //
+/////////////////////////////////////////////////////////
+
+inline size_t
+EncodingBuffer::appendByte (uint8_t val)
+{
+  if (m_end == m_buffer->end ())
+    resize (m_buffer->size () * 2, false);
+
+  *m_end = val;
+  m_end++;
+  return 1;
+}
+
+inline size_t
+EncodingBuffer::appendByteArray (const uint8_t *arr, size_t len)
+{
+  if ((m_end + len) > m_buffer->end ())
+    resize (m_buffer->size () * 2 + len, false);
+
+  std::copy (arr, arr + len, m_end);
+  m_end += len;
+  return len;
+}
+
+inline size_t
+EncodingBuffer::appendBuffer (const Buffer& arr)
+{
+  if ((m_end + arr.size ()) > m_buffer->end ())
+    resize (m_buffer->size () * 2 + arr.size (), false);
+
+  std::copy (arr.begin (), arr.end (), m_end);
+  m_end -= arr.size ();
+  return arr.size ();
+}
+
+inline size_t
+EncodingBuffer::appendNonNegativeInteger (uint64_t varNumber)
+{
+  if (varNumber < 253) {
+    return appendByte (static_cast<uint8_t> (varNumber));
+  }
+  else if (varNumber <= std::numeric_limits<uint16_t>::max ()) {
+    uint16_t value = htobe16 (static_cast<uint16_t> (varNumber));
+    return appendByteArray (reinterpret_cast<const uint8_t*> (&value), 2);
+  }
+  else if (varNumber <= std::numeric_limits<uint32_t>::max ()) {
+    uint32_t value = htobe32 (static_cast<uint32_t> (varNumber));
+    return appendByteArray (reinterpret_cast<const uint8_t*> (&value), 4);
+  }
+  else {
+    uint64_t value = htobe64 (varNumber);
+    return appendByteArray (reinterpret_cast<const uint8_t*> (&value), 8);
+  }
+}
+
+inline size_t
+EncodingBuffer::appendVarNumber (uint64_t varNumber)
+{
+  if (varNumber < 253) {
+    appendByte (static_cast<uint8_t> (varNumber));
+    return 1;
+  }
+  else if (varNumber <= std::numeric_limits<uint16_t>::max ()) {
+    appendByte (253);
+    uint16_t value = htobe16 (static_cast<uint16_t> (varNumber));
+    appendByteArray (reinterpret_cast<const uint8_t*> (&value), 2);
+    return 3;
+  }
+  else if (varNumber <= std::numeric_limits<uint32_t>::max ()) {
+    appendByte (254);
+    uint32_t value = htobe32 (static_cast<uint32_t> (varNumber));
+    appendByteArray (reinterpret_cast<const uint8_t*> (&value), 4);
+    return 5;
+  }
+  else {
+    appendByte (255);
+    uint64_t value = htobe64 (varNumber);
+    appendByteArray (reinterpret_cast<const uint8_t*> (&value), 8);
+    return 9;
+  }
+}
+
+} // ndn
+
+#endif // NDN_ENCODING_BUFFER_HPP
diff --git a/src/management/fib-management-options.hpp b/src/management/fib-management-options.hpp
index b8b6fe7..58048b5 100644
--- a/src/management/fib-management-options.hpp
+++ b/src/management/fib-management-options.hpp
@@ -11,6 +11,7 @@
 #define NDN_FIB_MANAGEMENT_HPP
 
 #include "../encoding/block.hpp"
+#include "../encoding/encoding-buffer.hpp"
 #include "../encoding/tlv-nfd-control.hpp"
 #include "../name.hpp"
 
@@ -42,6 +43,9 @@
   void 
   setCost (int cost) { cost_ = cost; wire_.reset (); }
 
+  inline size_t
+  wireEncode (EncodingBuffer& blk);
+  
   inline const Block&
   wireEncode () const;
   
@@ -58,6 +62,33 @@
   mutable Block wire_;
 };
 
+inline size_t
+FibManagementOptions::wireEncode (EncodingBuffer& blk)
+{
+  size_t total_len = 0;
+  if (cost_ != -1)
+    {
+      size_t var_len = blk.prependNonNegativeInteger (cost_);
+      total_len += var_len;
+      total_len += blk.prependVarNumber (var_len);
+      total_len += blk.prependVarNumber (tlv::nfd_control::Cost);
+    }
+
+  if (faceId_ != -1)
+    {
+      size_t var_len = blk.prependNonNegativeInteger (faceId_);
+      total_len += var_len;
+      total_len += blk.prependVarNumber (var_len);
+      total_len += blk.prependVarNumber (tlv::nfd_control::FaceId);
+    }
+
+  total_len += name_.wireEncode (blk);
+
+  total_len += blk.prependVarNumber (total_len);
+  total_len += blk.prependVarNumber (tlv::nfd_control::FibManagementOptions);
+  return total_len;
+}
+
 inline const Block&
 FibManagementOptions::wireEncode () const
 {
diff --git a/src/name.cpp b/src/name.cpp
index 2ca9076..fe1f739 100644
--- a/src/name.cpp
+++ b/src/name.cpp
@@ -93,6 +93,16 @@
   return std::memcmp(getValue().buf(), other.getValue().buf(), getValue().size());
 }
 
+inline size_t
+Name::Component::wireEncode (EncodingBuffer& blk)
+{
+  size_t total_len = 0;
+  total_len += blk.prependBuffer (*value_);
+  total_len += blk.prependVarNumber (value_->size ());
+  total_len += blk.prependVarNumber (Tlv::NameComponent);
+  return total_len;
+}
+
 // const Block &
 // Name::wireEncode() const
 // {
@@ -375,4 +385,23 @@
       append(i->value(), i->value_size());
     }
 }
+
+
+size_t
+Name::wireEncode (EncodingBuffer& blk)
+{
+  size_t total_len = 0;
+  
+  for (std::vector<Component>::reverse_iterator i = components_.rbegin ();
+       i != components_.rend ();
+       ++i)
+    {
+      total_len += i->wireEncode (blk);
+    }
+
+  total_len += blk.prependVarNumber (total_len);
+  total_len += blk.prependVarNumber (Tlv::Name);
+  return total_len;
 }
+
+} // namespace ndn
diff --git a/src/name.hpp b/src/name.hpp
index 1603618..78bdfd7 100644
--- a/src/name.hpp
+++ b/src/name.hpp
@@ -15,6 +15,7 @@
 #include <sstream>
 #include <string.h>
 #include "encoding/block.hpp"
+#include "encoding/encoding-buffer.hpp"
 
 namespace ndn {
     
@@ -250,6 +251,10 @@
      */
     bool
     operator > (const Component& other) const { return compare(other) > 0; }
+
+    inline size_t
+    wireEncode (EncodingBuffer& blk);
+    
   private:
     ConstBufferPtr value_;
   };
@@ -297,6 +302,9 @@
     set(uri.c_str());
   }
 
+  size_t
+  wireEncode (EncodingBuffer& blk);
+  
   const Block &
   wireEncode() const;
 
diff --git a/tests/test-nfd-control.cpp b/tests/test-nfd-control.cpp
index ae898f7..48295aa 100644
--- a/tests/test-nfd-control.cpp
+++ b/tests/test-nfd-control.cpp
@@ -1,6 +1,6 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
 /**
  * Copyright (C) 2013 Regents of the University of California.
- * @author: Jeff Thompson <jefft0@remap.ucla.edu>
  * See COPYING for copyright and distribution information.
  */
 
@@ -63,6 +63,32 @@
                                    blk.begin (), blk.end ());
 }
 
+BOOST_AUTO_TEST_CASE (FibManagementOptionsFastEncoding)
+{
+  Name n ("/localhost/reg/test");
+  FibManagementOptions opt;
+
+  opt.setName (n);
+  opt.setFaceId (0);
+  opt.setCost (0);
+
+  EncodingBuffer blk;
+
+  BOOST_REQUIRE_NO_THROW (opt.wireEncode (blk));
+
+  BOOST_REQUIRE_EQUAL_COLLECTIONS (TestFibManagementOptions,
+                                   TestFibManagementOptions + sizeof (TestFibManagementOptions),
+                                   blk.begin (), blk.end ());
+
+  EncodingBuffer blk2 (4);
+
+  BOOST_REQUIRE_NO_THROW (opt.wireEncode (blk2));
+
+  BOOST_REQUIRE_EQUAL_COLLECTIONS (TestFibManagementOptions,
+                                   TestFibManagementOptions + sizeof (TestFibManagementOptions),
+                                   blk2.begin (), blk2.end ());
+}
+
 BOOST_AUTO_TEST_CASE (FibManagementOptionsDecoding)
 {
   Block blk (TestFibManagementOptions, sizeof (TestFibManagementOptions));