Crypto++ 8.2
Free C&
queue.cpp
1// queue.cpp - originally written and placed in the public domain by Wei Dai
2
3#include "pch.h"
4
5#ifndef CRYPTOPP_IMPORTS
6
7#include "queue.h"
8#include "filters.h"
9#include "misc.h"
10
11NAMESPACE_BEGIN(CryptoPP)
12
13static const unsigned int s_maxAutoNodeSize = 16*1024;
14
15// this class for use by ByteQueue only
17{
18public:
19 ByteQueueNode(size_t maxSize)
20 : m_buf(maxSize)
21 {
22 m_head = m_tail = 0;
23 m_next = NULLPTR;
24 }
25
26 inline size_t MaxSize() const {return m_buf.size();}
27
28 inline size_t CurrentSize() const
29 {
30 return m_tail-m_head;
31 }
32
33 inline bool UsedUp() const
34 {
35 return (m_head==MaxSize());
36 }
37
38 inline void Clear()
39 {
40 m_head = m_tail = 0;
41 }
42
43 inline size_t Put(const byte *begin, size_t length)
44 {
45 // Avoid passing NULL to memcpy
46 if (!begin || !length) return length;
47 size_t l = STDMIN(length, MaxSize()-m_tail);
48 if (m_buf+m_tail != begin)
49 memcpy(m_buf+m_tail, begin, l);
50 m_tail += l;
51 return l;
52 }
53
54 inline size_t Peek(byte &outByte) const
55 {
56 if (m_tail==m_head)
57 return 0;
58
59 outByte=m_buf[m_head];
60 return 1;
61 }
62
63 inline size_t Peek(byte *target, size_t copyMax) const
64 {
65 size_t len = STDMIN(copyMax, m_tail-m_head);
66 memcpy(target, m_buf+m_head, len);
67 return len;
68 }
69
70 inline size_t CopyTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL) const
71 {
72 size_t len = m_tail-m_head;
73 target.ChannelPut(channel, m_buf+m_head, len);
74 return len;
75 }
76
77 inline size_t CopyTo(BufferedTransformation &target, size_t copyMax, const std::string &channel=DEFAULT_CHANNEL) const
78 {
79 size_t len = STDMIN(copyMax, m_tail-m_head);
80 target.ChannelPut(channel, m_buf+m_head, len);
81 return len;
82 }
83
84 inline size_t Get(byte &outByte)
85 {
86 size_t len = Peek(outByte);
87 m_head += len;
88 return len;
89 }
90
91 inline size_t Get(byte *outString, size_t getMax)
92 {
93 size_t len = Peek(outString, getMax);
94 m_head += len;
95 return len;
96 }
97
98 inline size_t TransferTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL)
99 {
100 size_t len = m_tail-m_head;
101 target.ChannelPutModifiable(channel, m_buf+m_head, len);
102 m_head = m_tail;
103 return len;
104 }
105
106 inline size_t TransferTo(BufferedTransformation &target, lword transferMax, const std::string &channel=DEFAULT_CHANNEL)
107 {
108 size_t len = UnsignedMin(m_tail-m_head, transferMax);
109 target.ChannelPutModifiable(channel, m_buf+m_head, len);
110 m_head += len;
111 return len;
112 }
113
114 inline size_t Skip(size_t skipMax)
115 {
116 size_t len = STDMIN(skipMax, m_tail-m_head);
117 m_head += len;
118 return len;
119 }
120
121 inline byte operator[](size_t i) const
122 {
123 return m_buf[m_head+i];
124 }
125
126 ByteQueueNode* m_next;
127
128 SecByteBlock m_buf;
129 size_t m_head, m_tail;
130};
131
132// ********************************************************
133
134ByteQueue::ByteQueue(size_t nodeSize)
135 : Bufferless<BufferedTransformation>(), m_autoNodeSize(!nodeSize), m_nodeSize(nodeSize)
136 , m_head(NULLPTR), m_tail(NULLPTR), m_lazyString(NULLPTR), m_lazyLength(0), m_lazyStringModifiable(false)
137{
138 SetNodeSize(nodeSize);
139 m_head = m_tail = new ByteQueueNode(m_nodeSize);
140}
141
142void ByteQueue::SetNodeSize(size_t nodeSize)
143{
144 m_autoNodeSize = !nodeSize;
145 m_nodeSize = m_autoNodeSize ? 256 : nodeSize;
146}
147
149 : Bufferless<BufferedTransformation>(copy), m_lazyString(NULLPTR), m_lazyLength(0)
150{
151 CopyFrom(copy);
152}
153
154void ByteQueue::CopyFrom(const ByteQueue &copy)
155{
156 m_lazyLength = 0;
157 m_autoNodeSize = copy.m_autoNodeSize;
158 m_nodeSize = copy.m_nodeSize;
159 m_head = m_tail = new ByteQueueNode(*copy.m_head);
160
161 for (ByteQueueNode *current=copy.m_head->m_next; current; current=current->m_next)
162 {
163 m_tail->m_next = new ByteQueueNode(*current);
164 m_tail = m_tail->m_next;
165 }
166
167 m_tail->m_next = NULLPTR;
168
169 Put(copy.m_lazyString, copy.m_lazyLength);
170}
171
172ByteQueue::~ByteQueue()
173{
174 Destroy();
175}
176
177void ByteQueue::Destroy()
178{
179 for (ByteQueueNode *next, *current=m_head; current; current=next)
180 {
181 next=current->m_next;
182 delete current;
183 }
184}
185
187{
188 m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256);
189 Clear();
190}
191
192lword ByteQueue::CurrentSize() const
193{
194 lword size=0;
195
196 for (ByteQueueNode *current=m_head; current; current=current->m_next)
197 size += current->CurrentSize();
198
199 return size + m_lazyLength;
200}
201
202bool ByteQueue::IsEmpty() const
203{
204 return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0;
205}
206
207void ByteQueue::Clear()
208{
209 for (ByteQueueNode *next, *current=m_head->m_next; current; current=next)
210 {
211 next=current->m_next;
212 delete current;
213 }
214
215 m_tail = m_head;
216 m_head->Clear();
217 m_head->m_next = NULLPTR;
218 m_lazyLength = 0;
219}
220
221size_t ByteQueue::Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
222{
223 CRYPTOPP_UNUSED(messageEnd), CRYPTOPP_UNUSED(blocking);
224
225 if (m_lazyLength > 0)
226 FinalizeLazyPut();
227
228 size_t len;
229 while ((len=m_tail->Put(inString, length)) < length)
230 {
231 inString = PtrAdd(inString, len);
232 length -= len;
233 if (m_autoNodeSize && m_nodeSize < s_maxAutoNodeSize)
234 do
235 {
236 m_nodeSize *= 2;
237 }
238 while (m_nodeSize < length && m_nodeSize < s_maxAutoNodeSize);
239 m_tail->m_next = new ByteQueueNode(STDMAX(m_nodeSize, length));
240 m_tail = m_tail->m_next;
241 }
242
243 return 0;
244}
245
246void ByteQueue::CleanupUsedNodes()
247{
248 // Test for m_head due to Enterprise Anlysis finding
249 while (m_head && m_head != m_tail && m_head->UsedUp())
250 {
251 ByteQueueNode *temp=m_head;
252 m_head=m_head->m_next;
253 delete temp;
254 }
255
256 // Test for m_head due to Enterprise Anlysis finding
257 if (m_head && m_head->CurrentSize() == 0)
258 m_head->Clear();
259}
260
261void ByteQueue::LazyPut(const byte *inString, size_t size)
262{
263 if (m_lazyLength > 0)
264 FinalizeLazyPut();
265
266 if (inString == m_tail->m_buf+m_tail->m_tail)
267 Put(inString, size);
268 else
269 {
270 m_lazyString = const_cast<byte *>(inString);
271 m_lazyLength = size;
272 m_lazyStringModifiable = false;
273 }
274}
275
276void ByteQueue::LazyPutModifiable(byte *inString, size_t size)
277{
278 if (m_lazyLength > 0)
279 FinalizeLazyPut();
280 m_lazyString = inString;
281 m_lazyLength = size;
282 m_lazyStringModifiable = true;
283}
284
285void ByteQueue::UndoLazyPut(size_t size)
286{
287 if (m_lazyLength < size)
288 throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large");
289
290 m_lazyLength -= size;
291}
292
293void ByteQueue::FinalizeLazyPut()
294{
295 size_t len = m_lazyLength;
296 m_lazyLength = 0;
297 if (len)
298 Put(m_lazyString, len);
299}
300
301size_t ByteQueue::Get(byte &outByte)
302{
303 if (m_head->Get(outByte))
304 {
305 if (m_head->UsedUp())
306 CleanupUsedNodes();
307 return 1;
308 }
309 else if (m_lazyLength > 0)
310 {
311 outByte = *m_lazyString++;
312 m_lazyLength--;
313 return 1;
314 }
315 else
316 return 0;
317}
318
319size_t ByteQueue::Get(byte *outString, size_t getMax)
320{
321 ArraySink sink(outString, getMax);
322 return (size_t)TransferTo(sink, getMax);
323}
324
325size_t ByteQueue::Peek(byte &outByte) const
326{
327 if (m_head->Peek(outByte))
328 return 1;
329 else if (m_lazyLength > 0)
330 {
331 outByte = *m_lazyString;
332 return 1;
333 }
334 else
335 return 0;
336}
337
338size_t ByteQueue::Peek(byte *outString, size_t peekMax) const
339{
340 ArraySink sink(outString, peekMax);
341 return (size_t)CopyTo(sink, peekMax);
342}
343
344size_t ByteQueue::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
345{
346 if (blocking)
347 {
348 lword bytesLeft = transferBytes;
349 for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->m_next)
350 bytesLeft -= current->TransferTo(target, bytesLeft, channel);
351 CleanupUsedNodes();
352
353 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
354 if (len)
355 {
356 if (m_lazyStringModifiable)
357 target.ChannelPutModifiable(channel, m_lazyString, len);
358 else
359 target.ChannelPut(channel, m_lazyString, len);
360 m_lazyString = PtrAdd(m_lazyString, len);
361 m_lazyLength -= len;
362 bytesLeft -= len;
363 }
364 transferBytes -= bytesLeft;
365 return 0;
366 }
367 else
368 {
369 Walker walker(*this);
370 size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
371 Skip(transferBytes);
372 return blockedBytes;
373 }
374}
375
376size_t ByteQueue::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
377{
378 Walker walker(*this);
379 walker.Skip(begin);
380 lword transferBytes = end-begin;
381 size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
382 begin += transferBytes;
383 return blockedBytes;
384}
385
386void ByteQueue::Unget(byte inByte)
387{
388 Unget(&inByte, 1);
389}
390
391void ByteQueue::Unget(const byte *inString, size_t length)
392{
393 size_t len = STDMIN(length, m_head->m_head);
394 length -= len;
395 m_head->m_head = m_head->m_head - len;
396 memcpy(m_head->m_buf + m_head->m_head, inString + length, len);
397
398 if (length > 0)
399 {
400 ByteQueueNode *newHead = new ByteQueueNode(length);
401 newHead->m_next = m_head;
402 m_head = newHead;
403 m_head->Put(inString, length);
404 }
405}
406
407const byte * ByteQueue::Spy(size_t &contiguousSize) const
408{
409 contiguousSize = m_head->m_tail - m_head->m_head;
410 if (contiguousSize == 0 && m_lazyLength > 0)
411 {
412 contiguousSize = m_lazyLength;
413 return m_lazyString;
414 }
415 else
416 return m_head->m_buf + m_head->m_head;
417}
418
419byte * ByteQueue::CreatePutSpace(size_t &size)
420{
421 if (m_lazyLength > 0)
422 FinalizeLazyPut();
423
424 if (m_tail->m_tail == m_tail->MaxSize())
425 {
426 m_tail->m_next = new ByteQueueNode(STDMAX(m_nodeSize, size));
427 m_tail = m_tail->m_next;
428 }
429
430 size = m_tail->MaxSize() - m_tail->m_tail;
431 return PtrAdd(m_tail->m_buf.begin(), m_tail->m_tail);
432}
433
434ByteQueue & ByteQueue::operator=(const ByteQueue &rhs)
435{
436 Destroy();
437 CopyFrom(rhs);
438 return *this;
439}
440
441bool ByteQueue::operator==(const ByteQueue &rhs) const
442{
443 const lword currentSize = CurrentSize();
444
445 if (currentSize != rhs.CurrentSize())
446 return false;
447
448 Walker walker1(*this), walker2(rhs);
449 byte b1, b2;
450
451 while (walker1.Get(b1) && walker2.Get(b2))
452 if (b1 != b2)
453 return false;
454
455 return true;
456}
457
458byte ByteQueue::operator[](lword i) const
459{
460 for (ByteQueueNode *current=m_head; current; current=current->m_next)
461 {
462 if (i < current->CurrentSize())
463 return (*current)[(size_t)i];
464
465 i -= current->CurrentSize();
466 }
467
468 CRYPTOPP_ASSERT(i < m_lazyLength);
469 return m_lazyString[i];
470}
471
472void ByteQueue::swap(ByteQueue &rhs)
473{
474 std::swap(m_autoNodeSize, rhs.m_autoNodeSize);
475 std::swap(m_nodeSize, rhs.m_nodeSize);
476 std::swap(m_head, rhs.m_head);
477 std::swap(m_tail, rhs.m_tail);
478 std::swap(m_lazyString, rhs.m_lazyString);
479 std::swap(m_lazyLength, rhs.m_lazyLength);
480 std::swap(m_lazyStringModifiable, rhs.m_lazyStringModifiable);
481}
482
483// ********************************************************
484
486{
487 CRYPTOPP_UNUSED(parameters);
488
489 m_node = m_queue.m_head;
490 m_position = 0;
491 m_offset = 0;
492 m_lazyString = m_queue.m_lazyString;
493 m_lazyLength = m_queue.m_lazyLength;
494}
495
496size_t ByteQueue::Walker::Get(byte &outByte)
497{
498 ArraySink sink(&outByte, 1);
499 return (size_t)TransferTo(sink, 1);
500}
501
502size_t ByteQueue::Walker::Get(byte *outString, size_t getMax)
503{
504 ArraySink sink(outString, getMax);
505 return (size_t)TransferTo(sink, getMax);
506}
507
508size_t ByteQueue::Walker::Peek(byte &outByte) const
509{
510 ArraySink sink(&outByte, 1);
511 return (size_t)CopyTo(sink, 1);
512}
513
514size_t ByteQueue::Walker::Peek(byte *outString, size_t peekMax) const
515{
516 ArraySink sink(outString, peekMax);
517 return (size_t)CopyTo(sink, peekMax);
518}
519
520size_t ByteQueue::Walker::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
521{
522 lword bytesLeft = transferBytes;
523 size_t blockedBytes = 0;
524
525 while (m_node)
526 {
527 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_node->CurrentSize()-m_offset);
528 blockedBytes = target.ChannelPut2(channel, m_node->m_buf+m_node->m_head+m_offset, len, 0, blocking);
529
530 if (blockedBytes)
531 goto done;
532
533 m_position += len;
534 bytesLeft -= len;
535
536 if (!bytesLeft)
537 {
538 m_offset += len;
539 goto done;
540 }
541
542 m_node = m_node->m_next;
543 m_offset = 0;
544 }
545
546 if (bytesLeft && m_lazyLength)
547 {
548 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
549 blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking);
550 if (blockedBytes)
551 goto done;
552
553 m_lazyString = PtrAdd(m_lazyString, len);
554 m_lazyLength -= len;
555 bytesLeft -= len;
556 }
557
558done:
559 transferBytes -= bytesLeft;
560 return blockedBytes;
561}
562
563size_t ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
564{
565 Walker walker(*this);
566 walker.Skip(begin);
567 lword transferBytes = end-begin;
568 size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
569 begin += transferBytes;
570 return blockedBytes;
571}
572
573NAMESPACE_END
574
575#endif
Copy input to a memory buffer.
Definition: filters.h:1137
Interface for buffered transformations.
Definition: cryptlib.h:1599
virtual lword Skip(lword skipMax=LWORD_MAX)
Discard skipMax bytes from the output buffer.
Definition: cryptlib.cpp:573
size_t ChannelPutModifiable(const std::string &channel, byte *inString, size_t length, bool blocking=true)
Input multiple bytes that may be modified by callee on a channel.
Definition: cryptlib.h:2126
lword CopyTo(BufferedTransformation &target, lword copyMax=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL) const
copy copyMax bytes of the buffered output to target as input
Definition: cryptlib.h:1926
size_t ChannelPut(const std::string &channel, byte inByte, bool blocking=true)
Input a byte for processing on a channel.
Definition: cryptlib.h:2106
lword TransferTo(BufferedTransformation &target, lword transferMax=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL)
move transferMax bytes of the buffered output to target as input
Definition: cryptlib.h:1901
virtual size_t ChannelPut2(const std::string &channel, const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing on a channel.
Definition: cryptlib.cpp:464
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1620
Base class for bufferless filters.
Definition: simple.h:99
A ByteQueue iterator.
Definition: queue.h:77
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: queue.cpp:496
size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true)
Transfer bytes from this object to another BufferedTransformation.
Definition: queue.cpp:520
size_t CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true) const
Copy bytes from this object to another BufferedTransformation.
Definition: queue.cpp:563
size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Definition: queue.cpp:508
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: queue.cpp:485
Data structure used to store byte strings.
Definition: queue.h:19
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: queue.cpp:301
size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Definition: queue.cpp:325
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: queue.cpp:221
ByteQueue(size_t nodeSize=0)
Construct a ByteQueue.
Definition: queue.cpp:134
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: queue.cpp:186
size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true)
Transfer bytes from this object to another BufferedTransformation.
Definition: queue.cpp:344
byte * CreatePutSpace(size_t &size)
Request space which can be written into by the caller.
Definition: queue.cpp:419
size_t CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true) const
Copy bytes from this object to another BufferedTransformation.
Definition: queue.cpp:376
An invalid argument was detected.
Definition: cryptlib.h:203
Interface for retrieving values given their names.
Definition: cryptlib.h:294
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:395
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:772
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:797
SecBlock<byte> typedef.
Definition: secblock.h:1058
Implementation of BufferedTransformation's attachment interface.
Utility functions for the Crypto++ library.
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:578
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:567
PTR PtrAdd(PTR pointer, OFF offset)
Create a pointer with an offset.
Definition: misc.h:343
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:606
Crypto++ library namespace.
Precompiled header file.
Classes for an unlimited queue to store bytes.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69