What does this C function do?

Question

C source code at: http://pastebin.com/6Bywk5mf
Will also function in Java. Note that in C this won't work for values above 127 unless you change char to unsigned char.

Two questions:

1. Easy - What does the function do? This shouldn't require more than two words explanation.
2. Hard - How does it work? Of course this is slightly ill-defined, what "how" constitutes; you could just say "it executes this series of operations". I would consider that, if you can understand how this function was written, then you understand how it works.

Answer 1

Ok, So I have a pretty good idea of what is going on but I can't tell you how you came up with one crucial number in this thing.

First things first

This function returns non 0 for all primes and 1 (specifically 1540723609 when ints are 32bits)

The hard thing

You are finding patterns in the bits of prime numbers to create a list of all the primes pretty much by hand

Simplified code

http://pastebin.com/h4Z0enYC

How it works

Now onto the important bits (pun definitely intended). First we notice that the function is broken up into 3 sections.

Section 1: Lines 1-17 - We can call this "Set up"

Section 2: Lines 18-334 - Call this "the workhorse"

Section 3: Lines 355-366 - Call this "clean up"

As @Rubio mentioned

Section 3 really doesn't do much, the result is determined before this point. All these lines do is cause an integer overflow so if the result was even - it is now 0. If it was odd - it is still odd and more importantly not 0. This whole section can be replaced with

 v21 = v21 & 1;

After realizing that - we can quickly discover this whole thing is

based on integer overflow! The beauty of overflow (or at least how it is most often implemented with negative numbers being stored as 2's compliment) is that some mathematical properties still hold. The one that we will use the most is

odd + odd = even
even + even = even
odd + even = odd

and the corollaries for multiplication

odd * odd = odd
even * even = even
odd * even = even

And with the beauty of math we can replace all the hard coded numbers in section 2 with

 odds => 1
 evens => 0

Drilling down even further into section 2 we realize

It is made up of multiple sections of the form

      v20 = 32579;
      v14 = v0 + 183840;
      v20 *= v14;
      v15 = v1 + 92055;
      v20 *= v15;
      v16 = v6 + 31344;
      v20 *= v16;
      v17 = v7 + 156091;
      v20 *= v17;
      v18 = v8 + 95882;
      v20 *= v18;
      v19 = v12 + 45047;
      v20 = v19;
      v21 = (v20 + 34185)(v21 + 177757) + 126015;
 

After we make the odds/even replacement it is simplified down to

      v20 = 1;
      v14 = v0;
      v20 *= v14;
      v15 = v1 + 1;
      v20 *= v15;
      v16 = v6;
      v20 *= v16;
      v17 = v7 + 1;
      v20 *= v17;
      v18 = v8;
      v20 *= v18;
      v19 = v12 + 1;
      v20 = v19;
      v21 = (v20 + 1)(v21 + 1) + 1;
 

Lets pause for a moment before we go down the rabbit hole of section 2 and tackle Section 1 - this part is easy now that we understand what is going on.

Section 1 is essentially breaking some number into its first 14 bits and storing them in the variables v thru v13 All the lines can be re-written to the form
vX = (v >> X) & 1

(I am avoiding that stupid first line that sets v to a silly number for a reason, ill get back to it later)

Lines 3-16 are all similar - divide v by a power of 2 which is just a bitshift to the right.

v1 = v/2 becomes v1 = v >> 1
v2 = v/4 becomes v2 = v >> 2

and so on. Keeping in mind this all based on overflow and the rules of math outlined above, we can safely say that we only care if the result is odd or even (if the last bit is a 1 a 0). Therefore all the lines in this section get rewritten as
v1 = v/2 becomes v1 = (v >> 1) & 1

We need one more piece of information before we go back to section 2. We need a few rules of the logic operators ~, & and |. When dealing a single bit (1 or 0) these equivalences hold true:

result = a & b is the same as result = a * b.
result = ~a is the same as result = a + 1 (due to overflow in a single bit world
result = a | b is logically equivalent to result = ~(~a & ~b)
result = ~(~a & ~b) which is 1 + ((1+a) * (1+b))

Back to section 2 again now that we are armed with this new information. Lets keep making replacements in the part of section 2 we were working on.

      v20 = 1;
      v14 = v0;
      v20 &= v14;
      v15 = ~v1;
      v20 &= v15;
      v16 = v6;
      v20 &= v16;
      v17 = ~v7;
      v20 &= v17;
      v18 = v8;
      v20 &= v18;
      v19 = ~v12;
      v20 &= v19;
      v21 = v20 | v21
 

Now it is easy to see we don't need the variables v14-v21 at all. They are completely useless

      v20 = 1;
      v20 &= v0;
      v20 &= ~v1
      v20 &= v6;
      v20 &= ~v7;
      v20 &= v8;
      v20 &= ~v12;
      v21 = v20 | v21
 

simplifying one more step we get a one liner

 v21 |= v0 & ~v1 & v6 & ~v7 & v8 & ~v12
 

After we replace all the lines in section 2 with the one line above we can see a little clearer what is happening.

You Found patterns in the bits to create a list, in this case a list of known primes

The part I don't know

Line 2 - int v = a0 + ((a0*151)%256)/4*256;

What it does:

sets the first 8 bits of v to a0 and bits 8-13 to a number between 0 and 64 shifted left by 8. I assume this makes each number between 0 and 255 more unique (essentially a hash that adds more bits) and easier to target individual groups of numbers that have similar bit patterns.

Why 151?

Because it works? (I have no idea how you came up with this formula)

Answer 2

partial answer

Easy answer: the function

in two words "finds primes". not exactly, but close enough; it returns non-zero only if the input is 1 or a prime, for inputs between 0 and 255.

Hard answer:

I haven't the slightest idea what the mechanism here is. The computations are wrapping around MAXINT in a way that pushes the result to zero for composite input values, based on the binary-esque decomposition of "v" into v0..v13, but neither the meaning of "v" nor the choice of the magic constants make any sense to me.
I do know that the last 16 manipulations of v21 are superfluous; the result is already determined after
v21 = v21*(v21 + 14878);
(all that changes after that line is the specific value returned).