RLP.cpp

Go to the documentation of this file.

/*
    This file is part of cpp-ethereum.
 
    cpp-ethereum is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
 
    cpp-ethereum 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 cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
*/
 
#include "RLP.h"
using namespace std;
using namespace dev;
 
bytes dev::RLPNull = rlp("");
bytes dev::RLPEmptyList = rlpList();
 
namespace {
 
errinfo_comment constructRLPSizeErrorInfo(size_t _actualSize, size_t _dataSize)
{
    std::stringstream s;
    s << "Actual size: " << _actualSize << ", data size: " << _dataSize;
    return errinfo_comment(s.str());
}
 
}
 
RLP::RLP(bytesConstRef _d, Strictness _s):
    m_data(_d)
{
    if ((_s & FailIfTooBig) && actualSize() < _d.size())
    {
        if (_s & ThrowOnFail)
            BOOST_THROW_EXCEPTION(OversizeRLP() << constructRLPSizeErrorInfo(actualSize(), _d.size()));
        else
            m_data.reset();
    }
    if ((_s & FailIfTooSmall) && actualSize() > _d.size())
    {
        if (_s & ThrowOnFail)
            BOOST_THROW_EXCEPTION(UndersizeRLP() << constructRLPSizeErrorInfo(actualSize(), _d.size()));
        else
            m_data.reset();
    }
}
 
RLP::iterator& RLP::iterator::operator++()
{
    if (m_remaining)
    {
        m_currentItem.retarget(m_currentItem.next().data(), m_remaining);
        m_currentItem = m_currentItem.cropped(0, sizeAsEncoded(m_currentItem));
        m_remaining -= std::min<size_t>(m_remaining, m_currentItem.size());
    }
    else
        m_currentItem.retarget(m_currentItem.next().data(), 0);
    return *this;
}
 
RLP::iterator::iterator(RLP const& _parent, bool _begin)
{
    if (_begin && _parent.isList())
    {
        auto pl = _parent.payload();
        m_currentItem = pl.cropped(0, sizeAsEncoded(pl));
        m_remaining = pl.size() - m_currentItem.size();
    }
    else
    {
        m_currentItem = _parent.data().cropped(_parent.data().size());
        m_remaining = 0;
    }
}
 
RLP RLP::operator[](size_t _i) const
{
    if (_i < m_lastIndex)
    {
        m_lastEnd = sizeAsEncoded(payload());
        m_lastItem = payload().cropped(0, m_lastEnd);
        m_lastIndex = 0;
    }
    for (; m_lastIndex < _i && m_lastItem.size(); ++m_lastIndex)
    {
        m_lastItem = payload().cropped(m_lastEnd);
        m_lastItem = m_lastItem.cropped(0, sizeAsEncoded(m_lastItem));
        m_lastEnd += m_lastItem.size();
    }
    return RLP(m_lastItem, ThrowOnFail | FailIfTooSmall);
}
 
size_t RLP::actualSize() const
{
    if (isNull())
        return 0;
    if (isSingleByte())
        return 1;
    if (isData() || isList())
        return payloadOffset() + length();
    return 0;
}
 
void RLP::requireGood() const
{
    if (isNull())
        BOOST_THROW_EXCEPTION(BadRLP());
    byte n = m_data[0];
    if (n != c_rlpDataImmLenStart + 1)
        return;
    if (m_data.size() < 2)
        BOOST_THROW_EXCEPTION(BadRLP());
    if (m_data[1] < c_rlpDataImmLenStart)
        BOOST_THROW_EXCEPTION(BadRLP());
}
 
bool RLP::isInt() const
{
    if (isNull())
        return false;
    requireGood();
    byte n = m_data[0];
    if (n < c_rlpDataImmLenStart)
        return !!n;
    else if (n == c_rlpDataImmLenStart)
        return true;
    else if (n <= c_rlpDataIndLenZero)
    {
        if (m_data.size() <= 1)
            BOOST_THROW_EXCEPTION(BadRLP());
        return m_data[1] != 0;
    }
    else if (n < c_rlpListStart)
    {
        if (m_data.size() <= size_t(1 + n - c_rlpDataIndLenZero))
            BOOST_THROW_EXCEPTION(BadRLP());
        return m_data[1 + n - c_rlpDataIndLenZero] != 0;
    }
    else
        return false;
    return false;
}
 
size_t RLP::length() const
{
    if (isNull())
        return 0;
    requireGood();
    size_t ret = 0;
    byte const n = m_data[0];
    if (n < c_rlpDataImmLenStart)
        return 1;
    else if (n <= c_rlpDataIndLenZero)
        return n - c_rlpDataImmLenStart;
    else if (n < c_rlpListStart)
    {
        if (m_data.size() <= size_t(n - c_rlpDataIndLenZero))
            BOOST_THROW_EXCEPTION(BadRLP());
        if (m_data.size() > 1)
            if (m_data[1] == 0)
                BOOST_THROW_EXCEPTION(BadRLP());
        unsigned lengthSize = n - c_rlpDataIndLenZero;
        if (lengthSize > sizeof(ret))
            // We did not check, but would most probably not fit in our memory.
            BOOST_THROW_EXCEPTION(UndersizeRLP());
        // No leading zeroes.
        if (!m_data[1])
            BOOST_THROW_EXCEPTION(BadRLP());
        for (unsigned i = 0; i < lengthSize; ++i)
            ret = (ret << 8) | m_data[i + 1];
        // Must be greater than the limit.
        if (ret < c_rlpListStart - c_rlpDataImmLenStart - c_rlpMaxLengthBytes)
            BOOST_THROW_EXCEPTION(BadRLP());
    }
    else if (n <= c_rlpListIndLenZero)
        return n - c_rlpListStart;
    else
    {
        unsigned lengthSize = n - c_rlpListIndLenZero;
        if (m_data.size() <= lengthSize)
            BOOST_THROW_EXCEPTION(BadRLP());
        if (m_data.size() > 1)
            if (m_data[1] == 0)
                BOOST_THROW_EXCEPTION(BadRLP());
        if (lengthSize > sizeof(ret))
            // We did not check, but would most probably not fit in our memory.
            BOOST_THROW_EXCEPTION(UndersizeRLP());
        if (!m_data[1])
            BOOST_THROW_EXCEPTION(BadRLP());
        for (unsigned i = 0; i < lengthSize; ++i)
            ret = (ret << 8) | m_data[i + 1];
        if (ret < 0x100 - c_rlpListStart - c_rlpMaxLengthBytes)
            BOOST_THROW_EXCEPTION(BadRLP());
    }
    // We have to be able to add payloadOffset to length without overflow.
    // This rejects roughly 4GB-sized RLPs on some platforms.
    if (ret >= std::numeric_limits<size_t>::max() - 0x100)
        BOOST_THROW_EXCEPTION(UndersizeRLP());
    return ret;
}
 
size_t RLP::items() const
{
    if (isList())
    {
        bytesConstRef d = payload();
        size_t i = 0;
        for (; d.size(); ++i)
            d = d.cropped(sizeAsEncoded(d));
        return i;
    }
    return 0;
}
 
RLPStream& RLPStream::appendRaw(bytesConstRef _s, size_t _itemCount)
{
    m_out.insert(m_out.end(), _s.begin(), _s.end());
    noteAppended(_itemCount);
    return *this;
}
 
void RLPStream::noteAppended(size_t _itemCount)
{
    if (!_itemCount)
        return;
//  cdebug << "noteAppended(" << _itemCount << ")";
    while (m_listStack.size())
    {
        if (m_listStack.back().first < _itemCount)
            BOOST_THROW_EXCEPTION(RLPException() << errinfo_comment("itemCount too large") << RequirementError((bigint)m_listStack.back().first, (bigint)_itemCount));
        m_listStack.back().first -= _itemCount;
        if (m_listStack.back().first)
            break;
        else
        {
            auto p = m_listStack.back().second;
            m_listStack.pop_back();
            size_t s = m_out.size() - p;        // list size
            auto brs = bytesRequired(s);
            unsigned encodeSize = s < c_rlpListImmLenCount ? 1 : (1 + brs);
//          cdebug << "s: " << s << ", p: " << p << ", m_out.size(): " << m_out.size() << ", encodeSize: " << encodeSize << " (br: " << brs << ")";
            auto os = m_out.size();
            m_out.resize(os + encodeSize);
            memmove(m_out.data() + p + encodeSize, m_out.data() + p, os - p);
            if (s < c_rlpListImmLenCount)
                m_out[p] = (byte)(c_rlpListStart + s);
            else if (c_rlpListIndLenZero + brs <= 0xff)
            {
                m_out[p] = (byte)(c_rlpListIndLenZero + brs);
                byte* b = &(m_out[p + brs]);
                for (; s; s >>= 8)
                    *(b--) = (byte)s;
            }
            else
                BOOST_THROW_EXCEPTION(RLPException() << errinfo_comment("itemCount too large for RLP"));
        }
        _itemCount = 1; // for all following iterations, we've effectively appended a single item only since we completed a list.
    }
}
 
RLPStream& RLPStream::appendList(size_t _items)
{
//  cdebug << "appendList(" << _items << ")";
    if (_items)
        m_listStack.push_back(std::make_pair(_items, m_out.size()));
    else
        appendList(bytes());
    return *this;
}
 
RLPStream& RLPStream::appendList(bytesConstRef _rlp)
{
    if (_rlp.size() < c_rlpListImmLenCount)
        m_out.push_back((byte)(_rlp.size() + c_rlpListStart));
    else
        pushCount(_rlp.size(), c_rlpListIndLenZero);
    appendRaw(_rlp, 1);
    return *this;
}
 
RLPStream& RLPStream::append(bytesConstRef _s, bool _compact)
{
    size_t s = _s.size();
    byte const* d = _s.data();
    if (_compact)
        for (size_t i = 0; i < _s.size() && !*d; ++i, --s, ++d) {}
 
    if (s == 1 && *d < c_rlpDataImmLenStart)
        m_out.push_back(*d);
    else
    {
        if (s < c_rlpDataImmLenCount)
            m_out.push_back((byte)(s + c_rlpDataImmLenStart));
        else
            pushCount(s, c_rlpDataIndLenZero);
        appendRaw(bytesConstRef(d, s), 0);
    }
    noteAppended();
    return *this;
}
 
RLPStream& RLPStream::append(bigint _i)
{
    if (!_i)
        m_out.push_back(c_rlpDataImmLenStart);
    else if (_i < c_rlpDataImmLenStart)
        m_out.push_back((byte)_i);
    else
    {
        unsigned br = bytesRequired(_i);
        if (br < c_rlpDataImmLenCount)
            m_out.push_back((byte)(br + c_rlpDataImmLenStart));
        else
        {
            auto brbr = bytesRequired(br);
            if (c_rlpDataIndLenZero + brbr > 0xff)
                BOOST_THROW_EXCEPTION(RLPException() << errinfo_comment("Number too large for RLP"));
            m_out.push_back((byte)(c_rlpDataIndLenZero + brbr));
            pushInt(br, brbr);
        }
        pushInt(_i, br);
    }
    noteAppended();
    return *this;
}
 
void RLPStream::pushCount(size_t _count, byte _base)
{
    auto br = bytesRequired(_count);
    if (int(br) + _base > 0xff)
        BOOST_THROW_EXCEPTION(RLPException() << errinfo_comment("Count too large for RLP"));
    m_out.push_back((byte)(br + _base));    // max 8 bytes.
    pushInt(_count, br);
}
 
static void streamOut(std::ostream& _out, dev::RLP const& _d, unsigned _depth = 0)
{
    if (_depth > 64)
        _out << "<max-depth-reached>";
    else if (_d.isNull())
        _out << "null";
    else if (_d.isInt())
        _out << std::showbase << std::hex << std::nouppercase << _d.toInt<bigint>(RLP::LaissezFaire) << dec;
    else if (_d.isData())
        _out << escaped(_d.toString(), false);
    else if (_d.isList())
    {
        _out << "[";
        int j = 0;
        for (auto i: _d)
        {
            _out << (j++ ? ", " : " ");
            streamOut(_out, i, _depth + 1);
        }
        _out << " ]";
    }
}
 
std::ostream& dev::operator<<(std::ostream& _out, RLP const& _d)
{
    streamOut(_out, _d);
    return _out;
}