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

/*!
Provides utility functions used in other parts of the library.
*/
use std::num::Wrapping;

use num_traits::Float;

/// Determines how the convolution is computed. This mostly affects behaviour at the boundaries.
#[derive(Debug)]
pub(crate) enum ConvolutionMode<F> {
    /// Returns the convolution at each point of overlap, assuming the signals wrap around.
    Wrap,
    /// Returns the convolution at each point of overlap, assuming the signals
    /// are extended by the given value.
    Extended(F),
}

/// Compute the discrete convolution of the two slices.
/// This might be slow, as this function is not optimised in any way.
pub(crate) fn convolve<F: Float>(a: &[F], b: &[F], mode: ConvolutionMode<F>) -> Vec<F> {
    let (a, b) = if a.len() < b.len() { (b, a) } else { (a, b) };

    match mode {
        ConvolutionMode::Wrap => convolve_wrap(a, b),
        ConvolutionMode::Extended(c) => convolve_extended(a, b, c),
    }
}

fn convolve_extended<F: Float>(signal: &[F], window: &[F], c: F) -> Vec<F> {
    let m = signal.len() as i64;
    let n = window.len() as i64;
    debug_assert!(m >= n);

    let mut result = Vec::default();
    for i in 0..m {
        let mut x = F::zero();
        for j in 0..n {
            let s_ij = {
                let ix = i - j + (n / 2);
                *signal.get(ix as usize).unwrap_or(&c)
            };
            let w_ij = *window.get(j as usize).unwrap_or(&c);
            x = x + s_ij * w_ij;
        }
        result.push(x)
    }
    result
}

fn convolve_wrap<F: Float>(signal: &[F], window: &[F]) -> Vec<F> {
    let m = signal.len() as i64;
    let n = window.len() as i64;
    debug_assert!(m >= n);

    let mut result = Vec::with_capacity(m as usize);
    result.resize_with(m as usize, F::zero);

    for i in 0..m {
        for j in 0..n {
            let s_ij = {
                let ix = (m + i - j + (n / 2)) % m;
                signal[ix as usize]
            };
            let w_ij = window[j as usize];
            result[i as usize] = result[i as usize] + (s_ij * w_ij);
        }
    }
    result
}

fn roll<T: Copy>(a: &[T], shift: i64) -> Vec<T> {
    let mut out = Vec::with_capacity(a.len());
    for i in 0..a.len() as i64 {
        let ix = (Wrapping(i) - Wrapping(shift)).0 % (a.len() as i64);
        let ix = if ix < 0 { ix + a.len() as i64 } else { ix };
        out.push(a[ix as usize])
    }
    out
}

fn shift_extend<T: Copy>(a: &[T], shift: i64, value: T) -> Vec<T> {
    let mut out: Vec<T> = Vec::with_capacity(a.len());
    for i in 0..a.len() as i64 {
        let ix = i - shift;
        out.push(*a.get(ix as usize).unwrap_or(&value))
    }
    out
}

pub(crate) enum ShiftMode<F> {
    Wrap,
    Extend(F),
}

pub(crate) fn shift<T: Copy>(a: &[T], shift: i64, mode: ShiftMode<T>) -> Vec<T> {
    match mode {
        ShiftMode::Wrap => roll(a, shift),
        ShiftMode::Extend(c) => shift_extend(a, shift, c),
    }
}

#[cfg(test)]
mod tests {
    use assert_approx_eq::assert_approx_eq;

    use super::*;

    #[test]
    fn test_convolve_extended() {
        let a = &[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0];
        let b = &[0.0, 1.0, 0.5];

        let result = convolve(a, b, ConvolutionMode::Extended(100.0));

        let reference = [51.0, 2.5, 4.0, 5.5, 7.0, 8.5, 10.0, 11.5, 13.0];
        dbg!(&result);
        dbg!(&reference);

        debug_assert_eq!(reference.len(), result.len());
        for i in 0..reference.len() {
            assert_approx_eq!(reference[i], result[i]);
        }
    }

    #[test]
    fn test_convolve_extended2() {
        let a = &[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0];
        let b = &[0.0, 1.0, 0.5, 10.0];

        let result = convolve(a, b, ConvolutionMode::Extended(100.0));

        let reference = [1002.5, 14., 25.5, 37., 48.5, 60., 71.5, 83., 184.5];
        dbg!(&result);
        dbg!(&reference);

        debug_assert_eq!(reference.len(), result.len());
        for i in 0..reference.len() {
            assert_approx_eq!(reference[i], result[i]);
        }
    }

    #[test]
    fn test_roll() {
        let a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

        let c = roll(&a, 2);

        debug_assert_eq!(10, c.len());
        debug_assert_eq!(8, c[0]);
        debug_assert_eq!(9, c[1]);
        debug_assert_eq!(0, c[2]);
        debug_assert_eq!(1, c[3]);
        debug_assert_eq!(2, c[4]);
        debug_assert_eq!(3, c[5]);
        debug_assert_eq!(4, c[6]);
        debug_assert_eq!(5, c[7]);
        debug_assert_eq!(6, c[8]);
        debug_assert_eq!(7, c[9]);
    }

    #[test]
    fn test_roll_negative() {
        let a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

        let c = roll(&a, -2);

        debug_assert_eq!(10, c.len());
        debug_assert_eq!(2, c[0]);
        debug_assert_eq!(3, c[1]);
        debug_assert_eq!(4, c[2]);
        debug_assert_eq!(5, c[3]);
        debug_assert_eq!(6, c[4]);
        debug_assert_eq!(7, c[5]);
        debug_assert_eq!(8, c[6]);
        debug_assert_eq!(9, c[7]);
        debug_assert_eq!(0, c[8]);
        debug_assert_eq!(1, c[9]);
    }

    #[test]
    fn test_shift_extend() {
        let a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

        let c = shift_extend(&a, 2, 100);

        debug_assert_eq!(10, c.len());
        debug_assert_eq!(100, c[0]);
        debug_assert_eq!(100, c[1]);
        debug_assert_eq!(0, c[2]);
        debug_assert_eq!(1, c[3]);
        debug_assert_eq!(2, c[4]);
        debug_assert_eq!(3, c[5]);
        debug_assert_eq!(4, c[6]);
        debug_assert_eq!(5, c[7]);
        debug_assert_eq!(6, c[8]);
        debug_assert_eq!(7, c[9]);

        let a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

        let c = shift_extend(&a, -2, 100);

        debug_assert_eq!(10, c.len());
        debug_assert_eq!(2, c[0]);
        debug_assert_eq!(3, c[1]);
        debug_assert_eq!(4, c[2]);
        debug_assert_eq!(5, c[3]);
        debug_assert_eq!(6, c[4]);
        debug_assert_eq!(7, c[5]);
        debug_assert_eq!(8, c[6]);
        debug_assert_eq!(9, c[7]);
        debug_assert_eq!(100, c[8]);
        debug_assert_eq!(100, c[9]);
    }
}