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