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

RLP::RLP(bytesConstRef _d, Strictness _s):
        m_data(_d)
{
        if ((_s & FailIfTooBig) && actualSize() < _d.size())
        {
                if (_s & ThrowOnFail)
                        BOOST_THROW_EXCEPTION(OversizeRLP());
                else
                        m_data.reset();
        }
        if ((_s & FailIfTooSmall) && actualSize() > _d.size())
        {
                if (_s & ThrowOnFail)
                        BOOST_THROW_EXCEPTION(UndersizeRLP());
                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);
}

RLPs RLP::toList(int _flags) const
{
        RLPs ret;
        if (!isList())
        {
                if (_flags & ThrowOnFail)
                        BOOST_THROW_EXCEPTION(BadCast());
                else
                        return ret;
        }
        for (auto const& i: *this)
                ret.push_back(i);
        return ret;
}

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