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 #define LOG_TAG "SparseBitSet" 18 19 #include <stddef.h> 20 #include <string.h> 21 22 #include <log/log.h> 23 24 #include <minikin/SparseBitSet.h> 25 #include <utils/WindowsUtils.h> 26 27 namespace minikin { 28 29 const uint32_t SparseBitSet::kNotFound; 30 calcNumPages(const uint32_t * ranges,size_t nRanges)31uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) { 32 bool haveZeroPage = false; 33 uint32_t nonzeroPageEnd = 0; 34 uint32_t nPages = 0; 35 for (size_t i = 0; i < nRanges; i++) { 36 uint32_t start = ranges[i * 2]; 37 uint32_t end = ranges[i * 2 + 1]; 38 uint32_t startPage = start >> kLogValuesPerPage; 39 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 40 if (startPage >= nonzeroPageEnd) { 41 if (startPage > nonzeroPageEnd) { 42 if (!haveZeroPage) { 43 haveZeroPage = true; 44 nPages++; 45 } 46 } 47 nPages++; 48 } 49 nPages += endPage - startPage; 50 nonzeroPageEnd = endPage + 1; 51 } 52 return nPages; 53 } 54 initFromRanges(const uint32_t * ranges,size_t nRanges)55void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) { 56 if (nRanges == 0) { 57 return; 58 } 59 const uint32_t maxVal = ranges[nRanges * 2 - 1]; 60 if (maxVal >= kMaximumCapacity) { 61 return; 62 } 63 mMaxVal = maxVal; 64 mIndices.reset(new uint16_t[(mMaxVal + kPageMask) >> kLogValuesPerPage]); 65 uint32_t nPages = calcNumPages(ranges, nRanges); 66 mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]()); 67 mZeroPageIndex = noZeroPage; 68 uint32_t nonzeroPageEnd = 0; 69 uint32_t currentPage = 0; 70 for (size_t i = 0; i < nRanges; i++) { 71 uint32_t start = ranges[i * 2]; 72 uint32_t end = ranges[i * 2 + 1]; 73 LOG_ALWAYS_FATAL_IF(end < start); // make sure range size is nonnegative 74 uint32_t startPage = start >> kLogValuesPerPage; 75 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 76 if (startPage >= nonzeroPageEnd) { 77 if (startPage > nonzeroPageEnd) { 78 if (mZeroPageIndex == noZeroPage) { 79 mZeroPageIndex = (currentPage++) 80 << (kLogValuesPerPage - kLogBitsPerEl); 81 } 82 for (uint32_t j = nonzeroPageEnd; j < startPage; j++) { 83 mIndices[j] = mZeroPageIndex; 84 } 85 } 86 mIndices[startPage] = (currentPage++) 87 << (kLogValuesPerPage - kLogBitsPerEl); 88 } 89 90 size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) + 91 ((start & kPageMask) >> kLogBitsPerEl); 92 size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl; 93 if (nElements == 1) { 94 mBitmaps[index] |= (kElAllOnes >> (start & kElMask)) & 95 (kElAllOnes << ((~end + 1) & kElMask)); 96 } else { 97 mBitmaps[index] |= kElAllOnes >> (start & kElMask); 98 for (size_t j = 1; j < nElements - 1; j++) { 99 mBitmaps[index + j] = kElAllOnes; 100 } 101 mBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask); 102 } 103 for (size_t j = startPage + 1; j < endPage + 1; j++) { 104 mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 105 } 106 nonzeroPageEnd = endPage + 1; 107 } 108 } 109 110 #if defined(_WIN32) CountLeadingZeros(element x)111int SparseBitSet::CountLeadingZeros(element x) { 112 return sizeof(element) <= sizeof(int) ? clz_win(x) : clzl_win(x); 113 } 114 #else CountLeadingZeros(element x)115int SparseBitSet::CountLeadingZeros(element x) { 116 // Note: GCC / clang builtin 117 return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x); 118 } 119 #endif 120 nextSetBit(uint32_t fromIndex) const121uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const { 122 if (fromIndex >= mMaxVal) { 123 return kNotFound; 124 } 125 uint32_t fromPage = fromIndex >> kLogValuesPerPage; 126 const element* bitmap = &mBitmaps[mIndices[fromPage]]; 127 uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl; 128 element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask)); 129 if (e != 0) { 130 return (fromIndex & ~kElMask) + CountLeadingZeros(e); 131 } 132 for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); 133 j++) { 134 e = bitmap[j]; 135 if (e != 0) { 136 return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + 137 CountLeadingZeros(e); 138 } 139 } 140 uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage; 141 for (uint32_t page = fromPage + 1; page < maxPage; page++) { 142 uint16_t index = mIndices[page]; 143 if (index == mZeroPageIndex) { 144 continue; 145 } 146 bitmap = &mBitmaps[index]; 147 for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 148 e = bitmap[j]; 149 if (e != 0) { 150 return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + 151 CountLeadingZeros(e); 152 } 153 } 154 } 155 return kNotFound; 156 } 157 158 } // namespace minikin 159