zkaluvm/
fe.rs

1// AluVM ISA extension for Galois fields
2//
3// SPDX-License-Identifier: Apache-2.0
4//
5// Designed in 2024-2025 by Dr Maxim Orlovsky <orlovsky@ubideco.org>
6// Written in 2024-2025 by Dr Maxim Orlovsky <orlovsky@ubideco.org>
7//
8// Copyright (C) 2024-2025 Laboratories for Ubiquitous Deterministic Computing (UBIDECO),
9//                         Institute for Distributed and Cognitive Systems (InDCS), Switzerland.
10// Copyright (C) 2024-2025 Dr Maxim Orlovsky.
11// All rights under the above copyrights are reserved.
12//
13// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
14// in compliance with the License. You may obtain a copy of the License at
15//
16//        http://www.apache.org/licenses/LICENSE-2.0
17//
18// Unless required by applicable law or agreed to in writing, software distributed under the License
19// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
20// or implied. See the License for the specific language governing permissions and limitations under
21// the License.
22
23use core::str::FromStr;
24
25use amplify::confinement::TinyBlob;
26use amplify::hex::FromHex;
27use amplify::num::u256;
28use amplify::{hex, Bytes32, Wrapper};
29use strict_encoding::{StrictDecode, StrictProduct, StrictTuple, StrictType, TypeName};
30
31use crate::LIB_NAME_FINITE_FIELD;
32
33/// Element of a Galois finite field.
34///
35/// Maximum size is 256 bits.
36#[allow(non_camel_case_types)]
37#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug, Display, From)]
38#[display("{0:X}.fe", alt = "{0:064X}.fe")]
39#[derive(StrictDumb, StrictEncode, StrictDecode)]
40#[strict_type(lib = LIB_NAME_FINITE_FIELD)]
41pub struct fe256(
42    #[from(u8)]
43    #[from(u16)]
44    #[from(u32)]
45    #[from(u64)]
46    #[from(u128)]
47    u256,
48);
49
50impl fe256 {
51    /// Zero element of the field.
52    pub const ZERO: Self = Self(u256::ZERO);
53
54    /// Construct a field element from a 256-bit unsigned integer value.
55    pub const fn to_u256(&self) -> u256 { self.0 }
56}
57
58impl From<Bytes32> for fe256 {
59    fn from(bytes: Bytes32) -> Self { Self::from(bytes.into_inner()) }
60}
61
62impl From<[u8; 32]> for fe256 {
63    fn from(bytes: [u8; 32]) -> Self {
64        let val = u256::from_le_bytes(bytes);
65        Self::from(val)
66    }
67}
68
69impl From<u256> for fe256 {
70    fn from(val: u256) -> Self { Self(val) }
71}
72
73impl StrictType for fe256 {
74    const STRICT_LIB_NAME: &'static str = LIB_NAME_FINITE_FIELD;
75    fn strict_name() -> Option<TypeName> { Some(tn!("Fe256")) }
76}
77impl StrictProduct for fe256 {}
78impl StrictTuple for fe256 {
79    const FIELD_COUNT: u8 = 1;
80}
81
82#[cfg(feature = "serde")]
83mod _serde {
84    use serde::de::{Error, Unexpected};
85    use serde::{Deserialize, Deserializer, Serialize, Serializer};
86
87    use super::*;
88
89    impl Serialize for fe256 {
90        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
91        where S: Serializer {
92            if serializer.is_human_readable() {
93                self.to_string().serialize(serializer)
94            } else {
95                self.0.serialize(serializer)
96            }
97        }
98    }
99
100    impl<'de> Deserialize<'de> for fe256 {
101        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
102        where D: Deserializer<'de> {
103            if deserializer.is_human_readable() {
104                let s = String::deserialize(deserializer)?;
105                Self::from_str(&s).map_err(|e| D::Error::invalid_value(Unexpected::Str(&s), &e.to_string().as_str()))
106            } else {
107                let val = u256::deserialize(deserializer)?;
108                Ok(Self(val))
109            }
110        }
111    }
112}
113
114/// Errors parsing field elements.
115#[derive(Clone, PartialEq, Eq, Debug, Display, Error, From)]
116pub enum ParseFeError {
117    /// Missed `.fe` suffix.
118    #[display("field element `{0}` must have a `.fe` suffix.")]
119    NoSuffix(String),
120
121    /// Invalid hex value.
122    #[from]
123    #[display(inner)]
124    Value(hex::Error),
125}
126
127impl FromStr for fe256 {
128    type Err = ParseFeError;
129
130    fn from_str(s: &str) -> Result<Self, Self::Err> {
131        let s = s
132            .strip_suffix(".fe")
133            .ok_or_else(|| ParseFeError::NoSuffix(s.to_owned()))?;
134        let bytes = if s.len() % 2 == 1 { TinyBlob::from_hex(&format!("0{s}"))? } else { TinyBlob::from_hex(s)? };
135        const BUF_SIZE: usize = 32;
136        let mut buf = [0u8; BUF_SIZE];
137        if bytes.len() > BUF_SIZE {
138            return Err(hex::Error::InvalidLength(BUF_SIZE, bytes.len()).into());
139        }
140        buf[(BUF_SIZE - bytes.len())..].copy_from_slice(bytes.as_slice());
141        let val = u256::from_be_bytes(buf);
142        Ok(Self(val))
143    }
144}
145
146#[cfg(test)]
147mod tests {
148    #![cfg_attr(coverage_nightly, coverage(off))]
149
150    use amplify::confinement::Confined;
151    use strict_encoding::{StrictDeserialize, StrictDumb, StrictSerialize};
152
153    use super::*;
154
155    #[test]
156    fn display_from_str() {
157        let s = "0000000000000000000000000000000000000000000000000000000000000000.fe";
158        let fe = fe256::from_str(s).unwrap();
159        assert_eq!(fe, fe256::ZERO);
160        assert_eq!(format!("{}", fe), "0.fe");
161        assert_eq!(format!("{:#}", fe), s);
162        assert_eq!(format!("{:?}", fe), "fe256(0x0000000000000000000000000000000000000000000000000000000000000000)");
163
164        let s = "A489C5940DEDEADBEEFBADCAFEFEEDDEEDABCDEF012345678047345495749857.fe";
165        let fe = fe256::from_str(s).unwrap();
166        assert_eq!(format!("{}", fe), s);
167        assert_eq!(format!("{:#}", fe), s);
168        assert_eq!(format!("{:?}", fe), "fe256(0xa489c5940dedeadbeefbadcafefeeddeedabcdef012345678047345495749857)");
169
170        let s = "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.fe";
171        let fe = fe256::from_str(s).unwrap();
172        assert_eq!(fe, fe256::from(u256::MAX));
173        assert_eq!(format!("{}", fe), s);
174        assert_eq!(format!("{:#}", fe), s);
175        assert_eq!(format!("{:?}", fe), "fe256(0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)");
176
177        let s = "0000000000000000000000000000000000000000000000000000000000000345.fe";
178        let fe = fe256::from_str(s).unwrap();
179        assert_eq!(format!("{}", fe), "345.fe");
180        assert_eq!(format!("{:#}", fe), s);
181        assert_eq!(format!("{:?}", fe), "fe256(0x0000000000000000000000000000000000000000000000000000000000000345)");
182
183        let s = "345.fe";
184        let fe = fe256::from_str(s).unwrap();
185        assert_eq!(format!("{}", fe), "345.fe");
186        assert_eq!(format!("{:#}", fe), "0000000000000000000000000000000000000000000000000000000000000345.fe");
187        assert_eq!(format!("{:?}", fe), "fe256(0x0000000000000000000000000000000000000000000000000000000000000345)");
188
189        let s = "1230000000000000000000000000000000000000000000000000000000000000.fe";
190        let fe = fe256::from_str(s).unwrap();
191        assert_eq!(format!("{}", fe), "1230000000000000000000000000000000000000000000000000000000000000.fe");
192        assert_eq!(format!("{:#}", fe), s);
193        assert_eq!(format!("{:?}", fe), "fe256(0x1230000000000000000000000000000000000000000000000000000000000000)");
194    }
195
196    #[test]
197    #[should_panic(expected = r#"NoSuffix("0000000000000000000000000000000000000000000000000000000000000000")"#)]
198    fn from_str_no_suffix() {
199        let s = "0000000000000000000000000000000000000000000000000000000000000000";
200        fe256::from_str(s).unwrap();
201    }
202
203    #[test]
204    #[should_panic(expected = "Value(InvalidLength(32, 33))")]
205    fn from_str_invalid_len() {
206        let s = "AA0000000000000000000000000000000000000000000000000000000000000000.fe";
207        fe256::from_str(s).unwrap();
208    }
209
210    #[test]
211    fn serde() {
212        use serde_test::{assert_tokens, Configure, Token};
213
214        let s = "A489C5940DEDEADBEEFBADCAFEFEEDDEEDABCDEF012345678047345495749857.fe";
215        let val = fe256::from_str(s).unwrap();
216        let dat = [
217            // Bincode length prefix
218            0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // The actual value
219            0xA4, 0x89, 0xC5, 0x94, 0x0D, 0xED, 0xEA, 0xDB, 0xEE, 0xFB, 0xAD, 0xCA, 0xFE, 0xFE, 0xED, 0xDE, 0xED, 0xAB,
220            0xCD, 0xEF, 0x01, 0x23, 0x45, 0x67, 0x80, 0x47, 0x34, 0x54, 0x95, 0x74, 0x98, 0x57,
221        ];
222        assert_eq!(bincode::serialize(&val).unwrap(), dat);
223        assert_eq!(bincode::deserialize::<fe256>(&dat).unwrap(), val);
224        assert_eq!(bincode::serialize(&val).unwrap(), bincode::serialize(&val.0).unwrap());
225        assert_tokens(&val.readable(), &[Token::Str(s)]);
226    }
227
228    #[test]
229    fn from_bytes() {
230        let mut bytes = [
231            0xA4, 0x89, 0xC5, 0x94, 0x0D, 0xED, 0xEA, 0xDB, 0xEE, 0xFB, 0xAD, 0xCA, 0xFE, 0xFE, 0xED, 0xDE, 0xED, 0xAB,
232            0xCD, 0xEF, 0x01, 0x23, 0x45, 0x67, 0x80, 0x47, 0x34, 0x54, 0x95, 0x74, 0x98, 0x57,
233        ];
234        // We use little-endian!
235        bytes.reverse();
236        let fe1 = fe256::from(bytes);
237        let fe2 = fe256::from(Bytes32::from_byte_array(bytes));
238        assert_eq!(fe1, fe2);
239        assert_eq!(fe1.to_string(), "A489C5940DEDEADBEEFBADCAFEFEEDDEEDABCDEF012345678047345495749857.fe");
240    }
241
242    #[test]
243    fn strict_encoding() {
244        #![allow(non_local_definitions)]
245
246        assert_eq!(fe256::strict_dumb(), fe256::ZERO);
247
248        impl StrictSerialize for fe256 {}
249        impl StrictDeserialize for fe256 {}
250
251        let bytes = [
252            0xA4, 0x89, 0xC5, 0x94, 0x0D, 0xED, 0xEA, 0xDB, 0xEE, 0xFB, 0xAD, 0xCA, 0xFE, 0xFE, 0xED, 0xDE, 0xED, 0xAB,
253            0xCD, 0xEF, 0x01, 0x23, 0x45, 0x67, 0x80, 0x47, 0x34, 0x54, 0x95, 0x74, 0x98, 0x57,
254        ];
255        let mut rev = bytes;
256        // We use little-endian!
257        rev.reverse();
258        let fe = fe256::from(rev);
259        assert_eq!(fe.to_strict_serialized::<32>().unwrap().as_slice(), rev.as_slice());
260        assert_eq!(fe, fe256::from_strict_serialized::<32>(Confined::from_iter_checked(rev)).unwrap());
261        assert_eq!(fe.to_string(), "A489C5940DEDEADBEEFBADCAFEFEEDDEEDABCDEF012345678047345495749857.fe");
262    }
263}
zkaluvm/fe.rs

zkaluvm/
fe.rs
