Tuesday, November 2, 2010

LFSR in 386 assembly

Don't hold it against me. This is with the x^32+x^31+x^29+x+1 poly from the wikipedia page on linear feedback shift registers.

do {
lfsr = (lfsr >> 1) ^ (unsigned int)(0 - (lfsr & 1u) & 0xd0000001u);
} while(lfsr != 1u);

cute trick, but compiles to this:

movl $1, %ebx
movl %ebx, %edx
andl $1, %ebx
negl %ebx
shrl %edx
andl $-805306367, %ebx
xorl %edx, %ebx
cmpl $1, %ebx
jne L2

The carry flag will be set from the shift, so we can use sub with borrow to set eax to 0 or -1. With my not-very-accurate measurements, 7 seconds (down from 9) to go through 2^32:

mov edx, 1
shr edx
sbb eax, eax
and eax, 0xd0000001
xor edx, eax
cmp edx, 1
jne L2

Thanks Phil for the idea!

No comments: