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