sp1_core_machine/alu/sll/
mod.rs

1use core::{
2    borrow::{Borrow, BorrowMut},
3    mem::{size_of, MaybeUninit},
4};
5use std::marker::PhantomData;
6
7use hashbrown::HashMap;
8use itertools::Itertools;
9use slop_air::{Air, AirBuilder, BaseAir};
10use slop_algebra::{AbstractField, Field, PrimeField, PrimeField32};
11use slop_matrix::Matrix;
12use slop_maybe_rayon::prelude::{ParallelBridge, ParallelIterator, ParallelSlice};
13use sp1_core_executor::{
14    events::{AluEvent, ByteLookupEvent, ByteRecord},
15    ALUTypeRecord, ByteOpcode, ExecutionRecord, Opcode, Program, CLK_INC, PC_INC,
16};
17use sp1_derive::AlignedBorrow;
18use sp1_hypercube::{air::MachineAir, Word};
19use sp1_primitives::consts::{u32_to_u16_limbs, u64_to_u16_limbs, WORD_SIZE};
20use struct_reflection::{StructReflection, StructReflectionHelper};
21
22use crate::{
23    adapter::{
24        register::alu_type::{ALUTypeReader, ALUTypeReaderInput},
25        state::{CPUState, CPUStateInput},
26    },
27    air::{SP1CoreAirBuilder, SP1Operation},
28    eval_untrusted_program,
29    operations::{U16MSBOperation, U16MSBOperationInput},
30    utils::next_multiple_of_32,
31    SupervisorMode, TrustMode, UserMode,
32};
33
34/// The number of main trace columns for `ShiftLeft` in Supervisor mode.
35pub const NUM_SHIFT_LEFT_COLS_SUPERVISOR: usize = size_of::<ShiftLeftCols<u8, SupervisorMode>>();
36/// The number of main trace columns for `ShiftLeft` in User mode.
37pub const NUM_SHIFT_LEFT_COLS_USER: usize = size_of::<ShiftLeftCols<u8, UserMode>>();
38
39/// The number of bits in a byte.
40pub const BYTE_SIZE: usize = 8;
41
42/// A chip that implements bitwise operations for the opcodes SLL and SLLI.
43#[derive(Default)]
44pub struct ShiftLeftChip<M: TrustMode> {
45    pub _phantom: PhantomData<M>,
46}
47
48/// The column layout for the chip.
49#[derive(AlignedBorrow, StructReflection, Default, Debug, Clone, Copy)]
50#[repr(C)]
51pub struct ShiftLeftCols<T, M: TrustMode> {
52    /// The current shard, timestamp, program counter of the CPU.
53    pub state: CPUState<T>,
54
55    /// The adapter to read program and register information.
56    pub adapter: ALUTypeReader<T>,
57
58    /// The output operand.
59    pub a: Word<T>,
60
61    /// The lowerst byte of `c`.
62    pub c_bits: [T; 6],
63
64    /// v01 = (c0 + 1) * (3c1 + 1)
65    pub v_01: T,
66
67    /// v012 = (c0 + 1) * (3c1 + 1) * (15c2 + 1)
68    pub v_012: T,
69
70    /// v012 * c3
71    pub v_0123: T,
72
73    /// Flags representing c4 + 2c5.
74    pub shift_u16: [T; 4],
75
76    /// The lower bits of each limb.
77    pub lower_limb: Word<T>,
78
79    /// The higher bits of each limb.
80    pub higher_limb: Word<T>,
81
82    /// The limb results.
83    pub limb_result: Word<T>,
84
85    /// The most significant byte of the result of SLLW.
86    pub sllw_msb: U16MSBOperation<T>,
87
88    /// If the opcode is SLL.
89    pub is_sll: T,
90
91    /// If the opcode is SLLW.
92    pub is_sllw: T,
93
94    /// If the opcode is SLLW and immediate.
95    pub is_sllw_imm: T,
96
97    /// Adapter columns for trust mode specific data.
98    pub adapter_cols: M::AdapterCols<T>,
99}
100
101impl<F: PrimeField32, M: TrustMode> MachineAir<F> for ShiftLeftChip<M> {
102    type Record = ExecutionRecord;
103
104    type Program = Program;
105
106    fn name(&self) -> &'static str {
107        if M::IS_TRUSTED {
108            "ShiftLeft"
109        } else {
110            "ShiftLeftUser"
111        }
112    }
113
114    fn column_names(&self) -> Vec<String> {
115        ShiftLeftCols::<F, M>::struct_reflection().unwrap()
116    }
117
118    fn num_rows(&self, input: &Self::Record) -> Option<usize> {
119        if input.program.enable_untrusted_programs == M::IS_TRUSTED {
120            return Some(0);
121        }
122        let nb_rows =
123            next_multiple_of_32(input.shift_left_events.len(), input.fixed_log2_rows::<F, _>(self));
124        Some(nb_rows)
125    }
126
127    fn generate_trace_into(
128        &self,
129        input: &ExecutionRecord,
130        _output: &mut ExecutionRecord,
131        buffer: &mut [MaybeUninit<F>],
132    ) {
133        if input.program.enable_untrusted_programs == M::IS_TRUSTED {
134            return;
135        }
136
137        // Generate the trace rows for each event.
138        let padded_nb_rows = <ShiftLeftChip<M> as MachineAir<F>>::num_rows(self, input).unwrap();
139        let nb_rows = input.shift_left_events.len();
140        let chunk_size = std::cmp::max((padded_nb_rows + 1) / num_cpus::get(), 1);
141        let width = <ShiftLeftChip<M> as BaseAir<F>>::width(self);
142
143        unsafe {
144            let padding_start = nb_rows * width;
145            let padding_size = (padded_nb_rows - nb_rows) * width;
146            if padding_size > 0 {
147                core::ptr::write_bytes(buffer[padding_start..].as_mut_ptr(), 0, padding_size);
148            }
149        }
150
151        let buffer_ptr = buffer.as_mut_ptr() as *mut F;
152        let values = unsafe { core::slice::from_raw_parts_mut(buffer_ptr, padded_nb_rows * width) };
153
154        let padded_row_template = {
155            let mut row = vec![F::zero(); width];
156            let cols: &mut ShiftLeftCols<F, M> = row.as_mut_slice().borrow_mut();
157            cols.v_01 = F::one();
158            cols.v_012 = F::one();
159            cols.v_0123 = F::one();
160            row
161        };
162
163        values.chunks_mut(chunk_size * width).enumerate().par_bridge().for_each(|(i, rows)| {
164            rows.chunks_mut(width).enumerate().for_each(|(j, row)| {
165                let idx = i * chunk_size + j;
166                let cols: &mut ShiftLeftCols<F, M> = row.borrow_mut();
167
168                if idx < nb_rows {
169                    let mut blu = Vec::new();
170                    let event = &input.shift_left_events[idx];
171                    cols.adapter.populate(&mut blu, event.1);
172                    self.event_to_row(&event.0, &event.1, cols, &mut blu);
173                    cols.state.populate(&mut blu, event.0.clk, event.0.pc);
174                    if !M::IS_TRUSTED {
175                        let cols: &mut ShiftLeftCols<F, UserMode> = row.borrow_mut();
176                        cols.adapter_cols.is_trusted = F::from_bool(!event.1.is_untrusted);
177                    }
178                } else {
179                    row.copy_from_slice(&padded_row_template);
180                }
181            });
182        });
183    }
184
185    fn generate_dependencies(&self, input: &Self::Record, output: &mut Self::Record) {
186        if input.program.enable_untrusted_programs == M::IS_TRUSTED {
187            return;
188        }
189
190        let chunk_size = std::cmp::max(input.shift_left_events.len() / num_cpus::get(), 1);
191        let width = <ShiftLeftChip<M> as BaseAir<F>>::width(self);
192
193        let blu_batches = input
194            .shift_left_events
195            .par_chunks(chunk_size)
196            .map(|events| {
197                let mut blu: HashMap<ByteLookupEvent, usize> = HashMap::new();
198                events.iter().for_each(|event| {
199                    let mut row = vec![F::zero(); width];
200                    let cols: &mut ShiftLeftCols<F, M> = row.as_mut_slice().borrow_mut();
201                    cols.adapter.populate(&mut blu, event.1);
202                    self.event_to_row(&event.0, &event.1, cols, &mut blu);
203                    cols.state.populate(&mut blu, event.0.clk, event.0.pc);
204                });
205                blu
206            })
207            .collect::<Vec<_>>();
208
209        output.add_byte_lookup_events_from_maps(blu_batches.iter().collect_vec());
210    }
211
212    fn included(&self, shard: &Self::Record) -> bool {
213        if let Some(shape) = shard.shape.as_ref() {
214            shape.included::<F, _>(self)
215        } else {
216            !shard.shift_left_events.is_empty()
217                && (M::IS_TRUSTED != shard.program.enable_untrusted_programs)
218        }
219    }
220}
221
222impl<M: TrustMode> ShiftLeftChip<M> {
223    /// Create a row from an event.
224    fn event_to_row<F: PrimeField>(
225        &self,
226        event: &AluEvent,
227        record: &ALUTypeRecord,
228        cols: &mut ShiftLeftCols<F, M>,
229        blu: &mut impl ByteRecord,
230    ) {
231        let c = u64_to_u16_limbs(event.c)[0];
232
233        if event.opcode == Opcode::SLLW {
234            let sllw_val = ((event.b as i64) << (c & 0x1f)) as u32;
235            let sllw_limbs = u32_to_u16_limbs(sllw_val);
236            cols.sllw_msb.populate_msb(blu, sllw_limbs[1]);
237        } else {
238            cols.sllw_msb.msb = F::zero();
239        }
240
241        cols.a = Word::from(event.a);
242        let is_sll = event.opcode == Opcode::SLL;
243        cols.is_sll = F::from_bool(is_sll);
244
245        cols.is_sllw = F::from_bool(event.opcode == Opcode::SLLW);
246        cols.is_sllw_imm = F::from_bool(event.opcode == Opcode::SLLW && record.is_imm);
247
248        for i in 0..6 {
249            cols.c_bits[i] = F::from_canonical_u16((c >> i) & 1);
250        }
251        blu.add_bit_range_check(c >> 6, 10);
252
253        cols.v_01 = F::from_canonical_u16(1 << (c & 3));
254        cols.v_012 = F::from_canonical_u16(1 << (c & 7));
255        cols.v_0123 = F::from_canonical_u16(1 << (c & 15));
256
257        let shift_amount = ((c >> 4) & 1) + 2 * ((c >> 5) & 1) * (is_sll as u16);
258
259        let mut shift = [0u16; 4];
260        for i in 0..4 {
261            if i == shift_amount as usize {
262                shift[i] = 1;
263            }
264        }
265
266        let b = u64_to_u16_limbs(event.b);
267        let bit_shift = (c & 0xF) as u8;
268        for i in 0..WORD_SIZE {
269            let limb = b[i] as u32;
270            let lower_limb = (limb & ((1 << (16 - bit_shift)) - 1)) as u16;
271            let higher_limb = (limb >> (16 - bit_shift)) as u16;
272            cols.lower_limb[i] = F::from_canonical_u16(lower_limb);
273            cols.higher_limb[i] = F::from_canonical_u16(higher_limb);
274            blu.add_bit_range_check(lower_limb, 16 - bit_shift);
275            blu.add_bit_range_check(higher_limb, bit_shift);
276        }
277
278        for i in 0..WORD_SIZE {
279            cols.limb_result[i] = cols.lower_limb[i] * F::from_canonical_u32(1u32 << bit_shift);
280            if i != 0 {
281                cols.limb_result[i] += cols.higher_limb[i - 1];
282            }
283        }
284
285        cols.shift_u16 = shift.map(|x| F::from_canonical_u16(x));
286    }
287}
288
289impl<F, M: TrustMode> BaseAir<F> for ShiftLeftChip<M> {
290    fn width(&self) -> usize {
291        if M::IS_TRUSTED {
292            NUM_SHIFT_LEFT_COLS_SUPERVISOR
293        } else {
294            NUM_SHIFT_LEFT_COLS_USER
295        }
296    }
297}
298
299impl<AB, M> Air<AB> for ShiftLeftChip<M>
300where
301    AB: SP1CoreAirBuilder,
302    M: TrustMode,
303{
304    fn eval(&self, builder: &mut AB) {
305        let main = builder.main();
306        let local = main.row_slice(0);
307        let local: &ShiftLeftCols<AB::Var, M> = (*local).borrow();
308
309        // SAFETY: All selectors `is_sll`, `is_sllw` are checked to be boolean.
310        // Each "real" row has exactly one selector turned on, as `is_real = is_sll + is_sllw` is
311        // boolean. All interactions are done with multiplicity `is_real`.
312        // Therefore, the `opcode` matches the corresponding opcode.
313        let is_real = local.is_sll + local.is_sllw;
314        builder.assert_bool(is_real.clone());
315        builder.assert_bool(local.is_sll);
316        builder.assert_bool(local.is_sllw);
317
318        // Check that `local.c_bits` are the 6 lowest bits of `c`.
319        for i in 0..6 {
320            builder.assert_bool(local.c_bits[i]);
321        }
322        let mut c_lower_bits = AB::Expr::zero();
323        let mut bit_shift = AB::Expr::zero();
324        for i in 0..6 {
325            c_lower_bits = c_lower_bits + local.c_bits[i] * AB::F::from_canonical_u32(1 << i);
326            if i == 3 {
327                bit_shift = c_lower_bits.clone();
328            }
329        }
330        let inverse_64 = AB::F::from_canonical_u32(64).inverse();
331        builder.send_byte(
332            AB::F::from_canonical_u32(ByteOpcode::Range as u32),
333            (local.adapter.c()[0] - c_lower_bits) * inverse_64,
334            AB::Expr::from_canonical_u32(10),
335            AB::Expr::zero(),
336            is_real.clone(),
337        );
338
339        // Check that `shift_u16` represents the boolean flag for the u16 limb shifts.
340        for i in 0..WORD_SIZE {
341            builder.when(local.shift_u16[i]).assert_eq(
342                local.c_bits[4] + local.c_bits[5] * AB::F::from_canonical_u32(2) * local.is_sll,
343                AB::Expr::from_canonical_u32(i as u32),
344            );
345            builder.assert_bool(local.shift_u16[i]);
346        }
347
348        builder.when(is_real.clone()).assert_eq(
349            local.shift_u16[0] + local.shift_u16[1] + local.shift_u16[2] + local.shift_u16[3],
350            AB::Expr::from_canonical_u32(1),
351        );
352
353        let one = AB::F::from_canonical_u32(1);
354        let three = AB::F::from_canonical_u32(3);
355        let fifteen = AB::F::from_canonical_u32(15);
356        let two_fifty_five = AB::F::from_canonical_u32(255);
357        builder.assert_eq(local.v_01, (local.c_bits[0] + one) * (local.c_bits[1] * three + one));
358        builder.assert_eq(local.v_012, local.v_01 * (local.c_bits[2] * fifteen + one));
359        builder.assert_eq(local.v_0123, local.v_012 * (local.c_bits[3] * two_fifty_five + one));
360
361        for i in 0..WORD_SIZE {
362            let limb = local.adapter.b()[i];
363            // Check that `lower_limb < 2^(16 - bit_shift)`
364            builder.send_byte(
365                AB::F::from_canonical_u32(ByteOpcode::Range as u32),
366                local.lower_limb[i],
367                AB::Expr::from_canonical_u32(16) - bit_shift.clone(),
368                AB::Expr::zero(),
369                is_real.clone(),
370            );
371            // Check that `higher_limb < 2^(bit_shift)`
372            builder.send_byte(
373                AB::F::from_canonical_u32(ByteOpcode::Range as u32),
374                local.higher_limb[i],
375                bit_shift.clone(),
376                AB::Expr::zero(),
377                is_real.clone(),
378            );
379            // Check that `limb == higher_limb * 2^(16 - bit_shift) + lower_limb`
380            // Multiply `2^(bit_shift)` to the equation to avoid populating `2^(16 - bit_shift)`.
381            // This is possible, since `2^(bit_shift)` is not zero.
382            builder.assert_eq(
383                limb * local.v_0123,
384                local.higher_limb[i] * AB::Expr::from_canonical_u32(1 << 16)
385                    + local.lower_limb[i] * local.v_0123,
386            );
387        }
388
389        // Compute the limb result based on the lower limbs and higher limbs.
390        for i in 0..WORD_SIZE {
391            let mut limb_result = local.lower_limb[i] * local.v_0123;
392            if i != 0 {
393                limb_result = limb_result.clone() + local.higher_limb[i - 1];
394            }
395            builder.assert_eq(local.limb_result[i], limb_result);
396        }
397
398        // Perform the limb shifts based on `shift_u16` boolean flags.
399        for i in 0..WORD_SIZE {
400            for j in 0..WORD_SIZE {
401                if j < i {
402                    builder.when(local.is_sll).when(local.shift_u16[i]).assert_zero(local.a[j]);
403                } else {
404                    builder
405                        .when(local.is_sll)
406                        .when(local.shift_u16[i])
407                        .assert_eq(local.a[j], local.limb_result[j - i]);
408                }
409            }
410        }
411
412        for i in 0..WORD_SIZE / 2 {
413            for j in 0..WORD_SIZE / 2 {
414                if j < i {
415                    builder.when(local.is_sllw).when(local.shift_u16[i]).assert_zero(local.a[j]);
416                } else {
417                    builder
418                        .when(local.is_sllw)
419                        .when(local.shift_u16[i])
420                        .assert_eq(local.a[j], local.limb_result[j - i]);
421                }
422            }
423        }
424        let u16_max = AB::F::from_canonical_u16(u16::MAX);
425        for i in WORD_SIZE / 2..WORD_SIZE {
426            builder.when(local.is_sllw).assert_eq(local.sllw_msb.msb * u16_max, local.a[i]);
427        }
428
429        U16MSBOperation::<AB::F>::eval(
430            builder,
431            U16MSBOperationInput::new(local.a[1].into(), local.sllw_msb, local.is_sllw.into()),
432        );
433
434        let opcode = local.is_sll * AB::F::from_canonical_u32(Opcode::SLL as u32)
435            + local.is_sllw * AB::F::from_canonical_u32(Opcode::SLLW as u32);
436
437        // Compute instruction field constants for each opcode
438        let funct3 = local.is_sll * AB::Expr::from_canonical_u8(Opcode::SLL.funct3().unwrap())
439            + local.is_sllw * AB::Expr::from_canonical_u8(Opcode::SLLW.funct3().unwrap());
440        let funct7 = local.is_sll * AB::Expr::from_canonical_u8(Opcode::SLL.funct7().unwrap_or(0))
441            + local.is_sllw * AB::Expr::from_canonical_u8(Opcode::SLLW.funct7().unwrap_or(0));
442
443        let (sll_base, sll_imm) = Opcode::SLL.base_opcode();
444        let sll_imm = sll_imm.expect("SLL immediate opcode not found");
445        let (sllw_base, sllw_imm) = Opcode::SLLW.base_opcode();
446        let sllw_imm = sllw_imm.expect("SLLW immediate opcode not found");
447
448        let imm_base_difference = sll_base.checked_sub(sll_imm).unwrap();
449        assert!(imm_base_difference == sllw_base.checked_sub(sllw_imm).unwrap());
450
451        let sll_base_expr = AB::Expr::from_canonical_u32(sll_base);
452        let sllw_base_expr = AB::Expr::from_canonical_u32(sllw_base);
453
454        // Start with register opcode, if it's immediate, subtract the difference
455        let calculated_base_opcode = local.is_sll * sll_base_expr + local.is_sllw * sllw_base_expr
456            - AB::Expr::from_canonical_u32(imm_base_difference) * local.adapter.imm_c;
457
458        let sll_instr_type = Opcode::SLL.instruction_type().0 as u32;
459        let sll_instr_type_imm =
460            Opcode::SLL.instruction_type().1.expect("SLL immediate instruction type not found")
461                as u32;
462        let sllw_instr_type = Opcode::SLLW.instruction_type().0 as u32;
463        let sllw_instr_type_imm =
464            Opcode::SLLW.instruction_type().1.expect("SLLW immediate instruction type not found")
465                as u32;
466
467        let instr_type_difference = sll_instr_type.checked_sub(sll_instr_type_imm).unwrap();
468        let w_instr_imm_adjustment = sll_instr_type_imm.checked_sub(sllw_instr_type_imm).unwrap();
469        assert_eq!(
470            sllw_instr_type.checked_sub(sllw_instr_type_imm).unwrap(),
471            instr_type_difference + w_instr_imm_adjustment,
472        );
473
474        builder.assert_eq(local.is_sllw_imm, local.is_sllw * local.adapter.imm_c);
475
476        let calculated_instr_type = local.is_sll * AB::Expr::from_canonical_u32(sll_instr_type)
477            + local.is_sllw * AB::Expr::from_canonical_u32(sllw_instr_type)
478            - (AB::Expr::from_canonical_u32(instr_type_difference) * local.adapter.imm_c
479                + AB::Expr::from_canonical_u32(w_instr_imm_adjustment) * local.is_sllw_imm);
480
481        // Constrain the CPU state.
482        // The program counter and timestamp increment by `4` and `8`.
483        <CPUState<AB::F> as SP1Operation<AB>>::eval(
484            builder,
485            CPUStateInput::new(
486                local.state,
487                [
488                    local.state.pc[0] + AB::F::from_canonical_u32(PC_INC),
489                    local.state.pc[1].into(),
490                    local.state.pc[2].into(),
491                ],
492                AB::Expr::from_canonical_u32(CLK_INC),
493                is_real.clone(),
494            ),
495        );
496
497        let mut is_trusted: AB::Expr = is_real.clone();
498
499        #[cfg(feature = "mprotect")]
500        builder.assert_eq(
501            builder.extract_public_values().is_untrusted_programs_enabled,
502            AB::Expr::from_bool(!M::IS_TRUSTED),
503        );
504
505        if !M::IS_TRUSTED {
506            let local = main.row_slice(0);
507            let local: &ShiftLeftCols<AB::Var, UserMode> = (*local).borrow();
508
509            let instruction = local.adapter.instruction::<AB>(opcode.clone());
510
511            #[cfg(not(feature = "mprotect"))]
512            builder.assert_zero(is_real.clone());
513
514            eval_untrusted_program(
515                builder,
516                local.state.pc,
517                instruction,
518                [calculated_instr_type, calculated_base_opcode, funct3, funct7],
519                [local.state.clk_high::<AB>(), local.state.clk_low::<AB>()],
520                is_real.clone(),
521                local.adapter_cols,
522            );
523
524            is_trusted = local.adapter_cols.is_trusted.into();
525        }
526
527        // This chip is for the case `rd != x0`.
528        builder.assert_zero(local.adapter.op_a_0);
529
530        // Constrain the program and register reads.
531        let alu_reader_input = ALUTypeReaderInput::<AB, AB::Expr>::new(
532            local.state.clk_high::<AB>(),
533            local.state.clk_low::<AB>(),
534            local.state.pc,
535            opcode,
536            local.a.map(|x| x.into()),
537            local.adapter,
538            is_real.clone(),
539            is_trusted,
540        );
541        ALUTypeReader::<AB::F>::eval(builder, alu_reader_input);
542    }
543}
544
545//     use std::borrow::BorrowMut;
546
547//     use crate::{
548//         alu::ShiftLeftCols,
549//         io::SP1Stdin,
550//         riscv::RiscvAir,
551//         utils::{run_malicious_test, run_test_machine, setup_test_machine},
552//     };
553//     use sp1_primitives::SP1Field;
554//     use slop_matrix::dense::RowMajorMatrix;
555//     use rand::{thread_rng, Rng};
556//     use sp1_core_executor::{
557//         events::{AluEvent, MemoryRecordEnum},
558//         ExecutionRecord, Instruction, Opcode, Program,
559//     };
560//     use sp1_hypercube::{
561//         air::{MachineAir, SP1_PROOF_NUM_PV_ELTS},
562//         koala_bear_poseidon2::SP1InnerPcs,
563//         chip_name, Chip, CpuProver, MachineProver, StarkMachine, Val,
564//     };
565
566//     use super::ShiftLeft;
567
568//     #[test]
569//     fn generate_trace() {
570//         let mut shard = ExecutionRecord::default();
571//         shard.shift_left_events = vec![AluEvent::new(0, Opcode::SLL, 16, 8, 1, false)];
572//         let chip = ShiftLeft::default();
573//         let trace: RowMajorMatrix<SP1Field> =
574//             chip.generate_trace(&shard, &mut ExecutionRecord::default());
575//         println!("{:?}", trace.values)
576//     }
577
578//     #[test]
579//     fn prove_koalabear() {
580//         let mut shift_events: Vec<AluEvent> = Vec::new();
581//         let shift_instructions: Vec<(Opcode, u32, u32, u32)> = vec![
582//             (Opcode::SLL, 0x00000002, 0x00000001, 1),
583//             (Opcode::SLL, 0x00000080, 0x00000001, 7),
584//             (Opcode::SLL, 0x00004000, 0x00000001, 14),
585//             (Opcode::SLL, 0x80000000, 0x00000001, 31),
586//             (Opcode::SLL, 0xffffffff, 0xffffffff, 0),
587//             (Opcode::SLL, 0xfffffffe, 0xffffffff, 1),
588//             (Opcode::SLL, 0xffffff80, 0xffffffff, 7),
589//             (Opcode::SLL, 0xffffc000, 0xffffffff, 14),
590//             (Opcode::SLL, 0x80000000, 0xffffffff, 31),
591//             (Opcode::SLL, 0x21212121, 0x21212121, 0),
592//             (Opcode::SLL, 0x42424242, 0x21212121, 1),
593//             (Opcode::SLL, 0x90909080, 0x21212121, 7),
594//             (Opcode::SLL, 0x48484000, 0x21212121, 14),
595//             (Opcode::SLL, 0x80000000, 0x21212121, 31),
596//             (Opcode::SLL, 0x21212121, 0x21212121, 0xffffffe0),
597//             (Opcode::SLL, 0x42424242, 0x21212121, 0xffffffe1),
598//             (Opcode::SLL, 0x90909080, 0x21212121, 0xffffffe7),
599//             (Opcode::SLL, 0x48484000, 0x21212121, 0xffffffee),
600//             (Opcode::SLL, 0x00000000, 0x21212120, 0xffffffff),
601//         ];
602//         for t in shift_instructions.iter() {
603//             shift_events.push(AluEvent::new(0, t.0, t.1, t.2, t.3, false));
604//         }
605
606//         // Append more events until we have 1000 tests.
607//         for _ in 0..(1000 - shift_instructions.len()) {
608//             //shift_events.push(AluEvent::new(0, 0, Opcode::SLL, 14, 8, 6));
609//         }
610
611//         let mut shard = ExecutionRecord::default();
612//         shard.shift_left_events = shift_events;
613
614//         // Run setup.
615//         let air = ShiftLeft::default();
616//         let config = SP1InnerPcs::new();
617//         let chip = Chip::new(air);
618//         let (pk, vk) = setup_test_machine(StarkMachine::new(
619//             config.clone(),
620//             vec![chip],
621//             SP1_PROOF_NUM_PV_ELTS,
622//             true,
623//         ));
624
625//         // Run the test.
626//         let air = ShiftLeft::default();
627//         let chip: Chip<SP1Field, ShiftLeft> = Chip::new(air);
628//         let machine = StarkMachine::new(config.clone(), vec![chip], SP1_PROOF_NUM_PV_ELTS, true);
629//         run_test_machine::<SP1InnerPcs, ShiftLeft>(vec![shard], machine, pk,
630// vk).unwrap();     }
631
632//     #[test]
633//     fn test_malicious_sll() {
634//         const NUM_TESTS: usize = 5;
635
636//         for _ in 0..NUM_TESTS {
637//             let op_a = thread_rng().gen_range(0..u32::MAX);
638//             let op_b = thread_rng().gen_range(0..u32::MAX);
639//             let op_c = thread_rng().gen_range(0..u32::MAX);
640
641//             let correct_op_a = op_b << (op_c & 0x1F);
642
643//             assert!(op_a != correct_op_a);
644
645//             let instructions = vec![
646//                 Instruction::new(Opcode::SLL, 5, op_b, op_c, true, true),
647//                 Instruction::new(Opcode::ADD, 10, 0, 0, false, false),
648//             ];
649
650//             let program = Program::new(instructions, 0, 0);
651//             let stdin = SP1Stdin::new();
652
653//             type P = CpuProver<SP1InnerPcs, RiscvAir<SP1Field>>;
654
655//             let malicious_trace_pv_generator =
656//                 move |prover: &P,
657//                       record: &mut ExecutionRecord|
658//                       -> Vec<(String, RowMajorMatrix<Val<SP1InnerPcs>>)> {
659//                     let mut malicious_record = record.clone();
660//                     malicious_record.cpu_events[0].a = op_a as u32;
661//                     if let Some(MemoryRecordEnum::Write(mut write_record)) =
662//                         malicious_record.cpu_events[0].a_record
663//                     {
664//                         write_record.value = op_a as u32;
665//                     }
666//                     let mut traces = prover.generate_traces(&malicious_record);
667//                     let shift_left_chip_name = chip_name!(ShiftLeft, SP1Field);
668//                     for (name, trace) in traces.iter_mut() {
669//                         if *name == shift_left_chip_name {
670//                             let first_row = trace.row_mut(0);
671//                             let first_row: &mut ShiftLeftCols<SP1Field> = first_row.borrow_mut();
672//                             first_row.a = op_a.into();
673//                         }
674//                     }
675
676//                     traces
677//                 };
678
679//             let result =
680//                 run_malicious_test::<P>(program, stdin, Box::new(malicious_trace_pv_generator));
681//             assert!(result.is_err() && result.unwrap_err().is_constraints_failing());
682//         }
683//     }
684// }
sp1_core_machine/alu/sll/mod.rs

sp1_core_machine/alu/sll/
mod.rs
