wlan_common/
tim.rs

1// Copyright 2020 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use crate::mac::{Aid, MAX_AID};
6
7const TIM_BITMAP_LEN: usize = (MAX_AID as usize + 1) / 8;
8
9/// Represents a complete (that is, not partial) traffic indication bitmap. Consists of 2008 bits
10/// (i.e. 251 bytes).
11pub struct TrafficIndicationMap([u8; TIM_BITMAP_LEN]);
12
13impl TrafficIndicationMap {
14    pub fn new() -> Self {
15        Self([0; TIM_BITMAP_LEN])
16    }
17
18    /// Sets a given AID to have buffered traffic (or not) in the traffic indication map.
19    ///
20    /// There is no special handling for AID 0 (i.e. for group traffic), we do not set it as the TIM
21    /// header will indicate it, as per IEEE Std 802.11-2016, 9.4.2.6: The bit numbered 0 in the
22    /// traffic indication virtual bitmap need not be included in the Partial Virtual Bitmap field
23    /// even if that bit is set.
24    pub fn set_traffic_buffered(&mut self, aid: Aid, buffered: bool) {
25        let octet = aid as usize / 8;
26        let bit_offset = aid as usize % 8;
27        self.0[octet] = (self.0[octet] & !(1 << bit_offset)) | ((buffered as u8) << bit_offset)
28    }
29
30    /// IEEE Std 802.11-2016, 9.4.2.6: N1 is the largest even number such that bits numbered 1 to
31    /// (N1 * 8) - 1 in the traffic indication virtual bitmap are all 0.
32    fn n1(&self) -> usize {
33        // TODO(https://fxbug.dev/42116033): Consider using u64 and CTZ instead of checking all the bytes individually.
34        for (i, b) in self.0.iter().enumerate() {
35            if *b != 0 {
36                // Round down to the nearest even number.
37                return i & !0b1;
38            }
39        }
40
41        // IEEE Std 802.11-2016, 9.4.2.6: In the event that all bits other than bit 0 in the traffic
42        // indication virtual bitmap are 0, [...], the Bitmap Offset subfield is 0, [...].
43        0
44    }
45
46    /// IEEE Std 802.11-2016, 9.4.2.6: N2 is the smallest number such that bits numbered
47    /// (N2 + 1) * 8 to 2007 in the traffic indication virtual bitmap are all 0.
48    fn n2(&self) -> usize {
49        // TODO(https://fxbug.dev/42116033): Consider using u64 and CLZ instead of checking all the bytes individually.
50        for (i, b) in self.0.iter().enumerate().rev() {
51            if *b != 0 {
52                return i;
53            }
54        }
55
56        0
57    }
58
59    /// Creates a view into TrafficIndicationMap suitable for use in a TIM IE.
60    pub fn make_partial_virtual_bitmap(&self) -> (u8, &[u8]) {
61        // Invariant: n1 <= n2. This is guaranteed as n1 scans from the front and n2 scans from the
62        // back, so the range of n1..n2 is always non-decreasing.
63        let n1 = self.n1();
64        let n2 = self.n2();
65
66        // IEEE Std 802.11-2016, 9.4.2.6: In the event that all bits other than bit 0 in the traffic
67        // indication virtual bitmap are 0, the Partial Virtual Bitmap field is encoded as a single
68        // octet equal to 0, [...].
69        //
70        // We always have at least one item in the bitmap here, even if there are no items in the
71        // traffic indication bitmap: both n1 and n2 will be 0, which will take the first octet from
72        // the bitmap (which will always be 0).
73        ((n1 / 2) as u8, &self.0[n1..n2 + 1])
74    }
75}
76
77pub fn is_traffic_buffered(offset: u8, bitmap: &[u8], aid: Aid) -> bool {
78    // IEEE 802.11-2016 Std, 9.4.2.6: When dot11MultiBSSIDActivated is false [...] In this case, the
79    // Bitmap Offset subfield value contains the number N1/2.
80    let n1 = offset as usize * 2;
81    let octet = aid as usize / 8;
82
83    let carries_aid = n1 <= octet && octet < bitmap.len() + n1;
84    carries_aid && bitmap[octet - n1] & (1 << (aid as usize % 8)) != 0
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90
91    #[test]
92    fn zero_offset() {
93        let bitmap = &[0b0010010][..];
94
95        assert!(!is_traffic_buffered(0, bitmap, 0));
96        assert!(is_traffic_buffered(0, bitmap, 1));
97        assert!(!is_traffic_buffered(0, bitmap, 2));
98        assert!(!is_traffic_buffered(0, bitmap, 3));
99        assert!(is_traffic_buffered(0, bitmap, 4));
100        assert!(!is_traffic_buffered(0, bitmap, 5));
101        assert!(!is_traffic_buffered(0, bitmap, 6));
102        assert!(!is_traffic_buffered(0, bitmap, 7));
103        assert!(!is_traffic_buffered(0, bitmap, 100));
104    }
105
106    #[test]
107    fn with_offset() {
108        let bitmap = &[0b0010010][..];
109
110        // Offset of 1 means "skip 16 bits"
111        assert!(!is_traffic_buffered(1, bitmap, 15));
112        assert!(!is_traffic_buffered(1, bitmap, 16));
113        assert!(is_traffic_buffered(1, bitmap, 17));
114        assert!(!is_traffic_buffered(1, bitmap, 18));
115        assert!(!is_traffic_buffered(1, bitmap, 19));
116        assert!(is_traffic_buffered(1, bitmap, 20));
117        assert!(!is_traffic_buffered(1, bitmap, 21));
118        assert!(!is_traffic_buffered(1, bitmap, 22));
119        assert!(!is_traffic_buffered(1, bitmap, 100));
120    }
121
122    #[test]
123    fn traffic_indication_map_set_traffic_buffered() {
124        let mut tim = TrafficIndicationMap::new();
125        tim.set_traffic_buffered(12, true);
126        let mut expected_bitmap = [0; TIM_BITMAP_LEN];
127        expected_bitmap[1] = 0b00010000;
128        assert_eq!(&tim.0[..], &expected_bitmap[..]);
129        assert_eq!(tim.n1(), 0);
130        assert_eq!(tim.n2(), 1);
131    }
132
133    #[test]
134    fn traffic_indication_map_set_traffic_buffered_multiple_octets() {
135        let mut tim = TrafficIndicationMap::new();
136        tim.set_traffic_buffered(12, true);
137        tim.set_traffic_buffered(35, true);
138        let mut expected_bitmap = [0; TIM_BITMAP_LEN];
139        expected_bitmap[1] = 0b00010000;
140        expected_bitmap[4] = 0b00001000;
141        assert_eq!(&tim.0[..], &expected_bitmap[..]);
142        assert_eq!(tim.n1(), 0);
143        assert_eq!(tim.n2(), 4);
144    }
145
146    #[test]
147    fn from_partial_virtual_bitmap() {
148        let mut tim = TrafficIndicationMap::new();
149        tim.set_traffic_buffered(12, true);
150        let (offset, bitmap) = tim.make_partial_virtual_bitmap();
151        assert_eq!(offset, 0);
152        assert_eq!(bitmap, &[0b00000000, 0b00010000]);
153        assert!(is_traffic_buffered(offset, bitmap, 12));
154    }
155
156    #[test]
157    fn from_partial_virtual_bitmap_bigger_offset() {
158        let mut tim = TrafficIndicationMap::new();
159        tim.set_traffic_buffered(49, true);
160        let (offset, bitmap) = tim.make_partial_virtual_bitmap();
161        assert_eq!(offset, 3);
162        assert_eq!(bitmap, &[0b00000010]);
163        assert!(is_traffic_buffered(offset, bitmap, 49));
164    }
165
166    #[test]
167    fn from_partial_virtual_bitmap_multiple_octets() {
168        let mut tim = TrafficIndicationMap::new();
169        tim.set_traffic_buffered(12, true);
170        tim.set_traffic_buffered(35, true);
171        let (offset, bitmap) = tim.make_partial_virtual_bitmap();
172        assert_eq!(offset, 0);
173        assert_eq!(bitmap, &[0b00000000, 0b00010000, 0b00000000, 0b00000000, 0b00001000]);
174        assert!(is_traffic_buffered(offset, bitmap, 12));
175        assert!(is_traffic_buffered(offset, bitmap, 35));
176    }
177
178    #[test]
179    fn from_partial_virtual_bitmap_no_traffic() {
180        let tim = TrafficIndicationMap::new();
181        let (offset, bitmap) = tim.make_partial_virtual_bitmap();
182        assert_eq!(offset, 0);
183        assert_eq!(bitmap, &[0b00000000]);
184    }
185}
wlan_common/tim.rs

wlan_common/
tim.rs
