pinch_points/share.rs
1//! Share codes: a beach, a level, or a whole round as one line of text.
2//!
3//! A code is `PP<kind><body>`, where the body is the payload compressed
4//! ([`crate::lzw`]) and written in an alphabet chosen to survive being read
5//! aloud, retyped, and passed through a chat window that likes to capitalise
6//! things. The last character is a checksum, so a code with a typo in it is
7//! refused rather than half-loaded.
8//!
9//! The alphabet is Crockford's base32: ten digits and twenty-two letters,
10//! with `I`, `L`, `O` and `U` left out: the first three because they are
11//! the ones people confuse with `1` and `0`, and the last because leaving
12//! it out means no code ever spells anything unfortunate. Decoding maps the
13//! confusable characters back, so a code someone typed as `IL0` still reads.
14
15use crate::lzw;
16
17const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
18
19/// What a code carries. One letter each, in the code's third character, so a
20/// code says what it is before anything tries to load it. Pasting a level
21/// where a round was wanted should say so, not fail obscurely.
22#[derive(Clone, Copy, PartialEq, Eq, Debug)]
23pub enum Kind {
24 /// A beach mid-play: the board exactly as it stands, and the table
25 /// it is being played at. Pasting one puts you where its sender was.
26 Beach,
27 /// A level, as the level format's own text.
28 Level,
29 /// A recorded round, as the replay format's own text.
30 Round,
31}
32
33impl Kind {
34 fn letter(self) -> char {
35 match self {
36 Kind::Beach => 'B',
37 Kind::Level => 'L',
38 Kind::Round => 'R',
39 }
40 }
41
42 fn from_letter(letter: char) -> Option<Kind> {
43 match letter {
44 'B' => Some(Kind::Beach),
45 'L' => Some(Kind::Level),
46 'R' => Some(Kind::Round),
47 _ => None,
48 }
49 }
50}
51
52/// Group size for readability. A code arrives as one run of characters and
53/// is shown in fives, which is how people read a licence key.
54const GROUP: usize = 5;
55
56/// Write a payload as a share code, hyphenated into readable groups.
57pub fn encode(kind: Kind, payload: &[u8]) -> String {
58 let packed = lzw::compress(payload, 8);
59 let mut body = base32_encode(&packed);
60 body.push(ALPHABET[usize::from(checksum(&body))] as char);
61 let mut out = format!("PP{}", kind.letter());
62 for (i, ch) in body.chars().enumerate() {
63 if i > 0 && i.is_multiple_of(GROUP) {
64 out.push('-');
65 }
66 out.push(ch);
67 }
68 out
69}
70
71/// Read a share code back, or `None` if it is not one: wrong prefix, a
72/// character that is not in the alphabet, or a checksum that does not match
73/// what was typed.
74///
75/// Deliberately forgiving about everything that does not change the
76/// meaning (case, spaces, hyphens, and the four letters the alphabet leaves
77/// out) because a code is something a person retypes from another screen.
78pub fn decode(code: &str) -> Option<(Kind, Vec<u8>)> {
79 let mut chars = code.chars().filter(|ch| !matches!(ch, '-' | ' ' | '\t'));
80 let (p, q) = (chars.next()?, chars.next()?);
81 if !p.eq_ignore_ascii_case(&'P') || !q.eq_ignore_ascii_case(&'P') {
82 return None;
83 }
84 let kind = Kind::from_letter(chars.next()?.to_ascii_uppercase())?;
85 let body: String = chars.map(tidy).collect();
86 let (digits, check) = body.split_at_checked(body.len().checked_sub(1)?)?;
87 if check.chars().next()? != ALPHABET[usize::from(checksum(digits))] as char {
88 return None;
89 }
90 let packed = base32_decode(digits)?;
91 let payload = lzw::decompress(&packed, 8)?;
92 Some((kind, payload))
93}
94
95/// The characters people substitute, mapped back to what they meant.
96fn tidy(ch: char) -> char {
97 match ch.to_ascii_uppercase() {
98 'I' | 'L' => '1',
99 'O' => '0',
100 'U' => 'V',
101 other => other,
102 }
103}
104
105/// A checksum over the body. Not a hash: it is here to catch a mistyped
106/// character, a swapped pair, or a dropped group, and one character of code
107/// is the right price for that.
108///
109/// Two details carry the guarantee that *every* single wrong character is
110/// caught. The sum is over each character's **alphabet index**, not its byte:
111/// the byte values are not contiguous, and `'0'` and `'P'` happen to sit 32
112/// apart, so a swap between them would vanish under the modulus. And the
113/// weights are **odd**, which makes them invertible modulo 32, so one wrong
114/// character always moves the sum, where an even weight can be cancelled
115/// by a difference that shares its factors of two.
116///
117/// The cost of that choice, and it is the right way round: adjacent
118/// transpositions move the sum by twice the difference of the two indices,
119/// so the one pair this misses is two characters exactly 16 apart in the
120/// alphabet. Both guarantees at once are beyond a single base-32 check
121/// character by a weighted sum: full substitution cover needs odd weights,
122/// and the difference of two odd weights is always even. Mistyping one
123/// character is the common error; transposing a pair that happens to be 16
124/// apart is not.
125fn checksum(body: &str) -> u8 {
126 let mut sum = 0u32;
127 for (i, ch) in body.chars().enumerate() {
128 let value = index_of(ch).map_or(0, u32::from);
129 let weight = 2 * (i as u32 % 16) + 1;
130 sum = sum.wrapping_add(value.wrapping_mul(weight));
131 }
132 (sum % 32) as u8
133}
134
135/// Where `ch` sits in the alphabet, if it is in it at all.
136fn index_of(ch: char) -> Option<u8> {
137 ALPHABET
138 .iter()
139 .position(|&a| a == ch as u8)
140 .map(|index| index as u8)
141}
142
143fn base32_encode(bytes: &[u8]) -> String {
144 let mut out = String::new();
145 let (mut acc, mut bits) = (0u32, 0u8);
146 for &byte in bytes {
147 acc = (acc << 8) | u32::from(byte);
148 bits += 8;
149 while bits >= 5 {
150 bits -= 5;
151 out.push(ALPHABET[((acc >> bits) & 0x1F) as usize] as char);
152 }
153 }
154 if bits > 0 {
155 out.push(ALPHABET[((acc << (5 - bits)) & 0x1F) as usize] as char);
156 }
157 out
158}
159
160fn base32_decode(text: &str) -> Option<Vec<u8>> {
161 let mut out = Vec::new();
162 let (mut acc, mut bits) = (0u32, 0u8);
163 for ch in text.chars() {
164 acc = (acc << 5) | u32::from(index_of(ch)?);
165 bits += 5;
166 if bits >= 8 {
167 bits -= 8;
168 out.push(((acc >> bits) & 0xFF) as u8);
169 }
170 }
171 // The tail bits are the encoder's padding, not data.
172 Some(out)
173}
174
175#[cfg(test)]
176mod tests {
177 use super::*;
178
179 #[test]
180 fn codes_round_trip_at_every_size() {
181 for payload in [
182 vec![],
183 vec![0u8],
184 b"wrap: on\n".to_vec(),
185 (0..500u32).map(|i| (i % 251) as u8).collect(),
186 ] {
187 for kind in [Kind::Beach, Kind::Level, Kind::Round] {
188 let code = encode(kind, &payload);
189 assert_eq!(decode(&code), Some((kind, payload.clone())), "{code}");
190 }
191 }
192 }
193
194 /// A code is something a person reads off one screen and types into
195 /// another, so everything that survives that has to survive this.
196 #[test]
197 fn a_retyped_code_still_reads() {
198 let code = encode(Kind::Level, b"a small beach");
199 let expected = decode(&code).expect("the code as written");
200 for variant in [
201 code.to_lowercase(),
202 code.replace('-', ""),
203 code.replace('-', " "),
204 format!(" {code} ").replace(' ', ""),
205 ] {
206 assert_eq!(decode(&variant), Some(expected.clone()), "{variant}");
207 }
208 // And the letters the alphabet leaves out map back to what they
209 // looked like, so a code read aloud survives the trip.
210 let muddled: String = code
211 .chars()
212 .map(|ch| match ch {
213 '1' => 'I',
214 '0' => 'O',
215 other => other,
216 })
217 .collect();
218 assert_eq!(decode(&muddled), Some(expected), "{muddled}");
219 }
220
221 /// The checksum earns its character: a typo is refused, not half-loaded.
222 ///
223 /// Every position of the code is mistyped as every other letter of the
224 /// alphabet: the body, and the checksum character itself. Testing only
225 /// the last character would have missed that the old checksum let a
226 /// wrong body character through whenever the two bytes sat 32 apart.
227 #[test]
228 fn a_typo_is_refused() {
229 for payload in [b"seed 12345".as_slice(), b"a", b"wrap: on\n"] {
230 let code = encode(Kind::Beach, payload);
231 assert!(decode(&code).is_some(), "the code itself is good");
232 let chars: Vec<char> = code.chars().collect();
233 for (at, &original) in chars.iter().enumerate() {
234 // The `PP<kind>` prefix is not covered by the checksum; it
235 // is checked outright by `decode`.
236 if at < 3 || original == '-' {
237 continue;
238 }
239 for replacement in ALPHABET.iter().map(|&b| b as char) {
240 if replacement == original {
241 continue;
242 }
243 let mut typo = chars.clone();
244 typo[at] = replacement;
245 let typo: String = typo.into_iter().collect();
246 assert_eq!(decode(&typo), None, "{original}->{replacement} in {code}");
247 }
248 }
249 }
250 }
251
252 /// A swapped pair, which a plain unweighted sum would wave through:
253 /// every adjacent pair except the documented blind spot, two characters
254 /// exactly 16 apart in the alphabet.
255 #[test]
256 fn a_swapped_pair_is_refused() {
257 let code = encode(Kind::Beach, b"seed 12345");
258 let body: Vec<char> = code.chars().filter(|c| *c != '-').collect();
259 let mut swaps = 0;
260 for at in 3..body.len() - 1 {
261 let (a, b) = (body[at], body[at + 1]);
262 let apart = index_of(a).unwrap().abs_diff(index_of(b).unwrap());
263 if a == b || apart == 16 {
264 continue;
265 }
266 let mut swapped = body.clone();
267 swapped.swap(at, at + 1);
268 let swapped: String = swapped.into_iter().collect();
269 assert_eq!(decode(&swapped), None, "swap at {at} of {code}");
270 swaps += 1;
271 }
272 assert!(swaps > 0, "the sample code had no adjacent pair to swap");
273 }
274
275 #[test]
276 fn what_is_not_a_code_is_refused() {
277 for junk in [
278 "",
279 "PP",
280 "PPX-12345",
281 "hello",
282 "PPB", // no body at all
283 "12345-67890",
284 ] {
285 assert_eq!(decode(junk), None, "{junk}");
286 }
287 }
288
289 /// The point of compressing: a round is thirty kilobytes of mostly the
290 /// same few characters, and a code nobody can carry is not a share code.
291 #[test]
292 fn a_repetitive_payload_shrinks() {
293 let round = "000000 000000 000000 000000\n".repeat(400);
294 let code = encode(Kind::Round, round.as_bytes());
295 assert!(
296 code.len() < round.len() / 8,
297 "{} characters for {} bytes",
298 code.len(),
299 round.len()
300 );
301 assert_eq!(
302 decode(&code).map(|(_, bytes)| bytes),
303 Some(round.into_bytes())
304 );
305 }
306}