It is currently Fri Dec 15, 2017 6:38 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 9 posts ] 
Author Message
PostPosted: Sun May 08, 2016 12:31 am 
Offline

Joined: Mon Sep 27, 2004 2:57 pm
Posts: 1248
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:
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:
 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.


Top
 Profile  
 
PostPosted: Sun May 08, 2016 1:56 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7317
Location: Chexbres, VD, Switzerland
Quote:
(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:
(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.


Top
 Profile  
 
PostPosted: Sun May 08, 2016 7:10 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19348
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Sun May 08, 2016 9:22 am 
Offline

Joined: Mon Sep 27, 2004 2:57 pm
Posts: 1248
@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.


Top
 Profile  
 
PostPosted: Sun May 08, 2016 10:03 am 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5898
Location: Canada
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:
    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.

Top
 Profile  
 
PostPosted: Sun May 08, 2016 8:20 pm 
Offline

Joined: Mon Sep 27, 2004 2:57 pm
Posts: 1248
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.


Top
 Profile  
 
PostPosted: Sun May 08, 2016 8:50 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19348
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Sun May 08, 2016 9:20 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 5898
Location: Canada
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.


Top
 Profile  
 
PostPosted: Wed Dec 07, 2016 12:09 am 
Offline
User avatar

Joined: Wed Dec 07, 2016 12:05 am
Posts: 11
Location: PAL
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 10 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group