rust-hll 0.1.2

A Rust implementation of HLL that is compatible with the Aggregate Knowledge HLL Storage Spec
Documentation 
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

use crate::{
    Registers, Settings, Storage,
    explicit::ExplicitStorage,
    sparse::SparseRegisters,
    utils::{calc_position, divide_by_8_round_up, read_u8_bits, write_u8_bits},
};

#[derive(Debug, Clone, PartialEq)]
pub struct DenseRegisters {
    pub settings: Settings,
    buf: Vec<u8>,
}

impl DenseRegisters {
    pub fn with_settings(settings: &Settings) -> Self {
        let cap = divide_by_8_round_up((1 << settings.log_2m) * settings.reg_width);

        Self {
            settings: *settings,
            buf: vec![0; cap as usize],
        }
    }

    pub fn clone_with_settings(&self, settings: &Settings) -> Self {
        Self {
            settings: *settings,
            buf: self.buf.clone(),
        }
    }

    pub fn union_explicit(&mut self, explicit_storage: &ExplicitStorage) {
        for i in explicit_storage.iter() {
            self.set(i);
        }
    }

    pub fn union_sparse(&mut self, sparse_storage: &SparseRegisters) {
        for (reg_num, value) in sparse_storage.iter() {
            self.set_if_greater(*reg_num, *value);
        }
    }

    pub fn union_dense(&mut self, other: &Self) {
        for (reg_num, value) in other.iter() {
            self.set_if_greater(reg_num, value);
        }
    }

    // get extracts a single register value.  It is provided to enable union-ing two
    // dense storage instance with different Hll settings.
    pub fn get(&self, reg_num: u32) -> u8 {
        let (idx, pos) = calc_position(reg_num, self.settings.reg_width as u8);
        read_u8_bits(&self.buf, idx, pos, self.settings.reg_width as u8)
    }

    pub fn set_reg(&mut self, reg_num: u32, value: u8) {
        let (idx, pos) = calc_position(reg_num, self.settings.reg_width as u8);
        write_u8_bits(
            &mut self.buf,
            idx,
            pos,
            value,
            self.settings.reg_width as u8,
        );
    }

    pub fn iter(&self) -> RegisterIter<'_> {
        RegisterIter {
            reg_num: 0,
            reg_cnt: 1 << self.settings.log_2m,
            registers: self,
        }
    }
}

impl Registers for DenseRegisters {
    fn set_if_greater(&mut self, reg_num: u32, value: u8) {
        let (idx, pos) = calc_position(reg_num, self.settings.reg_width as u8);
        let register = read_u8_bits(&self.buf, idx, pos, self.settings.reg_width as u8);

        if value > register {
            write_u8_bits(
                &mut self.buf,
                idx,
                pos,
                value,
                self.settings.reg_width as u8,
            );
        }
    }

    fn indicator(&self) -> (f64, u32) {
        let mut sum: f64 = 0.0;
        let mut number_of_zeros = 0;
        let num_reg = 1 << self.settings.log_2m;

        for i in 0..num_reg {
            let value = self.get(i);

            sum += 1.0 / ((1_u64 << value) as f64);
            if value == 0 {
                number_of_zeros += 1;
            }
        }

        (sum, number_of_zeros)
    }

    fn log_2m(&self) -> u32 {
        self.settings.log_2m
    }

    fn pw_max_mask(&self) -> u64 {
        self.settings.pw_max_mask
    }

    fn m_bits_mask(&self) -> u64 {
        self.settings.m_bits_mask
    }
}

impl Storage for DenseRegisters {
    fn bytes_size(&self) -> usize {
        self.buf.len()
    }

    fn to_bytes(&self, buf: &mut [u8]) {
        assert!(buf.len() >= self.buf.len());
        buf[..self.buf.len()].copy_from_slice(&self.buf);
    }

    fn from_bytes(settings: &Settings, buf: &[u8]) -> Self {
        let mut res = Self::with_settings(settings);
        assert!(res.buf.len() >= buf.len());
        res.buf[..buf.len()].copy_from_slice(buf);

        res
    }

    fn clear(&mut self) {
        for i in 0..self.buf.len() {
            self.buf[i] = 0;
        }
    }
}

pub struct RegisterIter<'a> {
    reg_num: u32,
    reg_cnt: u32,
    registers: &'a DenseRegisters,
}

impl Iterator for RegisterIter<'_> {
    type Item = (u32, u8);

    fn next(&mut self) -> Option<Self::Item> {
        if self.reg_num < self.reg_cnt {
            let value = self.registers.get(self.reg_num);
            let res = Some((self.reg_num, value));
            self.reg_num += 1;

            return res;
        }

        None
    }
}