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 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363
//!
//! # Cyphal acceptance filter configuration
//!
//! This library implements the automatic hardware acceptance filter configuration described
//! in section 4.2.4.4 of the Cyphal specification.
//!
//! To reduce the amount of CPU time spent processing messages, a Cyphal device can use hardware
//! acceptance filters to ignore CAN messages that it is not interested in. When the application
//! is interested in more message IDs than the number of filters that the hardware supports,
//! this library can find a quasi-optimal set of filters that accepts all interesting message
//! IDs and the minimum number of non-interesting message IDs.
//!
//! ## Basic operation
//!
//! 1. Find the set of message IDs the application is interested in, based on the topics, requests,
//! and responses it wants to receive
//! 2. For each interesting message ID, create a filter that matches exactly that ID. Optimize those
//! filters down to the number of filters the hardware supports:
//!
//! ```
//! use canadensis_filter_config::{optimize, Filter};
//!
//! let interesting_message_ids = [0x107d552a, 0x11733775, 0x136b957b, 0x126bbdaa, 0x1073373b];
//! let mut ideal_filters = [
//! Filter::exact_match(interesting_message_ids[0]),
//! Filter::exact_match(interesting_message_ids[1]),
//! Filter::exact_match(interesting_message_ids[2]),
//! Filter::exact_match(interesting_message_ids[3]),
//! Filter::exact_match(interesting_message_ids[4]),
//! ];
//! // Using an imaginary CAN peripheral that supports only 2 receive filters
//! let max_hardware_filters = 2;
//! let optimized_filters = optimize(&mut ideal_filters, max_hardware_filters);
//! assert_eq!(optimized_filters.len(), 2);
//!
//! // Each interesting message ID will be accepted by at least one of the optimized filters
//! for &id in interesting_message_ids.iter() {
//! assert!(optimized_filters.iter().any(|filter| filter.accepts(id)));
//! }
//! ```
//!
//! 3. Apply the resulting filters to the CAN hardware
#![no_std]
#![deny(missing_docs)]
/// Mask of allowed extended CAN IDs
const EXTENDED_ID_MASK: u32 = 0x1fff_ffff;
/// Bit 31, used to mark a filter as valid
const VALID_BIT: u32 = 0x8000_0000;
/// A generic mask-based filter for extended CAN IDs
///
/// A filter will accept a message if (message_id & filter.mask) == (filter.id & filter.mask).
#[derive(Clone)]
#[cfg_attr(test, derive(PartialEq))]
pub struct Filter {
/// Mask of bits to compare (0x1fff_ffff requires all ID bits to match, 0x0 accepts any ID)
mask: u32,
/// Message ID to accept
///
/// The most significant bit (bit 31) indicates that this filter is valid. The optimize function
/// uses this bit to keep track of empty slots in the slice of filters.
id_and_valid: u32,
}
impl Filter {
/// Creates a filter
///
/// If the mask or ID is too large to fit into 29 bits, it will be silently truncated.
#[inline]
pub fn new(mask: u32, id: u32) -> Self {
Filter {
mask: mask & EXTENDED_ID_MASK,
id_and_valid: (id & EXTENDED_ID_MASK) | VALID_BIT,
}
}
/// Creates a filter that matches exactly one message ID
///
/// If the ID is too larg to fit into 29 bits, it will be silently truncated.
pub fn exact_match(id: u32) -> Self {
Filter::new(EXTENDED_ID_MASK, id)
}
/// Returns the mask of this filter, which indicates the bits that are checked
#[inline]
pub fn mask(&self) -> u32 {
self.mask
}
/// Returns the message ID that this filter (partially) matches
#[inline]
pub fn id(&self) -> u32 {
self.id_and_valid & EXTENDED_ID_MASK
}
/// Returns true if this filter is valid
fn is_valid(&self) -> bool {
(self.id_and_valid & VALID_BIT) != 0
}
/// Marks this filter as not valid and resets its mask and ID
fn invalidate(&mut self) {
self.mask = 0;
self.id_and_valid = 0;
}
/// Returns the number of 1 bits in the mask
///
/// A higher rank means that the filter will reject more messages.
fn rank(&self) -> u32 {
self.mask.count_ones()
}
/// Returns true if this filter accepts a message with the provided ID
pub fn accepts(&self, id: u32) -> bool {
(self.mask() & id) == (self.mask() & self.id())
}
}
mod debug_impl {
use super::Filter;
use core::fmt::{Debug, Formatter, Result};
impl Debug for Filter {
fn fmt(&self, f: &mut Formatter<'_>) -> Result {
f.debug_struct("Filter")
.field("valid", &self.is_valid())
.field("mask", &DebugHex(self.mask()))
.field("id", &DebugHex(self.id()))
.finish()
}
}
struct DebugHex(u32);
impl Debug for DebugHex {
fn fmt(&self, f: &mut Formatter<'_>) -> Result {
write!(f, "{:#010x}", self.0)
}
}
}
fn merge_masks(a: &Filter, b: &Filter) -> u32 {
a.mask() & b.mask() & !(a.id() ^ b.id())
}
/// Merges two filters, producing a new filter that accepts the union of the IDs accepted by the
/// two input filters (and possibly more IDs)
fn merge(a: &Filter, b: &Filter) -> Filter {
let mask = merge_masks(a, b);
Filter::new(mask, a.id() & mask)
}
/// Combines a slice of ideal filters down to max_filters filters that will accept a superset
/// of the message IDs of the ideal filters
///
/// The returned slice will be a sub-slice of ideal_filters.
///
/// If max_filters is zero, this function returns an empty slice. If max_filters is greater than
/// the length of ideal_filters, this function returns ideal_filters.
pub fn optimize(ideal_filters: &mut [Filter], max_filters: usize) -> &[Filter] {
if max_filters == 0 {
// Can't really do anything when nothing can be filtered
return &[];
}
let working_filters = ideal_filters;
// Step 1: Merge filters
merge_filters(working_filters, max_filters);
// In debug mode, check that not too many filters remain
debug_assert!(
working_filters
.iter()
.filter(|filter| filter.is_valid())
.count()
<= max_filters
);
// Step 2: Compact
compact(working_filters);
// Step 3: Return only the beginning part of the slice that contains valid filters
let first_invalid = working_filters
.iter()
.position(|filter| !filter.is_valid())
.unwrap_or(working_filters.len());
let (valid_filters, invalid_filters) = working_filters.split_at(first_invalid);
#[cfg(debug_assertions)]
{
// Check that the filters have been correctly split into valid and invalid
assert!(valid_filters.iter().all(Filter::is_valid));
assert!(!invalid_filters.iter().any(Filter::is_valid));
}
#[cfg(not(debug_assertions))]
let _ = invalid_filters;
valid_filters
}
/// Merges filters so that a maximum of max_filters are valid
fn merge_filters(working_filters: &mut [Filter], max_filters: usize) {
assert_ne!(max_filters, 0);
let mut valid_filters = working_filters.len();
while valid_filters > max_filters {
// Find the pair of valid filters with the maximum rank when merged
let mut max_rank = 0;
let mut max_rank_indices = (0, 0);
for i in 0..working_filters.len() {
for j in (i + 1)..working_filters.len() {
let filter1 = &working_filters[i];
let filter2 = &working_filters[j];
if filter1.is_valid() && filter2.is_valid() {
let rank = merge(filter1, filter2).rank();
if rank >= max_rank {
max_rank_indices = (i, j);
max_rank = rank;
}
}
}
}
// Merge those filters into the first, invalidate the second
working_filters[max_rank_indices.0] = merge(
&working_filters[max_rank_indices.0],
&working_filters[max_rank_indices.1],
);
working_filters[max_rank_indices.1].invalidate();
valid_filters -= 1;
debug_assert_eq!(
valid_filters,
working_filters
.iter()
.filter(|filter| filter.is_valid())
.count()
);
}
}
/// Moves all valid filter to the beginning of filters, and all invalid filters to the end
fn compact(filters: &mut [Filter]) {
// This could use the core library sort functions, but they add a lot of code size
// (about 5000 bytes for thumbvem-none-eabihf).
// Do this simple thing, based on insertion sort, instead.
// This is O(n^2), but the number of filters is likely to be less than 100.
for i in 1..filters.len() {
let mut j = i;
while j != 0 && !filters[j - 1].is_valid() && filters[j].is_valid() {
filters.swap(j - 1, j);
j -= 1;
}
}
}
#[cfg(test)]
mod test_compact {
use super::{compact, Filter};
/// Returns an invalid filter
fn invalid() -> Filter {
let mut filter = Filter::new(0, 0);
filter.invalidate();
filter
}
/// Returns a valid filter
fn valid() -> Filter {
Filter::new(0, 0)
}
fn check(inputs: &mut [Filter]) {
compact(inputs);
let first_invalid_index = inputs
.iter()
.position(|filter| !filter.is_valid())
.unwrap_or(inputs.len());
let (valid, invalid) = inputs.split_at(first_invalid_index);
assert!(valid.iter().all(Filter::is_valid));
assert!(!invalid.iter().any(Filter::is_valid));
}
#[test]
fn basics() {
check(&mut []);
check(&mut [valid()]);
check(&mut [invalid()]);
check(&mut [valid(), invalid()]);
check(&mut [invalid(), valid()]);
check(&mut [invalid(), invalid()]);
check(&mut [valid(), valid()]);
}
fn valid_from_bit_8(value: u8, bit: u8) -> Filter {
if ((value >> bit) & 1) == 1 {
valid()
} else {
invalid()
}
}
#[test]
fn longer() {
// Check all combinations of 8 valid and invalid filters
for permutation in 0..=u8::MAX {
let mut filters = [
valid_from_bit_8(permutation, 0),
valid_from_bit_8(permutation, 1),
valid_from_bit_8(permutation, 2),
valid_from_bit_8(permutation, 3),
valid_from_bit_8(permutation, 4),
valid_from_bit_8(permutation, 5),
valid_from_bit_8(permutation, 6),
valid_from_bit_8(permutation, 7),
];
check(&mut filters);
}
}
}
#[cfg(test)]
mod test_single_merge {
use super::{merge, Filter, EXTENDED_ID_MASK};
/// Merge two filters that are the same, result should be equal to the inputs
#[test]
fn merge_two_equal() {
let test_filters = [
Filter::new(0x0, 0x0),
Filter::new(0x1, 0x1),
Filter::new(0x1, 0x0),
Filter::new(0x3, 0x0),
Filter::new(0x3, 0x1),
Filter::new(0x3, 0x2),
Filter::new(0x3, 0x3),
];
for filter in test_filters.iter() {
let combined = merge(filter, filter);
assert_eq!(&combined, filter);
}
}
/// Merge two filters that accept exactly one ID each
///
/// The combination should accept both IDs
#[test]
fn merge_two_exact_id() {
let ids = [
(0x0, 0x0),
(0x10, 0x0),
(0x0, 0x10),
(EXTENDED_ID_MASK, 0x0),
(0x0, EXTENDED_ID_MASK),
(0x12933, 0x12932),
];
for &(id1, id2) in ids.iter() {
let filter1 = Filter::new(EXTENDED_ID_MASK, id1);
let filter2 = Filter::new(EXTENDED_ID_MASK, id2);
assert!(filter1.accepts(id1));
assert!(filter2.accepts(id2));
let merged = merge(&filter1, &filter2);
assert!(merged.accepts(id1));
assert!(merged.accepts(id2));
}
}
}