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