1#pragma once
2#include <assert.h>
3
4#include <stddef.h>
5#include <stdbool.h>
6
7// Bitmask operations
8// Uses uint64_t arrays as underlying store
9
10#define BM_SET(BS, I) bm_set((BS), sizeof(BS)/sizeof(uint64_t), (I))
11static inline void
12bm_set(uint64_t *bs, size_t n, size_t i) {
13    assert(i < (n * 64));
14    bs[i / 64] |= 1ul << (i % 64);
15}
16
17/*
18#define BM_CLEAR(BS, I) bm_clear((BS), sizeof(BS)/sizeof(uint64_t), (I))
19static inline void
20bm_clear(uint64_t *bs, size_t n, size_t i) {
21    assert(i < (n * 64));
22    bs[i / 64] &= ~(1ul << (i % 64));
23}
24*/
25
26#define BM_ISSET(BS, I) bm_isset((BS), sizeof(BS)/sizeof(uint64_t), (I))
27static inline bool
28bm_isset(const uint64_t *bs, size_t n, size_t i) {
29    assert(i < (n * 64));
30    return !!(bs[i / 64] & (1ul << (i % 64)));
31}
32
33#define BM_ISEMPTY(BS) bm_isempty((BS), sizeof(BS)/sizeof(uint64_t))
34static inline bool
35bm_isempty(const uint64_t *bs, size_t n) {
36    for(; n; n--) {
37        if (*bs++) return false;
38    }
39    return true;
40}
41
42#define BM_ISMATCH(BS, INVS) bm_ismatch((BS), (INVS), sizeof(BS)/sizeof(uint64_t))
43static inline bool
44bm_ismatch(const uint64_t *bs, const uint64_t *invs, size_t n) {
45    // This is an operation needed by ap_req.c,
46    // if `invs` satisfies the requirements in `bs`
47    for(; n; n--) {
48        if (*bs++ & ~*invs++) return false;
49    }
50    return true;
51}
52
53#define BM_ANDEQ(BS, XS) bm_andeq((BS), (XS), sizeof(BS)/sizeof(uint64_t))
54static inline void
55bm_andeq(uint64_t *bs, const uint64_t *xs, size_t n) {
56    for(; n; n--) {
57        *bs++ &= *xs++;
58    }
59}
60
61#define BM_POPCOUNT(BS) bm_popcount((BS), sizeof(BS)/sizeof(uint64_t))
62static inline size_t
63bm_popcount(const uint64_t *bs, size_t n) {
64    size_t c = 0;
65    static_assert(sizeof(unsigned long) == sizeof(uint64_t), "Update __builtin_popcountl to match uint64_t");
66    for(; n; n--) {
67        c += __builtin_popcountl(*bs++);
68    }
69    return c;
70}
71
72#define BM_FFZ(BS) bm_ffz((BS), sizeof(BS)/sizeof(uint64_t))
73static inline size_t 
74bm_ffz(const uint64_t *bs, size_t n) {
75    static_assert(sizeof(unsigned long) == sizeof(uint64_t), "Update __builtin_ffsl to match uint64_t");
76    for (size_t i = 0; i < n; i++) {
77        size_t z = __builtin_ffsl(~bs[i]);
78        if (z != 0) {
79            return (z - 1) + (i * 64);
80        }
81    }
82    return n * 64;
83}