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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
use bigint::prelude::*;
#[derive(Debug, PartialEq)]
pub struct Histogram {
pub bucket_bounds: Vec<U256>,
pub counts: Vec<u64>
}
impl Histogram {
pub fn new(corpus: &[U256], bucket_number: usize) -> Option<Histogram> {
if corpus.len() < 1 { return None; }
let corpus_end = corpus.last().expect("there is at least 1 element; qed").clone();
let corpus_start = corpus.first().expect("there is at least 1 element; qed").clone();
let bucket_size = {
let raw_bucket_size = (corpus_end - corpus_start + bucket_number.into()) / bucket_number.into();
if raw_bucket_size == 0.into() { 1.into() } else { raw_bucket_size }
};
let mut bucket_end = corpus_start + bucket_size;
let mut bucket_bounds = vec![corpus_start; bucket_number + 1];
let mut counts = vec![0; bucket_number];
let mut corpus_i = 0;
for bucket in 0..bucket_number {
while corpus.get(corpus_i).map_or(false, |v| v < &bucket_end) {
counts[bucket] += 1;
corpus_i += 1;
}
bucket_bounds[bucket + 1] = bucket_end;
bucket_end = bucket_end + bucket_size;
}
Some(Histogram { bucket_bounds: bucket_bounds, counts: counts })
}
}
#[cfg(test)]
mod tests {
use bigint::prelude::U256;
use super::Histogram;
#[test]
fn check_histogram() {
let hist = Histogram::new(slice_into![643,689,1408,2000,2296,2512,4250,4320,4842,4958,5804,6065,6098,6354,7002,7145,7845,8589,8593,8895], 5).unwrap();
let correct_bounds: Vec<U256> = vec_into![643, 2294, 3945, 5596, 7247, 8898];
assert_eq!(Histogram { bucket_bounds: correct_bounds, counts: vec![4,2,4,6,4] }, hist);
}
#[test]
fn smaller_data_range_than_bucket_range() {
assert_eq!(
Histogram::new(slice_into![1, 2, 2], 3),
Some(Histogram { bucket_bounds: vec_into![1, 2, 3, 4], counts: vec![1, 2, 0] })
);
}
#[test]
fn data_range_is_not_multiple_of_bucket_range() {
assert_eq!(
Histogram::new(slice_into![1, 2, 5], 2),
Some(Histogram { bucket_bounds: vec_into![1, 4, 7], counts: vec![2, 1] })
);
}
#[test]
fn data_range_is_multiple_of_bucket_range() {
assert_eq!(
Histogram::new(slice_into![1, 2, 6], 2),
Some(Histogram { bucket_bounds: vec_into![1, 4, 7], counts: vec![2, 1] })
);
}
#[test]
fn none_when_too_few_data() {
assert!(Histogram::new(slice_into![], 1).is_none());
}
}