lernie 0.1.63

lernie: the operator seat — the window and wire client for a yog server
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

//! **The payload as a bit stream**: the segment header, the padding that fills
//! the symbol, the split into blocks, and the interleave that is the order the
//! modules are actually written in.
//!
//! # Why the bits are a `Vec<bool>` and not packed
//!
//! Everything upstream of placement is byte-aligned — a byte-mode segment's
//! header is 12 or 20 bits, both multiples of four, and every codeword is
//! eight. So the packing would buy nothing but the unpacking, and placement
//! wants one bit at a time in a zigzag that is nothing like byte order.
//!
//! # The stream is short and that is not an error
//!
//! Some versions have three, four or seven modules left over after the last
//! codeword — the symbol's area is not a whole number of codewords. Every
//! implementation that carries a table of those *remainder bits* is carrying a
//! table of zeroes: the modules are written light, which is what reading past
//! the end of this stream already gives you. Placement asks for bit `n` and
//! takes `false` when there is none, and the table dissolves.

use super::gf;
use super::version::{BYTE_MODE, Plan};

/// The two padding codewords the standard names, alternating, that fill a
/// symbol the payload does not.
const PAD_FIRST: u8 = 0b1110_1100;
const PAD_SECOND: u8 = 0b0001_0001;

/// **The final codeword order**: every block's data interleaved, then every
/// block's check bytes interleaved, as one stream of bits.
pub(super) fn stream(payload: &[u8], plan: Plan) -> Vec<bool> {
    let blocks = split(&codewords(payload, plan), plan);
    let checks: Vec<Vec<u8>> = blocks.iter().map(|b| gf::check(b, plan.check)).collect();
    interleave(&blocks)
        .into_iter()
        .chain(interleave(&checks))
        .flat_map(|byte| (0..8).rev().map(move |at| byte >> at & 1 == 1))
        .collect()
}

/// **The data codewords**: the header, the payload, a terminator, and padding
/// to the version's full data capacity.
///
/// The terminator is four zero bits and it is **truncated rather than
/// dropped** when the symbol has fewer than four left — a decoder reading a
/// full symbol stops at the capacity it already knows, so the terminator is
/// what tells it to stop *early*, and where there is no early to stop at there
/// is nothing to say.
fn codewords(payload: &[u8], plan: Plan) -> Vec<u8> {
    let mut bits = Bits::new();
    bits.push(BYTE_MODE, 4);
    bits.push(
        u32::try_from(payload.len()).unwrap_or(u32::MAX),
        plan.count_bits(),
    );
    for &byte in payload {
        bits.push(u32::from(byte), 8);
    }
    let room = plan.data * 8;
    bits.push(0, 4.min(room.saturating_sub(bits.len)));
    bits.pad_to_byte();
    let mut out = bits.bytes;
    out.truncate(plan.data);
    let mut pad = [PAD_FIRST, PAD_SECOND].into_iter().cycle();
    while out.len() < plan.data {
        out.push(pad.next().unwrap_or(PAD_FIRST));
    }
    out
}

/// The data codewords cut into the version's blocks, shortest first.
fn split(data: &[u8], plan: Plan) -> Vec<Vec<u8>> {
    let mut rest = data;
    plan.block_lengths()
        .into_iter()
        .map(|len| {
            let (block, tail) = rest.split_at(len.min(rest.len()));
            rest = tail;
            block.to_vec()
        })
        .collect()
}

/// **Column-wise across the blocks**: the first byte of every block, then the
/// second of every block, and so on — a block that has run out contributing
/// nothing, which is what makes the short and long blocks interleave correctly
/// with no case for either.
fn interleave(blocks: &[Vec<u8>]) -> Vec<u8> {
    let longest = blocks.iter().map(Vec::len).max().unwrap_or(0);
    (0..longest)
        .flat_map(|at| {
            blocks
                .iter()
                .filter_map(move |block| block.get(at).copied())
        })
        .collect()
}

/// A bit stream being written most-significant bit first, packed as it goes.
struct Bits {
    bytes: Vec<u8>,
    len: usize,
}

impl Bits {
    fn new() -> Self {
        Self {
            bytes: Vec::new(),
            len: 0,
        }
    }

    /// Append the low `width` bits of `value`, highest first.
    fn push(&mut self, value: u32, width: usize) {
        for at in (0..width).rev() {
            if self.len.is_multiple_of(8) {
                self.bytes.push(0);
            }
            let set = u8::from(value >> at & 1 == 1) << (7 - self.len % 8);
            if let Some(byte) = self.bytes.last_mut() {
                *byte |= set;
            }
            self.len += 1;
        }
    }

    /// Round the stream up to a whole codeword with light modules.
    fn pad_to_byte(&mut self) {
        self.push(0, (8 - self.len % 8) % 8);
    }
}