Parallel processing in Cairo with single instruction, multiple data (SIMD) operations

simd.cairo

//
// SIMD Operation for Bitwise Rotations of Seven UInt32 Values in Parallel
//

%builtins bitwise
from starkware.cairo.common.bitwise import BitwiseBuiltin


// How many bitwise steps do we want to rotate?
// 2**t expresses a rotation of t bits to the right.
// For a rotation to the left use `32-t`.
const SHIFT_t = 2**8;


// The size of the UInt32 space is 32 bits.
// The size of Cairo's native field is 251 bits. Floor(251/32) == 7
// so we can process up to 7 x 32 bits in a single field element in parallel.
const UINT32 = 2**32;


// We can have from zero up to three carry bits. So, from 32 to 35 bits per UInt32 in the vector.
// With 3 carry bits we can perform up to 2**3 = 8 additions without an overflow.
const CARRY = 2**0;
// const CARRY = 2**3

// The size of the vector's entries is 32 bits plus the carry bits
const BASE = UINT32 * CARRY;


// The unit vector = (1, 1, 1, 1, 1, 1, 1)
const VEC7_ONE = BASE**0 + BASE**1 + BASE**2 + BASE**3 + BASE**4 + BASE**5 + BASE**6;


// The bit mask to perform the rotation. 
// Returns all bits to be shifted to the right.
// Inverting this mask returns all the bits to be shifted to the left
const SHIFT_MASK = (UINT32 - SHIFT_t) * VEC7_ONE;


func main{bitwise_ptr: BitwiseBuiltin*}(){    
    // An input vector of the seven UInt32 values to be rotated
    let vec7_inputs = 0x11111122 * BASE**0 + 
                      0x33333344 * BASE**1 + 
                      0x55555566 * BASE**2 + 
                      0x77777788 * BASE**3 + 
                      0x999999aa * BASE**4 + 
                      0xbbbbbbcc * BASE**5 + 
                      0xddddddee * BASE**6;
    
    //
    // Rotate Right
    //
    
    // Apply the shift mask to the input vector
    assert bitwise_ptr.x = vec7_inputs;
    assert bitwise_ptr.y = SHIFT_MASK;
    
    // Rotate the vector's entries using the original vector and the masked vector
    tempvar vec7_rotated = vec7_inputs * UINT32 / SHIFT_t - bitwise_ptr.x_and_y * (UINT32-1) / SHIFT_t;
    
    // Boilerplate to "call" the low-level API of BitwiseBuiltin
    let bitwise_ptr = bitwise_ptr + BitwiseBuiltin.SIZE;


    // Format and print the result in Python
    %{ print( hex(ids.vec7_inputs) ) %}
    %{ print( hex(ids.vec7_rotated) ) %}
    return ();
}