1 // queue.h - originally written and placed in the public domain by Wei Dai
2
3 /// \file
4 /// \brief Classes for an unlimited queue to store bytes
5
6 #ifndef CRYPTOPP_QUEUE_H
7 #define CRYPTOPP_QUEUE_H
8
9 #include "cryptlib.h"
10 #include "simple.h"
11
NAMESPACE_BEGIN(CryptoPP)12 NAMESPACE_BEGIN(CryptoPP)
13
14 class ByteQueueNode;
15
16 /// \brief Data structure used to store byte strings
17 /// \details The queue is implemented as a linked list of byte arrays.
18 /// Each byte array is stored in a ByteQueueNode.
19 /// \sa <A HREF="https://www.cryptopp.com/wiki/ByteQueue">ByteQueue</A>
20 /// on the Crypto++ wiki.
21 /// \since Crypto++ 2.0
22 class CRYPTOPP_DLL ByteQueue : public Bufferless<BufferedTransformation>
23 {
24 public:
25 virtual ~ByteQueue();
26
27 /// \brief Construct a ByteQueue
28 /// \param nodeSize the initial node size
29 /// \details Internally, ByteQueue uses a ByteQueueNode to store bytes,
30 /// and <tt>nodeSize</tt> determines the size of the ByteQueueNode. A value
31 /// of 0 indicates the ByteQueueNode should be automatically sized,
32 /// which means a value of 256 is used.
33 ByteQueue(size_t nodeSize=0);
34
35 /// \brief Copy construct a ByteQueue
36 /// \param copy the other ByteQueue
37 ByteQueue(const ByteQueue ©);
38
39 // BufferedTransformation
40 lword MaxRetrievable() const
41 {return CurrentSize();}
42 bool AnyRetrievable() const
43 {return !IsEmpty();}
44
45 void IsolatedInitialize(const NameValuePairs ¶meters);
46 byte * CreatePutSpace(size_t &size);
47 size_t Put2(const byte *inString, size_t length, int messageEnd, bool blocking);
48
49 size_t Get(byte &outByte);
50 size_t Get(byte *outString, size_t getMax);
51
52 size_t Peek(byte &outByte) const;
53 size_t Peek(byte *outString, size_t peekMax) const;
54
55 size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true);
56 size_t CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true) const;
57
58 /// \brief Set node size
59 /// \param nodeSize the new node size, in bytes
60 /// \details The default node size is 256.
61 void SetNodeSize(size_t nodeSize);
62
63 /// \brief Determine data size
64 /// \return the data size, in bytes
65 lword CurrentSize() const;
66
67 /// \brief Determine data availability
68 /// \return true if the ByteQueue has data, false otherwise
69 bool IsEmpty() const;
70
71 /// \brief Empty the queue
72 void Clear();
73
74 /// \brief Insert data in the queue
75 /// \param inByte a byte to insert
76 /// \details Unget() inserts a byte at the head of the queue
77 void Unget(byte inByte);
78
79 /// \brief Insert data in the queue
80 /// \param inString a byte array to insert
81 /// \param length the size of the byte array
82 /// \details Unget() inserts a byte array at the head of the queue
83 void Unget(const byte *inString, size_t length);
84
85 /// \brief Peek data in the queue
86 /// \param contiguousSize the size of the data
87 /// \details Spy() peeks at data at the head of the queue. Spy() does
88 /// not remove data from the queue.
89 /// \details The data's size is returned in <tt>contiguousSize</tt>.
90 /// Spy() returns the size of the first byte array in the list. The
91 /// entire data may be larger since the queue is a linked list of
92 /// byte arrays.
93 const byte * Spy(size_t &contiguousSize) const;
94
95 /// \brief Insert data in the queue
96 /// \param inString a byte array to insert
97 /// \param size the length of the byte array
98 /// \details LazyPut() inserts a byte array at the tail of the queue.
99 /// The data may not be copied at this point. Rather, the pointer
100 /// and size to external data are recorded.
101 /// \details Another call to Put() or LazyPut() will force the data to
102 /// be copied. When lazy puts are used, the data is copied when
103 /// FinalizeLazyPut() is called.
104 /// \sa LazyPutter
105 void LazyPut(const byte *inString, size_t size);
106
107 /// \brief Insert data in the queue
108 /// \param inString a byte array to insert
109 /// \param size the length of the byte array
110 /// \details LazyPut() inserts a byte array at the tail of the queue.
111 /// The data may not be copied at this point. Rather, the pointer
112 /// and size to external data are recorded.
113 /// \details Another call to Put() or LazyPut() will force the data to
114 /// be copied. When lazy puts are used, the data is copied when
115 /// FinalizeLazyPut() is called.
116 /// \sa LazyPutter
117 void LazyPutModifiable(byte *inString, size_t size);
118
119 /// \brief Remove data from the queue
120 /// \param size the length of the data
121 /// \throw InvalidArgument if there is no lazy data in the queue or if
122 /// size is larger than the lazy string
123 /// \details UndoLazyPut() truncates data inserted using LazyPut() by
124 /// modifying size.
125 /// \sa LazyPutter
126 void UndoLazyPut(size_t size);
127
128 /// \brief Insert data in the queue
129 /// \details FinalizeLazyPut() copies external data inserted using
130 /// LazyPut() or LazyPutModifiable() into the tail of the queue.
131 /// \sa LazyPutter
132 void FinalizeLazyPut();
133
134 /// \brief Assign contents from another ByteQueue
135 /// \param rhs the other ByteQueue
136 /// \return reference to this ByteQueue
137 ByteQueue & operator=(const ByteQueue &rhs);
138
139 /// \brief Bitwise compare two ByteQueue
140 /// \param rhs the other ByteQueue
141 /// \return true if the size and bits are equal, false otherwise
142 /// \details operator==() walks each ByteQueue comparing bytes in
143 /// each queue. operator==() is not constant time.
144 bool operator==(const ByteQueue &rhs) const;
145
146 /// \brief Bitwise compare two ByteQueue
147 /// \param rhs the other ByteQueue
148 /// \return true if the size and bits are not equal, false otherwise
149 /// \details operator!=() is implemented in terms of operator==().
150 /// operator==() is not constant time.
151 bool operator!=(const ByteQueue &rhs) const {return !operator==(rhs);}
152
153 /// \brief Retrieve data from the queue
154 /// \param index of byte to retrieve
155 /// \return byte at the specified index
156 /// \details operator[]() does not perform bounds checking.
157 byte operator[](lword index) const;
158
159 /// \brief Swap contents with another ByteQueue
160 /// \param rhs the other ByteQueue
161 void swap(ByteQueue &rhs);
162
163 /// \brief A ByteQueue iterator
164 class Walker : public InputRejecting<BufferedTransformation>
165 {
166 public:
167 /// \brief Construct a ByteQueue Walker
168 /// \param queue a ByteQueue
169 Walker(const ByteQueue &queue)
170 : m_queue(queue), m_node(NULLPTR), m_position(0), m_offset(0), m_lazyString(NULLPTR), m_lazyLength(0)
171 {Initialize();}
172
173 lword GetCurrentPosition() {return m_position;}
174
175 lword MaxRetrievable() const
176 {return m_queue.CurrentSize() - m_position;}
177
178 void IsolatedInitialize(const NameValuePairs ¶meters);
179
180 size_t Get(byte &outByte);
181 size_t Get(byte *outString, size_t getMax);
182
183 size_t Peek(byte &outByte) const;
184 size_t Peek(byte *outString, size_t peekMax) const;
185
186 size_t TransferTo2(BufferedTransformation &target, lword &transferBytes, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true);
187 size_t CopyRangeTo2(BufferedTransformation &target, lword &begin, lword end=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL, bool blocking=true) const;
188
189 private:
190 const ByteQueue &m_queue;
191 const ByteQueueNode *m_node;
192 lword m_position;
193 size_t m_offset;
194 const byte *m_lazyString;
195 size_t m_lazyLength;
196 };
197
198 friend class Walker;
199
200 protected:
201 void CleanupUsedNodes();
202 void CopyFrom(const ByteQueue ©);
203 void Destroy();
204
205 private:
206 ByteQueueNode *m_head, *m_tail;
207 byte *m_lazyString;
208 size_t m_lazyLength;
209 size_t m_nodeSize;
210 bool m_lazyStringModifiable;
211 bool m_autoNodeSize;
212 };
213
214 /// \brief Helper class to finalize Puts on ByteQueue
215 /// \details LazyPutter ensures LazyPut is committed to the ByteQueue
216 /// in event of exception. During destruction, the LazyPutter class
217 /// calls FinalizeLazyPut.
218 class CRYPTOPP_DLL LazyPutter
219 {
220 public:
~LazyPutter()221 virtual ~LazyPutter() {
222 try {m_bq.FinalizeLazyPut();}
223 catch(const Exception&) {CRYPTOPP_ASSERT(0);}
224 }
225
226 /// \brief Construct a LazyPutter
227 /// \param bq the ByteQueue
228 /// \param inString a byte array to insert
229 /// \param size the length of the byte array
230 /// \details LazyPutter ensures LazyPut is committed to the ByteQueue
231 /// in event of exception. During destruction, the LazyPutter class
232 /// calls FinalizeLazyPut.
LazyPutter(ByteQueue & bq,const byte * inString,size_t size)233 LazyPutter(ByteQueue &bq, const byte *inString, size_t size)
234 : m_bq(bq) {bq.LazyPut(inString, size);}
235
236 protected:
LazyPutter(ByteQueue & bq)237 LazyPutter(ByteQueue &bq) : m_bq(bq) {}
238
239 private:
240 ByteQueue &m_bq;
241 };
242
243 /// \brief Helper class to finalize Puts on ByteQueue
244 /// \details LazyPutterModifiable ensures LazyPut is committed to the
245 /// ByteQueue in event of exception. During destruction, the
246 /// LazyPutterModifiable class calls FinalizeLazyPut.
247 class LazyPutterModifiable : public LazyPutter
248 {
249 public:
250 /// \brief Construct a LazyPutterModifiable
251 /// \param bq the ByteQueue
252 /// \param inString a byte array to insert
253 /// \param size the length of the byte array
254 /// \details LazyPutterModifiable ensures LazyPut is committed to the
255 /// ByteQueue in event of exception. During destruction, the
256 /// LazyPutterModifiable class calls FinalizeLazyPut.
LazyPutterModifiable(ByteQueue & bq,byte * inString,size_t size)257 LazyPutterModifiable(ByteQueue &bq, byte *inString, size_t size)
258 : LazyPutter(bq) {bq.LazyPutModifiable(inString, size);}
259 };
260
261 NAMESPACE_END
262
263 #ifndef __BORLANDC__
NAMESPACE_BEGIN(std)264 NAMESPACE_BEGIN(std)
265 template<> inline void swap(CryptoPP::ByteQueue &a, CryptoPP::ByteQueue &b)
266 {
267 a.swap(b);
268 }
269 NAMESPACE_END
270 #endif
271
272 #endif
273