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");


}

A little fun with L1/L2/L3 cache RAM fetch speed

I know it has been a while since I've posted. And that's pretty much a reflection of being super busy as well as not having a little nugget at the tips of my fingers to post.

So I'm back.

I wrote the little program below to test the cost of fetching values from lookup tables of various sizes. Presumably this would show up in performance differences once the lookup table exceeds the size of the various cache it could easily fit within.

So, my little experiment went as followed:

Mad Cyclist on Hwy-101

OK, on 12/10 I saw something I would never expect to see on a freeway.

Leading into San Francisco from Silicon Valley (well the Peninsula actually) there was this crazy dude cycling and passing traffic on 101.

OK--it was stop and go kind of speeds, but what the heck! I've got to give this man credit for going for broke when even the most insane of us would say no thanks.

And here's one a little further on--notice that he's actually passing the slow lane:

Cycling from SF to Yosemite

OK, my oldest said I was mad, and she's right. But last week I ended up cycling for 2 days from SF up to Yosemite. It was one of those things that seemed doable knowing what it's like to ride longer distances, but still seemed daunting given the lack of ride support (disclaimer: I've done two double centuries but this was way different).

The hardest part of the trip was the climbing (no kidding), and the heat (turns out to have been over 100 on each day). As my friend texted me during the ordeal: loads of water, electrolytes, food.

The heat and hills combined to double team my sweat glands--you could almost just watch sweat pouring down my arms later in the day.

Getting my VM to talk to the office

Admittedly, without putting too much thought into this I expected to be able to configure a VM located on my home machine to connect to a work computer through an already established VPN tunnel without too much hassle.

Well, I ran into a couple bumps getting this system up and running. To be specific I needed sessions to be initiated from both directions (from work to the local VM, and from the local VM to work).

So, basically, the configuration looked like this: There's a VPN tunnel established between work and my home computer. On the home computer there's a VM that needs to reach a system at work, and the system at work needs to reach the VM at home.

Or similar to the illustration below:

So, I guess why I found this interesting is that it wasn't as simple as I initially thought. First stab was to set up the VM and bridging the network on the VM to the host systems interface. But the bridged VM ended up getting the dhcp advertised default route from my home router and therefore packets would not travel through the VPN tunnel. The routing table on the VM looks like (where 10.0.1.1 is the IP of my home router):

root@debian:~# ip route
10.0.1.0/24 dev eth0  proto kernel  scope link  src 10.0.1.48 
default via 10.0.1.1 dev eth0 

A little perl nugget: differences between two arrays

Something small, simple...

I have two perl arrays and I want to remove all elements in common between the two arrays, leaving only the elements in list_one that are unique to list_one.


For example pre-populate two arrays with the following values.

my @list_one = ();
push(@list_one,'a');
push(@list_one,'b');
push(@list_one,'c');

my @list_two = ();
push(@list_two,'b');

Setting up Perf for performance evaluation of your code

OK--some quick notes on setting up and running linux tools performance profiling (perf):

sudo apt-get install libelf-dev binutils-dev

wget http://www.kernel.org/pub/linux/kernel/v3.0/linux-3.0.4.tar.gz

tar xvfz linux-3.0.4.tar.gz

cd linux-3.0.4/tools/perf/

make

scp /usr/lib/libelf.so.1 [to-target-system]
scp /usr/lib/libbfd-2.20.1-system.20100303.so [to-target-system]


# sudo /opt/bin/perf 

usage: perf [--version] [--help] COMMAND [ARGS]

The most commonly used perf commands are:
annotate        Read perf.data (created by perf record) and display annotated code
archive         Create archive with object files with build-ids found in perf.data file
bench           General framework for benchmark suites
buildid-cache   Manage build-id cache.
buildid-list    List the buildids in a perf.data file
diff            Read two perf.data files and display the differential profile
evlist          List the event names in a perf.data file
inject          Filter to augment the events stream with additional information
kmem            Tool to trace/measure kernel memory(slab) properties
kvm             Tool to trace/measure kvm guest os
list            List all symbolic event types
lock            Analyze lock events
probe           Define new dynamic tracepoints
record          Run a command and record its profile into perf.data
report          Read perf.data (created by perf record) and display the profile
sched           Tool to trace/measure scheduler properties (latencies)
script          Read perf.data (created by perf record) and display trace output
stat            Run a command and gather performance counter statistics
test            Runs sanity tests.
timechart       Tool to visualize total system behavior during a workload
top             System profiling tool.

See 'perf help COMMAND' for more information on a specific command.



to run (C specifies which CPU, and p specifies which process to attach to):

sudo /opt/bin/perf record  -p 4040 -C 5
sudo /opt/bin/perf report -i perf.data