Jump to content
Sign in to follow this  
RevEng

running the bB 8-bit rand in reverse

Recommended Posts

As part of a LFSR development tool I put together recently, I put together a version of the bB rand lfsr that runs backwards through the usual bB rand sequence. I'll leave this here, in case anybody is interested...

  asm
.unrand
  LDA rand
  ASL
  BCC unrandnoeor
  EOR #$69
unrandnoeor:
  STA rand
  STA temp6
  RETURN
end

 

Just "gosub unrand" to run rand backwards. In the code above I stuffed a copy of "rand" into temp6, which you can use to read the value. (if you don't read temp6, when you try to read "rand", bB will call it's rand routine, which will undo the work the unrand routine did.

 

What's this good for? Well, this is more or less how pitfall creates algorithmic level data, since it can be reversed when the player backtracks. There are other ways to do this without reversal (e.g. stuffing your own data into the rand seed) but this is one more tool for the kit.

 

I took a crack at reversing the rand16 lfsr, but no luck on that. It's not entirely clear to me if it's actually trivially reversible.

 

  • Like 4

Share this post


Link to post
Share on other sites

This is pretty cool, and could be useful for certain circumstances. I wish there were a good way to jump N iterations ahead or backward without having to run the functions repeatedly, but I'm sure that's not feasible. 

 

Oh, how about also adding an "undrawscreen" which lets you undo the last frame?  :D

Share this post


Link to post
Share on other sites

Hah. I'll get to work on undrawscreen once I figure out how to reverse the beam. :D

 

Stepping over a bunch of LFSR iterations isn't in the cards. The conditional EOR that happens pretty much guarantees you need to iterate one value at a time, and I'm pretty sure any clever work around will eat more cycles than multiple iterations would. Neat thought, though!

Share this post


Link to post
Share on other sites
On 5/18/2020 at 3:33 PM, RevEng said:

I took a crack at reversing the rand16 lfsr, but no luck on that. It's not entirely clear to me if it's actually trivially reversible.

 

it's just a 16 bit LSFR

 

  dim sc0 = score
  dim sc1 = score + 1
  dim sc2 = score + 2

  dim         rndbBlo = rand16
  dim         rndbBhi = rand
  dim          rand16 = z
  dim right_edge_flag = r
  dim  left_edge_flag = l


  scorecolor = $33
  COLUBK = 0
  COLUPF = 68
  var40 = $55 : var41 = $AA

draw
  if joy0right then right_edge_flag = 0 else right_edge_flag = 1
  if joy0left  then  left_edge_flag = 0 else  left_edge_flag = 1

  drawscreen

  if joy0right && right_edge_flag then temp1 = rand : goto display
  if joy0left  &&  left_edge_flag then temp1 = unrand() : goto display
  goto draw


display
  var36 = rndbBhi : var37 = rndbBlo

update_scr
  sc0 = 0 : sc1 = sc1 & 15
  if temp1 >= 100 then sc0 = sc0 + 16 : temp1 = temp1 - 100
  if temp1 >= 100 then sc0 = sc0 + 16 : temp1 = temp1 - 100
  if temp1 >= 50 then sc0 = sc0 + 5 : temp1 = temp1 - 50
  if temp1 >= 30 then sc0 = sc0 + 3 : temp1 = temp1 - 30
  if temp1 >= 20 then sc0 = sc0 + 2 : temp1 = temp1 - 20
  if temp1 >= 10 then sc0 = sc0 + 1 : temp1 = temp1 - 10
  sc1 = (temp1 * 4 * 4) | sc1

  goto draw


  function unrand()
  asm
  lda rndbBlo
  lsr
  lda rndbBhi
  rol
  bcc skip_eor16
  eor #$68
skip_eor16
  sta rndbBhi
  ror rndbBlo
  eor rndbBlo
  rts 
end


 

joy0right rand forward

joy0left unrand() backwards

 

the screen is the LFSR  (the bottom row is just to show where the bits are)

the score is the return value

 

(I didn't actually do an exhaustive test, but it looks like it works :P )

 

 

unrand16.bas unrand16.bas.bin

  • Like 2

Share this post


Link to post
Share on other sites

By the way, I added some visualizations of the bB lfsr's to the lfsr6502 thread. Despite complaints of clumpiness, they look pretty evenly distributed.

 

 

Share this post


Link to post
Share on other sites
Posted (edited)
On 5/19/2020 at 8:58 PM, RevEng said:

By the way, I added some visualizations of the bB lfsr's to the lfsr6502 thread. Despite complaints of clumpiness, they look pretty evenly distributed.

 

 

here (pastebin) is some javascript to do scatterplots of the bB rand LFSR(s)

 

did this a while ago and just came back across it so you may have seen it

 

looks like there's points clustered at the edges.  that makes me wonder if it works the way it should

 

I don't specifically recall (and I haven't looked yet) but I assume it plots this value against the previous value

 

rand 16 looks a lot better

Edited by bogax

Share this post


Link to post
Share on other sites

Nice. bB8 looks horrid with that style of plotting, which I guess in small part is due to the limited period, though clearly the lfsr pattern is the main issue. It would be interesting to see the other 8-bit LFSRs, so I might look at adding something like that to lfsr6502. (tho probably not soon.)

Share this post


Link to post
Share on other sites

Here's some scatters I did of some LFSRs

combined with a simple LCG  x'=x*17+103

 

scatters.thumb.gif.baaea590c88ba2f66f361dc7ce17b554.gif

  • Like 1

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...