It is currently Tue Aug 21, 2018 10:42 pm

 All times are UTC - 7 hours

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Parity on NES (and 6502's)Posted: Thu Sep 10, 2015 8:28 am

Joined: Fri Aug 29, 2014 1:45 pm
Posts: 62
This is related to Hamming codes, as well as plain parity. Had a discussion on IRC and we came up with some ideas on how to implement it. Posted here so it doesn't vanish off the Internet anytime soon.

Code:
OneByteParity:
;Takes A, counts the number of 1s, and returns LSb in A.
;Divide-and-conquer method (using ZP for work)
;By alphamule
STA \$00;  Can replace this with any temp value location
LSR 4;  Divide A by 16 using 4 Logical Shift Right instructions.
EOR \$00;  4-bit pieces
STA \$00
LSR 2
EOR \$00; 2-bit pieces
STA \$00
LSR
EOR \$00;  Now A contains the result of XORing all 1-bit pieces
RTS
;19 bytes, 3+8+3+3+4+3+3+2+3=32 cycles (not counting entrance/RTS)

Code:
;Kevtris' 1st method:
sta 00h: 7x(lsr 00h : adc 00h)  ;15 bytes, 3+7(5+3)=59cycles

Code:
;Kevtris' 2nd method:
ldx #\$0 : lsr a : bcc + inx : + lsr a : bcc : + lsr a : bcc : + lsr a : bcc : + lsr a : bcc : + lsr a

: bcc : + lsr a : bcc : + lsr a : bcc : + lsr a : bcc

Code:
;Using 16-bit table
;By alphamule
STA \$00
LSR 4
EOR \$00
AND #\$0F
LDA ParityTable16,X
;13 bytes, 3+8+3+2+(4 to 5)=20 to 21 cycles

Code:
;Using 256-bit table
;Too obvious to credit anyone.  LOL, but thanks Fys+Kevtris for reminding me (more than once)!
TAX
LDA ParityTable256,X
;4 bytes, 2+(4 to 5)=6 to 7 cycles
;This can be reduced to 3 bytes and 4 cycles if careful.  LDA affects Z/N flags.
;Pushing and pulling X would be safe but add 2 bytes and a few cycles.
;If not using a mapper, LSR should be safe on ROM, and not touch A (best to pass X).
;LSR version:  X is input, C flag is output, 3 bytes, _7_ cycles

Bogax's;tpw_rules' method (new links: https://web.archive.org/web/20100225124 ... alogue.htm http://reveng.sourceforge.net/crc-catalogue/ )
Code:
;I think I am missing part of this
;lsr ; eor \$original ; and #\$55 ; adc #\$33 ; and #\$44 ; adc #\$3C
STA \$00
LSR
EOR \$00
AND #\$55
AND #\$44
;Those ANDs and ADCs look like they're using the relationship of addition with AND+XOR and it _should_
;work, but not sure what went wrong.  Will have to look closely at bit flow and logic tables...
;Edit:  Thanks tepples - seems that the original was slightly different.  When I tried the one above, it
;would not get different results when I changed the input bits.  Just a copy of a copy degradation.  ;)

Original using AA,66,88,78:
LDA  WORD
ASL
EOR  WORD
AND #b10101010
AND #b10001000

Code:
;Using carry/negative flags?
;Never even bothered as this seems useless.

Kind of a reference implementation.
Code:
TwoByteSplitParity:
;This finds the parity bits of branches of a binary tree.
;In other words, even-single bits, then even pairs, even nibbles, and so on upto both bytes.
;This is the naive recursive-parity method, using OneByteParity with A passing data in/out.
;By alphamule
LDA #\$00;  Clears the parity bits.
STA Parity

LDA EvenByte
JSR OneByteParity
ROL 3;  Repeat 3 times for 8's place.  This is actually 3 ROL instructions, obviously.
EOR Parity
STA Parity

LDA EvenByte
AND #\$F0
JSR OneByteParity
ROL 2;  4's place
EOR Parity
STA Parity

LDA EvenByte
AND #\$CC
JSR OneByteParity
ROL;  2's place
EOR Parity
STA Parity

LDA EvenByte
AND #\$AA
JSR OneByteParity
EOR Parity;  Goes directly into 1's place so no ROL
STA Parity

;Now for the odd byte
LDA OddByte
JSR OneByteParity
TAX;  1's place in X - this'll make sense at the end

LDA OddByte
AND #\$F0
JSR OneByteParity
ROL 2;  4's place
EOR Parity
STA Parity

LDA OddByte
AND #\$CC
JSR OneByteParity
ROL;  2's place
EOR Parity
STA Parity

LDA OddByte
AND #\$AA
JSR OneByteParity
EOR Parity;  Goes directly into 1's place
STA Parity

;We now have the first 4 powers of 2.  Next is both bytes.
TXA
AND #\$01
ROL 3;  8's place
EOR Parity
AND #\$08
ROL;  16's place
EOR Parity
STA Parity
RTS

Note: Incomplete
Code:
TwoByteSplitParity:
;This finds the parity bits of branches of a binary tree.
;In other words, even-single bits, then even pairs, even nibbles, and so on upto both bytes.
;This is the 256x4-bit-table method, using EOR for the 5th bit(bit 4; 16's place).
;By alphamule
LDX EvenByte
LDA BinaryParityTable,X
STA Parity;  Overwrites previous value, so no clearing needed

LDX OddByte
LDA BinaryParityTable,X
EOR Parity
STA Parity
RTS
;22 bytes code+256 bytes data=278 bytes of ROM
;2 bytes of RAM
;The code size can be reduced to 15 bytes if using ZP
;4+4+4+4+4+4+4 = 28 cycles for non-ZP, not counting entrance or RTS (this can be macroed if need be)

You can use the associative property for XOR, to get the parity of the group of bytes, by simply finding the parity of the XOR8 hash. Doing a separate XOR8 hash for odd and even bytes is also possible.
Code:
;Post-parity method using XOR8 hash
;By alphamule
;Assuming XOR8 result in A register.
STA XOR8Sum
ROR 4 ;  ROR repeated 4 times for brevity
EOR XOR8Sum
AND #\$0F
TAX
LDA ParityTable,X  ;Use 4-bit reduced value to load parity bit from an array, into A.
RTS
ParityTable:
;Note the symmetry.  This could reduced to less values but with increase in code size and cycles
;Removing the table entirely could be done by repeating the EOR with AND #33 then AND #11 or the like.
.byte 00 01 01 00 01 00 00 01
.byte 01 00 00 01 00 01 01 00
;2+4+2+2+1+2+1=14 bytes (ZP variables) with optional 3 bytes (if not ZP variables) of code memory
;16 bytes of unpacked parity table, either in ZP RAM or using 16-bit addresses
;33 bytes total PRG-ROM maximum
;Adds (3+1)+4(2)+(3+1)+2+2+4+6=4+8+4+8+6=30 cycles maximum to end of XOR8 call.

_________________
Idealogical
From: I have an idea. It seems logical. Thus everyone must agree.

Fail, fail, fail again. Keep trying, then maybe this damn thing will work. Eventually you might even know why it worked.

Last edited by alphamule on Mon Oct 05, 2015 12:35 am, edited 4 times in total.

Top

 Post subject: Re: Parity on NES (and 6502's)Posted: Thu Sep 10, 2015 10:33 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20434
Location: NE Indiana, USA (NTSC)
tpw_rules method was posted by bogax in this topic on 6502.org:
Code:
sta tmp
asl a
eor tmp
and #%10101010
and #%10001000

The ADC instructions use the carry propagation to exclusive-OR different bits in one byte.

Top

 Post subject: Re: Parity on NES (and 6502's)Posted: Thu Sep 10, 2015 12:22 pm

Joined: Fri Aug 29, 2014 1:45 pm
Posts: 62
tepples wrote:
tpw_rules method was posted by bogax in this topic on 6502.org:
Code:
sta tmp
asl a
eor tmp
and #%10101010
and #%10001000

The ADC instructions use the carry propagation to exclusive-OR different bits in one byte.

Oops, my bad. I'll correct the post.

_________________
Idealogical
From: I have an idea. It seems logical. Thus everyone must agree.

Fail, fail, fail again. Keep trying, then maybe this damn thing will work. Eventually you might even know why it worked.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 3 posts ]

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: No registered users and 3 guests

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

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki