Re: Announcing cdrskin-0.7.2

| From: Thomas Schmitt <[email protected]>

| I have to correct myself:
| > I.e. the indice of the power and log table
| > represent natural numbers, not polynomials.
| 
| The indice of the power table are natural
| numbers, the indice of the log table
| are polynomials.

Thanks for your very useful explanations.

The logs are whole numbers.  I was taught that 0 is not included in
natural numbers.  This is a matter of dispute among mathematicians;
see the first paragraph of:
	http://en.wikipedia.org/wiki/Natural_number

As you explained elsewhere, they are actually the integers mod 255.

As such, your original gfpow table should have had a size of
255 elements, not 256.  Your initializer only initialized 255, leaving
the last (unused) element to be implicitly initialized with 0.  In
fact, no entry of gfpow should be 0 because no power of x is 0.
Luckily, that wrong entry would never be used.

| One has to unroll the table gfpow[] up to 511
| elements because the highest sum of two gflog[]
| elements is 510.

The smallest log is 0.  The largest is 254 (not 255).  So
the range of sums of pairs of logs is [0-508].  So you actually need
only 509 elements in the expanded table.

It seems easier to just double the table of 255 elements to 510
elements.

================

I'm glad that eliminating the % made a significant speedup.

That leads me to wonder about a different idea that might or
might not cause a speedup.

In burn_rspc_mult:
453        if (a == 0 || b == 0)
454	                return 0;

On most modern machines, branches are slow.  This test requires two
branches.  So it might be faster to use "|" in place of "||" because
only one branch would be required.

That depends on the compiler knowing how to calculate == without
branching.

If the compiler is not smart enough, this test should do the same job:
	((a + 0xFF) & (b + 0xFF) & 0x100) == 0
Explanation: a + 0xFF will have the 0x100 bit on UNLESS a was zero.
The result of the first & will have that bit on unless either a or b
was zero.

So would this:
	((a - 1) | (b - 1)) < 0
Explanation: a - 1 will be less than 0 if and only if a was 0.  The result of
the | will be negative if and only if one of its operands was negative.

This second test won't work on a class of machines that I've never
seen: ones where sizeof(unsigned char) == sizeof(int).  Why?  Because
C's promotion rules mean that a - 1 on such a machine would be done in
type unsigned int, and thus the result could never become negative.
(Actually, some compilers from before the C Standard have this
too.)

Here is a more bullet-proof version of the second test:
	(((int)a - 1) | ((int)b - 1)) < 0

As you can see, these tricky tests require several extra operations to
save a branch.  I would expect that to be faster on most modern
processors but I have not tested this.

================

In burn_rspc_div, you return -1 if the division is by 0.
-1 isn't really a nice unsigned char value.

Do you know if this case ever comes up?  If it "should" not, for some
values of "should", perhaps the function could abort instead.

467	        d = gflog[a] - gflog[b];
468	        if (d < 0)
469	                d += 255;
470	        return gfpow[d];

Now that you have the doubled table, I guess that this could be
rewritten as:

	return gfpow[gflog[a] - gflog[b] + 255];

================

Looking at next_bit().  These comments are REALLY unimportant.

- is there any reason that the & 0x3fff is needed?  How would the
  0x8000 bit get set?

- should the type of the result of next_bit (and ret) be unsigned
  short?

673	        ecma_130_fsr = (ecma_130_fsr >> 1) & 0x3fff;
674	        if (ret ^ (ecma_130_fsr & 1))
675	                ecma_130_fsr |= 0x4000;

		ecma_130_fsr >>= 1;
		ecma_130_fsr |= (ret ^ (ecma_130_fsr & 1)) << 14
Simpler?

================

Several functions unconditionally return 1.  For example
burn_rspc_p0p1.  In that case at least, the caller ignores the result.
Why not define the function with a return type of "void"?


-- 
To UNSUBSCRIBE, email to [email protected]
with a subject of "unsubscribe". Trouble? Contact [email protected]