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