diff options
| -rw-r--r-- | core/Makefile.inc | 2 | ||||
| -rw-r--r-- | core/bitmap.c | 56 | ||||
| -rw-r--r-- | include/bitmap.h | 69 |
3 files changed, 126 insertions, 1 deletions
diff --git a/core/Makefile.inc b/core/Makefile.inc index 9223af1b..98bcb11c 100644 --- a/core/Makefile.inc +++ b/core/Makefile.inc @@ -8,7 +8,7 @@ CORE_OBJS += pci-opal.o fast-reboot.o device.o exceptions.o trace.o affinity.o CORE_OBJS += vpd.o hostservices.o platform.o nvram.o nvram-format.o hmi.o CORE_OBJS += console-log.o ipmi.o time-utils.o pel.o pool.o errorlog.o CORE_OBJS += timer.o i2c.o rtc.o flash.o sensor.o ipmi-opal.o -CORE_OBJS += flash-subpartition.o +CORE_OBJS += flash-subpartition.o bitmap.o ifeq ($(SKIBOOT_GCOV),1) CORE_OBJS += gcov-profiling.o diff --git a/core/bitmap.c b/core/bitmap.c new file mode 100644 index 00000000..be0700f4 --- /dev/null +++ b/core/bitmap.c @@ -0,0 +1,56 @@ +/* Copyright 2016 IBM Corp. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + * implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include "bitmap.h" + +static int __bitmap_find_bit(bitmap_t map, unsigned int start, unsigned int count, + bool value) +{ + unsigned int el, first_bit; + unsigned int end = start + count; + bitmap_elem_t e, ev; + int b; + + ev = value ? -1ul : 0; + el = BITMAP_ELEM(start); + first_bit = BITMAP_BIT(start); + + while (start < end) { + e = map[el] ^ ev; + e |= ((1ul << first_bit) - 1); + if (~e) + break; + start = (start + BITMAP_ELSZ) & ~(BITMAP_ELSZ - 1); + first_bit = 0; + el++; + } + for (b = first_bit; b < BITMAP_ELSZ && start < end; b++,start++) { + if ((e & (1ull << b)) == 0) + return start; + } + + return -1; +} + +int bitmap_find_zero_bit(bitmap_t map, unsigned int start, unsigned int count) +{ + return __bitmap_find_bit(map, start, count, false); +} + +int bitmap_find_one_bit(bitmap_t map, unsigned int start, unsigned int count) +{ + return __bitmap_find_bit(map, start, count, true); +} + diff --git a/include/bitmap.h b/include/bitmap.h new file mode 100644 index 00000000..12913ea0 --- /dev/null +++ b/include/bitmap.h @@ -0,0 +1,69 @@ +/* Copyright 2016 IBM Corp. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + * implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __BITMAP_H +#define __BITMAP_H + +#include <stdint.h> +#include <stdbool.h> + +typedef unsigned long bitmap_elem_t; +typedef bitmap_elem_t bitmap_t[]; + +#define BITMAP_ELSZ (sizeof(bitmap_elem_t) << 3) + +/* Number of elements for _n bits (rounded up) */ +#define BITMAP_ELEMS(_n) (((_n) + (BITMAP_ELSZ - 1)) / BITMAP_ELSZ) +/* Number of bytes for _n bits (rounded up) */ +#define BITMAP_BYTES(_n) (BITMAP_ELEMS(_n) * sizeof(bitmap_elem_t)) +/* Bit number within an elemnt for bit _n */ +#define BITMAP_BIT(_n) ((_n) & (BITMAP_ELSZ - 1)) +/* Corresponding mask */ +#define BITMAP_MASK(_n) (1ul << BITMAP_BIT(_n)) +/* Element number for bit _n */ +#define BITMAP_ELEM(_n) ((_n) / BITMAP_ELSZ) + +static inline void bitmap_set_bit(bitmap_t map, unsigned int bit) +{ + map[BITMAP_ELEM(bit)] |= BITMAP_MASK(bit); +} + +static inline void bitmap_clr_bit(bitmap_t map, unsigned int bit) +{ + map[BITMAP_ELEM(bit)] &= ~BITMAP_MASK(bit); +} + +static inline bool bitmap_tst_bit(bitmap_t map, unsigned int bit) +{ + return map[BITMAP_ELEM(bit)] & BITMAP_MASK(bit); +} + +extern int bitmap_find_zero_bit(bitmap_t map, unsigned int start, + unsigned int count); +extern int bitmap_find_one_bit(bitmap_t map, unsigned int start, + unsigned int count); + +#define bitmap_for_each_zero(map, size, bit) \ + for (bit = bitmap_find_zero_bit(map, 0, size); \ + bit >= 0; \ + bit = bitmap_find_zero_bit(map, bit + 1, size)) + +#define bitmap_for_each_one(map, size, bit) \ + for (bit = bitmap_find_one_bit(map, 0, size); \ + bit >= 0; \ + bit = bitmap_find_one_bit(map, bit + 1, size)) + +#endif /* __BITMAP_H */ |
