Crypto++ 7.0 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
11 NAMESPACE_BEGIN(CryptoPP)
12
13 static const unsigned int s_maxAutoNodeSize = 16*1024;
14
15 // this class for use by ByteQueue only
16 class ByteQueueNode
17 {
18 public:
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
134 ByteQueue::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
142 void ByteQueue::SetNodeSize(size_t nodeSize)
143 {
144 m_autoNodeSize = !nodeSize;
145 m_nodeSize = m_autoNodeSize ? 256 : nodeSize;
146 }
147
148 ByteQueue::ByteQueue(const ByteQueue &copy)
149 : Bufferless<BufferedTransformation>(copy), m_lazyString(NULLPTR), m_lazyLength(0)
150 {
151 CopyFrom(copy);
152 }
153
154 void 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
172 ByteQueue::~ByteQueue()
173 {
174 Destroy();
175 }
176
177 void 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
186 void ByteQueue::IsolatedInitialize(const NameValuePairs &parameters)
187 {
188 m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256);
189 Clear();
190 }
191
192 lword 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
202 bool ByteQueue::IsEmpty() const
203 {
204 return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0;
205 }
206
207 void 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
221 size_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
246 void 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
261 void 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
276 void 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
285 void 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
293 void ByteQueue::FinalizeLazyPut()
294 {
295 size_t len = m_lazyLength;
296 m_lazyLength = 0;
297 if (len)
298 Put(m_lazyString, len);
299 }
300
301 size_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
319 size_t ByteQueue::Get(byte *outString, size_t getMax)
320 {
321 ArraySink sink(outString, getMax);
322 return (size_t)TransferTo(sink, getMax);
323 }
324
325 size_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
338 size_t ByteQueue::Peek(byte *outString, size_t peekMax) const
339 {
340 ArraySink sink(outString, peekMax);
341 return (size_t)CopyTo(sink, peekMax);
342 }
343
344 size_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
376 size_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
386 void ByteQueue::Unget(byte inByte)
387 {
388 Unget(&inByte, 1);
389 }
390
391 void 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
407 const 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
419 byte * 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
434 ByteQueue & ByteQueue::operator=(const ByteQueue &rhs)
435 {
436 Destroy();
437 CopyFrom(rhs);
438 return *this;
439 }
440
441 bool 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
458 byte 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
472 void 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
485 void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs &parameters)
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
496 size_t ByteQueue::Walker::Get(byte &outByte)
497 {
498 ArraySink sink(&outByte, 1);
499 return (size_t)TransferTo(sink, 1);
500 }
501
502 size_t ByteQueue::Walker::Get(byte *outString, size_t getMax)
503 {
504 ArraySink sink(outString, getMax);
505 return (size_t)TransferTo(sink, getMax);
506 }
507
508 size_t ByteQueue::Walker::Peek(byte &outByte) const
509 {
510 ArraySink sink(&outByte, 1);
511 return (size_t)CopyTo(sink, 1);
512 }
513
514 size_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
520 size_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
558 done:
559 transferBytes -= bytesLeft;
560 return blockedBytes;
561 }
562
563 size_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
573 NAMESPACE_END
574
575 #endif
NameValuePairs::GetIntValueWithDefault
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:395
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:202
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.
Definition: queue.cpp:563
ByteQueue::IsolatedInitialize
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: queue.cpp:186
misc.h
Utility functions for the Crypto++ library.
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:2072
ByteQueue::Walker::IsolatedInitialize
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Definition: queue.cpp:485
SecByteBlock
SecBlock<byte> typedef.
Definition: secblock.h:1052
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1564
ByteQueue::Walker::Get
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: queue.cpp:496
ArraySink
Copy input to a memory buffer.
Definition: filters.h:1136
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.
Definition: queue.cpp:344
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:1867
ByteQueue::ByteQueue
ByteQueue(size_t nodeSize=0)
Construct a ByteQueue.
Definition: queue.cpp:134
BufferedTransformation::Put
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1586
DEFAULT_CHANNEL
const std::string DEFAULT_CHANNEL
Default channel for BufferedTransformation.
Definition: cryptlib.h:482
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:2092
ByteQueue::Peek
size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Definition: queue.cpp:325
pch.h
Precompiled header file.
UnsignedMin
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:602
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.
Definition: cryptlib.cpp:464
BufferedTransformation::Skip
virtual lword Skip(lword skipMax=LWORD_MAX)
Discard skipMax bytes from the output buffer.
Definition: cryptlib.cpp:573
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:563
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:60
ByteQueue::Walker::Peek
size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Definition: queue.cpp:508
ByteQueue
Data structure used to store byte strings.
Definition: queue.h:18
SecBlock::begin
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:766
filters.h
Implementation of BufferedTransformation&#39;s attachment interface.
PtrAdd
PTR PtrAdd(PTR pointer, OFF offset)
Create a pointer with an offset.
Definition: misc.h:371
BufferedTransformation::CopyTo
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:1892
ByteQueue::CreatePutSpace
byte * CreatePutSpace(size_t &size)
Request space which can be written into by the caller.
Definition: queue.cpp:419
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.
Definition: queue.cpp:520
ByteQueueNode
Definition: queue.cpp:16
STDMAX
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:574
CryptoPP
Crypto++ library namespace.
ByteQueue::Walker
A ByteQueue iterator.
Definition: queue.h:76
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.
Definition: queue.cpp:376
ByteQueue::Get
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: queue.cpp:301
ByteQueue::Put2
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Definition: queue.cpp:221
SecBlock::size
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:791
Bufferless
Base class for bufferless filters.
Definition: simple.h:98
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:293