1 /** Algorithms for dynamic and static bitarrays based with integral blocks.
2 *
3 * Algorithms are qualified as `package` because they should only be used by
4 * bit-array containers.
5 */
6 module nxt.bitarray_algorithm;
7
8 @safe pure nothrow @nogc:
9
10 size_t countOnes(Blocks, bool blockAlignedLength = false)(const scope auto ref Blocks blocks, size_t length) @trusted
11 if (isBlocks!Blocks)
12 {
13 alias Block = typeof(Blocks.init[0]);
14 enum bitsPerBlock = 8*Block.sizeof;
15
16 typeof(return) result = 0;
17
18 import core.bitop : popcnt;
19 const fullBlockCount = length / bitsPerBlock;
20 foreach (const block; blocks.ptr[0 .. fullBlockCount])
21 {
22 result += cast(typeof(result))popcnt(block);
23 }
24
25 // dbg("bitsPerBlock:", bitsPerBlock,
26 // " length:", length,
27 // " fullBlockCount:", fullBlockCount);,
28
29 static if (!blockAlignedLength)
30 {
31 const restBitCount = length % bitsPerBlock;
32 if (restBitCount)
33 {
34 result += cast(typeof(result))popcnt(blocks.ptr[fullBlockCount] & ((1UL << restBitCount)-1));
35 }
36
37 // dbg(" restBitCount:", restBitCount);
38 }
39
40 return typeof(return)(result);
41 }
42
43 /// Test `countOnes` with full blocks.
44 @safe pure nothrow @nogc unittest
45 {
46 alias Block = size_t;
47 enum bitsPerBlock = 8*Block.sizeof;
48
49 enum blockCount = 3;
50 Block[blockCount] x;
51 const length = 8*x.sizeof;
52 assert(countOnes(x, length) == 0);
53
54 x[0] = 1;
55 assert(countOnes(x, length) == 1);
56
57 x[0] = 1+2;
58 assert(countOnes(x, length) == 2);
59
60 x[0] = 1+2;
61 x[1] = 1+2;
62 assert(countOnes(x, length) == 4);
63
64 x[0] = 1+2;
65 x[1] = 1+2;
66 x[2] = 1+2;
67 assert(countOnes(x, length) == 6);
68 }
69
70 /// Test `countOnes` with partial blocks.
71 @safe pure nothrow @nogc unittest
72 {
73 alias Block = size_t;
74 static void test(uint blockCount)()
75 {
76 Block[blockCount] x;
77 foreach (const length; 1 .. 8*x.sizeof)
78 {
79 assert(countOnes(x, length) == 0);
80
81 x[0] |= 1UL << (length-1);
82 assert(countOnes(x, length) == 1);
83 x[0] = 0;
84 }
85 }
86 test!1();
87 test!2();
88 test!3();
89 }
90
91 /** Find index of first cleared (zero) bit or `length` if no bit cleared.
92 *
93 * Optimized for zeros-sparsity.
94 */
95 size_t indexOfFirstZero(Blocks, bool blockAlignedLength = false)(const scope auto ref Blocks blocks, size_t length)
96 if (isBlocks!Blocks)
97 {
98 static if (blockAlignedLength)
99 {
100 foreach (const blockIndex, block; blocks)
101 {
102 if (block != block.max) // optimize for zeros-sparsity
103 {
104 import core.bitop : bsf;
105 const hitIndex = blockIndex*8*block.sizeof + bsf(~block); // TODO is there a builtin for `bsf(~block)`?
106 return hitIndex < length ? hitIndex : length; // if hit beyond end miss
107 }
108 }
109 }
110 else
111 {
112 // TODO handle blocks with garbage in the rest block
113 foreach (const blockIndex, block; blocks)
114 {
115 if (block != block.max) // optimize for zeros-sparsity
116 {
117 import core.bitop : bsf;
118 const hitIndex = blockIndex*8*block.sizeof + bsf(~block); // TODO is there a builtin for `bsf(~block)`?
119 return hitIndex < length ? hitIndex : length; // if hit beyond end miss
120 }
121 }
122 }
123 return length; // miss
124 }
125
126 /** Find index of first set (one) bit or `length` if no bit cleared.
127 *
128 * Optimized for ones-sparsity.
129 */
130 size_t indexOfFirstOne(Blocks, bool blockAlignedLength = false)(const scope auto ref Blocks blocks, size_t length)
131 if (isBlocks!Blocks)
132 {
133 static if (blockAlignedLength)
134 {
135 foreach (const blockIndex, const block; blocks)
136 {
137 if (block != block.min) // optimize for ones-sparsity
138 {
139 import core.bitop : bsf;
140 const hitIndex = blockIndex*8*block.sizeof + bsf(block);
141 return hitIndex < length ? hitIndex : length; // if hit beyond end miss
142 }
143 }
144 }
145 else
146 {
147 // TODO handle blocks with garbage in the rest block
148 foreach (const blockIndex, const block; blocks)
149 {
150 if (block != block.min) // optimize for ones-sparsity
151 {
152 import core.bitop : bsf;
153 const hitIndex = blockIndex*8*block.sizeof + bsf(block);
154 return hitIndex < length ? hitIndex : length; // if hit beyond end miss
155 }
156 }
157 }
158 return length; // miss
159 }
160
161 private enum isBlocks(Blocks) = (is(typeof(Blocks.init[0]) : uint) ||
162 is(typeof(Blocks.init[0]) : ulong));