EliasOenal/multimonNG — pull request #6 by arekinath (2013-03-27 12:15:50+00:00)
Title: Calculate POCSAG syndrome with a bitslice algorithm

## What is this?

This patch reworks the POCSAG error correction code to use a bit-slice algorithm to compute the syndrome.

It's sort of like the bitslice triple-DES you use in a password cracker (see John the Ripper's code), we turn the problem sideways and do 32 attempts at once, in parallel. This turns out to save quite a bit of CPU time when we're correcting POCSAG errors.

## Bitslice what?

The original pocsag_syndrome looks like this:

unsigned int pocsag_syndrome(uint32_t data)
{
uint32_t shreg = data >> 1;
uint32_t mask = 1L << (BCH_N-1), coeff = BCH_POLY << (BCH_K-1);
int n = BCH_K;

for(; n > 0; mask >>= 1, coeff >>= 1, n--)
if (shreg & mask)
shreg ^= coeff;
if (even_parity(data))
shreg |= (1 << (BCH_N - BCH_K));

return shreg;
}

We go down the data (after removing the parity bit) checking each bit and XORing with the coefficient. This normally requires 21 XOR operations for each syndrome. We also perform the parity shift and final parity XOR once for each syndrome. For 32 syndromes, this adds up to 32*21 + 32 = 704 XOR operations.

One important thing to note here is that the coefficient only has 8 bits set in it. This might not seem significant, but we will come back to it in a moment.

Now imagine a 32x32 bit matrix of these 32 arbitrary inputs to pocsag_syndrome. (We'd be doing them one at a time, but imagine 32 of them batched up together) Now transpose this matrix (make its columns its rows and vice versa) -- we still have 32x 32-bit ints, but each int represents one bit of all of the inputs. So anything we do to index 0 in the array is now happening to all of the first bits of the inputs and no other bits.

With the matrix rotated, we can take advantage of the fact that only 8 bits are set in the coefficient. We only have to consider the bit slices where the coefficient has a 1 bit, reducing our operations to 32*8 = 256 XORs. Additionally, we can now do the parity XOR operation for all 32 inputs in one go (though we still have to calculate the mask first). So we total about 288 XORs -- about 40% of the number of operations we had before.

Additionally, we now have completely branchless code, which means our tight loop no longer will have issues with the branch predictor and can run at full speed on our CPU.

As an aside -- we can now generate the 32 parallel inputs to pocsag_syndrome in a more efficient manner, too, since our brute force algorithm depends on mutating individual bits. So there are wins everywhere.

### Comparison with some sample data (on x86-64)

$ time cat sample.bin | ./multimonNG -t raw -a POCSAG512 -a POCSAG1200 \
-f alpha /dev/stdin -v 1 \
> master.output
real	0m1.717s
user	0m1.695s
sys	0m0.016s

$ git checkout bitslice_pocsag && make

$ time cat sample.bin | ./multimonNG -t raw -a POCSAG512 -a POCSAG1200 \
-f alpha /dev/stdin -v 1 \
> bitslice.output
real 0m0.325s
user 0m0.315s
sys 0m0.011s

$ diff -u master.output bitslice.output
$

(Not showing the 100 repetitions of each test to verify timing numbers. Numbers shown are the median, and the distribution is pretty tight. I can provide full data if you want)