Coding Question

[pgrmdave]

While reading the source code (in C) to Rogue, I came across this block:

 

if (rand_type == 0) {
	i = state[0] = (state[0]*1103515245 + 12345) & 0x7fffffff;
} else {
	*fptr += *rptr;
	i = (*fptr >> 1) & 0x7fffffff;
	if (++fptr >= end_ptr) {
		fptr = state;
		++rptr;
	} else {
		if (++rptr >= end_ptr) {
			rptr = state;
		}
	}
}

 

Can anybody explain the use of the '&' in this context?

[Buffy]

Yep. Its a "bitwise-and". The statement takes that state variable (a seed it looks like), multiplies it and adds to make it more pseudo-random, and then the bitwise and lops the top 4 bits off of the resulting long integer....

 

Cheers,

Buffy

[Buffy]

Oh I guess I should explain this "a bit" more: bitwise operations work on data by allowing operations on each individual bit. Put your hex hat and grok these examples:

• 0xFFFF & 0x00FF = 0x00FF
  
• 0xFFFF & 0 = 0x0000
  
• 0xFFFF | 0x00FF = 0xFFFF (bitwise-or)
  

 

Binarily,

Buffy

[Buffy]

And the real reason you use them (and you'll see a lot of this in the rogue/hack source as well as a lot of BSD code), is to pack a bunch of booleans into a small space. In Rogue, I'm pretty sure that all the scrolls, potions, etc are each stored in a single variable:

#define ICE_STAFF 0x0001
#define FIRE_STAFF 0x002
#define SPEED_STAFF 0x004

#define CUREALL_POTION 0x0002
...
int staffs;
int potions;

if (staffs & ICE_STAFF) {
  freeze(troll);
  if (badluck)
     potions = potions & ~CUREALL_POTION; /* takes it out of your bag */
}

 

That last line is because the "~" bitwise operator inverts all the bits so:

   x = 0x000f;
   y = ~x;
   /* y is now 0xFFF0 */

 

Hack, hack, hack,

Buffy

[pgrmdave]

Buffy, you're my hero. :naughty:

[Qfwfq]

and then the bitwise and lops the top 4 bits off of the resulting long integer....

When I read that I thought :naughty: and felt like a jackass for having though the (one) highest bit but, no, your a deceiver Buffy! And even if the top byte weren't 7f but 07 then it would be 5 bits, not 4.

:)

[Buffy]

but, no, your a deceiver Buffy! And even if the top byte weren't 7f but 07 then it would be 5 bits, not 4.

I was lazy once and then devious: I didn't bother to count the F's and I *can* tell you that that code is *unbelievably* sloppy, so having 0x7... at the top could easily have been an odd hex digit, and should have been more correctly written 0x07, but I was too lazy to count all those ffffs...I bet on the fact that I know how these lazy folks used to code and just assumed! :naughty: Then I was devious: if you were watching closely I originally put in "5 bits", and then later edited it to "4 bits" to see if you or one of the other closet hackers here would notice. You get a cookie Q!

 

Devil in the details, :)

Buffy

[Buffy]

Buffy, you're my hero. :)

Thank you! Tell you friends in your game programming class I said "hi!"

 

Cheers!

Buffy

[Buffy]

Oh and Q (or anyone else who wants to play), I'll give you 18 hours to find the other *massive* error in the code in #4 above that will cause the code to fail...

 

Another cookie is riding on this one.

 

Survivors ready [flips arms], go!

Buffy

[Qfwfq]

I *can* tell you that that code is *unbelievably* sloppy, so having 0x7... at the top could easily have been an odd hex digit, and should have been more correctly written 0x07, but I was too lazy to count all those ffffs...I bet on the fact that I know how these lazy folks used to code and just assumed! ;) Then I was devious: if you were watching closely I originally put in "5 bits", and then later edited it to "4 bits" to see if you or one of the other closet hackers here would notice.

Ooooooooooh, Buf, when I read his question, "Can anybody explain the use of the '&' in this context?" I simply switched my parser to scan-for-ampersand mode and didn't notice the terrible sloppiness. Not that unsloppiness is a guarantee without counting, or selecting pairs or fours like I usually do... I was then grinning widely at the prolixity of your replies :evil: but I didn't notice that fledgling 5... ;)

 

I will take the #4 challenge though, in some spare moment when I can figure out the logic of it... :eek2:

ctrl-C, ctrl-V into UE-32...

[Qfwfq]

Hmmm, the bits get filled in, no problem, the only suspiscious things I see are not using an unsigned type with this sort of bit trickery (but I don't see where it'll make that simple stuff fail) and the lack of () in #defineing number literals which can cause unexpected results after preprocessing, perhaps even in the case of ~CUREALL_POTION but I'm not sure 'cause I never get these details straight I simply try to remember avoiding them.

[Buffy]

In spite of his lack of certainty, Q gets the prize. Yes, not making those ints unsigned causes you a problem with many--but not all--compilers which can start having fits when you do any bitwise operations on signed types. Even if not caught at compile time, some code will cause the CPU to do a hardware overflow when the top bit gets set/unset....

 

Oh and my reference to "the code being sloppy" was not a reference to the fragment that dave quoted, but that in general, the rogue/hack code and a surprising amount of the BSD code is pretty darn sloppy (written by grad students with little sleep and not enough Top Dogs in them)

 

Choco chip or Oatmeal, Q?

Buffy

[alexander]

oh that code could potentially be exploited too, if you were to attatch to the process and undefine ICE_STAFF, that would cause that if statement to become false no matter what you do and allow you to use your staff as much as you want without it ever being taken out of your bag.... theoretically....

[Buffy]

if you were to attatch to the process and undefine ICE_STAFF.... theoretically....

Most compilers in production mode would do all the #define subtitutions at lex or parse time (as is actually specified by the original C spec), and the value might end up as inline code (not on the stack, not in static data space, right there on the And instruction as a constant value), so you'd have to find the exact instruction and change the fixed value. C is sooooo much more primitive than most languages people are used to using....

 

There *are* obviously exploits though, and alexander is the man to find them! :)

 

C is Zen,

Buffy

[Qfwfq]

Certainly Alex, the #define has nothing to do with runtime because it is a preprocessor directive which, by definition, means it has effect before the actual compiling. C ain't Perl.

 

Yes, not making those ints unsigned causes you a problem with many--but not all--compilers which can start having fits when you do any bitwise operations on signed types. Even if not caught at compile time, some code will cause the CPU to do a hardware overflow when the top bit gets set/unset....

Oats will be fine for an old horse, thanks, but a correct, proper compiler won't give any error for bitwise operations on signed types, one is perfectly free to do it and must only mind that >> will preserve the sign, top filling with bits equal to the topmost one. In short, it divides by 2^n for both signed and unsigned integral types. This simply might not be what one is expecting when the intent is flag manipulation. C is mathematically consistent.

 

A compiler that gives trouble with bitwise operation is lousy IMHO. Here's a cookie up for prize: declare a and b of a same integral type, you must exchange their r-values but you don't want to use a third l-value. How can you do so?

 

Here's another cookie up for prize: I've been working with an absolutely lousy compiler on Unix (native compiler of AIX version 5.2, IBM, and I've found other quirks with it) and I'm bashing my head against the following wall: I realized yesterday that an improvement I made to a numerical calculation method fails due to an unbelievable thing in the following code frag:

	if(condition){
		double t, dr = 0, s = 0;
		for( i=1L, j=(DRES->dim)/2L; i<(studio->num_nodi); i++, j++ ){
			t = DRES->ve[i - 1] = P->ve[i] - V->ve[i] * sigma_p( i, MY, AY, D, V ) - RES->ve[i - 1];
			printf("n%d DRES %f RES %f", i, t, RES->ve[i - 1]);
			dr += t*t;
			t = DRES->ve[j] = Q->ve[i] - V->ve[i] * sigma_q( i, MY, AY, D, V ) - RES->ve[j];
			printf("n%d DRES %f RES %f", i, t, RES->ve[j]);
			dr += t*t;
			s += DRES->ve[i - 1]*RES->ve[i - 1] + DRES->ve[j]*RES->ve[j];	/* s = RES*DRES; dr = |DRES|^2 */
		}
		if(dr){
			s = s/dr;
			printf("ns = %fn", s);
			/* use of s */
		}
	}

the final s value is systematically 1.000000 and the other two diagnostic printf() calls tell me that the results of:

= Q->ve - V->ve * sigma_q( i, MY, AY, D, V ) - RES->ve[j] and the other, are as if they were exactly:

= RES->ve[j and i - 1] regardless of the values of those expressions which are all of type double (Meschach library). I called the Ghostbusters and I've been trying various breakdowns of the arithmetic and I even tried declaring those vars local to the whole function instead of to the if() block, but I still haven't got it figured out...

:confused: :confused: :confused: :confused: :confused: :confused: :confused: :confused: :confused: :confused: :confused: :confused: :confused:

 

Oh and my reference to "the code being sloppy" was not a reference to the fragment that dave quoted, but that in general, the rogue/hack code and a surprising amount of the BSD code is pretty darn sloppy (written by grad students with little sleep and not enough Top Dogs in them)

What you call sloppy code is what I call :evil: code. The thing I like about C/C++ is :cool: what can be done in an expression. Have you ever used the ? : operator as an l-value? :hihi: Ra doesn't let you do that.

[alexander]

My b, i was thinking of an interpreted language while talking about a compiled one, i mean as Buffy says, you can still do it by searching for that value in memory and replacing it with another one, but that is a bit of an overkill for trying to cheat, but then again there are some people.....

 

Have you ever used the ? : operator as an l-value?

people need their hands slapped for doing that.... and yet again there are some people....

 

could you post some more code or initial conditions of values going into the function and possibly some output, but try to separate your assignment statements, i've seen crazier results on some compilers for that before, oh alsoseparate out your sigma function call from the expression, other then that, need to think about it more, that compiler is crazy though, for example i know that on some compiler for AIX you can not reference a character to a bit, you can declare a character which is a bit, but for some reason or another can not reference it to one... so some of that would not be the craziest stuff i've seen before...

[Qfwfq]

Don't worry Alex, I finally got it working fine. Thanks for comfirming that this compiler is lousy, but you sure ain't gonna slap my hands for doin' absolutely :tongue: things... :xx:

 

I had already tried breaking down the line with sigma, in a way that, you never know, maybe even Buffy and Edsgar might even approve of :circle: get a load of:

       a = P->ve[i];
       b = V->ve[i] * sigma_p( i, MY, AY, D, V );
       c = RES->ve[i - 1];
       t = a - b;
       DRES->ve[i - 1] = t - c;
       printf("nDRES %f = %f - %f (%f) - %f", DRES->ve[i - 1], a, b, t, c);
       t = DRES->ve[i - 1];

Notice a - b and then - c separately! Anyway this morning I saw DRES was coming out right and I even tried putting it back the way it was before but there was still the s value bug. Look at the code now, that works right:

   if(correzione){
     double t, c, dr = 0., s = 0.;
     for( i=1L, j=(DRES->dim)/2L; i<(studio->num_nodi); i++, j++ ){
       c = RES->ve[i - 1];
       t = DRES->ve[i - 1] = P->ve[i] - V->ve[i] * sigma_p( i, MY, AY, D, V ) - RES->ve[i - 1];
       printf("nDRES %f RES %f", t, c);
       s -= t*c;
       dr += t*t;
       c = RES->ve[j];
       t = DRES->ve[j] = Q->ve[i] - V->ve[i] * sigma_q( i, MY, AY, D, V ) - RES->ve[j];
       printf("nDRES %f RES %f", t, c);
       dr += t*t;
       s -= t*c;  /* DRES->ve[i - 1]*RES->ve[i - 1] + DRES->ve[j]*RES->ve[j];	s = -RES*DRES; dr = |DRES|^2 */
       printf("ns = %f dr = %f", s, dr);
     }

with the original expression for s left in comment. I put the sign back to the original - because it was right, it was the compiler, not me, that was getting the sign of s wrong. Apart from this it was formally correct but the compiler was written by drunkards. It works and it improves convergence, now I'll be studying some rapidly divergent cases that become non-divergent but not convergent.

 

Anyway, I get one of my own cookies, who gets the other?

 

Hint: how do you put the two r-values into the same l-value?