Check for integer overflow in CFX_BasicArray.
[pdfium.git] / core / src / fxcrt / fx_basic_array.cpp
1 // Copyright 2014 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6
7 #include "../../include/fxcrt/fx_basic.h"
8 #include "../../../third_party/numerics/safe_math.h"
9
10 CFX_BasicArray::CFX_BasicArray(int unit_size)
11     : m_pData(NULL)
12     , m_nSize(0)
13     , m_nMaxSize(0)
14     , m_nGrowBy(0)
15 {
16     if (unit_size < 0 || unit_size > (1 << 28)) {
17         m_nUnitSize = 4;
18     } else {
19         m_nUnitSize = unit_size;
20     }
21 }
22 CFX_BasicArray::~CFX_BasicArray()
23 {
24     FX_Free(m_pData);
25 }
26 FX_BOOL CFX_BasicArray::SetSize(int nNewSize, int nGrowBy)
27 {
28     if (nNewSize <= 0) {
29         FX_Free(m_pData);
30         m_pData = NULL;
31         m_nSize = m_nMaxSize = 0;
32         return 0 == nNewSize;
33     }
34
35     m_nGrowBy = nGrowBy >= 0 ? nGrowBy : m_nGrowBy;
36
37     if (m_pData == NULL) {
38         base::CheckedNumeric<int> totalSize = nNewSize;
39         totalSize *= m_nUnitSize;
40         if (!totalSize.IsValid()) {
41             m_nSize = m_nMaxSize = 0;
42             return FALSE;
43         }
44         m_pData = FX_Alloc(FX_BYTE, totalSize.ValueOrDie());
45         if (!m_pData) {
46             m_nSize = m_nMaxSize = 0;
47             return FALSE;
48         }
49         m_nSize = m_nMaxSize = nNewSize;
50     } else if (nNewSize <= m_nMaxSize) {
51         if (nNewSize > m_nSize) {
52             FXSYS_memset32(m_pData + m_nSize * m_nUnitSize, 0, (nNewSize - m_nSize) * m_nUnitSize);
53         }
54         m_nSize = nNewSize;
55     } else {
56         int nGrowBy = m_nGrowBy;
57         if (nGrowBy == 0) {
58             nGrowBy = m_nSize / 8;
59             nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
60         }
61         int nNewMax;
62         if (nNewSize < m_nMaxSize + nGrowBy) {
63             nNewMax = m_nMaxSize + nGrowBy;
64         } else {
65             nNewMax = nNewSize;
66         }
67
68         base::CheckedNumeric<int> totalSize = nNewMax;
69         totalSize *= m_nUnitSize;
70         if (!totalSize.IsValid() || nNewMax < m_nSize) {
71             return FALSE;
72         }
73         FX_LPBYTE pNewData = FX_Realloc(FX_BYTE, m_pData, totalSize.ValueOrDie());
74         if (pNewData == NULL) {
75             return FALSE;
76         }
77         FXSYS_memset32(pNewData + m_nSize * m_nUnitSize, 0, (nNewMax - m_nSize) * m_nUnitSize);
78         m_pData = pNewData;
79         m_nSize = nNewSize;
80         m_nMaxSize = nNewMax;
81     }
82     return TRUE;
83 }
84 FX_BOOL CFX_BasicArray::Append(const CFX_BasicArray& src)
85 {
86     int nOldSize = m_nSize;
87     base::CheckedNumeric<int> newSize = m_nSize;
88     newSize += src.m_nSize;
89     if (m_nUnitSize != src.m_nUnitSize || !newSize.IsValid() || !SetSize(newSize.ValueOrDie(), -1)) {
90         return FALSE;
91     }
92
93     FXSYS_memcpy32(m_pData + nOldSize * m_nUnitSize, src.m_pData, src.m_nSize * m_nUnitSize);
94     return TRUE;
95 }
96 FX_BOOL CFX_BasicArray::Copy(const CFX_BasicArray& src)
97 {
98     if (!SetSize(src.m_nSize, -1)) {
99         return FALSE;
100     }
101     FXSYS_memcpy32(m_pData, src.m_pData, src.m_nSize * m_nUnitSize);
102     return TRUE;
103 }
104 FX_LPBYTE CFX_BasicArray::InsertSpaceAt(int nIndex, int nCount)
105 {
106     if (nIndex < 0 || nCount <= 0) {
107         return NULL;
108     }
109     if (nIndex >= m_nSize) {
110         if (!SetSize(nIndex + nCount, -1)) {
111             return NULL;
112         }
113     } else {
114         int nOldSize = m_nSize;
115         if (!SetSize(m_nSize + nCount, -1)) {
116             return NULL;
117         }
118         FXSYS_memmove32(m_pData + (nIndex + nCount)*m_nUnitSize, m_pData + nIndex * m_nUnitSize,
119                         (nOldSize - nIndex) * m_nUnitSize);
120         FXSYS_memset32(m_pData + nIndex * m_nUnitSize, 0, nCount * m_nUnitSize);
121     }
122     return m_pData + nIndex * m_nUnitSize;
123 }
124 FX_BOOL CFX_BasicArray::RemoveAt(int nIndex, int nCount)
125 {
126     if (nIndex < 0 || nCount <= 0 || m_nSize < nIndex + nCount) {
127         return FALSE;
128     }
129     int nMoveCount = m_nSize - (nIndex + nCount);
130     if (nMoveCount) {
131         FXSYS_memmove32(m_pData + nIndex * m_nUnitSize, m_pData + (nIndex + nCount) * m_nUnitSize, nMoveCount * m_nUnitSize);
132     }
133     m_nSize -= nCount;
134     return TRUE;
135 }
136 FX_BOOL CFX_BasicArray::InsertAt(int nStartIndex, const CFX_BasicArray* pNewArray)
137 {
138     if (pNewArray == NULL) {
139         return FALSE;
140     }
141     if (pNewArray->m_nSize == 0) {
142         return TRUE;
143     }
144     if (!InsertSpaceAt(nStartIndex, pNewArray->m_nSize)) {
145         return FALSE;
146     }
147     FXSYS_memcpy32(m_pData + nStartIndex * m_nUnitSize, pNewArray->m_pData, pNewArray->m_nSize * m_nUnitSize);
148     return TRUE;
149 }
150 const void* CFX_BasicArray::GetDataPtr(int index) const
151 {
152     if (index < 0 || index >= m_nSize || m_pData == NULL) {
153         return NULL;
154     }
155     return m_pData + index * m_nUnitSize;
156 }
157 CFX_BaseSegmentedArray::CFX_BaseSegmentedArray(int unit_size, int segment_units, int index_size)
158     : m_UnitSize(unit_size)
159     , m_SegmentSize(segment_units)
160     , m_IndexSize(index_size)
161     , m_IndexDepth(0)
162     , m_DataSize(0)
163     , m_pIndex(NULL)
164 {
165 }
166 void CFX_BaseSegmentedArray::SetUnitSize(int unit_size, int segment_units, int index_size)
167 {
168     ASSERT(m_DataSize == 0);
169     m_UnitSize = unit_size;
170     m_SegmentSize = segment_units;
171     m_IndexSize = index_size;
172 }
173 CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray()
174 {
175     RemoveAll();
176 }
177 static void _ClearIndex(int level, int size, void** pIndex)
178 {
179     if (level == 0) {
180         FX_Free(pIndex);
181         return;
182     }
183     for (int i = 0; i < size; i++) {
184         if (pIndex[i] == NULL) {
185             continue;
186         }
187         _ClearIndex(level - 1, size, (void**)pIndex[i]);
188     }
189     FX_Free(pIndex);
190 }
191 void CFX_BaseSegmentedArray::RemoveAll()
192 {
193     if (m_pIndex == NULL) {
194         return;
195     }
196     _ClearIndex(m_IndexDepth, m_IndexSize, (void**)m_pIndex);
197     m_pIndex = NULL;
198     m_IndexDepth = 0;
199     m_DataSize = 0;
200 }
201 void* CFX_BaseSegmentedArray::Add()
202 {
203     if (m_DataSize % m_SegmentSize) {
204         return GetAt(m_DataSize ++);
205     }
206     void* pSegment = FX_Alloc(FX_BYTE, m_UnitSize * m_SegmentSize);
207     if (!pSegment) {
208         return NULL;
209     }
210     if (m_pIndex == NULL) {
211         m_pIndex = pSegment;
212         m_DataSize ++;
213         return pSegment;
214     }
215     if (m_IndexDepth == 0) {
216         void** pIndex = (void**)FX_Alloc(void*, m_IndexSize);
217         if (pIndex == NULL) {
218             FX_Free(pSegment);
219             return NULL;
220         }
221         pIndex[0] = m_pIndex;
222         pIndex[1] = pSegment;
223         m_pIndex = pIndex;
224         m_DataSize ++;
225         m_IndexDepth ++;
226         return pSegment;
227     }
228     int seg_index = m_DataSize / m_SegmentSize;
229     if (seg_index % m_IndexSize) {
230         void** pIndex = GetIndex(seg_index);
231         pIndex[seg_index % m_IndexSize] = pSegment;
232         m_DataSize ++;
233         return pSegment;
234     }
235     int tree_size = 1;
236     int i;
237     for (i = 0; i < m_IndexDepth; i ++) {
238         tree_size *= m_IndexSize;
239     }
240     if (m_DataSize == tree_size * m_SegmentSize) {
241         void** pIndex = (void**)FX_Alloc(void*, m_IndexSize);
242         if (pIndex == NULL) {
243             FX_Free(pSegment);
244             return NULL;
245         }
246         pIndex[0] = m_pIndex;
247         m_pIndex = pIndex;
248         m_IndexDepth ++;
249     } else {
250         tree_size /= m_IndexSize;
251     }
252     void** pSpot = (void**)m_pIndex;
253     for (i = 1; i < m_IndexDepth; i ++) {
254         if (pSpot[seg_index / tree_size] == NULL) {
255             pSpot[seg_index / tree_size] = (void*)FX_Alloc(void*, m_IndexSize);
256             if (pSpot[seg_index / tree_size] == NULL) {
257                 break;
258             }
259         }
260         pSpot = (void**)pSpot[seg_index / tree_size];
261         seg_index = seg_index % tree_size;
262         tree_size /= m_IndexSize;
263     }
264     if (i < m_IndexDepth) {
265         FX_Free(pSegment);
266         RemoveAll();
267         return NULL;
268     }
269     pSpot[seg_index % m_IndexSize] = pSegment;
270     m_DataSize ++;
271     return pSegment;
272 }
273 void** CFX_BaseSegmentedArray::GetIndex(int seg_index) const
274 {
275     ASSERT(m_IndexDepth != 0);
276     if (m_IndexDepth == 1) {
277         return (void**)m_pIndex;
278     } else if (m_IndexDepth == 2) {
279         return (void**)((void**)m_pIndex)[seg_index / m_IndexSize];
280     }
281     int tree_size = 1;
282     int i;
283     for (i = 1; i < m_IndexDepth; i ++) {
284         tree_size *= m_IndexSize;
285     }
286     void** pSpot = (void**)m_pIndex;
287     for (i = 1; i < m_IndexDepth; i ++) {
288         pSpot = (void**)pSpot[seg_index / tree_size];
289         seg_index = seg_index % tree_size;
290         tree_size /= m_IndexSize;
291     }
292     return pSpot;
293 }
294 void* CFX_BaseSegmentedArray::IterateSegment(FX_LPCBYTE pSegment, int count, FX_BOOL (*callback)(void* param, void* pData), void* param) const
295 {
296     for (int i = 0; i < count; i ++) {
297         if (!callback(param, (void*)(pSegment + i * m_UnitSize))) {
298             return (void*)(pSegment + i * m_UnitSize);
299         }
300     }
301     return NULL;
302 }
303 void* CFX_BaseSegmentedArray::IterateIndex(int level, int& start, void** pIndex, FX_BOOL (*callback)(void* param, void* pData), void* param) const
304 {
305     if (level == 0) {
306         int count = m_DataSize - start;
307         if (count > m_SegmentSize) {
308             count = m_SegmentSize;
309         }
310         start += count;
311         return IterateSegment((FX_LPCBYTE)pIndex, count, callback, param);
312     }
313     for (int i = 0; i < m_IndexSize; i ++) {
314         if (pIndex[i] == NULL) {
315             continue;
316         }
317         void* p = IterateIndex(level - 1, start, (void**)pIndex[i], callback, param);
318         if (p) {
319             return p;
320         }
321     }
322     return NULL;
323 }
324 void* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, void* pData), void* param) const
325 {
326     if (m_pIndex == NULL) {
327         return NULL;
328     }
329     int start = 0;
330     return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param);
331 }
332 void* CFX_BaseSegmentedArray::GetAt(int index) const
333 {
334     if (index < 0 || index >= m_DataSize) {
335         return NULL;
336     }
337     if (m_IndexDepth == 0) {
338         return (FX_LPBYTE)m_pIndex + m_UnitSize * index;
339     }
340     int seg_index = index / m_SegmentSize;
341     return (FX_LPBYTE)GetIndex(seg_index)[seg_index % m_IndexSize] + (index % m_SegmentSize) * m_UnitSize;
342 }
343 void CFX_BaseSegmentedArray::Delete(int index, int count)
344 {
345     if(index < 0 || count < 1 || index + count > m_DataSize) {
346         return;
347     }
348     int i;
349     for (i = index; i < m_DataSize - count; i ++) {
350         FX_BYTE* pSrc = (FX_BYTE*)GetAt(i + count);
351         FX_BYTE* pDest = (FX_BYTE*)GetAt(i);
352         for (int j = 0; j < m_UnitSize; j ++) {
353             pDest[j] = pSrc[j];
354         }
355     }
356     int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize;
357     int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize;
358     if (new_segs < old_segs) {
359         if(m_IndexDepth) {
360             for (i = new_segs; i < old_segs; i ++) {
361                 void** pIndex = GetIndex(i);
362                 FX_Free(pIndex[i % m_IndexSize]);
363                 pIndex[i % m_IndexSize] = NULL;
364             }
365         } else {
366             FX_Free(m_pIndex);
367             m_pIndex = NULL;
368         }
369     }
370     m_DataSize -= count;
371 }