Re: Announcing cdrskin-0.7.2
| From: Thomas Schmitt <scdbackup@gmx.net>
| 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"?
Reply to: