pic_continuity/authority/
bitmap.rs

1/*
2 * Copyright Nitro Agility S.r.l.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17//! Removal bitmaps (Profile 0.2).
18//!
19//! For section-local index `i`: `byte_index = floor(i / 8)`,
20//! `bit_index = i mod 8`, `mask = 1 << bit_index` — least-significant-bit
21//! first. Index `0` is `h'01'`, index `7` is `h'80'`, index `8` is `h'0001'`.
22//!
23//! Canonical form: non-empty, no trailing zero bytes. A no-op bitmap is
24//! omitted together with its attenuation member, never encoded.
25
26use crate::error::RejectReason;
27
28/// A canonical removal bitmap over the section-local indexes of one
29/// Indexed Authority Map section.
30#[derive(Debug, Clone, PartialEq, Eq)]
31pub struct RemoveBitmap(Vec<u8>);
32
33impl RemoveBitmap {
34    /// Builds a canonical bitmap from a set of section-local indexes.
35    /// Returns `None` for an empty set: a no-op bitmap must be omitted.
36    pub fn from_indices(indices: &[u32]) -> Option<Self> {
37        if indices.is_empty() {
38            return None;
39        }
40        let max = *indices.iter().max().unwrap();
41        let mut bytes = vec![0u8; (max / 8) as usize + 1];
42        for &i in indices {
43            bytes[(i / 8) as usize] |= 1u8 << (i % 8);
44        }
45        Some(Self(bytes))
46    }
47
48    /// Parses wire bytes, rejecting the non-canonical forms the profile
49    /// forbids: an empty bitmap and trailing zero bytes.
50    pub fn from_bytes(bytes: &[u8]) -> Result<Self, RejectReason> {
51        if bytes.is_empty() || bytes.last() == Some(&0) {
52            return Err(RejectReason::BitmapNotCanonical);
53        }
54        Ok(Self(bytes.to_vec()))
55    }
56
57    /// The set of section-local indexes this bitmap removes.
58    pub fn indices(&self) -> Vec<u32> {
59        let mut out = Vec::new();
60        for (byte_index, byte) in self.0.iter().enumerate() {
61            for bit_index in 0..8u32 {
62                if byte & (1u8 << bit_index) != 0 {
63                    out.push(byte_index as u32 * 8 + bit_index);
64                }
65            }
66        }
67        out
68    }
69
70    /// The highest index a set bit refers to.
71    pub fn max_index(&self) -> u32 {
72        // Canonical form guarantees the last byte is non-zero.
73        *self
74            .indices()
75            .last()
76            .expect("canonical bitmap is non-empty")
77    }
78
79    /// Validates that every set bit refers to an existing predecessor index
80    /// in a section with `entry_count` entries (indexes `0..entry_count`).
81    pub fn validate_against(
82        &self,
83        entry_count: u32,
84        section: &'static str,
85    ) -> Result<(), RejectReason> {
86        if entry_count == 0 || self.max_index() >= entry_count {
87            return Err(RejectReason::BitmapIndexOutOfRange(section));
88        }
89        Ok(())
90    }
91
92    /// The exact wire bytes.
93    pub fn bytes(&self) -> &[u8] {
94        &self.0
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn spec_examples() {
104        assert_eq!(RemoveBitmap::from_indices(&[0]).unwrap().bytes(), &[0x01]);
105        assert_eq!(RemoveBitmap::from_indices(&[1]).unwrap().bytes(), &[0x02]);
106        assert_eq!(RemoveBitmap::from_indices(&[2]).unwrap().bytes(), &[0x04]);
107        assert_eq!(RemoveBitmap::from_indices(&[7]).unwrap().bytes(), &[0x80]);
108        assert_eq!(
109            RemoveBitmap::from_indices(&[8]).unwrap().bytes(),
110            &[0x00, 0x01]
111        );
112    }
113
114    #[test]
115    fn noop_is_omitted() {
116        assert!(RemoveBitmap::from_indices(&[]).is_none());
117    }
118
119    #[test]
120    fn roundtrip_indices() {
121        let bm = RemoveBitmap::from_indices(&[0, 3, 9]).unwrap();
122        assert_eq!(bm.indices(), vec![0, 3, 9]);
123        let parsed = RemoveBitmap::from_bytes(bm.bytes()).unwrap();
124        assert_eq!(parsed, bm);
125    }
126
127    #[test]
128    fn rejects_non_canonical() {
129        assert_eq!(
130            RemoveBitmap::from_bytes(&[]).unwrap_err(),
131            RejectReason::BitmapNotCanonical
132        );
133        assert_eq!(
134            RemoveBitmap::from_bytes(&[0x01, 0x00]).unwrap_err(),
135            RejectReason::BitmapNotCanonical
136        );
137        assert_eq!(
138            RemoveBitmap::from_bytes(&[0x00]).unwrap_err(),
139            RejectReason::BitmapNotCanonical
140        );
141    }
142
143    #[test]
144    fn rejects_out_of_range() {
145        let bm = RemoveBitmap::from_indices(&[1]).unwrap();
146        assert!(bm.validate_against(2, "invariants").is_ok());
147        assert_eq!(
148            bm.validate_against(1, "invariants").unwrap_err(),
149            RejectReason::BitmapIndexOutOfRange("invariants")
150        );
151    }
152}
pic_continuity/authority/bitmap.rs

pic_continuity/authority/
bitmap.rs
