Circular shift 28 bits within 4 bytes in C

Question

I have an unsigned char *Buffer that contains 4 bytes, but only 28 of them are relevant to me.

I am looking to create a function that will do a circular shift of the 28 bits while ignoring the remaining 4 bits.

For example, I have the following within *Buffer

1111000011001100101010100000

Say I want to left circular shift by 1 bit of the 28 bits, making it

1110000110011001010101010000

I have looked around and I can't figure out how to get the shift, ignore the last 4 bits, and have the ability to shift either 1, 2, 3, or 4 bits depending on a variable set earlier in the program.

Any help with this would be smashing! Thanks in advance.

Isn't a left circular shift of `1111000011001100101010100000` actually supposed to be `1110000110011001010101010001`? Or do you not mean the "circular" part? — Tibrogargan, Mar 21 '16 at 06:00
What do you mean ignore? We have to put something there, no? Some code would be great. — Debosmit Ray, Mar 21 '16 at 06:02
Your example trims one bit from both the left and right ends. Look up bit shifting and bit masks... you might just need `num >> 4`. — ZachB, Mar 21 '16 at 06:07

Tibrogargan · Answer 1 · 2016-03-22T07:41:34.950

1

Only 1 bit at a time, but this does a 28 bit circular shift

uint32_t csl28(uint32_t value) {
    uint32_t overflow_mask = 0x08000000;
    uint32_t value_mask = 0x07FFFFFF;
    return ((value & value_mask) << 1) | ((value & overflow_mask) >> 27);
}

uint32_t csr28(uint32_t value) {
    uint32_t overflow_mask = 0x00000001;
    uint32_t value_mask = 0x0FFFFFFE;
    return ((value & value_mask) >> 1) | ((value & overflow_mask) << 27);
}

Another version, based on this article. This shifts an artbitrary number of bits (count) within an arbitrarily wide bit field (width). To left shift a value 5 bits in a 23 bit wide field: rotl32(value, 5, 23);

uint32_t rotl32 (uint32_t value, uint32_t count, uint32_t width) {
    uint32_t value_mask = ((uint32_t)~0) >> (CHAR_BIT * sizeof(value) - width);
    const uint32_t mask = (width-1);
    count &= mask;
    return value_mask & ((value<<count) | (value>>( (-count) & mask )));
}

uint32_t rotr32 (uint32_t value, uint32_t count, uint32_t width) {
    uint32_t value_mask = ((uint32_t)~0) >> (CHAR_BIT * sizeof(value) - width);
    const uint32_t mask = (width-1);
    count &= mask;
    return value_mask & ((value>>count) | (value<<( (-count) & mask )));
}

The above functions assume the value is stored in the low order bits of "value"

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

const char *uint32_to_binary(uint32_t x)
{
    static char b[33];
    b[0] = '\0';

    uint32_t z;
    for (z = 0x80000000; z > 0; z >>= 1)
    {
        strcat(b, ((x & z) == z) ? "1" : "0");
    }

    return b;
}

uint32_t reverse(uint32_t value)
{
     return (value & 0x000000FF) << 24 | (value & 0x0000FF00) << 8 |
            (value & 0x00FF0000) >> 8  | (value & 0xFF000000) >> 24;
}

int is_big_endian(void)
{
    union {
        uint32_t i;
        char c[4];
    } bint = {0x01020304};

    return bint.c[0] == 1; 
}

int main(int argc, char** argv) {
    char b[] = { 0x98, 0x02, 0xCA, 0xF0 };
    char *buffer = b;        

    //uint32_t num = 0x01234567;
    uint32_t  num = *((uint32_t *)buffer);
    if (!is_big_endian()) {
        num = reverse(*((uint32_t *)buffer));
    }
    num >>= 4;
    printf("%x\n", num);

    for(int i=0;i<5;i++) {
        printf("%s\n", uint32_to_binary(num));
        num = rotl32(num, 3, 28);
    }
    for(int i=0;i<5;i++) {
        //printf("%08x\n", num);
        printf("%s\n", uint32_to_binary(num));
        num = rotr32(num, 3, 28);
    }

    unsigned char out[4];
    memset(out, 0, sizeof(unsigned char) * 4);
    num <<= 4;
    if (!is_big_endian()) {
        num = reverse(num);
    }
    *((uint32_t*)out) = num;
    printf("[ ");
    for (int i=0;i<4;i++) {
      printf("%s0x%02x", i?", ":"", out[i] );
    }
    printf(" ]\n");
}

edited Mar 22 '16 at 07:41

answered Mar 21 '16 at 06:31

Tibrogargan

4,508
3
19
38

This may work. Ill give it a shot. In regards to the last answer given below, There are 32 bits in the char 11110000110011001010101000000000, and I was to ignore the last 4 bits. So shifting left 1 would become 1110000110011001010101000001 That was a mistype for the right most 4 bits – TyrantUT Mar 22 '16 at 03:17
I don't seem to be able to implement this within my code. Lets say *buffer, which is an unsigned char, contains `0011000000000101100101011110000` or `9802CAF0` in hex As you can see, 1 have 32 bytes there. I need to mask off and completely ignore the last 0, or the last 0000 in bits. Then circular shift the rest. I'm sure the code you have here may work, I just don't know how to implement it into my code. I would prefer to have it in a void () function if possible. – TyrantUT Mar 22 '16 at 06:45
It's unclear how your data is stored. Are you storing a string of 1s and 0s? (i..e Your string is literally `"0011000000000101100101011110000"`?). Or do you have a hex value? i.e. Your char * is really an array of 4 chars holding `[ 0x98, 0x02, 0xCA, 0xF0 ]`? It it's the later you could do this: `uint32_t val = *((uint32 *)buffer) >> 4`; (endianness may cause grief) – Tibrogargan Mar 22 '16 at 06:54
What do you mean a void() function? You want to pass in an address value where you can store the result as an additional parameter? Why? – Tibrogargan Mar 22 '16 at 06:58
And why are you using a char* when your values all fit neatly into a 32 bit int, signed or unsigned? – Tibrogargan Mar 22 '16 at 07:01
it is a char * 4 holding hex. so 4 bytes, but I only care about the 28 most significant bits. The last 4 bits i want to completely ignore, but not remove them. Just leave them as 0. I did a memset originally to 0 out the char *. – TyrantUT Mar 22 '16 at 07:16
Added some helper functions and a little example program. Depending on your endianess, you may want to remove the reverse() call. – Tibrogargan Mar 22 '16 at 07:23
Awesome! Ill see what I can do to implement it into my program. I think the endiness is off though. Removing the reverse function, just return value there? – TyrantUT Mar 22 '16 at 07:36
Added a method to check endianess to determine if the reverse is necessary – Tibrogargan Mar 22 '16 at 07:42
The main takes a byte[], prints it shifts it left 5 times (showing the bit pattern), shifts it right 5 times and then puts the result into a second byte array then prints that so you can see they match – Tibrogargan Mar 22 '16 at 07:43
You may want to consider storing your bit patterns in a union similar to that used to detect the endianness – Tibrogargan Mar 22 '16 at 07:47
Here you have `char b[] = { 0x98, 0x02, 0xCA, 0xF0 };` How do I adopt that to unsigned char *buffer. Which contains 4 bytes, 9802caf0? charb[] here is an array. – TyrantUT Mar 22 '16 at 07:57
You could just do `buffer = b;`. There is almost no difference in C between an array of char and a pointer to char. Also, the only difference between `char` and `unsigned char` that you would care about here is sign extension when you're shifting or promoting to an int. – Tibrogargan Mar 22 '16 at 08:15

score 0 · Answer 2 · answered Mar 21 '16 at 06:09

0

First you mask the top four most significant bits

*(buffer + 3) &= 0x0F;

Then you can perform the circular shift of the remaining 28 bits by x bits.

Note: This will work for little endian architecture(x86 Pc's and most microcontrollers)

answered Mar 21 '16 at 06:09

Rishikesh Raje

8,556
2
16
31

score -1 · Answer 3 · edited May 23 '17 at 11:50

-1

[...] that contains 4 bytes, but only 28 of them [...]

We got it, but...

I guess that you mis-typed the second number of your example. Or you '''ignore''' 4 bits from left and right so you're actually interrested in 24 bits? Anyway:

Use same principle as in Circular shift in c.

You need to convert your Buffer to a 32 bit arithmetic type, before. Maybe uint32_t is what you need?

Where did Buffer get his value? You may need to think about endianness.

edited May 23 '17 at 11:50

Community

1
1

answered Mar 21 '16 at 06:19

yarl

161
1
6

The buffer value was from the following `unsigned int byteArray[8]; int i; size_t keyLen = strlen(keyInput); if (keyLen > 16) { fprintf(stderr, "Invalid key length.\n"); exit(-1); } for (i = 0; i < 8; i++) { sscanf(keyInput + 2 * i, "%02x", &byteArray[i]); Buffer[i] = byteArray[i]; }` Buffer is unsigned char *Buffer = malloc(8 * sizeof (char)); – TyrantUT Mar 22 '16 at 03:22

Circular shift 28 bits within 4 bytes in C

3 Answers3

Linked