1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240
//! # Grand Unified Finite Field library* //! //! Implements GF(2<sup>x</sup>) for various "natural" sizes //! such as 2<sup>8</sup>, 2<sup>16</sup> and 2<sup>32</sup>. //! //! My goals for this crate are to: //! //! 1. help me learn to write good modules in Rust //! //! 2. help interested users learn about finite fields (ie, Galois //! fields) //! //! 3. provide a generic baseline implementation of basic maths //! (add, multiply, divide, etc.) over finite fields //! //! 4. explore various optimisations/adaptations (including //! table-based lookups and architecture-specific SIMD code) that can //! selectively override some/all of the default implementations //! (while remaining compatible with other implementations). //! //! Also to: //! //! 5. provide some useful utility functions that go beyond just //! `add`, `mul`, `div`, etc. (eg, determining whether a field //! polynomial is primitive, or generating lookup tables for different //! kinds of optimisations) //! //! See the top-level `Readme` for more information about the above. //! //! # Basic Use: doing maths in a particular field //! //! As a user, the steps to take to use this library are: //! //! * decide what "class" of field you want to use (GF(2<sup>8</sup>), //! GF(2<sup>16</sup>), etc.); //! //! * decide if you want to use one of the optimised adaptations or //! are happy with the default, generic code; //! //! * create a new field object (we can call `f`) of that class with //! your chosen field polynomial (aka "irreducible polynomial") by //! calling the appropriate constructor; //! //! * use that object to do maths in that field: eg, `result = //! f.mul(a,b)` //! # Crate Name //! //! \* The crate name is deliberately hyperbolic: //! //! > Noun *guff* - unacceptable behavior (especially ludicrously false statements) use num_traits; use num::{PrimInt,One,Zero}; /// A typing trait meant to map to a primitive unsigned integer type /// such as u8, u16 or u32. pub trait ElementStore : 'static + Copy + num_traits::int::PrimInt + std::fmt::Display + num::FromPrimitive + num::ToPrimitive // + num::FromPrimitive + num::ToPrimitive // + num::Integer // + num::cast::AsPrimitive<Self::E> // + num::Integer + num::One {} impl<T> ElementStore for T where T : 'static + Copy + num_traits::int::PrimInt + std::fmt::Display + num::FromPrimitive + num::ToPrimitive {} /// pub trait GaloisField { /// Natural storage class (u8, u16, u32, etc.) for storing /// elements of the field. type E : ElementStore; /// The next largest natural storage class, eg if E is u8, then EE /// should be U16. Used for: /// /// * storing/returning field polynomial, which is always larger /// than the largest field element /// /// * storing the result of a non-modular (overflowing) multiply /// of two field elements type EE : ElementStore; /// The field polynomial with (implicit) high bit stripped off. fn poly(&self) -> Self::E; /// Field polynomial in full fn full_poly(&self) -> Self::EE; /// These will become associated constants fn high_bit() -> Self::E; fn order() -> u16; fn field_mask() -> Self::E; fn add(&self, a : Self::E, b : Self::E) -> Self::E { a ^ b } // upgrade storage class to prevent overflow // fn mul_no_mod(&self, a : Self::E, b : Self::E) // -> Self::EE // { // // implement straight, non-modular addition // 6u8.into() // } fn mul(&self, mut a : Self::E, b : Self::E) -> Self::E { let poly = self.poly(); // let zero : Self::E = num::NumCast::from(0).unwrap(); let zero : Self::E = num::zero(); let one : Self::E = num::one(); // let one = Self::E::one(); let field_mask : Self::E = Self::field_mask(); let high_bit : Self::E = Self::high_bit(); let mut result : Self::E = if b & one != zero {a} else { zero }; let mut bit : Self::E = one + one; loop { if a & high_bit != zero { // need to apply mask for GF(16) a = ((a << 1) ^ poly) & field_mask; } else { // no mask here, as it can't overflow a = a << 1 } if b & bit != zero { result = result ^ a } bit = bit << 1; // // eprintln!("a: {}, b: {}, bit: {}, result: {}", // // a,b,bit,result); if bit & field_mask == zero { return result } } // unreachable!() } fn div(&self, a : Self::E, b : Self::E) -> Self::E { self.mul(a, self.inv(b)) } fn inv(&self, a : Self::E) -> Self::E { let (zero, one) = (Self::E::zero(), Self::E::one()); let mut u : Self::E = self.poly(); let mut v : Self::E = a; let mut z : Self::E = zero; let mut g : Self::E = one; let mut t : Self::E; // always set before being used // special cases of 1/1 and 1/0 if a == zero || a == one { return a } // unroll first loop iteration (knowing initial i >= 0) // rustc can't determine that i is always positive here, // though, so we have to try_into() let mut i : u32 = 1 + v.leading_zeros(); u = u ^ v << i as usize; z = z ^ g << i as usize; while u != one { // in C: i=size_in_bits(u) - size_in_bits(v) // size_in_bits is order - leading zeroes // so we get i = (order - clz(u)) - (order - clz(v)) // the order cancels and we get: // i = clz(v) - clz(u) // further changed this to make i unsigned always // i = v.leading_zeros() - u.leading_zeros(); if u.leading_zeros() > v.leading_zeros() { t=u; u=v; v=t; t=z; z=g; g=t; // i = u.leading_zeros() - v.leading_zeros(); } else { // i = v.leading_zeros() - u.leading_zeros(); } i = v.leading_zeros() - u.leading_zeros(); u = u ^ v << i as usize; z = z ^ g << i as usize; } z } fn pow(&self, a : Self::E, b : Self::EE) -> Self::E { let mut result : Self::E = a; let zero : Self::EE = num::zero(); let one : Self::E = num::one(); let mut mask : Self::EE; // identity below only works on field if b == num::zero() // || b == self.field_mask() { return one } // shift mask right if there are leading zeros // fixup for GF(16) to ignore unused top nibble // Since we have mask : P, subtract any extra leading 0 // want to move mask right so that it coincides with // highest bit of b. This alternative way works: let clz = b.leading_zeros() as usize; let bits = zero.leading_zeros() as usize; // mask = Self::EE::one() << (bits - clz - 1); loop { mask = mask >> 1; if mask == zero { break } result = self.mul(result, result); if b & mask != zero { result = self.mul(result, a) } } result } } struct F8; #[cfg(test)] mod tests { #[test] fn it_works() { assert_eq!(2 + 2, 4); } }