Crypto++  8.3
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 
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
An invalid argument was detected.
Definition: cryptlib.h:202
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 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.
CRYPTOPP_DLL int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:424
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
Utility functions for the Crypto++ library.
size_t ChannelPut(const std::string &channel, byte inByte, bool blocking=true)
Input a byte for processing on a channel.
Definition: cryptlib.h:2177
void IsolatedInitialize(const NameValuePairs &parameters)
Initialize or reinitialize this object, without signal propagation.
SecBlock<byte> typedef.
Definition: secblock.h:1103
Interface for buffered transformations.
Definition: cryptlib.h:1634
size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Copy input to a memory buffer.
Definition: filters.h:1199
size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true)
Transfer bytes from this object to another BufferedTransformation.
Classes for an unlimited queue to store bytes.
ByteQueue(size_t nodeSize=0)
Construct a ByteQueue.
const std::string DEFAULT_CHANNEL
Default channel for BufferedTransformation.
Definition: cryptlib.h:511
byte * CreatePutSpace(size_t &size)
Request space which can be written into by the caller.
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
size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Precompiled header file.
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:674
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:635
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
size_t Peek(byte &outByte) const
Peek a 8-bit byte.
Data structure used to store byte strings.
Definition: queue.h:18
Implementation of BufferedTransformation&#39;s attachment interface.
word64 lword
Large word type.
Definition: config_int.h:158
unsigned char byte
8-bit unsigned datatype
Definition: config_int.h:56
PTR PtrAdd(PTR pointer, OFF offset)
Create a pointer with an offset.
Definition: misc.h:384
Debugging and diagnostic assertions.
size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true)
Transfer bytes from this object to another BufferedTransformation.
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:646
Crypto++ library namespace.
void swap(::SecBlock< T, A > &a, ::SecBlock< T, A > &b)
Swap two SecBlocks.
Definition: secblock.h:1165
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 Get(byte &outByte)
Retrieve a 8-bit byte.
size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Base class for bufferless filters.
Definition: simple.h:119
#define SIZE_MAX
The maximum value of a machine word.
Definition: misc.h:116
Interface for retrieving values given their names.
Definition: cryptlib.h:321