How to swap n bits from 2 numbers?-CodePudding

So currently (I don't know if the width is relevant) I have 2 128bit integers that I want to swap shift bits as shift is a part of a structure:

unsigned char shift : 7;

So I get the relevant bits like this:

__uint128_t rawdata = ((*pfirst << shift) >> shift), rawdatasecond = ((*psecond << shift) >> shift);

And then I swap them like this:

*pfirst = *pfirst >> 127 - shift << 127 - shift | rawdatasecond;

*psecond = *psecond >> 127 - shift << 127 - shift | rawdata;

But I feel like I'm missing something - or am I (not sure how to test either)?

Note:

__uint128_t *pfirst, *psecond; //pointer to some integers

CodePudding user response：

As I understand the task, you would like to swap bits 0, ..., n-1 for two integers. This can be done as follows:

static inline void swapbits(__uint128_t *a, __uint128_t *b, unsigned n)
{
    if(n < 8 * sizeof(*a))
    {
        __uint128_t mask = (((__uint128_t)1) << n) - 1;
        __uint128_t bits_a = *a & mask;  // Get the bits from a
        __uint128_t bits_b = *b & mask;  // Get the bits from b
        *a = (*a & ~mask) | bits_b;    // Set bits in a
        *b = (*b & ~mask) | bits_a;    // Set bits in b
    }
}

Testing is a matter of calling the function with different combinations of values for a, b and n and checking that the result is as expected.

Clearly it is not feasible to test all combinations so a number of representative cases must be defined. It is not an exact science, but think about middle and corner cases: n=0, n=1, n=64, n=127, n=128 and a and b having different bit patterns around the left-most and right-most positions as well as around the n'th position.

CodePudding user response：

static void SwapHighNBits(__uint128_t *a, __uint128_t *b, size_t n)
{
    //  Calculate number of uninvolved bits.
    size_t NU = 128 - n;

    //  Calculate bitwise difference and remove uninvolved bits.
    __uint128_t d = (*a ^ *b) >> NU << NU;

    //  Apply difference.
    *a ^= d;
    *b ^= d;
}

A good test suite would include all combinations of bits in the critical positions: The high bit, the lowest bit swapped, the highest bit not swapped, and the lowest bit. That is four bits in each of two operands, so eight bits total, 256 combinations for a specific value of n. Then test values of n from 2 to 126. Other bits can be filled randomly.

For n = 1, the high bit and the lowest bit swapped are identical, so make separate test code for that, or write the common test code carefully to cover that. Similarly, for n = 127, the highest bit not swapped and the lowest bit are identical, and, for n = 128, there are no bits not swapped.

If defined behavior is defined for n ≤ 0 or n > 128, add test cases for those. Note that the code above does not support n = 0, as NU will be 128, and the shifts are not defined by the C standard. Of course, for n = 0, one can simply return without making any changes.