Revisiting DMC-safe controller reading

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Revisiting DMC-safe controller reading

Post by Drag »

Back when dinosaurs roamed the earth, the method for DMC-safe controller reading was either to continually reread until two consecutive reads match, or to read a fixed amount of times and pick out a matching pair of reads, falling back to the previous frame's controller state if there's none. There's potentially another way to do it.

Bits have two possible states, so if you have three bits, you're guaranteed a matching pair of values somewhere among those three bits. If you fetch 3 controller status bytes, you should be able to build a new controller status byte by finding the matching pair for each bit, using the three bytes.

The truth table to apply to each bit is this:

Code: Select all

A B C
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1
The logic for that is: (A & (B | C)) | (B & C)

If you read the controller three times and store each byte in A, B, and C, the 6502 code to do a bitwise "sock pairing" is this:

Code: Select all

 lda B
 ora C
 and A
 sta A
 lda B
 and C
 ora A
 sta A
A is only needed once, so it can double as the result byte. Assuming zeropage, this code is 24 cycles, plus the time it takes to do 3 full reads of the controller port, which should be fixed time as well. The advantage of doing it this way versus a 3-way byte-comparing way is that the single frame latency for a failed matchmaking is localized to each individual button of the controller, rather than all buttons.

Edit: One caveat is, because of the possible latency with the individual bits, there are extremely extremely extremely rare situations where a DMC glitch can happen right as you shift your thumb on the d-pad to another direction, to cause the software to see both up+down or both left+right pressed simultaneously. For instance, one byte of left pressed, one byte of right pressed, and a DMC-glitched byte of right pressed that looks like left+right are pressed; the pairing algorithm will see two 1's for left and two 1's for right, giving the software one frame of left+right. This requires an extremely specific case of everything being timed perfectly, and may be just as rare as a real controller physically having left+right pressed.
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Revisiting DMC-safe controller reading

Post by Bregalad »

(A & (B | C)) | (B & C)
I am unhappy by the non symmetry of your formula. A, B and C are basically exactly the same thing and should be interchangeable.

EDIT: A formula that would seem to work and be symetrical is:

Code: Select all

(A and B and C) xor (A or B or C) xor (A xor B xor C)
I don't know whether that would be practical.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Revisiting DMC-safe controller reading

Post by tepples »

I'm not so sure how bitwise majority can be more effective than bytewise majority, other than using constant cycles. The effect of a DMA clock glitch is not a flip but instead a deletion, which may change all subsequent bits.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Revisiting DMC-safe controller reading

Post by Drag »

@Bregalad
Another formula is (A&B) | (A&C) | (B&C), but that requires more instructions than the asymmetric formula does. And either way, it doesn't matter which of the three reads goes into A, just as long as something goes there.

@Tepples
Yeah, it's probably not any more effective than the other methods, but it's indeed another way to do it. What would be great is if the code could be simplified some more, in which case it'd have a size and speed advantage, if it doesn't already.
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Revisiting DMC-safe controller reading

Post by rainwarrior »

Note that if you're working under the assumption that 3 reads is sufficient, and at least 2 are equal, then you really only need to do one bytewise compare.

1. Presume that A = B or A = C or B = C:
2. If A = B then just take A or take B.
3. If A != B, then either A = C or B = C. Take C for either case (there is no need to actually compare).

The bytewise version is something like:

Code: Select all

    lda A
    cmp B
    beq end ; A=B, keep A
    lda C   ; A!=B implies A=C or B=C, keep C
end:
Also note that if A=B you don't even have to poll for C, which is a lot bigger savings than the comparision logic itself. (Also, if you're polling as you go, you don't need to store B or C either.)


Now, the presumption that at least two are equal could in theory be a false presumption, but given what tepples pointed out (i.e. a bit deletion invalidates the whole byte), I think it's as strong a presumption as you're starting with for the A/B/C bit-majority approach.

With the presumption that no more than 1 in 3 consecutive reads will fail, then they seem equivalently correct. Speed differences I think would be down to how often a deleted bit comes up. If you account for that, I think the bitwise majority approach is unfortunately the worst of these three:

1. Poll until 2-in-a-row: min 2 polls (common), max 4 polls (rare).
2. Poll A=B or C: min 2 polls (common), max 3 polls (rare).
3. Poll A,B,C bitwise majority: min/max 3 polls (always).

Though worth noting that there are some extremely rare edge cases where 1 could poll more (or many more) than 4 times, whereas the 2/3 will always terminate within 3 (whether "right" or "wrong"). Not really an issue unless you need to make severe restrictions about timing.

Edit: after further consideration, the bitwise method definitely seems superior in the rare worst case. See below.
Last edited by rainwarrior on Sun May 08, 2016 9:50 pm, edited 1 time in total.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Revisiting DMC-safe controller reading

Post by Drag »

That's a nice shortcut, but there's a problem: when A and B don't match and C is the DMC-glitched read, C gets taken, even though it's a totally invalid byte, so you really do need to check all three combinations of bytes.

In bitwise majority, the glitched byte does not have the power to change the state of a button by itself; it requires the button's state in one of the other (valid) bytes to match it, meaning the glitched state either coincides with an intentional state, or it doesn't and gets ignored.

Also, there may not be a big drawback in only performing two reads, and using the previous frame's joypad byte as byte A. The main reason for three new reads is so the result is more likely to reflect a new controller state, rather than the previous one. For instance, going from no buttons pressed to a single button pressed, if one read is glitched, the old state of no buttons pressed is kept for one frame, versus if three new reads were performed, it's likely to receive two bytes reflecting the pressed button, meaning the newly pressed button is reflected in the result. If the DMC glitch consistently occured each time the joypad routine was called, if it only did two reads, it'd be stuck in the old state.

Edit: You could combine methods though; perform two reads, if they match, good! If not, do a third read and then do bitwise majority.

Also worth noting, a bit deletion means some part of the byte is still valid. The A button is least likely to be affected by a dmc glitch, followed by B, start, select, up, down, left, and finally right, which is most likely to be affected. A glitched byte isn't good to use as the joypad status, but bitwise, a portion of the byte may still hold valid button states.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Revisiting DMC-safe controller reading

Post by tepples »

On an NES with an official controller (NES-004 or NES-039), Right will always be pressed in a glitch read. This can be used as an optimization if you detect an official controller at power-on.

NOTE: Controllers other than NES-004 or NES-039, particularly the Four Score accessory (NES-034) and some unlicensed controllers, do not obey this rule. Test for this when powering on the system by seeing if reads 9 through 16 are all 1.
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Revisiting DMC-safe controller reading

Post by rainwarrior »

Drag wrote:That's a nice shortcut, but there's a problem: when A and B don't match and C is the DMC-glitched read, C gets taken, even though it's a totally invalid byte, so you really do need to check all three combinations of bytes.
In a bytewise comparison, if all three bytes are different, there's nothing to gain by testing the other two equalities unless you're willing to poll for a 4th byte.

In the bitwise case, though, where A and B are different but valid, and C is a DMC, the bitwise should be superior result to this. I agree. All bits will match either their state in A or B. This is indeed an improvement over getting the bad DMC byte. The bit(s) changed by the user will be randomly behind one frame, or up to date, basically, and the rest would be valid. Seems like a good result to me.

So, overall, yeah if you do a compare after the first 2 reads, this is as good functionally as method 1, and faster in the worst case.

While a DPCM deletion is I think a "once every couple of seconds" case at the highest playback rate (unless you have some very unlucky regular timing), the DPCM deletion + user input case is more like "once every couple of hours", if I remember correctly. Not that it's not worth thinking about, stability is important, but we should know how much we actually stand to gain from the optimization.


So, yeah. Your bitwise version (3) with an early compare is superior to the 3-bytes version (2), and very slightly superior to the poll-until-stable "classic" version (1), as far as I can tell.
User avatar
norill
Posts: 26
Joined: Wed Dec 07, 2016 12:05 am
Location: PAL

Re: Revisiting DMC-safe controller reading

Post by norill »

can't you poll only once and compare with previous frame and bail out early if it matches? most of the time it would match, so this sounds like a pretty good heuristic.
User avatar
aquasnake
Posts: 515
Joined: Fri Sep 13, 2019 11:22 pm

Re: Revisiting DMC-safe controller reading

Post by aquasnake »

DMC interferes with joypad reading, which affects all bits, the obtained key value is shifted one bit to the left. When an error reading occurs, a whole byte is wrong, not just a bit. For the recognition of a single key (except combined keys), a bit error can still be filtered through the algorithm, but it is not suitable for multiple keys to be pressed together. I doubt what this algorithm is expected to achieve. The comparison bit algorithm is faster than byte comparison, but the key value accuracy is the lowest.

I think the speed performance of different algorithms:

three reads match by bit > three reads match by byte > repetitive 2-byte reads

In terms of stability and safety:
repetitive 2-byte reads > three reads match by byte > three reads match by bit

(A & (B | C)) | (B & C)
Four ORA/AND/EOR operations are a little faster than three repetitions of CMP + BEQ, but they are limited. Compared with the reduction of accuracy, I choose to perform three fixed reads and compare any two by byte.

As for the repetitive reading cycle for 2 times, the execution time of this algorithm is unpredictable. In the worst case, it may repeat reading for 5-9 times. It is not suitable for games requiring fast key recognition.

I think the key frame rate should be evaluated according to the minimum frame rate, not the average frame rate.

Basically, the key frame rate of 12-15fps is better than that of 5-28fps
Post Reply