19cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien/*
29cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * Copyright (C) 2012 The Android Open Source Project
39cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien *
49cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * Licensed under the Apache License, Version 2.0 (the "License");
59cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * you may not use this file except in compliance with the License.
69cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * You may obtain a copy of the License at
79cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien *
89cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien *      http://www.apache.org/licenses/LICENSE-2.0
99cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien *
109cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * Unless required by applicable law or agreed to in writing, software
119cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * distributed under the License is distributed on an "AS IS" BASIS,
129cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
139cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * See the License for the specific language governing permissions and
149cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * limitations under the License.
159cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien */
169cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
1773abbd59344770601991248cc56846cd199812b8Raph Levien#include <cutils/log.h>
189cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <stddef.h>
199cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <string.h>
209cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <minikin/SparseBitSet.h>
219cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
229cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Leviennamespace android {
239cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
249cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienconst uint32_t SparseBitSet::kNotFound;
259cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
269cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienvoid SparseBitSet::clear() {
279cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    mMaxVal = 0;
289cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    mIndices.reset();
299cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    mBitmaps.reset();
309cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien}
319cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
329cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienuint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) {
339cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    bool haveZeroPage = false;
349cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t nonzeroPageEnd = 0;
359cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t nPages = 0;
369cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    for (size_t i = 0; i < nRanges; i++) {
379cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t start = ranges[i * 2];
389cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t end = ranges[i * 2 + 1];
399cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t startPage = start >> kLogValuesPerPage;
409cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
419cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        if (startPage >= nonzeroPageEnd) {
429cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            if (startPage > nonzeroPageEnd) {
439cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                if (!haveZeroPage) {
449cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                    haveZeroPage = true;
459cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                    nPages++;
469cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                }
479cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            }
489cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            nPages++;
499cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        }
509cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        nPages += endPage - startPage;
519cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        nonzeroPageEnd = endPage + 1;
529cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    }
539cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    return nPages;
549cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien}
559cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
569cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienvoid SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) {
579cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    if (nRanges == 0) {
589cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        mMaxVal = 0;
599cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        mIndices.reset();
609cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        mBitmaps.reset();
619cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        return;
629cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    }
639cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    mMaxVal = ranges[nRanges * 2 - 1];
649cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    size_t indexSize = (mMaxVal + kPageMask) >> kLogValuesPerPage;
659cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    mIndices.reset(new uint32_t[indexSize]);
669cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t nPages = calcNumPages(ranges, nRanges);
679cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]);
689cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    memset(mBitmaps.get(), 0, nPages << (kLogValuesPerPage - 3));
699cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    mZeroPageIndex = noZeroPage;
709cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t nonzeroPageEnd = 0;
719cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t currentPage = 0;
729cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    for (size_t i = 0; i < nRanges; i++) {
739cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t start = ranges[i * 2];
749cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t end = ranges[i * 2 + 1];
7573abbd59344770601991248cc56846cd199812b8Raph Levien        LOG_ALWAYS_FATAL_IF(end < start);  // make sure range size is nonnegative
769cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t startPage = start >> kLogValuesPerPage;
779cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
789cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        if (startPage >= nonzeroPageEnd) {
799cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            if (startPage > nonzeroPageEnd) {
809cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                if (mZeroPageIndex == noZeroPage) {
819cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                    mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
829cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                }
839cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
849cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                    mIndices[j] = mZeroPageIndex;
859cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                }
869cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            }
879cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            mIndices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
889cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        }
899cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
909cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) +
919cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            ((start & kPageMask) >> kLogBitsPerEl);
929cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl;
939cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        if (nElements == 1) {
949cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            mBitmaps[index] |= (kElAllOnes >> (start & kElMask)) &
951bbe03d215c9452bc9917111e63f19160cc5f56aDan Austin                (kElAllOnes << ((~end + 1) & kElMask));
969cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        } else {
979cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            mBitmaps[index] |= kElAllOnes >> (start & kElMask);
989cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            for (size_t j = 1; j < nElements - 1; j++) {
999cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                mBitmaps[index + j] = kElAllOnes;
1009cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            }
1011bbe03d215c9452bc9917111e63f19160cc5f56aDan Austin            mBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask);
1029cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        }
1039cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        for (size_t j = startPage + 1; j < endPage + 1; j++) {
1049cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
1059cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        }
1069cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        nonzeroPageEnd = endPage + 1;
1079cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    }
1089cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien}
1099cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
1109cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienint SparseBitSet::CountLeadingZeros(element x) {
111329ae0639e332fa0ca85049f738776083b6dbafcBehdad Esfahbod    // Note: GCC / clang builtin
112329ae0639e332fa0ca85049f738776083b6dbafcBehdad Esfahbod    return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
1139cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien}
1149cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
1159cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienuint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
1169cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    if (fromIndex >= mMaxVal) {
1179cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        return kNotFound;
1189cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    }
1199cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t fromPage = fromIndex >> kLogValuesPerPage;
1209cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    const element* bitmap = &mBitmaps[mIndices[fromPage]];
1219cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
1229cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
1239cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    if (e != 0) {
1249cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        return (fromIndex & ~kElMask) + CountLeadingZeros(e);
1259cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    }
1269cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
1279cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        e = bitmap[j];
1289cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        if (e != 0) {
1299cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
1309cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        }
1319cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    }
1329cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage;
1339cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    for (uint32_t page = fromPage + 1; page < maxPage; page++) {
1349cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        uint32_t index = mIndices[page];
1359cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        if (index == mZeroPageIndex) {
1369cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            continue;
1379cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        }
1389cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        bitmap = &mBitmaps[index];
1399cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
1409cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            e = bitmap[j];
1419cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            if (e != 0) {
1429cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien                return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
1439cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien            }
1449cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien        }
1459cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    }
1469cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien    return kNotFound;
1479cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien}
1489cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien
1499cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien}  // namespace android
150