lcs_png_diff/
lib.rs

1use base64::{decode, encode, DecodeError};
2use image::io::Reader;
3use image::DynamicImage;
4use image::DynamicImage::ImageRgba8;
5use image::GenericImageView;
6use image::ImageBuffer;
7use image::Rgba;
8use std::io::Cursor;
9use std::{cmp, vec};
10
11pub static BLACK: (u8, u8, u8) = (0, 0, 0);
12pub static RED: (u8, u8, u8) = (255, 119, 119);
13pub static GREEN: (u8, u8, u8) = (99, 195, 99);
14static RATE: f32 = 0.25;
15
16#[derive(Debug, PartialEq)]
17enum DiffResult<'a, T: PartialEq> {
18    Removed(DiffElement<'a, T>),
19    Common(DiffElement<'a, T>),
20    Added(DiffElement<'a, T>),
21}
22
23#[derive(Debug, PartialEq)]
24struct DiffElement<'a, T: PartialEq> {
25    pub data: &'a T,
26}
27
28// Table is like:
29// \ o l d
30// n
31// e
32// w
33pub fn create_table<T: PartialEq>(old: &[T], new: &[T]) -> Vec<Vec<u32>> {
34    let new_len = new.len();
35    let old_len = old.len();
36    let mut table = vec![vec![0; old_len + 1]; new_len + 1];
37    for i in 0..new_len {
38        let i = new_len - i - 1;
39        for j in 0..old_len {
40            let j = old_len - j - 1;
41            // Performance bottle neck - long string comparison
42            table[i][j] = if new[i] == old[j] {
43                table[i + 1][j + 1] + 1
44            } else {
45                cmp::max(table[i + 1][j], table[i][j + 1])
46            }
47        }
48    }
49    table
50}
51
52fn lcs_diff<'a, T: PartialEq>(old: &'a [T], new: &'a [T]) -> Vec<DiffResult<'a, T>> {
53    let new_len = new.len();
54    let old_len = old.len();
55
56    if new_len == 0 {
57        let mut result = Vec::with_capacity(old_len);
58        let mut o = 0;
59        while o < old_len {
60            result.push(DiffResult::Removed(DiffElement { data: &old[o] }));
61            o += 1;
62        }
63        return result;
64    } else if old_len == 0 {
65        let mut result = Vec::with_capacity(new_len);
66        let mut n = 0;
67        while n < new_len {
68            result.push(DiffResult::Added(DiffElement { data: &new[n] }));
69            n += 1;
70        }
71        return result;
72    } else {
73        let mut o = 0;
74        let mut n = 0;
75        let common_prefix = old.iter().zip(new).take_while(|p| p.0 == p.1);
76        let prefix_size = common_prefix.count();
77        let common_suffix = old
78            .iter()
79            .rev()
80            .zip(new.iter().rev())
81            .take(cmp::min(old_len, new_len) - prefix_size)
82            .take_while(|p| p.0 == p.1);
83        let suffix_size = common_suffix.count();
84        let table = create_table(
85            &old[prefix_size..(old_len - suffix_size)],
86            &new[prefix_size..(new_len - suffix_size)],
87        );
88        let new_len = new_len - prefix_size - suffix_size;
89        let old_len = old_len - prefix_size - suffix_size;
90        let mut result = Vec::with_capacity(prefix_size + cmp::max(old_len, new_len) + suffix_size);
91
92        // Restore common prefix
93        let mut prefix_index = 0;
94        while prefix_index < prefix_size {
95            result.push(DiffResult::Common(DiffElement {
96                data: &old[prefix_index],
97            }));
98            prefix_index += 1;
99        }
100
101        loop {
102            if n >= new_len || o >= old_len {
103                break;
104            }
105            let new_index = n + prefix_size;
106            let old_index = o + prefix_size;
107            if new[new_index] == old[old_index] {
108                result.push(DiffResult::Common(DiffElement {
109                    data: &new[new_index],
110                }));
111                n += 1;
112                o += 1;
113            } else if table[n + 1][o] >= table[n][o + 1] {
114                result.push(DiffResult::Added(DiffElement {
115                    data: &new[new_index],
116                }));
117                n += 1;
118            } else {
119                result.push(DiffResult::Removed(DiffElement {
120                    data: &old[old_index],
121                }));
122                o += 1;
123            }
124        }
125        while n < new_len {
126            let new_index = n + prefix_size;
127            result.push(DiffResult::Added(DiffElement {
128                data: &new[new_index],
129            }));
130            n += 1;
131        }
132        while o < old_len {
133            let old_index = o + prefix_size;
134            result.push(DiffResult::Removed(DiffElement {
135                data: &old[old_index],
136            }));
137            o += 1;
138        }
139
140        // Restore common suffix
141        let mut suffix_index = 0;
142        while suffix_index < suffix_size {
143            let old_index = suffix_index + old_len + prefix_size;
144            result.push(DiffResult::Common(DiffElement {
145                data: &old[old_index],
146            }));
147            suffix_index += 1;
148        }
149        result
150    }
151}
152
153fn blend(base: Rgba<u8>, rgb: (u8, u8, u8), rate: f32) -> Rgba<u8> {
154    Rgba([
155        (base[0] as f32 * (1.0 - rate) + rgb.0 as f32 * (rate)) as u8,
156        (base[1] as f32 * (1.0 - rate) + rgb.1 as f32 * (rate)) as u8,
157        (base[2] as f32 * (1.0 - rate) + rgb.2 as f32 * (rate)) as u8,
158        base[3],
159    ])
160}
161
162fn put_diff_pixels(
163    y: usize,
164    img: &mut ImageBuffer<Rgba<u8>, Vec<u8>>,
165    row_width: u32,
166    data: &str,
167    rgb: (u8, u8, u8),
168    rate: f32,
169) -> Result<(), base64::DecodeError> {
170    let row = decode(data)?;
171    for x in 0..img.dimensions().0 {
172        let index = x as usize * 4;
173        let pixel = if row_width > x {
174            Rgba([row[index], row[index + 1], row[index + 2], row[index + 3]])
175        } else {
176            Rgba([0, 0, 0, 0])
177        };
178        img.put_pixel(x as u32, y as u32, blend(pixel, rgb, rate));
179    }
180    Ok(())
181}
182
183pub fn diff(
184    before_png: &DynamicImage,
185    after_png: &DynamicImage,
186) -> Result<DynamicImage, DecodeError> {
187    let after_w = after_png.dimensions().0;
188    let before_w = before_png.dimensions().0;
189    let before_encoded_png: Vec<String> = before_png
190        .as_bytes()
191        .chunks(before_w as usize * 4)
192        .map(encode)
193        .collect();
194    let after_encoded_png: Vec<String> = after_png
195        .as_bytes()
196        .chunks(after_w as usize * 4)
197        .map(encode)
198        .collect();
199
200    let diff_result = lcs_diff(&before_encoded_png, &after_encoded_png);
201
202    let height = diff_result.len() as u32;
203    let width = cmp::max(before_w, after_w) as u32;
204    let mut img = ImageBuffer::new(width, height);
205    for (y, d) in diff_result.iter().enumerate() {
206        match d {
207            DiffResult::Added(ref a) => {
208                put_diff_pixels(y, &mut img, after_w as u32, a.data, GREEN, RATE)?
209            }
210            DiffResult::Removed(ref r) => {
211                put_diff_pixels(y, &mut img, before_w as u32, r.data, RED, RATE)?
212            }
213            DiffResult::Common(ref c) => put_diff_pixels(y, &mut img, width, c.data, BLACK, 0.0)?,
214        }
215    }
216    Ok(ImageRgba8(img))
217}
218
219pub fn diff_slice(
220    before_slice: &[u8],
221    after_slice: &[u8],
222) -> Result<(Vec<u8>, u32, u32), DecodeError> {
223    let before_png = Reader::new(Cursor::new(before_slice))
224        .with_guessed_format()
225        .expect("Cursor io never fails")
226        .decode()
227        .expect("Unable to decode before_png");
228    let after_png = Reader::new(Cursor::new(after_slice))
229        .with_guessed_format()
230        .expect("Cursor io never fails")
231        .decode()
232        .expect("Unable to decode after_png");
233    diff(&before_png, &after_png).map(|img| {
234        (
235            img.as_bytes().to_vec(),
236            img.dimensions().0,
237            img.dimensions().1,
238        )
239    })
240}
241
242#[allow(dead_code)]
243fn gen_lcs<'a, T: PartialEq>(table: &Vec<Vec<u32>>, old: &[T], new: &'a [T]) -> Vec<&'a T> {
244    let o_len = old.len();
245    let n_len = new.len();
246    let mut o = 0;
247    let mut n = 0;
248    let mut res = vec![];
249    while o < o_len && n < n_len {
250        if old[o] == new[n] {
251            res.push(&new[n]);
252            o = o + 1;
253            n = n + 1; // Common
254        } else if table[n + 1][o] >= table[n][o + 1] {
255            n += 1; // Add from new
256        } else {
257            o += 1; // Remove from old
258        }
259    }
260    res
261}
262
263#[cfg(test)]
264mod tests {
265    use super::*;
266
267    #[test]
268    fn should_create_table_with_encode_pixel_array() {
269        let old = [
270            255, 255, 255, 5, 167, 167, 133, 7, 133, 71, 132, 4, 255, 255, 255, 10,
271        ];
272        let old_chunks: Vec<String> = old.to_vec().chunks(4).map(encode).collect();
273        let new = [
274            255, 255, 255, 5, 133, 71, 132, 4, 167, 167, 133, 7, 255, 255, 255, 10,
275        ];
276        let new_chunks: Vec<String> = new.to_vec().chunks(4).map(encode).collect();
277        let lcs_table = create_table(&old_chunks, &new_chunks);
278        assert_eq!(
279            vec!["////BQ==", "p6eFBw==", "////Cg=="],
280            gen_lcs(&lcs_table, &old_chunks, &new_chunks)
281        );
282        assert_eq!(vec![255, 255, 255, 5], decode("////BQ==").unwrap());
283        assert_eq!(vec![167, 167, 133, 7], decode("p6eFBw==").unwrap());
284        assert_eq!(vec![255, 255, 255, 10], decode("////Cg==").unwrap());
285        assert_eq!(3, lcs_table[0][0]);
286    }
287
288    #[test]
289    fn should_create_table_with_strings2() {
290        let old = [
291            "HH", "ee", "ll", "ll", "oo", "  ", "ww", "oo", "rr", "ll", "dd",
292        ];
293        let new = [
294            "HH", "aa", "cc", "kk", "yy", "ii", "nn", "  ", "oo", "oo", "zz",
295        ];
296        let lcs_table = create_table(&old, &new);
297        let expected = vec![
298            /* * * * * H  e  l  l  o  _  w  o  r  l  d  */
299            /*H*/ vec![3, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
300            /*a*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
301            /*c*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
302            /*k*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
303            /*y*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
304            /*i*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
305            /*n*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
306            /*_*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
307            /*o*/ vec![2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0],
308            /*o*/ vec![1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
309            /*z*/ vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
310            /* */ vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
311        ];
312        assert_eq!(
313            ["HH", "oo", "oo"].iter().collect::<Vec<_>>(),
314            gen_lcs(&lcs_table, &old, &new)
315        );
316        assert_eq!(expected, lcs_table);
317    }
318
319    #[test]
320    fn should_create_table_with_strings() {
321        let old = ["H", "e", "l", "l", "o", " ", "w", "o", "r", "l", "d"];
322        let new = ["H", "a", "c", "k", "y", "i", "n", " ", "o", "o", "z"];
323        let lcs_table = create_table(&old, &new);
324        let expected = vec![
325            /* * * * * H  e  l  l  o  _  w  o  r  l  d  */
326            /*H*/ vec![3, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
327            /*a*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
328            /*c*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
329            /*k*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
330            /*y*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
331            /*i*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
332            /*n*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
333            /*_*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
334            /*o*/ vec![2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0],
335            /*o*/ vec![1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
336            /*z*/ vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
337            /* */ vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
338        ];
339        assert_eq!(
340            ["H", "o", "o"].iter().collect::<Vec<_>>(),
341            gen_lcs(&lcs_table, &old, &new)
342        );
343        assert_eq!(expected, lcs_table);
344    }
345
346    #[test]
347    fn should_create_table_with_chars() {
348        let old = ['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd'];
349        let new = ['H', 'a', 'c', 'k', 'y', 'i', 'n', ' ', 'o', 'o', 'z'];
350        let lcs_table = create_table(&old, &new);
351        let expected = vec![
352            /* * * * * H  e  l  l  o  _  w  o  r  l  d  */
353            /*H*/ vec![3, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
354            /*a*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
355            /*c*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
356            /*k*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
357            /*y*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
358            /*i*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
359            /*n*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
360            /*_*/ vec![2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0],
361            /*o*/ vec![2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0],
362            /*o*/ vec![1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
363            /*z*/ vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
364            /* */ vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
365        ];
366        assert_eq!(
367            ['H', 'o', 'o'].iter().collect::<Vec<_>>(),
368            gen_lcs(&lcs_table, &old, &new)
369        );
370        assert_eq!(expected, lcs_table);
371    }
372
373    #[test]
374    fn should_create_table_with_numbers() {
375        let old = [1, 2, 3, 4];
376        let new = [2, 4];
377        let lcs_table = create_table(&old, &new);
378        let expected = vec![
379            vec![2, 2, 1, 1, 0],
380            vec![1, 1, 1, 1, 0],
381            vec![0, 0, 0, 0, 0],
382        ];
383        let res = gen_lcs(&lcs_table, &old, &new);
384        assert_eq!([2, 4].iter().collect::<Vec<_>>(), res);
385        assert_eq!(expected, lcs_table);
386    }
387}
lcs_png_diff/lib.rs

lcs_png_diff/
lib.rs
