Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/base2x.rs

18.5 KiB, 57 runs

created by r1870400018:1095, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! `Base2x` is a more flexible Unicode alternative to ASCII-only Base64, allowing an arbitrary
2//! user-supplied alphabet and padding characters, but only for binary tokens of fixed size. The
3//! alphabet must consist of 2^X Unicode characters for X up to 32. Each alphabet character is
4//! associated with a binary token of fixed length X.
5//!
6//! Encoding schemes exist (e.g. Base62) that allow an arbitrary alphabet length by using tokens of
7//! variable size. Base2x is limited to lengths of 2^x for simplicity and speed.
8//!
9//! Encoding a byte slice to a string automatically appends padding characters if necessary. In
10//! this case, the padding always consists of precisely three characters, namely the alphabet
11//! character associated with a zero-padded partial token, the user-specified padding separator
12//! (e.g. '=') and a padding character from the user-supplied padding set. The index of the
13//! padding character gives the number of padding bits, ranging from 1 to X-1.
14//!
15//! Note that this fixed size padding scheme potentially adds one character more than the Base64
16//! variable scheme using one or two '=' characters. A `normalise` method is provided to add this
17//! padding if it is not present. Decoding an arbitrary string that uses the correct alphabet
18//! without padding executes without error, but the last byte may not match a proper encoding of
19//! the original binary. It's best to always use padding, and to normalise if unsure.
20
21use oxedyne_fe2o3_core::prelude::*;
22
23use std::collections::HashSet;
24
25
26pub const MAX_X: usize = 32;
27// `u64` because `2^32` overflows a 32-bit `usize` (e.g. on `wasm32`); the value
28// is an alphabet-size ceiling, compared against a `usize` after a widening cast.
29pub const MAX_A: u64 = 2_u64.pow(MAX_X as u32);
30
31// Some const instances.
32pub const BASE64: Base2x<64, 6> = base64();
33pub const HEMATITE64: Base2x<64, 6> = hematite64();
34pub const HEMATITE32: Base2x<32, 5> = hematite32();
35pub const HEX: Base2x<16, 4> = hex();
36
37pub const BASE64_ALPHABET: [char; 64] = [
38 // "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
39 // This is not a replacement for standard Base64, because a different padding scheme is used.
40 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
41 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
42 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
43 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
44 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
45 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
46 'w', 'x', 'y', 'z', '0', '1', '2', '3',
47 '4', '5', '6', '7', '8', '9', '+', '/',
48];
49pub const fn base64() -> Base2x<64, 6> {
50 Base2x::<64, 6>{
51 alphabet: BASE64_ALPHABET,
52 padding: Some(('=', ['1', '2', '3', '4', '5', '_' ])),
53 }
54}
55
56pub const HEMATITE64_ALPHABET: [char; 64] = [
57 // Start with Base64:
58 // "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
59 // place numerals first and make the substitutions
60 // 'I' -> '#'
61 // 'O' -> '@',
62 // 'l' -> '%',
63 // 'o' -> '-',
64 // '/' -> '*',
65 // "0123456789ABCDEFGH#JKLMN@PQRSTUVWXYZabcdef%hijklmn-pqrstuvwxyz+/";
66 '0', '1', '2', '3', '4', '5', '6', '7',
67 '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
68 'G', 'H', '#', 'J', 'K', 'L', 'M', 'N',
69 '@', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
70 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd',
71 'e', 'f', 'g', 'h', 'i', 'j', 'k', '%',
72 'm', 'n', '-', 'p', 'q', 'r', 's', 't',
73 'u', 'v', 'w', 'x', 'y', 'z', '+', '*',
74];
75pub const fn hematite64() -> Base2x<64, 6> {
76 Base2x::<64, 6>{
77 alphabet: HEMATITE64_ALPHABET,
78 padding: Some(('=', ['1', '2', '3', '4', '5', '_' ])),
79 }
80}
81
82pub const HEX_ALPHABET: [char; 16] = [
83 '0', '1', '2', '3', '4', '5', '6', '7',
84 '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
85];
86pub const fn hex() -> Base2x<16, 4> {
87 Base2x::<16, 4>{
88 alphabet: HEX_ALPHABET,
89 padding: Some(('=', ['1', '2', '3', '_' ])),
90 }
91}
92
93pub const HEMATITE32_ALPHABET: [char; 32] = [
94 // Simply extend the use of alphabetical characters from 'A'..'F' to 'A'..'M', 'a'..'f' to
95 // 'a'..'m', excluding 'I', 'i', 'L' and 'l'.
96 '0', '1', '2', '3', '4', '5', '6', '7',
97 '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
98 'G', 'H', 'J', 'K', 'M', 'a', 'b', 'c',
99 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm',
100];
101pub const fn hematite32() -> Base2x<32, 5> {
102 Base2x::<32, 5>{
103 alphabet: HEMATITE32_ALPHABET,
104 padding: Some(('=', ['1', '2', '3', '4', '_' ])),
105 }
106}
107
108/// Douglas Crockford's base 32, for identifiers a person reads aloud and types back.
109///
110/// The digits come first, then the letters with `I`, `L`, `O` and `U` left out: the first three
111/// because they are misread as `1`, `1` and `0`, and `U` so that no accidental obscenity appears in
112/// a generated identifier. It is the alphabet to reach for when the output will be spoken over a
113/// telephone or copied off a screen by hand, which is a different job from [`HEMATITE32`], whose
114/// alphabet is mixed case and denser.
115pub const CROCKFORD32_ALPHABET: [char; 32] = [
116 '0', '1', '2', '3', '4', '5', '6', '7',
117 '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
118 'G', 'H', 'J', 'K', 'M', 'N', 'P', 'Q',
119 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z',
120];
121
122/// Crockford base 32. See [`CROCKFORD32_ALPHABET`].
123pub const CROCKFORD32: Base2x<32, 5> = crockford32();
124
125/// Builds the Crockford base 32 codec.
126pub const fn crockford32() -> Base2x<32, 5> {
127 Base2x::<32, 5>{
128 alphabet: CROCKFORD32_ALPHABET,
129 padding: Some(('=', ['1', '2', '3', '4', '_' ])),
130 }
131}
132
133pub const BINHEX4_ALPHABET: &'static str =
134 // Removes '7', 'O', 'g', 'n', 'o', "stuvwxyz"
135 "!\"#$%&'()*+,-012345689@ABCDEFGHIJKLMNPQRSTUVXYZ[`abcdefhijklmpqr";
136
137pub const fn alphabet_size(x: u32) -> usize {
138 2_usize.pow(x)
139}
140
141pub struct Base2x<
142 const A: usize, // Alphabet length, 2^X.
143 const X: usize, // Token (binary) length.
144> {
145 alphabet: [char; A],
146 padding: Option<(char, [char; X])>,
147}
148
149impl<
150 const A: usize,
151 const X: usize,
152>
153 Base2x<A, X>
154{
155
156 const TOKEN_MASK: u64 = Self::lower_bit_mask(X);
157
158 pub fn new(
159 alphabet: [char; A],
160 padding: Option<(char, [char; X])>,
161 )
162 -> Outcome<Self>
163 {
164 if X < 2 || X > MAX_X {
165 return Err(err!(
166 "The token size X provided, {}, must be at least 2 and no \
167 more than {}.", X, MAX_X;
168 Invalid, Input));
169 }
170 let padding_reqd = !(X == 2 || X == 4 || X == 8);
171 if !padding_reqd && padding.is_some() {
172 return Err(err!(
173 "Padding is not required for a token size of {}, so padding parameters \
174 should be set to None.", X;
175 Invalid, Input, Mismatch));
176 }
177 if padding_reqd && padding.is_none() {
178 return Err(err!(
179 "Padding is required for a token size {} but no padding characters \
180 were provided.", X;
181 Invalid, Input, Missing));
182 }
183 let x = match Self::validate_size(A) {
184 Some(x) => x,
185 None => return Err(err!(
186 "Alphabet length {} must be a power of 2, and less than {}",
187 A, MAX_A;
188 Invalid, Input)),
189 };
190 if x != X {
191 return Err(err!(
192 "The alphabet length {} must equal 2^X ({}) where the X \
193 supplied is {}.", A, 2_usize.pow(X as u32), X;
194 Invalid, Input));
195 }
196 let non_unique = Self::find_non_unique_chars(&alphabet, &padding.map(|(c, _)| c));
197 if non_unique.len() > 0 {
198 return Err(err!(
199 "Alphabet characters must be unique, these ones repeat: {:?}.", non_unique;
200 Invalid, Input));
201 }
202 if padding_reqd {
203 if let Some(p) = padding {
204 let non_unique = Self::find_non_unique_chars(&p.1, &Some(p.0));
205 if non_unique.len() > 0 {
206 return Err(err!(
207 "Padding set characters must be unique, these ones repeat: {:?}.",
208 non_unique;
209 Invalid, Input));
210 }
211 }
212 }
213 Ok(Self {
214 alphabet,
215 padding,
216 })
217 }
218
219 /// Returns a set of non-unique characters in the proposed alphabet. None of the characters
220 /// should match the padding character.
221 fn find_non_unique_chars<const T: usize>(a: &[char; T], pad_sep: &Option<char>) -> HashSet<char> {
222 let mut seen = HashSet::new();
223 let mut non_unique = HashSet::new();
224
225 for &c in a {
226 if !seen.insert(c) || Some(c) == *pad_sep {
227 non_unique.insert(c);
228 }
229 }
230
231 non_unique
232 }
233
234 /// Checks the size of the alphabet and returns the base two logarithm of the size if it is an
235 /// integer, or `None` otherwise.
236 fn validate_size(n: usize) -> Option<usize> {
237 if n == 0 || n as u64 > MAX_A { return None; }
238
239 let mut exponent = 0;
240 let mut value = n;
241
242 while value != 1 {
243 if value % 2 != 0 {
244 return None;
245 }
246 value /= 2;
247 exponent += 1;
248 }
249
250 Some(exponent)
251 }
252
253 /// A helper for preparing alphabets into the required array form.
254 pub fn prepare_alphabet(s: &str) -> Outcome<[char; A]> {
255 let chars: Vec<char> = s.chars().collect();
256 if chars.len() != A {
257 return Err(err!(
258 "The number of characters in the given alphabet, {}, does not match \
259 your generic parameter, {}.", chars.len(), A;
260 Invalid, Size, Input, Mismatch));
261 }
262 match chars.try_into() {
263 Ok(a) => Ok(a),
264 Err(_) => Err(err!(
265 "Failed to convert Vec<char> to [char; {}].", A;
266 Conversion)),
267 }
268 }
269
270 /// A helper for preparing padding sets into the required array form.
271 pub fn prepare_pad_set(s: &str) -> Outcome<[char; X]> {
272 let chars: Vec<char> = s.chars().collect();
273 if chars.len() != X {
274 return Err(err!(
275 "The number of characters in the padding set, {}, does not match \
276 your generic parameter, {}.", chars.len(), X;
277 Invalid, Size, Input, Mismatch));
278 }
279 match chars.try_into() {
280 Ok(a) => Ok(a),
281 Err(_) => Err(err!(
282 "Failed to convert Vec<char> to [char; {}].", X;
283 Conversion)),
284 }
285 }
286
287 pub fn pad_sep(&self) -> Option<char> { self.padding.map(|(c, _)| c) }
288 pub fn alphabet_size(&self) -> usize { A }
289 pub fn token_size(&self) -> usize { X }
290
291 pub fn fmt_pad_set(&self) -> String {
292 let mut result = String::new();
293 if let Some((_, pad_set)) = self.padding {
294 for c in pad_set {
295 result.push(c);
296 }
297 }
298 result
299 }
300
301 pub fn fmt_char_map(&self) -> Vec<String> {
302 let mut result = Vec::new();
303 for (i, c) in self.alphabet.iter().enumerate() {
304 result.push(fmt!("'{}' -> {:0width$b}", c, i, width = X));
305 }
306 result
307 }
308
309 pub fn get_char(&self, token: u32) -> char {
310 self.alphabet[token as usize]
311 }
312
313 pub fn get_pad_char(&self, padding: u8) -> Option<char> {
314 self.padding.map(|(_, pad_set)| pad_set[padding as usize])
315 }
316
317 pub fn get_token(&self, c: char) -> Option<u32> {
318 self.alphabet.iter().position(|&x| x == c)
319 .and_then(|v| u32::try_from(v).ok())
320 }
321
322 pub fn get_padding_bits(&self, p: char) -> Option<u8> {
323 match self.padding {
324 Some((_, pad_set)) => pad_set.iter().position(|&c| c == p)
325 .and_then(|v| u8::try_from(v).ok()),
326 None => None,
327 }
328 }
329
330 /// Append padding characters to the given string. Padding value must be > 0.
331 pub fn push_pad(&self, encoded: &mut String, padding: u8) {
332 if let Some((pad_sep, _)) = self.padding {
333 encoded.push(pad_sep);
334 }
335 if let Some(c) = self.get_pad_char(padding - 1) {
336 encoded.push(c);
337 }
338 }
339
340 pub fn to_string(&self, input: &[u8]) -> String {
341 let mut encoded = String::new();
342 let (tokens, padding) = self.tokenise(input);
343 for token in tokens {
344 encoded.push(self.get_char(token));
345 }
346 if padding > 0 {
347 //trace!("padding = {}, '{}'", padding, self.fmt_pad_set());
348 self.push_pad(&mut encoded, padding);
349 }
350 encoded
351 }
352
353 #[inline]
354 const fn lower_bit_mask(z: usize) -> u64 {
355 (1 << z) - 1
356 }
357
358 fn tokenise(&self, data: &[u8]) -> (Vec<u32>, u8) {
359 //trace!("mask: {}",
360 // Stringer::new(fmt!("{:0width$b}", Self::TOKEN_MASK, width = 64)).insert_every("_", 8),
361 //);
362 let mut tokens = Vec::new();
363 let mut buf: u64 = 0; // Handle overflow.
364 let mut bits_in_buf = 0;
365
366 for &byt in data {
367 //buf |= (*byt as u64) << bits_in_buf;
368 buf = (buf << 8) | byt as u64;
369 bits_in_buf += 8;
370 //trace!("bite: shift next byte in from left, buf {} {:08b} {}",
371 // Stringer::new(fmt!("{:0width$b}", buf, width = 64)).insert_every("_", 8),
372 // byt, bits_in_buf,
373 //);
374
375 // Extract as many tokens as possible.
376 while bits_in_buf >= X {
377 let token = (buf >> (bits_in_buf - X)) & Self::TOKEN_MASK;
378 //trace!(" chew: buf right shifted by {} {}", bits_in_buf - X,
379 // Stringer::new(fmt!("{:0width$b}", buf >> (bits_in_buf - X), width = 64)).insert_every("_", 8),
380 //);
381 //trace!(" chew: token {}",
382 // Stringer::new(fmt!("{:0width$b}", token, width = X)).insert_every("_", 8),
383 //);
384 tokens.push(token as u32);
385 bits_in_buf -= X;
386 //trace!(" chew: buf {} token {:0width$b} {}",
387 // Stringer::new(fmt!("{:0width$b}", buf, width = 64)).insert_every("_", 8),
388 // token, bits_in_buf, width = X,
389 //);
390 }
391 }
392
393 let padding = if bits_in_buf > 0 {
394 let padding = X - bits_in_buf;
395 let token = buf << padding & Self::TOKEN_MASK;
396 tokens.push(token as u32);
397 //trace!(" final token {:0width$b} {} padding {}", token, bits_in_buf, padding, width = X);
398 padding
399 } else {
400 0
401 };
402
403 (tokens, padding as u8)
404 }
405
406 pub fn string_to_tokens(&self, encoded: String) -> Outcome<Vec<u32>> {
407 let mut tokens = Vec::new();
408 for c in encoded.chars() {
409 let index = self.get_token(c);
410 match index {
411 Some(i) => tokens.push(i),
412 None => return Err(err!(
413 "Character '{}' not recognised by this Base2x alphabet.", c;
414 Unknown, Invalid, Input, String, Decode)),
415 }
416 }
417 Ok(tokens)
418 }
419
420 pub fn from_str(&self, s: &str) -> Outcome<Vec<u8>> {
421 if s.len() == 0 {
422 return Ok(Vec::new());
423 }
424 let (encoded, padding) = res!(self.parse_pad(s));
425 if padding > 0 {
426 res!(self.validate(&encoded, padding));
427 }// else {
428 // padding = self.normalise(&mut encoded);
429 //}
430 //trace!("from_str: '{}', padding {}", encoded, padding);
431 let tokens = res!(self.string_to_tokens(encoded));
432 // We just needed to ensure any partial token is present at the end, and no longer need the
433 // padding amount, since the padding bits are automatically filled with zeros.
434 Ok(self.detokenise(&tokens))
435 }
436
437 fn validate(&self, encoded: &String, padding: u8) -> Outcome<()> {
438 let bits = encoded.chars().count() * X - ( padding as usize );
439 if padding > 0 {
440 //trace!("validation: padding = {} bits = {}", padding, bits);
441 if bits % 8 != 0 {
442 return Err(err!(
443 "The padding of {} zero bits is not valid because string decoding \
444 will lead to a total bit length that is not divisible by 8.", padding;
445 Invalid, Input, Mismatch, String, Decode));
446 }
447 }
448 Ok(())
449 }
450
451 pub fn normalise(&self, encoded: &mut String) -> u8 {
452 let bits = encoded.len() * X;
453 let rem = (bits + 7) / 8 * 8 - bits;
454 let mut padding = 0;
455 if rem > 0 {
456 padding = (X - rem) as u8;
457 (*encoded).push(self.get_char(0));
458 //trace!("normalisation: padding = {} new encoded = '{}'", padding, encoded);
459 }
460 padding
461 }
462
463 fn parse_pad(&self, encoded: &str) -> Outcome<(String, u8)> {
464 let mut encoded = encoded.to_string();
465 if let Some((pad_sep, _)) = self.padding {
466 if encoded.ends_with(|c: char| c.is_digit(10)) &&
467 encoded.chars().nth_back(1) == Some(pad_sep)
468 {
469 if let Some(padding_amount_char) = encoded.pop() {
470 if encoded.pop() == Some(pad_sep) {
471 match self.get_padding_bits(padding_amount_char) {
472 Some(padding) => return Ok((encoded, padding + 1)),
473 None => return Err(err!(
474 "Padding character '{}' is invalid, must be in the \
475 set {}.", padding_amount_char, self.fmt_pad_set();
476 Invalid, Input, String, Decode)),
477 }
478 } else {
479 unreachable!()
480 }
481 }
482 }
483 }
484 Ok((encoded, 0))
485 }
486
487 fn detokenise(&self, tokens: &[u32]) -> Vec<u8> {
488 let mut data = Vec::new();
489 let mut buf: u64 = 0;
490 let mut bits_in_buf = 0;
491
492 for token in tokens {
493 buf = (buf << X) | *token as u64;
494 bits_in_buf += X;
495 //trace!("bite: buf {} {} token {:0width$b}",
496 // Stringer::new(fmt!("{:0width$b}", buf, width = 64)).insert_every("_", 8),
497 // bits_in_buf, token, width = X,
498 //);
499
500 while bits_in_buf >= 8 {
501 let byt = (buf >> (bits_in_buf - 8)) & 0xff; // Extract byte from the top.
502 //trace!(" chew: buf {} byt {:08b}",
503 // Stringer::new(fmt!("{:0width$b}", buf, width = 64)).insert_every("_", 8),
504 // byt,
505 //);
506 data.push(byt as u8);
507 bits_in_buf -= 8;
508 }
509 }
510
511 data
512 }
513}