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 "xfa/fgas/crt/fgas_utils.h"
8
9 #include <algorithm>
10
11 #include "core/fxcrt/fx_basic.h"
12
13 class FX_BASEARRAYDATA {
14 public:
15 FX_BASEARRAYDATA(int32_t growsize, int32_t blocksize);
16 ~FX_BASEARRAYDATA();
17
18 int32_t iGrowSize;
19 int32_t iBlockSize;
20 int32_t iTotalCount;
21 int32_t iBlockCount;
22 uint8_t* pBuffer;
23 };
24
FX_BASEARRAYDATA(int32_t growsize,int32_t blocksize)25 FX_BASEARRAYDATA::FX_BASEARRAYDATA(int32_t growsize, int32_t blocksize)
26 : iGrowSize(growsize),
27 iBlockSize(blocksize),
28 iTotalCount(0),
29 iBlockCount(0),
30 pBuffer(nullptr) {}
31
~FX_BASEARRAYDATA()32 FX_BASEARRAYDATA::~FX_BASEARRAYDATA() {
33 FX_Free(pBuffer);
34 }
35
CFX_BaseArray(int32_t iGrowSize,int32_t iBlockSize)36 CFX_BaseArray::CFX_BaseArray(int32_t iGrowSize, int32_t iBlockSize) {
37 ASSERT(iGrowSize > 0 && iBlockSize > 0);
38 m_pData = new FX_BASEARRAYDATA(iGrowSize, iBlockSize);
39 }
~CFX_BaseArray()40 CFX_BaseArray::~CFX_BaseArray() {
41 RemoveAll(false);
42 delete m_pData;
43 }
GetSize() const44 int32_t CFX_BaseArray::GetSize() const {
45 return m_pData->iBlockCount;
46 }
GetBlockSize() const47 int32_t CFX_BaseArray::GetBlockSize() const {
48 return m_pData->iBlockSize;
49 }
AddSpaceTo(int32_t index)50 uint8_t* CFX_BaseArray::AddSpaceTo(int32_t index) {
51 ASSERT(index > -1);
52 uint8_t*& pBuffer = m_pData->pBuffer;
53 int32_t& iTotalCount = m_pData->iTotalCount;
54 int32_t iBlockSize = m_pData->iBlockSize;
55 if (index >= iTotalCount) {
56 int32_t iGrowSize = m_pData->iGrowSize;
57 iTotalCount = (index / iGrowSize + 1) * iGrowSize;
58 int32_t iNewSize = iTotalCount * iBlockSize;
59 if (!pBuffer) {
60 pBuffer = FX_Alloc(uint8_t, iNewSize);
61 } else {
62 pBuffer = FX_Realloc(uint8_t, pBuffer, iNewSize);
63 }
64 }
65 int32_t& iBlockCount = m_pData->iBlockCount;
66 if (index >= iBlockCount) {
67 iBlockCount = index + 1;
68 }
69 return pBuffer + index * iBlockSize;
70 }
GetAt(int32_t index) const71 uint8_t* CFX_BaseArray::GetAt(int32_t index) const {
72 ASSERT(index > -1 && index < m_pData->iBlockCount);
73 return m_pData->pBuffer + index * m_pData->iBlockSize;
74 }
GetBuffer() const75 uint8_t* CFX_BaseArray::GetBuffer() const {
76 return m_pData->pBuffer;
77 }
Append(const CFX_BaseArray & src,int32_t iStart,int32_t iCount)78 int32_t CFX_BaseArray::Append(const CFX_BaseArray& src,
79 int32_t iStart,
80 int32_t iCount) {
81 int32_t iBlockSize = m_pData->iBlockSize;
82 ASSERT(iBlockSize == src.m_pData->iBlockSize);
83 int32_t& iBlockCount = m_pData->iBlockCount;
84 int32_t iAdded = src.GetSize();
85 ASSERT(iStart > -1 && iStart < iAdded);
86 if (iCount < 0) {
87 iCount = iAdded;
88 }
89 if (iStart + iCount > iAdded) {
90 iCount = iAdded - iStart;
91 }
92 if (iCount < 1) {
93 return 0;
94 }
95 uint8_t* pDst = m_pData->pBuffer + iBlockCount * iBlockSize;
96 AddSpaceTo(iBlockCount + iCount - 1);
97 FXSYS_memcpy(pDst, src.m_pData->pBuffer + iStart * iBlockSize,
98 iCount * iBlockSize);
99 return iCount;
100 }
Copy(const CFX_BaseArray & src,int32_t iStart,int32_t iCount)101 int32_t CFX_BaseArray::Copy(const CFX_BaseArray& src,
102 int32_t iStart,
103 int32_t iCount) {
104 int32_t iBlockSize = m_pData->iBlockSize;
105 ASSERT(iBlockSize == src.m_pData->iBlockSize);
106 int32_t iCopied = src.GetSize();
107 ASSERT(iStart > -1 && iStart < iCopied);
108 if (iCount < 0) {
109 iCount = iCopied;
110 }
111 if (iStart + iCount > iCopied) {
112 iCount = iCopied - iStart;
113 }
114 if (iCount < 1) {
115 return 0;
116 }
117 RemoveAll(true);
118 AddSpaceTo(iCount - 1);
119 FXSYS_memcpy(m_pData->pBuffer, src.m_pData->pBuffer + iStart * iBlockSize,
120 iCount * iBlockSize);
121 return iCount;
122 }
RemoveLast(int32_t iCount)123 int32_t CFX_BaseArray::RemoveLast(int32_t iCount) {
124 int32_t& iBlockCount = m_pData->iBlockCount;
125 if (iCount < 0 || iCount > iBlockCount) {
126 iCount = iBlockCount;
127 iBlockCount = 0;
128 } else {
129 iBlockCount -= iCount;
130 }
131 return iCount;
132 }
RemoveAll(bool bLeaveMemory)133 void CFX_BaseArray::RemoveAll(bool bLeaveMemory) {
134 if (!bLeaveMemory) {
135 uint8_t*& pBuffer = m_pData->pBuffer;
136 if (pBuffer) {
137 FX_Free(pBuffer);
138 pBuffer = nullptr;
139 }
140 m_pData->iTotalCount = 0;
141 }
142 m_pData->iBlockCount = 0;
143 }
144
CFX_BaseMassArrayImp(int32_t iChunkSize,int32_t iBlockSize)145 CFX_BaseMassArrayImp::CFX_BaseMassArrayImp(int32_t iChunkSize,
146 int32_t iBlockSize)
147 : m_iChunkSize(iChunkSize),
148 m_iBlockSize(iBlockSize),
149 m_iChunkCount(0),
150 m_iBlockCount(0),
151 m_pData(new CFX_ArrayTemplate<void*>()) {
152 ASSERT(m_iChunkSize > 0 && m_iBlockSize > 0);
153 m_pData->SetSize(16);
154 }
~CFX_BaseMassArrayImp()155 CFX_BaseMassArrayImp::~CFX_BaseMassArrayImp() {
156 RemoveAll(false);
157 delete m_pData;
158 }
AddSpaceTo(int32_t index)159 uint8_t* CFX_BaseMassArrayImp::AddSpaceTo(int32_t index) {
160 ASSERT(index > -1);
161 uint8_t* pChunk;
162 if (index < m_iBlockCount) {
163 pChunk = (uint8_t*)m_pData->GetAt(index / m_iChunkSize);
164 } else {
165 int32_t iMemSize = m_iChunkSize * m_iBlockSize;
166 while (true) {
167 if (index < m_iChunkCount * m_iChunkSize) {
168 pChunk = (uint8_t*)m_pData->GetAt(index / m_iChunkSize);
169 break;
170 } else {
171 pChunk = FX_Alloc(uint8_t, iMemSize);
172 if (m_iChunkCount < m_pData->GetSize()) {
173 m_pData->SetAt(m_iChunkCount, pChunk);
174 } else {
175 m_pData->Add(pChunk);
176 }
177 m_iChunkCount++;
178 }
179 }
180 }
181 ASSERT(pChunk);
182 m_iBlockCount = index + 1;
183 return pChunk + (index % m_iChunkSize) * m_iBlockSize;
184 }
GetAt(int32_t index) const185 uint8_t* CFX_BaseMassArrayImp::GetAt(int32_t index) const {
186 ASSERT(index > -1 && index < m_iBlockCount);
187 uint8_t* pChunk = (uint8_t*)m_pData->GetAt(index / m_iChunkSize);
188 ASSERT(pChunk);
189 return pChunk + (index % m_iChunkSize) * m_iBlockSize;
190 }
Append(const CFX_BaseMassArrayImp & src,int32_t iStart,int32_t iCount)191 int32_t CFX_BaseMassArrayImp::Append(const CFX_BaseMassArrayImp& src,
192 int32_t iStart,
193 int32_t iCount) {
194 ASSERT(m_iBlockSize == src.m_iBlockSize);
195 int32_t iAdded = src.m_iBlockCount;
196 ASSERT(iStart > -1 && iStart < iAdded);
197 if (iCount < 0) {
198 iCount = iAdded;
199 }
200 if (iStart + iCount > iAdded) {
201 iCount = iAdded - iStart;
202 }
203 if (iCount < 1) {
204 return m_iBlockCount;
205 }
206 int32_t iBlockCount = m_iBlockCount;
207 int32_t iTotal = m_iBlockCount + iCount;
208 AddSpaceTo(iTotal - 1);
209 Append(iBlockCount, src, iStart, iCount);
210 return m_iBlockCount;
211 }
Copy(const CFX_BaseMassArrayImp & src,int32_t iStart,int32_t iCount)212 int32_t CFX_BaseMassArrayImp::Copy(const CFX_BaseMassArrayImp& src,
213 int32_t iStart,
214 int32_t iCount) {
215 ASSERT(m_iBlockSize == src.m_iBlockSize);
216 int32_t iCopied = src.m_iBlockCount;
217 ASSERT(iStart > -1);
218 if (iStart >= iCopied) {
219 return 0;
220 }
221 RemoveAll(true);
222 if (iCount < 0) {
223 iCount = iCopied;
224 }
225 if (iStart + iCount > iCopied) {
226 iCount = iCopied - iStart;
227 }
228 if (iCount < 1) {
229 return 0;
230 }
231 if (m_iBlockCount < iCount) {
232 AddSpaceTo(iCount - 1);
233 }
234 Append(0, src, iStart, iCount);
235 return m_iBlockCount;
236 }
237
Append(int32_t iDstStart,const CFX_BaseMassArrayImp & src,int32_t iSrcStart,int32_t iSrcCount)238 void CFX_BaseMassArrayImp::Append(int32_t iDstStart,
239 const CFX_BaseMassArrayImp& src,
240 int32_t iSrcStart,
241 int32_t iSrcCount) {
242 ASSERT(iDstStart > -1);
243 ASSERT(m_iBlockSize == src.m_iBlockSize);
244 ASSERT(src.m_iBlockCount > 0);
245 ASSERT(m_iBlockCount >= iDstStart + iSrcCount);
246 ASSERT(iSrcStart > -1);
247 ASSERT(iSrcStart < src.m_iBlockCount);
248 ASSERT(iSrcCount > 0);
249 ASSERT(iSrcStart + iSrcCount <= src.m_iBlockCount);
250
251 int32_t iDstChunkIndex = iDstStart / m_iChunkSize;
252 int32_t iSrcChunkIndex = iSrcStart / src.m_iChunkSize;
253 uint8_t* pDstChunk = (uint8_t*)GetAt(iDstStart);
254 uint8_t* pSrcChunk = (uint8_t*)src.GetAt(iSrcStart);
255 int32_t iDstChunkSize = m_iChunkSize - (iDstStart % m_iChunkSize);
256 int32_t iSrcChunkSize = src.m_iChunkSize - (iSrcStart % src.m_iChunkSize);
257 int32_t iCopySize =
258 std::min(iSrcCount, std::min(iSrcChunkSize, iDstChunkSize));
259 int32_t iCopyBytes = iCopySize * m_iBlockSize;
260 while (iSrcCount > 0) {
261 ASSERT(pDstChunk && pSrcChunk);
262 FXSYS_memcpy(pDstChunk, pSrcChunk, iCopyBytes);
263 iSrcCount -= iCopySize;
264 iSrcChunkSize -= iCopySize;
265 if (iSrcChunkSize < 1) {
266 iSrcChunkSize = src.m_iChunkSize;
267 iSrcChunkIndex++;
268 pSrcChunk = (uint8_t*)src.m_pData->GetAt(iSrcChunkIndex);
269 } else {
270 pSrcChunk += iCopyBytes;
271 }
272 iDstChunkSize -= iCopySize;
273 if (iDstChunkSize < 1) {
274 iDstChunkSize = m_iChunkSize;
275 iDstChunkIndex++;
276 pDstChunk = (uint8_t*)m_pData->GetAt(iDstChunkIndex);
277 } else {
278 pDstChunk += iCopyBytes;
279 }
280 iCopySize = std::min(iSrcCount, std::min(iSrcChunkSize, iDstChunkSize));
281 iCopyBytes = iCopySize * m_iBlockSize;
282 }
283 }
RemoveLast(int32_t iCount)284 int32_t CFX_BaseMassArrayImp::RemoveLast(int32_t iCount) {
285 if (iCount < 0 || iCount >= m_iBlockCount) {
286 m_iBlockCount = 0;
287 } else {
288 m_iBlockCount -= iCount;
289 }
290 return m_iBlockCount;
291 }
RemoveAll(bool bLeaveMemory)292 void CFX_BaseMassArrayImp::RemoveAll(bool bLeaveMemory) {
293 if (bLeaveMemory) {
294 m_iBlockCount = 0;
295 return;
296 }
297 for (int32_t i = 0; i < m_iChunkCount; i++)
298 FX_Free(m_pData->GetAt(i));
299
300 m_pData->RemoveAll();
301 m_iChunkCount = 0;
302 m_iBlockCount = 0;
303 }
304
305 struct FX_BASEDISCRETEARRAYDATA {
306 int32_t iBlockSize;
307 int32_t iChunkSize;
308 int32_t iChunkCount;
309 CFX_ArrayTemplate<uint8_t*> ChunkBuffer;
310 };
311
CFX_BaseDiscreteArray(int32_t iChunkSize,int32_t iBlockSize)312 CFX_BaseDiscreteArray::CFX_BaseDiscreteArray(int32_t iChunkSize,
313 int32_t iBlockSize) {
314 ASSERT(iChunkSize > 0 && iBlockSize > 0);
315 FX_BASEDISCRETEARRAYDATA* pData = new FX_BASEDISCRETEARRAYDATA;
316 m_pData = pData;
317 pData->ChunkBuffer.SetSize(16);
318 pData->iChunkCount = 0;
319 pData->iChunkSize = iChunkSize;
320 pData->iBlockSize = iBlockSize;
321 }
~CFX_BaseDiscreteArray()322 CFX_BaseDiscreteArray::~CFX_BaseDiscreteArray() {
323 RemoveAll();
324 delete static_cast<FX_BASEDISCRETEARRAYDATA*>(m_pData);
325 }
AddSpaceTo(int32_t index)326 uint8_t* CFX_BaseDiscreteArray::AddSpaceTo(int32_t index) {
327 ASSERT(index > -1);
328 FX_BASEDISCRETEARRAYDATA* pData = (FX_BASEDISCRETEARRAYDATA*)m_pData;
329 int32_t& iChunkCount = pData->iChunkCount;
330 int32_t iChunkSize = pData->iChunkSize;
331 uint8_t* pChunk = nullptr;
332 int32_t iChunk = index / iChunkSize;
333 if (iChunk < iChunkCount) {
334 pChunk = pData->ChunkBuffer.GetAt(iChunk);
335 }
336 if (!pChunk) {
337 pChunk = FX_Alloc2D(uint8_t, iChunkSize, pData->iBlockSize);
338 FXSYS_memset(pChunk, 0, iChunkSize * pData->iBlockSize);
339 pData->ChunkBuffer.SetAtGrow(iChunk, pChunk);
340 if (iChunkCount <= iChunk) {
341 iChunkCount = iChunk + 1;
342 }
343 }
344 return pChunk + (index % iChunkSize) * pData->iBlockSize;
345 }
GetAt(int32_t index) const346 uint8_t* CFX_BaseDiscreteArray::GetAt(int32_t index) const {
347 ASSERT(index >= 0);
348 FX_BASEDISCRETEARRAYDATA* pData = (FX_BASEDISCRETEARRAYDATA*)m_pData;
349 int32_t iChunkSize = pData->iChunkSize;
350 int32_t iChunk = index / iChunkSize;
351 if (iChunk >= pData->iChunkCount)
352 return nullptr;
353
354 uint8_t* pChunk = pData->ChunkBuffer.GetAt(iChunk);
355 if (!pChunk)
356 return nullptr;
357
358 return pChunk + (index % iChunkSize) * pData->iBlockSize;
359 }
RemoveAll()360 void CFX_BaseDiscreteArray::RemoveAll() {
361 FX_BASEDISCRETEARRAYDATA* pData = (FX_BASEDISCRETEARRAYDATA*)m_pData;
362 CFX_ArrayTemplate<uint8_t*>& ChunkBuffer = pData->ChunkBuffer;
363 int32_t& iChunkCount = pData->iChunkCount;
364 for (int32_t i = 0; i < iChunkCount; i++)
365 FX_Free(ChunkBuffer.GetAt(i));
366
367 ChunkBuffer.RemoveAll();
368 iChunkCount = 0;
369 }
CFX_BaseStack(int32_t iChunkSize,int32_t iBlockSize)370 CFX_BaseStack::CFX_BaseStack(int32_t iChunkSize, int32_t iBlockSize) {
371 m_pData = new CFX_BaseMassArrayImp(iChunkSize, iBlockSize);
372 }
~CFX_BaseStack()373 CFX_BaseStack::~CFX_BaseStack() {
374 delete (CFX_BaseMassArrayImp*)m_pData;
375 }
Push()376 uint8_t* CFX_BaseStack::Push() {
377 return m_pData->AddSpace();
378 }
Pop()379 void CFX_BaseStack::Pop() {
380 int32_t& iBlockCount = m_pData->m_iBlockCount;
381 if (iBlockCount < 1) {
382 return;
383 }
384 iBlockCount--;
385 }
GetTopElement() const386 uint8_t* CFX_BaseStack::GetTopElement() const {
387 int32_t iSize = m_pData->m_iBlockCount;
388 if (iSize < 1) {
389 return nullptr;
390 }
391 return m_pData->GetAt(iSize - 1);
392 }
GetSize() const393 int32_t CFX_BaseStack::GetSize() const {
394 return m_pData->m_iBlockCount;
395 }
GetAt(int32_t index) const396 uint8_t* CFX_BaseStack::GetAt(int32_t index) const {
397 return m_pData->GetAt(index);
398 }
RemoveAll(bool bLeaveMemory)399 void CFX_BaseStack::RemoveAll(bool bLeaveMemory) {
400 m_pData->RemoveAll(bLeaveMemory);
401 }
402