pinch-points 0.1.0

A fast, kid-friendly crab-routing game: route streams of crabs into your sandcastle before the tide comes in
Documentation 
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306

//! Share codes: a beach, a level, or a whole round as one line of text.
//!
//! A code is `PP<kind><body>`, where the body is the payload compressed
//! ([`crate::lzw`]) and written in an alphabet chosen to survive being read
//! aloud, retyped, and passed through a chat window that likes to capitalise
//! things. The last character is a checksum, so a code with a typo in it is
//! refused rather than half-loaded.
//!
//! The alphabet is Crockford's base32: ten digits and twenty-two letters,
//! with `I`, `L`, `O` and `U` left out: the first three because they are
//! the ones people confuse with `1` and `0`, and the last because leaving
//! it out means no code ever spells anything unfortunate. Decoding maps the
//! confusable characters back, so a code someone typed as `IL0` still reads.

use crate::lzw;

const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";

/// What a code carries. One letter each, in the code's third character, so a
/// code says what it is before anything tries to load it. Pasting a level
/// where a round was wanted should say so, not fail obscurely.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Kind {
    /// A beach mid-play: the board exactly as it stands, and the table
    /// it is being played at. Pasting one puts you where its sender was.
    Beach,
    /// A level, as the level format's own text.
    Level,
    /// A recorded round, as the replay format's own text.
    Round,
}

impl Kind {
    fn letter(self) -> char {
        match self {
            Kind::Beach => 'B',
            Kind::Level => 'L',
            Kind::Round => 'R',
        }
    }

    fn from_letter(letter: char) -> Option<Kind> {
        match letter {
            'B' => Some(Kind::Beach),
            'L' => Some(Kind::Level),
            'R' => Some(Kind::Round),
            _ => None,
        }
    }
}

/// Group size for readability. A code arrives as one run of characters and
/// is shown in fives, which is how people read a licence key.
const GROUP: usize = 5;

/// Write a payload as a share code, hyphenated into readable groups.
pub fn encode(kind: Kind, payload: &[u8]) -> String {
    let packed = lzw::compress(payload, 8);
    let mut body = base32_encode(&packed);
    body.push(ALPHABET[usize::from(checksum(&body))] as char);
    let mut out = format!("PP{}", kind.letter());
    for (i, ch) in body.chars().enumerate() {
        if i > 0 && i.is_multiple_of(GROUP) {
            out.push('-');
        }
        out.push(ch);
    }
    out
}

/// Read a share code back, or `None` if it is not one: wrong prefix, a
/// character that is not in the alphabet, or a checksum that does not match
/// what was typed.
///
/// Deliberately forgiving about everything that does not change the
/// meaning (case, spaces, hyphens, and the four letters the alphabet leaves
/// out) because a code is something a person retypes from another screen.
pub fn decode(code: &str) -> Option<(Kind, Vec<u8>)> {
    let mut chars = code.chars().filter(|ch| !matches!(ch, '-' | ' ' | '\t'));
    let (p, q) = (chars.next()?, chars.next()?);
    if !p.eq_ignore_ascii_case(&'P') || !q.eq_ignore_ascii_case(&'P') {
        return None;
    }
    let kind = Kind::from_letter(chars.next()?.to_ascii_uppercase())?;
    let body: String = chars.map(tidy).collect();
    let (digits, check) = body.split_at_checked(body.len().checked_sub(1)?)?;
    if check.chars().next()? != ALPHABET[usize::from(checksum(digits))] as char {
        return None;
    }
    let packed = base32_decode(digits)?;
    let payload = lzw::decompress(&packed, 8)?;
    Some((kind, payload))
}

/// The characters people substitute, mapped back to what they meant.
fn tidy(ch: char) -> char {
    match ch.to_ascii_uppercase() {
        'I' | 'L' => '1',
        'O' => '0',
        'U' => 'V',
        other => other,
    }
}

/// A checksum over the body. Not a hash: it is here to catch a mistyped
/// character, a swapped pair, or a dropped group, and one character of code
/// is the right price for that.
///
/// Two details carry the guarantee that *every* single wrong character is
/// caught. The sum is over each character's **alphabet index**, not its byte:
/// the byte values are not contiguous, and `'0'` and `'P'` happen to sit 32
/// apart, so a swap between them would vanish under the modulus. And the
/// weights are **odd**, which makes them invertible modulo 32, so one wrong
/// character always moves the sum, where an even weight can be cancelled
/// by a difference that shares its factors of two.
///
/// The cost of that choice, and it is the right way round: adjacent
/// transpositions move the sum by twice the difference of the two indices,
/// so the one pair this misses is two characters exactly 16 apart in the
/// alphabet. Both guarantees at once are beyond a single base-32 check
/// character by a weighted sum: full substitution cover needs odd weights,
/// and the difference of two odd weights is always even. Mistyping one
/// character is the common error; transposing a pair that happens to be 16
/// apart is not.
fn checksum(body: &str) -> u8 {
    let mut sum = 0u32;
    for (i, ch) in body.chars().enumerate() {
        let value = index_of(ch).map_or(0, u32::from);
        let weight = 2 * (i as u32 % 16) + 1;
        sum = sum.wrapping_add(value.wrapping_mul(weight));
    }
    (sum % 32) as u8
}

/// Where `ch` sits in the alphabet, if it is in it at all.
fn index_of(ch: char) -> Option<u8> {
    ALPHABET
        .iter()
        .position(|&a| a == ch as u8)
        .map(|index| index as u8)
}

fn base32_encode(bytes: &[u8]) -> String {
    let mut out = String::new();
    let (mut acc, mut bits) = (0u32, 0u8);
    for &byte in bytes {
        acc = (acc << 8) | u32::from(byte);
        bits += 8;
        while bits >= 5 {
            bits -= 5;
            out.push(ALPHABET[((acc >> bits) & 0x1F) as usize] as char);
        }
    }
    if bits > 0 {
        out.push(ALPHABET[((acc << (5 - bits)) & 0x1F) as usize] as char);
    }
    out
}

fn base32_decode(text: &str) -> Option<Vec<u8>> {
    let mut out = Vec::new();
    let (mut acc, mut bits) = (0u32, 0u8);
    for ch in text.chars() {
        acc = (acc << 5) | u32::from(index_of(ch)?);
        bits += 5;
        if bits >= 8 {
            bits -= 8;
            out.push(((acc >> bits) & 0xFF) as u8);
        }
    }
    // The tail bits are the encoder's padding, not data.
    Some(out)
}

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

    #[test]
    fn codes_round_trip_at_every_size() {
        for payload in [
            vec![],
            vec![0u8],
            b"wrap: on\n".to_vec(),
            (0..500u32).map(|i| (i % 251) as u8).collect(),
        ] {
            for kind in [Kind::Beach, Kind::Level, Kind::Round] {
                let code = encode(kind, &payload);
                assert_eq!(decode(&code), Some((kind, payload.clone())), "{code}");
            }
        }
    }

    /// A code is something a person reads off one screen and types into
    /// another, so everything that survives that has to survive this.
    #[test]
    fn a_retyped_code_still_reads() {
        let code = encode(Kind::Level, b"a small beach");
        let expected = decode(&code).expect("the code as written");
        for variant in [
            code.to_lowercase(),
            code.replace('-', ""),
            code.replace('-', " "),
            format!("  {code}  ").replace(' ', ""),
        ] {
            assert_eq!(decode(&variant), Some(expected.clone()), "{variant}");
        }
        // And the letters the alphabet leaves out map back to what they
        // looked like, so a code read aloud survives the trip.
        let muddled: String = code
            .chars()
            .map(|ch| match ch {
                '1' => 'I',
                '0' => 'O',
                other => other,
            })
            .collect();
        assert_eq!(decode(&muddled), Some(expected), "{muddled}");
    }

    /// The checksum earns its character: a typo is refused, not half-loaded.
    ///
    /// Every position of the code is mistyped as every other letter of the
    /// alphabet: the body, and the checksum character itself. Testing only
    /// the last character would have missed that the old checksum let a
    /// wrong body character through whenever the two bytes sat 32 apart.
    #[test]
    fn a_typo_is_refused() {
        for payload in [b"seed 12345".as_slice(), b"a", b"wrap: on\n"] {
            let code = encode(Kind::Beach, payload);
            assert!(decode(&code).is_some(), "the code itself is good");
            let chars: Vec<char> = code.chars().collect();
            for (at, &original) in chars.iter().enumerate() {
                // The `PP<kind>` prefix is not covered by the checksum; it
                // is checked outright by `decode`.
                if at < 3 || original == '-' {
                    continue;
                }
                for replacement in ALPHABET.iter().map(|&b| b as char) {
                    if replacement == original {
                        continue;
                    }
                    let mut typo = chars.clone();
                    typo[at] = replacement;
                    let typo: String = typo.into_iter().collect();
                    assert_eq!(decode(&typo), None, "{original}->{replacement} in {code}");
                }
            }
        }
    }

    /// A swapped pair, which a plain unweighted sum would wave through:
    /// every adjacent pair except the documented blind spot, two characters
    /// exactly 16 apart in the alphabet.
    #[test]
    fn a_swapped_pair_is_refused() {
        let code = encode(Kind::Beach, b"seed 12345");
        let body: Vec<char> = code.chars().filter(|c| *c != '-').collect();
        let mut swaps = 0;
        for at in 3..body.len() - 1 {
            let (a, b) = (body[at], body[at + 1]);
            let apart = index_of(a).unwrap().abs_diff(index_of(b).unwrap());
            if a == b || apart == 16 {
                continue;
            }
            let mut swapped = body.clone();
            swapped.swap(at, at + 1);
            let swapped: String = swapped.into_iter().collect();
            assert_eq!(decode(&swapped), None, "swap at {at} of {code}");
            swaps += 1;
        }
        assert!(swaps > 0, "the sample code had no adjacent pair to swap");
    }

    #[test]
    fn what_is_not_a_code_is_refused() {
        for junk in [
            "",
            "PP",
            "PPX-12345",
            "hello",
            "PPB", // no body at all
            "12345-67890",
        ] {
            assert_eq!(decode(junk), None, "{junk}");
        }
    }

    /// The point of compressing: a round is thirty kilobytes of mostly the
    /// same few characters, and a code nobody can carry is not a share code.
    #[test]
    fn a_repetitive_payload_shrinks() {
        let round = "000000 000000 000000 000000\n".repeat(400);
        let code = encode(Kind::Round, round.as_bytes());
        assert!(
            code.len() < round.len() / 8,
            "{} characters for {} bytes",
            code.len(),
            round.len()
        );
        assert_eq!(
            decode(&code).map(|(_, bytes)| bytes),
            Some(round.into_bytes())
        );
    }
}