zippopotamus 0.1.2

Lazy implementation of zip
Documentation 
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


use std::collections::HashMap;
use std::cmp::min;
use std::fmt::Error;
//try using a trie to see if there's a speedup
//use qp_trie::Trie;

//usize for convenience in slices even though it can only actually
//use 16 bits
///How far back a match can be found. Must be a power of 2 - 1
const WINDOW_LEN: usize = 32767;
// const _: () = assert!(WINDOW_LEN > 0 && (WINDOW_LEN & (WINDOW_LEN + 1)) == 0,
//     "WINDOW_LEN must be a power of 2 minus 1");

const MAX_MATCH_LEN: usize = 255;//((65536 / (WINDOW_LEN + 1)) - 1) as u16;

// const OFFSET_BITS: usize = (WINDOW_LEN + 1).ilog2() as usize;
// const LEN_BITS: usize = 16 - OFFSET_BITS;


struct Match {
    len: u8,
    offset: u16,
    next_symbol: u8,
}

pub fn lz77_encode(source: &[u8]) -> Vec<u8> {
    let mut search_buf: &[u8] = &[];
    let mut lookahead_buf = &source[0..min(WINDOW_LEN, source.len())];

    let mut output = Vec::<u8>::new();

    //starting index of lookahead buffer
    let mut cursor: usize = 0;

    while lookahead_buf.len() > 0 {
        let mut best_match = Match::with_symbol(source[cursor]);

        let mut sb_iter = search_buf.iter().enumerate().peekable();

        //for each byte in the search buffer
        while sb_iter.peek().is_some() {
            let sb_pos = sb_iter.peek().unwrap().0;

            let mut inner_sb_iter = sb_iter.clone().cycle();
            let mut match_len = 0;

            //iterate over the lookahead buffer, and find the longest match
            //starting from our current position in the search buffer
            for (lb_pos, lb_symbol) in lookahead_buf.iter().enumerate() {
                let sb_symbol = inner_sb_iter.next().unwrap().1;

                if sb_symbol == lb_symbol {
                    match_len += 1;
                }
                //if symbols are mismatched or the loop is ending,
                //check the match and restart counter
                if sb_symbol != lb_symbol || lb_pos == lookahead_buf.len()-1 || match_len == MAX_MATCH_LEN {

                    //check if our current match is the longest one, and
                    //update it as our best match if so
                    if match_len as u8 > best_match.len {
                        best_match.len = match_len as u8;
                        // - cursor.saturating_sub(WINDOW_LEN)
                        best_match.offset = (search_buf.len() - sb_pos) as u16;
                        best_match.next_symbol = lookahead_buf[min(match_len as usize, lookahead_buf.len()-1)];
                    }

                    break;
                }
            }

            sb_iter.next();
        }

        //output best match as a (length:offset:next_symbol) tuple
        output.push(best_match.len);
        output.push((best_match.offset >> 8) as u8);
        output.push(best_match.offset as u8);
        output.push(best_match.next_symbol);

        //advance by the length of the match we found
        cursor += best_match.len as usize + 1;

        if cursor >= source.len() { break; }
        //expand search buffer until it reaches size WINDOW_LEN, then shift to right
        search_buf = &source[cursor.saturating_sub(WINDOW_LEN)..cursor];
        //vice versa
        lookahead_buf = &source[cursor..min(WINDOW_LEN+cursor, source.len())];
    }

    output
}

pub fn lz77_decode(source: &[u8]) -> Result<Vec<u8>, Error> {
    let mut output = Vec::new();

    let mut iter = source.iter();

    //extract length, offset and next symbol
    while let Some(&len) = iter.next() {
        let first_off_byte = *iter.next().ok_or(Error)? as u16;
        let second_off_byte = *iter.next().ok_or(Error)? as u16;

        let offset = (first_off_byte << 8) | second_off_byte;

        let next_symbol = *iter.next().ok_or(Error)?;


        let start = output.len() - offset as usize;
        for i in start..start+len as usize {
            output.push(output[i % output.len()]);
        }

        output.push(next_symbol);
    }

    Ok(output)
}


impl Match {
    pub fn new() -> Self { Match { len: 0, offset: 0, next_symbol: 0 } }

    pub fn with_symbol(symbol: u8) -> Self {
        Match { len: 0, offset: 0, next_symbol: symbol }
    }
}

//experimental ting u should try l8r
pub fn trie_encode(source: &[u8]) {

}