Reduce copying/allocations when BER decoding

We are constrained in how far we can go because BER_Object must
mandatorily copy its value (due to the public member variable
exposting the bytes). But this reduces the number of allocations
when parsing a sample X.509 certificate by about 15%

2 files changed, 194 insertions, 81 deletions

diff --git a/src/lib/asn1/ber_dec.cpp b/src/lib/asn1/ber_dec.cpp
index 35f1a53b5..313e7fd15 100644
--- a/src/lib/asn1/ber_dec.cpp
+++ b/src/lib/asn1/ber_dec.cpp
@@ -1,6 +1,6 @@
 /*
 * BER Decoder
-* (C) 1999-2008,2015,2017 Jack Lloyd
+* (C) 1999-2008,2015,2017,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -145,6 +145,51 @@ size_t find_eoc(DataSource* ber, size_t allow_indef)
    return length;
    }
 
+class DataSource_BERObject final : public DataSource
+   {
+   public:
+      size_t read(uint8_t out[], size_t length) override
+         {
+         BOTAN_ASSERT_NOMSG(m_offset <= m_obj.length());
+         const size_t got = std::min<size_t>(m_obj.length() - m_offset, length);
+         copy_mem(out, m_obj.bits() + m_offset, got);
+         m_offset += got;
+         return got;
+         }
+
+      size_t peek(uint8_t out[], size_t length, size_t peek_offset) const override
+         {
+         BOTAN_ASSERT_NOMSG(m_offset <= m_obj.length());
+         const size_t bytes_left = m_obj.length() - m_offset;
+
+         if(peek_offset >= bytes_left)
+            return 0;
+
+         const size_t got = std::min(bytes_left - peek_offset, length);
+         copy_mem(out, m_obj.bits() + peek_offset, got);
+         return got;
+         }
+
+      bool check_available(size_t n) override
+         {
+         BOTAN_ASSERT_NOMSG(m_offset <= m_obj.length());
+         return (n <= (m_obj.length() - m_offset));
+         }
+
+      bool end_of_data() const override
+         {
+         return get_bytes_read() == m_obj.length();
+         }
+
+      size_t get_bytes_read() const override { return m_offset; }
+
+      explicit DataSource_BERObject(BER_Object&& obj) : m_obj(std::move(obj)), m_offset(0) {}
+
+   private:
+      BER_Object m_obj;
+      size_t m_offset;
+   };
+
 }
 
 /*
@@ -225,12 +270,6 @@ BER_Object BER_Decoder::get_next_object()
    return next;
    }
 
-BER_Decoder& BER_Decoder::get_next(BER_Object& ber)
-   {
-   ber = get_next_object();
-   return (*this);
-   }
-
 /*
 * Push a object back into the stream
 */
@@ -241,18 +280,18 @@ void BER_Decoder::push_back(const BER_Object& obj)
    m_pushed = obj;
    }
 
-/*
-* Begin decoding a CONSTRUCTED type
-*/
-BER_Decoder BER_Decoder::start_cons(ASN1_Tag type_tag,
-                                    ASN1_Tag class_tag)
+void BER_Decoder::push_back(BER_Object&& obj)
+   {
+   if(m_pushed.is_set())
+      throw Invalid_State("BER_Decoder: Only one push back is allowed");
+   m_pushed = std::move(obj);
+   }
+
+BER_Decoder BER_Decoder::start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag)
    {
    BER_Object obj = get_next_object();
    obj.assert_is_a(type_tag, ASN1_Tag(class_tag | CONSTRUCTED));
-
-   BER_Decoder result(obj.bits(), obj.length());
-   result.m_parent = this;
-   return result;
+   return BER_Decoder(std::move(obj), this);
    }
 
 /*
@@ -261,14 +300,17 @@ BER_Decoder BER_Decoder::start_cons(ASN1_Tag type_tag,
 BER_Decoder& BER_Decoder::end_cons()
    {
    if(!m_parent)
-      throw Invalid_State("BER_Decoder::end_cons called with NULL parent");
+      throw Invalid_State("BER_Decoder::end_cons called with null parent");
    if(!m_source->end_of_data())
       throw Decoding_Error("BER_Decoder::end_cons called with data left");
    return (*m_parent);
    }
 
-BER_Decoder::BER_Decoder(const BER_Object& obj) : BER_Decoder(obj.bits(), obj.length())
+BER_Decoder::BER_Decoder(BER_Object&& obj, BER_Decoder* parent)
    {
+   m_data_src.reset(new DataSource_BERObject(std::move(obj)));
+   m_source = m_data_src.get();
+   m_parent = parent;
    }
 
 /*
@@ -340,30 +382,6 @@ BER_Decoder& BER_Decoder::decode_null()
    return (*this);
    }
 
-/*
-* Decode a BER encoded BOOLEAN
-*/
-BER_Decoder& BER_Decoder::decode(bool& out)
-   {
-   return decode(out, BOOLEAN, UNIVERSAL);
-   }
-
-/*
-* Decode a small BER encoded INTEGER
-*/
-BER_Decoder& BER_Decoder::decode(size_t& out)
-   {
-   return decode(out, INTEGER, UNIVERSAL);
-   }
-
-/*
-* Decode a BER encoded INTEGER
-*/
-BER_Decoder& BER_Decoder::decode(BigInt& out)
-   {
-   return decode(out, INTEGER, UNIVERSAL);
-   }
-
 BER_Decoder& BER_Decoder::decode_octet_string_bigint(BigInt& out)
    {
    secure_vector<uint8_t> out_vec;
@@ -372,13 +390,6 @@ BER_Decoder& BER_Decoder::decode_octet_string_bigint(BigInt& out)
    return (*this);
    }
 
-std::vector<uint8_t> BER_Decoder::get_next_octet_string()
-   {
-   std::vector<uint8_t> out_vec;
-   decode(out_vec, OCTET_STRING);
-   return out_vec;
-   }
-
 /*
 * Decode a BER encoded BOOLEAN
 */
@@ -405,6 +416,8 @@ BER_Decoder& BER_Decoder::decode(size_t& out,
    BigInt integer;
    decode(integer, type_tag, class_tag);
 
+   if(integer.is_negative())
+
    if(integer.bits() > 32)
       throw BER_Decoding_Error("Decoded integer value larger than expected");
 
diff --git a/src/lib/asn1/ber_dec.h b/src/lib/asn1/ber_dec.h
index d454c45d6..2086eacd3 100644
--- a/src/lib/asn1/ber_dec.h
+++ b/src/lib/asn1/ber_dec.h
@@ -1,6 +1,6 @@
 /*
 * BER Decoder
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -13,28 +13,103 @@
 
 namespace Botan {
 
+class BigInt;
+
 /**
 * BER Decoding Object
 */
 class BOTAN_PUBLIC_API(2,0) BER_Decoder final
    {
    public:
+      /**
+      * Set up to BER decode the data in buf of length len
+      */
+      BER_Decoder(const uint8_t buf[], size_t len);
+
+      /**
+      * Set up to BER decode the data in vec
+      */
+      explicit BER_Decoder(const secure_vector<uint8_t>& vec);
+
+      /**
+      * Set up to BER decode the data in vec
+      */
+      explicit BER_Decoder(const std::vector<uint8_t>& vec);
+
+      /**
+      * Set up to BER decode the data in src
+      */
+      explicit BER_Decoder(DataSource& src);
+
+      /**
+      * Set up to BER decode the data in obj
+      */
+      BER_Decoder(const BER_Object& obj) :
+         BER_Decoder(obj.bits(), obj.length()) {}
+
+      BER_Decoder(const BER_Decoder& other);
+
+      BER_Decoder& operator=(const BER_Decoder&) = delete;
+
+      /**
+      * Get the next object in the data stream.
+      * If EOF, returns an object with type NO_OBJECT.
+      */
       BER_Object get_next_object();
 
-      std::vector<uint8_t> get_next_octet_string();
+      BER_Decoder& get_next(BER_Object& ber)
+         {
+         ber = get_next_object();
+         return (*this);
+         }
 
+      /**
+      * Push an object back onto the stream. Throws if another
+      * object was previously pushed and has not been subsequently
+      * read out.
+      */
       void push_back(const BER_Object& obj);
 
+      /**
+      * Push an object back onto the stream. Throws if another
+      * object was previously pushed and has not been subsequently
+      * read out.
+      */
+      void push_back(BER_Object&& obj);
+
+      /**
+      * Return true if there is at least one more item remaining
+      */
       bool more_items() const;
+
+      /**
+      * Verify the stream is concluded, throws otherwise.
+      * Returns (*this)
+      */
       BER_Decoder& verify_end();
+
+      /**
+      * Verify the stream is concluded, throws otherwise.
+      * Returns (*this)
+      */
       BER_Decoder& verify_end(const std::string& err_msg);
 
+      /**
+      * Discard any data that remains unread
+      * Returns (*this)
+      */
       BER_Decoder& discard_remaining();
 
-      BER_Decoder  start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag = UNIVERSAL);
-      BER_Decoder& end_cons();
+      /**
+      * Start decoding a constructed data (sequence or set)
+      */
+      BER_Decoder start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag = UNIVERSAL);
 
-      BER_Decoder& get_next(BER_Object& ber);
+      /**
+      * Finish decoding a constructed data, throws if any data remains.
+      * Returns the parent of *this (ie the object on which start_cons was called).
+      */
+      BER_Decoder& end_cons();
 
       /**
       * Get next object and copy value to POD type
@@ -82,9 +157,37 @@ class BOTAN_PUBLIC_API(2,0) BER_Decoder final
          }
 
       BER_Decoder& decode_null();
-      BER_Decoder& decode(bool& v);
-      BER_Decoder& decode(size_t& v);
-      BER_Decoder& decode(class BigInt& v);
+
+      /**
+      * Decode a BER encoded BOOLEAN
+      */
+      BER_Decoder& decode(bool& out)
+         {
+         return decode(out, BOOLEAN, UNIVERSAL);
+         }
+
+      /*
+      * Decode a small BER encoded INTEGER
+      */
+      BER_Decoder& decode(size_t& out)
+         {
+         return decode(out, INTEGER, UNIVERSAL);
+         }
+
+      /*
+      * Decode a BER encoded INTEGER
+      */
+      BER_Decoder& decode(BigInt& out)
+         {
+         return decode(out, INTEGER, UNIVERSAL);
+         }
+
+      std::vector<uint8_t> get_next_octet_string()
+         {
+         std::vector<uint8_t> out_vec;
+         decode(out_vec, OCTET_STRING);
+         return out_vec;
+         }
 
       /*
       * BER decode a BIT STRING or OCTET STRING
@@ -103,7 +206,7 @@ class BOTAN_PUBLIC_API(2,0) BER_Decoder final
                           ASN1_Tag type_tag,
                           ASN1_Tag class_tag = CONTEXT_SPECIFIC);
 
-      BER_Decoder& decode(class BigInt& v,
+      BER_Decoder& decode(BigInt& v,
                           ASN1_Tag type_tag,
                           ASN1_Tag class_tag = CONTEXT_SPECIFIC);
 
@@ -121,11 +224,14 @@ class BOTAN_PUBLIC_API(2,0) BER_Decoder final
                           ASN1_Tag type_tag = NO_OBJECT,
                           ASN1_Tag class_tag = NO_OBJECT);
 
-      BER_Decoder& decode_octet_string_bigint(class BigInt& b);
+      /**
+      * Decode an integer value which is typed as an octet string
+      */
+      BER_Decoder& decode_octet_string_bigint(BigInt& b);
 
       uint64_t decode_constrained_integer(ASN1_Tag type_tag,
-                                        ASN1_Tag class_tag,
-                                        size_t T_bytes);
+                                          ASN1_Tag class_tag,
+                                          size_t T_bytes);
 
       template<typename T> BER_Decoder& decode_integer_type(T& out)
          {
@@ -190,36 +296,27 @@ class BOTAN_PUBLIC_API(2,0) BER_Decoder final
          if(obj.is_a(type_tag, class_tag))
             {
             if((class_tag & CONSTRUCTED) && (class_tag & CONTEXT_SPECIFIC))
+               {
                BER_Decoder(obj).decode(out, real_type).verify_end();
+               }
             else
                {
-               push_back(obj);
+               push_back(std::move(obj));
                decode(out, real_type, type_tag, class_tag);
                }
             }
          else
             {
             out.clear();
-            push_back(obj);
+            push_back(std::move(obj));
             }
 
          return (*this);
          }
 
-      BER_Decoder& operator=(const BER_Decoder&) = delete;
-
-      explicit BER_Decoder(DataSource&);
-
-      BER_Decoder(const uint8_t[], size_t);
-
-      explicit BER_Decoder(const BER_Object& obj);
-
-      explicit BER_Decoder(const secure_vector<uint8_t>&);
-
-      explicit BER_Decoder(const std::vector<uint8_t>& vec);
-
-      BER_Decoder(const BER_Decoder&);
    private:
+      BER_Decoder(BER_Object&& obj, BER_Decoder* parent);
+
       BER_Decoder* m_parent = nullptr;
       BER_Object m_pushed;
       // either m_data_src.get() or an unowned pointer
@@ -241,17 +338,19 @@ BER_Decoder& BER_Decoder::decode_optional(T& out,
    if(obj.is_a(type_tag, class_tag))
       {
       if((class_tag & CONSTRUCTED) && (class_tag & CONTEXT_SPECIFIC))
+         {
          BER_Decoder(obj).decode(out).verify_end();
+         }
       else
          {
-         push_back(obj);
+         push_back(std::move(obj));
          decode(out, type_tag, class_tag);
          }
       }
    else
       {
       out = default_value;
-      push_back(obj);
+      push_back(std::move(obj));
       }
 
    return (*this);
@@ -274,13 +373,14 @@ BER_Decoder& BER_Decoder::decode_optional_implicit(
    if(obj.is_a(type_tag, class_tag))
       {
       obj.set_tagging(real_type, real_class);
-      push_back(obj);
+      push_back(std::move(obj));
       decode(out, real_type, real_class);
       }
    else
       {
+      // Not what we wanted, push it back on the stream
       out = default_value;
-      push_back(obj);
+      push_back(std::move(obj));
       }
 
    return (*this);
@@ -299,7 +399,7 @@ BER_Decoder& BER_Decoder::decode_list(std::vector<T>& vec,
       {
       T value;
       list.decode(value);
-      vec.push_back(value);
+      vec.push_back(std::move(value));
       }
 
    list.end_cons();