running the bB 8-bit rand in reverse

[RevEng]

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.

 

[+Karl G]

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?  

[RevEng]

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

 

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!

[bogax]

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  )

 

 

unrand16.bas unrand16.bas.bin

[RevEng]

Yay... well done! ?

[RevEng]

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.

 

 

[bogax]

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 May 26, 2020 by bogax

[RevEng]

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.)

[bogax]

Here's some scatters I did of some LFSRs

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

 

[bogax]

I found this PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (from this page) interesting

 

 

bB rand16 is kinda like that (with an LFSR instead of LCG) 

[RevEng]

Nice... now I have some interesting reading for the weekend. ?

[+Random Terrain]

On 5/18/2020 at 6:33 PM, RevEng said:

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.

 

 

I tried to find the answer online but "period" and "colon" are kind of hard to search for.

 

What does the period in ".unrand" do or mean?

 

What does the colon in "unrandnoeor:" do or mean?

 

 

Thanks.

[RevEng]

Nerds often refer to the period symbol as "dot", when it's not being used at the end of a sentence. That would have helped with the search.

 

A label that begins with a dot is limited in scope. i.e. if you use a particular dot label somewhere in a dasm subroutine, you can use the same dot label elsewhere for some other purpose, without a name clash.

 

The reason for the dot label in this particular case is to make it possible to "gosub unrand" directly from bB source code. bB prepends a dot to all of it's labels, which means the basic code "gosub unrand" becomes the assembly code "jsr .unrand".

 

A natural follow-up question might be "why does bB internally add a dot to each label?" The reason bB does that is to support line numbers as labels. Dasm doesn't support symbols that are just numbers, or even those that begin with numbers. So adding the dot to each label was batari's way to turn the line numbers into a label that dasm would accept. (bB doesn't actually use dasm subroutines at all, as far as I recall)

 

The colon is just an optional dasm syntax for labels. Some people use it to make labels more obvious in their assembly source, or because they previously used an assembler that required the colon for labels. I typically don't use it, but I did for some reason here. (and inconsistently too, since .unrand doesn't have one)