inflate.rs

//! deflate の展開 (RFC 1951)
//!
//! ZIP のエントリはほとんどが deflate で縮めてある。ここはそれを元に戻すところである。
//!
//! # 表引きで符号を読む
//!
//! ハフマン符号は 1 ビットずつ木をたどっても読めるが、記号ごとに平均 8 回まわることになる。
//! ここでは先に表を作っておき、流れの先頭の 11 ビット (距離は 8 ビット) で 1 回引く。
//! 符号がそれより長いときは、表の項目が小さな表を指しているので、残りのビットでもう 1 回引く。
//!
//! 表の項目には、使うビット数、記号の種類、値を詰めてある。長さと距離の記号なら、
//! 値は基準値で、種類は追加ビット数である。1 回引くだけで、長さや距離の計算に要るものがそろう。
//!
//! # ビットは 8 バイトずつ補う
//!
//! 読みかけのビットは 64 ビットの入れ物に持ち、減ったら入力の 8 バイトをまとめて読んで足す。
//! 長さと距離の組は、符号と追加ビットを合わせても 48 ビットに収まる。
//! だから補ったあとは、組 1 つを途中で補わずに読み切れる。
//!
//! # 出口には余白を持つ
//!
//! 出口の入れ物には、一致 1 つぶんより広い余白を常に空けておく。
//! 一致を写すときは 16 バイト単位で写し、はみ出したぶんは次に出すバイトで上書きされる。
//!
//! # 入口も出口もためこまない
//!
//! 巨大なシートは、縮めたままでも数百 MB、展開すると数 GB になる。どちらもメモリには置けない。
//! [`inflate_stream`] は縮めたバイトを少しずつ受け取り、展開できたぶんを少しずつ渡す。
//! 手元に残すのは、読みかけの入力と、後ろ向きの参照に要る 32KB だけである。
//! 小さなパートは [`inflate`] で一度に受け取ればよい。

use crate::error::Error;


/// 文字と長さの表で、1 回目に引くビット数
const LITERAL_BITS: u32 = 11;

/// 距離の表で、1 回目に引くビット数
const DISTANCE_BITS: u32 = 8;

/// 符号長そのものを送る符号の表で、1 回目に引くビット数。符号は 7 ビットまでなので、1 回で済む
const ORDER_BITS: u32 = 7;

/// 後ろ向きの参照が届く距離。deflate の決まりで 32768 バイト
const HISTORY: usize = 32768;

/// これだけたまったら呼び出し側へ渡す
const FLUSH_LIMIT: usize = 256 * 1024;

/// 読み終えた入力をこれだけためたら捨てる
const COMPACT: usize = 256 * 1024;

/// 出口に空けておく余白。一致 1 つの最大 258 バイトを、16 バイト単位で写しても収まる広さ
const MARGIN: usize = 272;

/// 項目の種類。値が文字
const LITERAL: u32 = 16;

/// 項目の種類。区画の終わり
const END: u32 = 17;

/// 項目の種類。小さな表を指す。値がその表の位置、使うビット数のところにその表のビット数が入る
const LINK: u32 = 18;

/// 項目の種類。どの符号にも当たらない
const BROKEN: u32 = 19;

/// どの符号にも当たらない項目
const BROKEN_ENTRY: u32 = BROKEN << 8;

/// 長さ符号 257..285 の基準値
const LENGTH_BASE: [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,
];

/// 長さ符号 257..285 の追加ビット数
const LENGTH_EXTRA: [u32; 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,
];

/// 距離符号 0..29 の基準値
const DISTANCE_BASE: [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,
];

/// 距離符号 0..29 の追加ビット数
const DISTANCE_EXTRA: [u32; 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 ORDER: [usize; 19] = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];


/// 縮めたバイト列を元に戻して、全部まとめて返す
pub fn inflate(data: &[u8]) -> Result<Vec<u8>, Error> {
    inflate_sized(data, 0)
}


/// 展開後の大きさが分かっているときは、先に場所を取っておく
pub fn inflate_sized(data: &[u8], size: usize) -> Result<Vec<u8>, Error> {
    inflate_owned(data.to_vec(), size)
}


/// 縮めたバイト列を受け取って展開する。写さずにそのまま読むので、手元にあるときはこちらが速い
pub fn inflate_owned(data: Vec<u8>, size: usize) -> Result<Vec<u8>, Error> {
    let mut output = Output {
        window: vec![0; size + MARGIN],
        length: 0,
        sent: 0,
        sink: None,
    };

    let mut once = Some(data);
    let mut supply = move || Ok(once.take());
    run(&mut supply, &mut output)?;
    output.window.truncate(output.length);
    Ok(output.window)
}


/// そろっているバイト列を展開しながら、出てきたぶんを少しずつ sink へ渡す
pub fn inflate_with(
    data: &[u8],
    sink: &mut dyn FnMut(&[u8]) -> Result<(), Error>,
) -> Result<(), Error> {
    let mut once = Some(data.to_vec());
    let mut supply = move || Ok(once.take());
    inflate_stream(&mut supply, sink)
}


/// 縮めたバイトを少しずつ受け取り、展開したぶんを少しずつ sink へ渡す
///
/// supply は続きを返す。もう続きがなければ None を返す。
/// sink は出力の続きを順に受け取る。同じバイトが二度渡ることはない。
pub fn inflate_stream(
    supply: &mut dyn FnMut() -> Result<Option<Vec<u8>>, Error>,
    sink: &mut dyn FnMut(&[u8]) -> Result<(), Error>,
) -> Result<(), Error> {
    let mut output = Output {
        window: vec![0; FLUSH_LIMIT + HISTORY + MARGIN],
        length: 0,
        sent: 0,
        sink: Some(sink),
    };

    run(supply, &mut output)?;
    output.flush(true)
}


/// 出力を貯めるところ
struct Output<'a> {
    /// 出したバイトと、その後ろの余白。sink があるときは、後ろ向きの参照に要るぶんだけを残す
    window: Vec<u8>,
    /// window のうち、出したバイトの数
    length: usize,
    /// window の先頭から、すでに sink へ渡したバイト数
    sent: usize,
    /// 渡す先。ない場合は window に全部ためる
    sink: Option<&'a mut dyn FnMut(&[u8]) -> Result<(), Error>>,
}


impl Output<'_> {
    /// 後ろに extra バイトの余白を空ける
    fn reserve(&mut self, extra: usize) -> Result<(), Error> {
        if self.length + extra <= self.window.len() {
            return Ok(());
        }

        if self.sink.is_some() {
            self.flush(true)?;
        }

        if self.length + extra > self.window.len() {
            let size = (self.window.len() * 2).max(self.length + extra);
            self.window.resize(size, 0);
        }

        Ok(())
    }

    /// そろっているバイト列を出す
    fn write(&mut self, piece: &[u8]) -> Result<(), Error> {
        self.reserve(piece.len() + MARGIN)?;
        self.window[self.length..self.length + piece.len()].copy_from_slice(piece);
        self.length += piece.len();
        Ok(())
    }

    /// distance だけ戻ったところから length バイト写す。余白は空けてある前提である
    fn copy(&mut self, distance: usize, length: usize) -> Result<(), Error> {
        if distance > self.length {
            return Err(Error::new("圧縮データが届かないところを参照しています"));
        }

        let start = self.length - distance;
        let end = self.length + length;

        if distance >= 16 {
            // 写す元の 16 バイトは、どれも写し先より前にあるので、すでに出来上がっている
            let mut done = 0;

            while done < length {
                self.window.copy_within(start + done..start + done + 16, self.length + done);
                done += 16;
            }
        } else if distance == 1 {
            let byte = self.window[start];
            self.window[self.length..end].fill(byte);
        } else {
            // 重なっているので 1 バイトずつ。写したそばから写す元になる
            for index in 0..length {
                self.window[self.length + index] = self.window[start + index];
            }
        }

        self.length = end;
        Ok(())
    }

    /// たまったぶんを渡す。force でないときは、たまるまで何もしない
    fn flush(&mut self, force: bool) -> Result<(), Error> {
        let Some(sink) = self.sink.as_mut() else {
            return Ok(());
        };

        if !force && self.length < FLUSH_LIMIT + HISTORY {
            return Ok(());
        }

        if self.length > self.sent {
            sink(&self.window[self.sent..self.length])?;
            self.sent = self.length;
        }

        if self.length > HISTORY {
            let start = self.length - HISTORY;
            self.window.copy_within(start..self.length, 0);
            self.length = HISTORY;
            self.sent = HISTORY;
        }

        Ok(())
    }
}


/// ビットを下位から順に取り出す
///
/// data は縮めたバイトの読みかけの区間である。読み終えた前のほうは捨て、
/// 足りなくなったら supply から続きを受け取る。
///
/// hold の count より上のビットにも、続きのバイトが入っていることがある。
/// 8 バイトまとめて読んだとき、数えきれなかった端のぶんである。中身は続きのバイトそのものなので、
/// あとで同じ位置へ同じバイトを足しても変わらない。
struct Bits<'a> {
    data: Vec<u8>,
    /// data のうち、hold へ取り込んだところまでの位置
    position: usize,
    /// 取り込んだビット。下位が先に読むほう
    hold: u64,
    /// hold に入っている有効なビット数
    count: u32,
    /// 続きをくれるもの
    supply: &'a mut dyn FnMut() -> Result<Option<Vec<u8>>, Error>,
    /// supply が尽きたか
    ended: bool,
}


impl Bits<'_> {
    /// 続きを受け取る。もうなければ false
    fn pull(&mut self) -> Result<bool, Error> {
        if self.ended {
            return Ok(false);
        }

        match (self.supply)()? {
            Some(piece) => {
                // 空なら、受け取ったものを写さずにそのまま持つ
                if self.data.is_empty() {
                    self.data = piece;
                } else {
                    self.data.extend_from_slice(&piece);
                }

                Ok(true)
            }

            None => {
                self.ended = true;
                Ok(false)
            }
        }
    }

    /// 読み終えた前のほうを捨てる
    fn compact(&mut self) {
        let keep = self.byte_position();

        if keep < COMPACT {
            return;
        }

        self.data.copy_within(keep.., 0);
        self.data.truncate(self.data.len() - keep);
        self.position -= keep;
    }

    /// hold を埋められるだけ埋める
    fn refill(&mut self) -> Result<(), Error> {
        // 8 バイト読めるなら、まとめて読む。取り込めたのは count が 56 以上になるまでのバイトである
        if self.position + 8 <= self.data.len() && self.count < 64 {
            let mut word = [0u8; 8];
            word.copy_from_slice(&self.data[self.position..self.position + 8]);
            self.hold |= u64::from_le_bytes(word) << self.count;
            self.position += ((63 - self.count) >> 3) as usize;
            self.count |= 56;
            return Ok(());
        }

        // 入力の終わりに近い。1 バイトずつ足し、足りなければ続きを受け取る
        while self.count <= 56 {
            if self.position >= self.data.len() {
                self.compact();

                if !self.pull()? {
                    return Ok(());
                }

                continue;
            }

            self.hold |= (self.data[self.position] as u64) << self.count;
            self.position += 1;
            self.count += 8;
        }

        Ok(())
    }

    /// n ビット取り出す
    fn take(&mut self, n: u32) -> Result<u32, Error> {
        if self.count < n {
            self.refill()?;
        }

        if self.count < n {
            return Err(Error::new("圧縮データが途中で終わっています"));
        }

        let value = (self.hold & ((1u64 << n) - 1)) as u32;
        self.hold >>= n;
        self.count -= n;
        Ok(value)
    }

    /// バイトの境目までビットを捨てる
    fn align(&mut self) {
        let extra = self.count % 8;
        self.hold >>= extra;
        self.count -= extra;
    }

    /// 境目にそろえたあとの、data 上の読み出し位置
    fn byte_position(&self) -> usize {
        self.position - (self.count / 8) as usize
    }

    /// 読み出し位置から need バイト用意する
    fn ready(&mut self, need: usize) -> Result<(), Error> {
        loop {
            if self.data.len() - self.byte_position() >= need {
                return Ok(());
            }

            self.compact();

            if !self.pull()? {
                return Err(Error::new("圧縮データが途中で終わっています"));
            }
        }
    }

    /// 境目にそろえたあと、length バイトぶん進める
    fn skip(&mut self, length: usize) {
        let start = self.byte_position();
        self.position = start + length;
        self.hold = 0;
        self.count = 0;
    }

    /// 表を引いて記号を 1 つ読む。項目の種類と値を返す
    fn decode(&mut self, table: &Table) -> Result<(u32, u32), Error> {
        if self.count < 15 {
            self.refill()?;
        }

        let entry = table.lookup(self.hold);
        let used = entry & 0xff;

        if used > self.count {
            return Err(Error::new("圧縮データが途中で終わっています"));
        }

        self.hold >>= used;
        self.count -= used;
        Ok(((entry >> 8) & 0xff, entry >> 16))
    }
}


/// 符号長の並びから作った引き表
///
/// 項目は、下位 8 ビットが使うビット数、次の 8 ビットが種類、上位 16 ビットが値である。
/// 種類が 0 から 15 の項目は長さか距離で、種類が追加ビット数、値が基準値になる。
struct Table {
    entry: Vec<u32>,
    /// 1 回目に引くビット数
    bits: u32,
}


impl Table {
    /// 流れの先頭のビットで項目を引く
    fn lookup(&self, hold: u64) -> u32 {
        let first = self.entry[(hold & ((1u64 << self.bits) - 1)) as usize];

        if (first >> 8) & 0xff != LINK {
            return first;
        }

        let sub = first & 0xff;
        let index = (first >> 16) as usize + ((hold >> self.bits) & ((1u64 << sub) - 1)) as usize;
        self.entry[index]
    }
}


/// 文字と長さの記号から、項目の種類と値を決める
fn literal_kind(symbol: usize) -> (u32, u32) {
    match symbol {
        0..=255 => (LITERAL, symbol as u32),
        256 => (END, 0),
        257..=285 => (LENGTH_EXTRA[symbol - 257], LENGTH_BASE[symbol - 257] as u32),
        _ => (BROKEN, 0),
    }
}


/// 距離の記号から、項目の種類と値を決める
fn distance_kind(symbol: usize) -> (u32, u32) {
    match symbol {
        0..=29 => (DISTANCE_EXTRA[symbol], DISTANCE_BASE[symbol] as u32),
        _ => (BROKEN, 0),
    }
}


/// 符号長そのものを送る記号は、記号をそのまま値にする
fn order_kind(symbol: usize) -> (u32, u32) {
    (LITERAL, symbol as u32)
}


/// 符号長の並びから引き表を作る
///
/// 記号が 1 つだけの符号は、埋まりきらない不完全な符号になる。
/// 中身が空の区画や、一致がまったくない区画で実際に出てくるので、single を渡して受ける。
/// 受けるのは記号が 1 つ以下のときだけで、それ以外の不完全な符号は壊れたデータとして弾く。
/// 符号長そのものを送る符号では、これも許さない。
fn build(length: &[u8], bits: u32, single: bool, kind: fn(usize) -> (u32, u32)) -> Result<Table, Error> {
    let mut count = [0u16; 16];

    for value in length {
        count[*value as usize] += 1;
    }

    count[0] = 0;
    let mut left: i32 = 1;

    for size in 1..16 {
        left <<= 1;
        left -= count[size] as i32;

        if left < 0 {
            return Err(Error::new("圧縮データの符号長が多すぎます"));
        }
    }

    let longest = (1..16).rev().find(|size| count[*size] != 0).unwrap_or(0);

    if left > 0 && !(single && longest <= 1) {
        return Err(Error::new("圧縮データの符号長が足りません"));
    }

    // 符号長ごとの、最初の符号
    let mut first = [0u32; 16];
    let mut code = 0;

    for size in 1..16 {
        code = (code + count[size - 1] as u32) << 1;
        first[size] = code;
    }

    let size = 1usize << bits;
    let mask = size - 1;
    let mut entry = vec![BROKEN_ENTRY; size];

    // 1 回目の表に収まらない符号は、先頭の bits ビットごとに小さな表へまとめる。
    // 小さな表の大きさは、そこに入るいちばん長い符号で決まる
    let mut deepest = vec![0u8; size];
    let mut next = first;

    for value in length {
        let value = *value as u32;

        if value == 0 {
            continue;
        }

        let assigned = next[value as usize];
        next[value as usize] += 1;

        if value > bits {
            let place = reverse(assigned, value) as usize & mask;
            deepest[place] = deepest[place].max(value as u8);
        }
    }

    for place in 0..size {
        if deepest[place] == 0 {
            continue;
        }

        let sub = deepest[place] as u32 - bits;
        entry[place] = ((entry.len() as u32) << 16) | (LINK << 8) | sub;
        entry.resize(entry.len() + (1 << sub), BROKEN_ENTRY);
    }

    // 流れの先頭ビットが符号の最上位なので、表を引くには符号を逆に並べる
    let mut next = first;

    for (symbol, value) in length.iter().enumerate() {
        let value = *value as u32;

        if value == 0 {
            continue;
        }

        let assigned = next[value as usize];
        next[value as usize] += 1;

        let reversed = reverse(assigned, value) as usize;
        let (tag, number) = kind(symbol);
        let item = (number << 16) | (tag << 8) | value;

        if value <= bits {
            let mut place = reversed;

            while place < size {
                entry[place] = item;
                place += 1 << value;
            }

            continue;
        }

        let link = entry[reversed & mask];
        let offset = (link >> 16) as usize;
        let sub = link & 0xff;
        let mut place = reversed >> bits;

        while place < 1 << sub {
            entry[offset + place] = item;
            place += 1 << (value - bits);
        }
    }

    Ok(Table {entry, bits})
}


/// 下位 bits ビットを逆に並べる
fn reverse(value: u32, bits: u32) -> u32 {
    value.reverse_bits() >> (32 - bits)
}


/// 区画を順に読んで展開する
fn run(
    supply: &mut dyn FnMut() -> Result<Option<Vec<u8>>, Error>,
    output: &mut Output,
) -> Result<(), Error> {
    let mut bits = Bits {
        data: Vec::new(),
        position: 0,
        hold: 0,
        count: 0,
        supply,
        ended: false,
    };

    // 決め打ちの符号表は、使うときに一度だけ作る
    let mut fixed: Option<(Table, Table)> = None;

    loop {
        let last = bits.take(1)?;
        let kind = bits.take(2)?;

        match kind {
            0 => stored(&mut bits, output)?,

            1 => {
                if fixed.is_none() {
                    fixed = Some(fixed_table()?);
                }

                if let Some((literal, distance)) = &fixed {
                    block(&mut bits, output, literal, distance)?;
                }
            }

            2 => {
                let (literal, distance) = dynamic(&mut bits)?;
                block(&mut bits, output, &literal, &distance)?;
            }

            _ => return Err(Error::new("圧縮データに知らない区画の種類があります")),
        }

        output.flush(false)?;

        if last == 1 {
            return Ok(());
        }
    }
}


/// 縮めていない区画をそのまま写す
fn stored(bits: &mut Bits, output: &mut Output) -> Result<(), Error> {
    bits.align();
    bits.ready(4)?;
    let start = bits.byte_position();
    let length = u16::from_le_bytes([bits.data[start], bits.data[start + 1]]) as usize;
    let check = u16::from_le_bytes([bits.data[start + 2], bits.data[start + 3]]) as usize;

    if length != !check & 0xffff {
        return Err(Error::new("縮めていない区画の長さが合いません"));
    }

    bits.ready(4 + length)?;
    let start = bits.byte_position();
    output.write(&bits.data[start + 4..start + 4 + length])?;
    bits.skip(4 + length);
    Ok(())
}


/// 決め打ちの符号表
fn fixed_table() -> Result<(Table, Table), Error> {
    let mut literal = [0u8; 288];

    for value in 0..288 {
        literal[value] = match value {
            0..=143 => 8,
            144..=255 => 9,
            256..=279 => 7,
            _ => 8,
        };
    }

    // 距離符号は 32 個ぶん 5 ビットで置く。30 と 31 は現れないが、符号としては埋まっている
    let distance = [5u8; 32];

    Ok((
        build(&literal, LITERAL_BITS, false, literal_kind)?,
        build(&distance, DISTANCE_BITS, false, distance_kind)?,
    ))
}


/// 区画の頭に載っている符号表を読む
fn dynamic(bits: &mut Bits) -> Result<(Table, Table), Error> {
    let literal_count = bits.take(5)? as usize + 257;
    let distance_count = bits.take(5)? as usize + 1;
    let order_count = bits.take(4)? as usize + 4;

    if literal_count > 286 || distance_count > 30 {
        return Err(Error::new("圧縮データの符号表が大きすぎます"));
    }

    let mut order_length = [0u8; 19];

    for index in 0..order_count {
        order_length[ORDER[index]] = bits.take(3)? as u8;
    }

    let order = build(&order_length, ORDER_BITS, false, order_kind)?;
    let mut length = vec![0u8; literal_count + distance_count];
    let mut index = 0;

    while index < length.len() {
        let (tag, symbol) = bits.decode(&order)?;

        if tag != LITERAL {
            return Err(Error::new("圧縮データの符号長が壊れています"));
        }

        match symbol {
            0..=15 => {
                length[index] = symbol as u8;
                index += 1;
            }

            16 => {
                if index == 0 {
                    return Err(Error::new("圧縮データの符号長に写す元がありません"));
                }

                let previous = length[index - 1];
                let repeat = bits.take(2)? as usize + 3;
                index = fill(&mut length, index, repeat, previous)?;
            }

            17 => {
                let repeat = bits.take(3)? as usize + 3;
                index = fill(&mut length, index, repeat, 0)?;
            }

            18 => {
                let repeat = bits.take(7)? as usize + 11;
                index = fill(&mut length, index, repeat, 0)?;
            }

            _ => return Err(Error::new("圧縮データの符号長が壊れています")),
        }
    }

    let literal = build(&length[..literal_count], LITERAL_BITS, true, literal_kind)?;
    let distance = build(&length[literal_count..], DISTANCE_BITS, true, distance_kind)?;
    Ok((literal, distance))
}


/// 符号長を repeat 個ぶん埋める
fn fill(length: &mut [u8], index: usize, repeat: usize, value: u8) -> Result<usize, Error> {
    if index + repeat > length.len() {
        return Err(Error::new("圧縮データの符号長が多すぎます"));
    }

    for place in index..index + repeat {
        length[place] = value;
    }

    Ok(index + repeat)
}


/// 符号表が決まったあとの本体。記号を読んでは出していく
fn block(bits: &mut Bits, output: &mut Output, literal: &Table, distance: &Table) -> Result<(), Error> {
    loop {
        if output.length + MARGIN > output.window.len() {
            output.reserve(MARGIN)?;
        }

        // 長さと距離の組 1 つぶん (最大 48 ビット) を、ここで一度に補っておく
        if bits.count < 48 {
            bits.refill()?;
        }

        let entry = literal.lookup(bits.hold);
        let used = entry & 0xff;

        if used > bits.count {
            return Err(Error::new("圧縮データが途中で終わっています"));
        }

        bits.hold >>= used;
        bits.count -= used;
        let tag = (entry >> 8) & 0xff;

        if tag == LITERAL {
            output.window[output.length] = (entry >> 16) as u8;
            output.length += 1;
            continue;
        }

        if tag == END {
            return Ok(());
        }

        if tag > 15 {
            return Err(Error::new("圧縮データの符号が壊れています"));
        }

        let length = (entry >> 16) as usize + extra(bits, tag)? as usize;
        let entry = distance.lookup(bits.hold);
        let used = entry & 0xff;

        if used > bits.count {
            return Err(Error::new("圧縮データが途中で終わっています"));
        }

        bits.hold >>= used;
        bits.count -= used;
        let tag = (entry >> 8) & 0xff;

        if tag > 15 {
            return Err(Error::new("圧縮データの距離符号が壊れています"));
        }

        let reach = (entry >> 16) as usize + extra(bits, tag)? as usize;
        output.copy(reach, length)?;
    }
}


/// 追加ビットを読む。補ってあるので、足りないのはデータが途中で終わっているときだけである
fn extra(bits: &mut Bits, n: u32) -> Result<u32, Error> {
    if n > bits.count {
        return Err(Error::new("圧縮データが途中で終わっています"));
    }

    let value = (bits.hold & ((1u64 << n) - 1)) as u32;
    bits.hold >>= n;
    bits.count -= n;
    Ok(value)
}