Spiffy Snippets

[linuxfood]

Everyone, I'm sure, has come across "Spiffy Snippets". That is, those pieces of short code that:

• Teach you something new
• Do something in a novel way
• Inspire new approaches to old problems

Snippets should be short, and accompanied with an explanation of what it does, why it works, and how you came to it.
If you don't know how it works, don't be afraid to post it. Posting a snippet that you don't understand will give people an opportunity to dissect it, and that way everyone benefits.
So, post your "Spiffy Snippet".

Mine is:

Code: Select all

uint32_t next_power_of_2(uint32_t x) {
  x--;
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x++;
  return x;
}

What it does:
Finds the next power of two, or returns x number if it is a power of two.

Why it works:
It relies on the base-2 nature of computation with computers.
The sequence of right shifts, and OR's results in every bit, upto (exclusive) the highest bit in x being set.
Then adds one more, to force a "roll over", to the next power of two (or your original number because of the initial x--).

Cheap diagram:

Code: Select all

starting x:
+-------------------------------------------------+
| ... | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
+-------------------------------------------------+
x--:
+-------------------------------------------------+
| ... | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
+-------------------------------------------------+
after shifts:
+-------------------------------------------------+
| ... | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------------------------------------------------+
x++:
+-------------------------------------------------+
| ... | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-------------------------------------------------+

How I came to it:
I was implementing a simple hash table, and wanted an "efficient" way of calculating the next power of two.
I was unsatisfied with the readily apparent approach which is:

Code: Select all

int y=log(x)/log(2);
y++; y=pow((double)y,2.0);

Because, well, it just wasn't cool enough. I also recall measuring and finding that log() was a large number of instructions.
I didn't find the code on my own, I was googling for alternative ways of calculating the next power of two when I found this.
I had to spend quite a few hours working it out on a whiteboard until I was confident I knew what was happening.

[earlz]

the thing that totally changed things for me was somethign like this:

Code: Select all

uint8_t *memory;

...
*(uint32_t*)&memory=0xBADA55;

which basically avoids my prior usage of temporary variables in order to do casting. I know its a very simple thing, but to new coders this can make life much much simpler.

Basically what it does it gets the address of the byte-addressed `memory` and then casts it so it is dword-address, and then dereferences that new dword-addressed pointer so that you can write a dword to a pointer that before you could only write a byte to.

[gravaera]

Hmmm...this is a bad thing to use habitually, and should only be used as a method to overcome design flaws (in a restrictive area of a language), such as the inabiliy to cast a C++ member Function pointer to a normal void * or uint32. In my interrupt Manager I used the following to get the absolute addresses of several member functions and store them in an array to be used elsewhere. I couldn't cast them to uint32, and I can't remember right now, but simply saving them in the array as member function pointers was going to be a design problem as well. So I used:

Code: Select all

__method_to_uint:
   push ebp            ; The stack frame may, of course, be omitted.
   mov ebp, esp
   mov eax, [ebp+8]
   mov esp, ebp
   pop ebp
ret

[NickJohnson]

Well, going in linuxfood's vein of bit twiddling via two's complement, I found this interesting operation/snippet:

Code: Select all

x&=-x;

It sets x to the lowest bit previously set in x. When x is negated, it inverts all the bits, then adds one. The lowest bit is the only one set in x and -x, due to the carrying. The string of zeros on the little end of the number causes a carry in the negation, clearing the space in -x where the zeroes were in x and setting the bit immediately to the left (which must be set in x, because it terminates the string of zeroes) which is the only difference between -x and ~x:

Code: Select all

x    = 00000001
~x   = 11111110
-x   = 11111111
x&-x = 00000001

x    = 00001000
~x   = 11110111
-x   = 11111000
x&-x = 00001000

x    = 10111000
~x   = 01000111
-x   = 01001000
x&-x = 00001000

It's not quite as useful as a log, but if you take the log of the output when x is incremented (a log that is simpler to calculate b/c it's a power of the base), you get a nice 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 etc. pattern that can be used to distribute things in nice proportions. Of course, I'm sure it has some other uses as well, perhaps in a cleverly constructed bit flag setup or something.

Edit: @gravaera:
Don't you think there might be a reason that you can't cast methods to pointers like you can functions? If it were as simple as that function (i.e. a cast), the compiler would probably let you do it. I don't use C++, but I'd guess it has to do with some OO-related stuff. I really wouldn't do that if I were you... you may be tying yourself down in terms of other C++ features (or just not reading the manuals correctly ).

[neon]

I suppose Ill add mine (in signature as well)

Code: Select all

char c[3]={"\x90\xC3"};
int main() {
   void(*f)()=(void(__cdecl*)(void))(void*)&c;
   f();
}

It was kind of a test to see if it was possible to execute an array as a function...it is

[Firestryke31]

Now you need to make it do SMC...

[Solar]

Not a snippet really, but my coding style changed significantly once I fully realized that the variables in the parameter list of a function are passed by value...

It's not much, and probably every compiler out there can optimize it away, but once I realized that, I saw many other ways to make code more compact - which, IMHO, also improved its readability.

Edit: And then I proceeded to paste comparative code snippets from my PDCLib and a couple of other libraries to prove my point. And found a bug in my code. So I hang my head in shame and, instead of posting "code brag", will return to the ole edit - compile - test cycle.

[tantrikwizard]

This one has several uses. I've used it in a point and sweep algorithm and some bitmap algorithms. It returns the number of bits that are set in the passed parameter;

Code: Select all

unsigned CountBits(unsigned num){
	num = (num & 0x55555555) + ((num >> 1) & 0x55555555); 
	num = (num & 0x33333333) + ((num >> 2) & 0x33333333); 
	num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F); 
	num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF); 
	num = (num & 0x0000FFFF); 
	return num;
}

[gravaera]

Edit: @gravaera:
Don't you think there might be a reason that you can't cast methods to pointers like you can functions? If it were as simple as that function (i.e. a cast), the compiler would probably let you do it. I don't use C++, but I'd guess it has to do with some OO-related stuff. I really wouldn't do that if I were you... you may be tying yourself down in terms of other C++ features (or just not reading the manuals correctly ).

I use it when I need to store an array of methods and export them, and I also find it useful for calling C++ class methods as IRQ routines. But you also need to keep a sort of...log of sorts containing a list of the kernel's classes, so that you can query the address of the object when calling the method. A C++ method requires a pointer to its object. I spent some time, and after some disassembling, I've discovered that the 'thiscall' convention is absolutely not standardized. But that's a digression.

Another thing I'm finding it useful for is API design: most applications are designed in C, and not C++, and are absolutely unaware that my kernel is composed of classes, and methods, and that their API calls are actually linked to functions in my kernel that require pointers to objects within the kernel. I've developed a very simple method for obtaining the 'this' pointer to any Kernel Aggregate Module using this function as well.

While it could be described as a hack method, I believe the reasons I've outlined at least excuse it, if not justify it. . And there's more stuff I need similar 'C++ transformation ASM routines' for. In order to ensure that my kernel is maximally efficient for API calls from C and C++ programs, and whatever is in between that's compatible, I also have several other slight hacks. The most important thing in my kernel is compatibility, and flexibility.

[NickJohnson]

@gravaera:

I see now: the compiler can't decouple a method from an object because the method needs to access the variables in the object as well. But I don't think it would be possible to use that technique if the method was in any non-singleton class... how would you choose which object it references? And if you are using/can use only singleton classes, why bother with making kludges to support OO at all?

The only realistic way I see to do this would be to have a structure or class that contains a void and function pointer that acts as a "method pointer", coupled with a modified version of your assembly routine. It would be slowish and take up twice as much memory though. The other problem would be that you would need a separate function pointer type for each method pointer type, and even with polymorphism that would be a drag if you want to use it in a bunch of places.

[gravaera]

And if you are using/can use only singleton classes, why bother with making kludges to support OO at all?

Not that I can't (by that I mean it's not impossible...for someone else more knowledgable. I'm sure JamesM and pcmattman manage fine in pedigreee) support inheritance/multiple inheritance, but it would be too complex for me at this point: both in the time factor, and in the technical knowledge and experience factor: the C++ This pointer radically changes from a simple pointer to a sort of index table when multiple inheritance and virtual functions are involved. And there's is NO standardization. Each compiler has its own method of doing the index table of base/super class pointers and...maybe you could try to asphyxiate your brain on it here: url=http://www.codeproject.com/KB/cpp/FastDelegate.aspx

But I've been prowling round the pedigree repository. I'm learning...