Archived

This topic is now archived and is closed to further replies.

jediknight219

How's this for cryptic, uncommented code

Recommended Posts

I needed a gcd function, so I quickly hacked out this one. Then I looked back at it and was glad I knew how it worked, because it looked pretty arcane for something so simple. What does everybody else think?
int gcd(int x, int y) {
	if(x < 0) {
		x = -x;
	}
	if(y < 0) {
		y = -y;
	}
	if(x == 0) {
		return y;
	}
	if(y == 0) {
		return x;
	}
	while(true) {
		if(x > y) {
			x = x % y;
			if(x == 0) {
				return y;
			}
		} else {
			y = y % x;
			if(y == 0) {
				return x;
			}
		}
	}
}
  
[edit]Ok, fixed the divide by zero problem.[/edit] [edited by - jediknight219 on October 31, 2002 11:54:15 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It''s not bad really, pretty easy to follow. I guess it depends on how much nasty code you have had to wade through .

Share this post


Link to post
Share on other sites
Yeah, that''s not too bad, here''s a few lines of my worst. I really should go back and comment this so I can remember what it does

rotX = animationArray[activeAnimation].frameArray[animationArray[activeAnimation].activeFrame].rotationArray[ID].x + rotX;
rotY = animationArray[activeAnimation].frameArray[animationArray[activeAnimation].activeFrame].rotationArray[ID].y + rotY;
rotZ = animationArray[activeAnimation].frameArray[animationArray[activeAnimation].activeFrame].rotationArray[ID].z + rotZ;
deltaRotX = rotX - animationArray[activeAnimation].frameArray[animationArray[activeAnimation].activeFrame].rotationArray[ID].x*(1-fraction);
deltaRotY = rotY - animationArray[activeAnimation].frameArray[animationArray[activeAnimation].activeFrame].rotationArray[ID].y*(1-fraction) ;
deltaRotZ = rotZ - animationArray[activeAnimation].frameArray[animationArray[activeAnimation].activeFrame].rotationArray[ID].z*(1-fraction) ;


________________________
Grab your sword, and get prepared for the SolidSteel RPG engine, coming soon...(i.e. when it''s done)

Share this post


Link to post
Share on other sites
I imagine that the function would be hard to understand if you didn''t know the Eulerian method for computing the GCD. In terms of coding style, it seems fairly good.


Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
Here's an obfuscated Eulerian GCD function for ya :-D


#DEFINE a(x) (((x)>0)?x:-x)


int gcd(int x,
int/* O O */y){
x=a/* */(x)
;y=/* \____/ */abs
(y);while (x*y){if
(x<y) swap (x,y)
;x=x%y;} return x?x:y;}



Don't listen to me. I've had too much coffee.


[edited by - sneftel on October 31, 2002 12:52:20 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Amnesty
OP: Thats not bad at all. Quite easy to follow. In fact, i would say that code is very readable.

To Cold_steel: Good God



The scary thing is, I've seen much, much worse! I was playing some game, and an error occurred and some debug output popped up with the call that caused the error. Anyway, I have never seen so many ->'s in my life. Honestly there must have been at least 10, any maybe more.

Something->SomethingElse->MoreStuff->anotherThing->YetMore->AndAgain->andAgain->something();

Only worse
I really should just copy the rotation vector and get rid of those horendous 6 lines of code. It's got to be hurting performance Screw it, I'll optimize it later

________________________
Grab your sword, and get prepared for the SolidSteel RPG engine, coming soon...(i.e. when it's done)

[edited by - Cold_Steel on October 31, 2002 12:22:17 AM]

Share this post


Link to post
Share on other sites
Numerical double integrator
Implementation of properties in standard c++.

And my gcd can beat up your gcd:

  
int gcd_of_evil(int a, int b)
{
while (true) {
if (a > (b << 2))
a %= b;
else
while (a >= b) a -= b;
if (!a) return b;
if (b > (a << 2))
b %= a;
else
while (b >= a) b -= a;
if (!b) return a;
}
}

Share this post


Link to post
Share on other sites
I also thought about doing it this way. It looks clearer, but you get the overhead of the recursive function calls.


int gcd(int x, int y) {
if(x < 0) {
x = -x;
}
if(y < 0) {
y = -y;
}
if(x == 0) {
return y;
}
if(y == 0) {
return x;
}
if(x > y) {
return gcd(x % y, y);
} else {
return gcd(x, y % x);
}
}

Share this post


Link to post
Share on other sites
Wow... While it''s easy to follow, you''re wasting a lot of effort.


  
int gcd(int a, int b)
{
if (a < 0) a = -a;
if (b < 0) b = -b;

if (a < b)
{
int t = a;
a = b;
b = t;
}

while (b > 0)
{
a %= b;
int t = a;
a = b;
b = t;
}

return a;
}


If you just make sure a >= b before going into the loop, you can make it a loop invariant which leads to less code. And given that it''s all going to be in registers anyway, execution speed should be the same.

Share this post


Link to post
Share on other sites
quote:
Original post by jediknight219
I also thought about doing it this way. It looks clearer, but you get the overhead of the recursive function calls.



Any compiler worth its salt is able to optimize tail-recursion and turn int into an iterative solution.


int gcd(int x, int y) {

if( !x ) return y;
if( !y ) return x;

x = abs( x );
y = abs( y );

if( y < x ) std::swap( x, y );

return gcd( x % y, y );
}



Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]


[edited by - Fruny on November 1, 2002 1:56:01 AM]

Share this post


Link to post
Share on other sites
How''s this?

bm FillUpOccluded (bm b, bm c)
{
b |= (b << 8) & c;
c &= (c << 8);
b |= (b << 16) & c;
c &= (c << 16);
b |= (b << 32) & c;
return b << 8;
}

or...

bm Fill8 (bm b)
{
return ((b >> 17) & 0x7F7F7F7F7F7F7F7F) | ((b << 15) & 0x7F7F7F7F7F7F7F7F) | ((b >> 15) & 0xFEFEFEFEFEFEFEFE) | ((b << 17) & 0xFEFEFEFEFEFEFEFE) | ((b >> 10) & 0x3F3F3F3F3F3F3F3F) | ((b << 6) & 0x3F3F3F3F3F3F3F3F) | ((b >> 6) & 0xFCFCFCFCFCFCFCFC) | ((b << 10) & 0xFCFCFCFCFCFCFCFC);
}

Can you figure out what those are supposed to do?

Share this post


Link to post
Share on other sites
quote:
Original post by c_wraith
Wow... While it''s easy to follow, you''re wasting a lot of effort.


I''ll go ahead and acknowledge that I don''t know the first thing about optimization (and very little about x86 assembly). But I was (probably erroneously) thinking that doing the swap would give three assigns that I could avoid.

quote:
Original post by Fruny
Any compiler worth its salt is able to optimize tail-recursion and turn int into an iterative solution.


Ooh nifty. Makes sense though.

Share this post


Link to post
Share on other sites
Cold_Steel:

I think that game with all the "->"s was Unreal Tournament. First time i saw it, I thought it was a list of indirections. However, after crashing a few times with UnrealEd, I understood that it''s not real indirections, but a function history, such as:

***GameLoop()->Render()->RenderObjects()->RenderObjectModel()->CalculateMatrix()->CalculateOriginMatrix()->CalculateOriginMatrix()->ConvertOriginToPosition()->GetFullMatrix()

These few lines being an excerpt of a log from my FULLY LOGGED 3D engine, "Extatica" (evil pimpage).

Extatica is coming soon!
Check it out on:
http://www.extatica.com02.com
Nexeruza Studios:
http://nexeruza.ionichost.com/home.html

Share this post


Link to post
Share on other sites
quote:
Original post by jediknight219
But I was (probably erroneously) thinking that doing the swap would give three assigns that I could avoid.


True, it would. But assigns are fast (since your variables will all be in registers). Branches are sloooooow.


Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
quote:
Original post by Fruny
Any compiler worth its salt is able to optimize tail-recursion and turn int into an iterative solution.


Yes, but where does it jump back to? I remember looking before, but forget what the answer was... I strongly suspect that it will jump back to the very top (into the prolog code) of the function and push more crap onto the stack. Considering it''s a gcd function, this could be considerable overhead where you don''t actually need the previous result. If you''re really interested, do an asm dump and see where it jumps to (and remind me ).

Hey Russell, unless bm is an __int64 (or bigger), the results of b<<32 are undefined.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Any function of the form:


  
int f(int a)
{
if (base condition)
return literal;
else // implied non-base condition

return f(some computation based on a);
}


Should roughly translate into:


  
int f(int a)
{
for (;;) {
if (base condition) {
a = literal;
break;
} else { // implied non-base condition

a = some computation based on a;
}
}

return regret;
}


Or in x86 ASM:


  
;; eax contains a
.globle F

F: cmp eax, something
je BASECASE
RECCASE: mov eax, something
jmp F

BASECASE: mov eax, something
ret


Man my ASM sucks. Anyways, my point is that it won''t jump back to where it tries to push the values onto the stack, or at least it shouldn''t. For the given gcd function it would probably put the x = abs(x); inside the loop though.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Actually:


  
int f(int a)
{
for (;;) {
if (base condition) {
return literal;
} else { // implied non-base condition

a = some computation based on a;
}
}
}


I shoudl think things through before I post them.

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
Hey Russell, unless bm is an __int64 (or bigger), the results of b<<32 are undefined.


It''s not undefined...hint, hint Notice all of the hex values are also 64-bit.

Actually what they do are generate bitmaps (bm) containing legal moves or attacks in a game of chess. It would probably be more clear if I named the function FillUpOccluded(bm b, bm c) to something like RookAttacks(bm rooks, bm empty). So if you have a bitmap (64-bit value) where each bit is answers a yes/no question, you have the following bitmaps:

bm rooks: Is there a rook on this square?
00000000
00000000
00000000
00000000
00000000
00000000
00000000
10000000

bm empty: Is this square empty?
11111111
11111111
01111111
11111111
11111111
11111111
11111111
01111111

Then FillUpOccluded returns the following bitmap, answering the question "Does a rook attack this square?"

00000000
00000000
10000000
10000000
10000000
10000000
10000000
00000000

And then I have one that generates horizontal attacks, diagonal attacks, etc. The other function (Fill8) generates knight attacks. These become very useful. If you want to generate only captures, you simply AND this resulting attack bitmap with a bitmap for "all black pieces" and you''re set. These algorithms are variants of a kogge-stone parallel prefix algorithm. The cool thing is that if there are two rooks on the board, this algorithm will generate an attack bitmap for both rooks in parallel. Using this bitmap approach rather than an array offset approach (like int squares[64] for the board, or whatever) is very cool and allows for many such parallel operations, but I imagine it would be hell trying to figure out what the code did with no documentations or good function names. I changed the names of my functions BTW, because "KnightAttacks" might have given it away

Russell

Share this post


Link to post
Share on other sites