#![no_std]

extern crate alloc;

use alloc::boxed::Box;
use alloc::vec::Vec;

trait ParallelReverse {
    fn swap_bits(self) -> Self;
}

impl ParallelReverse for u8 {
    #[inline]
    fn swap_bits(self) -> u8 {
        let mut v = self;

        // Swap odd and even bits
        v = ((v >> 1) & (0b01010101 as u8)) | ((v & (0b01010101 as u8)) << 1);
        // Swap consecutive pairs
        v = ((v >> 2) & (0b00110011 as u8)) | ((v & (0b00110011 as u8)) << 2);
        // Swap nibbles
        v = ((v >> 4) & (0b00001111 as u8)) | ((v & (0b00001111 as u8)) << 4);

        v
    }
}

macro_rules! with_codes (($clens:expr, $max_bits:expr => $code_ty:ty, $cb:expr) => ({
    let mut bl_count = [0 as $code_ty; ($max_bits+1)];
    for &bits in $clens.iter() {
        if bits != 0 {
            bl_count[bits as usize] += 1;
        }
    }

    let mut next_code = [0 as $code_ty; ($max_bits+1)];
    let mut code = 0 as $code_ty;

    for bits in 1..=$max_bits {
        code =
            code.checked_add(bl_count[bits as usize - 1])
                .ok_or_else(|| "Error generating huffman codes: Invalid set of code lengths")? << 1;
        next_code[bits as usize] = code;
    }

    for (i, &bits) in $clens.iter().enumerate() {
        if bits != 0 {
            let code = next_code[bits as usize];
            let new_code =
                code.checked_add(1)
                    .ok_or_else(|| "Error generating huffman codes: Invalid set of code lengths!")?;
            next_code[bits as usize] = new_code;
            match $cb(i as $code_ty, code, bits) {
                Ok(()) => (),
                Err(err) => return Err(err)
            }
        }
    }
}));

static mut PATTERNSBUFFER: [u8; 128] = [0xffu8; 128];

#[derive(Debug)]
struct CodeLengthReader {
    clens: Box<[u8; 19]>,
    result: Vec<u8>,
    num_lit: u16,
    num_dist: u8,
}

impl CodeLengthReader {
    fn new(
        clens: Box<[u8; 19]>,
        num_lit: u16,
        num_dist: u8,
    ) -> Result<CodeLengthReader, &'static str> {
        // Fill in the 7-bit patterns that match each code.
        unsafe {
            PATTERNSBUFFER.fill(0xffu8);
        };
        with_codes!(clens, 7 => u8, |i: u8, code: u8, bits| -> _ {
            let base = (code << (8 - bits as u8)).swap_bits();
            for rest in 0u8 .. 1u8 << (7 - bits) {
                unsafe {PATTERNSBUFFER[(base | (rest << bits)) as usize] = i};
            }
            Ok(())
        });

        Ok(CodeLengthReader {
            clens,
            result: Vec::with_capacity(num_lit as usize + num_dist as usize),
            num_lit,
            num_dist,
        })
    }

    fn read(&mut self, stream: &mut BitStream) -> Result<bool, &'static str> {
        let total_len = self.num_lit as usize + self.num_dist as usize;
        while self.result.len() < total_len {
            if !stream.need(7) {
                return Ok(false);
            }
            let save = stream.clone();
            macro_rules! take (($n:expr) => (match stream.take($n) {
                Some(v) => v,
                None => {
                    *stream = save;
                    return Ok(false);
                }
            }));
            let code = unsafe { PATTERNSBUFFER[(stream.state.v & 0x7f) as usize] };
            stream.take(match self.clens.get(code as usize) {
                Some(&len) => len,
                None => return Err("invalid length code"),
            });
            match code {
                0..=15 => self.result.push(code),
                16 => {
                    let last = match self.result.last() {
                        Some(&v) => v,
                        None => return Err("invalid length code"),
                    };
                    for _ in 0..3 + take!(2) {
                        self.result.push(last);
                    }
                }
                17 => {
                    for _ in 0..3 + take!(3) {
                        self.result.push(0);
                    }
                }
                18 => {
                    for _ in 0..11 + take!(7) {
                        self.result.push(0);
                    }
                }
                _ => unreachable!(),
            }
        }
        Ok(true)
    }

    fn to_lit_and_dist(&self) -> Result<(DynHuffman16, DynHuffman16), &'static str> {
        let num_lit = self.num_lit as usize;
        let lit = DynHuffman16::new(&self.result[..num_lit], DynHuffmanType::LIT)?;
        let dist = DynHuffman16::new(&self.result[num_lit..], DynHuffmanType::DIST)?;
        Ok((lit, dist))
    }
}

#[derive(Debug)]
struct Trie8bit {
    data: [u16; 16],
    children: [Option<Box<[u16; 16]>>; 16],
}

static mut DYNLITBUFFER: [u16; 256] = [0; 256];
static mut DYNDISTBUFFER: [u16; 256] = [0; 256];

enum DynHuffmanType {
    LIT,
    DIST,
}

#[derive(Debug)]
struct DynHuffman16 {
    patterns: &'static mut [u16; 256],
    rest: Vec<Trie8bit>,
}

impl DynHuffman16 {
    fn new(clens: &[u8], ty: DynHuffmanType) -> Result<DynHuffman16, &'static str> {
        let patterns = unsafe {
            match ty {
                DynHuffmanType::LIT => &mut DYNLITBUFFER,
                DynHuffmanType::DIST => &mut DYNDISTBUFFER,
            }
        };
        patterns.fill(0xffffu16);
        let mut rest = Vec::new();
        with_codes!(clens, 15 => u16, |i: u16, code: u16, bits: u8| -> _ {
            let entry = i | (u16::from(bits) << 12);
            if bits <= 8 {
                let base = match u8::try_from(code << (8 - bits)) {
                    Ok(v) => v.swap_bits(),
                    _ => return Err("invalid length code")
                };
                for rest in 0u8 .. 1 << (8 - bits) {
                    patterns[(base | (rest << (bits & 7))) as usize] = entry;
                }
            } else {
                let low = match u8::try_from(code >> (bits - 8)) {
                    Ok(v) => v.swap_bits(),
                    _ => return Err("invalid length code")
                };
                let high = (code << (16 - bits)) & 0xff;
                let high = (high as u8).swap_bits();
                let (min_bits, idx) = if patterns[low as usize] != 0xffff {
                    let bits_prev = (patterns[low as usize] >> 12) as u8;
                    (core::cmp::min(bits_prev, bits), patterns[low as usize] & 0x7ff)
                } else {
                    rest.push(Trie8bit {
                        data: [0xffff; 16],
                        children: [
                            None, None, None, None,
                            None, None, None, None,
                            None, None, None, None,
                            None, None, None, None
                        ]
                    });
                    (bits, (rest.len() - 1) as u16)
                };
                patterns[low as usize] = idx | 0x800 | (u16::from(min_bits) << 12);
                let trie_entry = match rest.get_mut(idx as usize) {
                    Some(v) => v,
                    None => return Err("invalid huffman code")
                };
                if bits <= 12 {
                    for rest in 0u8 .. 1 << (12 - bits) {
                        trie_entry.data[(high | (rest << (bits - 8))) as usize] = entry;
                    }
                } else {
                    let child = &mut trie_entry.children[(high & 0xf) as usize];
                    if child.is_none() {
                        *child = Some(Box::new([0xffff; 16]));
                    }
                    let child = &mut **child.as_mut().unwrap();
                    let high_top = high >> 4;
                    for rest in 0u8 .. 1 << (16 - bits) {
                        child[(high_top | (rest << (bits - 12))) as usize] = entry;
                    }
                }
            }
            Ok(())
        });
        Ok(DynHuffman16 { patterns, rest })
    }

    fn read<'a>(
        &self,
        stream: &mut BitStream<'a>,
    ) -> Result<Option<(BitStream<'a>, u16)>, &'static str> {
        let has8 = stream.need(8);
        let entry = self.patterns[(stream.state.v & 0xff) as usize];
        let bits = (entry >> 12) as u8;

        Ok(if !has8 {
            if bits <= stream.state.n {
                let save = stream.clone();
                stream.state.n -= bits;
                stream.state.v >>= bits;
                Some((save, entry & 0xfff))
            } else {
                None
            }
        } else if bits <= 8 {
            let save = stream.clone();
            stream.state.n -= bits;
            stream.state.v >>= bits;
            Some((save, entry & 0xfff))
        } else {
            let has16 = stream.need(16);
            let trie = match self.rest.get((entry & 0x7ff) as usize) {
                Some(trie) => trie,
                None => return Err("invalid entry in stream"),
            };
            let idx = stream.state.v >> 8;
            let trie_entry = match trie.children[(idx & 0xf) as usize] {
                Some(ref child) => child[((idx >> 4) & 0xf) as usize],
                None => trie.data[(idx & 0xf) as usize],
            };
            let trie_bits = (trie_entry >> 12) as u8;
            if has16 || trie_bits <= stream.state.n {
                let save = stream.clone();
                stream.state.n -= trie_bits;
                stream.state.v >>= trie_bits;
                Some((save, trie_entry & 0xfff))
            } else {
                None
            }
        })
    }
}

#[derive(Debug)]
enum BitsNext {
    BlockHeader,
    BlockUncompressedLen,
    BlockUncompressedNLen(u16),
    BlockDynHlit,
    BlockDynHdist(u8),
    BlockDynHclen(u8, u8),
    BlockDynClenCodeLengths(u8, u8, u8, u8, Box<[u8; 19]>),
    BlockDynCodeLengths(CodeLengthReader),
    BlockDyn(DynHuffman16, DynHuffman16, u16),
}
use BitsNext::*;

enum State {
    Bits(BitsNext, BitState),
    LenDist((BitsNext, BitState), u16, u16),
    Uncompressed(u16),
    CheckCRC,
    Finished,
}
use State::*;

#[derive(Copy, Clone, Debug)]
struct BitState {
    n: u8,
    v: u32,
}

#[derive(Clone)]
struct BitStream<'a> {
    bytes: core::slice::Iter<'a, u8>,
    used: usize,
    state: BitState,
}

impl<'a> BitStream<'a> {
    fn new(bytes: &'a [u8], state: BitState) -> BitStream<'a> {
        BitStream {
            bytes: bytes.iter(),
            used: 0,
            state,
        }
    }

    fn fill(&mut self) -> BitState {
        while self.state.n + 8 <= 32 && self.use_byte() {}
        self.state
    }

    fn use_byte(&mut self) -> bool {
        match self.bytes.next() {
            Some(&b) => {
                self.state.v |= u32::from(b) << self.state.n;
                self.state.n += 8;
                self.used += 1;
                true
            }
            None => false,
        }
    }

    fn need(&mut self, n: u8) -> bool {
        if self.state.n < n {
            if !self.use_byte() {
                return false;
            }
            if n > 8 && self.state.n < n {
                assert!(n <= 16);
                if !self.use_byte() {
                    return false;
                }
            }
        }
        true
    }

    fn take16(&mut self, n: u8) -> Option<u16> {
        if self.need(n) {
            self.state.n -= n;
            let v = self.state.v & ((1 << n) - 1);
            self.state.v >>= n;
            Some(v as u16)
        } else {
            None
        }
    }

    fn take(&mut self, n: u8) -> Option<u8> {
        assert!(n <= 8);
        self.take16(n).map(|v: u16| v as u8)
    }

    fn align_byte(&mut self) {
        if self.state.n > 0 {
            let n = self.state.n % 8;
            self.take(n);
        }
    }
}

pub struct InflateStream {
    buffer: Vec<u8>,
    pos: u16,
    state: Option<State>,
    final_block: bool,
}

impl InflateStream {
    pub fn new() -> Self {
        let state = Bits(BlockHeader, BitState { n: 0, v: 0 });
        let buffer = Vec::with_capacity(32 * 1024);

        InflateStream {
            buffer: buffer,
            pos: 0,
            state: Some(state),
            final_block: false,
        }
    }

    fn run_len_dist(&mut self, len: u16, dist: u16) -> Result<Option<u16>, &'static str> {
        if dist < 1 {
            return Err("invalid run length in stream 0");
        }
        // `buffer_size` is used for validating `unsafe` below, handle with care
        let buffer_size = self.buffer.capacity() as u16;
        let len = if self.pos < dist {
            // Handle copying from ahead, until we hit the end reading.
            let pos_end = self.pos + len;
            let (pos_end, left) = if pos_end < dist {
                (pos_end, 0)
            } else {
                (dist, pos_end - dist)
            };
            if dist > buffer_size {
                return Err("run length distance is bigger than the window size");
            }
            let forward = buffer_size - dist;
            if pos_end + forward > self.buffer.len() as u16 {
                return Err("invalid run length in stream 1");
            }

            for i in self.pos as usize..pos_end as usize {
                self.buffer[i] = self.buffer[i + forward as usize];
            }
            self.pos = pos_end;
            left
        } else {
            len
        };
        // Handle copying from before, until we hit the end writing.
        let pos_end = self.pos + len;
        let (pos_end, left) = if pos_end <= buffer_size {
            (pos_end, None)
        } else {
            (buffer_size, Some(pos_end - buffer_size))
        };

        if self.pos < dist && pos_end > self.pos {
            return Err("invalid run length in stream 2");
        }

        if self.buffer.len() < pos_end as usize {
            // ensure the buffer length will not exceed the amount of allocated memory
            assert!(pos_end <= buffer_size);
            // ensure that the uninitialized chunk of memory will be fully overwritten
            assert!(self.pos as usize <= self.buffer.len());
            unsafe {
                self.buffer.set_len(pos_end as usize);
            }
        }
        assert!(dist > 0); // validation against reading uninitialized memory
        for i in self.pos as usize..pos_end as usize {
            self.buffer[i] = self.buffer[i - dist as usize];
        }
        self.pos = pos_end;
        Ok(left)
    }

    fn next_state(&mut self, data: &[u8]) -> Result<usize, &'static str> {
        macro_rules! ok_bytes (($n:expr, $state:expr) => ({
            self.state = Some($state);
            Ok($n)
        }));
        macro_rules! push_or (($b:expr, $ret:expr) => (if self.pos < self.buffer.capacity() as u16 {
            let b = $b;
            if (self.pos as usize) < self.buffer.len() {
                self.buffer[self.pos as usize] = b;
            } else {
                assert_eq!(self.pos as usize, self.buffer.len());
                self.buffer.push(b);
            }
            self.pos += 1;
        } else {
            return $ret;
        }));

        macro_rules! run_len_dist (($len:expr, $dist:expr => ($bytes:expr, $next:expr, $state:expr)) => ({
            let dist = $dist;
            let left = self.run_len_dist($len, dist)?;
            if let Some(len) = left {
                return ok_bytes!($bytes, LenDist(($next, $state), len, dist));
            }
        }));

        let state = self.state.take().unwrap();

        match state {
            Bits(next, state) => {
                let mut stream = BitStream::new(data, state);
                macro_rules! ok_state (($state:expr) => ({self.state = Some($state); Ok(stream.used)}));
                macro_rules! ok (($next:expr) => (ok_state!(Bits($next, stream.fill()))));
                macro_rules! take (
                    ($n:expr => $next:expr) => (match stream.take($n) {
                        Some(v) => v,
                        None => return ok!($next)
                    });
                    ($n:expr) => (take!($n => next))
                );
                macro_rules! take16 (
                    ($n:expr => $next:expr) => (match stream.take16($n) {
                        Some(v) => v,
                        None => return ok!($next)
                    });
                    ($n:expr) => (take16!($n => next))
                );
                macro_rules! len_dist (
                    ($len:expr, $code:expr, $bits:expr => $next_early:expr, $next:expr) => ({
                        let dist = 1 + if $bits == 0 { 0 } else { // new_base
                            2 << $bits
                        } + (($code as u16 - if $bits == 0 { 0 } else { // old_base
                            $bits * 2 + 2
                        }) << $bits) + take16!($bits => $next_early) as u16;
                        run_len_dist!($len, dist => (stream.used, $next, stream.state));
                    });
                    ($len:expr, $code:expr, $bits:expr) => (
                        len_dist!($len, $code, $bits => next, next)
                    )
                );
                match next {
                    BlockHeader => {
                        if self.final_block {
                            return ok_state!(CheckCRC);
                        }
                        let h = take!(3);
                        let (final_, block_type) = ((h & 1) != 0, (h >> 1) & 0b11);

                        self.final_block = final_;

                        match block_type {
                            0 => {
                                // Skip to the next byte for an uncompressed block.
                                stream.align_byte();
                                ok!(BlockUncompressedLen)
                            }
                            1 => {
                                // Unwrap is safe because the data is valid.
                                let lit = DynHuffman16::new(
                                    &[
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 0-15
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 16-31
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 32-47
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 48-63
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 64-79
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 80-95
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 96-101
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 112-127
                                        8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
                                        8, // 128-143
                                        9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
                                        9, // 144-159
                                        9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
                                        9, // 160-175
                                        9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
                                        9, // 176-191
                                        9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
                                        9, // 192-207
                                        9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
                                        9, // 208-223
                                        9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
                                        9, // 224-239
                                        9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
                                        9, // 240-255
                                        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                        7, // 256-271
                                        7, 7, 7, 7, 7, 7, 7, 7, // 272-279
                                        8, 8, 8, 8, 8, 8, 8, 8, // 280-287
                                    ],
                                    DynHuffmanType::LIT,
                                )
                                .unwrap();

                                #[rustfmt::skip]
                                let dist = DynHuffman16::new(&[
                                    5, 5, 5, 5, 5, 5, 5, 5,
                                    5, 5, 5, 5, 5, 5, 5, 5,
                                    5, 5, 5, 5, 5, 5, 5, 5,
                                    5, 5, 5, 5, 5, 5, 5, 5
                                ], DynHuffmanType::DIST).unwrap();
                                ok!(BlockDyn(lit, dist, 0))
                            }
                            2 => ok!(BlockDynHlit),
                            _ => Err("unimplemented DEFLATE block type"),
                        }
                    }
                    BlockUncompressedLen => {
                        let len = take16!(16);
                        ok_state!(Bits(BlockUncompressedNLen(len), stream.state))
                    }
                    BlockUncompressedNLen(len) => {
                        let nlen = take16!(16);
                        assert_eq!(stream.state.n, 0);
                        if !len != nlen {
                            return Err("invalid uncompressed block len");
                        }
                        ok_state!(Uncompressed(len))
                    }
                    BlockDynHlit => ok!(BlockDynHdist(take!(5) + 1)),
                    BlockDynHdist(hlit) => ok!(BlockDynHclen(hlit, take!(5) + 1)),
                    BlockDynHclen(hlit, hdist) => ok!(BlockDynClenCodeLengths(
                        hlit,
                        hdist,
                        take!(4) + 4,
                        0,
                        Box::new([0; 19])
                    )),
                    BlockDynClenCodeLengths(hlit, hdist, hclen, i, mut clens) => {
                        let v = match stream.take(3) {
                            Some(v) => v,
                            None => {
                                return ok!(BlockDynClenCodeLengths(hlit, hdist, hclen, i, clens))
                            }
                        };
                        clens[[
                            16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
                        ][i as usize]] = v;
                        if i < hclen - 1 {
                            ok!(BlockDynClenCodeLengths(hlit, hdist, hclen, i + 1, clens))
                        } else {
                            ok!(BlockDynCodeLengths(CodeLengthReader::new(
                                clens,
                                u16::from(hlit) + 256,
                                hdist
                            )?))
                        }
                    }
                    BlockDynCodeLengths(mut reader) => {
                        let finished = reader.read(&mut stream)?;
                        if finished {
                            let (lit, dist) = reader.to_lit_and_dist()?;
                            ok!(BlockDyn(lit, dist, 0))
                        } else {
                            ok!(BlockDynCodeLengths(reader))
                        }
                    }
                    BlockDyn(huff_lit_len, huff_dist, mut prev_len) => {
                        macro_rules! next (($save_len:expr) => (BlockDyn(huff_lit_len, huff_dist, $save_len)));
                        loop {
                            let len = if prev_len != 0 {
                                let len = prev_len;
                                prev_len = 0;
                                len
                            } else {
                                let (save, code16) = match huff_lit_len.read(&mut stream)? {
                                    Some(data) => data,
                                    None => return ok!(next!(0)),
                                };
                                let code = code16 as u8;
                                match code16 {
                                    0..=255 => {
                                        push_or!(
                                            code,
                                            ok!({
                                                stream = save;
                                                next!(0)
                                            })
                                        );
                                        continue;
                                    }
                                    256..=285 => {}
                                    _ => return Err("bad DEFLATE len code"),
                                }

                                macro_rules! len (($code:expr, $bits:expr) => (
                                    3 + if $bits == 0 { 0 } else { // new_base
                                        4 << $bits
                                    } + ((if $code == 29 {
                                        256
                                    } else {
                                        $code as u16
                                    } - if $bits == 0 { 0 } else { // old_base
                                        $bits * 4 + 4
                                    } - 1) << $bits) + take!($bits => {stream = save; next!(0)}) as u16
                                ));
                                match code {
                                    0 => {
                                        return if self.final_block {
                                            ok_state!(CheckCRC)
                                        } else {
                                            ok!(BlockHeader)
                                        }
                                    }
                                    1..=8 => len!(code, 0),
                                    9..=12 => len!(code, 1),
                                    13..=16 => len!(code, 2),
                                    17..=20 => len!(code, 3),
                                    21..=24 => len!(code, 4),
                                    25..=28 => len!(code, 5),
                                    29 => len!(29, 0),
                                    _ => return Err("bad DEFLATE len code"),
                                }
                            };

                            let (save, dist_code) = match huff_dist.read(&mut stream)? {
                                Some(data) => data,
                                None => return ok!(next!(len)),
                            };
                            macro_rules! len_dist_case (($bits:expr) => (
                                len_dist!(len, dist_code, $bits => {stream = save; next!(len)}, next!(0))
                            ));
                            match dist_code {
                                0..=3 => len_dist_case!(0),
                                4..=5 => len_dist_case!(1),
                                6..=7 => len_dist_case!(2),
                                8..=9 => len_dist_case!(3),
                                10..=11 => len_dist_case!(4),
                                12..=13 => len_dist_case!(5),
                                14..=15 => len_dist_case!(6),
                                16..=17 => len_dist_case!(7),
                                18..=19 => len_dist_case!(8),
                                20..=21 => len_dist_case!(9),
                                22..=23 => len_dist_case!(10),
                                24..=25 => len_dist_case!(11),
                                26..=27 => len_dist_case!(12),
                                28..=29 => len_dist_case!(13),
                                _ => return Err("bad DEFLATE dist code"),
                            }
                        }
                    }
                }
            }
            LenDist((next, state), len, dist) => {
                run_len_dist!(len, dist => (0, next, state));
                ok_bytes!(0, Bits(next, state))
            }
            CheckCRC => {
                return ok_bytes!(0, Finished);
            }
            Finished => {
                ok_bytes!(data.len(), Finished)
            }
            _ => Err("Invalid method"),
        }
    }

    pub fn update<'a>(&'a mut self, mut data: &[u8]) -> Result<(usize, &'a [u8]), &'static str> {
        let original_size = data.len();
        let original_pos = self.pos as usize;
        let mut empty = false;

        while !empty
            && ((self.pos as usize) < self.buffer.capacity() || self.buffer.capacity() == 0)
        {
            empty = data.is_empty();
            match self.next_state(data) {
                Ok(n) => {
                    data = &data[n..];
                }
                Err(e) => return Err(e),
            }
        }
        let output = &self.buffer[original_pos..self.pos as usize];
        if self.pos as usize >= self.buffer.capacity() {
            self.pos = 0;
        }

        Ok((original_size - data.len(), output))
    }
}

fn inflate(inflater: &mut InflateStream, data: &[u8]) -> Result<Vec<u8>, &'static str> {
    let mut decoded = Vec::<u8>::new();

    let mut n = 0;
    loop {
        let (num_bytes_read, bytes) = inflater.update(&data[n..])?;
        if bytes.is_empty() {
            break;
        }
        n += num_bytes_read;
        decoded.extend_from_slice(bytes);
    }
    Ok(decoded)
}

pub fn inflate_bytes(data: &[u8]) -> Result<Vec<u8>, &'static str> {
    inflate(&mut InflateStream::new(), data)
}