1 // SPDX-License-Identifier: BSD-3-Clause
2 /* ==========================================================================
3 * Copyright (c) 2016-2018, The Linux Foundation.
4 * Copyright (c) 2018-2024, Laurence Lundblade.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
16 * * Neither the name of The Linux Foundation nor the names of its
17 * contributors, nor the name "Laurence Lundblade" may be used to
18 * endorse or promote products derived from this software without
19 * specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
22 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
25 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
28 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
30 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
31 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 * ========================================================================= */
33
34
35
36 /*=============================================================================
37 FILE: UsefulBuf.c
38
39 DESCRIPTION: General purpose input and output buffers
40
41 EDIT HISTORY FOR FILE:
42
43 This section contains comments describing changes made to the module.
44 Notice that changes are listed in reverse chronological order.
45
46 when who what, where, why
47 -------- ---- ---------------------------------------------------
48 21/05/2024 llundblade Comment formatting and some code tidiness.
49 19/12/2022 llundblade Don't pass NULL to memmove when adding empty data.
50 4/11/2022 llundblade Add GetOutPlace and Advance to UsefulOutBuf
51 3/6/2021 mcr/llundblade Fix warnings related to --Wcast-qual
52 01/28/2020 llundblade Refine integer signedness to quiet static analysis.
53 01/08/2020 llundblade Documentation corrections & improved code formatting.
54 11/08/2019 llundblade Re check pointer math and update comments
55 3/6/2019 llundblade Add UsefulBuf_IsValue()
56 09/07/17 llundbla Fix critical bug in UsefulBuf_Find() -- a read off
57 the end of memory when the bytes to find is longer
58 than the bytes to search.
59 06/27/17 llundbla Fix UsefulBuf_Compare() bug. Only affected comparison
60 for < or > for unequal length buffers. Added
61 UsefulBuf_Set() function.
62 05/30/17 llundbla Functions for NULL UsefulBufs and const / unconst
63 11/13/16 llundbla Initial Version.
64
65 ============================================================================*/
66
67 #include "UsefulBuf.h"
68
69 /* used to catch use of uninitialized or corrupted UsefulOutBuf */
70 #define USEFUL_OUT_BUF_MAGIC (0x0B0F)
71
72
73 /*
74 * Public function -- see UsefulBuf.h
75 */
UsefulBuf_CopyOffset(UsefulBuf Dest,size_t uOffset,const UsefulBufC Src)76 UsefulBufC UsefulBuf_CopyOffset(UsefulBuf Dest, size_t uOffset, const UsefulBufC Src)
77 {
78 /* Do this with subtraction so it doesn't give an erroneous
79 * result if uOffset + Src.len overflows. Right side is equivalent to
80 * uOffset + Src.len > Dest.len
81 */
82 if(uOffset > Dest.len || Src.len > Dest.len - uOffset) {
83 return NULLUsefulBufC;
84 }
85
86 memcpy((uint8_t *)Dest.ptr + uOffset, Src.ptr, Src.len);
87
88 return (UsefulBufC){Dest.ptr, Src.len + uOffset};
89 }
90
91
92 /*
93 * Public function -- see UsefulBuf.h
94 */
UsefulBuf_Compare(const UsefulBufC UB1,const UsefulBufC UB2)95 int UsefulBuf_Compare(const UsefulBufC UB1, const UsefulBufC UB2)
96 {
97 /* Use comparisons rather than subtracting lengths to
98 * return an int instead of a size_t
99 */
100 if(UB1.len < UB2.len) {
101 return -1;
102 } else if (UB1.len > UB2.len) {
103 return 1;
104 } /* else UB1.len == UB2.len */
105
106 return memcmp(UB1.ptr, UB2.ptr, UB1.len);
107 }
108
109
110 /*
111 * Public function -- see UsefulBuf.h
112 */
UsefulBuf_IsValue(const UsefulBufC UB,uint8_t uValue)113 size_t UsefulBuf_IsValue(const UsefulBufC UB, uint8_t uValue)
114 {
115 if(UsefulBuf_IsNULLOrEmptyC(UB)) {
116 /* Not a match */
117 return 0;
118 }
119
120 const uint8_t * const pEnd = (const uint8_t *)UB.ptr + UB.len;
121 for(const uint8_t *p = UB.ptr; p < pEnd; p++) {
122 if(*p != uValue) {
123 /* Byte didn't match */
124 /* Cast from signed to unsigned. Safe because the loop increments.*/
125 return (size_t)(p - (const uint8_t *)UB.ptr);
126 }
127 }
128
129 /* Success. All bytes matched */
130 return SIZE_MAX;
131 }
132
133
134 /*
135 * Public function -- see UsefulBuf.h
136 */
UsefulBuf_FindBytes(UsefulBufC BytesToSearch,UsefulBufC BytesToFind)137 size_t UsefulBuf_FindBytes(UsefulBufC BytesToSearch, UsefulBufC BytesToFind)
138 {
139 if(BytesToSearch.len < BytesToFind.len) {
140 return SIZE_MAX;
141 }
142
143 for(size_t uPos = 0; uPos <= BytesToSearch.len - BytesToFind.len; uPos++) {
144 UsefulBufC SearchNext;
145
146 SearchNext.ptr = ((const uint8_t *)BytesToSearch.ptr) + uPos;
147 SearchNext.len = BytesToFind.len;
148 if(!UsefulBuf_Compare(SearchNext, BytesToFind)) {
149 return uPos;
150 }
151 }
152
153 return SIZE_MAX;
154 }
155
156
157 /*
158 * Public function -- see UsefulBuf.h
159 *
160 * Code Reviewers: THIS FUNCTION DOES POINTER MATH
161 */
UsefulOutBuf_Init(UsefulOutBuf * pMe,UsefulBuf Storage)162 void UsefulOutBuf_Init(UsefulOutBuf *pMe, UsefulBuf Storage)
163 {
164 pMe->magic = USEFUL_OUT_BUF_MAGIC;
165 UsefulOutBuf_Reset(pMe);
166 pMe->UB = Storage;
167
168 #if 0
169 /* This check is off by default.
170 *
171 * The following check fails on ThreadX
172 *
173 * Sanity check on the pointer and size to be sure we are not
174 * passed a buffer that goes off the end of the address space.
175 * Given this test, we know that all unsigned lengths less than
176 * me->size are valid and won't wrap in any pointer additions
177 * based off of pStorage in the rest of this code.
178 */
179 const uintptr_t ptrM = UINTPTR_MAX - Storage.len;
180 if(Storage.ptr && (uintptr_t)Storage.ptr > ptrM) /* Check #0 */
181 me->err = 1;
182 #endif
183 }
184
185
186
187 /*
188 * Public function -- see UsefulBuf.h
189 *
190 * The core of UsefulOutBuf -- put some bytes in the buffer without writing off
191 * the end of it.
192 *
193 * Code Reviewers: THIS FUNCTION DOES POINTER MATH
194 *
195 * This function inserts the source buffer, NewData, into the destination
196 * buffer, me->UB.ptr.
197 *
198 * Destination is represented as:
199 * me->UB.ptr -- start of the buffer
200 * me->UB.len -- size of the buffer UB.ptr
201 * me->data_len -- length of value data in UB
202 *
203 * Source is data:
204 * NewData.ptr -- start of source buffer
205 * NewData.len -- length of source buffer
206 *
207 * Insertion point:
208 * uInsertionPos.
209 *
210 * Steps:
211 *
212 * 0. Corruption checks on UsefulOutBuf
213 *
214 * 1. Figure out if the new data will fit or not
215 *
216 * 2. Is insertion position in the range of valid data?
217 *
218 * 3. If insertion point is not at the end, slide data to the right of the
219 * insertion point to the right
220 *
221 * 4. Put the new data in at the insertion position.
222 *
223 */
UsefulOutBuf_InsertUsefulBuf(UsefulOutBuf * pMe,UsefulBufC NewData,size_t uInsertionPos)224 void UsefulOutBuf_InsertUsefulBuf(UsefulOutBuf *pMe, UsefulBufC NewData, size_t uInsertionPos)
225 {
226 if(pMe->err) {
227 /* Already in error state. */
228 return;
229 }
230
231 /* 0. Sanity check the UsefulOutBuf structure
232 * A "counter measure". If magic number is not the right number it
233 * probably means pMe was not initialized or it was corrupted. Attackers
234 * can defeat this, but it is a hurdle and does good with very
235 * little code.
236 */
237 if(pMe->magic != USEFUL_OUT_BUF_MAGIC) {
238 pMe->err = 1;
239 return; /* Magic number is wrong due to uninitalization or corrption */
240 }
241
242 /* Make sure valid data is less than buffer size. This would only occur
243 * if there was corruption of me, but it is also part of the checks to
244 * be sure there is no pointer arithmatic under/overflow.
245 */
246 if(pMe->data_len > pMe->UB.len) { /* Check #1 */
247 pMe->err = 1;
248 /* Offset of valid data is off the end of the UsefulOutBuf due to
249 * uninitialization or corruption
250 */
251 return;
252 }
253
254 /* 1. Will it fit?
255 * WillItFit() is the same as: NewData.len <= (me->UB.len - me->data_len)
256 * Check #1 makes sure subtraction in RoomLeft will not wrap around
257 */
258 if(! UsefulOutBuf_WillItFit(pMe, NewData.len)) { /* Check #2 */
259 /* The new data will not fit into the the buffer. */
260 pMe->err = 1;
261 return;
262 }
263
264 /* 2. Check the Insertion Position
265 * This, with Check #1, also confirms that uInsertionPos <= me->data_len and
266 * that uInsertionPos + pMe->UB.ptr will not wrap around the end of the
267 * address space.
268 */
269 if(uInsertionPos > pMe->data_len) { /* Check #3 */
270 /* Off the end of the valid data in the buffer. */
271 pMe->err = 1;
272 return;
273 }
274
275 /* 3. Slide existing data to the right */
276 if (!UsefulOutBuf_IsBufferNULL(pMe)) {
277 uint8_t *pSourceOfMove = ((uint8_t *)pMe->UB.ptr) + uInsertionPos; /* PtrMath #1 */
278 size_t uNumBytesToMove = pMe->data_len - uInsertionPos; /* PtrMath #2 */
279 uint8_t *pDestinationOfMove = pSourceOfMove + NewData.len; /* PtrMath #3*/
280
281 /* To know memmove won't go off end of destination, see PtrMath #4.
282 * Use memove because it handles overlapping buffers
283 */
284 memmove(pDestinationOfMove, pSourceOfMove, uNumBytesToMove);
285
286 /* 4. Put the new data in */
287 uint8_t *pInsertionPoint = pSourceOfMove;
288 /* To know memmove won't go off end of destination, see PtrMath #5 */
289 if(NewData.ptr != NULL) {
290 memmove(pInsertionPoint, NewData.ptr, NewData.len);
291 }
292 }
293
294 pMe->data_len += NewData.len;
295 }
296
297
298 /*
299 * Rationale that describes why the above pointer math is safe
300 *
301 * PtrMath #1 will never wrap around over because
302 * Check #0 in UsefulOutBuf_Init that me->UB.ptr + me->UB.len doesn't wrap
303 * Check #1 makes sure me->data_len is less than me->UB.len
304 * Check #3 makes sure uInsertionPos is less than me->data_len
305 *
306 * PtrMath #2 will never wrap around under because
307 * Check #3 makes sure uInsertionPos is less than me->data_len
308 *
309 * PtrMath #3 will never wrap around over because
310 * PtrMath #1 is checked resulting in pSourceOfMove being between me->UB.ptr and me->UB.ptr + me->data_len
311 * Check #2 that NewData.len will fit in the unused space left in me->UB
312 *
313 * PtrMath #4 will never wrap under because
314 * Calculation for extent or memmove is uRoomInDestination = me->UB.len - (uInsertionPos + NewData.len)
315 * Check #3 makes sure uInsertionPos is less than me->data_len
316 * Check #3 allows Check #2 to be refactored as NewData.Len > (me->size - uInsertionPos)
317 * This algebraically rearranges to me->size > uInsertionPos + NewData.len
318 *
319 * PtrMath #5 will never wrap under because
320 * Calculation for extent of memove is uRoomInDestination = me->UB.len - uInsertionPos;
321 * Check #1 makes sure me->data_len is less than me->size
322 * Check #3 makes sure uInsertionPos is less than me->data_len
323 */
324
325
326 /*
327 * Public function for advancing data length. See qcbor/UsefulBuf.h
328 */
UsefulOutBuf_Advance(UsefulOutBuf * pMe,size_t uAmount)329 void UsefulOutBuf_Advance(UsefulOutBuf *pMe, size_t uAmount)
330 {
331 /* This function is a trimmed down version of
332 * UsefulOutBuf_InsertUsefulBuf(). This could be combined with the
333 * code in UsefulOutBuf_InsertUsefulBuf(), but that would make
334 * UsefulOutBuf_InsertUsefulBuf() bigger and this will be very
335 * rarely used.
336 */
337
338 if(pMe->err) {
339 /* Already in error state. */
340 return;
341 }
342
343 /* 0. Sanity check the UsefulOutBuf structure
344 *
345 * A "counter measure". If magic number is not the right number it
346 * probably means me was not initialized or it was
347 * corrupted. Attackers can defeat this, but it is a hurdle and
348 * does good with very little code.
349 */
350 if(pMe->magic != USEFUL_OUT_BUF_MAGIC) {
351 pMe->err = 1;
352 return; /* Magic number is wrong due to uninitalization or corrption */
353 }
354
355 /* Make sure valid data is less than buffer size. This would only
356 * occur if there was corruption of me, but it is also part of the
357 * checks to be sure there is no pointer arithmatic
358 * under/overflow.
359 */
360 if(pMe->data_len > pMe->UB.len) { /* Check #1 */
361 pMe->err = 1;
362 /* Offset of valid data is off the end of the UsefulOutBuf due
363 * to uninitialization or corruption.
364 */
365 return;
366 }
367
368 /* 1. Will it fit?
369 *
370 * WillItFit() is the same as: NewData.len <= (me->UB.len -
371 * me->data_len) Check #1 makes sure subtraction in RoomLeft will
372 * not wrap around
373 */
374 if(! UsefulOutBuf_WillItFit(pMe, uAmount)) { /* Check #2 */
375 /* The new data will not fit into the the buffer. */
376 pMe->err = 1;
377 return;
378 }
379
380 pMe->data_len += uAmount;
381 }
382
383
384 /*
385 * Public function -- see UsefulBuf.h
386 */
UsefulOutBuf_OutUBuf(UsefulOutBuf * pMe)387 UsefulBufC UsefulOutBuf_OutUBuf(UsefulOutBuf *pMe)
388 {
389 if(pMe->err) {
390 return NULLUsefulBufC;
391 }
392
393 if(pMe->magic != USEFUL_OUT_BUF_MAGIC) {
394 pMe->err = 1;
395 return NULLUsefulBufC;
396 }
397
398 return (UsefulBufC){pMe->UB.ptr, pMe->data_len};
399 }
400
401
402 /*
403 * Public function -- see UsefulBuf.h
404 *
405 * Copy out the data accumulated in to the output buffer.
406 */
UsefulOutBuf_CopyOut(UsefulOutBuf * pMe,UsefulBuf pDest)407 UsefulBufC UsefulOutBuf_CopyOut(UsefulOutBuf *pMe, UsefulBuf pDest)
408 {
409 const UsefulBufC Tmp = UsefulOutBuf_OutUBuf(pMe);
410 if(UsefulBuf_IsNULLC(Tmp)) {
411 return NULLUsefulBufC;
412 }
413 return UsefulBuf_Copy(pDest, Tmp);
414 }
415
416
417
418
419 /*
420 * Public function -- see UsefulBuf.h
421 *
422 * The core of UsefulInputBuf -- consume bytes without going off end of buffer.
423 *
424 * Code Reviewers: THIS FUNCTION DOES POINTER MATH
425 */
UsefulInputBuf_GetBytes(UsefulInputBuf * pMe,size_t uAmount)426 const void * UsefulInputBuf_GetBytes(UsefulInputBuf *pMe, size_t uAmount)
427 {
428 /* Already in error state. Do nothing. */
429 if(pMe->err) {
430 return NULL;
431 }
432
433 if(!UsefulInputBuf_BytesAvailable(pMe, uAmount)) {
434 /* Number of bytes asked for is more than available */
435 pMe->err = 1;
436 return NULL;
437 }
438
439 /* This is going to succeed */
440 const void * const result = ((const uint8_t *)pMe->UB.ptr) + pMe->cursor;
441 /* Won't overflow because of check using UsefulInputBuf_BytesAvailable() */
442 pMe->cursor += uAmount;
443 return result;
444 }
445