Crypto++
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  size_t l = STDMIN(length, MaxSize()-m_tail);
45  if (buf+m_tail != begin)
46  memcpy(buf+m_tail, begin, l);
47  m_tail += l;
48  return l;
49  }
50 
51  inline size_t Peek(byte &outByte) const
52  {
53  if (m_tail==m_head)
54  return 0;
55 
56  outByte=buf[m_head];
57  return 1;
58  }
59 
60  inline size_t Peek(byte *target, size_t copyMax) const
61  {
62  size_t len = STDMIN(copyMax, m_tail-m_head);
63  memcpy(target, buf+m_head, len);
64  return len;
65  }
66 
67  inline size_t CopyTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL) const
68  {
69  size_t len = m_tail-m_head;
70  target.ChannelPut(channel, buf+m_head, len);
71  return len;
72  }
73 
74  inline size_t CopyTo(BufferedTransformation &target, size_t copyMax, const std::string &channel=DEFAULT_CHANNEL) const
75  {
76  size_t len = STDMIN(copyMax, m_tail-m_head);
77  target.ChannelPut(channel, buf+m_head, len);
78  return len;
79  }
80 
81  inline size_t Get(byte &outByte)
82  {
83  size_t len = Peek(outByte);
84  m_head += len;
85  return len;
86  }
87 
88  inline size_t Get(byte *outString, size_t getMax)
89  {
90  size_t len = Peek(outString, getMax);
91  m_head += len;
92  return len;
93  }
94 
95  inline size_t TransferTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL)
96  {
97  size_t len = m_tail-m_head;
98  target.ChannelPutModifiable(channel, buf+m_head, len);
99  m_head = m_tail;
100  return len;
101  }
102 
103  inline size_t TransferTo(BufferedTransformation &target, lword transferMax, const std::string &channel=DEFAULT_CHANNEL)
104  {
105  size_t len = UnsignedMin(m_tail-m_head, transferMax);
106  target.ChannelPutModifiable(channel, buf+m_head, len);
107  m_head += len;
108  return len;
109  }
110 
111  inline size_t Skip(size_t skipMax)
112  {
113  size_t len = STDMIN(skipMax, m_tail-m_head);
114  m_head += len;
115  return len;
116  }
117 
118  inline byte operator[](size_t i) const
119  {
120  return buf[m_head+i];
121  }
122 
123  ByteQueueNode *next;
124 
125  SecByteBlock buf;
126  size_t m_head, m_tail;
127 };
128 
129 // ********************************************************
130 
131 ByteQueue::ByteQueue(size_t nodeSize)
132  : m_lazyString(NULL), m_lazyLength(0)
133 {
134  SetNodeSize(nodeSize);
135  m_head = m_tail = new ByteQueueNode(m_nodeSize);
136 }
137 
138 void ByteQueue::SetNodeSize(size_t nodeSize)
139 {
140  m_autoNodeSize = !nodeSize;
141  m_nodeSize = m_autoNodeSize ? 256 : nodeSize;
142 }
143 
144 ByteQueue::ByteQueue(const ByteQueue &copy)
145  : m_lazyString(NULL)
146 {
147  CopyFrom(copy);
148 }
149 
150 void ByteQueue::CopyFrom(const ByteQueue &copy)
151 {
152  m_lazyLength = 0;
153  m_autoNodeSize = copy.m_autoNodeSize;
154  m_nodeSize = copy.m_nodeSize;
155  m_head = m_tail = new ByteQueueNode(*copy.m_head);
156 
157  for (ByteQueueNode *current=copy.m_head->next; current; current=current->next)
158  {
159  m_tail->next = new ByteQueueNode(*current);
160  m_tail = m_tail->next;
161  }
162 
163  m_tail->next = NULL;
164 
165  Put(copy.m_lazyString, copy.m_lazyLength);
166 }
167 
168 ByteQueue::~ByteQueue()
169 {
170  Destroy();
171 }
172 
173 void ByteQueue::Destroy()
174 {
175  for (ByteQueueNode *next, *current=m_head; current; current=next)
176  {
177  next=current->next;
178  delete current;
179  }
180 }
181 
182 void ByteQueue::IsolatedInitialize(const NameValuePairs &parameters)
183 {
184  m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256);
185  Clear();
186 }
187 
188 lword ByteQueue::CurrentSize() const
189 {
190  lword size=0;
191 
192  for (ByteQueueNode *current=m_head; current; current=current->next)
193  size += current->CurrentSize();
194 
195  return size + m_lazyLength;
196 }
197 
198 bool ByteQueue::IsEmpty() const
199 {
200  return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0;
201 }
202 
203 void ByteQueue::Clear()
204 {
205  for (ByteQueueNode *next, *current=m_head->next; current; current=next)
206  {
207  next=current->next;
208  delete current;
209  }
210 
211  m_tail = m_head;
212  m_head->Clear();
213  m_head->next = NULL;
214  m_lazyLength = 0;
215 }
216 
217 size_t ByteQueue::Put2(const byte *inString, size_t length, int messageEnd, bool blocking)
218 {
219  if (m_lazyLength > 0)
220  FinalizeLazyPut();
221 
222  size_t len;
223  while ((len=m_tail->Put(inString, length)) < length)
224  {
225  inString += len;
226  length -= len;
227  if (m_autoNodeSize && m_nodeSize < s_maxAutoNodeSize)
228  do
229  {
230  m_nodeSize *= 2;
231  }
232  while (m_nodeSize < length && m_nodeSize < s_maxAutoNodeSize);
233  m_tail->next = new ByteQueueNode(STDMAX(m_nodeSize, length));
234  m_tail = m_tail->next;
235  }
236 
237  return 0;
238 }
239 
240 void ByteQueue::CleanupUsedNodes()
241 {
242  while (m_head != m_tail && m_head->UsedUp())
243  {
244  ByteQueueNode *temp=m_head;
245  m_head=m_head->next;
246  delete temp;
247  }
248 
249  if (m_head->CurrentSize() == 0)
250  m_head->Clear();
251 }
252 
253 void ByteQueue::LazyPut(const byte *inString, size_t size)
254 {
255  if (m_lazyLength > 0)
256  FinalizeLazyPut();
257 
258  if (inString == m_tail->buf+m_tail->m_tail)
259  Put(inString, size);
260  else
261  {
262  m_lazyString = const_cast<byte *>(inString);
263  m_lazyLength = size;
264  m_lazyStringModifiable = false;
265  }
266 }
267 
268 void ByteQueue::LazyPutModifiable(byte *inString, size_t size)
269 {
270  if (m_lazyLength > 0)
271  FinalizeLazyPut();
272  m_lazyString = inString;
273  m_lazyLength = size;
274  m_lazyStringModifiable = true;
275 }
276 
277 void ByteQueue::UndoLazyPut(size_t size)
278 {
279  if (m_lazyLength < size)
280  throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large");
281 
282  m_lazyLength -= size;
283 }
284 
285 void ByteQueue::FinalizeLazyPut()
286 {
287  size_t len = m_lazyLength;
288  m_lazyLength = 0;
289  if (len)
290  Put(m_lazyString, len);
291 }
292 
293 size_t ByteQueue::Get(byte &outByte)
294 {
295  if (m_head->Get(outByte))
296  {
297  if (m_head->UsedUp())
298  CleanupUsedNodes();
299  return 1;
300  }
301  else if (m_lazyLength > 0)
302  {
303  outByte = *m_lazyString++;
304  m_lazyLength--;
305  return 1;
306  }
307  else
308  return 0;
309 }
310 
311 size_t ByteQueue::Get(byte *outString, size_t getMax)
312 {
313  ArraySink sink(outString, getMax);
314  return (size_t)TransferTo(sink, getMax);
315 }
316 
317 size_t ByteQueue::Peek(byte &outByte) const
318 {
319  if (m_head->Peek(outByte))
320  return 1;
321  else if (m_lazyLength > 0)
322  {
323  outByte = *m_lazyString;
324  return 1;
325  }
326  else
327  return 0;
328 }
329 
330 size_t ByteQueue::Peek(byte *outString, size_t peekMax) const
331 {
332  ArraySink sink(outString, peekMax);
333  return (size_t)CopyTo(sink, peekMax);
334 }
335 
336 size_t ByteQueue::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
337 {
338  if (blocking)
339  {
340  lword bytesLeft = transferBytes;
341  for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->next)
342  bytesLeft -= current->TransferTo(target, bytesLeft, channel);
343  CleanupUsedNodes();
344 
345  size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
346  if (len)
347  {
348  if (m_lazyStringModifiable)
349  target.ChannelPutModifiable(channel, m_lazyString, len);
350  else
351  target.ChannelPut(channel, m_lazyString, len);
352  m_lazyString += len;
353  m_lazyLength -= len;
354  bytesLeft -= len;
355  }
356  transferBytes -= bytesLeft;
357  return 0;
358  }
359  else
360  {
361  Walker walker(*this);
362  size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
363  Skip(transferBytes);
364  return blockedBytes;
365  }
366 }
367 
368 size_t ByteQueue::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
369 {
370  Walker walker(*this);
371  walker.Skip(begin);
372  lword transferBytes = end-begin;
373  size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
374  begin += transferBytes;
375  return blockedBytes;
376 }
377 
378 void ByteQueue::Unget(byte inByte)
379 {
380  Unget(&inByte, 1);
381 }
382 
383 void ByteQueue::Unget(const byte *inString, size_t length)
384 {
385  size_t len = STDMIN(length, m_head->m_head);
386  length -= len;
387  m_head->m_head -= len;
388  memcpy(m_head->buf + m_head->m_head, inString + length, len);
389 
390  if (length > 0)
391  {
392  ByteQueueNode *newHead = new ByteQueueNode(length);
393  newHead->next = m_head;
394  m_head = newHead;
395  m_head->Put(inString, length);
396  }
397 }
398 
399 const byte * ByteQueue::Spy(size_t &contiguousSize) const
400 {
401  contiguousSize = m_head->m_tail - m_head->m_head;
402  if (contiguousSize == 0 && m_lazyLength > 0)
403  {
404  contiguousSize = m_lazyLength;
405  return m_lazyString;
406  }
407  else
408  return m_head->buf + m_head->m_head;
409 }
410 
411 byte * ByteQueue::CreatePutSpace(size_t &size)
412 {
413  if (m_lazyLength > 0)
414  FinalizeLazyPut();
415 
416  if (m_tail->m_tail == m_tail->MaxSize())
417  {
418  m_tail->next = new ByteQueueNode(STDMAX(m_nodeSize, size));
419  m_tail = m_tail->next;
420  }
421 
422  size = m_tail->MaxSize() - m_tail->m_tail;
423  return m_tail->buf + m_tail->m_tail;
424 }
425 
426 ByteQueue & ByteQueue::operator=(const ByteQueue &rhs)
427 {
428  Destroy();
429  CopyFrom(rhs);
430  return *this;
431 }
432 
433 bool ByteQueue::operator==(const ByteQueue &rhs) const
434 {
435  const lword currentSize = CurrentSize();
436 
437  if (currentSize != rhs.CurrentSize())
438  return false;
439 
440  Walker walker1(*this), walker2(rhs);
441  byte b1, b2;
442 
443  while (walker1.Get(b1) && walker2.Get(b2))
444  if (b1 != b2)
445  return false;
446 
447  return true;
448 }
449 
450 byte ByteQueue::operator[](lword i) const
451 {
452  for (ByteQueueNode *current=m_head; current; current=current->next)
453  {
454  if (i < current->CurrentSize())
455  return (*current)[(size_t)i];
456 
457  i -= current->CurrentSize();
458  }
459 
460  assert(i < m_lazyLength);
461  return m_lazyString[i];
462 }
463 
464 void ByteQueue::swap(ByteQueue &rhs)
465 {
466  std::swap(m_autoNodeSize, rhs.m_autoNodeSize);
467  std::swap(m_nodeSize, rhs.m_nodeSize);
468  std::swap(m_head, rhs.m_head);
469  std::swap(m_tail, rhs.m_tail);
470  std::swap(m_lazyString, rhs.m_lazyString);
471  std::swap(m_lazyLength, rhs.m_lazyLength);
472  std::swap(m_lazyStringModifiable, rhs.m_lazyStringModifiable);
473 }
474 
475 // ********************************************************
476 
477 void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs &parameters)
478 {
479  m_node = m_queue.m_head;
480  m_position = 0;
481  m_offset = 0;
482  m_lazyString = m_queue.m_lazyString;
483  m_lazyLength = m_queue.m_lazyLength;
484 }
485 
486 size_t ByteQueue::Walker::Get(byte &outByte)
487 {
488  ArraySink sink(&outByte, 1);
489  return (size_t)TransferTo(sink, 1);
490 }
491 
492 size_t ByteQueue::Walker::Get(byte *outString, size_t getMax)
493 {
494  ArraySink sink(outString, getMax);
495  return (size_t)TransferTo(sink, getMax);
496 }
497 
498 size_t ByteQueue::Walker::Peek(byte &outByte) const
499 {
500  ArraySink sink(&outByte, 1);
501  return (size_t)CopyTo(sink, 1);
502 }
503 
504 size_t ByteQueue::Walker::Peek(byte *outString, size_t peekMax) const
505 {
506  ArraySink sink(outString, peekMax);
507  return (size_t)CopyTo(sink, peekMax);
508 }
509 
510 size_t ByteQueue::Walker::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking)
511 {
512  lword bytesLeft = transferBytes;
513  size_t blockedBytes = 0;
514 
515  while (m_node)
516  {
517  size_t len = (size_t)STDMIN(bytesLeft, (lword)m_node->CurrentSize()-m_offset);
518  blockedBytes = target.ChannelPut2(channel, m_node->buf+m_node->m_head+m_offset, len, 0, blocking);
519 
520  if (blockedBytes)
521  goto done;
522 
523  m_position += len;
524  bytesLeft -= len;
525 
526  if (!bytesLeft)
527  {
528  m_offset += len;
529  goto done;
530  }
531 
532  m_node = m_node->next;
533  m_offset = 0;
534  }
535 
536  if (bytesLeft && m_lazyLength)
537  {
538  size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength);
539  blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking);
540  if (blockedBytes)
541  goto done;
542 
543  m_lazyString += len;
544  m_lazyLength -= len;
545  bytesLeft -= len;
546  }
547 
548 done:
549  transferBytes -= bytesLeft;
550  return blockedBytes;
551 }
552 
553 size_t ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const
554 {
555  Walker walker(*this);
556  walker.Skip(begin);
557  lword transferBytes = end-begin;
558  size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking);
559  begin += transferBytes;
560  return blockedBytes;
561 }
562 
563 NAMESPACE_END
564 
565 #endif