I just found out about these and wrote a little test program which has curious behaviour. For those who don't know, the basic algorithm is this

track a variable holding the last result
shift it one to the right
mask off a few bits and count the set ones
if an odd number are set, set the msb of the variable  

The code I used was simply this

loop_top:
shr EAX, 1
test EAX, lfsrmask
jnp @F
	or EAX, 2147483648
@@:
push EAX
dec ECX
jnz loop_top  

With an initial value of 3544756459 for EAX, and a mask of 1174405121 (this mask is supposed to make the algo visit every possible number at least once before looping) I dumped a meg of the stack noise to the disk to see how random it was. At a first glance in a hex editor it didn't look too promising, there were clear diagonal repeats of symbols in groups, but it isn't so straitforward. For a start the repeats are seperated by 33 bytes so the stream of DWORDs is actually very diverse. Secondly the groups of four symbols which repeated changed slightly each time. Typical example: xNYû 29 bytes of other stuff xNYV 29 bytes of other stuff xNÜV 29 bytes of other stuff xEÜV and so on... And that's not just the occasional bit change, eg û to V is 0xEA to 0x56, or, in binary 11101010 01010110 So why are the other 3 bytes unchanged? And why should *every * pattern be (almost) repeated exactly 33 bytes later? Wierd. But these pattern's aren't just occational, they aren't even all over the place, they ARE the output. Thousands of unique patterns overlapping. Look at this typical selection

_HËèa檧+"M+çEÜV
ï4¡iZ:,ʦuXñi
Û_HËÈa檮+"MRçEÜ
Ñï4Kiû:,Ê,uXñ
YÛ_H_Èaæe®+"-RçE
ûÑï-K[û:,À,uX
nYÛ_¦_Èa¦e®+t-Rç
ÚûÑË-Kº[û:OÀ,u
×nYÛ<¦_Èx¦e®±t-R
ÔÚûÑ+Ë-Kèº[û§OÀ,
+×nYV<¦_¡x¦eZ±t-
¦ÔÚûi+Ë-Ëèº[ª§OÀ
M+×nÜV<¦4¡x¦iZ±t
ʦÔÚñi+ËHËèºæª§O
"M+×EÜV<ï4¡xiZ±
,ʦÔXñi+_HËèa檧
+"M+çEÜVï4¡iZ
:,ʦuXñiÛ_HËÈaæª
®+"MRçEÜÑï4Ki
û:,Ê,uXñYÛ_H_Èaæ
e®+"-RçEûÑï-K
   

3-byte groups always appear exactly twice. I just ran this thing ten million times and i haven't found a single repeated DWORD so I suspect the claim that this particular bit mask does visit every possible number is true. I ran it again with the "test EAX, lfsrmask" line edited out, so the parity check is on the whole value, not just a few bits. Naturally the output was different but it behaves exactly the same way, same style of repetition exactly and I still haven't found repeated DWORDs in several megabyte files. I don't know about you but I find this mildly fascinating. It's certainly a good algo for games: it's fast and even when a number partially repeats it's a byte out of place and 8 DWORDs after it's previous. Do you like this as much as I do? EDIT: This output is every eigth iteration, so you can beter see the semi-repeats

ÒyP
Òy
&Òy
¼&Ò
ë¼&
+ë¼&
Î+ë¼
"Î+ë
©"Î+
}©"Î
}©"
c}©
½c}
,½c
 ,½c
ä ,½
yä ,
yä l
yäÓl
ykÓl
|kÓl
+|kÓ
Ú+|k
TÚ+|
ÐTÚ+
ïÐTÚ
_ïÐT
M_ïÐ
?M_ï
ú?M_
sú?M
ñsú?
õñsú
õñs
òõñ 

******** I am not the Iraqi information minister. GSACP : GameDev Society Against Crap Posting To join: Put these lines in your signature and don't post crap! [edited by - walkingcarcass on August 6, 2003 4:30:53 PM]