GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
4fa10c30a716d7fc2f67a0a385f3da565daa1237

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/paulimer/src/bits

source/paulimer/src/bits/bitvec.rs

527lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4use crate::bits::bitblock::{BitBlock, Word};
5use crate::bits::bitview::{BitView, MutableBitView};
6use crate::bits::index_set::IndexSet;
7use crate::bits::{Bitwise, BitwiseBinaryOps, Dot, IndexAssignable, OverlapWeight};
8use crate::NeutralElement;
9
10use super::standard_types::{BitIterator, BitsPerBlock};
11use super::{are_supports_equal, BorrowAsBitIterator};
12use super::{BitwiseNeutralElement, FromBits};
13
14pub const WORD_COUNT_DEFAULT: usize = 8usize;
15
16pub fn block_count(length: usize, bits_per_block: usize) -> usize {
17 let mut block_count = length / bits_per_block;
18 if !length.is_multiple_of(bits_per_block) {
19 block_count += 1;
20 }
21 block_count
22}
23
24#[must_use]
25#[derive(Eq, Clone, Debug)]
26pub struct BitVec<const WORD_COUNT: usize = WORD_COUNT_DEFAULT> {
27 pub(crate) blocks: Vec<[Word; WORD_COUNT]>,
28}
29
30impl<const WORD_COUNT: usize> std::hash::Hash for BitVec<WORD_COUNT> {
31 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
32 self.blocks.hash(state);
33 }
34}
35
36impl<const WORD_COUNT: usize> BitVec<WORD_COUNT> {
37 const fn bits_per_block() -> usize {
38 <[Word; WORD_COUNT] as BitsPerBlock>::BITS_PER_BLOCK
39 }
40
41 pub fn of_length(length: usize) -> BitVec<WORD_COUNT> {
42 Self::zeros(length)
43 }
44
45 pub fn zeros(length: usize) -> BitVec<WORD_COUNT> {
46 BitVec {
47 blocks: vec![[0; WORD_COUNT]; block_count(length, Self::bits_per_block())],
48 }
49 }
50
51 #[must_use]
52 pub fn top(&self) -> u64 {
53 self.blocks[0][0]
54 }
55
56 pub fn top_mut(&mut self) -> &mut u64 {
57 &mut self.blocks[0][0]
58 }
59
60 pub fn from_view<const WORD_COUNT_IN: usize>(
61 view: &BitView<WORD_COUNT_IN>,
62 ) -> BitVec<WORD_COUNT_IN> {
63 BitVec::<WORD_COUNT_IN> {
64 blocks: view.blocks.to_vec(),
65 }
66 }
67
68 pub fn from_view_mut<const WORD_COUNT_IN: usize>(
69 view: &MutableBitView<WORD_COUNT_IN>,
70 ) -> BitVec<WORD_COUNT_IN> {
71 BitVec::<WORD_COUNT_IN> {
72 blocks: view.blocks.to_vec(),
73 }
74 }
75
76 pub fn selected_from<'life, Iterable, const WORD_COUNT_IN: usize>(
77 view: &'life BitView<WORD_COUNT_IN>,
78 support: Iterable,
79 ) -> BitVec<WORD_COUNT_IN>
80 where
81 Iterable: IntoIterator<Item = &'life usize>,
82 Iterable::IntoIter: ExactSizeIterator<Item = &'life usize>,
83 {
84 let support_iterator = support.into_iter();
85 let mut bits = BitVec::<WORD_COUNT_IN>::of_length(support_iterator.len());
86 for index in support_iterator {
87 bits.assign_index(*index, view.index(*index));
88 }
89 bits
90 }
91
92 #[must_use]
93 pub fn as_view(&self) -> BitView<'_, WORD_COUNT> {
94 BitView {
95 blocks: &self.blocks,
96 }
97 }
98
99 pub fn as_view_mut(&mut self) -> MutableBitView<'_, WORD_COUNT> {
100 MutableBitView {
101 blocks: &mut self.blocks,
102 }
103 }
104
105 #[must_use]
106 pub fn len(&self) -> usize {
107 self.blocks.len() * <[Word; WORD_COUNT] as BitsPerBlock>::BITS_PER_BLOCK
108 }
109
110 #[must_use]
111 pub fn is_empty(&self) -> bool {
112 self.blocks.len() == 0
113 }
114}
115
116// Bit traits : Unary
117
118macro_rules! blocks_neutral_element_body {
119 () => {
120 type NeutralElementType = BitVec<WORD_COUNT>;
121
122 fn neutral_element(&self) -> <Self as NeutralElement>::NeutralElementType {
123 BitVec::<WORD_COUNT> {
124 blocks: self.blocks.neutral_element(),
125 }
126 }
127
128 fn default_size_neutral_element() -> <Self as NeutralElement>::NeutralElementType {
129 BitVec::<WORD_COUNT>::zeros(0)
130 }
131
132 fn neutral_element_of_size(size: usize) -> <Self as NeutralElement>::NeutralElementType {
133 BitVec::<WORD_COUNT>::zeros(size)
134 }
135 };
136}
137
138impl<const WORD_COUNT: usize> NeutralElement for BitVec<WORD_COUNT> {
139 blocks_neutral_element_body!();
140}
141
142impl<const WORD_COUNT: usize> NeutralElement for MutableBitView<'_, WORD_COUNT> {
143 blocks_neutral_element_body!();
144}
145
146impl<const WORD_COUNT: usize> NeutralElement for BitView<'_, WORD_COUNT> {
147 blocks_neutral_element_body!();
148}
149
150impl<const WORD_COUNT: usize> BitwiseNeutralElement for BitVec<WORD_COUNT> {}
151impl<const WORD_COUNT: usize> BitwiseNeutralElement for MutableBitView<'_, WORD_COUNT> {}
152impl<const WORD_COUNT: usize> BitwiseNeutralElement for BitView<'_, WORD_COUNT> {}
153
154macro_rules! blocks_bitwise_body {
155 () => {
156 fn index(&self, index: usize) -> bool {
157 self.blocks.index(index)
158 }
159
160 fn support(&self) -> impl sorted_iter::SortedIterator<Item = usize> {
161 self.blocks.support()
162 }
163
164 fn weight(&self) -> usize {
165 self.blocks.weight()
166 }
167
168 fn parity(&self) -> bool {
169 self.blocks.parity()
170 }
171
172 fn is_zero(&self) -> bool {
173 self.blocks.is_zero()
174 }
175 };
176}
177
178impl<const WORD_COUNT: usize> Bitwise for BitVec<WORD_COUNT> {
179 blocks_bitwise_body!();
180}
181
182impl<const WORD_COUNT: usize> Bitwise for MutableBitView<'_, WORD_COUNT> {
183 blocks_bitwise_body!();
184}
185
186impl<const WORD_COUNT: usize> Bitwise for BitView<'_, WORD_COUNT> {
187 blocks_bitwise_body!();
188}
189
190impl<const WORD_COUNT: usize> Bitwise for BitBlock<WORD_COUNT> {
191 blocks_bitwise_body!();
192}
193
194impl<const WORD_COUNT: usize> Bitwise for &BitBlock<WORD_COUNT> {
195 blocks_bitwise_body!();
196}
197
198impl<const WORD_COUNT: usize> Bitwise for &mut BitBlock<WORD_COUNT> {
199 blocks_bitwise_body!();
200}
201
202macro_rules! blocks_index_assignable_body {
203 () => {
204 fn assign_index(&mut self, index: usize, to: bool) {
205 self.blocks.assign_index(index, to)
206 }
207
208 fn negate_index(&mut self, index: usize) {
209 self.blocks.negate_index(index)
210 }
211
212 fn clear_bits(&mut self) {
213 self.blocks.clear_bits()
214 }
215 };
216}
217
218impl<const WORD_COUNT: usize> IndexAssignable for BitVec<WORD_COUNT> {
219 blocks_index_assignable_body!();
220}
221
222impl<const WORD_COUNT: usize> IndexAssignable for MutableBitView<'_, WORD_COUNT> {
223 blocks_index_assignable_body!();
224}
225
226impl<const WORD_COUNT: usize> IndexAssignable for &mut BitBlock<WORD_COUNT> {
227 blocks_index_assignable_body!();
228}
229
230impl<const WORD_COUNT: usize> IndexAssignable for BitBlock<WORD_COUNT> {
231 blocks_index_assignable_body!();
232}
233
234macro_rules! borrow_as_bit_iterator_body {
235 () => {
236 type BitIterator<'life1>
237 = BitIterator<'life1>
238 where
239 Self: 'life1;
240 fn borrow_as_bit_iterator(&self) -> Self::BitIterator<'_> {
241 self.blocks.borrow_as_bit_iterator()
242 }
243 };
244}
245
246impl<const WORD_COUNT: usize> BorrowAsBitIterator for BitVec<WORD_COUNT> {
247 borrow_as_bit_iterator_body!();
248}
249
250impl<const WORD_COUNT: usize> BorrowAsBitIterator for BitBlock<WORD_COUNT> {
251 borrow_as_bit_iterator_body!();
252}
253
254impl<const WORD_COUNT: usize> BorrowAsBitIterator for &BitBlock<WORD_COUNT> {
255 borrow_as_bit_iterator_body!();
256}
257
258impl<const WORD_COUNT: usize> BorrowAsBitIterator for &mut BitBlock<WORD_COUNT> {
259 borrow_as_bit_iterator_body!();
260}
261
262impl<const WORD_COUNT: usize> BorrowAsBitIterator for MutableBitView<'_, WORD_COUNT> {
263 borrow_as_bit_iterator_body!();
264}
265
266impl<const WORD_COUNT: usize> BorrowAsBitIterator for BitView<'_, WORD_COUNT> {
267 borrow_as_bit_iterator_body!();
268}
269
270// Bit traits : Binary
271
272macro_rules! blocks_bitwise_binary_ops_body {
273 ($other_type:ty) => {
274 fn assign(&mut self, other: &$other_type) {
275 self.blocks.assign(&other.blocks)
276 }
277
278 fn bitxor_assign(&mut self, other: &$other_type) {
279 self.blocks.bitxor_assign(&other.blocks)
280 }
281
282 fn bitand_assign(&mut self, other: &$other_type) {
283 self.blocks.bitand_assign(&other.blocks)
284 }
285 };
286}
287
288macro_rules! blocks_bitwise_binary_ops_refs {
289 ($other_type:ty,$vec_type:ty) => {
290 impl<const WORD_COUNT: usize> BitwiseBinaryOps<$other_type> for $vec_type {
291 blocks_bitwise_binary_ops_body!($other_type);
292 }
293 };
294}
295
296macro_rules! blocks_bitwise_binary_ops {
297 ($vec_type:ty) => {
298 blocks_bitwise_binary_ops_refs!(BitVec<WORD_COUNT>, $vec_type);
299 blocks_bitwise_binary_ops_refs!(BitView<'_, WORD_COUNT>, $vec_type);
300 blocks_bitwise_binary_ops_refs!(MutableBitView<'_, WORD_COUNT>, $vec_type);
301 };
302}
303
304blocks_bitwise_binary_ops!(BitVec<WORD_COUNT>);
305blocks_bitwise_binary_ops!(MutableBitView<'_, WORD_COUNT>);
306
307macro_rules! bitblock_bitwise_binary_ops {
308 ($bitblock_type:ty) => {
309 blocks_bitwise_binary_ops_refs!(BitBlock<WORD_COUNT>, $bitblock_type);
310 blocks_bitwise_binary_ops_refs!(&BitBlock<WORD_COUNT>, $bitblock_type);
311 blocks_bitwise_binary_ops_refs!(&mut BitBlock<WORD_COUNT>, $bitblock_type);
312 };
313}
314
315bitblock_bitwise_binary_ops!(BitBlock<WORD_COUNT>);
316bitblock_bitwise_binary_ops!(&mut BitBlock<WORD_COUNT>);
317
318macro_rules! blocks_dot_body {
319 ($other_type:ty) => {
320 fn dot(&self, other: &$other_type) -> bool {
321 self.blocks.dot(&other.blocks)
322 }
323 };
324}
325
326macro_rules! blocks_overlap_weight_body {
327 ($other_type:ty) => {
328 fn and_weight(&self, other: &$other_type) -> usize {
329 self.blocks.and_weight(&other.blocks)
330 }
331
332 fn or_weight(&self, other: &$other_type) -> usize {
333 self.blocks.or_weight(&other.blocks)
334 }
335 };
336}
337
338macro_rules! bitblock_dot_refs {
339 ($other_type:ty,$bitblock_type:ty) => {
340 impl<const WORD_COUNT: usize> Dot<$other_type> for $bitblock_type {
341 blocks_dot_body!($other_type);
342 }
343
344 impl<const WORD_COUNT: usize> OverlapWeight<$other_type> for $bitblock_type {
345 blocks_overlap_weight_body!($other_type);
346 }
347 };
348}
349
350macro_rules! blocks_dot {
351 ($vec_type:ty) => {
352 bitblock_dot_refs!(BitVec<WORD_COUNT>, $vec_type);
353 bitblock_dot_refs!(BitView<'_, WORD_COUNT>, $vec_type);
354 bitblock_dot_refs!(MutableBitView<'_, WORD_COUNT>, $vec_type);
355 };
356}
357
358blocks_dot!(BitVec<WORD_COUNT>);
359blocks_dot!(BitView<'_, WORD_COUNT>);
360blocks_dot!(MutableBitView<'_, WORD_COUNT>);
361
362macro_rules! bitblock_dot {
363 ($bitblock_type:ty) => {
364 bitblock_dot_refs!(BitBlock<WORD_COUNT>, $bitblock_type);
365 bitblock_dot_refs!(&BitBlock<WORD_COUNT>, $bitblock_type);
366 bitblock_dot_refs!(&mut BitBlock<WORD_COUNT>, $bitblock_type);
367 };
368}
369
370bitblock_dot!(BitBlock<WORD_COUNT>);
371bitblock_dot!(&BitBlock<WORD_COUNT>);
372bitblock_dot!(&mut BitBlock<WORD_COUNT>);
373
374// Standard traits
375
376impl<const WORD_COUNT: usize> FromIterator<bool> for BitVec<WORD_COUNT> {
377 fn from_iter<Iterator: IntoIterator<Item = bool>>(iterator: Iterator) -> Self {
378 let mut blocks = vec![];
379 let mut iterator = iterator.into_iter();
380
381 // Note: once `Iterator::array_chunks` is stabilized, we can use that instead.
382 loop {
383 let mut block = [0 as Word; WORD_COUNT];
384 for index in 0..Self::bits_per_block() {
385 match iterator.next() {
386 Some(bit) => block.assign_index(index, bit),
387 None if index == 0 => return BitVec { blocks },
388 None => {
389 blocks.push(block);
390 return BitVec { blocks };
391 }
392 }
393 }
394 blocks.push(block);
395 }
396 }
397}
398
399macro_rules! blocks_partial_eq_body {
400 ($other_type:ty) => {
401 fn eq(&self, other: &$other_type) -> bool {
402 self.blocks == other.blocks
403 }
404 };
405}
406
407macro_rules! blocks_partial_eq_body_bool {
408 ($other_type:ty) => {
409 fn eq(&self, other: &$other_type) -> bool {
410 are_supports_equal(self, other)
411 }
412 };
413}
414
415macro_rules! blocks_partial_eq_vec_bool {
416 ($vec_bool:ty,$vec_type:ty) => {
417 impl<const WORD_COUNT: usize> PartialEq<$vec_bool> for $vec_type {
418 blocks_partial_eq_body_bool!($vec_bool);
419 }
420
421 impl<const WORD_COUNT: usize> PartialEq<$vec_type> for $vec_bool {
422 blocks_partial_eq_body_bool!($vec_type);
423 }
424 };
425}
426
427macro_rules! blocks_partial_eq {
428 ($vec_type:ty) => {
429 impl<const WORD_COUNT: usize> PartialEq<BitVec<WORD_COUNT>> for $vec_type {
430 blocks_partial_eq_body!(BitVec<WORD_COUNT>);
431 }
432
433 impl<const WORD_COUNT: usize> PartialEq<MutableBitView<'_, WORD_COUNT>> for $vec_type {
434 blocks_partial_eq_body!(MutableBitView<'_, WORD_COUNT>);
435 }
436
437 impl<const WORD_COUNT: usize> PartialEq<BitView<'_, WORD_COUNT>> for $vec_type {
438 blocks_partial_eq_body!(BitView<'_, WORD_COUNT>);
439 }
440
441 impl<const WORD_COUNT: usize> PartialEq<IndexSet> for $vec_type {
442 blocks_partial_eq_body_bool!(IndexSet);
443 }
444
445 blocks_partial_eq_vec_bool!(Vec<bool>, $vec_type);
446 blocks_partial_eq_vec_bool!(&[bool], $vec_type);
447 blocks_partial_eq_vec_bool!(&mut [bool], $vec_type);
448 };
449}
450
451blocks_partial_eq!(BitVec<WORD_COUNT>);
452blocks_partial_eq!(MutableBitView<'_, WORD_COUNT>);
453blocks_partial_eq!(BitView<'_, WORD_COUNT>);
454
455macro_rules! bitblocks_partial_eq {
456 ($vec_type:ty) => {
457 impl<const WORD_COUNT: usize> PartialEq<IndexSet> for $vec_type {
458 blocks_partial_eq_body_bool!(IndexSet);
459 }
460
461 blocks_partial_eq_vec_bool!(Vec<bool>, $vec_type);
462 blocks_partial_eq_vec_bool!(&[bool], $vec_type);
463 blocks_partial_eq_vec_bool!(&mut [bool], $vec_type);
464 };
465}
466
467bitblocks_partial_eq!(BitBlock<WORD_COUNT>);
468bitblocks_partial_eq!(&mut BitBlock<WORD_COUNT>);
469bitblocks_partial_eq!(&BitBlock<WORD_COUNT>);
470
471macro_rules! blocks_into_iterator_body {
472 () => {
473 type Item = bool;
474 type IntoIter = BitIterator<'life>;
475 fn into_iter(self) -> Self::IntoIter {
476 self.blocks.borrow_as_bit_iterator()
477 }
478 };
479}
480
481impl<'life, const WORD_COUNT: usize> IntoIterator for &'life BitVec<WORD_COUNT> {
482 blocks_into_iterator_body!();
483}
484
485impl<'life, const WORD_COUNT: usize> IntoIterator for &'life MutableBitView<'_, WORD_COUNT> {
486 blocks_into_iterator_body!();
487}
488
489impl<'life, const WORD_COUNT: usize> IntoIterator for &'life BitView<'_, WORD_COUNT> {
490 blocks_into_iterator_body!();
491}
492
493impl<const WORD_COUNT: usize> BitVec<WORD_COUNT> {
494 #[must_use]
495 pub fn iter(&self) -> BitIterator<'_> {
496 <&Self as IntoIterator>::into_iter(self)
497 }
498}
499
500impl<const WORD_COUNT: usize> BitView<'_, WORD_COUNT> {
501 #[must_use]
502 pub fn iter(&self) -> BitIterator<'_> {
503 <&Self as IntoIterator>::into_iter(self)
504 }
505}
506
507impl<const WORD_COUNT: usize> MutableBitView<'_, WORD_COUNT> {
508 #[must_use]
509 pub fn iter(&self) -> BitIterator<'_> {
510 <&Self as IntoIterator>::into_iter(self)
511 }
512}
513
514impl<
515 Other: BorrowAsBitIterator + Bitwise,
516 T: NeutralElement<NeutralElementType = Self> + IndexAssignable + BorrowAsBitIterator,
517 > FromBits<Other> for T
518{
519 fn from_bits(other: &Other) -> Self {
520 let iter = other.borrow_as_bit_iterator();
521 let mut res = Self::neutral_element_of_size(iter.len());
522 for index in other.support() {
523 res.assign_index(index, true);
524 }
525 res
526 }
527}
528