← Back to branch summary

~ubuntu-branches/debian/squeeze/pycryptopp/squeeze

« back to all changes in this revision

Viewing changes to cryptopp/queue.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Zooko O'Whielacronx
  • Date: 2009-06-22 22:20:50 UTC
  • Revision ID: james.westby@ubuntu.com-20090622222050-hbqmn50dt2kvoz5o
Tags: upstream-0.5.14
Import upstream version 0.5.14

Show diffs side-by-side

added added

removed removed

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