1 /*
2 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020-2021 Huawei Device Co., Ltd. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this list of
9 * conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 * of conditions and the following disclaimer in the documentation and/or other materials
13 * provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without specific prior written
17 * permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include "los_bitmap.h"
33 #include "los_printf.h"
34 #include "los_toolchain.h"
35
36
37 #define OS_BITMAP_MASK 0x1FU
38 #define OS_BITMAP_WORD_MASK ~0UL
39
40 /* find first zero bit starting from LSB */
Ffz(UINTPTR x)41 STATIC INLINE UINT16 Ffz(UINTPTR x)
42 {
43 return __builtin_ffsl(~x) - 1;
44 }
45
LOS_BitmapSet(UINT32 * bitmap,UINT16 pos)46 VOID LOS_BitmapSet(UINT32 *bitmap, UINT16 pos)
47 {
48 if (bitmap == NULL) {
49 return;
50 }
51
52 *bitmap |= 1U << (pos & OS_BITMAP_MASK);
53 }
54
LOS_BitmapClr(UINT32 * bitmap,UINT16 pos)55 VOID LOS_BitmapClr(UINT32 *bitmap, UINT16 pos)
56 {
57 if (bitmap == NULL) {
58 return;
59 }
60
61 *bitmap &= ~(1U << (pos & OS_BITMAP_MASK));
62 }
63
LOS_HighBitGet(UINT32 bitmap)64 UINT16 LOS_HighBitGet(UINT32 bitmap)
65 {
66 if (bitmap == 0) {
67 return LOS_INVALID_BIT_INDEX;
68 }
69
70 return (OS_BITMAP_MASK - CLZ(bitmap));
71 }
72
LOS_LowBitGet(UINT32 bitmap)73 UINT16 LOS_LowBitGet(UINT32 bitmap)
74 {
75 if (bitmap == 0) {
76 return LOS_INVALID_BIT_INDEX;
77 }
78
79 return CTZ(bitmap);
80 }
81
LOS_BitmapSetNBits(UINTPTR * bitmap,UINT32 start,UINT32 numsSet)82 VOID LOS_BitmapSetNBits(UINTPTR *bitmap, UINT32 start, UINT32 numsSet)
83 {
84 UINTPTR *p = bitmap + BITMAP_WORD(start);
85 const UINT32 size = start + numsSet;
86 UINT16 bitsToSet = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD);
87 UINTPTR maskToSet = BITMAP_FIRST_WORD_MASK(start);
88
89 while (numsSet > bitsToSet) {
90 *p |= maskToSet;
91 numsSet -= bitsToSet;
92 bitsToSet = BITMAP_BITS_PER_WORD;
93 maskToSet = OS_BITMAP_WORD_MASK;
94 p++;
95 }
96 if (numsSet) {
97 maskToSet &= BITMAP_LAST_WORD_MASK(size);
98 *p |= maskToSet;
99 }
100 }
101
LOS_BitmapClrNBits(UINTPTR * bitmap,UINT32 start,UINT32 numsClear)102 VOID LOS_BitmapClrNBits(UINTPTR *bitmap, UINT32 start, UINT32 numsClear)
103 {
104 UINTPTR *p = bitmap + BITMAP_WORD(start);
105 const UINT32 size = start + numsClear;
106 UINT16 bitsToClear = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD);
107 UINTPTR maskToClear = BITMAP_FIRST_WORD_MASK(start);
108
109 while (numsClear >= bitsToClear) {
110 *p &= ~maskToClear;
111 numsClear -= bitsToClear;
112 bitsToClear = BITMAP_BITS_PER_WORD;
113 maskToClear = OS_BITMAP_WORD_MASK;
114 p++;
115 }
116 if (numsClear) {
117 maskToClear &= BITMAP_LAST_WORD_MASK(size);
118 *p &= ~maskToClear;
119 }
120 }
121
LOS_BitmapFfz(UINTPTR * bitmap,UINT32 numBits)122 INT32 LOS_BitmapFfz(UINTPTR *bitmap, UINT32 numBits)
123 {
124 INT32 bit, i;
125
126 for (i = 0; i < BITMAP_NUM_WORDS(numBits); i++) {
127 if (bitmap[i] == OS_BITMAP_WORD_MASK) {
128 continue;
129 }
130 bit = i * BITMAP_BITS_PER_WORD + Ffz(bitmap[i]);
131 if (bit < numBits) {
132 return bit;
133 }
134 return -1;
135 }
136 return -1;
137 }
138
139