fp/vector/
impl_fqslice.rs

1use itertools::Itertools;
2
3use super::{
4    inner::{FqSlice, FqVector},
5    iter::{FqVectorIterator, FqVectorNonZeroIterator},
6};
7use crate::{
8    constants,
9    field::{Field, element::FieldElement},
10    limb::Limb,
11    prime::{Prime, ValidPrime},
12};
13
14// Public methods
15
16impl<'a, F: Field> FqSlice<'a, F> {
17    pub fn prime(&self) -> ValidPrime {
18        self.fq().characteristic().to_dyn()
19    }
20
21    pub fn len(&self) -> usize {
22        self.end() - self.start()
23    }
24
25    pub const fn is_empty(&self) -> bool {
26        self.start() == self.end()
27    }
28
29    pub fn entry(&self, index: usize) -> FieldElement<F> {
30        debug_assert!(
31            index < self.len(),
32            "Index {} too large, length of vector is only {}.",
33            index,
34            self.len()
35        );
36        let bit_mask = self.fq().bitmask();
37        let limb_index = self.fq().limb_bit_index_pair(index + self.start());
38        let mut result = self.limbs()[limb_index.limb];
39        result >>= limb_index.bit_index;
40        result &= bit_mask;
41        self.fq().decode(result)
42    }
43
44    /// TODO: implement prime 2 version
45    pub fn iter(self) -> FqVectorIterator<'a, F> {
46        FqVectorIterator::new(self)
47    }
48
49    pub fn iter_nonzero(self) -> FqVectorNonZeroIterator<'a, F> {
50        FqVectorNonZeroIterator::new(self)
51    }
52
53    pub fn first_nonzero(&self) -> Option<(usize, FieldElement<F>)> {
54        self.iter_nonzero().next()
55    }
56
57    pub fn is_zero(&self) -> bool {
58        let limb_range = self.limb_range();
59        if limb_range.is_empty() {
60            return true;
61        }
62        let (min_mask, max_mask) = self.limb_masks();
63        if self.limbs()[limb_range.start] & min_mask != 0 {
64            return false;
65        }
66
67        let inner_range = self.limb_range_inner();
68        if !inner_range.is_empty() && self.limbs()[inner_range].iter().any(|&x| x != 0) {
69            return false;
70        }
71        if self.limbs()[limb_range.end - 1] & max_mask != 0 {
72            return false;
73        }
74        true
75    }
76
77    #[must_use]
78    pub fn restrict(self, start: usize, end: usize) -> Self {
79        assert!(start <= end && end <= self.len());
80
81        FqSlice::new(
82            self.fq(),
83            self.into_limbs(),
84            self.start() + start,
85            self.start() + end,
86        )
87    }
88
89    /// Converts a slice to an owned FqVector. This is vastly more efficient if the start of the vector is aligned.
90    #[must_use]
91    pub fn to_owned(self) -> FqVector<F> {
92        let mut new = FqVector::new(self.fq(), self.len());
93        if self.start().is_multiple_of(self.fq().entries_per_limb()) {
94            let limb_range = self.limb_range();
95            new.limbs_mut()[0..limb_range.len()].copy_from_slice(&self.limbs()[limb_range]);
96            if !new.limbs().is_empty() {
97                let len = new.limbs().len();
98                new.limbs_mut()[len - 1] &= self.limb_masks().1;
99            }
100        } else {
101            new.as_slice_mut().assign(self);
102        }
103        new
104    }
105}
106
107// Limb methods
108impl<F: Field> FqSlice<'_, F> {
109    #[inline]
110    pub(super) fn offset(&self) -> usize {
111        let bit_length = self.fq().bit_length();
112        let entries_per_limb = self.fq().entries_per_limb();
113        (self.start() % entries_per_limb) * bit_length
114    }
115
116    #[inline]
117    pub(super) fn limb_range(&self) -> std::ops::Range<usize> {
118        self.fq().range(self.start(), self.end())
119    }
120
121    /// This function underflows if `self.end() == 0`, which happens if and only if we are taking a
122    /// slice of width 0 at the start of an `FpVector`. This should be a very rare edge case.
123    /// Dealing with the underflow properly would probably require using `saturating_sub` or
124    /// something of that nature, and that has a nontrivial (10%) performance hit.
125    #[inline]
126    pub(super) fn limb_range_inner(&self) -> std::ops::Range<usize> {
127        let range = self.limb_range();
128        (range.start + 1)..(usize::max(range.start + 1, range.end - 1))
129    }
130
131    #[inline(always)]
132    pub(super) fn min_limb_mask(&self) -> Limb {
133        !0 << self.offset()
134    }
135
136    #[inline(always)]
137    pub(super) fn max_limb_mask(&self) -> Limb {
138        let num_entries = 1 + (self.end() - 1) % self.fq().entries_per_limb();
139        let bit_max = num_entries * self.fq().bit_length();
140
141        (!0) >> (constants::BITS_PER_LIMB - bit_max)
142    }
143
144    #[inline(always)]
145    pub(super) fn limb_masks(&self) -> (Limb, Limb) {
146        if self.limb_range().len() == 1 {
147            (
148                self.min_limb_mask() & self.max_limb_mask(),
149                self.min_limb_mask() & self.max_limb_mask(),
150            )
151        } else {
152            (self.min_limb_mask(), self.max_limb_mask())
153        }
154    }
155}
156
157impl<'a, F: Field> From<&'a FqVector<F>> for FqSlice<'a, F> {
158    fn from(v: &'a FqVector<F>) -> Self {
159        v.slice(0, v.len())
160    }
161}
162
163impl<F: Field> std::fmt::Display for FqSlice<'_, F> {
164    /// # Example
165    /// ```
166    /// # use fp::field::{Field, SmallFq};
167    /// # use fp::prime::{P2, ValidPrime};
168    /// # use fp::vector::FqVector;
169    /// let fq = SmallFq::new(P2, 3);
170    /// let v = FqVector::from_slice(fq, &[fq.zero(), fq.one(), fq.a(), fq.a() * fq.a()]);
171    /// assert_eq!(&format!("{v}"), "[0, 1, a, a^2]");
172    ///
173    /// // This only looks reasonable over prime fields of order less than 10
174    /// assert_eq!(&format!("{v:#}"), "01aa^2");
175    /// ```
176    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
177        if f.alternate() {
178            for v in self.iter() {
179                // If self.p >= 11, this will look funky
180                write!(f, "{v}")?;
181            }
182            Ok(())
183        } else {
184            write!(f, "[{}]", self.iter().format(", "))
185        }
186    }
187}
fp/vector/impl_fqslice.rs

fp/vector/
impl_fqslice.rs
