httproxide_h3/qpack/
vas.rs

1/**
2 * https://tools.ietf.org/html/draft-ietf-quic-qpack-01#section-2.2.1
3 * https://tools.ietf.org/html/draft-ietf-quic-qpack-01#section-2.2.2
4 */
5
6/*
7 *  # Virtually infinite address space mapper.
8 *
9 *  It can be described as a infinitively growable list, with a visibility
10 *  window that can only move in the direction of insertion.
11 *
12 *  Origin          Visible window
13 *  /\         /===========^===========\
14 *  ++++-------+ - + - + - + - + - + - +
15 *  ||||       |   |   |   |   |   |   |  ==> Grow direction
16 *  ++++-------+ - + - + - + - + - + - +
17 *  \================v==================/
18 *           Full Virtual Space
19 *
20 *
21 *  QPACK indexing is 1-based for absolute index, and 0-based for relative's.
22 *  Container (ex: list) indexing is 0-based.
23 *
24 *
25 *  # Basics
26 *
27 *  inserted: number of insertion
28 *  dropped : number of drop
29 *  delta   : count of available elements
30 *
31 *  abs: absolute index
32 *  rel: relative index
33 *  pos: real index in memory container
34 *  pst: post-base relative index (only with base index)
35 *
36 *    first      oldest              lastest
37 *    element    insertion           insertion
38 *    (not       available           available
39 *    available) |                   |
40 *    |          |                   |
41 *    v          v                   v
42 *  + - +------+ - + - + - + - + - + - +  inserted: 21
43 *  | a |      | p | q | r | s | t | u |  dropped: 15
44 *  + - +------+ - + - + - + - + - + - +  delta: 21 - 15: 6
45 *    ^          ^                   ^
46 *    |          |                   |
47 * abs:-      abs:16              abs:21
48 * rel:-      rel:5               rel:0
49 * pos:-      pos:0               pos:6
50 *
51 *
52 * # Base index
53 * A base index can arbitrary shift the relative index.
54 * The base index itself is a absolute index.
55 *
56 *                       base index: 17
57 *                       |
58 *                       v
59 *  + - +------+ - + - + - + - + - + - +  inserted: 21
60 *  | a |      | p | q | r | s | t | u |  dropped: 15
61 *  + - +------+ - + - + - + - + - + - +  delta: 21 - 15: 6
62 *    ^          ^       ^           ^
63 *    |          |       |           |
64 * abs:-      abs:16  abs:18      abs:21
65 * rel:-      rel:2   rel:0       rel:-
66 * pst:-      pst:-   pst:-       pst:2
67 * pos:-      pos:0   pos:2       pos:6
68 */
69
70pub type RelativeIndex = usize;
71pub type AbsoluteIndex = usize;
72
73#[derive(Debug, PartialEq)]
74pub enum Error {
75    RelativeIndex(usize),
76    PostbaseIndex(usize),
77    Index(usize),
78}
79
80#[derive(Debug, Default)]
81pub struct VirtualAddressSpace {
82    inserted: usize,
83    dropped: usize,
84    delta: usize,
85}
86
87impl VirtualAddressSpace {
88    pub fn add(&mut self) -> AbsoluteIndex {
89        self.inserted += 1;
90        self.delta += 1;
91        self.inserted
92    }
93
94    pub fn drop(&mut self) {
95        self.dropped += 1;
96        self.delta -= 1;
97    }
98
99    pub fn relative(&self, index: RelativeIndex) -> Result<usize, Error> {
100        if self.inserted < index || self.delta == 0 || self.inserted - index <= self.dropped {
101            Err(Error::RelativeIndex(index))
102        } else {
103            Ok(self.inserted - self.dropped - index - 1)
104        }
105    }
106
107    pub fn evicted(&self, index: AbsoluteIndex) -> bool {
108        index != 0 && index <= self.dropped
109    }
110
111    pub fn relative_base(&self, base: usize, index: RelativeIndex) -> Result<usize, Error> {
112        if self.delta == 0 || index > base || base - index <= self.dropped {
113            Err(Error::RelativeIndex(index))
114        } else {
115            Ok(base - self.dropped - index - 1)
116        }
117    }
118
119    pub fn post_base(&self, base: usize, index: RelativeIndex) -> Result<usize, Error> {
120        if self.delta == 0 || base + index >= self.inserted || base + index < self.dropped {
121            Err(Error::PostbaseIndex(index))
122        } else {
123            Ok(base + index - self.dropped)
124        }
125    }
126
127    pub fn index(&self, index: usize) -> Result<usize, Error> {
128        if index >= self.delta {
129            Err(Error::Index(index))
130        } else {
131            Ok(index + self.dropped + 1)
132        }
133    }
134
135    pub fn largest_ref(&self) -> usize {
136        self.inserted - self.dropped
137    }
138
139    pub fn total_inserted(&self) -> usize {
140        self.inserted
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use proptest::proptest;
148
149    #[test]
150    fn test_no_relative_index_when_empty() {
151        let vas = VirtualAddressSpace::default();
152        let res = vas.relative_base(0, 0);
153        assert_eq!(res, Err(Error::RelativeIndex(0)));
154    }
155
156    #[test]
157    fn test_relative_underflow_protected() {
158        let mut vas = VirtualAddressSpace::default();
159        vas.add();
160        assert_eq!(vas.relative(2), Err(Error::RelativeIndex(2)));
161    }
162
163    proptest! {
164        #[test]
165        fn test_first_insertion_without_drop(
166            ref count in 1..2200usize
167        ) {
168            let mut vas = VirtualAddressSpace::default();
169            vas.add();
170            (1..*count).for_each(|_| { vas.add(); });
171
172            assert_eq!(vas.relative_base(*count, count - 1), Ok(0), "{:?}", vas);
173        }
174
175        #[test]
176        fn test_first_insertion_with_drop(
177            ref count in 2..2200usize
178        ) {
179            let mut vas = VirtualAddressSpace::default();
180            vas.add();
181            (1..*count).for_each(|_| { vas.add(); });
182            (0..*count - 1).for_each(|_| vas.drop());
183
184            assert_eq!(vas.relative_base(*count, count - 1), Err(Error::RelativeIndex(count - 1)), "{:?}", vas);
185        }
186
187        #[test]
188        fn test_last_insertion_without_drop(
189            ref count in 1..2200usize
190        ) {
191            let mut vas = VirtualAddressSpace::default();
192            (1..*count).for_each(|_| { vas.add(); });
193            vas.add();
194
195            assert_eq!(vas.relative_base(*count, 0), Ok(count -1),
196                       "{:?}", vas);
197        }
198
199        #[test]
200        fn test_last_insertion_with_drop(
201            ref count in 2..2200usize
202        ) {
203            let mut vas = VirtualAddressSpace::default();
204            (0..*count - 1).for_each(|_| { vas.add(); });
205            vas.add();
206            (0..*count - 1).for_each(|_| { vas.drop(); });
207
208            assert_eq!(vas.relative_base(*count, 0), Ok(0),
209                       "{:?}", vas);
210        }
211    }
212
213    #[test]
214    fn test_post_base_index() {
215        /*
216         * Base index: D
217         * Target value: B
218         *
219         * VAS: ]GFEDCBA]
220         * abs:  1234567
221         * rel:  3210---
222         * pst:  ----012
223         * pos:  0123456
224         */
225        let mut vas = VirtualAddressSpace::default();
226        (0..7).for_each(|_| {
227            vas.add();
228        });
229
230        assert_eq!(vas.post_base(4, 1), Ok(5));
231    }
232
233    #[test]
234    fn largest_ref() {
235        let mut vas = VirtualAddressSpace::default();
236        (0..7).for_each(|_| {
237            vas.add();
238        });
239        assert_eq!(vas.largest_ref(), 7);
240    }
241
242    #[test]
243    fn relative() {
244        let mut vas = VirtualAddressSpace::default();
245
246        (0..7).for_each(|_| {
247            vas.add();
248        });
249
250        assert_eq!(vas.relative(0), Ok(6));
251        assert_eq!(vas.relative(1), Ok(5));
252        assert_eq!(vas.relative(6), Ok(0));
253        assert_eq!(vas.relative(7), Err(Error::RelativeIndex(7)));
254    }
255
256    #[test]
257    fn absolute_from_real_index() {
258        let mut vas = VirtualAddressSpace::default();
259        assert_eq!(vas.index(0), Err(Error::Index(0)));
260        vas.add();
261        assert_eq!(vas.index(0), Ok(1));
262        vas.add();
263        vas.drop();
264        assert_eq!(vas.index(0), Ok(2));
265        vas.drop();
266        assert_eq!(vas.index(0), Err(Error::Index(0)));
267        vas.add();
268        vas.add();
269        assert_eq!(vas.index(0), Ok(3));
270        assert_eq!(vas.index(1), Ok(4));
271        assert_eq!(vas.index(2), Err(Error::Index(2)));
272    }
273
274    #[test]
275    fn evicted() {
276        let mut vas = VirtualAddressSpace::default();
277        assert_eq!(vas.evicted(0), false);
278        assert_eq!(vas.evicted(1), false);
279        vas.add();
280        vas.add();
281        assert_eq!(vas.evicted(1), false);
282        vas.drop();
283        assert_eq!(vas.evicted(0), false);
284        assert_eq!(vas.evicted(1), true);
285        assert_eq!(vas.evicted(2), false);
286        vas.drop();
287        assert_eq!(vas.evicted(2), true);
288    }
289}
httproxide_h3/qpack/vas.rs

httproxide_h3/qpack/
vas.rs
