Skip to content

Windows shell replacement in Rust: taskbar, file manager, NTFS search, task manager, disk cleaner. One installer exe.

Rust
59.5 KB
Raw Blame
//! Our own ZIP: CRC-32, inflate, deflate (LZ77 + dynamic Huffman) and the container with ZIP64. No crates.
//! shortcuts: encrypted entries and methods other than stored / deflate are refused (upgrade when someone needs them); a sample
//! with random-looking bytes is stored without trying to compress it, so a repeated random block would not be squeezed.
use std::{
    fs,
    io::{self, BufWriter, Read, Seek, SeekFrom, Write},
    path::{Component, Path, PathBuf},
    time::{Duration, SystemTime, UNIX_EPOCH},
};

// ---------- CRC-32 ----------

const fn crc_tables() -> [[u32; 256]; 8] {
    let mut t = [[0u32; 256]; 8];
    let mut i = 0;
    while i < 256 {
        let mut c = i as u32;
        let mut k = 0;
        while k < 8 {
            c = if c & 1 != 0 { 0xEDB8_8320 ^ (c >> 1) } else { c >> 1 };
            k += 1;
        }
        t[0][i] = c;
        i += 1;
    }
    let mut i = 0;
    while i < 256 {
        let mut s = 1;
        while s < 8 {
            t[s][i] = (t[s - 1][i] >> 8) ^ t[0][(t[s - 1][i] & 0xFF) as usize];
            s += 1;
        }
        i += 1;
    }
    t
}
static CRC: [[u32; 256]; 8] = crc_tables();

/// CRC-32 of `data` continuing `crc` (start with 0).
pub fn crc32(crc: u32, data: &[u8]) -> u32 {
    let mut c = !crc;
    let mut ch = data.chunks_exact(8);
    for b in &mut ch {
        let lo = u32::from_le_bytes([b[0], b[1], b[2], b[3]]) ^ c;
        let hi = u32::from_le_bytes([b[4], b[5], b[6], b[7]]);
        c = CRC[7][(lo & 0xFF) as usize]
            ^ CRC[6][((lo >> 8) & 0xFF) as usize]
            ^ CRC[5][((lo >> 16) & 0xFF) as usize]
            ^ CRC[4][(lo >> 24) as usize]
            ^ CRC[3][(hi & 0xFF) as usize]
            ^ CRC[2][((hi >> 8) & 0xFF) as usize]
            ^ CRC[1][((hi >> 16) & 0xFF) as usize]
            ^ CRC[0][(hi >> 24) as usize];
    }
    for &b in ch.remainder() {
        c = CRC[0][((c ^ b as u32) & 0xFF) as usize] ^ (c >> 8);
    }
    !c
}

// ---------- shared deflate tables ----------

const LBASE: [u16; 29] = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258];
const LEXT: [u8; 29] = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0];
const DBASE: [u16; 30] = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577];
const DEXT: [u8; 30] = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13];
const CL_ORDER: [usize; 19] = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];

const fn len_codes() -> [u8; 259] {
    let mut t = [0u8; 259];
    let mut c = 0;
    while c < 29 {
        let mut l = LBASE[c] as usize;
        let end = if c == 28 { 259 } else { LBASE[c + 1] as usize };
        while l < end {
            t[l] = c as u8;
            l += 1;
        }
        c += 1;
    }
    t[258] = 28;
    t
}
static LEN_CODE: [u8; 259] = len_codes();

fn dist_code(d: usize) -> usize {
    let x = d - 1;
    if x < 4 {
        x
    } else {
        let l = (usize::BITS - 1 - x.leading_zeros()) as usize;
        2 * l + ((x >> (l - 1)) & 1)
    }
}

fn rev_bits(mut c: u32, n: u32) -> u32 {
    let mut r = 0;
    for _ in 0..n {
        r = (r << 1) | (c & 1);
        c >>= 1;
    }
    r
}

// ---------- deflate ----------

/// Code lengths (at most `limit`) of a canonical Huffman code for these frequencies; the code is complete.
fn code_lengths(freq: &[u32], limit: u32) -> Vec<u8> {
    let mut len = vec![0u8; freq.len()];
    let used: Vec<usize> = (0..freq.len()).filter(|&i| freq[i] > 0).collect();
    match used.len() {
        0 => return len,
        1 => {
            len[used[0]] = 1;
            return len;
        }
        _ => {}
    }
    // Huffman tree by a heap; the depth of a leaf is its length
    let mut parent = vec![usize::MAX; freq.len() + used.len()];
    let mut heap = std::collections::BinaryHeap::new();
    for &i in &used {
        heap.push(std::cmp::Reverse((freq[i] as u64, i)));
    }
    let mut next = freq.len();
    while heap.len() > 1 {
        let std::cmp::Reverse((fa, a)) = heap.pop().unwrap();
        let std::cmp::Reverse((fb, b)) = heap.pop().unwrap();
        parent[a] = next;
        parent[b] = next;
        heap.push(std::cmp::Reverse((fa + fb, next)));
        next += 1;
    }
    for &i in &used {
        let (mut d, mut n) = (0u32, i);
        while parent[n] != usize::MAX {
            n = parent[n];
            d += 1;
        }
        len[i] = d.min(limit) as u8;
    }
    // the clamp can oversubscribe the code: lengthen the cheapest codes until it fits, then spend the slack on the commonest
    let unit = |l: u8| 1u64 << (limit - l as u32);
    let mut kraft: u64 = used.iter().map(|&i| unit(len[i])).sum();
    let full = 1u64 << limit;
    let mut by_freq = used.clone();
    by_freq.sort_by_key(|&i| std::cmp::Reverse(freq[i]));
    while kraft > full {
        let i = *used.iter().filter(|&&i| (len[i] as u32) < limit).max_by_key(|&&i| (len[i], std::cmp::Reverse(freq[i]))).unwrap();
        kraft -= unit(len[i]) / 2; // len -> len + 1 halves its share
        len[i] += 1;
    }
    loop {
        let mut changed = false;
        for &i in &by_freq {
            if kraft < full && len[i] > 1 && full - kraft >= unit(len[i]) {
                kraft += unit(len[i]); // len -> len - 1 doubles its share: adds one more of the same
                len[i] -= 1;
                changed = true;
            }
        }
        if kraft == full || !changed {
            break;
        }
    }
    len
}

/// Canonical codes for the lengths, already bit-reversed for the LSB-first stream.
fn codes(len: &[u8]) -> Vec<u32> {
    let mut count = [0u32; 16];
    for &l in len {
        count[l as usize] += 1;
    }
    count[0] = 0;
    let (mut next, mut code) = ([0u32; 16], 0u32);
    for b in 1..16 {
        code = (code + count[b - 1]) << 1;
        next[b] = code;
    }
    len.iter()
        .map(|&l| {
            if l == 0 {
                return 0;
            }
            let c = next[l as usize];
            next[l as usize] += 1;
            rev_bits(c, l as u32)
        })
        .collect()
}

struct BitW {
    acc: u64,
    n: u32,
}

impl BitW {
    fn put(&mut self, out: &mut Vec<u8>, v: u32, bits: u32) {
        self.acc |= (v as u64) << self.n;
        self.n += bits;
        while self.n >= 8 {
            out.push(self.acc as u8);
            self.acc >>= 8;
            self.n -= 8;
        }
    }
    fn align(&mut self, out: &mut Vec<u8>) {
        if self.n > 0 {
            out.push(self.acc as u8);
            self.acc = 0;
            self.n = 0;
        }
    }
}

const WIN: usize = 32768;
const HASH_BITS: u32 = 15;
const MAX_CHAIN: u32 = 16;
const LAZY_BELOW: u32 = 16;

/// Deflate with a bit stream that continues across chunks; a match may reach back into the last 32 KB of the previous chunk.
pub struct Deflater {
    bw: BitW,
    head: Vec<u32>,
    prev: Vec<u32>,
    next_ins: usize,
    hist: Vec<u8>,
}

/// Bytes that look random (an already compressed file): not worth a match search. Order-0 entropy of 8 samples of 512 bytes.
fn looks_random(d: &[u8]) -> bool {
    if d.len() < 4096 {
        return false;
    }
    let mut count = [0u32; 256];
    let step = d.len() / 8;
    for k in 0..8 {
        for &b in &d[k * step..k * step + 512] {
            count[b as usize] += 1;
        }
    }
    let h: f64 = count.iter().filter(|&&c| c > 0).map(|&c| { let p = c as f64 / 4096.0; -p * p.log2() }).sum();
    h > 7.8
}

impl Deflater {
    pub fn new() -> Self {
        Deflater { bw: BitW { acc: 0, n: 0 }, head: vec![u32::MAX; 1 << HASH_BITS], prev: vec![u32::MAX; WIN], next_ins: 0, hist: Vec::new() }
    }

    fn hash(d: &[u8], i: usize) -> usize {
        let v = u32::from_le_bytes([d[i], d[i + 1], d[i + 2], d[i + 3]]);
        (v.wrapping_mul(0x9E37_79B1) >> (32 - HASH_BITS)) as usize
    }

    fn ins(&mut self, d: &[u8], i: usize) {
        if i >= self.next_ins && i + 4 <= d.len() {
            let h = Self::hash(d, i);
            self.prev[i & (WIN - 1)] = self.head[h];
            self.head[h] = i as u32;
            self.next_ins = i + 1;
        }
    }

    fn search(&self, d: &[u8], i: usize) -> (u32, u32) {
        if i + 4 > d.len() {
            return (0, 0);
        }
        let max = (d.len() - i).min(258);
        let (mut best, mut best_d) = (0usize, 0usize);
        let mut cand = self.head[Self::hash(d, i)];
        let mut chain = MAX_CHAIN;
        while cand != u32::MAX && chain > 0 {
            let c = cand as usize;
            if c >= i || i - c > WIN {
                break;
            }
            let mut l = 0;
            while l + 8 <= max {
                let x = u64::from_le_bytes(d[c + l..c + l + 8].try_into().unwrap()) ^ u64::from_le_bytes(d[i + l..i + l + 8].try_into().unwrap());
                if x != 0 {
                    l += (x.trailing_zeros() / 8) as usize;
                    break;
                }
                l += 8;
            }
            while l < max && d[c + l] == d[i + l] {
                l += 1;
            }
            if l > best {
                best = l;
                best_d = i - c;
                if l == max {
                    break;
                }
                if l >= 128 {
                    chain >>= 2;
                }
            }
            let nxt = self.prev[c & (WIN - 1)];
            if nxt >= cand {
                break;
            }
            cand = nxt;
            chain -= 1;
        }
        if best < 4 && !(best == 3 && best_d <= 4096) { (0, 0) } else { (best as u32, best_d as u32) }
    }

    /// Appends the compressed form of `data` (not the end of the stream: call `finish` after the last chunk).
    pub fn chunk(&mut self, data: &[u8], out: &mut Vec<u8>) {
        if data.is_empty() {
            return;
        }
        if looks_random(data) {
            self.stored(data, out);
        } else {
            self.matched(data, out);
        }
        self.hist.extend_from_slice(data);
        if self.hist.len() > WIN {
            self.hist.drain(..self.hist.len() - WIN);
        }
    }

    fn matched(&mut self, data: &[u8], out: &mut Vec<u8>) {
        let h = self.hist.len();
        let mut buf = Vec::with_capacity(h + data.len());
        buf.extend_from_slice(&self.hist);
        buf.extend_from_slice(data);
        let d = &buf[..];
        self.head.fill(u32::MAX);
        self.next_ins = 0;
        for j in 0..h {
            self.ins(d, j);
        }
        let mut syms: Vec<u32> = Vec::with_capacity(data.len() / 2 + 16); // literal = byte, match = len << 16 | dist
        let n = d.len();
        let mut i = h;
        while i < n {
            let mut m = self.search(d, i);
            self.ins(d, i);
            if m.0 >= 3 {
                while m.0 < LAZY_BELOW && i + 1 < n {
                    let m2 = self.search(d, i + 1);
                    if m2.0 <= m.0 {
                        break;
                    }
                    syms.push(d[i] as u32);
                    i += 1;
                    self.ins(d, i);
                    m = m2;
                }
                syms.push(m.0 << 16 | m.1);
                // inside a long match only its start and end go into the hash: the middle is rarely found again and costs time
                let end = i + m.0 as usize;
                for j in (i + 1..end).filter(|&j| m.0 < 48 || j < i + 17 || j + 16 >= end) {
                    self.ins(d, j);
                }
                i = end;
            } else {
                syms.push(d[i] as u32);
                i += 1;
            }
        }
        self.block(data, &syms, out);
    }

    fn stored(&mut self, raw: &[u8], out: &mut Vec<u8>) {
        for part in raw.chunks(65535) {
            self.bw.put(out, 0, 3);
            self.bw.align(out);
            out.extend_from_slice(&(part.len() as u16).to_le_bytes());
            out.extend_from_slice(&(!(part.len() as u16)).to_le_bytes());
            out.extend_from_slice(part);
        }
    }

    fn block(&mut self, raw: &[u8], syms: &[u32], out: &mut Vec<u8>) {
        let (mut lf, mut df) = ([0u32; 286], [0u32; 30]);
        lf[256] = 1;
        for &s in syms {
            if s >> 16 == 0 {
                lf[s as usize] += 1;
            } else {
                lf[257 + LEN_CODE[(s >> 16) as usize] as usize] += 1;
                df[dist_code((s & 0xFFFF) as usize)] += 1;
            }
        }
        if df.iter().all(|&f| f == 0) {
            df[0] = 1;
        }
        let ll = code_lengths(&lf, 15);
        let dl = code_lengths(&df, 15);
        let hlit = (257..=286).rev().find(|&n| ll[n - 1] != 0).unwrap_or(257);
        let hdist = (1..=30).rev().find(|&n| dl[n - 1] != 0).unwrap_or(1);
        // the lengths as run-length symbols (16 = repeat previous, 17 / 18 = zeros)
        let all: Vec<u8> = ll[..hlit].iter().chain(&dl[..hdist]).copied().collect();
        let mut rl: Vec<(u8, u8)> = vec![];
        let mut k = 0;
        while k < all.len() {
            let v = all[k];
            let mut run = 1;
            while k + run < all.len() && all[k + run] == v {
                run += 1;
            }
            k += run;
            if v == 0 {
                while run >= 3 {
                    let r = run.min(138);
                    if r >= 11 { rl.push((18, (r - 11) as u8)) } else { rl.push((17, (r - 3) as u8)) }
                    run -= r;
                }
            } else {
                rl.push((v, 0));
                run -= 1;
                while run >= 3 {
                    let r = run.min(6);
                    rl.push((16, (r - 3) as u8));
                    run -= r;
                }
            }
            for _ in 0..run {
                rl.push((v, 0));
            }
        }
        let mut cf = [0u32; 19];
        for &(s, _) in &rl {
            cf[s as usize] += 1;
        }
        let cl = code_lengths(&cf, 7);
        let hclen = (4..=19).rev().find(|&n| cl[CL_ORDER[n - 1]] != 0).unwrap_or(4);
        // dynamic against stored, in bits
        let mut bits: u64 = 17 + 3 * hclen as u64;
        bits += rl.iter().map(|&(s, _)| cl[s as usize] as u64 + [0, 0, 0, 2, 3, 7][if s >= 16 { s as usize - 13 } else { 0 }]).sum::<u64>();
        bits += (0..286).map(|i| lf[i] as u64 * (ll[i] as u64 + if i >= 257 { LEXT[i - 257] as u64 } else { 0 })).sum::<u64>();
        bits += (0..30).map(|i| df[i] as u64 * (dl[i] as u64 + DEXT[i] as u64)).sum::<u64>();
        let stored_bits = raw.len() as u64 * 8 + 40 * (raw.len() as u64 / 65535 + 1);
        if bits >= stored_bits {
            self.stored(raw, out);
            return;
        }
        let (lc, dc, cc) = (codes(&ll), codes(&dl), codes(&cl));
        let bw = &mut self.bw;
        bw.put(out, 0b100, 3); // not final (0), dynamic Huffman (type 2, LSB first)
        bw.put(out, (hlit - 257) as u32, 5);
        bw.put(out, (hdist - 1) as u32, 5);
        bw.put(out, (hclen - 4) as u32, 4);
        for &o in &CL_ORDER[..hclen] {
            bw.put(out, cl[o] as u32, 3);
        }
        for &(s, x) in &rl {
            bw.put(out, cc[s as usize], cl[s as usize] as u32);
            match s {
                16 => bw.put(out, x as u32, 2),
                17 => bw.put(out, x as u32, 3),
                18 => bw.put(out, x as u32, 7),
                _ => {}
            }
        }
        for &s in syms {
            if s >> 16 == 0 {
                bw.put(out, lc[s as usize], ll[s as usize] as u32);
            } else {
                let (len, dist) = ((s >> 16) as usize, (s & 0xFFFF) as usize);
                let c = LEN_CODE[len] as usize;
                bw.put(out, lc[257 + c], ll[257 + c] as u32);
                bw.put(out, (len - LBASE[c] as usize) as u32, LEXT[c] as u32);
                let d = dist_code(dist);
                bw.put(out, dc[d], dl[d] as u32);
                bw.put(out, (dist - DBASE[d] as usize) as u32, DEXT[d] as u32);
            }
        }
        bw.put(out, lc[256], ll[256] as u32);
    }

    /// Ends the stream: an empty final block, padded to a whole byte.
    pub fn finish(&mut self, out: &mut Vec<u8>) {
        self.bw.put(out, 0b011, 3); // final, fixed Huffman
        self.bw.put(out, 0, 7); // end of block
        self.bw.align(out);
    }
}

/// The whole of `data` as one deflate stream.
pub fn deflate(data: &[u8]) -> Vec<u8> {
    let mut d = Deflater::new();
    let mut out = Vec::with_capacity(data.len() / 2 + 64);
    for c in data.chunks(CHUNK) {
        d.chunk(c, &mut out);
    }
    d.finish(&mut out);
    out
}

pub const CHUNK: usize = 1 << 20;
const FLUSH_AT: usize = (1 << 19) + WIN;

// ---------- inflate ----------

struct Bits<R: Read> {
    r: R,
    buf: Box<[u8; 1 << 16]>,
    pos: usize,
    len: usize,
    acc: u64,
    n: u32,
}

fn eof() -> io::Error {
    io::Error::new(io::ErrorKind::UnexpectedEof, "compressed data ends too early")
}

fn bad(m: &str) -> io::Error {
    io::Error::new(io::ErrorKind::InvalidData, m.to_string())
}

impl<R: Read> Bits<R> {
    fn new(r: R) -> Self {
        Bits { r, buf: Box::new([0; 1 << 16]), pos: 0, len: 0, acc: 0, n: 0 }
    }
    fn fill_buf(&mut self) -> io::Result<()> {
        if self.pos == self.len {
            self.len = self.r.read(&mut self.buf[..])?;
            self.pos = 0;
        }
        Ok(())
    }
    fn refill(&mut self) -> io::Result<()> {
        while self.n <= 56 {
            self.fill_buf()?;
            if self.pos == self.len {
                break; // the end: the missing bits read as zeros and `take` complains if they were needed
            }
            self.acc |= (self.buf[self.pos] as u64) << self.n;
            self.pos += 1;
            self.n += 8;
        }
        Ok(())
    }
    fn peek(&mut self, k: u32) -> io::Result<u32> {
        if self.n < k {
            self.refill()?;
        }
        Ok((self.acc & ((1u64 << k) - 1)) as u32)
    }
    fn take(&mut self, k: u32) -> io::Result<()> {
        if self.n < k {
            return Err(eof());
        }
        self.acc >>= k;
        self.n -= k;
        Ok(())
    }
    fn bits(&mut self, k: u32) -> io::Result<u32> {
        let v = self.peek(k)?;
        self.take(k)?;
        Ok(v)
    }
    /// `n` whole bytes after aligning (stored block), appended to `out`.
    fn bytes(&mut self, mut n: usize, out: &mut Vec<u8>) -> io::Result<()> {
        while n > 0 && self.n >= 8 {
            out.push(self.acc as u8);
            self.acc >>= 8;
            self.n -= 8;
            n -= 1;
        }
        while n > 0 {
            self.fill_buf()?;
            if self.pos == self.len {
                return Err(eof());
            }
            let k = n.min(self.len - self.pos);
            out.extend_from_slice(&self.buf[self.pos..self.pos + k]);
            self.pos += k;
            n -= k;
        }
        Ok(())
    }
}

/// Lookup by the next `max` bits (bit-reversed codes): `len << 9 | symbol`, 0 = no such code.
struct Table {
    max: u32,
    t: Vec<u16>,
}

impl Table {
    fn new(len: &[u8]) -> io::Result<Table> {
        let max = len.iter().copied().max().unwrap_or(0) as u32;
        let mut count = [0u32; 16];
        for &l in len {
            count[l as usize] += 1;
        }
        count[0] = 0;
        let (mut next, mut code) = ([0u32; 16], 0u32);
        for b in 1..16 {
            code = (code + count[b - 1]) << 1;
            next[b] = code;
            if count[b] > 0 && code + count[b] > 1 << b {
                return Err(bad("oversubscribed Huffman code"));
            }
        }
        let mut t = vec![0u16; 1 << max];
        for (s, &l) in len.iter().enumerate() {
            if l == 0 {
                continue;
            }
            let c = rev_bits(next[l as usize], l as u32) as usize;
            next[l as usize] += 1;
            for k in (c..t.len()).step_by(1 << l) {
                t[k] = (l as u16) << 9 | s as u16;
            }
        }
        Ok(Table { max, t })
    }
    fn sym<R: Read>(&self, b: &mut Bits<R>) -> io::Result<usize> {
        let e = *self.t.get(b.peek(self.max)? as usize).ok_or_else(|| bad("bad Huffman code"))?;
        if e == 0 {
            return Err(bad("bad Huffman code"));
        }
        b.take((e >> 9) as u32)?;
        Ok((e & 511) as usize)
    }
}

/// Inflates `r` into `w`; returns the CRC-32 and the size of the output. `progress` gets the bytes written so far in each step:
/// answering false stops with an Interrupted error.
pub fn inflate<R: Read, W: Write>(r: R, w: &mut W, progress: &mut dyn FnMut(u64) -> bool) -> io::Result<(u32, u64)> {
    let mut b = Bits::new(r);
    let mut out: Vec<u8> = Vec::with_capacity(1 << 19);
    let (mut crc, mut total) = (0u32, 0u64);
    let mut flush = |out: &mut Vec<u8>, w: &mut W, all: bool| -> io::Result<()> {
        let keep = if all { 0 } else { WIN };
        if out.len() > keep {
            let n = out.len() - keep;
            crc = crc32(crc, &out[..n]);
            total += n as u64;
            w.write_all(&out[..n])?;
            out.drain(..n);
            if !progress(n as u64) {
                return Err(io::Error::new(io::ErrorKind::Interrupted, "cancelled"));
            }
        }
        Ok(())
    };
    let fixed = {
        let mut l = [8u8; 288];
        l[144..256].fill(9);
        l[256..280].fill(7);
        (Table::new(&l)?, Table::new(&[5u8; 30])?)
    };
    loop {
        let last = b.bits(1)? == 1;
        match b.bits(2)? {
            0 => {
                b.take(b.n % 8)?;
                let len = b.bits(16)? as usize;
                if b.bits(16)? as usize != !len & 0xFFFF {
                    return Err(bad("stored block length"));
                }
                b.bytes(len, &mut out)?;
            }
            t @ (1 | 2) => {
                let dynamic;
                let (lt, dt) = if t == 1 {
                    (&fixed.0, &fixed.1)
                } else {
                    let (hlit, hdist, hclen) = (b.bits(5)? as usize + 257, b.bits(5)? as usize + 1, b.bits(4)? as usize + 4);
                    if hlit > 286 || hdist > 30 {
                        return Err(bad("too many codes"));
                    }
                    let mut cl = [0u8; 19];
                    for &o in &CL_ORDER[..hclen] {
                        cl[o] = b.bits(3)? as u8;
                    }
                    let ct = Table::new(&cl)?;
                    let mut lens = vec![0u8; hlit + hdist];
                    let mut i = 0;
                    while i < lens.len() {
                        let s = ct.sym(&mut b)?;
                        let (v, rep) = match s {
                            0..=15 => (s as u8, 1),
                            16 => (*lens[..i].last().ok_or_else(|| bad("repeat with nothing before"))?, 3 + b.bits(2)? as usize),
                            17 => (0, 3 + b.bits(3)? as usize),
                            _ => (0, 11 + b.bits(7)? as usize),
                        };
                        if i + rep > lens.len() {
                            return Err(bad("code lengths overrun"));
                        }
                        lens[i..i + rep].fill(v);
                        i += rep;
                    }
                    dynamic = (Table::new(&lens[..hlit])?, Table::new(&lens[hlit..])?);
                    (&dynamic.0, &dynamic.1)
                };
                loop {
                    let s = lt.sym(&mut b)?;
                    if s < 256 {
                        out.push(s as u8);
                    } else if s == 256 {
                        break;
                    } else {
                        let c = s - 257;
                        if c >= 29 {
                            return Err(bad("bad length code"));
                        }
                        let len = LBASE[c] as usize + b.bits(LEXT[c] as u32)? as usize;
                        let d = dt.sym(&mut b)?;
                        if d >= 30 {
                            return Err(bad("bad distance code"));
                        }
                        let dist = DBASE[d] as usize + b.bits(DEXT[d] as u32)? as usize;
                        if dist > out.len() {
                            return Err(bad("distance reaches before the start"));
                        }
                        let from = out.len() - dist;
                        if dist >= len {
                            out.extend_from_within(from..from + len);
                        } else {
                            for k in 0..len {
                                out.push(out[from + k]);
                            }
                        }
                    }
                    if out.len() >= FLUSH_AT {
                        flush(&mut out, w, false)?;
                    }
                }
            }
            _ => return Err(bad("bad block type")),
        }
        if last {
            break;
        }
    }
    flush(&mut out, w, true)?;
    Ok((crc, total))
}

// ---------- ZIP container: writing ----------

const U32_MAX: u64 = 0xFFFF_FFFF;

/// A file compressed in memory by a worker thread, ready to be written.
pub struct Prepared {
    name: String,
    time: (u16, u16),
    method: u16,
    crc: u32,
    usize: u64,
    data: Vec<u8>,
}

impl Prepared {
    pub fn uncompressed_size(&self) -> u64 {
        self.usize
    }
}

/// Reads and compresses one file (the caller keeps these small: it all sits in memory).
pub fn prepare(name: String, path: &Path) -> io::Result<Prepared> {
    let raw = fs::read(path)?;
    let time = dos_time(path);
    let crc = crc32(0, &raw);
    let data = deflate(&raw);
    if raw.is_empty() || data.len() >= raw.len() {
        return Ok(Prepared { name, time, method: 0, crc, usize: raw.len() as u64, data: raw });
    }
    Ok(Prepared { name, time, method: 8, crc, usize: raw.len() as u64, data })
}

struct Cd {
    name: String,
    time: (u16, u16),
    method: u16,
    crc: u32,
    csize: u64,
    usize: u64,
    offset: u64,
    dir: bool,
}

pub struct Writer<W: Write> {
    w: W,
    pos: u64,
    cd: Vec<Cd>,
    limit: u64, // sizes and offsets from here on need ZIP64 fields
}

fn le16(v: &mut Vec<u8>, x: u16) {
    v.extend_from_slice(&x.to_le_bytes());
}
fn le32(v: &mut Vec<u8>, x: u32) {
    v.extend_from_slice(&x.to_le_bytes());
}
fn le64(v: &mut Vec<u8>, x: u64) {
    v.extend_from_slice(&x.to_le_bytes());
}

impl<W: Write> Writer<W> {
    pub fn new(w: W) -> Self {
        Writer { w, pos: 0, cd: vec![], limit: U32_MAX }
    }

    /// Tests: ZIP64 fields from a small size on, to exercise them without gigabytes.
    #[cfg(test)]
    fn with_limit(mut self, limit: u64) -> Self {
        self.limit = limit;
        self
    }

    fn put(&mut self, b: &[u8]) -> io::Result<()> {
        self.w.write_all(b)?;
        self.pos += b.len() as u64;
        Ok(())
    }

    pub fn add_dir(&mut self, name: &str, time: (u16, u16)) -> io::Result<()> {
        let name = format!("{}/", name.trim_end_matches('/'));
        let offset = self.pos;
        let mut h = vec![];
        local_header(&mut h, &name, time, 0, 0, 0, 0, false);
        self.put(&h)?;
        self.cd.push(Cd { name, time, method: 0, crc: 0, csize: 0, usize: 0, offset, dir: true });
        Ok(())
    }

    pub fn add_prepared(&mut self, f: Prepared) -> io::Result<()> {
        let offset = self.pos;
        let mut h = vec![];
        local_header(&mut h, &f.name, f.time, f.method, f.crc, f.data.len() as u32, f.usize as u32, false);
        self.put(&h)?;
        self.put(&f.data)?;
        self.cd.push(Cd { name: f.name, time: f.time, method: f.method, crc: f.crc, csize: f.data.len() as u64, usize: f.usize, offset, dir: false });
        Ok(())
    }

    /// A big file streamed from disk (sizes are unknown up front: ZIP64 data descriptor). A reader thread keeps the next chunk
    /// coming while this one is compressed. `done` is told the bytes read in each step; false stops with an Interrupted error.
    pub fn add_stream(&mut self, name: String, path: &Path, mut done: impl FnMut(u64) -> bool) -> io::Result<()> {
        let time = dos_time(path);
        let mut f = fs::File::open(path)?;
        let offset = self.pos;
        let mut h = vec![];
        local_header(&mut h, &name, time, 8, 0, U32_MAX as u32, U32_MAX as u32, true);
        self.put(&h)?;
        let (mut d, mut out) = (Deflater::new(), Vec::new());
        let (mut crc, mut total, mut csize) = (0u32, 0u64, 0u64);
        let (tx, rx) = std::sync::mpsc::sync_channel::<io::Result<Vec<u8>>>(2);
        std::thread::scope(|s| -> io::Result<()> {
            s.spawn(move || loop {
                let mut buf = vec![0u8; CHUNK];
                let mut n = 0;
                let r = loop {
                    if n == CHUNK {
                        break Ok(n);
                    }
                    match f.read(&mut buf[n..]) {
                        Ok(0) => break Ok(n),
                        Ok(k) => n += k,
                        Err(e) => break Err(e),
                    }
                };
                let last = !matches!(r, Ok(n) if n == CHUNK);
                let msg = r.map(|n| { buf.truncate(n); buf });
                if tx.send(msg).is_err() || last {
                    break; // the writer gave up, or the file ended
                }
            });
            for r in rx {
                let buf = r?;
                if buf.is_empty() {
                    break;
                }
                crc = crc32(crc, &buf);
                total += buf.len() as u64;
                out.clear();
                d.chunk(&buf, &mut out);
                csize += out.len() as u64;
                self.put(&out)?;
                if !done(buf.len() as u64) {
                    return Err(io::Error::new(io::ErrorKind::Interrupted, "cancelled"));
                }
            }
            Ok(())
        })?;
        out.clear();
        d.finish(&mut out);
        csize += out.len() as u64;
        self.put(&out)?;
        let mut dd = vec![];
        le32(&mut dd, 0x0807_4b50);
        le32(&mut dd, crc);
        le64(&mut dd, csize);
        le64(&mut dd, total);
        self.put(&dd)?;
        self.cd.push(Cd { name, time, method: 8, crc, csize, usize: total, offset, dir: false });
        Ok(())
    }

    pub fn finish(mut self) -> io::Result<W> {
        let start = self.pos;
        let mut v = vec![];
        for e in &self.cd {
            let mut x = vec![]; // zip64 extra: only the fields that do not fit 32 bits, in this order
            let (us, cs, of) = (e.usize >= self.limit, e.csize >= self.limit, e.offset >= self.limit);
            if us {
                le64(&mut x, e.usize);
            }
            if cs {
                le64(&mut x, e.csize);
            }
            if of {
                le64(&mut x, e.offset);
            }
            let big = |b: bool, v: u64| if b { U32_MAX as u32 } else { v as u32 };
            le32(&mut v, 0x0201_4b50);
            le16(&mut v, 45 | 10 << 8); // made by: 4.5, FAT
            le16(&mut v, if x.is_empty() { 20 } else { 45 });
            le16(&mut v, 0x0800); // UTF-8 names
            le16(&mut v, e.method);
            le16(&mut v, e.time.0);
            le16(&mut v, e.time.1);
            le32(&mut v, e.crc);
            le32(&mut v, big(cs, e.csize));
            le32(&mut v, big(us, e.usize));
            le16(&mut v, e.name.len() as u16);
            le16(&mut v, if x.is_empty() { 0 } else { x.len() as u16 + 4 });
            le16(&mut v, 0);
            le16(&mut v, 0);
            le16(&mut v, 0);
            le32(&mut v, if e.dir { 0x10 } else { 0x20 }); // DOS attributes: directory / archive
            le32(&mut v, big(of, e.offset));
            v.extend_from_slice(e.name.as_bytes());
            if !x.is_empty() {
                le16(&mut v, 1);
                le16(&mut v, x.len() as u16);
                v.extend_from_slice(&x);
            }
        }
        let (n, size) = (self.cd.len() as u64, v.len() as u64);
        let z64 = n >= 0xFFFF || start >= self.limit || size >= self.limit;
        if z64 {
            let z = start + size;
            le32(&mut v, 0x0606_4b50); // zip64 end of central directory
            le64(&mut v, 44);
            le16(&mut v, 45);
            le16(&mut v, 45);
            le32(&mut v, 0);
            le32(&mut v, 0);
            le64(&mut v, n);
            le64(&mut v, n);
            le64(&mut v, size);
            le64(&mut v, start);
            le32(&mut v, 0x0706_4b50); // locator
            le32(&mut v, 0);
            le64(&mut v, z);
            le32(&mut v, 1);
        }
        le32(&mut v, 0x0605_4b50);
        le16(&mut v, 0);
        le16(&mut v, 0);
        let sat = |v: u64, m: u64| if z64 { m } else { v }; // with a ZIP64 directory the old fields hold the markers
        le16(&mut v, sat(n, 0xFFFF) as u16);
        le16(&mut v, sat(n, 0xFFFF) as u16);
        le32(&mut v, sat(size, U32_MAX) as u32);
        le32(&mut v, sat(start, U32_MAX) as u32);
        le16(&mut v, 0);
        self.put(&v)?;
        self.w.flush()?;
        Ok(self.w)
    }
}

#[allow(clippy::too_many_arguments)]
fn local_header(h: &mut Vec<u8>, name: &str, time: (u16, u16), method: u16, crc: u32, csize: u32, usize: u32, stream: bool) {
    le32(h, 0x0403_4b50);
    le16(h, if stream { 45 } else { 20 });
    le16(h, 0x0800 | if stream { 8 } else { 0 });
    le16(h, method);
    le16(h, time.0);
    le16(h, time.1);
    le32(h, crc);
    le32(h, csize);
    le32(h, usize);
    le16(h, name.len() as u16);
    le16(h, if stream { 20 } else { 0 });
    h.extend_from_slice(name.as_bytes());
    if stream {
        le16(h, 1); // zip64 extra: the real sizes follow in the data descriptor
        le16(h, 16);
        le64(h, 0);
        le64(h, 0);
    }
}

/// (DOS time, DOS date) of the file's modification, in local time.
pub fn dos_time(p: &Path) -> (u16, u16) {
    use windows_sys::Win32::{Foundation::{FILETIME, SYSTEMTIME}, Storage::FileSystem::FileTimeToLocalFileTime, System::Time::FileTimeToSystemTime};
    let t = fs::metadata(p).and_then(|m| m.modified()).ok().and_then(|t| t.duration_since(std::time::UNIX_EPOCH).ok());
    let Some(t) = t else { return (0, 0x21) };
    let ft100 = t.as_secs() * 10_000_000 + (t.subsec_nanos() / 100) as u64 + 116_444_736_000_000_000;
    let (ft, mut local, mut st) = (FILETIME { dwLowDateTime: ft100 as u32, dwHighDateTime: (ft100 >> 32) as u32 }, unsafe { std::mem::zeroed::<FILETIME>() }, unsafe { std::mem::zeroed::<SYSTEMTIME>() });
    unsafe {
        if FileTimeToLocalFileTime(&ft, &mut local) == 0 || FileTimeToSystemTime(&local, &mut st) == 0 || st.wYear < 1980 {
            return (0, 0x21);
        }
    }
    ((st.wHour << 11) | (st.wMinute << 5) | (st.wSecond / 2), ((st.wYear - 1980) << 9) | (st.wMonth << 5) | st.wDay)
}

/// The moment a (DOS time, DOS date) pair stands for (local time); None for "no time" (date 0 or the 1980-01-01 placeholder).
fn from_dos(t: (u16, u16)) -> Option<SystemTime> {
    use windows_sys::Win32::{Foundation::{FILETIME, SYSTEMTIME}, Storage::FileSystem::LocalFileTimeToFileTime, System::Time::SystemTimeToFileTime};
    let (tm, dt) = t;
    if dt == 0 || (dt == 0x21 && tm == 0) {
        return None;
    }
    let st = SYSTEMTIME { wYear: (dt >> 9) + 1980, wMonth: (dt >> 5) & 15, wDayOfWeek: 0, wDay: dt & 31, wHour: tm >> 11, wMinute: (tm >> 5) & 63, wSecond: (tm & 31) * 2, wMilliseconds: 0 };
    let (mut local, mut utc) = unsafe { (std::mem::zeroed::<FILETIME>(), std::mem::zeroed::<FILETIME>()) };
    unsafe {
        if SystemTimeToFileTime(&st, &mut local) == 0 || LocalFileTimeToFileTime(&local, &mut utc) == 0 {
            return None;
        }
    }
    let t100 = (utc.dwHighDateTime as u64) << 32 | utc.dwLowDateTime as u64;
    t100.checked_sub(116_444_736_000_000_000).map(|x| UNIX_EPOCH + Duration::from_nanos(x * 100))
}

fn set_mtime(path: &Path, t: SystemTime) {
    use std::os::windows::fs::OpenOptionsExt;
    // FILE_FLAG_BACKUP_SEMANTICS lets a folder be opened too
    if let Ok(f) = fs::OpenOptions::new().write(true).custom_flags(0x0200_0000).open(path) {
        let _ = f.set_modified(t);
    }
}

// ---------- ZIP container: reading ----------

struct Entry {
    name: String,
    time: (u16, u16),
    method: u16,
    flags: u16,
    crc: u32,
    csize: u64,
    usize: u64,
    offset: u64,
}

fn u16_at(b: &[u8], i: usize) -> u16 {
    u16::from_le_bytes([b[i], b[i + 1]])
}
fn u32_at(b: &[u8], i: usize) -> u32 {
    u32::from_le_bytes(b[i..i + 4].try_into().unwrap())
}
fn u64_at(b: &[u8], i: usize) -> u64 {
    u64::from_le_bytes(b[i..i + 8].try_into().unwrap())
}

fn read_at<F: Read + Seek>(f: &mut F, pos: u64, n: usize) -> io::Result<Vec<u8>> {
    f.seek(SeekFrom::Start(pos))?;
    let mut v = vec![0; n];
    f.read_exact(&mut v)?;
    Ok(v)
}

fn central_directory<F: Read + Seek>(f: &mut F) -> io::Result<Vec<Entry>> {
    let end = f.seek(SeekFrom::End(0))?;
    let tail_len = end.min(22 + 65535);
    let tail = read_at(f, end - tail_len, tail_len as usize)?;
    let at = (0..tail.len().saturating_sub(21)).rev().find(|&i| u32_at(&tail, i) == 0x0605_4b50).ok_or_else(|| bad("not a ZIP archive"))?;
    let eocd = end - tail_len + at as u64;
    let (mut count, mut size, mut start) = (u16_at(&tail, at + 10) as u64, u32_at(&tail, at + 12) as u64, u32_at(&tail, at + 16) as u64);
    if (count == 0xFFFF || size == U32_MAX || start == U32_MAX) && eocd >= 20 {
        let loc = read_at(f, eocd - 20, 20)?;
        if u32_at(&loc, 0) == 0x0706_4b50 {
            let z = read_at(f, u64_at(&loc, 8), 56)?;
            if u32_at(&z, 0) != 0x0606_4b50 {
                return Err(bad("broken ZIP64 directory"));
            }
            (count, size, start) = (u64_at(&z, 32), u64_at(&z, 40), u64_at(&z, 48));
        }
    }
    if size > 1 << 30 {
        return Err(bad("central directory is too big"));
    }
    let cd = read_at(f, start, size as usize)?;
    let (mut v, mut i) = (vec![], 0usize);
    for _ in 0..count {
        if i + 46 > cd.len() || u32_at(&cd, i) != 0x0201_4b50 {
            return Err(bad("broken central directory"));
        }
        let (flags, method) = (u16_at(&cd, i + 8), u16_at(&cd, i + 10));
        let (nl, el, cl) = (u16_at(&cd, i + 28) as usize, u16_at(&cd, i + 30) as usize, u16_at(&cd, i + 32) as usize);
        if i + 46 + nl + el + cl > cd.len() {
            return Err(bad("broken central directory"));
        }
        let mut e = Entry {
            name: decode_name(&cd[i + 46..i + 46 + nl], flags),
            time: (u16_at(&cd, i + 12), u16_at(&cd, i + 14)),
            method,
            flags,
            crc: u32_at(&cd, i + 16),
            csize: u32_at(&cd, i + 20) as u64,
            usize: u32_at(&cd, i + 24) as u64,
            offset: u32_at(&cd, i + 42) as u64,
        };
        let mut x = &cd[i + 46 + nl..i + 46 + nl + el];
        while x.len() >= 4 {
            let (id, sz) = (u16_at(x, 0), u16_at(x, 2) as usize);
            if x.len() < 4 + sz {
                break;
            }
            if id == 1 {
                let mut f = &x[4..4 + sz];
                for field in [&mut e.usize, &mut e.csize, &mut e.offset] {
                    if *field == U32_MAX && f.len() >= 8 {
                        *field = u64_at(f, 0);
                        f = &f[8..];
                    }
                }
            }
            x = &x[4 + sz..];
        }
        v.push(e);
        i += 46 + nl + el + cl;
    }
    Ok(v)
}

const CP437_HIGH: &str = "ÇüéâäàåçêëèïîìÄÅÉæÆôöòûùÿÖÜ¢£¥₧ƒáíóúñѪº¿⌐¬½¼¡«»░▒▓│┤╡╢╖╕╣║╗╝╜╛┐└┴┬├─┼╞╟╚╔╩╦╠═╬╧╨╤╥╙╘╒╓╫╪┘┌█▄▌▐▀αßΓπΣσµτΦΘΩδ∞φε∩≡±≥≤⌠⌡÷≈°∙·√ⁿ²■\u{a0}";

/// UTF-8 when the flag says so or the bytes are valid UTF-8; otherwise the old DOS code page 437.
fn decode_name(b: &[u8], flags: u16) -> String {
    match std::str::from_utf8(b) {
        Ok(s) => s.to_string(),
        Err(_) if flags & 0x800 != 0 => String::from_utf8_lossy(b).into_owned(),
        Err(_) => {
            let high: Vec<char> = CP437_HIGH.chars().collect();
            b.iter().map(|&c| if c < 0x80 { c as char } else { high[c as usize - 0x80] }).collect()
        }
    }
}

/// The path of an entry under `out`, or None for one that would land outside it (zip-slip) or has no name.
fn safe_path(out: &Path, name: &str) -> Result<Option<PathBuf>, String> {
    let mut p = out.to_path_buf();
    let mut any = false;
    for c in name.replace('\\', "/").split('/') {
        match c {
            "" | "." => continue,
            ".." => return Err(format!("{name}: the name leads out of the folder")),
            _ if Path::new(c).components().any(|k| !matches!(k, Component::Normal(_))) || c.contains(':') => return Err(format!("{name}: bad name")),
            _ => {
                p.push(c);
                any = true;
            }
        }
    }
    Ok(any.then_some(p))
}

/// One row of an archive browsed like a folder.
pub struct Item {
    pub name: String,
    pub dir: bool,
    pub size: u64,
    pub time: (u16, u16),
}

/// What is directly inside the folder `inner` ('/' separated, "" = the top) of the archive. Folders that exist only as a part
/// of a file's path are listed too.
pub fn list_dir(archive: &Path, inner: &str) -> Result<Vec<Item>, String> {
    let mut f = fs::File::open(archive).map_err(|e| e.to_string())?;
    let entries = central_directory(&mut f).map_err(|e| e.to_string())?;
    let prefix = if inner.is_empty() { String::new() } else { format!("{}/", inner.trim_matches('/')) };
    let mut m: std::collections::BTreeMap<String, Item> = Default::default();
    for e in entries {
        let name = e.name.replace('\\', "/");
        let Some(rest) = name.trim_start_matches('/').strip_prefix(&prefix) else { continue };
        let Some(first) = rest.split('/').next().filter(|f| !f.is_empty()) else { continue };
        let deeper = rest.trim_end_matches('/').len() > first.len() || rest.ends_with('/');
        let item = m.entry(first.to_string()).or_insert(Item { name: first.to_string(), dir: deeper, size: 0, time: (0, 0x21) });
        if deeper {
            item.dir = true;
            if rest.trim_end_matches('/') == first { item.time = e.time; } // the folder's own entry
        } else {
            item.size = e.usize;
            item.time = e.time;
        }
    }
    Ok(m.into_values().collect())
}

/// `C:\a\b.zip\x\y` -> (`C:\a\b.zip`, "x/y"): a path that goes into a .zip FILE (so it is no real folder path). The
/// archive itself gives ("", ...).
pub fn split_zip(p: &Path) -> Option<(PathBuf, String)> {
    let anc: Vec<&Path> = p.ancestors().collect();
    let a = anc.iter().rev().find(|a| a.extension().is_some_and(|e| e.eq_ignore_ascii_case("zip")) && a.is_file())?;
    let inner = p.strip_prefix(a).ok()?.components().map(|c| c.as_os_str().to_string_lossy().into_owned()).collect::<Vec<_>>().join("/");
    Some((a.to_path_buf(), inner))
}

/// A DOS time as FILETIME ticks (what the file list sorts and shows); 0 for none.
pub fn dos_to_filetime(t: (u16, u16)) -> u64 {
    from_dos(t).and_then(|t| t.duration_since(UNIX_EPOCH).ok()).map_or(0, |d| d.as_secs() * 10_000_000 + 116_444_736_000_000_000)
}

/// Unpacks the archive into `out` (created) and gives files and folders their stored times. Stops at the first bad entry.
/// `total` is told the unpacked size of everything up front; `step` the bytes written in each step (false = stop, "cancelled").
pub fn extract(archive: &Path, out: &Path, total: impl FnOnce(u64), step: impl FnMut(u64) -> bool) -> Result<(), String> {
    extract_where(archive, out, |n| Some(n.to_string()), total, step)
}

/// Only the entries under the given archive paths (files or folders, '/' separated): each lands in `out` under its own name,
/// with the path above it cut off. Used to take a few things out of an archive that is browsed like a folder.
pub fn extract_some(archive: &Path, names: &[String], out: &Path) -> Result<(), String> {
    let pick = |n: &str| {
        let n = n.replace('\\', "/");
        let n = n.trim_start_matches('/');
        names.iter().find_map(|sel| {
            let sel = sel.trim_matches('/');
            let cut = sel.rfind('/').map_or(0, |i| i + 1);
            (n.trim_end_matches('/') == sel || n.starts_with(&format!("{sel}/"))).then(|| n[cut..].to_string())
        })
    };
    extract_where(archive, out, pick, |_| {}, |_| true)
}

fn extract_where(archive: &Path, out: &Path, pick: impl Fn(&str) -> Option<String>, total: impl FnOnce(u64), mut step: impl FnMut(u64) -> bool) -> Result<(), String> {
    let mut f = fs::File::open(archive).map_err(|e| e.to_string())?;
    let entries = central_directory(&mut f).map_err(|e| e.to_string())?;
    fs::create_dir_all(out).map_err(|e| e.to_string())?;
    total(entries.iter().map(|e| e.usize).sum());
    let mut dirs = vec![];
    for e in entries {
        let Some(rel) = pick(&e.name) else { continue };
        let Some(path) = safe_path(out, &rel)? else { continue };
        if e.name.ends_with('/') || e.name.ends_with('\\') {
            fs::create_dir_all(&path).map_err(|x| format!("{}: {x}", e.name))?;
            dirs.push((path, from_dos(e.time)));
            continue;
        }
        if e.flags & 1 != 0 {
            return Err(format!("{}: encrypted entries are not supported", e.name));
        }
        let ctx = |x: io::Error| if x.kind() == io::ErrorKind::Interrupted { "cancelled".to_string() } else { format!("{}: {x}", e.name) };
        let lh = read_at(&mut f, e.offset, 30).map_err(ctx)?;
        if u32_at(&lh, 0) != 0x0403_4b50 {
            return Err(format!("{}: broken local header", e.name));
        }
        let data = e.offset + 30 + u16_at(&lh, 26) as u64 + u16_at(&lh, 28) as u64;
        f.seek(SeekFrom::Start(data)).map_err(ctx)?;
        if let Some(d) = path.parent() {
            fs::create_dir_all(d).map_err(ctx)?;
        }
        let mut w = BufWriter::with_capacity(1 << 20, fs::File::create(&path).map_err(ctx)?);
        let src = io::BufReader::with_capacity(1 << 16, (&mut f).take(e.csize));
        let (crc, size) = match e.method {
            0 => {
                let mut src = src;
                let (mut crc, mut n, mut buf) = (0u32, 0u64, vec![0u8; 1 << 16]);
                loop {
                    let k = src.read(&mut buf).map_err(ctx)?;
                    if k == 0 {
                        break;
                    }
                    crc = crc32(crc, &buf[..k]);
                    n += k as u64;
                    w.write_all(&buf[..k]).map_err(ctx)?;
                    if !step(k as u64) {
                        return Err("cancelled".into());
                    }
                }
                (crc, n)
            }
            8 => inflate(src, &mut w, &mut step).map_err(ctx)?,
            m => return Err(format!("{}: compression method {m} is not supported", e.name)),
        };
        let file = w.into_inner().map_err(|x| ctx(x.into_error()))?;
        if let Some(t) = from_dos(e.time) {
            let _ = file.set_modified(t);
        }
        drop(file);
        if crc != e.crc || size != e.usize {
            return Err(format!("{}: the data is damaged (checksum or size differs)", e.name));
        }
    }
    for (p, t) in dirs.into_iter().rev().filter_map(|(p, t)| Some((p, t?))) {
        set_mtime(&p, t); // last and deepest first: writing into a folder changes its time
    }
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Read;

    fn sample(n: usize, seed: u32) -> Vec<u8> {
        // text-like data with repeats, so matches and several symbol lengths all occur
        let words = ["alpha", "beta", "gamma", "delta", "epsilon", " ", "\n", "0123456789", "zip"];
        let (mut s, mut v) = (seed, Vec::new());
        while v.len() < n {
            s = s.wrapping_mul(1664525).wrapping_add(1013904223);
            v.extend_from_slice(words[(s >> 24) as usize % words.len()].as_bytes());
            if s >> 20 & 7 == 0 {
                v.push((s >> 8) as u8);
            }
        }
        v.truncate(n);
        v
    }

    fn noise(n: usize) -> Vec<u8> {
        let mut s = 12345u32;
        (0..n).map(|_| { s = s.wrapping_mul(1103515245).wrapping_add(12345); (s >> 16) as u8 }).collect()
    }

    fn round(data: &[u8]) {
        let z = deflate(data);
        let mut back = vec![];
        let (crc, n) = inflate(&z[..], &mut back, &mut |_| true).unwrap();
        assert_eq!(back, data);
        assert_eq!((crc, n), (crc32(0, data), data.len() as u64));
    }

    #[test]
    fn crc_known_value() {
        assert_eq!(crc32(0, b"123456789"), 0xCBF4_3926);
        assert_eq!(crc32(crc32(0, b"1234"), b"56789"), 0xCBF4_3926);
    }

    #[test]
    fn deflate_round_trips() {
        round(b"");
        round(b"a");
        round(b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
        round(&sample(10_000, 1));
        round(&sample(3_000_000, 2)); // several chunks
        round(&noise(200_000)); // stored blocks
        round(&vec![7u8; 300_000]);
        let mut mixed = sample(100_000, 3);
        mixed.extend(noise(70_000));
        mixed.extend(sample(100_000, 4));
        round(&mixed);
    }

    #[test]
    fn compresses_text_and_does_not_grow_noise() {
        let t = sample(1_000_000, 5);
        assert!(deflate(&t).len() < t.len() / 3, "text should shrink a lot");
        let n = noise(1_000_000);
        assert!(deflate(&n).len() < n.len() + 1000, "noise stays near its size");
    }

    fn tmp(tag: &str) -> PathBuf {
        let d = std::env::temp_dir().join(format!("zipx-{tag}-{}", std::process::id()));
        let _ = fs::remove_dir_all(&d);
        fs::create_dir_all(&d).unwrap();
        d
    }

    #[test]
    fn archive_round_trip_and_sizes() {
        let d = tmp("rt");
        fs::write(d.join("text.txt"), sample(500_000, 6)).unwrap();
        fs::write(d.join("noise.bin"), noise(100_000)).unwrap();
        fs::write(d.join("empty"), b"").unwrap();
        fs::write(d.join("big.txt"), sample(2_500_000, 7)).unwrap();
        let mut w = Writer::new(fs::File::create(d.join("o.zip")).unwrap());
        w.add_dir("dir", (0, 0x21)).unwrap();
        for n in ["text.txt", "noise.bin", "empty"] {
            w.add_prepared(prepare(format!("dir/{n}"), &d.join(n)).unwrap()).unwrap();
        }
        let mut seen = 0;
        w.add_stream("dir/big.txt".into(), &d.join("big.txt"), |n| { seen += n; true }).unwrap();
        assert_eq!(seen, 2_500_000);
        w.finish().unwrap();
        extract(&d.join("o.zip"), &d.join("back"), |_| {}, |_| true).unwrap();
        for n in ["text.txt", "noise.bin", "empty", "big.txt"] {
            assert_eq!(fs::read(d.join(n)).unwrap(), fs::read(d.join("back/dir").join(n)).unwrap(), "{n}");
        }
        let _ = fs::remove_dir_all(&d);
    }

    #[test]
    fn rejects_zip_slip_and_damage() {
        let o = Path::new(r"C:\x\out");
        assert!(safe_path(o, "../evil.txt").is_err());
        assert!(safe_path(o, r"a\..\..\evil.txt").is_err());
        assert!(safe_path(o, "C:/evil.txt").is_err());
        assert!(safe_path(o, "a:b.txt").is_err());
        assert_eq!(safe_path(o, "/abs/ok.txt").unwrap(), Some(o.join("abs").join("ok.txt")));
        assert_eq!(safe_path(o, "").unwrap(), None);
        // a flipped byte in the data is caught by the checksum or by the decoder
        let d = tmp("bad");
        fs::write(d.join("a.txt"), sample(50_000, 8)).unwrap();
        let mut w = Writer::new(fs::File::create(d.join("o.zip")).unwrap());
        w.add_prepared(prepare("a.txt".into(), &d.join("a.txt")).unwrap()).unwrap();
        w.finish().unwrap();
        let mut b = fs::read(d.join("o.zip")).unwrap();
        b[200] ^= 0x55;
        fs::write(d.join("bad.zip"), b).unwrap();
        assert!(extract(&d.join("bad.zip"), &d.join("out"), |_| {}, |_| true).is_err());
        assert!(extract(&d.join("a.txt"), &d.join("out2"), |_| {}, |_| true).is_err(), "not an archive");
        let _ = fs::remove_dir_all(&d);
    }

    #[test]
    fn matches_reach_across_chunks() {
        // the second chunk starts with the 20 KB that ended the first: the window carries over
        let tail = sample(20_000, 11);
        let mut d = sample(CHUNK - tail.len(), 12);
        d.extend(&tail);
        d.extend(&tail);
        d.extend(sample(5000, 13));
        round(&d);
        let (a, b) = (deflate(&d).len(), deflate(&d[..CHUNK]).len() + deflate(&d[CHUNK..]).len());
        assert!(a + 3_000 < b, "{a} vs {b}: the repeat should cost almost nothing");
    }

    #[test]
    fn random_looking_data_is_stored_fast() {
        let n = noise(3_000_000);
        let t = std::time::Instant::now();
        let z = deflate(&n);
        assert!(z.len() < n.len() + 400, "stored blocks add only headers");
        assert!(t.elapsed() < std::time::Duration::from_millis(500));
        round(&n);
    }

    #[test]
    fn zip64_fields_with_a_small_limit() {
        let d = tmp("z64");
        fs::write(d.join("a.txt"), sample(5000, 21)).unwrap();
        fs::write(d.join("b.txt"), sample(9000, 22)).unwrap();
        let mut w = Writer::new(fs::File::create(d.join("o.zip")).unwrap()).with_limit(100);
        w.add_dir("dir", (0, 0x21)).unwrap();
        w.add_prepared(prepare("dir/a.txt".into(), &d.join("a.txt")).unwrap()).unwrap();
        w.add_stream("dir/b.txt".into(), &d.join("b.txt"), |_| true).unwrap(); // data descriptor with 8-byte sizes
        w.finish().unwrap();
        extract(&d.join("o.zip"), &d.join("back"), |_| {}, |_| true).unwrap();
        assert_eq!(fs::read(d.join("a.txt")).unwrap(), fs::read(d.join("back/dir/a.txt")).unwrap());
        assert_eq!(fs::read(d.join("b.txt")).unwrap(), fs::read(d.join("back/dir/b.txt")).unwrap());
        // an independent reader finds the same through the ZIP64 directory
        let mut z = zip::ZipArchive::new(fs::File::open(d.join("o.zip")).unwrap()).unwrap();
        for (n, f) in [("dir/a.txt", "a.txt"), ("dir/b.txt", "b.txt")] {
            let mut got = vec![];
            z.by_name(n).unwrap().read_to_end(&mut got).unwrap();
            assert_eq!(got, fs::read(d.join(f)).unwrap(), "{n}");
        }
        let _ = fs::remove_dir_all(&d);
    }

    #[test]
    fn times_survive_a_round_trip() {
        let d = tmp("time");
        fs::create_dir(d.join("sub")).unwrap();
        fs::write(d.join("sub/f.txt"), b"x").unwrap();
        let then = UNIX_EPOCH + Duration::from_secs(1_500_000_000); // 2017-07-14, even seconds
        let f = fs::OpenOptions::new().write(true).open(d.join("sub/f.txt")).unwrap();
        f.set_modified(then).unwrap();
        drop(f);
        set_mtime(&d.join("sub"), then);
        let mut w = Writer::new(fs::File::create(d.join("o.zip")).unwrap());
        w.add_dir("sub", dos_time(&d.join("sub"))).unwrap();
        w.add_prepared(prepare("sub/f.txt".into(), &d.join("sub/f.txt")).unwrap()).unwrap();
        w.finish().unwrap();
        extract(&d.join("o.zip"), &d.join("back"), |_| {}, |_| true).unwrap();
        for p in ["back/sub/f.txt", "back/sub"] {
            let got = fs::metadata(d.join(p)).unwrap().modified().unwrap();
            assert_eq!(got, then, "{p}");
        }
        let _ = fs::remove_dir_all(&d);
    }

    #[test]
    fn old_dos_names_and_cancel() {
        assert_eq!(CP437_HIGH.chars().count(), 128);
        assert_eq!(decode_name(&[0x82, b'a', 0x94], 0), "éaö");
        assert_eq!(decode_name("é.txt".as_bytes(), 0), "é.txt");
        assert_eq!(decode_name(&[b'a', 0xFF], 0x800), "a\u{FFFD}");
        let d = tmp("cancel");
        fs::write(d.join("a.txt"), sample(3_000_000, 31)).unwrap();
        let mut w = Writer::new(fs::File::create(d.join("o.zip")).unwrap());
        w.add_prepared(prepare("a.txt".into(), &d.join("a.txt")).unwrap()).unwrap();
        w.finish().unwrap();
        let (mut total, mut seen) = (0, 0);
        let r = extract(&d.join("o.zip"), &d.join("out"), |t| total = t, |n| { seen += n; false });
        assert_eq!(r, Err("cancelled".to_string()));
        assert_eq!(total, 3_000_000);
        assert!(seen > 0 && seen < 3_000_000);
        let mut w = Writer::new(fs::File::create(d.join("p.zip")).unwrap());
        let e = w.add_stream("a.txt".into(), &d.join("a.txt"), |_| false).unwrap_err();
        assert_eq!(e.kind(), io::ErrorKind::Interrupted);
        let _ = fs::remove_dir_all(&d);
    }

    #[test]
    fn browses_an_archive_like_folders() {
        let d = tmp("browse");
        for (n, c) in [("a.txt", "A"), ("b.txt", "BB")] {
            fs::write(d.join(n), c).unwrap();
        }
        let mut w = Writer::new(fs::File::create(d.join("o.zip")).unwrap());
        w.add_prepared(prepare("top.txt".into(), &d.join("a.txt")).unwrap()).unwrap();
        w.add_prepared(prepare("dir/sub/deep.txt".into(), &d.join("b.txt")).unwrap()).unwrap(); // no entry for dir/ or dir/sub/
        w.add_prepared(prepare("dir/mid.txt".into(), &d.join("a.txt")).unwrap()).unwrap();
        w.add_dir("empty", (0, 0x21)).unwrap();
        w.finish().unwrap();
        let z = d.join("o.zip");
        let names = |inner: &str| list_dir(&z, inner).unwrap().into_iter().map(|i| format!("{}{}", i.name, if i.dir { "/" } else { "" })).collect::<Vec<_>>();
        assert_eq!(names(""), ["dir/", "empty/", "top.txt"]);
        assert_eq!(names("dir"), ["mid.txt", "sub/"]);
        assert_eq!(names("dir/sub"), ["deep.txt"]);
        assert!(names("nope").is_empty());
        assert_eq!(list_dir(&z, "dir/sub").unwrap()[0].size, 1 + 1);
        // taking things out: a file, and (as another selection) a folder with what is in it, each under its own name
        extract_some(&z, &["dir/sub/deep.txt".to_string()], &d.join("o1")).unwrap();
        extract_some(&z, &["dir".to_string(), "top.txt".to_string()], &d.join("o2")).unwrap();
        assert_eq!(fs::read_to_string(d.join("o1/deep.txt")).unwrap(), "BB");
        assert_eq!(fs::read_to_string(d.join("o2/dir/sub/deep.txt")).unwrap(), "BB");
        assert!(d.join("o2/dir/mid.txt").is_file() && d.join("o2/top.txt").is_file() && !d.join("o2/empty").exists());
        // paths into the archive
        assert_eq!(split_zip(&z.join("dir").join("sub")), Some((z.clone(), "dir/sub".to_string())));
        assert_eq!(split_zip(&z), Some((z.clone(), String::new())));
        assert_eq!(split_zip(&d), None);
        let _ = fs::remove_dir_all(&d);
    }

    /// By hand: `cargo test -p rust-explorer --release zipx::tests::bench -- --ignored --nocapture`. Ours against the zip crate (miniz_oxide) on the repo's sources.
    #[test]
    #[ignore]
    fn bench() {
        use std::io::Write;
        let mut text = vec![];
        let mut stack = vec![PathBuf::from(r"..\\..\\plugins"), PathBuf::from(r"..\\..\\src")];
        while let Some(d) = stack.pop() {
            for e in fs::read_dir(d).into_iter().flatten().flatten() {
                let p = e.path();
                if p.is_dir() && p.file_name().is_some_and(|n| n != "target") {
                    stack.push(p);
                } else if p.extension().is_some_and(|x| x == "rs") {
                    text.extend(fs::read(p).unwrap());
                }
            }
        }
        let mut exe = fs::read(r"C:\Windows\System32\kernel32.dll").unwrap_or_default();
        exe.truncate(2 << 20);
        for (name, data) in [("sources", text), ("dll", exe), ("noise", noise(2 << 20))] {
            if data.is_empty() {
                continue;
            }
            let t = std::time::Instant::now();
            let ours = deflate(&data);
            let t_ours = t.elapsed();
            let t = std::time::Instant::now();
            let mut w = zip::ZipWriter::new(io::Cursor::new(vec![]));
            w.start_file("a", zip::write::SimpleFileOptions::default().compression_method(zip::CompressionMethod::Deflated)).unwrap();
            w.write_all(&data).unwrap();
            let theirs = w.finish().unwrap().into_inner().len();
            let t_theirs = t.elapsed();
            let t = std::time::Instant::now();
            let mut back = vec![];
            inflate(&ours[..], &mut back, &mut |_| true).unwrap();
            println!("BENCH {name} {} B: ours {} B in {:?} (inflate {:?}), zip crate {} B in {:?}", data.len(), ours.len(), t_ours, t.elapsed(), theirs, t_theirs);
        }
    }
}