Bit shift 256 bits

Question

I have a working solution to my problem, but I'm less than satisfied with the result, both when it comes to style and performance.

In short, I need to be able to shift 256 bits of data, say an array of 4 64 bit integer, by n bit, right and left. If other type are easier to work with for some reason, it's really all the same to me.

My current implementation, which seems to work:

void shl( uint64_t * const b, uint_fast8_t n )
{
    for( int i = 3-(n/64); i >= 0 && n >=64; --i )
        b[i+n/64] = b[i];
    for( int i = n/64-1; i >= 0; --i)
        b[i] = 0;
    for( int_fast8_t i = 3; i > 0 && (n%64); --i )
        b[i] = (b[i] << (n%64)) | (b[i-1] >> (64-(n%64)));
    b[0] <<= n%64;

}
void shr( uint64_t * const b, uint_fast8_t n )
{
    for( int i = 0; i < 4-(n/64) && n >=64; ++i )
        b[i] = b[i+n/64];
    for( int i = 4-n/64; i < 4; ++i )
        b[i] = 0;
    for( int i = 0; i < 3 && (n%64); ++i )
        b[i] = (b[i] >> (n%64)) | (b[i+1] << (64-(n%64)));
    b[3] >>= n%64;
}

I have no need for a general solution, and in case it matters, I need not shift more than 192 bits in a given direction.

Anyway, what I have made, is absolutely awful. I have been searching for alternatives, but what little I've found has been limited to work within the width of the chosen type, in this case 64, or it has simply not been working. I'm sure the above can be optimized, but frankly, I'd prefer a different solution all together.

My first thought was to mess around with pointers, but I have yet to come up with with how that would actually work, so I've got nothing.

I would very much appreciate any ideas.

Also, I did just find one mistake, which has been corrected, so there may be more.

Update: Another approach, that is really the same, though slightly more efficient:

void shl( uint64_t * const b, const uint_fast8_t n )
{
    // If n != 0, we run through the 4 elements descending.
    for( int i = 3; n && i >= 0; --i )
        // Do we need to assign current element a value?
        if( i >= n/64 )
        {
            b[i] = b[i - n/64] << ( n%64 );
            // Check to avoid OOB and special case where n is a multiple of 64.
            if( i > n/64 && n%64 )
                b[i] |= b[i - n/64 - 1] >> ( 64 - ( n%64 ) );
        }
        // if not, value should be zero.
        else b[i] = 0;
}

void shr( uint64_t * const b, const uint_fast8_t n )
{
    // If n != 0, we run through the 4 elements ascending.
    for( int i = 0; n && i < 4; ++i )
        // Do we need to assign current element a value?
        if( i < 4 - n/64 )
        {
            b[i] = b[i + n/64] >> ( n%64 );
            // Check to avoid OOB and special case where n is a multiple of 64.
            if( i < 4 - n/64 - 1 < 4 && n%64 )
                b[i] |= b[i + n/64 + 1] << ( 64 - ( n%64 ) );
        }
        // if not, value should be zero.
        else b[i] = 0;
}

It seems to work, and unlike the other version, I can live with this, but still, there must be another way.

Answer 1

Stylistic (not asked) the wording can be more to the point. Sometimes that gives an optimisation idea.

Much elegance one might not expect, shifting in arrays in C. But I did find a spot.

As such:

void shl(uint8_t * const words, uint_fast_t n) {
    const int word_bits = 8;
    const int word_count = 256 / word_bits;
    const int word_shift = n / word_bits;
    const int bit_shift = n % word_bits;
    if (word_shift != 0) {
        for (int i = word_count - 1 - word_shift; i >= 0; --i) { // Or memcpy
            words[i + word_shift] = words[i];
        }
        for (int i = word_shift - 1; i >= 0; --i) { // Or memset
            words[i] = 0;
        }
    }
    uint8_t carry = 0;
    uint8_t mask = (1 << word_bits) - 1;
    for (int_fast8_t i = word_shift; i < word_count; ++i) {
        uint8_t m = carry;
        carry = (words[i] >> (word_bits - bit_shift)) & mask;
        words[i] = (words[i] << bit_shift) | m;
    }
}

As you see I replaced one decreasing loop + plus handling of [0] with a single increasing loop with a carry.

I used uint8_t instead of uint64_t (which is generally is faster), as the carry could then be done inside a larger uint16_t:

    uint16_t carry = 0;
    uint16_t mask = (1 << word_bits) - 1;
    for (int_fast8_t i = word_shift; i < word_count; ++i) {
        uint8_t m = carry;
        carry = ((uint16_t)words[i]) << bit_shift;
        words[i] = ((uint8)carry) | m;
        carry >>= bits_shift;
    }

This is my spotted "improvement" (which has to be proven by timing).

uint32_t instead of uint64_t would be a middle way.

Which is realy faster has to be determined.

By the way in C++'s std::bitset would be more elegant.

Answer 2

I tried to improve upon your second version, incorporating some changes of @JoopEggen and some of my own:

Word out ideas

As already pointed out, it can help much to simply define variables holding the values you will use later, eg. word_shift, etc. This does not cost any computation (or storage) time with any barely decent compiler but helps tremendously when thinking about the problem.

Use braces

I know, you didn't ask for code style improvements, but braces don't hurt either and having a multiline if-else within a for-loop without delimiting it with braces is not nicely readable and also often a source for future bugs.

Be explicit, write obvious code

Using n && i >= 0 in the for loop just gives extra reading burden to the programmer. If I see a condition within the loop head I think about why it's checked every iteration. I wrote instead:

if (n == 0) { return; }

for ( /* ... */ )

And I removed the comment as now the code is, indeed, self-documenting and obvious and the comment basically redundant.

Split the loop, move the if-statement outside

The if within the loop basically checks, whether we're already done shifting words and can begin filling up with zero. There's a neat way to do that (IMHO):

// Shift values into next word
int i;
for (i = num_words-1; i >= word_shift; i--) {
    // move word
    b[i] = b[i - word_shift] << bit_shift;
    // move leftover carried bits
    if (i != word_shift) {
        b[i] |= b[i-word_shift - 1] >> (word_bits - bit_shift);
    }
}
// Fill in zeroes
for (; i >= 0; i--) {
    b[i] = 0;
}

I move the iterator declaration outside of the loop and instead of counting til zero, I count to word_shift for moving the values and then have a separate loop filling up the remaining bits. Now the loop body doesn't have different meanings in different iterations, making it easier to model in your head.

I also removed the special case where n is a multiple of 64 since it doesn't matter for the semantics of the code and I doubt there's any gain performance-wise for that. If you want to keep it in, I'd rephrase it to n % 64 == 0 because here, as well, being more explicit doesn't hurt. Usually good choice of style is to emit the x == 0 check in cases where you want to check a Boolean, such as:

int flag = 0;
/* ... */
if (flag) { }

or the "existence" of a pointer:

int *p;
/* ... */
if (!p) { /* read: if p "doesn't exist" */
    /* ... */
}

If you want to check whether an integer holds zero, use x == 0, just as you would compare to 42 using x == 42. While, to the compiler, it's equivalent, to the reader it eases understanding.

Don't hardcode values

Now it's easy to "generalize" your function, if you want to. Using sizeof, CHAR_BIT and an additional argument to your function, it can process any bitset that is a multiple of 64 Bits (one could now implement the same function using uint8_t instead to allow almost any-sized bitsets and use it instead or as a fallback function called from this, if `bits % word_bits !=

void shl(uint64_t *const b, const uint16_t bits, const uint_fast8_t n)
{
    const uint8_t word_bits = sizeof (b[0]) * CHAR_BIT;
    const uint8_t word_shift = n / word_bits;
    const uint8_t bit_shift = n % word_bits;

    const uint8_t num_words = bits/word_bits;
    assert(bits % word_bits == 0);
}

Putting it together

void shl(uint64_t *const b, const uint16_t bits, const uint_fast8_t n)
{
    const uint8_t word_bits = sizeof (b[0]) * CHAR_BIT;
    const uint8_t word_shift = n / word_bits;
    const uint8_t bit_shift = n % word_bits;

    const uint8_t num_words = bits/word_bits;
    assert(bits % word_bits == 0);

    if (n == 0) { return; }

    // Shift values into next word
    int i;
    for (i = num_words-1; i >= word_shift; i--) {
        // move word
        b[i] = b[i - word_shift] << bit_shift;

        // move leftover carried bits
        if (i != word_shift) {
            b[i] |= b[i-word_shift - 1] >> (word_bits - bit_shift);
        }
    }
    // Fill in zeroes
    for (; i >= 0; i--) {
        b[i] = 0;
    }

}

Final notes

Currently, your layout to represent eg. 0x01020408 is an array { 0x08, 0x04, 0x02, 0x01 }. This, to me, feels a bit counter-intuitive and also makes it a bit more difficult to eventually "upcast" to an even higher bitset, if you'd order the bytes reversed, you'd simply copy them and append zeroes. But that decision personal preference and/or application dependent.

While my solution definitely uses more vertical space, we thankfully do not write on teletype writers anymore, making that a rather irrelevant restriction :)

Answer 3

Using the head of larkey. I did some optimizations. Don't do the word loop if there are less than word_bits to shift and don't recalculate the values.

void shr(uint64_t *const b, const uint16_t bits, const uint_fast8_t n)
{
    const uint8_t word_bits = sizeof (b[0]) * CHAR_BIT;
    const uint8_t word_shift = n / word_bits;
    const uint8_t bit_shift = n % word_bits;
    const uint8_t bit_rest = word_bits-bit_shift;
    const uint8_t num_words = bits/word_bits;
    assert(bits % word_bits == 0);

    if (n == 0) { return; }

    uint64_t *dst, *src;

    if(word_shift>0) {
        for(dst = b+num_words-1, src = dst-word_shift; src>=b; dst--, src--)
            *dst = *src;
        for(; dst>=b; dst--)
            *dst = 0;
    }
    for(dst = b+num_words-1; dst>b; dst--)
        *dst = (*dst>>bit_shift) | (dst[-1]<<bit_rest);
    *dst >>= bit_shift;
}