Initial revision

1 files changed, 518 insertions, 0 deletions

diff --git a/queue.cpp b/queue.cpp
new file mode 100644
index 00000000..a01e2138
--- /dev/null
+++ b/queue.cpp
@@ -0,0 +1,518 @@
+// queue.cpp - written and placed in the public domain by Wei Dai
+
+#include "pch.h"
+#include "queue.h"
+#include "filters.h"
+
+NAMESPACE_BEGIN(CryptoPP)
+
+// 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(byte inByte)
+	{
+		if (MaxSize()==m_tail)
+			return 0;
+
+		buf[m_tail++]=inByte;
+		return 1;
+	}
+*/
+	inline unsigned int Put(const byte *begin, unsigned int length)
+	{
+		unsigned int l = STDMIN(length, MaxSize()-m_tail);
+		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 m_nodeSize)
+	: m_nodeSize(m_nodeSize), 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_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()
+{
+	ByteQueueNode *next;
+
+	for (ByteQueueNode *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()
+{
+	Destroy();
+	m_head = m_tail = new ByteQueueNode(m_nodeSize);
+	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)
+	{
+		m_tail->next = new ByteQueueNode(m_nodeSize);
+		m_tail = m_tail->next;
+		inString += len;
+		length -= len;
+	}
+
+	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();
+	m_lazyString = inString;
+	m_lazyLength = size;
+}
+
+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)
+		{
+			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)
+{
+	// TODO: make this more efficient
+	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(size < m_nodeSize ? m_nodeSize : STDMAX(m_nodeSize, 1024U));
+		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