deflate.rs

//! deflate の圧縮 (RFC 1951)
//!
//! 一致を探して長さと距離に置き換え、出てきた記号をハフマン符号で詰める。
//!
//! # 一致の探し方
//!
//! 3 バイトのハッシュで同じ並びの候補をつなぎ、新しいほうから順にたどって最長の一致を採る。
//! たどる本数には上限を置く。深くたどるほど縮むが、時間はそれ以上に増える。
//! 一致が見つかっても、1 文字ずらしたほうが長く取れるならそちらを採る (lazy)。
//!
//! # 区画の選び方
//!
//! 区画ごとに、その場で作った符号表 (dynamic)、決め打ちの符号表 (fixed)、
//! 縮めずそのまま (stored) の 3 通りを見積もり、いちばん短いものを出す。
//! 区画に入れる入力は 65535 バイトまでにしてある。stored がこの長さまでしか持てないので、
//! 縮まらないデータでも必ず stored に逃げられるようにするためである。
//!
//! # 少しずつ渡せる
//!
//! [`Deflate::write`] は何度でも呼べる。前の 32KB は次の一致を探すために残し、
//! それより前は捨てる。捨てるときにハッシュをつなぎ直すので、区画をまたぐ一致も見つかる。

use std::collections::BinaryHeap;


/// 一致とみなす最短の長さ
const MIN_MATCH: usize = 3;

/// 一致の最長。deflate の決まり
const MAX_MATCH: usize = 258;

/// 後ろ向きの参照が届く距離
const HISTORY: usize = 32768;

/// ハッシュ表の大きさ
const HASH_SIZE: usize = 1 << 15;

/// つながりの終わり
const EMPTY: u32 = u32::MAX;

/// 候補をたどる本数の上限
const MAX_CHAIN: usize = 128;

/// これだけ長い一致が取れたら、それ以上は探さない
const NICE_MATCH: usize = 128;

/// 1 区画に入れる入力の長さ。stored に逃げられる上限に合わせる
const BLOCK: usize = 65535;

/// 入力をこれだけためたら、履歴を切り詰める
const CHUNK: usize = 512 * 1024;

/// 文字と長さの記号数 (0..255 の文字、256 の区画終わり、257..285 の長さ)
const LITERAL_COUNT: usize = 286;

/// 距離の記号数
const DISTANCE_COUNT: usize = 30;

/// 符号長そのものを送る記号数
const ORDER_COUNT: usize = 19;

/// 長さ符号 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; ORDER_COUNT] = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];

/// 長さ 3..258 から長さ符号を引く表
static LENGTH_CODE: [u8; 256] = length_code();

/// 距離 1..256 から距離符号を引く表
static DISTANCE_SMALL: [u8; 256] = distance_small();

/// 距離 257..32768 を 128 で割った値から距離符号を引く表
static DISTANCE_LARGE: [u8; 256] = distance_large();


/// 長さから符号を引く表を作る
const fn length_code() -> [u8; 256] {
    let mut table = [0u8; 256];
    let mut code = 0;

    while code < 29 {
        let base = LENGTH_BASE[code] as usize;
        let span = 1usize << LENGTH_EXTRA[code];
        let mut step = 0;

        while step < span && base - 3 + step < 256 {
            table[base - 3 + step] = code as u8;
            step += 1;
        }

        code += 1;
    }

    table
}


/// 短い距離から符号を引く表を作る
const fn distance_small() -> [u8; 256] {
    let mut table = [0u8; 256];
    let mut code = 0;

    while code < 16 {
        let base = DISTANCE_BASE[code] as usize;
        let span = 1usize << DISTANCE_EXTRA[code];
        let mut step = 0;

        while step < span && base + step <= 256 {
            table[base + step - 1] = code as u8;
            step += 1;
        }

        code += 1;
    }

    table
}


/// 長い距離から符号を引く表を作る
///
/// 257 以上の符号は追加ビットが 7 以上あり、受け持つ幅が 128 の倍数になる。
/// だから 128 ごとに 1 つ置けば足りる。
const fn distance_large() -> [u8; 256] {
    let mut table = [0u8; 256];
    let mut code = 16;

    while code < 30 {
        let base = DISTANCE_BASE[code] as usize;
        let stop = base + (1usize << DISTANCE_EXTRA[code]);
        let mut value = base;

        while value < stop {
            table[(value - 1) >> 7] = code as u8;
            value += 128;
        }

        code += 1;
    }

    table
}


/// 長さから長さ符号を引く
fn length_of(length: usize) -> usize {
    LENGTH_CODE[length - MIN_MATCH] as usize
}


/// 距離から距離符号を引く
fn distance_of(distance: usize) -> usize {
    if distance <= 256 {
        DISTANCE_SMALL[distance - 1] as usize
    } else {
        DISTANCE_LARGE[(distance - 1) >> 7] as usize
    }
}


/// 一致か文字か。distance が 0 なら文字
#[derive(Debug, Clone, Copy)]
struct Item {
    /// 文字そのもの、または一致の長さ
    value: u16,
    /// 一致の距離。文字のときは 0
    distance: u16,
}


/// 縮めながら少しずつ書き出す
pub struct Deflate {
    /// 履歴とこれから符号化する入力
    buffer: Vec<u8>,
    /// buffer のうち符号化を終えた位置
    done: usize,
    /// いま組み立てている区画の入力が始まる位置
    start: usize,
    /// ハッシュから最新の位置を引く
    head: Vec<u32>,
    /// 同じハッシュの一つ前の位置
    prev: Vec<u32>,
    /// この区画にためた記号
    item: Vec<Item>,
    /// 文字と長さの記号の出現数
    literal_count: [u32; LITERAL_COUNT],
    /// 距離の記号の出現数
    distance_count: [u32; DISTANCE_COUNT],
    /// 出来上がったバイト列
    output: Vec<u8>,
    /// まだバイトにならないビット
    hold: u64,
    /// hold に入っているビット数
    bits: u32,
}


impl Deflate {
    pub fn new() -> Deflate {
        Deflate {
            buffer: Vec::with_capacity(HISTORY + CHUNK + MAX_MATCH),
            done: 0,
            start: 0,
            head: vec![EMPTY; HASH_SIZE],
            prev: Vec::new(),
            item: Vec::with_capacity(BLOCK / 2),
            literal_count: [0; LITERAL_COUNT],
            distance_count: [0; DISTANCE_COUNT],
            output: Vec::new(),
            hold: 0,
            bits: 0,
        }
    }

    /// 続きの入力を渡す
    pub fn write(&mut self, data: &[u8]) {
        self.buffer.extend_from_slice(data);

        while self.buffer.len() >= HISTORY + CHUNK {
            let before = self.buffer.len();
            self.encode(false);
            self.slide();

            // 切り詰められないときは、これ以上まわしても減らない
            if self.buffer.len() == before {
                break;
            }
        }
    }

    /// 残りを出し切って終わりの印を付ける
    pub fn finish(&mut self) {
        self.encode(true);
        self.emit(true);
        self.align();
    }

    /// 出来ているぶんを取り出す
    pub fn take(&mut self) -> Vec<u8> {
        std::mem::take(&mut self.output)
    }

    /// 履歴を 32KB だけ残して前を捨て、ハッシュをつなぎ直す
    ///
    /// まだ出していない区画の入力は捨てられない。stored で出すときに元のバイトが要るので、
    /// 区画の始まりより前までしか切り詰めない。
    fn slide(&mut self) {
        if self.done <= HISTORY {
            return;
        }

        let shift = (self.done - HISTORY).min(self.start);

        if shift == 0 {
            return;
        }

        self.buffer.copy_within(shift.., 0);
        self.buffer.truncate(self.buffer.len() - shift);
        self.done -= shift;
        self.start -= shift;

        for place in self.head.iter_mut() {
            *place = EMPTY;
        }

        self.prev.clear();
        self.prev.resize(self.buffer.len(), EMPTY);

        for position in 0..self.done {
            self.insert(position);
        }
    }

    /// 位置をハッシュのつながりに足す
    fn insert(&mut self, position: usize) {
        if position + MIN_MATCH > self.buffer.len() {
            return;
        }

        if self.prev.len() < self.buffer.len() {
            self.prev.resize(self.buffer.len(), EMPTY);
        }

        let key = hash(&self.buffer, position);
        self.prev[position] = self.head[key];
        self.head[key] = position as u32;
    }

    /// position から始まる最長の一致を探す
    fn search(&self, position: usize) -> (usize, usize) {
        let most = MAX_MATCH.min(self.buffer.len() - position);

        if most < MIN_MATCH {
            return (0, 0);
        }

        let earliest = position.saturating_sub(HISTORY);
        let mut best_length = MIN_MATCH - 1;
        let mut best_distance = 0;
        let mut candidate = self.head[hash(&self.buffer, position)];
        let mut chain = MAX_CHAIN;

        while candidate != EMPTY && chain > 0 {
            let place = candidate as usize;

            if place < earliest || place >= position {
                break;
            }

            // 伸びる見込みのないものは、末尾の 1 バイトだけ見て落とす
            if self.buffer[place + best_length] == self.buffer[position + best_length] {
                let mut length = 0;

                while length < most && self.buffer[place + length] == self.buffer[position + length] {
                    length += 1;
                }

                if length > best_length {
                    best_length = length;
                    best_distance = position - place;

                    if length >= NICE_MATCH || length == most {
                        break;
                    }
                }
            }

            candidate = self.prev[place];
            chain -= 1;
        }

        if best_length >= MIN_MATCH {
            (best_length, best_distance)
        } else {
            (0, 0)
        }
    }

    /// 文字を 1 つためる
    fn push_literal(&mut self, byte: u8) {
        self.item.push(Item {value: byte as u16, distance: 0});
        self.literal_count[byte as usize] += 1;
    }

    /// 一致をためる
    fn push_match(&mut self, length: usize, distance: usize) {
        self.item.push(Item {value: length as u16, distance: distance as u16});
        self.literal_count[257 + length_of(length)] += 1;
        self.distance_count[distance_of(distance)] += 1;
    }

    /// 入力を記号に置き換えていく
    fn encode(&mut self, finish: bool) {
        let end = if finish {
            self.buffer.len()
        } else {
            self.buffer.len().saturating_sub(MAX_MATCH)
        };

        if self.prev.len() < self.buffer.len() {
            self.prev.resize(self.buffer.len(), EMPTY);
        }

        let mut position = self.done;

        while position < end {
            let (length, distance) = self.search(position);
            self.insert(position);

            if length >= MIN_MATCH {
                // 一歩ずらしたほうが長く取れるなら、ここは 1 文字だけにする
                if length < NICE_MATCH && position + 1 < end {
                    let (next_length, _) = self.search(position + 1);

                    if next_length > length {
                        self.push_literal(self.buffer[position]);
                        position += 1;
                        self.divide(position);
                        continue;
                    }
                }

                self.push_match(length, distance);

                for step in 1..length {
                    self.insert(position + step);
                }

                position += length;

            } else {
                self.push_literal(self.buffer[position]);
                position += 1;
            }

            self.divide(position);
        }

        self.done = position;
    }

    /// 区画に入る量に達していたら、そこで区切って出す
    fn divide(&mut self, position: usize) {
        if position - self.start >= BLOCK {
            self.done = position;
            self.emit(false);
        }
    }

    /// ためた記号を 1 区画として書き出す
    fn emit(&mut self, last: bool) {
        self.literal_count[256] += 1;
        let literal_length = code_length(&self.literal_count, 15);
        let distance_length = code_length(&self.distance_count, 15);

        let literal_used = used(&literal_length).max(257);
        let distance_used = used(&distance_length).max(1);
        let repeat = pack(&literal_length[..literal_used], &distance_length[..distance_used]);

        let mut order_count = [0u32; ORDER_COUNT];

        for one in &repeat {
            order_count[one.symbol as usize] += 1;
        }

        let order_length = code_length(&order_count, 7);
        let mut order_used = ORDER_COUNT;

        while order_used > 4 && order_length[ORDER[order_used - 1]] == 0 {
            order_used -= 1;
        }

        let extra = self.extra_bits();
        let dynamic = 3
            + 14
            + 3 * order_used as u64
            + repeat.iter().map(|one| order_length[one.symbol as usize] as u64 + one.bits as u64).sum::<u64>()
            + cost(&self.literal_count, &literal_length)
            + cost(&self.distance_count, &distance_length)
            + extra;

        let (fixed_literal, fixed_distance) = fixed_length();
        let fixed = 3
            + cost(&self.literal_count, &fixed_literal)
            + cost(&self.distance_count, &fixed_distance)
            + extra;

        let raw = (self.done - self.start) as u64;
        let stored = 3 + (8 - (self.bits as u64 + 3) % 8) % 8 + 32 + raw * 8;

        if stored <= dynamic && stored <= fixed && raw <= BLOCK as u64 {
            self.emit_stored(last);

        } else if fixed <= dynamic {
            let literal = canonical(&fixed_literal);
            let distance = canonical(&fixed_distance);
            self.put(last as u32, 1);
            self.put(1, 2);
            self.emit_item(&literal, &fixed_literal, &distance, &fixed_distance);

        } else {
            self.put(last as u32, 1);
            self.put(2, 2);
            self.put(literal_used as u32 - 257, 5);
            self.put(distance_used as u32 - 1, 5);
            self.put(order_used as u32 - 4, 4);

            for index in 0..order_used {
                self.put(order_length[ORDER[index]] as u32, 3);
            }

            let order = canonical(&order_length);

            for one in &repeat {
                self.put(order[one.symbol as usize] as u32, order_length[one.symbol as usize] as u32);

                if one.bits > 0 {
                    self.put(one.extra, one.bits);
                }
            }

            let literal = canonical(&literal_length);
            let distance = canonical(&distance_length);
            self.emit_item(&literal, &literal_length, &distance, &distance_length);
        }

        self.item.clear();
        self.literal_count = [0; LITERAL_COUNT];
        self.distance_count = [0; DISTANCE_COUNT];
        self.start = self.done;
    }

    /// 追加ビットの合計
    fn extra_bits(&self) -> u64 {
        let mut total = 0;

        for index in 0..LENGTH_EXTRA.len() {
            total += self.literal_count[257 + index] as u64 * LENGTH_EXTRA[index] as u64;
        }

        for index in 0..DISTANCE_EXTRA.len() {
            total += self.distance_count[index] as u64 * DISTANCE_EXTRA[index] as u64;
        }

        total
    }

    /// 縮めずにそのまま出す
    fn emit_stored(&mut self, last: bool) {
        self.put(last as u32, 1);
        self.put(0, 2);
        self.align();

        let length = (self.done - self.start) as u16;
        self.output.extend_from_slice(&length.to_le_bytes());
        self.output.extend_from_slice(&(!length).to_le_bytes());
        let piece = self.buffer[self.start..self.done].to_vec();
        self.output.extend_from_slice(&piece);
    }

    /// ためた記号を符号にして出す
    fn emit_item(
        &mut self,
        literal: &[u16],
        literal_length: &[u8],
        distance: &[u16],
        distance_length: &[u8],
    ) {
        let item = std::mem::take(&mut self.item);

        for one in &item {
            if one.distance == 0 {
                let symbol = one.value as usize;
                self.put(literal[symbol] as u32, literal_length[symbol] as u32);
                continue;
            }

            let length = one.value as usize;
            let code = length_of(length);
            self.put(literal[257 + code] as u32, literal_length[257 + code] as u32);

            if LENGTH_EXTRA[code] > 0 {
                self.put((length - LENGTH_BASE[code] as usize) as u32, LENGTH_EXTRA[code]);
            }

            let reach = one.distance as usize;
            let place = distance_of(reach);
            self.put(distance[place] as u32, distance_length[place] as u32);

            if DISTANCE_EXTRA[place] > 0 {
                self.put((reach - DISTANCE_BASE[place] as usize) as u32, DISTANCE_EXTRA[place]);
            }
        }

        self.put(literal[256] as u32, literal_length[256] as u32);
        self.item = item;
    }

    /// ビットを下位から詰める
    fn put(&mut self, value: u32, bits: u32) {
        if bits == 0 {
            return;
        }

        self.hold |= (value as u64) << self.bits;
        self.bits += bits;

        while self.bits >= 8 {
            self.output.push(self.hold as u8);
            self.hold >>= 8;
            self.bits -= 8;
        }
    }

    /// バイトの境目まで 0 を詰める
    fn align(&mut self) {
        if self.bits > 0 {
            self.output.push(self.hold as u8);
            self.hold = 0;
            self.bits = 0;
        }
    }
}


impl Default for Deflate {
    fn default() -> Deflate {
        Deflate::new()
    }
}


/// 一度に全部渡すとき
pub fn deflate(data: &[u8]) -> Vec<u8> {
    let mut state = Deflate::new();
    state.write(data);
    state.finish();
    state.take()
}


/// 3 バイトからハッシュを作る
fn hash(buffer: &[u8], position: usize) -> usize {
    let first = buffer[position] as usize;
    let second = buffer[position + 1] as usize;
    let third = buffer[position + 2] as usize;
    ((first << 10) ^ (second << 5) ^ third) & (HASH_SIZE - 1)
}


/// 符号長が 0 でない記号のうち、いちばん後ろのものの次
fn used(length: &[u8]) -> usize {
    let mut count = length.len();

    while count > 0 && length[count - 1] == 0 {
        count -= 1;
    }

    count
}


/// 符号長どおりに詰めたときのビット数
fn cost(count: &[u32], length: &[u8]) -> u64 {
    let mut total = 0;

    for index in 0..count.len() {
        total += count[index] as u64 * length[index] as u64;
    }

    total
}


/// 決め打ちの符号長
///
/// 記号数は文字と長さが 288、距離が 32 である。286 と 287、距離の 30 と 31 は実際には出てこないが、
/// 符号としては埋まっている。数を削ると他の記号に割り当てる符号まで変わってしまうので、
/// 出てこないぶんもそのまま置く。
fn fixed_length() -> ([u8; 288], [u8; 32]) {
    let mut literal = [0u8; 288];

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

    (literal, [5u8; 32])
}


/// 木を組むときの節
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Node {
    weight: u64,
    index: usize,
}


impl Ord for Node {
    fn cmp(&self, other: &Node) -> std::cmp::Ordering {
        // BinaryHeap は大きいほうから出すので、小さいほうが大きいことにする
        other.weight.cmp(&self.weight).then(other.index.cmp(&self.index))
    }
}


impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Node) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}


/// 出現数から符号長を決める。limit ビットを超えないようにする
///
/// まずふつうにハフマンの木を組み、深さを数える。limit を超えた葉は limit の段へ寄せ、
/// そのぶん埋まりすぎるので、浅いところの葉を 1 つずつ深くして帳尻を合わせる。
/// 最後に、出現数の多い記号ほど短い符号長になるよう割り当て直す。
fn code_length(count: &[u32], limit: usize) -> Vec<u8> {
    let mut order: Vec<usize> = (0..count.len()).filter(|index| count[*index] > 0).collect();
    let mut weight: Vec<u64> = count.iter().map(|value| *value as u64).collect();

    // 記号が 1 つ以下だと 1 ビットも送らない符号になる。読む側の作りを選ぶので、必ず 2 つ以上にする
    let mut spare = 0;

    while order.len() < 2 {
        while weight[spare] > 0 {
            spare += 1;
        }

        weight[spare] = 1;
        order.push(spare);
        order.sort_unstable();
    }

    let leaf = order.len();
    let mut left = vec![usize::MAX; leaf * 2];
    let mut right = vec![usize::MAX; leaf * 2];
    let mut heap = BinaryHeap::with_capacity(leaf);

    for (place, symbol) in order.iter().enumerate() {
        heap.push(Node {weight: weight[*symbol], index: place});
    }

    let mut next = leaf;

    while heap.len() > 1 {
        let first = heap.pop().unwrap();
        let second = heap.pop().unwrap();
        left[next] = first.index;
        right[next] = second.index;
        heap.push(Node {weight: first.weight + second.weight, index: next});
        next += 1;
    }

    let root = heap.pop().unwrap().index;
    let mut depth = vec![0usize; next.max(leaf + 1)];
    let mut stack = vec![(root, 0usize)];
    let mut deepest = 0;

    while let Some((node, level)) = stack.pop() {
        if node < leaf {
            depth[node] = level;
            deepest = deepest.max(level);
            continue;
        }

        stack.push((left[node], level + 1));
        stack.push((right[node], level + 1));
    }

    let mut level_count = vec![0u32; deepest.max(limit) + 2];
    let mut overflow = 0;

    for place in 0..leaf {
        let level = depth[place].min(limit);

        if depth[place] > limit {
            overflow += 1;
        }

        level_count[level] += 1;
    }

    while overflow > 0 {
        let mut level = limit - 1;

        while level_count[level] == 0 {
            level -= 1;
        }

        level_count[level] -= 1;
        level_count[level + 1] += 2;
        level_count[limit] -= 1;
        overflow -= 2;
    }

    // 出現数の多い記号から順に、浅い符号長を渡す
    order.sort_by(|first, second| {
        weight[*second].cmp(&weight[*first]).then(first.cmp(second))
    });

    let mut result = vec![0u8; count.len()];
    let mut place = 0;

    for level in 1..=limit {
        for _ in 0..level_count[level] {
            result[order[place]] = level as u8;
            place += 1;
        }
    }

    result
}


/// 符号長から、流れに詰める向きに並べ替えた符号を作る
fn canonical(length: &[u8]) -> Vec<u16> {
    let mut count = [0u32; 16];

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

    count[0] = 0;
    let mut next = [0u32; 16];
    let mut code = 0;

    for bits in 1..16 {
        code = (code + count[bits - 1]) << 1;
        next[bits] = code;
    }

    let mut result = vec![0u16; length.len()];

    for (symbol, bits) in length.iter().enumerate() {
        if *bits == 0 {
            continue;
        }

        let assigned = next[*bits as usize];
        next[*bits as usize] += 1;
        result[symbol] = reverse(assigned, *bits as u32) as u16;
    }

    result
}


/// 下位 bits ビットを逆に並べる
fn reverse(value: u32, bits: u32) -> u32 {
    let mut result = 0;

    for index in 0..bits {
        result |= ((value >> index) & 1) << (bits - 1 - index);
    }

    result
}


/// 符号長の並びを送るための 1 つ
struct Repeat {
    /// 0..15 は符号長そのもの、16 は直前の写し、17 と 18 は 0 の並び
    symbol: u8,
    /// 追加ビットの値
    extra: u32,
    /// 追加ビット数
    bits: u32,
}


/// 符号長の並びを、繰り返しをまとめた形に直す
fn pack(literal: &[u8], distance: &[u8]) -> Vec<Repeat> {
    let mut all = Vec::with_capacity(literal.len() + distance.len());
    all.extend_from_slice(literal);
    all.extend_from_slice(distance);

    let mut result = Vec::new();
    let mut index = 0;

    while index < all.len() {
        let value = all[index];
        let mut run = 1;

        while index + run < all.len() && all[index + run] == value {
            run += 1;
        }

        index += run;

        if value == 0 {
            while run >= 11 {
                let take = run.min(138);
                result.push(Repeat {symbol: 18, extra: take as u32 - 11, bits: 7});
                run -= take;
            }

            while run >= 3 {
                let take = run.min(10);
                result.push(Repeat {symbol: 17, extra: take as u32 - 3, bits: 3});
                run -= take;
            }

            for _ in 0..run {
                result.push(Repeat {symbol: 0, extra: 0, bits: 0});
            }

            continue;
        }

        // 16 は直前の符号長を写すので、まず 1 つそのまま置く
        result.push(Repeat {symbol: value, extra: 0, bits: 0});
        run -= 1;

        while run >= 3 {
            let take = run.min(6);
            result.push(Repeat {symbol: 16, extra: take as u32 - 3, bits: 2});
            run -= take;
        }

        for _ in 0..run {
            result.push(Repeat {symbol: value, extra: 0, bits: 0});
        }
    }

    result
}