Calculating Parity

[donkey]

Check eax for parity 32 bits

Code Select Expand

mov ebx,eax
shr eax,16
xor eax,ebx
xor al,ah

PF is set on even parity

Edgar

[dedndave]

i thought about that one Edgar - well - something similar   :P
i don't think it works

[donkey]

Hi Dave,

I edited and replaced the popcount method because it was slow and replaced it with a fast one. A check from 0-256 shows the one above is fine:

Code Select Expand

Line 151: EFLAGS = PF ZF IF 0000
Line 151: EFLAGS = IF 0001
Line 151: EFLAGS = IF 0010
Line 151: EFLAGS = PF IF 0011
Line 151: EFLAGS = IF 0100
Line 151: EFLAGS = PF IF 0101
Line 151: EFLAGS = PF IF 0110
Line 151: EFLAGS = IF 0111
Line 151: EFLAGS = IF 1000
Line 151: EFLAGS = PF IF 1001
etc...

[dedndave]

ok
try these values

101h
201h
10001h
20001h

all are even parity

0 to 256 isn't much of a test
for those values, OR EAX,EAX almost works

[donkey]

101h = 100000001 = EFLAGS = PF ZF IF >> correct
201h = 1000000001 = EFLAGS = PF IF >> correct
10001h = 10000000000000001 = EFLAGS = PF ZF IF >> correct
20001h = 100000000000000001 = EFLAGS = PF IF >> correct

[dedndave]

ok - let me see where i went wrong   :lol

[asm_coder]

Asm_coder,
from the intel manual:

PF (bit 2) Parity flag. Set if the least-significant byte of the result contains an even number of 1 bits; cleared otherwise.

That should explain the parity flag getting set when you xor something with itself. The CPU parity flag indicates that the low byte has even parity.

To calculate parity yourself you can use something like this:

Code Select Expand

!mov eax,9    'number to find the parity of
!mov ecx,32   'number of bits to do, may be 8 if you have bytes
!mov edx,0    'place where we'll count the bits

lp:
!shr eax,1    'move least significant bit into carry flag
!adc edx,0    'add the carry to the total so far


!dec ecx      'all done?
!jne lp       'no, go back for the next bit

'at this point edx contains a count of the ones in the original number.
'if the LSB of edx is 0 then the original number had even parity, if LSB=1 then it had odd parity
'you could test it by shifting that lsb into the carry flag:
!shr edx,1    'move lsb into carry.
!jc  OddParity    'Data has odd parity
!jnc EvenParity   'Data has even parity

Note that "parity" on it's own doesn't mean a lot. You need to be looking for "even parity" when there are an even number of ones or "odd parity" where there is an odd number of ones.
Usually parity bits are used in addition to the number to force odd or even parity to allow for a very basic check of data integrity.

So, where you require odd parity:

Code Select Expand

Original data    data parity   parity bit        Final data inc parity
                               needed to force
                               overall parity
                               to odd
9   (00001001)      Even          1              00001001 1 (3 set bits, odd parity)
27  (00011011)      Even          1              00011011 1 (5 set bits, odd parity)
31  (00011111)      Odd           0              00011111 0 (5 set bits, odd parity)     

Paul.

Okay here something I don't get again after thinking more about it,what do you mean by parity needed to force overall parity to odd,for example
we see here that 9 has even bit numbered in it's low byte and when I did loaded in olly I didn't see any instruction that would force an extra bit for example
let's see here this code as in example

Code Select Expand


mov al,9;
xor al,0;

how did the extra bit get forced then,if there isn't any tests or anything. ?

[dedndave]

if you toggle any odd number of bits, parity should reverse

xor al,1
xor al,2
xor al,4
xor al,8

xor al,7

all of those instructions reverse the parity of AL

[donkey]

Hi Dave,

My tests seem pretty reliable, I am using the following setup to test:

Code Select Expand

START:
mov ecx,StartNumber
TestParity:
mov eax,ecx

// parity check code
mov ebx,eax
shr eax,16
xor eax,ebx
xor al,ah

jnp >
invoke dw2bin,ecx,offset szTestParity ; szTestParity is a 256 byte buffer
PrintString(szTestParity)
:
inc ecx
cmp ecx,StartNumber+256
jl TestParity

invoke ExitProcess, 0

dw2bin FRAME dwValue,lpBuffer
uses edi,eax,ecx,edx

mov edi,[lpBuffer]
mov eax,[dwValue]
mov B[edi+32],0
mov ecx,31
L1:
ror eax,1
setc dl
or dl,30h
mov [edi+ecx],dl
dec ecx
jns L1

RET
ENDF

Every test I do turns out fine.

[asm_coder]

if you toggle any odd number of bits, parity should reverse

xor al,1
xor al,2
xor al,4
xor al,8

xor al,7

all of those instructions reverse the parity of AL

I m sorry I typed 9 wrong,what I meant was for example
9 = 1001
which has even set of bits in it's low byte
so when you
mov al,9;
xor al,0;

Parity flag = 1;
even though its even numbered bits.

[clive]

Both these are workable

Code Select Expand

; Input in EAX, Output EAX = 1 Odd, EAX = 0 Even

   mov edx,eax
   shr edx,16
   xor eax,edx
   mov edx,eax
   shr edx,8
   xor eax,edx

   mov eax,1 ; If you need a flag in EAX
   jpo ParityOdd

   xor eax,eax ; If you need a flag in EAX

ParityEven:

  ..

ParityOdd:


Code Select Expand

; Input in EAX, Output EAX = 1 Odd, EAX = 0 Even

   mov edx,eax
   shr edx,16
   xor eax,edx
   mov edx,eax
   shr edx,8
   xor eax,edx
   mov edx,eax
   shr edx,4
   xor eax,edx
   mov edx,eax
   shr edx,2
   xor eax,edx
   mov edx,eax
   shr edx,1
   xor eax,edx
   and eax,1

jnz ParityOdd

ParityEven:


[dedndave]

Edgar has the right stuff   :U

i ran through all 4,294,967,296 values and compared Edgars against mine

result:
other than the fact that mine has inverted the sense of parity, they match on all values   :lol
that is so because i used an odd number of XOR's to derive parity - oops
Edgars is easily smaller and faster than mine

Edgars code wins:

Code Select Expand

mov ebx,eax
shr eax,16
xor eax,ebx
xor al,ah

[asm_coder]

never mind I though it's the other way around,in which if odd number of bit,it would set the parity flag,but it was the other way around.
Which make me even wonder it said that parity flag see if number is even or odd,but here 7 = 111 which when you
mov al,7;
xor al,0

that would produce parity of 0,because 7 got odd number of bits which makes me wonder why did they design it like that .....

[asm_coder]

Edgar has the right stuff   :U

i ran through all 4,294,967,296 values and compared Edgars against mine

result:
other than the fact that mine has inverted the sense of parity, they match on all values   :lol
that is so because i used an odd number of XOR's to derive parity - oops
Edgars is easily smaller and faster than mine

Edgars code wins:

Code Select Expand

mov ebx,eax
shr eax,16
xor eax,ebx
xor al,ah

are you sure that would work ?
because here it would shift al,ah 16 bytes,which would be left is the upper half in which he xor them together to union the numbers,but you would need to union all the numbers
the bytes inside the register to see if it got even or odd number of bits.

[dedndave]

i am sure..... now   :lol