1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "minikin/SparseBitSet.h" 18 19 #include "MinikinInternal.h" 20 21 namespace minikin { 22 23 const uint32_t SparseBitSet::kNotFound; 24 25 uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) { 26 bool haveZeroPage = false; 27 uint32_t nonzeroPageEnd = 0; 28 uint32_t nPages = 0; 29 for (size_t i = 0; i < nRanges; i++) { 30 uint32_t start = ranges[i * 2]; 31 uint32_t end = ranges[i * 2 + 1]; 32 uint32_t startPage = start >> kLogValuesPerPage; 33 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 34 if (startPage >= nonzeroPageEnd) { 35 if (startPage > nonzeroPageEnd) { 36 if (!haveZeroPage) { 37 haveZeroPage = true; 38 nPages++; 39 } 40 } 41 nPages++; 42 } 43 nPages += endPage - startPage; 44 nonzeroPageEnd = endPage + 1; 45 } 46 return nPages; 47 } 48 49 void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) { 50 if (nRanges == 0) { 51 return; 52 } 53 const uint32_t maxVal = ranges[nRanges * 2 - 1]; 54 if (maxVal >= kMaximumCapacity) { 55 return; 56 } 57 mMaxVal = maxVal; 58 mIndices.reset(new uint16_t[(mMaxVal + kPageMask) >> kLogValuesPerPage]); 59 uint32_t nPages = calcNumPages(ranges, nRanges); 60 mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]()); 61 mZeroPageIndex = noZeroPage; 62 uint32_t nonzeroPageEnd = 0; 63 uint32_t currentPage = 0; 64 for (size_t i = 0; i < nRanges; i++) { 65 uint32_t start = ranges[i * 2]; 66 uint32_t end = ranges[i * 2 + 1]; 67 MINIKIN_ASSERT(start <= end, "Range size must be nonnegative"); 68 uint32_t startPage = start >> kLogValuesPerPage; 69 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 70 if (startPage >= nonzeroPageEnd) { 71 if (startPage > nonzeroPageEnd) { 72 if (mZeroPageIndex == noZeroPage) { 73 mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 74 } 75 for (uint32_t j = nonzeroPageEnd; j < startPage; j++) { 76 mIndices[j] = mZeroPageIndex; 77 } 78 } 79 mIndices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 80 } 81 82 size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) + 83 ((start & kPageMask) >> kLogBitsPerEl); 84 size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl; 85 if (nElements == 1) { 86 mBitmaps[index] |= 87 (kElAllOnes >> (start & kElMask)) & (kElAllOnes << ((~end + 1) & kElMask)); 88 } else { 89 mBitmaps[index] |= kElAllOnes >> (start & kElMask); 90 for (size_t j = 1; j < nElements - 1; j++) { 91 mBitmaps[index + j] = kElAllOnes; 92 } 93 mBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask); 94 } 95 for (size_t j = startPage + 1; j < endPage + 1; j++) { 96 mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 97 } 98 nonzeroPageEnd = endPage + 1; 99 } 100 } 101 102 int SparseBitSet::CountLeadingZeros(element x) { 103 // Note: GCC / clang builtin 104 return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x); 105 } 106 107 uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const { 108 if (fromIndex >= mMaxVal) { 109 return kNotFound; 110 } 111 uint32_t fromPage = fromIndex >> kLogValuesPerPage; 112 const element* bitmap = &mBitmaps[mIndices[fromPage]]; 113 uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl; 114 element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask)); 115 if (e != 0) { 116 return (fromIndex & ~kElMask) + CountLeadingZeros(e); 117 } 118 for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 119 e = bitmap[j]; 120 if (e != 0) { 121 return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 122 } 123 } 124 uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage; 125 for (uint32_t page = fromPage + 1; page < maxPage; page++) { 126 uint16_t index = mIndices[page]; 127 if (index == mZeroPageIndex) { 128 continue; 129 } 130 bitmap = &mBitmaps[index]; 131 for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 132 e = bitmap[j]; 133 if (e != 0) { 134 return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 135 } 136 } 137 } 138 return kNotFound; 139 } 140 141 } // namespace minikin 142
