ringbuffer_iteration/
lib.rs

1//! A ring buffer implementation where newer samples overwrite old samples. This implementation
2//! also enables the use of Rust iterators to iterate through the ring buffer in order from oldest
3//! to newest entries.
4//!
5//! This library is implemented without the use of the standard library, and thus requires passing
6//! in a "backing store" of a statically allocated array.
7#![no_std]
8extern crate libm;
9mod test_macros;
10use libm::sqrtf;
11use num_traits::PrimInt;
12
13/// An implementation of a ring buffer data structure that creates a "lossy" queue. This is a
14/// simplified version of the generic heapless `Queue` with a few constraints relaxed:
15///
16/// - The Item type is at least Copy + Clone
17/// - We do not care about overwritten data in the buffer. Should be able to write indefinitely
18///   without error.
19///
20/// An iterator is also defined for `RingBuffer` which implements [`Iterator`],
21/// [`ExactSizeIterator`], and [`DoubleEndedIterator`]. The iterator begins at the head of the ring
22/// buffer and iterates until it reaches the tail.
23///
24/// Also uses an internal flag `overwriting` to allow iteration over the last value in the
25/// ring buffer, giving the structure a capacity of `N` rather than the typical ringbuffer capacity
26/// of `N-1`.
27pub struct RingBuffer<T: Copy + Clone, const N: usize> {
28    inner: [T; N],
29    head: usize,
30    tail: usize,
31    overwriting: bool,
32}
33
34impl<T, const N: usize> RingBuffer<T, N>
35where
36    T: Copy + Clone,
37{
38    pub fn new(backing_store: [T; N]) -> Self {
39        RingBuffer {
40            inner: backing_store,
41            head: 0,
42            tail: 0,
43            overwriting: false,
44        }
45    }
46
47    pub fn is_empty(&self) -> bool {
48        self.head == self.tail
49    }
50
51    pub fn is_full(&self) -> bool {
52        (self.tail + 1) % self.inner.len() == self.head
53    }
54
55    pub fn capacity(&self) -> usize {
56        self.inner.len()
57    }
58
59    /// Add a new item to the ring buffer.
60    pub fn add(&mut self, item: T) {
61        self.inner[self.tail] = item;
62        if self.is_full() {
63            // Drop the last sample
64            self.head = (self.head + 1) % self.inner.len();
65            self.overwriting = true;
66        }
67        self.tail = (self.tail + 1) % self.inner.len();
68    }
69
70    /// Pops the last item off of the ring buffer.
71    pub fn pop(&mut self) -> Option<T> {
72        if self.is_empty() {
73            return None;
74        }
75        if self.overwriting {
76            // If overwriting, grab first value from position behind head
77            let compensated_index: usize = if self.head == 0 {
78                self.inner.len() - 1
79            } else {
80                self.head - 1
81            };
82            let val = self.inner[compensated_index];
83            self.overwriting = false;
84            Some(val)
85        } else {
86            let val = self.inner[self.head];
87            self.head = (self.head + 1) % self.inner.len();
88            self.overwriting = false;
89            Some(val)
90        }
91    }
92}
93
94pub struct RingBufferIterator<'a, T: Copy + Clone, const N: usize> {
95    inner: &'a [T; N],
96    head: usize,
97    tail: usize,
98    cursor: usize,
99    overwriting: bool,
100}
101
102impl<T, const N: usize> RingBufferIterator<'_, T, N>
103where
104    T: Copy + Clone,
105{
106    pub fn is_empty(&self) -> bool {
107        self.head == self.tail
108    }
109
110    pub fn is_full(&self) -> bool {
111        (self.tail + 1) % self.inner.len() == self.head
112    }
113
114    pub fn capacity(&self) -> usize {
115        self.inner.len()
116    }
117}
118
119impl<'a, T, const N: usize> IntoIterator for &'a RingBuffer<T, N>
120where
121    T: Copy + Clone,
122{
123    type Item = T;
124    type IntoIter = RingBufferIterator<'a, T, N>;
125
126    fn into_iter(self) -> Self::IntoIter {
127        RingBufferIterator {
128            inner: &self.inner,
129            head: self.head,
130            tail: self.tail,
131            cursor: self.head,
132            overwriting: self.overwriting,
133        }
134    }
135}
136
137impl<T, const N: usize> Iterator for RingBufferIterator<'_, T, N>
138where
139    T: Copy + Clone,
140{
141    type Item = T;
142
143    fn next(&mut self) -> Option<Self::Item> {
144        if self.cursor == self.head && self.overwriting {
145            // If overwriting, grab first value from position behind head
146            let compensated_index: usize = if self.head == 0 {
147                self.inner.len() - 1
148            } else {
149                self.head - 1
150            };
151            let val = self.inner[compensated_index];
152            self.overwriting = false;
153            return Some(val);
154        }
155        if self.cursor != self.tail {
156            let val = self.inner[self.cursor];
157            self.cursor = (self.cursor + 1) % self.inner.len();
158            return Some(val);
159        } else {
160            return None;
161        }
162    }
163
164    fn size_hint(&self) -> (usize, Option<usize>) {
165        let size = ring_buffer_iter_len(self);
166        (size, Some(size))
167    }
168}
169
170impl<T, const N: usize> ExactSizeIterator for RingBufferIterator<'_, T, N>
171where
172    T: Copy + Clone,
173{
174    fn len(&self) -> usize {
175        ring_buffer_iter_len(self)
176    }
177}
178
179impl<T, const N: usize> DoubleEndedIterator for RingBufferIterator<'_, T, N>
180where
181    T: Copy + Clone,
182{
183    fn next_back(&mut self) -> Option<Self::Item> {
184        if self.cursor != self.tail {
185            self.tail = if self.tail == 0 {
186                self.inner.len() - 1
187            } else {
188                self.tail - 1
189            };
190            let val = self.inner[self.tail];
191            return Some(val);
192        } else {
193            return None;
194        }
195    }
196}
197
198fn ring_buffer_iter_len<T, const N: usize>(buf: &RingBufferIterator<T, N>) -> usize
199where
200    T: Copy + Clone,
201{
202    if buf.cursor > buf.tail {
203        (buf.inner.len() - buf.cursor) + buf.tail + 1
204    } else {
205        buf.tail - buf.cursor
206    }
207}
208
209/// Calculate the mean of the values inside `buffer`.
210///
211/// This implementation upcasts to an i64 in order to prevent any risk of overflow during
212/// summation. The result is still returned as the original data type. This only operates over
213/// primitive integer types and not floating point numbers due to this upcast logic.
214pub fn mean<T, const N: usize>(buffer: &RingBuffer<T, N>) -> T
215where
216    T: PrimInt,
217{
218    _mean(buffer.into_iter())
219}
220
221/// Calculate the mean of the last `window_len` values inside `buffer`.
222///
223/// See [`mean`] for details.
224pub fn windowed_mean<T, const N: usize>(buffer: &RingBuffer<T, N>, window_len: usize) -> T
225where
226    T: PrimInt,
227{
228    _mean(buffer.into_iter().rev().take(window_len))
229}
230
231fn _mean<I, T>(iter: I) -> T
232where
233    I: ExactSizeIterator<Item = T>,
234    T: PrimInt,
235{
236    let len = iter.len();
237    let sum = |acc, el: T| acc + (el.to_i64().unwrap());
238    T::from(iter.fold(0_i64, sum) / (len as i64)).unwrap()
239}
240
241/// Calculate the root-mean-square of `buffer`, passing in `mean`
242/// as the pre-calculated mean.
243pub fn ac_rms<T, const N: usize>(buffer: &RingBuffer<T, N>, mean: T) -> f32
244where
245    T: PrimInt,
246{
247    _ac_rms(buffer.into_iter(), mean)
248}
249
250/// Calculate the AC RMS of the last `window_len` values inside `buffer`.
251///
252/// See [`ac_rms`] for details.
253pub fn windowed_ac_rms<T, const N: usize>(
254    buffer: &RingBuffer<T, N>,
255    mean: T,
256    window_len: usize,
257) -> f32
258where
259    T: PrimInt,
260{
261    _ac_rms(buffer.into_iter().rev().take(window_len), mean)
262}
263
264fn _ac_rms<I, T>(iter: I, mean: T) -> f32
265where
266    I: ExactSizeIterator<Item = T>,
267    T: PrimInt,
268{
269    // TODO: Derisk if this casting is a performance bottleneck?
270    let len = iter.len();
271    let sum_square =
272        |acc, el: T| acc + (el - mean).to_i64().unwrap() * (el - mean).to_i64().unwrap();
273    let avg_sum_squares = iter.fold(0, sum_square) / (len as i64);
274    sqrtf(avg_sum_squares as f32)
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280    type DataUnit = i32;
281
282    #[cfg_attr(target_os = "none", test_case)]
283    #[cfg_attr(not(target_os = "none"), test)]
284    fn test_empty_and_full() {
285        let backing_store = [0; 4];
286        let mut buf = RingBuffer::new(backing_store);
287        assert_eq!(buf.is_empty(), true);
288        assert_eq!(buf.is_full(), false);
289        buf.add(1);
290        assert_eq!(buf.is_empty(), false);
291        buf.add(2);
292        buf.add(3);
293        assert_eq!(buf.is_full(), true);
294    }
295
296    #[cfg_attr(target_os = "none", test_case)]
297    #[cfg_attr(not(target_os = "none"), test)]
298    fn test_add_items() {
299        let backing_store = [0; 4];
300        let mut buf = RingBuffer::new(backing_store);
301        buf.add(1);
302        buf.add(2);
303        buf.add(3);
304
305        assert_eq!(buf.pop(), Some(1));
306        assert_eq!(buf.pop(), Some(2));
307        assert_eq!(buf.pop(), Some(3));
308    }
309
310    #[cfg_attr(target_os = "none", test_case)]
311    #[cfg_attr(not(target_os = "none"), test)]
312    fn test_iterate_through_unfilled_buf() {
313        let backing_store = [0; 6];
314        let mut buf = RingBuffer::new(backing_store);
315        buf.add(1);
316        buf.add(2);
317        buf.add(3);
318        let expected_values = [1, 2, 3];
319        assert_eq!(buf.into_iter().len(), expected_values.len());
320        for (idx, val) in (&mut buf).into_iter().enumerate() {
321            assert_eq!(val, expected_values[idx]);
322        }
323    }
324
325    #[cfg_attr(target_os = "none", test_case)]
326    #[cfg_attr(not(target_os = "none"), test)]
327    fn test_iterate_through_items() {
328        let backing_store = [0; 4];
329        let mut buf = RingBuffer::new(backing_store);
330        buf.add(1);
331        buf.add(2);
332        buf.add(3);
333        buf.add(4);
334        buf.add(5);
335        buf.add(6);
336        let expected_values = [3, 4, 5, 6];
337        assert_eq!(buf.into_iter().len(), expected_values.len());
338        for (idx, val) in (&mut buf).into_iter().enumerate() {
339            assert_eq!(val, expected_values[idx]);
340        }
341
342        assert_eq!(buf.pop(), Some(3));
343        assert_eq!(buf.pop(), Some(4));
344        assert_eq!(buf.pop(), Some(5));
345        assert_eq!(buf.pop(), Some(6));
346    }
347
348    #[cfg_attr(target_os = "none", test_case)]
349    #[cfg_attr(not(target_os = "none"), test)]
350    fn test_item_overwrite() {
351        let backing_store = [0; 2];
352        let mut buf = RingBuffer::new(backing_store);
353        for i in 0..100 {
354            buf.add(i);
355        }
356        // Test checks that no panic was triggered
357    }
358
359    #[cfg_attr(target_os = "none", test_case)]
360    #[cfg_attr(not(target_os = "none"), test)]
361    fn test_exactsize_iter_length_counts() {
362        let backing_store = [0; 4];
363        let mut buf = RingBuffer::new(backing_store);
364        buf.add(1);
365        buf.add(2);
366        buf.add(3);
367        buf.add(4);
368        buf.add(5);
369        buf.add(6);
370        assert_eq!(buf.into_iter().len(), 4);
371
372        buf.pop();
373        buf.pop();
374        assert_eq!(buf.into_iter().len(), 2);
375
376        buf.add(7);
377        buf.add(8);
378        assert_eq!(buf.into_iter().len(), 4);
379
380        buf.add(9);
381        assert_eq!(buf.into_iter().len(), 4);
382    }
383
384    #[cfg_attr(target_os = "none", test_case)]
385    #[cfg_attr(not(target_os = "none"), test)]
386    fn test_reverse_iter() {
387        let backing_store = [0; 4];
388        let mut buf = RingBuffer::new(backing_store);
389        for i in 1..5 {
390            buf.add(i);
391        }
392        let expected_values: [DataUnit; 4] = [4, 3, 2, 1];
393        for (idx, val) in (&mut buf).into_iter().rev().enumerate() {
394            assert_eq!(val, expected_values[idx]);
395        }
396    }
397
398    #[cfg_attr(target_os = "none", test_case)]
399    #[cfg_attr(not(target_os = "none"), test)]
400    fn test_non_integer_storage() {
401        let backing_store: [(f32, &'static str); 5] = [(3.2, "hi"); 5];
402        let mut buf = RingBuffer::new(backing_store);
403        for i in 1..5 {
404            buf.add((i as f32 * 4.2, "Testing"));
405        }
406        let expected_values = [
407            (4.2, "Testing"),
408            (8.4, "Testing"),
409            (12.6, "Testing"),
410            (16.8, "Testing"),
411        ];
412        for (idx, val) in (&mut buf).into_iter().enumerate() {
413            assert_almost_eq!(val.0, expected_values[idx].0, 1e-3);
414            assert_eq!(val.1, expected_values[idx].1);
415        }
416    }
417
418    fn new_test_buffer() -> RingBuffer<DataUnit, 512> {
419        let array = [0_i32; 512];
420        RingBuffer::new(array)
421    }
422
423    mod mean {
424        use super::*;
425        #[cfg_attr(target_os = "none", test_case)]
426        #[cfg_attr(not(target_os = "none"), test)]
427        /// Tests that `mean` still returns accurate calculations when data changes in small
428        /// increments.
429        fn mean_small_delta() {
430            let mut buffer: RingBuffer<DataUnit, 512> = new_test_buffer();
431            let n = 15 << 10;
432            for idx in n..(n + buffer.capacity()) {
433                buffer.add(idx as i32);
434            }
435            let actual_mean = n as i32 + (buffer.capacity() as i32) / 2 - 1;
436            assert_eq!(mean(&mut buffer), actual_mean);
437        }
438
439        #[cfg_attr(target_os = "none", test_case)]
440        #[cfg_attr(not(target_os = "none"), test)]
441        /// Test that `mean` calculates the exact mean when data changes in steps of at least 1024.
442        fn mean_wide_step_size() {
443            let mut buffer: RingBuffer<DataUnit, 512> = new_test_buffer();
444            for idx in 0..buffer.capacity() {
445                buffer.add((idx as i32) << 10);
446            }
447            let actual_mean = ((buffer.capacity() as i32) - 1) << 9;
448            assert_eq!(mean(&mut buffer), actual_mean);
449        }
450
451        #[cfg_attr(target_os = "none", test_case)]
452        #[cfg_attr(not(target_os = "none"), test)]
453        /// Test that `mean` doesn't overflow when summing maximum values.
454        fn mean_no_overflow() {
455            let mut buffer: RingBuffer<DataUnit, 512> = new_test_buffer();
456            let max_val = (0x1 << 30) - 1 as i32;
457            for _idx in 0..buffer.capacity() {
458                buffer.add(max_val);
459            }
460            assert_eq!(mean(&mut buffer), max_val);
461        }
462
463        #[cfg_attr(target_os = "none", test_case)]
464        #[cfg_attr(not(target_os = "none"), test)]
465        /// Test that `mean` can be calculated over large buffer sizes
466        fn mean_larger_buffer() {
467            let array = [0_i32; 4096];
468            let mut buffer: RingBuffer<DataUnit, 4096> = RingBuffer::new(array);
469
470            let n = 25 << 10;
471            for idx in n..(n + buffer.capacity()) {
472                buffer.add(idx as i32);
473            }
474            let actual_mean = n as i32 + (buffer.capacity() as i32) / 2 - 1;
475            assert_eq!(mean(&mut buffer), actual_mean);
476        }
477
478        #[cfg_attr(target_os = "none", test_case)]
479        #[cfg_attr(not(target_os = "none"), test)]
480        /// Test that `mean` can be calculated over large buffer sizes
481        fn test_windowed_mean() {
482            let array = [0; 6];
483            let mut buffer: RingBuffer<DataUnit, 6> = RingBuffer::new(array);
484
485            let data = [0, 1, 2, 3, 4, 5];
486            for val in data.iter() {
487                buffer.add(*val as i32);
488            }
489            assert_eq!(windowed_mean(&mut buffer, 5), 3);
490        }
491    }
492
493    mod ac_rms {
494        use super::*;
495
496        #[cfg_attr(target_os = "none", test_case)]
497        #[cfg_attr(not(target_os = "none"), test)]
498        /// Test accuracy of ac_rms calculation on a "sine wave". In quotes because we are
499        /// casting the sine value float to an int, so it's really a digitized sine. Expected
500        /// result was calculated in Python.
501        fn ac_rms_sine() {
502            use libm::sin;
503
504            let func = |val: usize| sin(val as f64) * 1000000_f64;
505            let expected_result = 707128.4729105555_f32;
506
507            let mut buffer: RingBuffer<DataUnit, 512> = new_test_buffer();
508            let capacity = buffer.capacity();
509            for idx in 0..capacity {
510                buffer.add(func(idx) as i32);
511            }
512            let buf_mean = mean(&mut buffer);
513            assert_almost_eq!(ac_rms(&mut buffer, buf_mean), expected_result, 0.1);
514        }
515
516        #[cfg_attr(target_os = "none", test_case)]
517        #[cfg_attr(not(target_os = "none"), test)]
518        /// Tests that ac_rms does not change when a DC offset is added.
519        fn ac_rms_sine_dc_offset() {
520            use libm::sin;
521
522            let func = |val: usize| sin(val as f64) * 1000000_f64;
523            let expected_result = 707128.4729105555_f32;
524
525            let mut buffer: RingBuffer<DataUnit, 512> = new_test_buffer();
526            let capacity = buffer.capacity();
527            let offset = 1000000_i32;
528            for idx in 0..capacity {
529                buffer.add(func(idx) as i32 + offset);
530            }
531            let buf_mean = mean(&mut buffer);
532            assert_almost_eq!(ac_rms(&mut buffer, buf_mean), expected_result, 0.1);
533        }
534
535        #[cfg_attr(target_os = "none", test_case)]
536        #[cfg_attr(not(target_os = "none"), test)]
537        /// Tests that ac_rms does not overflow when processing maximum possible values.
538        fn ac_rms_no_overflow() {
539            let expected_result = 4194303.0_f32;
540
541            let mut buffer: RingBuffer<DataUnit, 512> = new_test_buffer();
542            let capacity = buffer.capacity();
543            let max_val: i32 = (0x1 << 22) - 1;
544            let min_val: i32 = -1 * ((0x1 << 22) - 1);
545            for idx in 0..capacity {
546                if idx % 2 == 0 {
547                    buffer.add(max_val);
548                } else {
549                    buffer.add(min_val);
550                }
551            }
552            let buf_mean = mean(&mut buffer);
553            assert_almost_eq!(ac_rms(&mut buffer, buf_mean), expected_result, 0.005);
554        }
555    }
556}
ringbuffer_iteration/lib.rs

ringbuffer_iteration/
lib.rs
