Crypto++ 8.5 Free C++ class library of cryptographic schemes

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