1/*
2 * bitset.h -- Dynamic bitset.
3 *
4 * Copyright (c) 2001-2020, NLnet Labs. All rights reserved.
5 *
6 * See LICENSE for the license.
7 *
8 */
9#include "config.h"
10#include "bitset.h"
11
12#include <assert.h>
13#include <limits.h>
14#include <string.h>
15
16size_t nsd_bitset_size(size_t bits)
17{
18	if(bits == 0)
19		bits++;
20
21	return (bits / CHAR_BIT) + ((bits % CHAR_BIT) != 0) + sizeof(size_t);
22}
23
24void nsd_bitset_zero(struct nsd_bitset *bset)
25{
26	size_t sz;
27
28	assert(bset != NULL);
29
30	sz = nsd_bitset_size(bset->size) - sizeof(bset->size);
31	assert(sz > 0);
32	memset(bset->bits, 0, sz);
33}
34
35void nsd_bitset_init(struct nsd_bitset *bset, size_t bits)
36{
37	assert(bset != NULL);
38	if (bits == 0)
39		bits++;
40
41	bset->size = bits;
42	nsd_bitset_zero(bset);
43}
44
45int nsd_bitset_isset(struct nsd_bitset *bset, size_t bit)
46{
47	assert(bset != NULL);
48	if(bit >= bset->size)
49		return 0;
50
51	return (bset->bits[ (bit / CHAR_BIT) ] & (1 << (bit % CHAR_BIT))) != 0;
52}
53
54void nsd_bitset_set(struct nsd_bitset *bset, size_t bit)
55{
56	assert(bset != NULL);
57	assert(bset->size > bit);
58	bset->bits[ (bit / CHAR_BIT) ] |= (1 << (bit % CHAR_BIT));
59}
60
61void nsd_bitset_unset(struct nsd_bitset *bset, size_t bit)
62{
63	assert(bset != NULL);
64	assert(bset->size > bit);
65	bset->bits[ (bit / CHAR_BIT) ] &= ~(1 << (bit % CHAR_BIT));
66}
67
68void nsd_bitset_or(
69	struct nsd_bitset *destset,
70	struct nsd_bitset *srcset1,
71	struct nsd_bitset *srcset2)
72{
73	size_t i, n, size, bytes;
74	unsigned char bits;
75	unsigned int mask;
76
77	assert(destset != NULL);
78	assert(srcset1 != NULL);
79	assert(srcset2 != NULL);
80
81	size = destset->size;
82	bytes = (size / CHAR_BIT) + ((size % CHAR_BIT) != 0);
83
84	for(i = 0; i < bytes; i++) {
85		bits = 0;
86
87		n = (srcset1->size / CHAR_BIT);
88		if (n > i) {
89			bits |= srcset1->bits[i];
90		} else {
91			n += ((srcset1->size % CHAR_BIT) != 0);
92			mask = (1 << ((srcset1->size % CHAR_BIT) + 1)) - 1;
93			if (n > i) {
94				bits |= (srcset1->bits[i] & mask);
95			}
96		}
97		n = (srcset2->size / CHAR_BIT);
98		if (n > i) {
99			bits |= srcset2->bits[i];
100		} else {
101			n += ((srcset2->size % CHAR_BIT) != 0);
102			mask = (1 << ((srcset2->size % CHAR_BIT) + 1)) - 1;
103			if (n > i) {
104				bits |= (srcset2->bits[i] & mask);
105			}
106		}
107		destset->bits[i] = bits;
108	}
109}
110