1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

pub const fn log2(mut x: usize) -> usize {
	let mut o: usize = 0;
	while x > 1 {
		x >>= 1;
		o += 1;
	}
	o
}

/// Check if x is a power of 2.
///
/// Zero is by definition not a power of 2.
pub const fn is_power_of_2(x: usize) -> bool {
	x > 0_usize && x & (x - 1) == 0
}

/// Tick up to the next higher power of 2 if
/// the provided number is not a power of 2.
pub const fn next_higher_power_of_2(k: usize) -> usize {
	if is_power_of_2(k) {
		k
	} else {
		1 << (log2(k) + 1)
	}
}

/// Tick down to the next higher power of 2 if
/// the provided number is not a power of 2.
pub const fn next_lower_power_of_2(k: usize) -> usize {
	if is_power_of_2(k) {
		k
	} else {
		1 << log2(k)
	}
}

/// Does not care about power of 2 requirements.
///
/// Covers the 1/3 case.
pub const fn recoverablity_subset_size(n_wanted_shards: usize) -> usize {
	(n_wanted_shards.saturating_sub(1) / 3) + 1
}

#[test]
fn three_f_plus_1() {
	assert_eq!(recoverablity_subset_size(0), 1); // degenerate
	assert_eq!(recoverablity_subset_size(1), 1);
	assert_eq!(recoverablity_subset_size(2), 1);
	assert_eq!(recoverablity_subset_size(3), 1);
	assert_eq!(recoverablity_subset_size(4), 2);
	assert_eq!(recoverablity_subset_size(5), 2);
	assert_eq!(recoverablity_subset_size(6), 2);
	assert_eq!(recoverablity_subset_size(8), 3);
	assert_eq!(recoverablity_subset_size(11), 4);

	assert_eq!(recoverablity_subset_size(173), 58);
	assert_eq!(recoverablity_subset_size(174), 58);
	assert_eq!(recoverablity_subset_size(175), 59);
}