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
10CFX_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}
18CFX_BasicArray::~CFX_BasicArray() {
19  FX_Free(m_pData);
20}
21FX_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}
63FX_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}
76FX_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}
83uint8_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}
103FX_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}
116FX_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}
131const 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}
137CFX_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) {}
146void 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}
154CFX_BaseSegmentedArray::~CFX_BaseSegmentedArray() {
155  RemoveAll();
156}
157static 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}
168void 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}
177void* 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}
234void** 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}
255void* 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}
267void* 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}
293void* 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}
302void* 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}
313void 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