byte swapping/reversing a character array

Question

I am looking for a method to reverse the bytes in a character array.I also need to reverse the individual bits of the bytes being swapped before positioning them in the right place. for example say I have a char arr[1000] whose arr[0] = 00100011 and arr[999] = 11010110, I want to swap arr[0] and arr[999] and in addition reverse the bits in each of them. so the output would be arr[999]= 11000100 ( reversed bits of arr[0]) and arr[0] = 01101011 (reversed bits of arr[999]).

I have some code to do the bit reversal inside a byte :

static  char reverseByte(char val)
{
    char result = 0;

    int counter = 8;
    while (counter-- < 0)
    {
        result <<= 1;
        result |= (char)(val & 1);
        val = (char)(val >> 1);
    }

    return result;
}

But this would mean running an outer loop to do the byte swap and then running the above small loop for each byte inside i.e 1000 in the above case. Is this the right approach ? Is there a better way to achieve this ? Any help would be greatly appreciated.

Answer 1

How about this?:

#include <stdio.h>
#include <limits.h>

#if CHAR_BIT != 8
#error char is expected to be 8 bits
#endif

unsigned char RevByte(unsigned char b)
{
  static const unsigned char t[16] =
  {
    0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE,
    0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF
  };
  return t[b >> 4] | (t[b & 0xF] << 4);
}

void RevBytes(unsigned char* b, size_t c)
{
  size_t i;
  for (i = 0; i < c / 2; i++)
  {
    unsigned char t = b[i];
    b[i] = RevByte(b[c - 1 - i]);
    b[c - 1 - i] = RevByte(t);
  }
  if (c & 1)
    b[c / 2] = RevByte(b[c / 2]);
}

int main(void)
{
  int i;
  unsigned char buf[16] = 
  {
    0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE,
    0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF
  };

  RevBytes(buf, 16);

  for (i = 0; i < 16; i++)
    printf("0x%02X ", buf[i]);
  puts("");

  return 0;
}

Output (ideone):

0xF0 0xE0 0xD0 0xC0 0xB0 0xA0 0x90 0x80 0x70 0x60 0x50 0x40 0x30 0x20 0x10 0x00

Answer 2

Reversing the elements of a collection is an old trick - you swap first and last, then first+1 and last-1, then... until first+i is equal to or further along the collection than last-j.

All you have to add onto that is

-flipping the bits of the two entries before swapping them

-if you have one element left in the middle, flip its bits on the spot

Answer 3

To do this - assuming your bit reversal method is correct - if you can spare the extra char in storage, you can simply traverse the bytes. Consider the following method:

static void swapReverseBytes(char* arr, size_t len)
{
  int i = 0;
  char tmp = 0;
  if(arr == NULL || len < 1)
    return;
  if(len == 1) {
    arr[0] = reverseByte(arr[0]);
    return;
  }
  for(i = 0 ; i < (len / 2) ; ++i) {
    tmp = arr[len - i - 1];
    arr[len - i - 1] = reverseByte(arr[i]);
    arr[i] = reverseByte(tmp);
  }
}

This is a rough sketch (should compile, I think) and, assuming I have no off-by-one errors, this should work. As mentioned earlier, it is probably fastest to reverse the bits using a LUT, but byte swapping will be relatively similar since you need to actually move each byte unless you are keeping some state about the traversal order of the array. If that is the case, it is quite possible to simply use some state (i.e. a flag) to determine whether the array should be traversed normally (1...n) or in reverse order (n...1). In any event, the swapping is "free" in the Big-O, but in practice may (not necessarily) show a performance impact (since there will be no "actual" swapping of the byte order). Note, this would not work if the user expects an array which is sorted - this trick only works in the event that this is internal (or you have some sort of encapsulation, say, as in a C++ class).

Answer 4

To do this - assuming your bit reversal method is correct - if you can spare the extra char in storage, you can simply traverse the bytes. Consider the following method:

static void swapReverseBytes(char* arr, size_t len)
{
  int i = 0;
  char tmp = 0;
  if(arr == NULL || len < 1)
    return;
  if(len == 1) {
    arr[0] = reverseByte(arr[0]);
    return;
  }
  for(i = 0 ; i < (len / 2) ; ++i) {
    tmp = arr[len - i - 1];
    arr[len - i - 1] = reverseByte(arr[i]);
    arr[i] = reverseByte(tmp);
  }
}

This is a rough sketch (should compile, I think) and, assuming I have no off-by-one errors, this should work. As mentioned earlier, it is probably fastest to reverse the bits using a LUT, but the byte swapping method will be relatively similar since you need to actually move each byte unless you are keeping some state about the traversal order of the array. If that is the case, it is quite possible to simply use some state (i.e. a flag) to determine whether the array should be traversed normally (1...n) or in reverse order (n...1). In any event, the swapping is "free" in the Big-O, but in practice may (not necessarily) show a performance impact. So if your optimization is really on speed and an extra int in space isn't too much, this state may be worthwhile for you. Note that this trick will only work if this is internal. If this method is public to the user and he or she does not know about the flag, then this will not actually flip anything. Another option to use this is if you can use C++, you can create a class which encapsulates this functionality for the user.