Crypto++
|
00001 // queue.cpp - written and placed in the public domain by Wei Dai 00002 00003 #include "pch.h" 00004 00005 #ifndef CRYPTOPP_IMPORTS 00006 00007 #include "queue.h" 00008 #include "filters.h" 00009 00010 NAMESPACE_BEGIN(CryptoPP) 00011 00012 static const unsigned int s_maxAutoNodeSize = 16*1024; 00013 00014 // this class for use by ByteQueue only 00015 class ByteQueueNode 00016 { 00017 public: 00018 ByteQueueNode(size_t maxSize) 00019 : buf(maxSize) 00020 { 00021 m_head = m_tail = 0; 00022 next = 0; 00023 } 00024 00025 inline size_t MaxSize() const {return buf.size();} 00026 00027 inline size_t CurrentSize() const 00028 { 00029 return m_tail-m_head; 00030 } 00031 00032 inline bool UsedUp() const 00033 { 00034 return (m_head==MaxSize()); 00035 } 00036 00037 inline void Clear() 00038 { 00039 m_head = m_tail = 0; 00040 } 00041 00042 inline size_t Put(const byte *begin, size_t length) 00043 { 00044 size_t l = STDMIN(length, MaxSize()-m_tail); 00045 if (buf+m_tail != begin) 00046 memcpy(buf+m_tail, begin, l); 00047 m_tail += l; 00048 return l; 00049 } 00050 00051 inline size_t Peek(byte &outByte) const 00052 { 00053 if (m_tail==m_head) 00054 return 0; 00055 00056 outByte=buf[m_head]; 00057 return 1; 00058 } 00059 00060 inline size_t Peek(byte *target, size_t copyMax) const 00061 { 00062 size_t len = STDMIN(copyMax, m_tail-m_head); 00063 memcpy(target, buf+m_head, len); 00064 return len; 00065 } 00066 00067 inline size_t CopyTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL) const 00068 { 00069 size_t len = m_tail-m_head; 00070 target.ChannelPut(channel, buf+m_head, len); 00071 return len; 00072 } 00073 00074 inline size_t CopyTo(BufferedTransformation &target, size_t copyMax, const std::string &channel=DEFAULT_CHANNEL) const 00075 { 00076 size_t len = STDMIN(copyMax, m_tail-m_head); 00077 target.ChannelPut(channel, buf+m_head, len); 00078 return len; 00079 } 00080 00081 inline size_t Get(byte &outByte) 00082 { 00083 size_t len = Peek(outByte); 00084 m_head += len; 00085 return len; 00086 } 00087 00088 inline size_t Get(byte *outString, size_t getMax) 00089 { 00090 size_t len = Peek(outString, getMax); 00091 m_head += len; 00092 return len; 00093 } 00094 00095 inline size_t TransferTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL) 00096 { 00097 size_t len = m_tail-m_head; 00098 target.ChannelPutModifiable(channel, buf+m_head, len); 00099 m_head = m_tail; 00100 return len; 00101 } 00102 00103 inline size_t TransferTo(BufferedTransformation &target, lword transferMax, const std::string &channel=DEFAULT_CHANNEL) 00104 { 00105 size_t len = UnsignedMin(m_tail-m_head, transferMax); 00106 target.ChannelPutModifiable(channel, buf+m_head, len); 00107 m_head += len; 00108 return len; 00109 } 00110 00111 inline size_t Skip(size_t skipMax) 00112 { 00113 size_t len = STDMIN(skipMax, m_tail-m_head); 00114 m_head += len; 00115 return len; 00116 } 00117 00118 inline byte operator[](size_t i) const 00119 { 00120 return buf[m_head+i]; 00121 } 00122 00123 ByteQueueNode *next; 00124 00125 SecByteBlock buf; 00126 size_t m_head, m_tail; 00127 }; 00128 00129 // ******************************************************** 00130 00131 ByteQueue::ByteQueue(size_t nodeSize) 00132 : m_lazyString(NULL), m_lazyLength(0) 00133 { 00134 SetNodeSize(nodeSize); 00135 m_head = m_tail = new ByteQueueNode(m_nodeSize); 00136 } 00137 00138 void ByteQueue::SetNodeSize(size_t nodeSize) 00139 { 00140 m_autoNodeSize = !nodeSize; 00141 m_nodeSize = m_autoNodeSize ? 256 : nodeSize; 00142 } 00143 00144 ByteQueue::ByteQueue(const ByteQueue ©) 00145 : m_lazyString(NULL) 00146 { 00147 CopyFrom(copy); 00148 } 00149 00150 void ByteQueue::CopyFrom(const ByteQueue ©) 00151 { 00152 m_lazyLength = 0; 00153 m_autoNodeSize = copy.m_autoNodeSize; 00154 m_nodeSize = copy.m_nodeSize; 00155 m_head = m_tail = new ByteQueueNode(*copy.m_head); 00156 00157 for (ByteQueueNode *current=copy.m_head->next; current; current=current->next) 00158 { 00159 m_tail->next = new ByteQueueNode(*current); 00160 m_tail = m_tail->next; 00161 } 00162 00163 m_tail->next = NULL; 00164 00165 Put(copy.m_lazyString, copy.m_lazyLength); 00166 } 00167 00168 ByteQueue::~ByteQueue() 00169 { 00170 Destroy(); 00171 } 00172 00173 void ByteQueue::Destroy() 00174 { 00175 for (ByteQueueNode *next, *current=m_head; current; current=next) 00176 { 00177 next=current->next; 00178 delete current; 00179 } 00180 } 00181 00182 void ByteQueue::IsolatedInitialize(const NameValuePairs ¶meters) 00183 { 00184 m_nodeSize = parameters.GetIntValueWithDefault("NodeSize", 256); 00185 Clear(); 00186 } 00187 00188 lword ByteQueue::CurrentSize() const 00189 { 00190 lword size=0; 00191 00192 for (ByteQueueNode *current=m_head; current; current=current->next) 00193 size += current->CurrentSize(); 00194 00195 return size + m_lazyLength; 00196 } 00197 00198 bool ByteQueue::IsEmpty() const 00199 { 00200 return m_head==m_tail && m_head->CurrentSize()==0 && m_lazyLength==0; 00201 } 00202 00203 void ByteQueue::Clear() 00204 { 00205 for (ByteQueueNode *next, *current=m_head->next; current; current=next) 00206 { 00207 next=current->next; 00208 delete current; 00209 } 00210 00211 m_tail = m_head; 00212 m_head->Clear(); 00213 m_head->next = NULL; 00214 m_lazyLength = 0; 00215 } 00216 00217 size_t ByteQueue::Put2(const byte *inString, size_t length, int messageEnd, bool blocking) 00218 { 00219 if (m_lazyLength > 0) 00220 FinalizeLazyPut(); 00221 00222 size_t len; 00223 while ((len=m_tail->Put(inString, length)) < length) 00224 { 00225 inString += len; 00226 length -= len; 00227 if (m_autoNodeSize && m_nodeSize < s_maxAutoNodeSize) 00228 do 00229 { 00230 m_nodeSize *= 2; 00231 } 00232 while (m_nodeSize < length && m_nodeSize < s_maxAutoNodeSize); 00233 m_tail->next = new ByteQueueNode(STDMAX(m_nodeSize, length)); 00234 m_tail = m_tail->next; 00235 } 00236 00237 return 0; 00238 } 00239 00240 void ByteQueue::CleanupUsedNodes() 00241 { 00242 while (m_head != m_tail && m_head->UsedUp()) 00243 { 00244 ByteQueueNode *temp=m_head; 00245 m_head=m_head->next; 00246 delete temp; 00247 } 00248 00249 if (m_head->CurrentSize() == 0) 00250 m_head->Clear(); 00251 } 00252 00253 void ByteQueue::LazyPut(const byte *inString, size_t size) 00254 { 00255 if (m_lazyLength > 0) 00256 FinalizeLazyPut(); 00257 00258 if (inString == m_tail->buf+m_tail->m_tail) 00259 Put(inString, size); 00260 else 00261 { 00262 m_lazyString = const_cast<byte *>(inString); 00263 m_lazyLength = size; 00264 m_lazyStringModifiable = false; 00265 } 00266 } 00267 00268 void ByteQueue::LazyPutModifiable(byte *inString, size_t size) 00269 { 00270 if (m_lazyLength > 0) 00271 FinalizeLazyPut(); 00272 m_lazyString = inString; 00273 m_lazyLength = size; 00274 m_lazyStringModifiable = true; 00275 } 00276 00277 void ByteQueue::UndoLazyPut(size_t size) 00278 { 00279 if (m_lazyLength < size) 00280 throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large"); 00281 00282 m_lazyLength -= size; 00283 } 00284 00285 void ByteQueue::FinalizeLazyPut() 00286 { 00287 size_t len = m_lazyLength; 00288 m_lazyLength = 0; 00289 if (len) 00290 Put(m_lazyString, len); 00291 } 00292 00293 size_t ByteQueue::Get(byte &outByte) 00294 { 00295 if (m_head->Get(outByte)) 00296 { 00297 if (m_head->UsedUp()) 00298 CleanupUsedNodes(); 00299 return 1; 00300 } 00301 else if (m_lazyLength > 0) 00302 { 00303 outByte = *m_lazyString++; 00304 m_lazyLength--; 00305 return 1; 00306 } 00307 else 00308 return 0; 00309 } 00310 00311 size_t ByteQueue::Get(byte *outString, size_t getMax) 00312 { 00313 ArraySink sink(outString, getMax); 00314 return (size_t)TransferTo(sink, getMax); 00315 } 00316 00317 size_t ByteQueue::Peek(byte &outByte) const 00318 { 00319 if (m_head->Peek(outByte)) 00320 return 1; 00321 else if (m_lazyLength > 0) 00322 { 00323 outByte = *m_lazyString; 00324 return 1; 00325 } 00326 else 00327 return 0; 00328 } 00329 00330 size_t ByteQueue::Peek(byte *outString, size_t peekMax) const 00331 { 00332 ArraySink sink(outString, peekMax); 00333 return (size_t)CopyTo(sink, peekMax); 00334 } 00335 00336 size_t ByteQueue::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking) 00337 { 00338 if (blocking) 00339 { 00340 lword bytesLeft = transferBytes; 00341 for (ByteQueueNode *current=m_head; bytesLeft && current; current=current->next) 00342 bytesLeft -= current->TransferTo(target, bytesLeft, channel); 00343 CleanupUsedNodes(); 00344 00345 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength); 00346 if (len) 00347 { 00348 if (m_lazyStringModifiable) 00349 target.ChannelPutModifiable(channel, m_lazyString, len); 00350 else 00351 target.ChannelPut(channel, m_lazyString, len); 00352 m_lazyString += len; 00353 m_lazyLength -= len; 00354 bytesLeft -= len; 00355 } 00356 transferBytes -= bytesLeft; 00357 return 0; 00358 } 00359 else 00360 { 00361 Walker walker(*this); 00362 size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); 00363 Skip(transferBytes); 00364 return blockedBytes; 00365 } 00366 } 00367 00368 size_t ByteQueue::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const 00369 { 00370 Walker walker(*this); 00371 walker.Skip(begin); 00372 lword transferBytes = end-begin; 00373 size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); 00374 begin += transferBytes; 00375 return blockedBytes; 00376 } 00377 00378 void ByteQueue::Unget(byte inByte) 00379 { 00380 Unget(&inByte, 1); 00381 } 00382 00383 void ByteQueue::Unget(const byte *inString, size_t length) 00384 { 00385 size_t len = STDMIN(length, m_head->m_head); 00386 length -= len; 00387 m_head->m_head -= len; 00388 memcpy(m_head->buf + m_head->m_head, inString + length, len); 00389 00390 if (length > 0) 00391 { 00392 ByteQueueNode *newHead = new ByteQueueNode(length); 00393 newHead->next = m_head; 00394 m_head = newHead; 00395 m_head->Put(inString, length); 00396 } 00397 } 00398 00399 const byte * ByteQueue::Spy(size_t &contiguousSize) const 00400 { 00401 contiguousSize = m_head->m_tail - m_head->m_head; 00402 if (contiguousSize == 0 && m_lazyLength > 0) 00403 { 00404 contiguousSize = m_lazyLength; 00405 return m_lazyString; 00406 } 00407 else 00408 return m_head->buf + m_head->m_head; 00409 } 00410 00411 byte * ByteQueue::CreatePutSpace(size_t &size) 00412 { 00413 if (m_lazyLength > 0) 00414 FinalizeLazyPut(); 00415 00416 if (m_tail->m_tail == m_tail->MaxSize()) 00417 { 00418 m_tail->next = new ByteQueueNode(STDMAX(m_nodeSize, size)); 00419 m_tail = m_tail->next; 00420 } 00421 00422 size = m_tail->MaxSize() - m_tail->m_tail; 00423 return m_tail->buf + m_tail->m_tail; 00424 } 00425 00426 ByteQueue & ByteQueue::operator=(const ByteQueue &rhs) 00427 { 00428 Destroy(); 00429 CopyFrom(rhs); 00430 return *this; 00431 } 00432 00433 bool ByteQueue::operator==(const ByteQueue &rhs) const 00434 { 00435 const lword currentSize = CurrentSize(); 00436 00437 if (currentSize != rhs.CurrentSize()) 00438 return false; 00439 00440 Walker walker1(*this), walker2(rhs); 00441 byte b1, b2; 00442 00443 while (walker1.Get(b1) && walker2.Get(b2)) 00444 if (b1 != b2) 00445 return false; 00446 00447 return true; 00448 } 00449 00450 byte ByteQueue::operator[](lword i) const 00451 { 00452 for (ByteQueueNode *current=m_head; current; current=current->next) 00453 { 00454 if (i < current->CurrentSize()) 00455 return (*current)[(size_t)i]; 00456 00457 i -= current->CurrentSize(); 00458 } 00459 00460 assert(i < m_lazyLength); 00461 return m_lazyString[i]; 00462 } 00463 00464 void ByteQueue::swap(ByteQueue &rhs) 00465 { 00466 std::swap(m_autoNodeSize, rhs.m_autoNodeSize); 00467 std::swap(m_nodeSize, rhs.m_nodeSize); 00468 std::swap(m_head, rhs.m_head); 00469 std::swap(m_tail, rhs.m_tail); 00470 std::swap(m_lazyString, rhs.m_lazyString); 00471 std::swap(m_lazyLength, rhs.m_lazyLength); 00472 std::swap(m_lazyStringModifiable, rhs.m_lazyStringModifiable); 00473 } 00474 00475 // ******************************************************** 00476 00477 void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs ¶meters) 00478 { 00479 m_node = m_queue.m_head; 00480 m_position = 0; 00481 m_offset = 0; 00482 m_lazyString = m_queue.m_lazyString; 00483 m_lazyLength = m_queue.m_lazyLength; 00484 } 00485 00486 size_t ByteQueue::Walker::Get(byte &outByte) 00487 { 00488 ArraySink sink(&outByte, 1); 00489 return (size_t)TransferTo(sink, 1); 00490 } 00491 00492 size_t ByteQueue::Walker::Get(byte *outString, size_t getMax) 00493 { 00494 ArraySink sink(outString, getMax); 00495 return (size_t)TransferTo(sink, getMax); 00496 } 00497 00498 size_t ByteQueue::Walker::Peek(byte &outByte) const 00499 { 00500 ArraySink sink(&outByte, 1); 00501 return (size_t)CopyTo(sink, 1); 00502 } 00503 00504 size_t ByteQueue::Walker::Peek(byte *outString, size_t peekMax) const 00505 { 00506 ArraySink sink(outString, peekMax); 00507 return (size_t)CopyTo(sink, peekMax); 00508 } 00509 00510 size_t ByteQueue::Walker::TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel, bool blocking) 00511 { 00512 lword bytesLeft = transferBytes; 00513 size_t blockedBytes = 0; 00514 00515 while (m_node) 00516 { 00517 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_node->CurrentSize()-m_offset); 00518 blockedBytes = target.ChannelPut2(channel, m_node->buf+m_node->m_head+m_offset, len, 0, blocking); 00519 00520 if (blockedBytes) 00521 goto done; 00522 00523 m_position += len; 00524 bytesLeft -= len; 00525 00526 if (!bytesLeft) 00527 { 00528 m_offset += len; 00529 goto done; 00530 } 00531 00532 m_node = m_node->next; 00533 m_offset = 0; 00534 } 00535 00536 if (bytesLeft && m_lazyLength) 00537 { 00538 size_t len = (size_t)STDMIN(bytesLeft, (lword)m_lazyLength); 00539 blockedBytes = target.ChannelPut2(channel, m_lazyString, len, 0, blocking); 00540 if (blockedBytes) 00541 goto done; 00542 00543 m_lazyString += len; 00544 m_lazyLength -= len; 00545 bytesLeft -= len; 00546 } 00547 00548 done: 00549 transferBytes -= bytesLeft; 00550 return blockedBytes; 00551 } 00552 00553 size_t ByteQueue::Walker::CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end, const std::string &channel, bool blocking) const 00554 { 00555 Walker walker(*this); 00556 walker.Skip(begin); 00557 lword transferBytes = end-begin; 00558 size_t blockedBytes = walker.TransferTo2(target, transferBytes, channel, blocking); 00559 begin += transferBytes; 00560 return blockedBytes; 00561 } 00562 00563 NAMESPACE_END 00564 00565 #endif