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