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