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;
}


I came across this python parsing library called pyparsing through my adviser. The first thing I wanted to try implementing on this is a verilog parser. Actually, the site’ pages allows us to request a verilog parser from the author for non-commercial purposes. Anyways, thats not the point. I know and understand some verilog. So it makes more sense for me to try a verilog parser first. I have my parser for structural verilog using this module in my pbwiki page. It cannot handle many cases yet. But I took about an hour to get that code done. I spent about a day or two trying to figure out pyparsing itself. The documentation is fairly good. There are some interesting code snippets and howto in the pyparsing wiki page.

Now I am writing a full fledged verilog parser using this module. I’ve not requested for the author’s script yet. Maybe I’ll do that once I complete to figure out how good I am in using this library. And the full semantic/syntactic specification is available in IEEE explore and in Samir Palnitkar’s book on verilog HDL. I am not sure how much time I can devote to this, so it could be some time before I’ve followed this up. Meanwhile you might want to check the various samples in the pyparsing wiki.