Whats the best way to shift an array of bytes by 12-bits?

Question

With gcc, I want to shift the contents of an array of bytes by 12-bit to the left.

For example, starting with this array:

uint8_t shift[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0x0A, 0xBC};

I'd like to shift it to the left by 12-bits resulting in:

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00

Answer 1

Lets make it the best way to shift N bits in the array of 8 bit integers.

N            - Total number of bits to shift
F = (N / 8) - Full 8 bit integers shifted
R = (N % 8) - Remaining bits that need to be shifted

I guess from here you would have to find the most optimal way to make use of this data to move around ints in an array. Generic algorithms would be to apply the full integer shifts by starting from the right of the array and moving each integer F indexes. Zero fill the newly empty spaces. Then finally perform an R bit shift on all of the indexes, again starting from the right.

In the case of shifting 0xBC by R bits you can calculate the overflow by doing a bitwise AND, and the shift using the bitshift operator:

// 0xAB shifted 4 bits is:
(0xAB & 0x0F) >> 4   // is the overflow      (0x0A)
0xAB << 4            // is the shifted value (0xB0)

Keep in mind that the 4 bits is just a simple mask: 0x0F or just 0b00001111. This is easy to calculate, dynamically build, or you can even use a simple static lookup table.

I hope that is generic enough. I'm not good with C/C++ at all so maybe someone can clean up my syntax or be more specific.

Bonus: If you're crafty with your C you might be able to fudge multiple array indexes into a single 16, 32, or even 64 bit integer and perform the shifts. But that is prabably not very portable and I would recommend against this. Just a possible optimization.

Answer 2

@Joseph, notice that the variables are 8 bits wide, while the shift is 12 bits wide. Your solution works only for N <= variable size.

If you can assume your array is a multiple of 4 you can cast the array into an array of uint64_t and then work on that. If it isn't a multiple of 4, you can work in 64-bit chunks on as much as you can and work on the remainder one by one. This may be a bit more coding, but I think it's more elegant in the end.

Answer 3

Hurray for pointers!

This code works by looking ahead 12 bits for each byte and copying the proper bits forward. 12 bits is the bottom half (nybble) of the next byte and the top half of 2 bytes away.

unsigned char length = 10;
unsigned char data[10] = {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0A,0xBC};
unsigned char *shift = data;
while (shift < data+(length-2)) {
    *shift = (*(shift+1)&0x0F)<<4 | (*(shift+2)&0xF0)>>4;
    shift++;
}
*(data+length-2) = (*(data+length-1)&0x0F)<<4;
*(data+length-1) = 0x00;

Justin wrote:
@Mike, your solution works, but does not carry.

Well, I'd say a normal shift operation does just that (called overflow), and just lets the extra bits fall off the right or left. It's simple enough to carry if you wanted to - just save the 12 bits before you start to shift. Maybe you want a circular shift, to put the overflowed bits back at the bottom? Maybe you want to realloc the array and make it larger? Return the overflow to the caller? Return a boolean if non-zero data was overflowed? You'd have to define what carry means to you.

unsigned char overflow[2];
*overflow = (*data&0xF0)>>4;
*(overflow+1) = (*data&0x0F)<<4 | (*(data+1)&0xF0)>>4;
while (shift < data+(length-2)) {
    /* normal shifting */
}  
/* now would be the time to copy it back if you want to carry it somewhere */
*(data+length-2) = (*(data+length-1)&0x0F)<<4 | (*(overflow)&0x0F);
*(data+length-1) = *(overflow+1);  

/* You could return a 16-bit carry int, 
 * but endian-ness makes that look weird 
 * if you care about the physical layout */
unsigned short carry = *(overflow+1)<<8 | *overflow;

Answer 4

Actually, I believe I handle bit shifts greater than 8 bits properly. The example I showed was only for a bit shift guarenteed to be less than 8 bits due to N mod 8. Handling anything over 8 bits in the array structure shown would entail moving ints across indexs.

Sorry for the typing on this one. Laptop died so I'm iPodding it.

Answer 5

Here's my solution, but even more importantly my approach to solving the problem.

I approached the problem by

• drawing the memory cells and drawing arrows from the destination to the source.
• made a table showing the above drawing.
• labeling each row in the table with the relative byte address.

This showed me the pattern:

• let iL be the low nybble (half byte) of a[i]
• let iH be the high nybble of a[i]
• iH = (i+1)L
• iL = (i+2)H

This pattern holds for all bytes.

Translating into C, this means:

a[i] = (iH << 4) OR iL
a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4)

We now make three more observations:

• since we carry out the assignments left to right, we don't need to store any values in temporary variables.
• we will have a special case for the tail: all 12 bits at the end will be zero.
• we must avoid reading undefined memory past the array. since we never read more than a[i+2], this only affects the last two bytes

So, we - handle the general case by looping for N-2 bytes and performing the general calculation above - handle the next to last byte by it by setting iH = (i+1)L - handle the last byte by setting it to 0

given a with length N, we get:

for (i = 0; i < N - 2; ++i) {
    a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4);
}
a[N-2] = (a[N-1) & 0x0f) << 4;
a[N-1] = 0;

And there you have it... the array is shifted left by 12 bits. It could easily be generalized to shifting N bits, noting that there will be M assignment statements where M = number of bits modulo 8, I believe.

The loop could be made more efficient on some machines by translating to pointers

for (p = a, p2=a+N-2; p != p2; ++p) {
    *p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
}

and by using the largest integer data type supported by the CPU.

(I've just typed this in, so now would be a good time for somebody to review the code, especially since bit twiddling is notoriously easy to get wrong.)

Answer 6

The 32 bit version... :-) Handles 1 <= count <= num_words

#include <stdio.h>

unsigned int array[] = {0x12345678,0x9abcdef0,0x12345678,0x9abcdef0,0x66666666};

int main(void) {
  int count;
  unsigned int *from, *to;
  from = &array[0];
  to = &array[0];
  count = 5;

  while (count-- > 1) {
    *to++ = (*from<<12) | ((*++from>>20)&0xfff);
  };
  *to = (*from<<12);

  printf("%x\n", array[0]);
  printf("%x\n", array[1]);
  printf("%x\n", array[2]);
  printf("%x\n", array[3]);
  printf("%x\n", array[4]);

  return 0;
}

Answer 7

Here a working solution, using temporary variables:

void shift_4bits_left(uint8_t* array, uint16_t size)
{
    int i;
    uint8_t shifted = 0x00;    
    uint8_t overflow = (0xF0 & array[0]) >> 4;

    for (i = (size - 1); i >= 0; i--)
    {
        shifted = (array[i] << 4) | overflow;
        overflow = (0xF0 & array[i]) >> 4;
        array[i] = shifted;
    }
}

Call this function 3 times for a 12-bit shift.

Mike's solution maybe faster, due to the use of temporary variables.

Answer 8

There are a couple of edge-cases which make this a neat problem:

• the input array might be empty
• the last and next-to-last bits need to be treated specially, because they have zero bits shifted into them

Here's a simple solution which loops over the array copying the low-order nibble of the next byte into its high-order nibble, and the high-order nibble of the next-next (+2) byte into its low-order nibble. To save dereferencing the look-ahead pointer twice, it maintains a two-element buffer with the "last" and "next" bytes:

void shl12(uint8_t *v, size_t length) {
  if (length == 0) {
    return; // nothing to do
  }

  if (length > 1) {
    uint8_t last_byte, next_byte;
    next_byte = *(v + 1);

    for (size_t i = 0; i + 2 < length; i++, v++) {
      last_byte = next_byte;
      next_byte = *(v + 2);
      *v = ((last_byte & 0x0f) << 4) | (((next_byte) & 0xf0) >> 4);
    }

    // the next-to-last byte is half-empty
    *(v++) = (next_byte & 0x0f) << 4;
  }

  // the last byte is always empty
  *v = 0;
}

Consider the boundary cases, which activate successively more parts of the function:

• When length is zero, we bail out without touching memory.
• When length is one, we set the one and only element to zero.
• When length is two, we set the high-order nibble of the first byte to low-order nibble of the second byte (that is, bits 12-16), and the second byte to zero. We don't activate the loop.
• When length is greater than two we hit the loop, shuffling the bytes across the two-element buffer.

If efficiency is your goal, the answer probably depends largely on your machine's architecture. Typically you should maintain the two-element buffer, but handle a machine word (32/64 bit unsigned integer) at a time. If you're shifting a lot of data it will be worthwhile treating the first few bytes as a special case so that you can get your machine word pointers word-aligned. Most CPUs access memory more efficiently if the accesses fall on machine word boundaries. Of course, the trailing bytes have to be handled specially too so you don't touch memory past the end of the array.

Answer 9

@Mike, your solution works, but does not carry.
Giving your code the following array:

uint8_t data[10] = {0xE0, 0x00, 0x0A, 0xBC, 0x00, 0x00, 0x00, 0x00, 0x0A, 0xBC};

Your function would lose the 0xE0. But otherwise it works, and shifts 12-bits.