It is currently Tue Oct 24, 2017 4:38 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Thu Sep 10, 2015 8:28 am 
Offline

Joined: Fri Aug 29, 2014 1:45 pm
Posts: 63
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
ADC #$33
AND #$44
ADC #$3C
;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
ADC #b01100110
AND #b10001000
ADC #b01111000


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
 Profile  
 
PostPosted: Thu Sep 10, 2015 10:33 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19122
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
  adc #%01100110
  and #%10001000
  adc #%01111000

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


Top
 Profile  
 
PostPosted: Thu Sep 10, 2015 12:22 pm 
Offline

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

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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 4 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