ms_codec/codex32/
field.rs

1// Vendored from `codex32` v0.1.0 (crates.io checksum
2// d230935faa4d0521349d228f39aba4ff489cf2a8bcab4d84e31f4cbd6fe918e9), CC0-1.0,
3// by Andrew Poelstra. Inlined into ms-codec (Cycle-B, shape A) to own the
4// Zeroize/Drop/redacting-Debug secret-hygiene fixes (FOLLOWUP
5// codex32-upstream-dormant-vendor-vs-accept-decision).
6//
7// Copied from the upstream runtime modules (lib.rs / field.rs / checksum.rs).
8// The ONLY substantive edits are: (1) Zeroize/ZeroizeOnDrop + a redacting Debug
9// on `Codex32String` (Phase 2); (2) module-routing of `use` paths to fit the
10// inlined submodule (`crate::field` -> `super::field` in checksum.rs, since the
11// codex32 crate root is now the `codex32` submodule); (3) crate-local lint
12// `#![allow(..)]`s (the crate denies missing_docs / runs -D-warnings clippy; the
13// upstream copy predates both). rustfmt also normalized a few cosmetic spots
14// (import order, one array literal, one fn-signature wrap) — NONE touch encoding
15// logic. The ENCODING (from_seed/from_string/interpolate_at/checksum/field) is
16// behaviorally UNCHANGED; the wire-byte-identity invariant is proven by
17// tests/codex32_vendor_parity.rs. The upstream CC0 LICENSE is retained verbatim
18// alongside as src/codex32/LICENSE.
19//
20// Rust Codex32 Library and Reference Implementation
21// Written in 2023 by
22//   Andrew Poelstra <apoelstra@wpsoftware.net>
23//
24// To the extent possible under law, the author(s) have dedicated all
25// copyright and related and neighboring rights to this software to
26// the public domain worldwide. This software is distributed without
27// any warranty.
28//
29// You should have received a copy of the CC0 Public Domain Dedication
30// along with this software.
31// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
32//
33
34//! Field Implementation
35//!
36//! Implements GF32 arithmetic, defined and encoded as in BIP-0173 "bech32"
37//!
38
39use std::{
40    convert::{TryFrom, TryInto},
41    fmt, num, ops, str,
42};
43
44/// Locarithm table of each bech32 element, as a power of alpha = Z.
45///
46/// Includes Q as 0 but this is false; you need to exclude Q because
47/// it has no discrete log. If we could have a 1-indexed array that
48/// would panic on a 0 index that would be better.
49#[rustfmt::skip]
50const LOG: [isize; 32] = [
51     0,  0,  1, 14,  2, 28, 15, 22,
52     3,  5, 29, 26, 16,  7, 23, 11, 
53     4, 25,  6, 10, 30, 13, 27, 21,
54    17, 18,  8, 19, 24,  9, 12, 20,
55];
56
57/// Mapping of powers of 2 to the numeric value of the element
58#[rustfmt::skip]
59const LOG_INV: [u8; 31] = [
60     1,  2,  4,  8, 16,  9, 18, 13,
61    26, 29, 19, 15, 30, 21,  3,  6,
62    12, 24, 25, 27, 31, 23,  7, 14,
63    28, 17, 11, 22,  5, 10, 20,
64];
65
66/// Mapping from numeric value to bech32 character
67#[rustfmt::skip]
68const CHARS_LOWER: [char; 32] = [
69    'q', 'p', 'z', 'r', 'y', '9', 'x', '8', //  +0
70    'g', 'f', '2', 't', 'v', 'd', 'w', '0', //  +8
71    's', '3', 'j', 'n', '5', '4', 'k', 'h', // +16
72    'c', 'e', '6', 'm', 'u', 'a', '7', 'l', // +24
73];
74
75/// Mapping from bech32 character (either case) to numeric value
76#[rustfmt::skip]
77const CHARS_INV: [i8; 128] = [
78    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
79    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
80    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
81    15, -1, 10, 17, 21, 20, 26, 30,  7,  5, -1, -1, -1, -1, -1, -1,
82    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
83     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1,
84    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
85     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1,
86];
87
88/// Field-related error
89#[derive(Debug)]
90pub enum Error {
91    /// Tried to decode a GF32 element from a string, but got more than one character
92    ExtraChar(char),
93    /// Tried to interpret an integer as a GF32 element but it could not be
94    /// converted to an u8.
95    NotAByte(num::TryFromIntError),
96    /// Tried to interpret a byte as a GF32 element but its numeric value was
97    /// outside of [0, 32).
98    InvalidByte(u8),
99}
100
101/// An element of GF32
102#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
103pub struct Fe(u8);
104
105impl ops::Add for Fe {
106    type Output = Fe;
107    fn add(self, other: Fe) -> Fe {
108        Fe(self.0 ^ other.0)
109    }
110}
111
112impl ops::AddAssign for Fe {
113    fn add_assign(&mut self, other: Fe) {
114        *self = *self + other;
115    }
116}
117
118// Subtraction is the same as addition in a char-2 field
119impl ops::Sub for Fe {
120    type Output = Fe;
121    fn sub(self, other: Fe) -> Fe {
122        self + other
123    }
124}
125
126impl ops::SubAssign for Fe {
127    fn sub_assign(&mut self, other: Fe) {
128        *self = *self - other;
129    }
130}
131
132impl ops::Mul for Fe {
133    type Output = Fe;
134    fn mul(self, other: Fe) -> Fe {
135        if self.0 == 0 || other.0 == 0 {
136            Fe(0)
137        } else {
138            let log1 = LOG[self.0 as usize];
139            let log2 = LOG[other.0 as usize];
140            Fe(LOG_INV[((log1 + log2) % 31) as usize])
141        }
142    }
143}
144
145impl ops::MulAssign for Fe {
146    fn mul_assign(&mut self, other: Fe) {
147        *self = *self * other;
148    }
149}
150
151impl ops::Div for Fe {
152    type Output = Fe;
153    fn div(self, other: Fe) -> Fe {
154        if self.0 == 0 {
155            Fe(0)
156        } else if other.0 == 0 {
157            panic!("Attempt to divide {} by 0 in GF32", self);
158        } else {
159            let log1 = LOG[self.0 as usize];
160            let log2 = LOG[other.0 as usize];
161            Fe(LOG_INV[((31 + log1 - log2) % 31) as usize])
162        }
163    }
164}
165
166impl ops::DivAssign for Fe {
167    fn div_assign(&mut self, other: Fe) {
168        *self = *self / other;
169    }
170}
171
172impl Fe {
173    // These are a little gratuitous for a reference implementation,
174    // but it makes me happy to do it
175    pub const Q: Fe = Fe(0);
176    pub const P: Fe = Fe(1);
177    #[allow(dead_code)]
178    pub const Z: Fe = Fe(2);
179    pub const R: Fe = Fe(3);
180    pub const Y: Fe = Fe(4);
181    pub const _9: Fe = Fe(5);
182    pub const X: Fe = Fe(6);
183    pub const _8: Fe = Fe(7);
184    pub const G: Fe = Fe(8);
185    pub const F: Fe = Fe(9);
186    pub const _2: Fe = Fe(10);
187    pub const T: Fe = Fe(11);
188    #[allow(dead_code)]
189    pub const V: Fe = Fe(12);
190    #[allow(dead_code)]
191    pub const D: Fe = Fe(13);
192    #[allow(dead_code)]
193    pub const W: Fe = Fe(14);
194    pub const _0: Fe = Fe(15);
195    pub const S: Fe = Fe(16);
196    pub const _3: Fe = Fe(17);
197    #[allow(dead_code)]
198    pub const J: Fe = Fe(18);
199    #[allow(dead_code)]
200    pub const N: Fe = Fe(19);
201    pub const _5: Fe = Fe(20);
202    pub const _4: Fe = Fe(21);
203    pub const K: Fe = Fe(22);
204    pub const H: Fe = Fe(23);
205    pub const C: Fe = Fe(24);
206    pub const E: Fe = Fe(25);
207    pub const _6: Fe = Fe(26);
208    pub const M: Fe = Fe(27);
209    #[allow(dead_code)]
210    pub const U: Fe = Fe(28);
211    pub const A: Fe = Fe(29);
212    pub const _7: Fe = Fe(30);
213    pub const L: Fe = Fe(31);
214
215    /// Iterator over all field elements, in alphabetical order
216    pub fn iter_alpha() -> impl Iterator<Item = Fe> {
217        [
218            Fe::A,
219            Fe::C,
220            Fe::D,
221            Fe::E,
222            Fe::F,
223            Fe::G,
224            Fe::H,
225            Fe::J,
226            Fe::K,
227            Fe::L,
228            Fe::M,
229            Fe::N,
230            Fe::P,
231            Fe::Q,
232            Fe::R,
233            Fe::S,
234            Fe::T,
235            Fe::U,
236            Fe::V,
237            Fe::W,
238            Fe::X,
239            Fe::Y,
240            Fe::Z,
241            Fe::_0,
242            Fe::_2,
243            Fe::_3,
244            Fe::_4,
245            Fe::_5,
246            Fe::_6,
247            Fe::_7,
248            Fe::_8,
249            Fe::_9,
250        ]
251        .iter()
252        .copied()
253    }
254
255    /// Creates a field element from an integer type
256    pub fn from_u8(byte: u8) -> Result<Fe, super::Error> {
257        if byte < 32 {
258            Ok(Fe(byte))
259        } else {
260            Err(super::Error::Field(Error::InvalidByte(byte)))
261        }
262    }
263
264    /// Creates a field element from an integer type
265    pub fn from_int<I>(i: I) -> Result<Fe, super::Error>
266    where
267        I: TryInto<u8, Error = num::TryFromIntError>,
268    {
269        i.try_into()
270            .map_err(|e| super::Error::Field(Error::NotAByte(e)))
271            .and_then(Self::from_u8)
272    }
273
274    /// Creates a field element from a single bech32 character
275    pub fn from_char(c: char) -> Result<Fe, super::Error> {
276        let byte = i8::try_from(u32::from(c)).map_err(|_| super::Error::InvalidChar(c))?;
277        let byte = byte as u8; // cast guaranteed to be ok since we started with an unsigned value
278        let u5 =
279            u8::try_from(CHARS_INV[usize::from(byte)]).map_err(|_| super::Error::InvalidChar(c))?;
280        Ok(Fe(u5))
281    }
282
283    /// Converts the field element to a lowercase bech32 character
284    pub fn to_char(self) -> char {
285        // casting and indexing fine as we have self.0 in [0, 32) as an invariant
286        CHARS_LOWER[self.0 as usize]
287    }
288
289    /// Converts the field element to a 5-bit u8, with bits representing the coefficients
290    /// of the polynomial representation.
291    pub fn to_u8(self) -> u8 {
292        self.0
293    }
294}
295
296impl fmt::Display for Fe {
297    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
298        fmt::Display::fmt(&self.to_char(), f)
299    }
300}
301
302impl str::FromStr for Fe {
303    type Err = super::Error;
304    fn from_str(s: &str) -> Result<Fe, super::Error> {
305        let mut chs = s.chars();
306        match (chs.next(), chs.next()) {
307            (Some(c), None) => Fe::from_char(c),
308            (Some(_), Some(c)) => Err(super::Error::Field(Error::ExtraChar(c))),
309            (None, _) => Err(super::Error::InvalidLength(0)),
310        }
311    }
312}
ms_codec/codex32/field.rs

ms_codec/codex32/
field.rs
