SEGV in CFX_BaseSegmentedArray::Iterate() when CS has malformed dictionary.
[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_Alloc(FX_BYTE, m_UnitSize * m_SegmentSize);
193     if (!pSegment) {
194         return NULL;
195     }
196     if (m_pIndex == NULL) {
197         m_pIndex = pSegment;
198         m_DataSize ++;
199         return pSegment;
200     }
201     if (m_IndexDepth == 0) {
202         void** pIndex = (void**)FX_Alloc(void*, m_IndexSize);
203         if (pIndex == NULL) {
204             FX_Free(pSegment);
205             return NULL;
206         }
207         pIndex[0] = m_pIndex;
208         pIndex[1] = pSegment;
209         m_pIndex = pIndex;
210         m_DataSize ++;
211         m_IndexDepth ++;
212         return pSegment;
213     }
214     int seg_index = m_DataSize / m_SegmentSize;
215     if (seg_index % m_IndexSize) {
216         void** pIndex = GetIndex(seg_index);
217         pIndex[seg_index % m_IndexSize] = pSegment;
218         m_DataSize ++;
219         return pSegment;
220     }
221     int tree_size = 1;
222     int i;
223     for (i = 0; i < m_IndexDepth; i ++) {
224         tree_size *= m_IndexSize;
225     }
226     if (m_DataSize == tree_size * m_SegmentSize) {
227         void** pIndex = (void**)FX_Alloc(void*, m_IndexSize);
228         if (pIndex == NULL) {
229             FX_Free(pSegment);
230             return NULL;
231         }
232         pIndex[0] = m_pIndex;
233         m_pIndex = pIndex;
234         m_IndexDepth ++;
235     } else {
236         tree_size /= m_IndexSize;
237     }
238     void** pSpot = (void**)m_pIndex;
239     for (i = 1; i < m_IndexDepth; i ++) {
240         if (pSpot[seg_index / tree_size] == NULL) {
241             pSpot[seg_index / tree_size] = (void*)FX_Alloc(void*, m_IndexSize);
242             if (pSpot[seg_index / tree_size] == NULL) {
243                 break;
244             }
245         }
246         pSpot = (void**)pSpot[seg_index / tree_size];
247         seg_index = seg_index % tree_size;
248         tree_size /= m_IndexSize;
249     }
250     if (i < m_IndexDepth) {
251         FX_Free(pSegment);
252         RemoveAll();
253         return NULL;
254     }
255     pSpot[seg_index % m_IndexSize] = pSegment;
256     m_DataSize ++;
257     return pSegment;
258 }
259 void** CFX_BaseSegmentedArray::GetIndex(int seg_index) const
260 {
261     ASSERT(m_IndexDepth != 0);
262     if (m_IndexDepth == 1) {
263         return (void**)m_pIndex;
264     } else if (m_IndexDepth == 2) {
265         return (void**)((void**)m_pIndex)[seg_index / m_IndexSize];
266     }
267     int tree_size = 1;
268     int i;
269     for (i = 1; i < m_IndexDepth; i ++) {
270         tree_size *= m_IndexSize;
271     }
272     void** pSpot = (void**)m_pIndex;
273     for (i = 1; i < m_IndexDepth; i ++) {
274         pSpot = (void**)pSpot[seg_index / tree_size];
275         seg_index = seg_index % tree_size;
276         tree_size /= m_IndexSize;
277     }
278     return pSpot;
279 }
280 void* CFX_BaseSegmentedArray::IterateSegment(FX_LPCBYTE pSegment, int count, FX_BOOL (*callback)(void* param, void* pData), void* param) const
281 {
282     for (int i = 0; i < count; i ++) {
283         if (!callback(param, (void*)(pSegment + i * m_UnitSize))) {
284             return (void*)(pSegment + i * m_UnitSize);
285         }
286     }
287     return NULL;
288 }
289 void* CFX_BaseSegmentedArray::IterateIndex(int level, int& start, void** pIndex, FX_BOOL (*callback)(void* param, void* pData), void* param) const
290 {
291     if (level == 0) {
292         int count = m_DataSize - start;
293         if (count > m_SegmentSize) {
294             count = m_SegmentSize;
295         }
296         start += count;
297         return IterateSegment((FX_LPCBYTE)pIndex, count, callback, param);
298     }
299     for (int i = 0; i < m_IndexSize; i ++) {
300         if (pIndex[i] == NULL) {
301             continue;
302         }
303         void* p = IterateIndex(level - 1, start, (void**)pIndex[i], callback, param);
304         if (p) {
305             return p;
306         }
307     }
308     return NULL;
309 }
310 void* CFX_BaseSegmentedArray::Iterate(FX_BOOL (*callback)(void* param, void* pData), void* param) const
311 {
312     if (m_pIndex == NULL) {
313         return NULL;
314     }
315     int start = 0;
316     return IterateIndex(m_IndexDepth, start, (void**)m_pIndex, callback, param);
317 }
318 void* CFX_BaseSegmentedArray::GetAt(int index) const
319 {
320     if (index < 0 || index >= m_DataSize) {
321         return NULL;
322     }
323     if (m_IndexDepth == 0) {
324         return (FX_LPBYTE)m_pIndex + m_UnitSize * index;
325     }
326     int seg_index = index / m_SegmentSize;
327     return (FX_LPBYTE)GetIndex(seg_index)[seg_index % m_IndexSize] + (index % m_SegmentSize) * m_UnitSize;
328 }
329 void CFX_BaseSegmentedArray::Delete(int index, int count)
330 {
331     if(index < 0 || count < 1 || index + count > m_DataSize) {
332         return;
333     }
334     int i;
335     for (i = index; i < m_DataSize - count; i ++) {
336         FX_BYTE* pSrc = (FX_BYTE*)GetAt(i + count);
337         FX_BYTE* pDest = (FX_BYTE*)GetAt(i);
338         for (int j = 0; j < m_UnitSize; j ++) {
339             pDest[j] = pSrc[j];
340         }
341     }
342     int new_segs = (m_DataSize - count + m_SegmentSize - 1) / m_SegmentSize;
343     int old_segs = (m_DataSize + m_SegmentSize - 1) / m_SegmentSize;
344     if (new_segs < old_segs) {
345         if(m_IndexDepth) {
346             for (i = new_segs; i < old_segs; i ++) {
347                 void** pIndex = GetIndex(i);
348                 FX_Free(pIndex[i % m_IndexSize]);
349                 pIndex[i % m_IndexSize] = NULL;
350             }
351         } else {
352             FX_Free(m_pIndex);
353             m_pIndex = NULL;
354         }
355     }
356     m_DataSize -= count;
357 }