💾 Archived View for vigrey.com › tarot › gb › log › 3.gmi captured on 2024-12-17 at 10:30:29. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
I now have the random number generation and card shuffling functionality programmed in! In case someone else ends up working on some low level retro computing project that involves shuffling a deck of cards, I included some technical info of how I did it for this project.
To generate random bits, I use a 32-bit linear feedback shift register (LFSR) with a polynomial value of $C5 (%11000101)
// 4 global variables (lfsr0, lfsr1, lfsr2, lfsr3) are manipulated
// The result is the modified value of lfsr0
// Polynomial value of $C5 (%11000101) is used
function LFSR() {
for x = 0; x < 8; x++ {
carry = 0
if lfsr0 & 1 {
carry = 128 // Set carry to 128 if rightmost bit of lfsr0 is set
}
lfsr0 = lfsr0 >> 1 // Shift lfsr0 1 bit right
c = carry // Carry of previous lfsr byte
carry = 0
if lfsr1 & 1 {
carry = 128 // Set carry to 128 if rightmost bit of lfsr1 is set
}
lfsr1 = lfsr1 >> 1 + c // Shift lfsr1 1 bit right and add in c
c = carry // Carry of previous lfsr byte
carry = 0
if lfsr2 & 1 {
carry = 128 // Set carry to 128 if rightmost bit of lfsr2 is set
}
lfsr2 = lfsr2 >> 1 + c // Shift lfsr2 1 bit right and add in c
c = carry // Carry of previous lfsr byte
carry = 0
if lfsr3 & 1 {
carry = 128 // Set carry to 128 if rightmost bit of lfsr3 is set
}
lfsr3 = lfsr3 >> 1 + c // Shift lfsr3 1 bit right and add in c
if carry == 128 {
lfsr0 = lfsr0 ^ $CF // XOR lfsr0 with $CF (%11000101) if carry set
}
}
return lfsr0
}
Essentially, shift the entire 32 bits to the right 1 bit, and if a 1 pops out of the right of the 32 bits, perform an Exclusive Or of the first 8 bits and the hex value CF. Do that 8 times to perform a full LFSR. The leftmost 8 bits of the completed LFSR will be a value that appears random and has an equal chance of being 0 through 255. It is VERY IMPORTANT though that the initial 32 bits are NEVER set to all 0s, as performing an LFSR on all 0 bits will result in all 0 bits every single time. It's recommended to have the 32 bits initially be a value that looks decently random, but other than not having the 32 bits all be 0s, it doesn't entirely matter what the 32 bits are set to initially.
The polynomial ($CF in this case) needs to be carefully chosen to maximize the amount of times the LFSR can be performed before the cycle starts over again. With $CF, the LFSR can be performed 4,294,967,295 (2**32 - 1) times before the cycle starts over and will go through every possible 32 bit combination with the exception of all 0s.
An LFSR is fine if I always wanted a number between 0 and 255, but there are 78 cards in a tarot deck, so values of 78 to 255 aren't useful. I could just throw away all results that are too large, but that's incredibly wasteful. A method for generating a random number from coin flips was described in a paper by Jeremie Lumroso though, linked below.
"Optimal Discrete Uniform Generation from Coin Flips, and Applications" by Jeremie Lumroso
This algorithm efficiently and effectively reuses bits if the result of the LFSR is too large rather than throwing out the entire result. Each byte of the LFSR result is a coin flip, 1 being heads and 0 being tails. We get 8 coin flips per LFSR result, so if I do all 8 coin flips, another LFSR needs to be performed again to get 8 more bits. The following pseudo code will globally keep track of how many flips are performed, and in order to not waste bits, if you don't use up exactly a multiple of 8 flips, there will still be bits remaining that can be used for the next random number.
// coinFlipsRemaining and rng are both global variables
coinFlipsRemaining = 0
rng = 0
// Returns a 1 or a 0 depending on the rightmost bit of rng
function coinFlip() {
if coinFlipsRemaining == 0 {
rng = LFSR()
coinFlipsRemaining = 8
}
result = rng & 1 // result is rightmost bit of rng
rng = rng >> 1 // Shift rng 1 bit right
coinFlipsRemaining -= 1
return result
}
// Returns a random number from 0 through 77
// All results are equally as likely as long as coinFlip() is fair
func getRandomNumber() {
v = 1
c = 0
while true { // Keep looping until result is found
v = v * 2
c = c * 2 + coinFlip() // 1 is only added if coin flip is heads
if v > 77 {
// c can be any number less than v, so make sure v is > 77
if c <= 77 {
break // c is a random result between 0 and 77
}
// c overshot, so subtract 77 from v and c
v = v - 77
c = c - 77
}
}
return c
}
The function results in a random number from 0 through a desired number (77 in my face because there are 78 cards in a tarot deck and counting them 0-indexed means the last index is 77) where each number is just as likely as any other number coming up, assuming the "coin flip" is fair and random. Computers have a really hard time with random, but it appears close enough to random for the needs of this project.
For this part, I need to set aside 78 bytes of memory and make sure all values 0 to 77 ($00-$4D) are represented in those 78 bytes. An easy way to initially do that is to just set offset 0's value to 0, offset 1's value to 1, offset 2's value to 2, . . ., and offset 77's value to 77. We only need to do this initialization once, as shuffling the deck will not change the property of those 78 bytes all being unique from each other. It honestly doesn't matter how the 78 bytes are initialized, but having the byte values be sequential values is pretty straight forward to do.
Once values 0 through 77 are uniquely in those 78 bytes of memory, we need to start shuffling the deck. It turns out shuffling the deck is equivalent in randomness to swapping a card at offset A with a random card at offset 0 through offset A and doing that for every card in the deck.
To shuffle the deck, we set the offset A to 77, then we swap the card at offset A with a card at a random offset from 0 through A, so a random card from offset 0 through 77. Once the cards are swapped, we set offset A to 76 and swap the card at offset A with a card at a random offset from 0 through A, so a random card from offset 0 through 76. Rinse and repeat, making sure to subtract 1 from A each time. The last swap is when offset A is set to 1.
Another way the cards could be shuffled is to always pick a random value from 0 through 77 and swap the card at offset A with that random offset, but the reason I do it the way I described is because it shrinks the maximum random value needed for each card swapped, which means fewer bits need to be converted to get random numbers, thus saving CPU cycles overall and making the code run faster. The process of shuffling the deck is computationally expensive, so cutting down the amount of CPU cycles on average is a good thing.
If you would like to reply to this post, feel free to send me an email or misfin message.