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