1 /*
2 * Copyright (C) 2015 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 "BitUtils"
18 //#define LOG_NDEBUG 0
19
20 #include "BitUtils.h"
21
22 #include <utils/Log.h>
23
24 // Enables debug output for hasKeyInRange
25 #define DEBUG_KEY_RANGE 0
26
27 namespace android {
28
29 #if DEBUG_KEY_RANGE
30 static const char* bitstrings[16] = {
31 "0000", "0001", "0010", "0011",
32 "0100", "0101", "0110", "0111",
33 "1000", "1001", "1010", "1011",
34 "1100", "1101", "1110", "1111",
35 };
36 #endif
37
testBitInRange(const uint8_t arr[],size_t start,size_t end)38 bool testBitInRange(const uint8_t arr[], size_t start, size_t end) {
39 #if DEBUG_KEY_RANGE
40 ALOGD("testBitInRange(%d, %d)", start, end);
41 #endif
42 // Invalid range! This is nonsense; just say no.
43 if (end <= start) return false;
44
45 // Find byte array indices. The end is not included in the range, nor is
46 // endIndex. Round up for endIndex.
47 size_t startIndex = start / 8;
48 size_t endIndex = (end + 7) / 8;
49 #if DEBUG_KEY_RANGE
50 ALOGD("startIndex=%d, endIndex=%d", startIndex, endIndex);
51 #endif
52 for (size_t i = startIndex; i < endIndex; ++i) {
53 uint8_t bits = arr[i];
54 uint8_t mask = 0xff;
55 #if DEBUG_KEY_RANGE
56 ALOGD("block %04d: %s%s", i, bitstrings[bits >> 4], bitstrings[bits & 0x0f]);
57 #endif
58 if (bits) {
59 // Mask off bits before our start bit
60 if (i == startIndex) {
61 mask &= 0xff << (start % 8);
62 }
63 // Mask off bits after our end bit
64 if (i == endIndex - 1 && (end % 8)) {
65 mask &= 0xff >> (8 - (end % 8));
66 }
67 #if DEBUG_KEY_RANGE
68 ALOGD("mask: %s%s", bitstrings[mask >> 4], bitstrings[mask & 0x0f]);
69 #endif
70 // Test the index against the mask
71 if (bits & mask) return true;
72 }
73 }
74 return false;
75 }
76 } // namespace android
77