queue.cpp

// queue.cpp - originally written and placed in the public domain by Wei Dai
 
#include "pch.h"
 
#ifndef CRYPTOPP_IMPORTS
 
#include "queue.h"
#include "filters.h"
#include "misc.h"
#include "trap.h"
 
NAMESPACE_BEGIN(CryptoPP)
 
static const unsigned int s_maxAutoNodeSize = 16*1024u;
 
// this class for use by ByteQueue only
class ByteQueueNode
{
public:
        ByteQueueNode(size_t maxSize)
                : m_buf(maxSize)
        {
                // See GH #962 for the reason for this assert.
                CRYPTOPP_ASSERT(maxSize != SIZE_MAX);
 
                m_head = m_tail = 0;
                m_next = NULLPTR;
        }
 
        inline size_t MaxSize() const {return m_buf.size();}
 
        inline size_t CurrentSize() const
        {
                return m_tail-m_head;
        }
 
        inline bool UsedUp() const
        {
                return (m_head==MaxSize());
        }
 
        inline void Clear()
        {
                m_head = m_tail = 0;
        }
 
        inline size_t Put(const byte *begin, size_t length)
        {
                // Avoid passing NULL to memcpy
                if (!begin || !length) return length;
                size_t l = STDMIN(length, MaxSize()-m_tail);
                if (m_buf+m_tail != begin)
                        memcpy(m_buf+m_tail, begin, l);
                m_tail += l;
                return l;
        }
 
        inline size_t Peek(byte &outByte) const
        {
                if (m_tail==m_head)
                        return 0;
 
                outByte=m_buf[m_head];
                return 1;
        }
 
        inline size_t Peek(byte *target, size_t copyMax) const
        {
                size_t len = STDMIN(copyMax, m_tail-m_head);
                memcpy(target, m_buf+m_head, len);
                return len;
        }
 
        inline size_t CopyTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL) const
        {
                size_t len = m_tail-m_head;
                target.ChannelPut(channel, m_buf+m_head, len);
                return len;
        }
 
        inline size_t CopyTo(BufferedTransformation &target, size_t copyMax, const std::string &channel=DEFAULT_CHANNEL) const
        {
                size_t len = STDMIN(copyMax, m_tail-m_head);
                target.ChannelPut(channel, m_buf+m_head, len);
                return len;
        }
 
        inline size_t Get(byte &outByte)
        {
                size_t len = Peek(outByte);
                m_head += len;
                return len;
        }
 
        inline size_t Get(byte *outString, size_t getMax)
        {
                size_t len = Peek(outString, getMax);
                m_head += len;
                return len;
        }
 
        inline size_t TransferTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL)
        {
                size_t len = m_tail-m_head;
                target.ChannelPutModifiable(channel, m_buf+m_head, len);
                m_head = m_tail;
                return len;
        }
 
        inline size_t TransferTo(BufferedTransformation &target, lword transferMax, const std::string &channel=DEFAULT_CHANNEL)
        {
                size_t len = UnsignedMin(m_tail-m_head, transferMax);
                target.ChannelPutModifiable(channel, m_buf+m_head, len);
                m_head += len;
                return len;
        }
 
        inline size_t Skip(size_t skipMax)
        {
                size_t len = STDMIN(skipMax, m_tail-m_head);
                m_head += len;
                return len;
        }
 
        inline byte operator[](size_t i) const
        {
                return m_buf[m_head+i];
        }
 
        ByteQueueNode* m_next;
 
        SecByteBlock m_buf;
        size_t m_head, m_tail;
};
 
// ********************************************************
 
ByteQueue::ByteQueue(size_t nodeSize)
        : Bufferless<BufferedTransformation>()
        , m_head(NULLPTR), m_tail(NULLPTR), m_lazyString(NULLPTR), m_lazyLength(0)
        , m_nodeSize(nodeSize), m_lazyStringModifiable(false), m_autoNodeSize(!nodeSize)
{
        // See GH #962 for the reason for this assert.
        CRYPTOPP_ASSERT(nodeSize != SIZE_MAX);
 
        SetNodeSize(nodeSize);
        m_head = m_tail = new ByteQueueNode(m_nodeSize);
}
 
void ByteQueue::SetNodeSize(size_t nodeSize)
{
        m_autoNodeSize = !nodeSize;
        m_nodeSize = m_autoNodeSize ? 256 : nodeSize;
}
 
ByteQueue::ByteQueue(const ByteQueue &copy)
        : Bufferless<BufferedTransformation>(copy), m_lazyString(NULLPTR), m_lazyLength(0)
{
        CopyFrom(copy);
}
 
void ByteQueue::CopyFrom(const ByteQueue &copy)
{
        m_lazyLength = 0;
        m_autoNodeSize = copy.m_autoNodeSize;
        m_nodeSize = copy.m_nodeSize;
        m_head = m_tail = new ByteQueueNode(*copy.m_head);
 
        for (ByteQueueNode *current=copy.m_head->m_next; current; current=current->m_next)
        {
                m_tail->m_next = new ByteQueueNode(*current);
                m_tail = m_tail->m_next;
        }
 
        m_tail->m_next = NULLPTR;
 
        Put(copy.m_lazyString, copy.m_lazyLength);
}
 
ByteQueue::~ByteQueue()
{
        Destroy();
}
 
void ByteQueue::Destroy()
{
        for (ByteQueueNode *next, *current=m_head; current; current=next)
        {
                next=current->m_next;
                delete current;
        }
}
 
void ByteQueue::IsolatedInitialize(const NameValuePairs &parameters)
{
        m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256);
        Clear();
}
 
lword ByteQueue::CurrentSize() const
{
        lword size=0;
 
        for (ByteQueueNode *current=m_head; current; current=current->m_next)
                size += current->CurrentSize();
 
        return size + m_lazyLength;
}
 
bool ByteQueue::IsEmpty() const
{
        return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0;
}
 
void ByteQueue::Clear()
{
        for (ByteQueueNode *next, *current=m_head->m_next; current; current=next)
        {
                next=current->m_next;
                delete current;
        }
 
        m_tail = m_head;
        m_head->Clear();
        m_head->m_next = NULLPTR;
        m_lazyLength = 0;
}
 
size_t ByteQueue::Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
{
        CRYPTOPP_UNUSED(messageEnd), CRYPTOPP_UNUSED(blocking);
 
        if (m_lazyLength > 0)
                FinalizeLazyPut();
 
        size_t len;
        while ((len=m_tail->Put(inString, length)) < length)
        {
                inString = PtrAdd(inString, len);
                length -= len;
                if (m_autoNodeSize && m_nodeSize < s_maxAutoNodeSize)
                {
                        do
                        {
                                m_nodeSize *= 2;
                        }
                        while (m_nodeSize < length && m_nodeSize < s_maxAutoNodeSize);
                }
                m_tail->m_next = new ByteQueueNode(STDMAX(m_nodeSize, length));
                m_tail = m_tail->m_next;
        }
 
        return 0;
}
 
void ByteQueue::CleanupUsedNodes()
{
        // Test for m_head due to Enterprise Analysis finding
        while (m_head && m_head != m_tail && m_head->UsedUp())
        {
                ByteQueueNode *temp=m_head;
                m_head=m_head->m_next;
                delete temp;
        }
 
        // Test for m_head due to Enterprise Analysis finding
        if (m_head && m_head->CurrentSize() == 0)
                m_head->Clear();
}
 
void ByteQueue::LazyPut(const byte *inString, size_t size)
{
        if (m_lazyLength > 0)
                FinalizeLazyPut();
 
        if (inString == m_tail->m_buf+m_tail->m_tail)
                Put(inString, size);
        else
        {
                m_lazyString = const_cast<byte *>(inString);
                m_lazyLength = size;
                m_lazyStringModifiable = false;
        }
}
 
void ByteQueue::LazyPutModifiable(byte *inString, size_t size)
{
        if (m_lazyLength > 0)
                FinalizeLazyPut();
        m_lazyString = inString;
        m_lazyLength = size;
        m_lazyStringModifiable = true;
}
 
void ByteQueue::UndoLazyPut(size_t size)
{
        if (m_lazyLength < size)
                throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large");
 
        m_lazyLength -= size;
}
 
void ByteQueue::FinalizeLazyPut()
{
        size_t len = m_lazyLength;
        m_lazyLength = 0;
        if (len)
                Put(m_lazyString, len);
}
 
size_t ByteQueue::Get(byte &outByte)
{
        if (m_head->Get(outByte))
        {
                if (m_head->UsedUp())
                        CleanupUsedNodes();
                return 1;
        }
        else if (m_lazyLength > 0)
        {
                outByte = *m_lazyString++;
                m_lazyLength--;
                return 1;
        }
        else
                return 0;
}
 
size_t ByteQueue::Get(byte *outString, size_t getMax)
{
        ArraySink sink(outString, getMax);
        return (size_t)TransferTo(sink, getMax);
}
 
size_t ByteQueue::Peek(byte &outByte) const
{
        if (m_head->Peek(outByte))
                return 1;
        else if (m_lazyLength > 0)
        {
                outByte = *m_lazyString;
                return 1;
        }
        else
                return 0;
}
 
size_t ByteQueue::Peek(byte *outString, size_t peekMax) const
{
        ArraySink sink(outString, peekMax);
        return (size_t)CopyTo(sink, peekMax);
}
 
size_t ByteQueue::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
{
        // No need for CRYPTOPP_ASSERT on transferBytes here.
        // TransferTo2 handles LWORD_MAX as expected.
 
        if (blocking)
        {
                lword bytesLeft = transferBytes;
                for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->m_next)
                        bytesLeft -= current->TransferTo(target, bytesLeft, channel);
                CleanupUsedNodes();
 
                size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
                if (len)
                {
                        if (m_lazyStringModifiable)
                                target.ChannelPutModifiable(channel, m_lazyString, len);
                        else
                                target.ChannelPut(channel, m_lazyString, len);
                        m_lazyString = PtrAdd(m_lazyString, len);
                        m_lazyLength -= len;
                        bytesLeft -= len;
                }
                transferBytes -= bytesLeft;
                return 0;
        }
        else
        {
                Walker walker(*this);
                size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
                Skip(transferBytes);
                return blockedBytes;
        }
}
 
size_t ByteQueue::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
{
        Walker walker(*this);
        walker.Skip(begin);
        lword transferBytes = end-begin;
 
        size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
        begin += transferBytes;
        return blockedBytes;
}
 
void ByteQueue::Unget(byte inByte)
{
        Unget(&inByte, 1);
}
 
void ByteQueue::Unget(const byte *inString, size_t length)
{
        // See GH #962 for the reason for this assert.
        CRYPTOPP_ASSERT(length != SIZE_MAX);
 
        size_t len = STDMIN(length, m_head->m_head);
        length -= len;
        m_head->m_head = m_head->m_head - len;
        memcpy(m_head->m_buf + m_head->m_head, inString + length, len);
 
        if (length > 0)
        {
                ByteQueueNode *newHead = new ByteQueueNode(length);
                newHead->m_next = m_head;
                m_head = newHead;
                m_head->Put(inString, length);
        }
}
 
const byte * ByteQueue::Spy(size_t &contiguousSize) const
{
        contiguousSize = m_head->m_tail - m_head->m_head;
        if (contiguousSize == 0 && m_lazyLength > 0)
        {
                contiguousSize = m_lazyLength;
                return m_lazyString;
        }
        else
                return m_head->m_buf + m_head->m_head;
}
 
byte * ByteQueue::CreatePutSpace(size_t &size)
{
        // See GH #962 for the reason for this assert.
        CRYPTOPP_ASSERT(size != SIZE_MAX);
        // Sanity check for a reasonable size
        CRYPTOPP_ASSERT(size <= 16U*1024*1024);
 
        if (m_lazyLength > 0)
                FinalizeLazyPut();
 
        if (m_tail->m_tail == m_tail->MaxSize())
        {
                m_tail->m_next = new ByteQueueNode(STDMAX(m_nodeSize, size));
                m_tail = m_tail->m_next;
        }
 
        size = m_tail->MaxSize() - m_tail->m_tail;
        return PtrAdd(m_tail->m_buf.begin(), m_tail->m_tail);
}
 
ByteQueue & ByteQueue::operator=(const ByteQueue &rhs)
{
        Destroy();
        CopyFrom(rhs);
        return *this;
}
 
bool ByteQueue::operator==(const ByteQueue &rhs) const
{
        const lword currentSize = CurrentSize();
 
        if (currentSize != rhs.CurrentSize())
                return false;
 
        Walker walker1(*this), walker2(rhs);
        byte b1, b2;
 
        while (walker1.Get(b1) && walker2.Get(b2))
                if (b1 != b2)
                        return false;
 
        return true;
}
 
byte ByteQueue::operator[](lword index) const
{
        for (ByteQueueNode *current=m_head; current; current=current->m_next)
        {
                if (index < current->CurrentSize())
                        return (*current)[(size_t)index];
 
                index -= current->CurrentSize();
        }
 
        CRYPTOPP_ASSERT(index < m_lazyLength);
        return m_lazyString[index];
}
 
void ByteQueue::swap(ByteQueue &rhs)
{
        std::swap(m_autoNodeSize, rhs.m_autoNodeSize);
        std::swap(m_nodeSize, rhs.m_nodeSize);
        std::swap(m_head, rhs.m_head);
        std::swap(m_tail, rhs.m_tail);
        std::swap(m_lazyString, rhs.m_lazyString);
        std::swap(m_lazyLength, rhs.m_lazyLength);
        std::swap(m_lazyStringModifiable, rhs.m_lazyStringModifiable);
}
 
// ********************************************************
 
void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs &parameters)
{
        CRYPTOPP_UNUSED(parameters);
 
        m_node = m_queue.m_head;
        m_position = 0;
        m_offset = 0;
        m_lazyString = m_queue.m_lazyString;
        m_lazyLength = m_queue.m_lazyLength;
}
 
size_t ByteQueue::Walker::Get(byte &outByte)
{
        ArraySink sink(&outByte, 1);
        return (size_t)TransferTo(sink, 1);
}
 
size_t ByteQueue::Walker::Get(byte *outString, size_t getMax)
{
        ArraySink sink(outString, getMax);
        return (size_t)TransferTo(sink, getMax);
}
 
size_t ByteQueue::Walker::Peek(byte &outByte) const
{
        ArraySink sink(&outByte, 1);
        return (size_t)CopyTo(sink, 1);
}
 
size_t ByteQueue::Walker::Peek(byte *outString, size_t peekMax) const
{
        ArraySink sink(outString, peekMax);
        return (size_t)CopyTo(sink, peekMax);
}
 
size_t ByteQueue::Walker::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
{
        // No need for CRYPTOPP_ASSERT on transferBytes here.
        // TransferTo2 handles LWORD_MAX as expected.
 
        lword bytesLeft = transferBytes;
        size_t blockedBytes = 0;
 
        while (m_node)
        {
                size_t len = (size_t)STDMIN(bytesLeft, (lword)m_node->CurrentSize()-m_offset);
                blockedBytes = target.ChannelPut2(channel, m_node->m_buf+m_node->m_head+m_offset, len, 0, blocking);
 
                if (blockedBytes)
                        goto done;
 
                m_position += len;
                bytesLeft -= len;
 
                if (!bytesLeft)
                {
                        m_offset += len;
                        goto done;
                }
 
                m_node = m_node->m_next;
                m_offset = 0;
        }
 
        if (bytesLeft && m_lazyLength)
        {
                size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
                blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking);
                if (blockedBytes)
                        goto done;
 
                m_lazyString = PtrAdd(m_lazyString, len);
                m_lazyLength -= len;
                bytesLeft -= len;
        }
 
done:
        transferBytes -= bytesLeft;
        return blockedBytes;
}
 
size_t ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
{
        Walker walker(*this);
        walker.Skip(begin);
        lword transferBytes = end-begin;
 
        size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
        begin += transferBytes;
        return blockedBytes;
}
 
NAMESPACE_END
 
#endif