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