Effective Java 2nd edition blurb:

I just bought this book because the effective c++ book was an awesome book for me. Granted, they’re by different authors but I’m going for the brand “Effective *blah*.” And gleaming the book so far I think the Java book lives up to the Effective brand.

Effective C++ blurb:

Alright, I’m on item #30, so I’m more than half way through the book. It’s REALLY easy read. Nothing too complicated or mind bending here. But it’s tremendously helpful, a very nice review, and reminder of c++’s ‘complications.’

I will come back to talk about this more tomorrow.

A few things before I go:

* Member variables all private:
Hmm, once a ‘guru’ c++ guy that I worked with said this: “What the hell are privates for? Just use protected.” (Full disclosure: He was a really good programmer, better than me. I wrote some crazy code… So I have no right to say anything. Mind you I’ve learned my lessons. I’m constantly trying to improve!) Well, the argument is that both public and protected do not adhere well to encapsulation. I usually tries to use privates that I believe fit a certain situation. I usually leave member variables protected if I feel that child-classes may have some need for a variable. And the rest private if I feel that they should be private from child-classes. But the author’s argument for private members is sound. If child-classes need to have access to base-class member variables then perhaps one need to think hard about the design.

After all, one needs to design the classes by designing them as TYPES. This brings me back to my algorithm class oh so long ago… The abstract data-types. So one should design one’s classes as TYPES that are as good as the build-in types. A corollary of this is to have the so called “namespace organized functions” that operate on these types, to further encapsulation.

*Exception Safe design:

To me this is somehow linked to the concept of invariant based programming. And also the concept of programming by contract (e.g. pre/post-conditions.)

…

Now, I just need to put these concepts into practice. As the saying goes, *engage brain before pencil*. Haha.

Effective C++ blurb:

I finally went out and got one of “the” c++ book that every c++ programmer should have on their desks. C++ as a language is unforgiving; it’s the language that allows the programmer to easily shoot one’s self in the foot, due to the myriad ways of doing things, and the kaleidoscopic amount of options. Effective C++ effectively helps the intermediate C++ user to safely navigate the jungle and trap is the powerful and dangerous computer language known as C++.

Thank god there is effective c++ for a noob such as myself. Now, don’t get me wrong, I’ve programmed my share of C++ programs , and read my C++ references, but I’ve yet to truly master it, since C++ is so difficult. The purview of effective C++ is a collection of best practices for someone who is comfortable with all the features and syntax of the language, but who yearns to be a true master. The book is divided into a series of items, with each items examining a particular aspect of c++, and it’s connections to other “items” of c++.

Going over the items in the content, I recognize many, plus quite a few that I’m not too familiar with. To effectively recognize some of these items one should have gotten it by learning the language, or from “doing” the language. However, the point of interest for me is not that I recognize the items but that I truly master and wholly comprehend the content of these items. To have someone who is is both knowledgeable (i.e. PH.D) and experienced (a master) to put their mastering of a subject beautifully laid out and written on a page, is to help one get closer to achieving the goal of becoming a master. That is, the book’s items bring to the forefront those things that you may vaguely be aware of (with respect to the programming language) and uses but in a way that fully analyzes these concepts in glorious and rigorous detail. And many of the concepts presented in the book one should have some exposure to in a course on Programming Languages taken in college, but the book effectively brings them forward in the light of the concreteness of C++. If not that, it’s a GOOD review!

I truly want to master the art of programming. I view it something that is art which is framed in the frame work of rigorous math and engineering. (In other words I probably need to get a girlfriend, lol). I like to think myself as both a master craftsman and a master artist similar to those of time long past (oookkkayy). And to put it into Eastern philosophical terms, I want to feel the Tao and Zen (my gawd you are stretching it today bud) of programming. But what I really want to do is to make programs that DON’T FREAKING CRASH and is easy to maintain. So Effective C++ effectively brings me one step closer to this goal (and some may argue one step closer towards total insanity.) (Another way to describe it is … it’s Science. It’s something that has a definite set of rules, yet these rules have a myriad of exceptions…So one have to constant experiment, to constantly update one’s purview of the world, to improve!!!)

Effective C++ is a piece to a giant puzzle, the art and craft that is applied Computer Science (by applied CS I mean doing a job that people are paying you for), in the sense that it helps one to master one particular aspect of that trade, namely C++. Together with say study of algorithms, discrete math, (speaking of which, I think I need to buy Art of Programming by Knuth) plus software engineering, combined to form the key which solves this huge yet interesting piece of machinery. (I realllllllyyyyyy need a girlfriend, HAHA. Let’s also see how you feel after 30 years in the field).

I wholly recommend the book.

(Seriously. Maybe many of the things I said above is BS. But really it IS ART. There are the rules, the theories, and then there is reality. The reality is that you have to take in each moment at hand and try to apply everything you’ve experienced up to this moment, in order to “live” in the moment. But you can’t ‘over think it,’ because the moment is so brief, so if you try to ‘chase’ after it you will never get it. So you just have to be yourself and give it all you got! I’m a ZEN master baby… Not.)

Some more on Geometry Image

Okay, so I’ve finished reading the Geometry Image paper. Links:

http://www.google.com/search?hl=en&fkt=505&fsdt=4659&q=geometry+image&btnG=Google+Search&aq=f&oq=

Hmm, now after reading, this is definitely something going on the back burner. I WILL eventually implement this, but just not now.

Another method of course, is to just use regular UVW mapping. It works the same way, I believe. For each imposter views I store the UV texture coords which maps into a texture map, plus a normal map. Of course, I need to think more about the details of how this is going to work exactly. But in general I think the method I outlined so far should work. Again, this is definitely something for the back burner.

What I’m focusing on now is to compress my imposter images. Currently, each of my imposter views is a 128 by 128 texture. This is wasteful, since the actual extent of the imposter object only takes up a small percentage of this texture. Thus, I need to come with a scheme so to minimize the area wasted. My thoughts as of now is to project the extent of each object, to figure out the extent, then from this extent get rid of all the wasted space. Another route is to use an optimization algorithm.

Once we get rid of the space, we still need a scale factor, in order to determine the extent of each individual imposter in the larger imposter texture (which contains all imposter views). In order to properly scale the billboard texture coordinates so I can access the correct imposter view, depending on the view direction. I can store this in an array of uniform shader variables, to be used in my fragment shader that renders the imposter.

But this means that the extent of each imposter view must be constant per a single phi value (the imposter views  are arranged vertically based on PHI). So the factor will be determined by the largest extent per row of phi value. Another route is storing the extent data in the first pixel of each imposter view. This is workable, and would allow arbitrary imposter extents, but at the cost of doing a texture read for this value…I’m probably going to implement it both ways to check it out.

Project Zombie imposter shader effects

So I finally fixed some bugs with my imposter renderer. Now it works great. I also put in some simple Phong shading.

I have several options for doing lighting:

1.

Store normal data along with the imposter texture. This is workable, but not memory efficient. This option would look great though. (This may actual work in the end. I still have not thought much about compression schemes for imposter textures).

2.

Chi Ting Lighting ™. Yes, this is what I have implemented, and is probably what I will go with in the end, if option 3 does not work out. Basically, I’m using a sphere to approximate the shape of my imposter object. I sample this sphere based on the texture coordinate (i.e. theta and phi values). So that, every pixel is shaded based on this sphere. Sort of like hemispheric lighting… An improvement to the current method is to compute some factors, such that, using these factors I can get a better sample, e.g. finding bounds for each imposter view angle and map this bound to a best fit spherical theta and phi range. This brings me to option 3…

3.

Use fancy mathematics ™. That is, find some sort of mathematical function that approximates the shape our object, and then sample from this function. Of course, any storage used for this function should be less than required for the normal option. Think spherical harmonics type stuff… I am not saying spherical harmonics will be the solution here, but I take my ideas from that- some special function to represent data.

Zombie “smooth wandering.” (randomly)

Right, I mentioned in an earlier post that I need my Zombies to wander randomly. However, if I simply randomly change the orientation the behavior would be similar to random walk. I.E. changing of orientation would not be “smooth.” So we need some sort of interpolation. First, I only need one degree of freedom for this sort of orientation, e.g. yaw. Secondly, I don’t need much precision, since the plan is to smoothly interpolate between orientations. So, some preliminary brainstorm suggests that I can pack a 2d vector (on the xy plane) into a 32bit float. That leaves me with 3 free floats left, which I can use to store interpolation offset. This leaves me with the question of “uniform smoothness” during orientation interpolation. I do not want to use quaternions since I only require a single degree of freedom. Perhaps I can store a single float “theta factor,” and interpolate this theta (i.e. X = cos(t)i + sin(t)j).

Edited:
Maybe I need to give some more thoughts into this. Smoothly interpolating orientation is fine, but we also need to think about the rate of this rotation. THis probably will be a randomized factor also. I don’t EVERYTHING to have smooth rotation, some need to arbitrarily change directions. Yeah, I think randomness will be fine. Just have to have some sort interpolation tho, so you won’t have TOO abrupt of a change.

MD5GPU reloaded (and debugged):

It’s working now. I haven’t tested it with DIEHARDER yet, I may do it later, when I have time. But if it looks like white noise, walks likes whitenoise…

BTW, the author’s (of the paper) optimization works fine. Realy, think about it, why wouldn’t it work? It’s still rotating, that’s all matters really.

I’m going to start working on the agent simulation part of PZ.

#extension GL_EXT_gpu_shader4 : enable
//This function initializes the 512bit data according to the MD5 spec.
//Such that, the first 128 bit is the input;
//we also xor these 128 bits with the key, which can act like a seed value.
//And the rest up of the 12 32bit data blocks are filled
//according to the md5 spec, in order to pad our data to 512 bits.
//block 0-3: input xor with key
//block 4: 0x80000000. This correponds to append 1 bit to block 0-4.
//block 5-13: 0. This corresponds to appending zeros up to 448 bit.
//block 14-15: 0x0000000000000080. This correspond to the bit length of the input (128 bit), as a 64bit
//litten endian.
void setupInput(in uvec4 input, in unsigned int key, inout unsigned int data[16])
{
	data[0] = input.x^key; data[1] = input.y^key; data[2] = input.z^key; data[3] = input.w^key; //xor base with key
	data[4] = 0x80000000u;
	data[5] = 0u; data[6] = 0u; data[7] = 0u; data[8] = 0u;
	data[9]=0u; data[10]=0u; data[11]=0u; data[12]=0u; data[13]=0u;
	data[14] = 0x00000000u; data[15]=0x00000080u;
}
//initialize to the 4 hexes.
uvec4 initDigest()
{
	return uvec4(0x01234567u,0x89ABCDEFu,0xFEDCBA98u,0x76543210u);
}
//F compression functions
//(b & c) | ((not b) & d)
unsigned int F0_15(in uvec3 tD)
{
	return (tD.x & tD.y) | ((~tD.x) & tD.z);
}
//(d & b) | ((not d) & c)
unsigned int F16_31(in uvec3 tD)
{
	return (tD.z & tD.x) | ((~tD.z) & tD.y);
}
//b ^ c ^ d
unsigned int F32_47(in uvec3 tD)
{
	return tD.x ^ tD.y ^ tD.z;
}
//c ^ (b | (~d))
unsigned int F48_63(in uvec3 tD)
{
	return tD.y ^ (tD.x | (~tD.z));
}

//return input/(2^32) //2^32 - 1.0 + 1.0
vec4 convertToR0_R1(in uvec4 input)
{

	return output;
}

uvec4 whiteNoise(in uvec4 input,in unsigned int key)
{
	unsigned int data[16];
	setupInput(input,key,data);
	uvec4 rot0_15 = uvec4(7u,12u,17u,22u);
	uvec4 rot16_31 = uvec4(5u,9u,14u,20u);
	uvec4 rot32_47 = uvec4(4u,11u,16u,23u);
	uvec4 rot48_63 = uvec4(6u,10u,15u,21u);

	uvec4 digest = initDigest();
	uvec4 tD;
	uvec4 fTmp;
	unsigned int i = 0u;
	unsigned int idx;
	unsigned int r;
	unsigned int trig; const unsigned int MAXFT = 4294967295; //2^32-1
	//What follows is the unrolled loop from 0 through 63
	//0
	tD = digest;
	unsigned int temp;
	for(;i<16u;i++)
	{
		fTmp = F0_15(tD.yzw);
		idx = i;
		r = rot0_15.x;
		rot0_15 = rot0_15.yzwx;
		trig = truncate(abs(sin(float(i+1)))*float(MAXFT));
		tD.x = tD.y + ((tD.x+fTmp+data[int(idx)]+trig) << r);
		tD = tD.yzwx;

		digest +=tD;
	}
	for(;i<32u;i++)
	{
		fTmp = F16_31(tD.yzw);
		idx = (5u*i + 1u) % 16u;
		r = rot16_31.x;
		rot16_31 = rot16_31.yzwx;
		trig = truncate(abs(sin(float(i+1)))*float(MAXFT));
		tD.x = tD.y + ((tD.x+fTmp+data[int(idx)]+trig) << r);
		tD = tD.yzwx;
		digest +=tD;
	}
	for(;i<48u;i++)
	{
		fTmp = F32_47(tD.yzw);
		idx = (3u*i + 5u) % 16u;
		r = rot32_47.x;
		rot32_47 = rot32_47.yzwx;
		trig = truncate(abs(sin(float(i+1)))*float(MAXFT));
		tD.x = tD.y + ((tD.x+fTmp+data[int(idx)]+trig) << r);
		tD = tD.yzwx;
		digest +=tD;
	}
	for(;i<64u;i++)
	{
		fTmp = F48_63(tD.yzw);
		idx = (7u*i) % 16u;
		r = rot48_63.x;
		rot48_63 = rot48_63.yzwx;
		trig = truncate(abs(sin(float(i+1)))*float(MAXFT));
		tD.x = tD.y + ((tD.x+fTmp+data[int(idx)]+trig) << r);
		tD = tD.yzwx;
		digest +=tD;
	}

	return digest;
}

My MD5GPU problems/bugs, oh noes…

Okay, i need to actually run my code first before pasting it all over the intertubes…

I found some problem with it. First, the way the pseudo code in the paper is doing the rotating a,b,c,d values does not reflect the MD5 spec as shown on the WIKI page. Perhaps I’m wrong, but I tried to work this out on paper… The paper has something like this:

x.a = x.b + (a + blah < < blah)
x = x.bcda

whereas in the wiki it goes like this:

temp = d.
d = c
c = b
b = b + (a + blah << blah)
a = temp

Which would give you different values… Unless the paper and the wiki code are equivalent, and I’m not seeing it…

Anyway, I will try to rework this in and see what happens.

Also I was setting the digest wrong at each clunk of the loop.

I feel stupid. I broke my own rules, never to unroll a loop until I made sure the damn loop worked first.

ARGHGHH!!!

0000
I’m not so sure, the dude did say it was an optimization… And when you think about sure, why would it matter?

What I was able to get is a what appears to be white noise. It’s just that when I’m trying to convert it to float, using bit packing, it screws up.

More on the whys of md5

Edited: I do not claim the stuff below is right. It’s just my thoughts, and in no way shape or form is attempting to provide a concrete claim of understanding .

Yeah, if you think about it. The compression functions of md5 scrambles the bit in an independent manner. Of course, the probability of a bit changing (through bitwise ops) is not dependent on any other bits, thus it is independent. So given a sample space S, where A and B comes from, P(A | B) = P(A), so P(AB) = P(A)P(B). Of course! They are binary bits! This makes sense. So with the way it is rotating it creates an ‘avalanche effect,’ so to minimized the chance for collision of similar digests (specially with this P(A)P(B) combinatoric thing).

After rotating through this space, the probability of collisions between two similar digests is very small. Just examining the output, since we know it’s can have 2^128 events in this sample space S, and since they are independent, the P(A) where A is in S = {2^128 elements} is very very very small.

But we also know now that MD5 has collision attack problems. Why? Just glancing at the wiki page it has to do with local collisions.. Hmm interesting.

This works in mind mind. I don’t have to convince you!!!

MD5GPU algorithm implemented (source code)

So I started implementing the MD5GPU algorithm. It’s pretty straightforward. Matter of fact, I will be brief. (Note, I have not tested the code below)

From the original MD5 algo., we need to break the input into 512 bit chunks. So, we need to first pad the input to a length a, and then add 64 bit to it in order to be able to break our input into 512 bit chunks, such that:

a congurent to 448 mod 512. So we keep on appending 0 to our digest (after we appended a 1 first) so that (a – 448) mod 512 = 0. Since, (note ~ is the equivalence relation)

a ~ b mod n => (a-b) = cn, => (a-b)/n = c, where c is in Z (integers), iff (a-b) mod n = 0. (Maybe in a future post I will talk about how this relates to group theory.)

But for our problem, since the message length is a constant 128 bit, then we know from the get-go that a is 448.

…

Okay, that’s not all that interesting, since I’m just describing the algorithm. I may post some more on this tomorrow. I’m heading out for the night.

The interesting part is WHY does this thing work? Why does it produce results that passes all the DIEHARD tests? My intitutive understanding of this (but I’m not sure. Never studied crypto) this is due to the combinatoric explosion nature of working with 512 bit chunks. The compression functions are such that a change in ONE single input bit results in change of each output bit with a probability of 1/2. So, it’s like we are ’scrambling’ the input in this 512 bit combinatoric ’space’, which is a huge space… (I’m really sorry if the above bit totally pisses you off due to all the hand waving due to ignorant understanding)

Not sure tho. That’s just my intuition…

What do you think?