How to shift 4 byte array by all 32 bits with a wraparound?

Question

I am trying to implement an animation shifting function, that will allow me to shift all (LAYERS*BYTES) LEDS by 32 bits with an overlap. I only could do it with byte shifting, but that is not what I need.

To better understnad the idea, the image is provided below:

I drew it out where C is a carry bit that is moved to the start of the following byte and the last element of 4 bytes is assigned to the first element of the first byte.

There might be a better way to implement this. I appreciate for any help in advance.

Additional information:

void Shift_Right_Byte(void){
    for (int row = 0; row < LAYERS; row++) {
            for (int col = 0; col < BYTES; col++) {
                LED_Buffer[row][col] = LED_Buffer[row][(col + 1) % BYTES];
            }
        }
        delay(1000);
}

New function:

void layer_rotate_right(void) 
{
    for (int row = 0; row < LAYERS; row++) {
        unsigned char carry = LED_Buffer[row][BYTES - 1] << 7 ;
        for( int i = 0; i < BYTES; i++ )
        {   
            unsigned char next_carry = LED_Buffer[row][i] << 7 ;
            LED_Buffer[row][i] = (LED_Buffer[row][i] >> 1) | carry ;
            carry = next_carry ;
        }
    }
}

This is commonly referred to as **rotating** a 4 byte array. — user3386109, Apr 23 '19 at 21:50
If it aligns on a proper boundary it might be possible to manipulate as a `uint32_t*` using a a shift | masked_shift (sometimes known as a "barrel roll" or "circular shift"). The bit patterns of the device are important (and may require a 'mix' instead of a shift on, eg, Big Endian). — user2864740, Apr 23 '19 at 21:50
https://stackoverflow.com/q/13289397/2864740 , https://stackoverflow.com/q/36124058/2864740 — user2864740, Apr 23 '19 at 21:53
"I only could do it with byte shifting, but that is not what I need" ...cool, show us the code. — bigwillydos, Apr 23 '19 at 22:21
@user2864740 Thanks for the provided links, I will have a look at them. — RytisBe, Apr 23 '19 at 23:20
"... with an overlap" is ambiguous - you mean "rotate 4 byte array"? — Clifford, Apr 24 '19 at 07:22

Clifford · Accepted Answer · 2019-04-24T07:40:45.760

2

A specific solution for if the layer is always 4 bytes is to pack the bytes into a uint32_t and apply the rotation to that.

Given:

void layer_rotate_right( uint8_t layer[4] ) 
{
    // Pack...
    uint32_t word = layer[0]<<24 | layer[1]<<16 | layer[2]<<8 | layer[3] ;

    // Rotate...
    uint32_t rotated = word << 31 | word >> 1 ;

    // Unpack...
    layer[0] = rotated >> 24 ;
    layer[1] = (rotated >> 16) & 0xff ;
    layer[2] = (rotated >> 8) & 0xff ;
    layer[3] = rotated & 0xff ;
}

Then:

for (int row = 0; row < LAYERS; row++) 
{
    layer_rotate_right( LED_Buffer[row] )
}

The packing and unpacking is somewhat cumbersome. Given appropriate endianness and alignment you may get away with casting, but as a solution it does not scale.

A more general solution for any size byte array is:

void layer_rotate_right( uint8_t* layer, int len ) 
{
    uint8_t carry = layer[len - 1] << 7 ;
    for( int i = 0; i < len; i++ )
    {   
        uint8_t next_carry = layer[i] << 7 ;
        layer[i] = (layer[i] >> 1) | carry ;
        carry = next_carry ;
    }
}

Then:

for (int row = 0; row < LAYERS; row++) 
{
    layer_rotate_right( LED_Buffer[row], BYTES )
}

edited Apr 24 '19 at 07:40

answered Apr 24 '19 at 07:21

Clifford

88,407
13
85
165

Thanks for your reply! I slightly modified your provided code and included in the main post. However, I observed that shifting of a single pixel say from LED_Buffer[0][0] is as expected (0b00000001 --> 0b10000000), but it then transitions to the LED_Buffer[0][3]-->LED_Buffer[0][2]-->LED_Buffer[0][1]. It should really go from [0][0].... to [0][3]. I tried to understand what needs to be done in order to fix this, but achieved no success. – RytisBe Apr 24 '19 at 19:39
1

@RytisBe : It looks like the byte order as rendered on your LED array is not the same as in your diagram where I had assumed that the left-hand side was index zero. Reverse the for loop to run from `len` to `0` perhaps? – Clifford Apr 24 '19 at 22:07
I would advise against changing the question to incorporate provided answers; it tends to make the answers look like nonsense. It now reads like "_Q: I tried X, but it does not work. A: Try X_". In this case a new question may be appropriate since I think the issue is a difference between what you asked for and what you actually need. – Clifford Apr 24 '19 at 22:16
I totaly agree with you. To be honest, you provided enough information and after spending a little bit more time I managed to modify the given function to behave the way I want it to. Thanks to you Clifford. – RytisBe Apr 24 '19 at 22:55

score 1 · Answer 2 · answered Apr 25 '19 at 18:56

A different approach would be to use a union. For example,

typedef union{
    uint8_t buff8[4];
    uint32_t buff32;
}led_buffer_t;

Then use this to declare LED_Buffer (e.g. led_buffer_t LED_Buffer[LAYERS] = {0};)

And then use the circular shift answer here: Circular shift in c

I tried it out here: https://onlinegdb.com/ByfcMY1sE

How to shift 4 byte array by all 32 bits with a wraparound?

2 Answers2