Saturday, April 19, 2014

Computing changed bits in a range of values

So, there's a reason to do this, other than just wasting CPU cycles. I need to take in a range of 2 byte values and compute a mask on all changed bits between the lower and upper value of this range.

The underlying reason is this allows for a quick match against network packet port ranges. So below I have a little test app that computes the changed bits given an arbitrary start stop value.

This ends up producing the following output:

slioch@slioch-All-Series:~/vyatta$ ./range 32076 62199
xxxxxxxxxxxxxxxx
slioch@slioch-All-Series:~/vyatta$ ./range 52076 62199
xxxxxxxxxxxxxx--
slioch@slioch-All-Series:~/vyatta$ ./range 62076 62199
xxxxxxxx--------
slioch@slioch-All-Series:~/vyatta$ ./range 1 2
xx--------------
slioch@slioch-All-Series:~/vyatta$ ./range 1 3
xx--------------
slioch@slioch-All-Series:~/vyatta$ ./range 1 4
xxx-------------
slioch@slioch-All-Series:~/vyatta$ ./range 1 1024
xxxxxxxxxxx-----
slioch@slioch-All-Series:~/vyatta$ ./range 1 1023
xxxxxxxxxx------

The "x" represents a bit position that changes, while the "-" represents a position that doesn't change. This ends up allowing for a quick comparison against a start-stop (or range) of values. Note that the representation above has the LSB (least signficant bit) on the left.



#include <string.h>
#include <strings.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <math.h>


#define NUM_BITS_FOUR_BYTES 32

static void
byte_to_binary(unsigned int *x, int num)
{
  unsigned int mask = 0x01;
  int z;
  for (z = 0; z < num; ++z) {
    printf(((*x & mask) == mask) ? "x" : "-");
    mask = mask << 1;
    if (z % NUM_BITS_FOUR_BYTES == (NUM_BITS_FOUR_BYTES - 1)) {
      mask = 0x01;
      x++;
    }
  }
}


/* 
   Calculate fixed/wildcards in ranges of numbers
   for binary representations.
*/
int main(int argc, char **argv)
{
  if (argc < 3) {
    printf("need start and end\n");
    return;  
  }

  long int start = strtoul(argv[1], NULL, 10);
  long int end = strtoul(argv[2], NULL, 10);
  if (end < start) {
    printf("Error in range\n");
    exit(0);
  }

  //now let's see compute all the bits changed in this range
  unsigned int i, accum = 0;
  accum = start ^ end;
  int loc = 32 - __builtin_clz(accum);
  for (i = 0; i < loc; ++i)
    accum |= 0x1 << i;
  byte_to_binary(&accum, 16);
  printf("\n");


}

No comments:

Post a Comment