Reverse Arbitrary Length Bit String

From Wiki
Jump to navigationJump to search

This code will reverse any number of bits, from 2 to MAX_INT.

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

int debug = 0;

//
//
//
void flip (uint8_t *ptr, int bitLength)
{
  int i;

  if (bitLength <= 1)
    return;

  if (debug)
    printf ("\n");

  for (i = 0; i < bitLength / 2; i++)
  {
    int leftIndex  = i / 8;
    int rightIndex = ((bitLength - 1) - i) / 8;

    int leftMask  = 1 << (7 - (i % 8));
    int rightMask = 1 << (7 - ((bitLength - 1) - i) % 8);

    int leftByte  = ptr [leftIndex];
    int rightByte = ptr [rightIndex];

    int leftBit   = leftByte & leftMask;
    int rightBit  = rightByte & rightMask;

    if (debug)
      printf ("li=%d,ri=%d, lm=0x%02x,rm=0x%02x, lB=0x%02x,rB=0x%02x, lb=0x%02x,rb=0x%02x\n",
          leftIndex, rightIndex,
          leftMask, rightMask,
          leftByte, rightByte,
          leftBit, rightBit);

    if (leftIndex == rightIndex)
    {
      leftByte &= ~leftMask;
      leftByte &= ~rightMask;

      leftByte |= (rightBit ? leftMask : 0);
      leftByte |= (leftBit ? rightMask : 0);

      ptr [leftIndex] = leftByte;
    }
    else
    {
      leftByte  &= ~leftMask;
      rightByte &= ~rightMask;

      leftByte  |= (rightBit ? leftMask : 0);
      rightByte |= (leftBit ? rightMask : 0);

      ptr [leftIndex] = leftByte;
      ptr [rightIndex] = rightByte;
    }
  }
}

int main (int argc __attribute__ ((unused)), char **argv __attribute__ ((unused)))
{
  const uint8_t test1 [] = { 0x40 };              //                     01xx-xxxx -> 10xx-xxxx
  const uint8_t test2 [] = { 0x60 };              //                     011x-xxxx -> 110x-xxxx
  const uint8_t test3 [] = { 0xaa };              //                     1010-1010 -> 0101-0101
  const uint8_t test4 [] = { 0xca, 0xfe };        //           1100-1010-1111-1110 -> 0111-1111-0101-0011
  const uint8_t test5 [] = { 0xca, 0xfe, 0x80 };  // 1100-1010-1111-1110-1xxx-xxxx -> 1011-1111-1010-1001-1xxx-xxxx
  const uint8_t test6 [] = { 0xca, 0xfe, 0x80 };  // 1100-1010-1111-1110-10xx-xxxx -> 0101-1111-1101-0100-11xx-xxxx
  uint8_t buffer [16];

  memcpy (buffer, test1, sizeof (test1)); flip (buffer,  2); printf ("test1:  2 bits, 0x40,     should be 0x80,     result is 0x%02x\n", buffer [0]);
  memcpy (buffer, test2, sizeof (test2)); flip (buffer,  3); printf ("test2:  3 bits, 0x60,     should be 0xc0,     result is 0x%02x\n", buffer [0]);
  memcpy (buffer, test3, sizeof (test3)); flip (buffer,  8); printf ("test3:  8 bits, 0xaa,     should be 0x55,     result is 0x%02x\n", buffer [0]);
  memcpy (buffer, test4, sizeof (test4)); flip (buffer, 16); printf ("test4: 16 bits, 0xcafe,   should be 0x7f53,   result is 0x%02x%02x\n", buffer [0], buffer [1]);
  memcpy (buffer, test5, sizeof (test5)); flip (buffer, 17); printf ("test4: 17 bits, 0xcafe80, should be 0xbfa980, result is 0x%02x%02x%02x\n", buffer [0], buffer [1], buffer [2]);
  memcpy (buffer, test6, sizeof (test6)); flip (buffer, 18); printf ("test4: 18 bits, 0xcafe80, should be 0x5fd4c0, result is 0x%02x%02x%02x\n", buffer [0], buffer [1], buffer [2]);

  exit (0);
}