RevEng Posted May 18, 2020 Share Posted May 18, 2020 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. 6 Quote Link to comment Share on other sites More sharing options...
+Karl G Posted May 19, 2020 Share Posted May 19, 2020 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? Quote Link to comment Share on other sites More sharing options...
RevEng Posted May 19, 2020 Author Share Posted May 19, 2020 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! Quote Link to comment Share on other sites More sharing options...
bogax Posted May 20, 2020 Share Posted May 20, 2020 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 2 Quote Link to comment Share on other sites More sharing options...
RevEng Posted May 20, 2020 Author Share Posted May 20, 2020 Yay... well done! ? Quote Link to comment Share on other sites More sharing options...
RevEng Posted May 20, 2020 Author Share Posted May 20, 2020 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. Quote Link to comment Share on other sites More sharing options...
bogax Posted May 26, 2020 Share Posted May 26, 2020 (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 May 26, 2020 by bogax Quote Link to comment Share on other sites More sharing options...
RevEng Posted May 26, 2020 Author Share Posted May 26, 2020 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.) Quote Link to comment Share on other sites More sharing options...
bogax Posted May 26, 2020 Share Posted May 26, 2020 Here's some scatters I did of some LFSRs combined with a simple LCG x'=x*17+103 2 Quote Link to comment Share on other sites More sharing options...
bogax Posted June 4, 2020 Share Posted June 4, 2020 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) 1 Quote Link to comment Share on other sites More sharing options...
RevEng Posted June 4, 2020 Author Share Posted June 4, 2020 Nice... now I have some interesting reading for the weekend. ? Quote Link to comment Share on other sites More sharing options...
+Random Terrain Posted June 23, 2021 Share Posted June 23, 2021 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. Quote Link to comment Share on other sites More sharing options...
RevEng Posted June 23, 2021 Author Share Posted June 23, 2021 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) 1 Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.