Bitshift on structures

Question

I'm unsure if this is possible due to structure padding and alignment but, assuming you take care of that by aligning your structures to 4/8 bytes, is it possible to bit shift on a structure as if it was a single variable?

What I'd like to do is take a string (max 8 bytes) and shift it into the high order bits of a 64-bit variable.

Like if I do this:

#include <stdint.h>
#include <string.h>
void shiftstr(uint64_t* t,char* c,size_t len){
    memcpy(t, c, len);
    //now *t==0x000000617369616b
    *t<<=(sizeof(uint64_t)-len)*8;
    //now *t==0x617369616b000000
}
int main(){
    uint64_t k = 0;
    char n[] = "kaisa";
    shiftstr(&k, n,strlen(n));
    return 0;
}

This works just fine, but what if I had, instead of a uint64_t, two uint32_t, either as individual variables or a structure.

#include <stdint.h>
#include <string.h>
struct U64{
    uint32_t x;
    uint32_t y;
};
void shiftstrstruct(struct U64* t, char* c, size_t len){
    memcpy(t, c, len);
    /*
     At this point I think
     x == 0x7369616b
     y == 0x00000061
     But I could be wrong
     */
    //but how can I perform the bit shift?
    //Where
    //x==0x0000006b
    //y==0x61697361
    
}
int main(){
    char n[] = "kaisa";
    struct U64 m = {0};
    shiftstrstruct(&m, n, strlen(n));
    return 0;
}

Up to the memcpy part, it should be the same as if I were performing it on a single variable. I believe the values of x and y are correct in such situations. But, if that's the case that means the values need to be shifted away from x towards y.

I know I can cast but what if I wanted to deal with a 16 byte string that needed to be shifted into two 64 bit variables, or even larger?

Is shifting structures like this possible? Is there a better alternative?

Answer 1

Is shifting structures like this possible?

No, not really. Even if the x and y members are in adjacent memory locations, bit-shift operations on either are performed as integer operations on the individual variables. So, you can't shift bits "out of" one and "into" the other: bits that "fall off" during the shift will be lost.

Is there a better alternative?

You would have to implement such a multi-component bit-shift yourself – making copies of the bits that would otherwise be lost and somehow masking those back into the result, after shifting other bits internally to each 'component' variable. Exactly how to do this would largely depend on the use case.

Here's one possible implementation of a right-shift function for a structure comprising two uint64_t members (I have not added any error-checking for the count, and I assume that uint64_t is exactly 64 bits wide):

#include <stdio.h>
#include <stdint.h>

typedef struct {
    uint64_t hi;
    uint64_t lo;
} ui128;

void Rshift(ui128* data, int count)
{
    uint64_t mask = (1uLL << count) - 1; // Set low "count" bits to 1
    uint64_t save = data->hi & mask;     // Save bits that fall off hi
    data->hi >>= count;                  // Shift the hi component
    data->lo >>= count;                  // Shift the lo component
    data->lo |= save << (64 - count);    // Mask in the bits from hi
    return;
}

int main()
{
    ui128 test = { 0xF001F002F003F004, 0xF005F006F007F008 };
    printf("%016llx%016llx\n", test.hi, test.lo);
    Rshift(&test, 16);
    printf("%016llx%016llx\n", test.hi, test.lo);
    return 0;
}

A similar logic could be used for a left-shift function, but you would then need to save the relevant upper (most significant) bits from the lo member and mask them into the shifted hi value:

void Lshift(ui128* data, int count)
{
    uint64_t mask = ((1uLL << count) - 1) << (64 - count);
    uint64_t save = data->lo & mask;
    data->hi <<= count;
    data->lo <<= count;
    data->hi |= save >> (64 - count);
    return;
}

Answer 2

union is your friend, this is what you want:

#include <stdint.h>
#include <stdio.h>

typedef union _shift_u64{
    struct _u64{
        uint32_t x;
        uint32_t y;
    } __attribute__((__packed__)) U64;
    uint64_t x_and_y;
} SHIFT_U64;

int main(int argc, char* argv[]){
    SHIFT_U64 test;
    
    test.U64.x = 4;
    test.U64.y = 8;
    printf("test.U64.x=%d, test.U64.y=%d, test.x_and_y=%ld\n", test.U64.x, test.U64.y, test.x_and_y);

    test.x_and_y<<=1;
    printf("test.U64.x=%d, test.U64.y=%d, test.x_and_y=%ld\n", test.U64.x, test.U64.y, test.x_and_y);

    test.x_and_y>>=1;
    printf("test.U64.x=%d, test.U64.y=%d, test.x_and_y=%ld\n", test.U64.x, test.U64.y, test.x_and_y);

    return 0;
}

---

EDIT: This simple program illustrates how to do it the other way, but you have to check for the carry over bit and shift overflow and shift underflow by yourself. union doesn't care about the data, you just have to make sure that the data makes sense. After compiling, redirect the output of the program to a file or hex-editor and read the errorlevel of the program.

Linux example: ./a.out > a.out.bin; echo "errorlevel=$?"; xxd a.out.bin

#include <stdio.h>

typedef union _shift_it{
    struct _data{
        unsigned long x : 64;
        unsigned long y : 64;
    } __attribute__((__packed__)) DATA;
    unsigned char x_and_y[16];
} __attribute__((__packed__)) SHIFT_IT;

int main(int argc, char* argv[]){
    SHIFT_IT test;
    int errorlevel = 0;

    //bitmask for shift operation
    static const unsigned long LEFT_SHIFTMASK64 = 0x8000000000000000;
    static const unsigned long RIGHT_SHIFTMASK64 = 0x0000000000000001;

    //test data
    test.DATA.x = 0x2468246824682468; //high bits
    test.DATA.y = 0x1357135713571357; //low bits

    //binary output to stdout
    for(int i=0; i<16; i++) putchar(test.x_and_y[i]);

    //left shift
    if(test.DATA.x & LEFT_SHIFTMASK64) errorlevel += 1;
    test.DATA.x <<= 1;
    if(test.DATA.y & LEFT_SHIFTMASK64) errorlevel += 2;
    test.DATA.y <<= 1;

    //binary output to stdout
    for(int i=0; i<16; i++) putchar(test.x_and_y[i]);

    //right shift
    if(test.DATA.y & RIGHT_SHIFTMASK64) errorlevel += 4;
    test.DATA.y >>= 1;
    if(test.DATA.x & RIGHT_SHIFTMASK64) errorlevel += 8;
    test.DATA.x >>= 1;

    //binary output to stdout
    for(int i=0; i<16; i++) putchar(test.x_and_y[i]);

    //right shift
    if(test.DATA.y & RIGHT_SHIFTMASK64) errorlevel += 16;
    test.DATA.y >>= 1;
    if(test.DATA.x & RIGHT_SHIFTMASK64) errorlevel += 32;
    test.DATA.x >>= 1;

    //binary output to stdout
    for(int i=0; i<16; i++) putchar(test.x_and_y[i]);

    //left shift
    if(test.DATA.x & LEFT_SHIFTMASK64) errorlevel += 64;
    test.DATA.x <<= 1;
    if(test.DATA.y & LEFT_SHIFTMASK64) errorlevel += 128;
    test.DATA.y <<= 1;

    //binary output to stdout
    for(int i=0; i<16; i++) putchar(test.x_and_y[i]);

    return errorlevel;
}