nxt.bitarray_algorithm source code

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));