Ja tak na to patrzyłem, i stwierdziłem, że to może być wszystko. No i było:)
Jest to bit nieparzystości dla danych 0..255.

Kiedyś... dawno, dawno temu... w czasach gdy na ziemi jeszcze pamięci FLASH nie było i gdy mikrokontrolery (MCU) miały okienko do kasowania promieniami UV, a 6502 było całkim szybkim CPU parzystość liczyłem w ten sposób:

parity  sta    v
    
        lda    #0
        sta    p
    
        lda    v
        beq    endp

loop    inc    p
        lda    v
        dec    v
        and    v
        sta    v
        bne    loop
    
endp    lda    p
        and    #1
        rts

a jak trzeba było mieć wynik ultra-szybko to się robiło look_up_table (LUT):

        ldy    #0

l0      tya
        jsr    parity
        sta    p_lut,y
    
        iny
        bne l0

i potem obliczenie parzystości danego bajtu było trywialne i szybkie, bo wystarczyło sięgnąć do tabelki.

Aby uzyskać wzór który wygenerował marok wystarczy albo skorzystać z p_lut, albo skorzystać z procedury parity:

        ldy    #0

l1      tya
        lda    p_lut,y

;       jsr    parity         ; --> gdy nie chcemy korzystać z look-up-table

        lsr    @
        ror    @
        sta    ($58),y
    
        iny    
        bne    l1

        lda    #$21
        sta    $22f

Jeżeli nie używamy LUT, to czas wykonania procedury "parity" jest oczywiście zależny od liczby "ustawionych" bitów w bajcie.

Oczywiście pomysł algorytmu nie był mój, podpatrzyłem go w jakimś artykule o programowaniu w C i przeniosłem sobie ten kod na assembler 6502. O ile dobrze pamiętam to powyższy algorytm bazował na sposobie liczenia bitów zaproponowany przez Brian-a Kernigan-a, a tenże algorytm (zliczania bitów) był opublikowany w książce "C Programming Language 2nd Ed." (by Brian W. Kernighan and Dennis M. Ritchie). Książka pochodziła chyba z okolic 1988 roku.

Wersja bez petli, czas wykonania staly niezaleznie od ilosci ustawionych bitow.
Kazdy dodatkowy bajt to dodatkowe 3-4 instrukcje w zaleznosci od implementacji(przyklad: parity16)

        org $600
p       equ $80      

start   ldy #0
l1      tya

        jsr parity8  

        lda #0
        ror @
        sta ($58),y

        iny    
        bne l1

        lda #$21
        sta $22f
l0      jmp l0


parity16 sta p   ;16b argument in A,X  
         txa
         eor p

parity8 sta p    ;8b argument in A
        lsr
        lsr
        lsr
        lsr
        eor p
        sta p
        lsr
        lsr
        eor p
        sta p
        lsr
        eor p
        lsr
        rts        ;parity in c

hi hi hi... wiedziałem że to się tak skończy :D nie wklejałem swojego wiekowego kodu aby udowadniać jaki jest szybki... to tak jak pisałem "kalka" algorytmu Kernigan-a przepisana bez jakichś specjalnych optymalizacji, bo i tak użycie LUT o wielkości 256 bajtów jest nie do pobicia, ale skoro zaczyna się "walka na cykle", to ja będę uparty jak osioł :D tzn. będe obstawał przy swoim (żartuję oczywiście), ale w ramach eksperymentu myślowego wyobraźmy sobie następującą procedurę testową:

st      sei
        inc    $d40e
        lda    $d40b
        bne    *-3
        sta    $d400

m_loop  lda    $d40b
        bpl    *-3
        lda    $d40b
        bmi    *-3
        lsr    $d01a

        ldx    #$00
l1      txa

        jsr    parity

        inx
        bne    l1

        inc    $d01a
        lda    $d40b
        cmp    vc_max
        bcc    l_nup
        sta    vc_max

l_nup    jmp    m_loop

A więc synchronizujemy się z VBL (powrót pionowy), obliczamy parzystość dla wszystkich bajtów od $00 do $FF, po czym odczytujemy wartość vcount ($D40B) sprawdzamy czy jest ona mniejsza czy większa niż poprzednio odczytana i zapamiętujemy ową wartość tylko jeżeli jest większa niż poprzednio odczytana (czyli zapamiętujemy najbardziej pesymistyczny przypadek)... i tak pętlimy w kółko (wartość vc_max) można odczytać pod debuggerem/emulatorem.

I teraz skoro już mamy procedurę testową zaproponuje swoje "zoptymalizowane" rozwiązanie, skoro użyłeś rej. Y (moja stara procka nie używała rejestrów X,Y, tylko A i lokacji na stronie zerowej) to zakładam że również mogę a więc:

parity  sta    v
    
        ldy    #0
    
        ora    #0
        beq    endp

loop    iny
        sec
        sbc    #1

        and    v
        sta    v
        bne    loop
    
endp    tya
        lsr    @
        rts

^^^ a więc tak jak u Ciebie, wejście rej. A, wyjście C.

I teraz prezentacja wyników: (mniej --> lepiej)

     LUT: $0D
   willy: $40
lizard_1: $6A
   seban: $6F
lizard_2: $78
qbahusak: $85

nie sądziłem że wyjdą z tego wyścigi na cykle! Ale skoro się zaczeło to czemu nie! Na pewno wyjdzie z tego coś fajnego! :)

EDIT1: o widzę że szybko się dzieje, willy dopisał wersję xor-based :D że tak powiem mocno HDL-owo się zrobiło! i szybko! :D uzupełniam zatem tabelkę.
EDIT2: dodałem do tabelki wyniki procek zaproponowanych przez Lizarda.

Oczywiście że wszystko można, nawet zrobić benchmark tak aby faworyzował dany algorytm, zresztą to i tak nie istotne... willy zapodał taki algo który nie zależy od ilości zapalonych/zgaszonych bitów. Zresztą każdy może powalczyć, do tego posta dodaję źródła na prędce skleconego "benchmarka"... to czy liczymy wszystkie wartości ($00-$FF) czy też sekwencję pseudo-losową ($D20A) ma niewielkie znaczenie, tzn. nie zamienia miejsc na liście w tym moim pseudo-benchmarku ;D

Jeżeli chodzi o ten mój ślimakowaty algo bazujący na pomyśle Kernigana, to podobało mi się w nim to że nie był zależny czasowo od wartości, np. czas wykonania obliczeń zarówno dla wartości $AA,$55,$0F,$F0 będzie identyczny... tzn. pętla skończy się po 4 przebiegach ... Zresztą różnice (w porównaniu z Twoją implementacją) są niewielkie... i całe te nasze wyścigi są czysto "akademickie", to takie udowadnianie wyższości jednych świąt nad drugimi ;-)

EDIT: Wyniki w tabelkach się nieco zmieniły (na wyższe) ponieważ w stosunku do wersji pierwotnej przybyło kodu w pętli pomiarowej, a nie chciało mi się już bawić w kompensację tegoż, gdyż wszystkie algo zostały ponownie uruchomione w "nowych warunkach". Drastycznie przybyło czasu dla wersji LUT, ponieważ proste LDA parity_table,X zostało zastąpione skokiem do procedury (a jak wiadomo JSR/RTS kosztują sporo czasu ;P)

Wersja Willyego opisana tu: http://graphics.stanford.edu/~seander/b … tyParallel

Willy, znałeś, czy wymyśliłeś?

No to mamy nowego króla wydajności (pomijając LUT na który trzeba zmarnować 256 bajtów pamięci :P)

ja metodę xor-based znałem ze świata HDL-owego (dlatego pisałem o tym że HDL-owo się zrobiło jak ją Willy zaprezentował), tzn. stosowałem ją np. w kodzie verilogowym dla SlightSID-a, tyle że w verilogu to jeszcze prościej, w przypadku rej. konfiguracyjnego SlightSID-a musi się zgadzać parzystość danych, tylko wtedy rej konf. będzie "zaktualizowany":

inout [7:0]            ata_DAT;            // ATARI data bus
...
...
if (atr_str[7:0]==8'h41 && ~(^ata_DAT)) cfg_reg  <= ata_DAT;

a więc jak widać całe "obliczenie" parzystości sprowadza się do wykonania operacji XOR na wszystkich bitach i zanegowaniu wyniku:

parity = ~(^ata_DAT)

I to jest własnie piękno "języków opisu sprzętu!" :D

W sumie po tych moich przygodach z parzystością na początku lat '90 nigdy potem nie miałem potrzeby obliczania parzystości na 6502 i zaprezentowałem te moje wykopalisko z przeszłości bez większego zastanawiania się nad problemem, nawet nie chodziło mi o żaden wyścig na cykle, a temat potraktowałem jako ciekawostkę, która koniec końców dzięki waszym postom przekształciła się całkiem ciekawy wątek. W dodatku QbaHusak zainspirował mnie to optymalizacji i napisania tego mini-bechmarka, wiem że nie jest on doskonały ani jakiś "pro", ale mniej więcej spełnia swoje zadanie pozwalając zweryfikować czy każda z procedur działa poprawnie i ile czasu się wykonuje.

Ostatni kod zaprezentowany przez Willy-iego (ten z 6502.org) pokazuje jak bardzo ekstremalnie można zoptymalizować każdy problem! :) To się nazywa pomysłowe wykorzystanie dostępnych instrukcji CPU aby osiągnąć efekt końcowy :D Ten fragment kodu w zestawieniu z verilogową implementacją bardzo fajnie pokazuje jak rozbić problem natury typowo równoległej na coś co da się wykonać etapami, i co ciekawe nie krok po kroku (metodą zliczania poszczególnych jedynek) ale jak wykorzystać możliwości prymitywnego ALU którym dysponuje 6502 do "zrównoleglenia" operacji.

@marok: dzięki za miłe słowa, jednak uważam że nie robię nic wyjątkowego, a to że czasami mi coś wyjdzie można chyba tłumaczyć tylko tym że jak mnie jakaś rzecz zainteresuje to staram się poznać dany temat jak najlepiej, czy też na tyle na ile pozwala moja możliwość percepcji. Sądzę że inni są o wiele bardziej sprawni w różnych kwestiach. Dla mnie niektóre rzeczy są po prostu poza zasięgiem bo wymagają jakiegoś mega abstrakcyjnego myślenia, co w moim przypadku jest chyba jakimś problemem... mój mózg działa chyba w ten sposób że wszystko dla niego musi być logiczne i wytłumaczalne w prosty sposób, jeżeli problem jest natury abstrakcyjnej trudno zainteresować moją mózgownicę tego rodzaju problemami, tak już mam i nic na to nie poradzę :D