4 ms·

The linear-feedback shift register method is also used for procedurally generating content in e.g. demos. Funny to see this implemented in hardware and it would

by pvitz 5y ago

The linear-feedback shift register method is also used for procedurally generating content in e.g. demos. Funny to see this implemented in hardware and it would be interesting to know when this trick was used firstly.

NobodyNada 5y ago
I don’t know the history, and I agree it would be fascinating to hear from someone who does — but the fact that we call it a “shift register” strongly suggests it was implemented in hardware first, because “shift register” is usually a hardware term rather than a software term. The earliest example of an LFSR I’ve seen is the Nintendo Entertainment System’s white noise generator, implemented in hardware. But many NES games used software LFSRs to generate random numbers for gameplay, so the trick was probably long-established and well-known at that time.
- kens 5y ago
  I don't know the full history, but a bit of searching shows that linear feedback shift registers were in use in the 1960s, so it's a pretty old technology.
  - pvitz 5y ago
    It's not about how old the technology is, but from when on it wasn't used as e.g. a pseudo-RNG, but rather for storing data. So, formally, still a RNG, but using a special seed to get a sequence that is equal to the data that one wants to store. I have found that "River Raid" (1982) and "The Sentinel" (1986) were using it for game data. Apparently, the original "Elite" was supposed to use one, too, but they decided against it.
marcan_42 5y ago
It's common where area or performance are paramount, since it performs better than an equivalent (binary) counter in silicon. The Numerically Controlled Oscillator in the Apple M1 that is used to generate audio sample rates uses an LFSR as its first stage clock divider, and the driver has to load the right LFSR initializer value directly. It was fun working that one out. They use an LFSR because the input clock is a rather fast 1GHz or so, and dividing that down requires a bit of optimization. There are some 4-bit CPUs that use an LFSR as the program counter, so the ROM gets stored in pseudorandom order. It's fun how the lowest tech chips and the highest tech chips both end up resorting to the same old techniques, isn't it? :)
- mikevin 5y ago
  I think I saw your tweet about getting nerd-sniped into figuring this out. Or was that another component? What would be the reason for the pseudorandom ROM order? Just a side effect of the PC choice or deliberate? sidenote: interesting that two sentences into your response I knew exactly what name I was going to see as the author. Thanks for the work you're doing and especially for documenting it. I've been reversing my old DSL-modem to pass time during lockdowns and since it's an obscure, asic based model it's highly educational to see you talk about figuring out things living on the hard/software boundary.
  - marcan_42 5y ago
    It was this :) The pseudorandom ROM order is just a consequence of using an LFSR as a counter, since it counts in pseudorandom order. I'm glad you enjoy what I'm doing! It's a lot of fun being able to work on a project like this, and I'm glad some of it is educational for other folks.

by pvitz 5y ago

NobodyNada 5y ago

I don’t know the history, and I agree it would be fascinating to hear from someone who does — but the fact that we call it a “shift register” strongly suggests it was implemented in hardware first, because “shift register” is usually a hardware term rather than a software term. The earliest example of an LFSR I’ve seen is the Nintendo Entertainment System’s white noise generator, implemented in hardware. But many NES games used software LFSRs to generate random numbers for gameplay, so the trick was probably long-established and well-known at that time.

kens 5y ago
I don't know the full history, but a bit of searching shows that linear feedback shift registers were in use in the 1960s, so it's a pretty old technology.
- pvitz 5y ago
  It's not about how old the technology is, but from when on it wasn't used as e.g. a pseudo-RNG, but rather for storing data. So, formally, still a RNG, but using a special seed to get a sequence that is equal to the data that one wants to store. I have found that "River Raid" (1982) and "The Sentinel" (1986) were using it for game data. Apparently, the original "Elite" was supposed to use one, too, but they decided against it.

marcan_42 5y ago

It's common where area or performance are paramount, since it performs better than an equivalent (binary) counter in silicon. The Numerically Controlled Oscillator in the Apple M1 that is used to generate audio sample rates uses an LFSR as its first stage clock divider, and the driver has to load the right LFSR initializer value directly. It was fun working that one out. They use an LFSR because the input clock is a rather fast 1GHz or so, and dividing that down requires a bit of optimization. There are some 4-bit CPUs that use an LFSR as the program counter, so the ROM gets stored in pseudorandom order. It's fun how the lowest tech chips and the highest tech chips both end up resorting to the same old techniques, isn't it? :)

mikevin 5y ago
I think I saw your tweet about getting nerd-sniped into figuring this out. Or was that another component? What would be the reason for the pseudorandom ROM order? Just a side effect of the PC choice or deliberate? sidenote: interesting that two sentences into your response I knew exactly what name I was going to see as the author. Thanks for the work you're doing and especially for documenting it. I've been reversing my old DSL-modem to pass time during lockdowns and since it's an obscure, asic based model it's highly educational to see you talk about figuring out things living on the hard/software boundary.
- marcan_42 5y ago
  It was this :) The pseudorandom ROM order is just a consequence of using an LFSR as a counter, since it counts in pseudorandom order. I'm glad you enjoy what I'm doing! It's a lot of fun being able to work on a project like this, and I'm glad some of it is educational for other folks.