clock_bigint/
encode.rs

1//! Canonical encoding and decoding for BigInt.
2//!
3//! Binary format: [sign: u8][limb_count: u32 LE][limbs: u64[] LE]
4//!
5//! All fields are encoded little-endian. The encoding is canonical,
6//! meaning exactly one valid encoding exists per integer value.
7
8use crate::error::{BigIntError, Result};
9use crate::limbs::{Limb, canonicalize, is_zero};
10use crate::types::{BigInt, BigIntCore};
11
12#[cfg(feature = "alloc")]
13/// Encode a BigInt to canonical binary format.
14///
15/// Format: [sign: u8][limb_count: u32 LE][limbs: u64[] LE]
16pub fn encode(bi: &BigInt) -> alloc::vec::Vec<u8> {
17    let limbs = bi.limbs();
18    let canonical_limbs = {
19        let mut limbs_copy = limbs.to_vec();
20        let len = canonicalize(&mut limbs_copy);
21        limbs_copy.truncate(len);
22        limbs_copy
23    };
24
25    let limb_count = canonical_limbs.len() as u32;
26    let sign_byte = if bi.sign() { 1u8 } else { 0u8 };
27
28    // Calculate total size: 1 (sign) + 4 (limb_count) + 8 * limb_count (limbs)
29    let mut result = alloc::vec::Vec::with_capacity(1 + 4 + (8 * canonical_limbs.len()));
30
31    // Write sign byte
32    result.push(sign_byte);
33
34    // Write limb count (little-endian u32)
35    result.extend_from_slice(&limb_count.to_le_bytes());
36
37    // Write limbs (little-endian u64 each)
38    for &limb in &canonical_limbs {
39        result.extend_from_slice(&limb.to_le_bytes());
40    }
41
42    result
43}
44
45#[cfg(feature = "alloc")]
46/// Decode a BigInt from canonical binary format.
47///
48/// Validates that the encoding is canonical:
49/// - Zero must have sign=0, n=1, limbs\[0\]=0
50/// - No leading zeros for nonzero values
51/// - Sign consistency
52pub fn decode(data: &[u8]) -> Result<BigInt> {
53    if data.len() < 5 {
54        return Err(BigIntError::InvalidEncoding);
55    }
56
57    // Read sign byte
58    let sign_byte = data[0];
59    if sign_byte > 1 {
60        return Err(BigIntError::InvalidEncoding);
61    }
62    let sign = sign_byte != 0;
63
64    // Read limb count (little-endian u32)
65    let limb_count_bytes = data[1..5]
66        .try_into()
67        .map_err(|_| BigIntError::InvalidEncoding)?;
68    let limb_count = u32::from_le_bytes(limb_count_bytes) as usize;
69
70    // Validate limb count
71    if limb_count == 0 || limb_count > crate::gas::MAX_LIMBS {
72        return Err(BigIntError::InvalidEncoding);
73    }
74
75    // Calculate expected data length
76    let expected_len = 1 + 4 + (8 * limb_count);
77    if data.len() < expected_len {
78        return Err(BigIntError::InvalidEncoding);
79    }
80
81    // Read limbs
82    let mut limbs = alloc::vec::Vec::with_capacity(limb_count);
83    for i in 0..limb_count {
84        let offset = 5 + (i * 8);
85        let limb_bytes = data[offset..offset + 8]
86            .try_into()
87            .map_err(|_| BigIntError::InvalidEncoding)?;
88        let limb = Limb::from_le_bytes(limb_bytes);
89        limbs.push(limb);
90    }
91
92    // Validate canonical form
93    // 1. Zero: sign=0, n=1, limbs[0]=0
94    let is_zero_value = is_zero(&limbs);
95    if is_zero_value {
96        if sign {
97            return Err(BigIntError::InvalidEncoding); // Negative zero forbidden
98        }
99        if limb_count != 1 || limbs[0] != 0 {
100            return Err(BigIntError::InvalidEncoding);
101        }
102    } else {
103        // 2. No leading zeros: limbs[n-1] ≠ 0
104        if limbs[limb_count - 1] == 0 {
105            return Err(BigIntError::InvalidEncoding);
106        }
107
108        // 3. Sign consistency: if sign=1, value must be negative
109        // (We can't verify this without knowing the actual value, but we check
110        // that the encoding is minimal)
111    }
112
113    // Create BigInt
114    let max_limbs = limb_count.max(crate::gas::MAX_LIMBS);
115    let mut result = BigInt::from_limbs(&limbs, max_limbs)?;
116    result.set_sign(sign);
117
118    // Final canonicalization check
119    result.canonicalize()?;
120
121    Ok(result)
122}
123
124#[cfg(all(test, feature = "alloc"))]
125mod tests {
126    use super::*;
127    use alloc::vec;
128
129    #[test]
130    fn test_encode_zero() {
131        let bi = BigInt::from_u64(0, 10);
132        let encoded = encode(&bi);
133        assert_eq!(encoded[0], 0); // sign
134        assert_eq!(u32::from_le_bytes(encoded[1..5].try_into().unwrap()), 1); // limb_count
135        assert_eq!(u64::from_le_bytes(encoded[5..13].try_into().unwrap()), 0); // limb[0]
136    }
137
138    #[test]
139    fn test_encode_decode_roundtrip() {
140        let bi = BigInt::from_u64(42, 10);
141        let encoded = encode(&bi);
142        let decoded = decode(&encoded).unwrap();
143        assert_eq!(decoded.limbs()[0], 42);
144        assert_eq!(decoded.sign(), bi.sign());
145    }
146
147    #[test]
148    fn test_decode_invalid_negative_zero() {
149        // Create invalid encoding: sign=1, but value is zero
150        let mut invalid = vec![1u8]; // sign = 1 (negative)
151        invalid.extend_from_slice(&1u32.to_le_bytes()); // limb_count = 1
152        invalid.extend_from_slice(&0u64.to_le_bytes()); // limb[0] = 0
153        assert!(decode(&invalid).is_err());
154    }
155
156    #[test]
157    fn test_decode_invalid_leading_zeros() {
158        // Create invalid encoding: nonzero value with leading zero
159        let mut invalid = vec![0u8]; // sign = 0
160        invalid.extend_from_slice(&2u32.to_le_bytes()); // limb_count = 2
161        invalid.extend_from_slice(&42u64.to_le_bytes()); // limb[0] = 42
162        invalid.extend_from_slice(&0u64.to_le_bytes()); // limb[1] = 0 (invalid!)
163        assert!(decode(&invalid).is_err());
164    }
165}
clock_bigint/encode.rs

clock_bigint/
encode.rs
