Tech Talk

I always considered myself a not-so-bad programmer, but I never have written my own algorithm for anything. Not to mean that I always lifted my code from somewhere, but almost always I would have coded some known algorithm to do the same work. You have pseudo codes in most algorithm text books.

Today, perhaps second or third time, I wrote my own algorithm to do a simple job: bit reverse an integer. It is a common thing in FFT implementations. In most cases, the bit reversal in FFT will use the block nature of FFT also. But my requirement is not in FFT. I looked around a bit and got quite a couple of links with working code. I ain’t linking them here.

Here is the snippet of code I wrote for this. I am not claiming anything by writing this code. Just that I spent a couple of minutes arriving at it. Its totally intuitive and “naive”, if you want to call it that.


int bitreverse(int val, int len) {
int i;
int br = 0;
for(i=0;i<len;i++) {
br += ((val&1) * ((int)exp2f((float)(len-i-1))));
val >>=1;
}
return br;
}


Image via Wikipedia

Yesterday was big disappointment. My python code was taking just too long to process a graph of about 30000 nodes and 80000 edges. Actually, it was taking more than an hour to just construct it. After that I have a bunch of algorithms to run on it. And this graph is generated from a sample graph of about 1024 nodes and edges. But in reality I need to run the whole thing against an initial graph of 20000 nodes. The whole thing just doesn’t sound to work. There are two possibilities: First is my code could be dirty; Or python does not do my kind of work very well. I can’t say anything about python until I have cleared my code to be the best. But I don’t have the time to invest here, since all this is just paths to my actual work, and my work is elsewhere!

So, the other choice is to code the whole thing in C/C++. Actually it should be C, because I am not a particular fan on C++. But given the time constraints, I just may have to go with C++. The reason is simple. I want something like STL to hasten my job and not worry about performance. I simply don’t see any such library for C. There are some ways to use STL with C, I guess. So, C++ it is. I should probably spend some time and write STL like library for C or at least spend some time to see if somebody is already doing the job. Anybody knows some good library for C, please leave a comment. Yeah, and don’t bother asking why I am not a fan of C++. I wouldn’t bother to reply.

This is an interesting learning in C today. With these new constructs, I am beginning to doubt if I know enough C at all. Anyway, I found the construct in a FFT code from this benchmarking suite. My sample follows.

#include <stdio.h>
#define cptr(p) check_ptr(p, #p)
check_ptr(void *p, char* pname)
{
if(p == NULL)
{
printf("Pointer %s is NULL.\n", pname);
}
else
printf("Pointer %s is valid.\n", pname);
}
int main()
{
char* a;
int b = 10;
cptr(a);
cptr(&b);
return 0;
}

And the output is

Pointer a is NULL.
Pointer &b is valid.

See the usage? Now if you already knew this, don’t bother letting me know.

Blogged with Flock

Tags: C, programming, flock, snippet

I was trying to compile and install pcb from source on my centos installation when I began running into all sorts of weird errors. The package requires to have gd library installed. I didn’t bother searching for RPMs and decided to install the library too from source. I guess that was where the trouble started.

The installation of libgd itself was painless. It would configure without errors or deps, compile and link also well. ‘make install’ seemed to work well too. It had copied the library to my prefix properly. But in all this, a rather simple regex-replace failed to work. I had not researched to where the failure happens (configure or install). The library creates a gdlib-config script that will be used by other libgd dependant packages for their linking and include referencing. This script seems to have used place-holders for detected libraries like @LIBICONV@ for libiconv. I don’t know if I have included iconv support. At least libgd didn’t seem to mind the absence. But inspite of not minding the absence, the place holder had remained in the script much to my annoyance.

While configuring pcb, it would complain that my installation of gd had no jpeg/png/gif support or my libgd was too old! Neither was possible : libgd was just downloaded from its hosting site; configure of libgd announced that I had configured to include jpeg/png and gif support in my compile. When I viewed the config.log for the causes, it would have failed because gcc would have a -l@LIBICONV@ flag and failed not finding the library. Well, quite obviously lib@LIBICONV@.so is not there on my machine.

I grepped the entire pcb source code to see where this particular library was getting referenced.. In vain. I reinstalled gd about three times. Funnily, each time I tried running gdlib-config but not ‘gdlib-config –libs’ even once!! After about six hours of fist-fighting with the machine, a round of cursing the pcb authors, centos maintainers, myself for being so oblivious of such ’simple’ things and another couple of hours later a little bulb flickered! I tried every option with gdlib-config command to find that gdlib was making such a ridiculous reference! Cursed myself another time for not trying hard enough and edited the gdlib-config shell script to remove the reference. Now pcb is all installed and working fine.

Ironically, this problem didn’t occur in the RedHat EL4 machine I tried to install pcb on. It did not have any -liconv, so @LIBICONV@ got removed somehow!

The other day I was writing my code to get the components of an IEEE floating point number. I wrote my own very long program doing all the binary conversions and all that. I know that was entirely unnecessary. But here I am with about 100 lines of code and had no clue how to check if I was doing it correct. So, I did a quick search to get some implementations of the same. This particular link got me thinking if there was more C than I had known.

I never knew I could have integes of specific bit widths! My test program initially had a union with a float and three characters. I had to set the float and read the characters. The traditional way and to get my result right, I had to do some masking, shifting and all that. This program works like charm and it taught me something.

At least that is what valgrind suggests. There are errors, and a lot of them, according to valgrind, but no memory leaks. I feel really good about this. It is a simple matrix related program. All it can do is just get the determinant value of a input matrix(-x+ces).  I will certainly not call it well written or effecient, but there is always a first step.