diff options
Diffstat (limited to 'util.h')
-rw-r--r-- | util.h | 110 |
1 files changed, 110 insertions, 0 deletions
@@ -0,0 +1,110 @@ +#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) +#define __round_mask(x, y) ((__typeof__(x))((y)-1)) +#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1) + +#define min(x, y) (((x) < (y)) ? (x) : (y)) + +#define likely(x) __builtin_expect(!!(x), 1) +#define unlikely(x) __builtin_expect(!!(x), 0) + +#ifdef VERBOSE +#define verbose(...) fprintf(stdout, __VA_ARGS__) +#else +#define verbose(...) do { } while (0) +#endif + +void set_bit(uint8_t *data, int n, int len); +void bit_sum(uint8_t *v, int n, int len); +void bit_sub(uint8_t *v, int n, int len); +void andmem(uint8_t *dst, uint8_t *src, int len); +void ormem(uint8_t *dst, uint8_t *src, int len); +int ffs_clear(uint8_t *data, int len, int byte_offset); +int test_bit(uint8_t *data, int n); +void fold_bits(uint8_t *data, int bit, int n, int len); + +/** + * fill() - Fill bits in given region + * @data: Memory region + * @start: First bit to set + * @len: Number of bits to set + * + * Equivalent to bitmap_set() in kernel. + */ +__always_inline void fill(uint8_t *data, int start, int len) +{ + uint8_t mask; + + data += start / 8; + if (likely(start % 8 || len < 8)) { + if (len + start % 8 < 8) { + mask = 0xff >> (8 - len); + *data |= mask << (start % 8); + return; + } + + *data |= 0xff << (start % 8); + len -= 8 - start % 8; + data++; + + if (len < 8) { + mask = 0xff >> (8 - len); + *data |= mask; + return; + } + } + memset(data, 0xff, len / 8); + data += len / 8; + + if (len %= 8) + *data |= 0xff >> (8 - len); +} + +/** + * ffs_and_fill() - For each set bit, set bits from selected mapping table item + * @map: Bitmap to be scanned for set bits + * @offset: Optional, initial offset, bytes + * @len: Length of bitmap in 64-bit words + * @dst: Destination bitmap + * @mt: Mapping table containing bit set specifiers + * @one: Find a single bit and return, don't fill + * + * Original implementation by Daniel Lemire, public domain. + * + * For each bit set in map, select the bucket from mapping table with index + * corresponding to the position of the bit set. Use start bit and amount of + * bits specified in bucket to fill region in dst. + * + * If __builtin_ctzl() is available, this is vastly more efficient compared to + * looking for bits using ffs64() as we can directly iterate without having to + * return the bit position and clearing it or caching it for each set bit. + * + * If __builtin_ctzl() is not available, ffs_clear() will be used instead. + * + * Return: 0 on match, bit position if 'one' is passed, -1 otherwise. + */ +__always_inline int ffs_and_fill(uint8_t *map, int offset, int len, + uint8_t *dst, union map_bucket *mt, int one) +{ + uint64_t bitset; + int k, ret = -1; + + for (k = offset / 8; k < len; k++) { + bitset = ((uint64_t *)map)[k]; + while (bitset) { + uint64_t t = bitset & -bitset; + int r = __builtin_ctzl(bitset); + + if (unlikely(one)) + return(k * 64 + r); + + ret = 0; + + fill(dst, mt[k * 64 + r].to, mt[k * 64 + r].n); + + bitset ^= t; + } + map[k] = 0; + } + + return ret; +} |