path: root/queue.cpp

// queue.cpp - written and placed in the public domain by Wei Dai

#include "pch.h"
#include "queue.h"
#include "filters.h"

NAMESPACE_BEGIN(CryptoPP)

static const unsigned int s_maxAutoNodeSize = 16*1024;

// this class for use by ByteQueue only
class ByteQueueNode
{
public:
	ByteQueueNode(unsigned int maxSize)
		: buf(maxSize)
	{
		m_head = m_tail = 0;
		next = 0;
	}

	inline unsigned int MaxSize() const {return buf.size();}

	inline unsigned int CurrentSize() const
	{
		return m_tail-m_head;
	}

	inline bool UsedUp() const
	{
		return (m_head==MaxSize());
	}

	inline void Clear()
	{
		m_head = m_tail = 0;
	}

	inline unsigned int Put(const byte *begin, unsigned int length)
	{
		unsigned int l = STDMIN(length, MaxSize()-m_tail);
		if (buf+m_tail != begin)
			memcpy(buf+m_tail, begin, l);
		m_tail += l;
		return l;
	}

	inline unsigned int Peek(byte &outByte) const
	{
		if (m_tail==m_head)
			return 0;

		outByte=buf[m_head];
		return 1;
	}

	inline unsigned int Peek(byte *target, unsigned int copyMax) const
	{
		unsigned int len = STDMIN(copyMax, m_tail-m_head);
		memcpy(target, buf+m_head, len);
		return len;
	}

	inline unsigned int CopyTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const
	{
		unsigned int len = m_tail-m_head;
		target.ChannelPut(channel, buf+m_head, len);
		return len;
	}

	inline unsigned int CopyTo(BufferedTransformation &target, unsigned int copyMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL) const
	{
		unsigned int len = STDMIN(copyMax, m_tail-m_head);
		target.ChannelPut(channel, buf+m_head, len);
		return len;
	}

	inline unsigned int Get(byte &outByte)
	{
		unsigned int len = Peek(outByte);
		m_head += len;
		return len;
	}

	inline unsigned int Get(byte *outString, unsigned int getMax)
	{
		unsigned int len = Peek(outString, getMax);
		m_head += len;
		return len;
	}

	inline unsigned int TransferTo(BufferedTransformation &target, const std::string &channel=BufferedTransformation::NULL_CHANNEL)
	{
		unsigned int len = m_tail-m_head;
		target.ChannelPutModifiable(channel, buf+m_head, len);
		m_head = m_tail;
		return len;
	}

	inline unsigned int TransferTo(BufferedTransformation &target, unsigned int transferMax, const std::string &channel=BufferedTransformation::NULL_CHANNEL)
	{
		unsigned int len = STDMIN(transferMax, m_tail-m_head);
		target.ChannelPutModifiable(channel, buf+m_head, len);
		m_head += len;
		return len;
	}

	inline unsigned int Skip(unsigned int skipMax)
	{
		unsigned int len = STDMIN(skipMax, m_tail-m_head);
		m_head += len;
		return len;
	}

	inline byte operator[](unsigned int i) const
	{
		return buf[m_head+i];
	}

	ByteQueueNode *next;

	SecByteBlock buf;
	unsigned int m_head, m_tail;
};

// ********************************************************

ByteQueue::ByteQueue(unsigned int nodeSize)
	: m_autoNodeSize(m_nodeSize==0), m_nodeSize(nodeSize ? nodeSize : 256), m_lazyLength(0)
{
	m_head = m_tail = new ByteQueueNode(m_nodeSize);
}

ByteQueue::ByteQueue(const ByteQueue &copy)
{
	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->next; current; current=current->next)
	{
		m_tail->next = new ByteQueueNode(*current);
		m_tail = m_tail->next;
	}

	m_tail->next = NULL;

	Put(copy.m_lazyString, copy.m_lazyLength);
}

ByteQueue::~ByteQueue()
{
	Destroy();
}

void ByteQueue::Destroy()
{
	for (ByteQueueNode *next, *current=m_head; current; current=next)
	{
		next=current->next;
		delete current;
	}
}

void ByteQueue::IsolatedInitialize(const NameValuePairs &parameters)
{
	m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256);
	Clear();
}

unsigned long ByteQueue::CurrentSize() const
{
	unsigned long size=0;

	for (ByteQueueNode *current=m_head; current; current=current->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->next; current; current=next)
	{
		next=current->next;
		delete current;
	}

	m_tail = m_head;
	m_head->Clear();
	m_head->next = NULL;
	m_lazyLength = 0;
}

unsigned int ByteQueue::Put2(const byte *inString, unsigned int length, int messageEnd, bool blocking)
{
	if (m_lazyLength > 0)
		FinalizeLazyPut();

	unsigned int len;
	while ((len=m_tail->Put(inString, length)) < length)
	{
		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->next = new ByteQueueNode(STDMAX(m_nodeSize, length));
		m_tail = m_tail->next;
	}

	return 0;
}

void ByteQueue::CleanupUsedNodes()
{
	while (m_head != m_tail && m_head->UsedUp())
	{
		ByteQueueNode *temp=m_head;
		m_head=m_head->next;
		delete temp;
	}

	if (m_head->CurrentSize() == 0)
		m_head->Clear();
}

void ByteQueue::LazyPut(const byte *inString, unsigned int size)
{
	if (m_lazyLength > 0)
		FinalizeLazyPut();

	if (inString == m_tail->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, unsigned int size)
{
	if (m_lazyLength > 0)
		FinalizeLazyPut();
	m_lazyString = inString;
	m_lazyLength = size;
	m_lazyStringModifiable = true;
}

void ByteQueue::UndoLazyPut(unsigned int size)
{
	if (m_lazyLength < size)
		throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large");

	m_lazyLength -= size;
}

void ByteQueue::FinalizeLazyPut()
{
	unsigned int len = m_lazyLength;
	m_lazyLength = 0;
	if (len)
		Put(m_lazyString, len);
}

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

unsigned int ByteQueue::Get(byte *outString, unsigned int getMax)
{
	ArraySink sink(outString, getMax);
	return TransferTo(sink, getMax);
}

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

unsigned int ByteQueue::Peek(byte *outString, unsigned int peekMax) const
{
	ArraySink sink(outString, peekMax);
	return CopyTo(sink, peekMax);
}

unsigned int ByteQueue::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking)
{
	if (blocking)
	{
		unsigned long bytesLeft = transferBytes;
		for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->next)
			bytesLeft -= current->TransferTo(target, bytesLeft, channel);
		CleanupUsedNodes();

		unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)m_lazyLength);
		if (len)
		{
			if (m_lazyStringModifiable)
				target.ChannelPutModifiable(channel, m_lazyString, len);
			else
				target.ChannelPut(channel, m_lazyString, len);
			m_lazyString += len;
			m_lazyLength -= len;
			bytesLeft -= len;
		}
		transferBytes -= bytesLeft;
		return 0;
	}
	else
	{
		Walker walker(*this);
		unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
		Skip(transferBytes);
		return blockedBytes;
	}
}

unsigned int ByteQueue::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const
{
	Walker walker(*this);
	walker.Skip(begin);
	unsigned long transferBytes = end-begin;
	unsigned int 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, unsigned int length)
{
	unsigned int len = STDMIN(length, m_head->m_head);
	length -= len;
	m_head->m_head -= len;
	memcpy(m_head->buf + m_head->m_head, inString + length, len);

	if (length > 0)
	{
		ByteQueueNode *newHead = new ByteQueueNode(length);
		newHead->next = m_head;
		m_head = newHead;
		m_head->Put(inString, length);
	}
}

const byte * ByteQueue::Spy(unsigned int &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->buf + m_head->m_head;
}

byte * ByteQueue::CreatePutSpace(unsigned int &size)
{
	if (m_lazyLength > 0)
		FinalizeLazyPut();

	if (m_tail->m_tail == m_tail->MaxSize())
	{
		m_tail->next = new ByteQueueNode(STDMAX(m_nodeSize, size));
		m_tail = m_tail->next;
	}

	size = m_tail->MaxSize() - m_tail->m_tail;
	return m_tail->buf + m_tail->m_tail;
}

ByteQueue & ByteQueue::operator=(const ByteQueue &rhs)
{
	Destroy();
	CopyFrom(rhs);
	return *this;
}

bool ByteQueue::operator==(const ByteQueue &rhs) const
{
	const unsigned long 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[](unsigned long i) const
{
	for (ByteQueueNode *current=m_head; current; current=current->next)
	{
		if (i < current->CurrentSize())
			return (*current)[i];
		
		i -= current->CurrentSize();
	}

	assert(i < m_lazyLength);
	return m_lazyString[i];
}

void ByteQueue::swap(ByteQueue &rhs)
{
	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);
}

// ********************************************************

void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs &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;
}

unsigned int ByteQueue::Walker::Get(byte &outByte)
{
	ArraySink sink(&outByte, 1);
	return TransferTo(sink, 1);
}

unsigned int ByteQueue::Walker::Get(byte *outString, unsigned int getMax)
{
	ArraySink sink(outString, getMax);
	return TransferTo(sink, getMax);
}

unsigned int ByteQueue::Walker::Peek(byte &outByte) const
{
	ArraySink sink(&outByte, 1);
	return CopyTo(sink, 1);
}

unsigned int ByteQueue::Walker::Peek(byte *outString, unsigned int peekMax) const
{
	ArraySink sink(outString, peekMax);
	return CopyTo(sink, peekMax);
}

unsigned int ByteQueue::Walker::TransferTo2(BufferedTransformation &target, unsigned long &transferBytes, const std::string &channel, bool blocking)
{
	unsigned long bytesLeft = transferBytes;
	unsigned int blockedBytes = 0;

	while (m_node)
	{
		unsigned int len = STDMIN(bytesLeft, (unsigned long)m_node->CurrentSize()-m_offset);
		blockedBytes = target.ChannelPut2(channel, m_node->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->next;
		m_offset = 0;
	}

	if (bytesLeft && m_lazyLength)
	{
		unsigned int len = (unsigned int)STDMIN(bytesLeft, (unsigned long)m_lazyLength);
		unsigned int blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking);
		if (blockedBytes)
			goto done;

		m_lazyString += len;
		m_lazyLength -= len;
		bytesLeft -= len;
	}

done:
	transferBytes -= bytesLeft;
	return blockedBytes;
}

unsigned int ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, unsigned long &begin, unsigned long end, const std::string &channel, bool blocking) const
{
	Walker walker(*this);
	walker.Skip(begin);
	unsigned long transferBytes = end-begin;
	unsigned int blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
	begin += transferBytes;
	return blockedBytes;
}

NAMESPACE_END