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 <cutils/log.h>
18#include <stddef.h>
19#include <string.h>
20#include <minikin/SparseBitSet.h>
21
22namespace android {
23
24const uint32_t SparseBitSet::kNotFound;
25
26void SparseBitSet::clear() {
27    mMaxVal = 0;
28    mIndices.reset();
29    mBitmaps.reset();
30}
31
32uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) {
33    bool haveZeroPage = false;
34    uint32_t nonzeroPageEnd = 0;
35    uint32_t nPages = 0;
36    for (size_t i = 0; i < nRanges; i++) {
37        uint32_t start = ranges[i * 2];
38        uint32_t end = ranges[i * 2 + 1];
39        uint32_t startPage = start >> kLogValuesPerPage;
40        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
41        if (startPage >= nonzeroPageEnd) {
42            if (startPage > nonzeroPageEnd) {
43                if (!haveZeroPage) {
44                    haveZeroPage = true;
45                    nPages++;
46                }
47            }
48            nPages++;
49        }
50        nPages += endPage - startPage;
51        nonzeroPageEnd = endPage + 1;
52    }
53    return nPages;
54}
55
56void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) {
57    if (nRanges == 0) {
58        mMaxVal = 0;
59        mIndices.reset();
60        mBitmaps.reset();
61        return;
62    }
63    mMaxVal = ranges[nRanges * 2 - 1];
64    size_t indexSize = (mMaxVal + kPageMask) >> kLogValuesPerPage;
65    mIndices.reset(new uint32_t[indexSize]);
66    uint32_t nPages = calcNumPages(ranges, nRanges);
67    mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]);
68    memset(mBitmaps.get(), 0, nPages << (kLogValuesPerPage - 3));
69    mZeroPageIndex = noZeroPage;
70    uint32_t nonzeroPageEnd = 0;
71    uint32_t currentPage = 0;
72    for (size_t i = 0; i < nRanges; i++) {
73        uint32_t start = ranges[i * 2];
74        uint32_t end = ranges[i * 2 + 1];
75        LOG_ALWAYS_FATAL_IF(end < start);  // make sure range size is nonnegative
76        uint32_t startPage = start >> kLogValuesPerPage;
77        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
78        if (startPage >= nonzeroPageEnd) {
79            if (startPage > nonzeroPageEnd) {
80                if (mZeroPageIndex == noZeroPage) {
81                    mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
82                }
83                for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
84                    mIndices[j] = mZeroPageIndex;
85                }
86            }
87            mIndices[startPage] = (currentPage++) << (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
110int SparseBitSet::CountLeadingZeros(element x) {
111    // Note: GCC / clang builtin
112    return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
113}
114
115uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
116    if (fromIndex >= mMaxVal) {
117        return kNotFound;
118    }
119    uint32_t fromPage = fromIndex >> kLogValuesPerPage;
120    const element* bitmap = &mBitmaps[mIndices[fromPage]];
121    uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
122    element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
123    if (e != 0) {
124        return (fromIndex & ~kElMask) + CountLeadingZeros(e);
125    }
126    for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
127        e = bitmap[j];
128        if (e != 0) {
129            return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
130        }
131    }
132    uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage;
133    for (uint32_t page = fromPage + 1; page < maxPage; page++) {
134        uint32_t index = mIndices[page];
135        if (index == mZeroPageIndex) {
136            continue;
137        }
138        bitmap = &mBitmaps[index];
139        for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
140            e = bitmap[j];
141            if (e != 0) {
142                return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
143            }
144        }
145    }
146    return kNotFound;
147}
148
149}  // namespace android
150