1use super::{Felt, STATE_WIDTH, ZERO};
  2
  3mod freq;
  4pub use freq::mds_multiply_freq;
  5
  6// MDS MULTIPLICATION
  7// ================================================================================================
  8
  9#[inline(always)]
 10pub fn apply_mds(state: &mut [Felt; STATE_WIDTH]) {
 11    let mut result = [ZERO; STATE_WIDTH];
 12
 13    // Using the linearity of the operations we can split the state into a low||high decomposition
 14    // and operate on each with no overflow and then combine/reduce the result to a field element.
 15    // The no overflow is guaranteed by the fact that the MDS matrix is a small powers of two in
 16    // frequency domain.
 17    let mut state_l = [0u64; STATE_WIDTH];
 18    let mut state_h = [0u64; STATE_WIDTH];
 19
 20    for r in 0..STATE_WIDTH {
 21        let s = state[r].inner();
 22        state_h[r] = s >> 32;
 23        state_l[r] = (s as u32) as u64;
 24    }
 25
 26    let state_h = mds_multiply_freq(state_h);
 27    let state_l = mds_multiply_freq(state_l);
 28
 29    for r in 0..STATE_WIDTH {
 30        let s = state_l[r] as u128 + ((state_h[r] as u128) << 32);
 31        let s_hi = (s >> 64) as u64;
 32        let s_lo = s as u64;
 33        let z = (s_hi << 32) - s_hi;
 34        let (res, over) = s_lo.overflowing_add(z);
 35
 36        result[r] = Felt::from_mont(res.wrapping_add(0u32.wrapping_sub(over as u32) as u64));
 37    }
 38    *state = result;
 39}
 40
 41// MDS MATRIX
 42// ================================================================================================
 43
 44/// RPO MDS matrix
 45pub const MDS: [[Felt; STATE_WIDTH]; STATE_WIDTH] = [
 46    [
 47        Felt::new(7),
 48        Felt::new(23),
 49        Felt::new(8),
 50        Felt::new(26),
 51        Felt::new(13),
 52        Felt::new(10),
 53        Felt::new(9),
 54        Felt::new(7),
 55        Felt::new(6),
 56        Felt::new(22),
 57        Felt::new(21),
 58        Felt::new(8),
 59    ],
 60    [
 61        Felt::new(8),
 62        Felt::new(7),
 63        Felt::new(23),
 64        Felt::new(8),
 65        Felt::new(26),
 66        Felt::new(13),
 67        Felt::new(10),
 68        Felt::new(9),
 69        Felt::new(7),
 70        Felt::new(6),
 71        Felt::new(22),
 72        Felt::new(21),
 73    ],
 74    [
 75        Felt::new(21),
 76        Felt::new(8),
 77        Felt::new(7),
 78        Felt::new(23),
 79        Felt::new(8),
 80        Felt::new(26),
 81        Felt::new(13),
 82        Felt::new(10),
 83        Felt::new(9),
 84        Felt::new(7),
 85        Felt::new(6),
 86        Felt::new(22),
 87    ],
 88    [
 89        Felt::new(22),
 90        Felt::new(21),
 91        Felt::new(8),
 92        Felt::new(7),
 93        Felt::new(23),
 94        Felt::new(8),
 95        Felt::new(26),
 96        Felt::new(13),
 97        Felt::new(10),
 98        Felt::new(9),
 99        Felt::new(7),
100        Felt::new(6),
101    ],
102    [
103        Felt::new(6),
104        Felt::new(22),
105        Felt::new(21),
106        Felt::new(8),
107        Felt::new(7),
108        Felt::new(23),
109        Felt::new(8),
110        Felt::new(26),
111        Felt::new(13),
112        Felt::new(10),
113        Felt::new(9),
114        Felt::new(7),
115    ],
116    [
117        Felt::new(7),
118        Felt::new(6),
119        Felt::new(22),
120        Felt::new(21),
121        Felt::new(8),
122        Felt::new(7),
123        Felt::new(23),
124        Felt::new(8),
125        Felt::new(26),
126        Felt::new(13),
127        Felt::new(10),
128        Felt::new(9),
129    ],
130    [
131        Felt::new(9),
132        Felt::new(7),
133        Felt::new(6),
134        Felt::new(22),
135        Felt::new(21),
136        Felt::new(8),
137        Felt::new(7),
138        Felt::new(23),
139        Felt::new(8),
140        Felt::new(26),
141        Felt::new(13),
142        Felt::new(10),
143    ],
144    [
145        Felt::new(10),
146        Felt::new(9),
147        Felt::new(7),
148        Felt::new(6),
149        Felt::new(22),
150        Felt::new(21),
151        Felt::new(8),
152        Felt::new(7),
153        Felt::new(23),
154        Felt::new(8),
155        Felt::new(26),
156        Felt::new(13),
157    ],
158    [
159        Felt::new(13),
160        Felt::new(10),
161        Felt::new(9),
162        Felt::new(7),
163        Felt::new(6),
164        Felt::new(22),
165        Felt::new(21),
166        Felt::new(8),
167        Felt::new(7),
168        Felt::new(23),
169        Felt::new(8),
170        Felt::new(26),
171    ],
172    [
173        Felt::new(26),
174        Felt::new(13),
175        Felt::new(10),
176        Felt::new(9),
177        Felt::new(7),
178        Felt::new(6),
179        Felt::new(22),
180        Felt::new(21),
181        Felt::new(8),
182        Felt::new(7),
183        Felt::new(23),
184        Felt::new(8),
185    ],
186    [
187        Felt::new(8),
188        Felt::new(26),
189        Felt::new(13),
190        Felt::new(10),
191        Felt::new(9),
192        Felt::new(7),
193        Felt::new(6),
194        Felt::new(22),
195        Felt::new(21),
196        Felt::new(8),
197        Felt::new(7),
198        Felt::new(23),
199    ],
200    [
201        Felt::new(23),
202        Felt::new(8),
203        Felt::new(26),
204        Felt::new(13),
205        Felt::new(10),
206        Felt::new(9),
207        Felt::new(7),
208        Felt::new(6),
209        Felt::new(22),
210        Felt::new(21),
211        Felt::new(8),
212        Felt::new(7),
213    ],
214];