Implement BigInt bit shifting using intrinsics over an array

Viewed 137

I'd like to implement bit shifting over a block of memory using SIMD. I have figured out this solution, that essentially follows these steps:

  • Byte shifts of shift / CHAR_BIT using memmove if the shift is greater than CHAR_BIT
  • Bit shifts iterating over each char of the memory block

This is essentially an O(n). I know I can just iterate over data types bigger than char, however I'm pretty sure this can be done even faster using intrinsics.

void rshift(void *self, int other, size_t size) {
    if (other < size * CHAR_BIT) {
        unsigned char *s = self,
                      *pass = calloc(2, sizeof(unsigned char));

        if (pass != NULL) {
            int chars = other / CHAR_BIT,
                bits = other % CHAR_BIT;

            if (chars > 0) {
                memmove(s + chars, s, size - chars);
                memset(s, 0, chars);
            }

            if (bits > 0) {
                for (size_t i = 0; i < size;
                     i++, pass[0] = pass[1] << (CHAR_BIT - bits)) {
                    pass[1] = s[i] & ((1 << bits) - 1);
                    s[i] = (s[i] >> bits) | pass[0];
                }
            }

            free(pass);
        }
    } else memset(self, 0, size);
}

I have tried taking a look at the different intrinsic operations, like _mm_srli_si128, that however byte shifts, doesn't bit shift.

Is there a way to implement the previous function using SIMD instructions?

0 Answers
Related