Calculate and set Parity

Calculate and set Parity

[Sebastian]

Hi,

I need a subroutine that calculates the parity of a record type with the
size of 16 bits. Is there some nice way
to do this? I currently have a solution were I use Unchecked_Conversion to
convert my variable to an
array booleans, then I calculate every true etc. Is there some way to do
this without using Unchecked_Conversion.

Greatful for any hints!

/S

Re: Calculate and set Parity

[Stephen Leake]

"Sebastian" <sebastian.madunic@avionics.saab.se> writes:

> Hi,
> 
> I need a subroutine that calculates the parity of a record type with the
> size of 16 bits. Is there some nice way
> to do this? I currently have a solution were I use Unchecked_Conversion to
> convert my variable to an
> array booleans, then I calculate every true etc. Is there some way to do
> this without using Unchecked_Conversion.

Why do you not want to use Unchecked_Conversion?

The calculation of parity inherently involves breaking the abstraction
of the type. Parity is defined in terms of bits; the normal operations
on the type are not.

Unchecked_Conversion is one mechanism Ada provides to let you break
the abstraction of a type. So Unchecked_Conversion _is_ the "nice" way
to do this.

Unchecked_Conversion is a violation of abstraction. That is not
_always_ a bad thing; just _usually_ a bad thing :).

-- 
-- Stephe

Re: Calculate and set Parity

[Jeffrey Carter]

Sebastian wrote:
> I need a subroutine that calculates the parity of a record type with the
> size of 16 bits. Is there some nice way
> to do this? I currently have a solution were I use Unchecked_Conversion to
> convert my variable to an
> array booleans, then I calculate every true etc. Is there some way to do
> this without using Unchecked_Conversion.

Well, you could always try

* using a machine code insertion
* using an imported C subprogram
* passing an address and size

but it you want it to be safe and readable, unchecked conversion to an 
array of Boolean seems like a good way to go. You then simply add up the 
Boolean'Pos of each element and determine if the result is even or odd 
("rem 2"). You could do an unchecked conversion to a 16-bit modular type 
and use shifts and masks to isolate the individual bits, but using 
Booleans seems simpler.

-- 
Jeff Carter
"Oh Lord, bless this thy hand grenade, that with it thou
mayst blow thine enemies to tiny bits, in thy mercy."
Monty Python and the Holy Grail

Re: Calculate and set Parity

[tmoran]

> array of Boolean seems like a good way to go. You then simply add up the
> Boolean'Pos of each element and determine if the result is even or odd
> ("rem 2").  You could do an unchecked conversion to a 16-bit modular type
> and use shifts and masks to isolate the individual bits, but using
> Booleans seems simpler.
  If speed is a consideration, and memory is available, convert to an
array of a 16 or an 8 bit type and look up the parity of each element in a
lookup table, then XOR the parities together.

Re: Calculate and set Parity

[tmoran]

> array of Boolean seems like a good way to go. You then simply add up the
> Boolean'Pos of each element and determine if the result is even or odd
> ("rem 2").  You could do an unchecked conversion to a 16-bit modular type
> and use shifts and masks to isolate the individual bits, but using
> Booleans seems simpler.
  If speed is a consideration, and memory is available, convert to an
array of a 16 or an 8 bit type and look up the parity of each element in a
lookup table, then XOR the parities together.

Re: Calculate and set Parity

[Nick Roberts]

On Mon, 16 Sep 2002 18:42:00 +0200, "Sebastian"
<sebastian.madunic@avionics.saab.se> strongly typed:

>Hi,
>
>I need a subroutine that calculates the parity of a record type with the
>size of 16 bits. Is there some nice way
>to do this? I currently have a solution were I use Unchecked_Conversion to
>convert my variable to an
>array booleans, then I calculate every true etc. Is there some way to do
>this without using Unchecked_Conversion.

From the Intel documentation:

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

This flag is set by any arithmetic instruction.

Assuming your 16-bit number is in DataHi:DataLo, the following code on any
IA machine should leave the answer in DL:

   MOV AL, DataLo  ; load a byte
   AND AL, AL      ; set PF
   LAHF            ; load flags byte
   SHR AH, 2       ; shift PF into bit 0
   AND AH, 1       ; mask off all other bits
   MOV DL, AH      ; result into DL
   MOV AL, DataHi
   AND AL, AL
   LAHF
   SHR AH, 2
   AND AH, 1
   XOR DL, AH      ; parities must be XORed to get cumulative result

I think most other architectures provide something similar.

I'll leave the details as an exercise ;-) HTH

-- 
Nick Roberts
Per Ardua ad Disastra

Re: Calculate and set Parity

[tmoran]

The example Intel code shifts and masks once for each of the two bytes.
You can do your XORs and just shift and mask once when you're done.

Re: Calculate and set Parity

[tmoran]

The XOR of the parities equals the parity of the XORed bytes.
Thus the code can be shortened:

>  MOV AL, DataLo  ; load a byte
>  AND AL, AL      ; set PF
  change AND above to XOR AL,DataHi
>  LAHF            ; load flags byte
>  SHR AH, 2       ; shift PF into bit 0
>  AND AH, 1       ; mask off all other bits
>  MOV DL, AH      ; result into DL
  drop the following lines
>  MOV AL, DataHi
>  AND AL, AL
>  LAHF
>  SHR AH, 2
>  AND AH, 1
>  XOR DL, AH      ; parities must be XORed to get cumulative result

Re: Calculate and set Parity

[Nick Roberts]

On Wed, 18 Sep 2002 00:17:15 GMT, tmoran@acm.org strongly typed:

>The XOR of the parities equals the parity of the XORed bytes.
>Thus the code can be shortened:
>...

Absolutely correct. I forgot this in my haste (and the lateness of the
hour). The revised code then is:

   MOV AX, Data    ; load a 16-bit word
   XOR AL, AH      ; XOR upper byte with lower
                   ; and at the same time set PF
   LAHF            ; load flags byte
   SHR AH, 2       ; shift PF into bit 0
   AND AH, 1       ; mask off all other bits

which leaves the result in AH. 

-- 
Nick Roberts
Per Ardua ad Disastra

Re: Calculate and set Parity

[SteveD]

For this application I think the use of Unchecked_Conversion is the most
straightforward.

Personally I would convert to an array of elements of type "mod 2" and then
do XOR's on all elements of the array to obtain the parity.

SteveD

"Sebastian" <sebastian.madunic@avionics.saab.se> wrote in message
news:am518n$qbq$1@newstoo.ericsson.se...
> Hi,
>
> I need a subroutine that calculates the parity of a record type with the
> size of 16 bits. Is there some nice way
> to do this? I currently have a solution were I use Unchecked_Conversion to
> convert my variable to an
> array booleans, then I calculate every true etc. Is there some way to do
> this without using Unchecked_Conversion.
>
> Greatful for any hints!
>
> /S
>

Parity using 'Write, was Re: Calculate and set Parity

[tmoran]

Assuming a reasonable compiler implementation of streams, where extra
bits from base type expansion are zeros, here's a way to calculate
the parity (or byte checksum) of an arbitrary record using 'write.
It accumulates a checksum in a stream object, and uses functions to
fetch a byte or a parity boolean from that accumulated checksum element.
  S : aliased Xors.Stream_Type;
  type something is record ...
  ...
  S.Check_Element := 0;
  Some_Record_Type'Write(S'access, R);
  Parity := Xors.Parity(S);
  Checksum_Byte := Xors.Check_Byte(S);
  ...

with Ada.Streams;
package Xors is

  type Stream_Type is new Ada.Streams.Root_Stream_Type with record
    Check_Element: Ada.Streams.Stream_Element := 0;
  end record;

  procedure Read(Stream : in out Stream_Type; -- nop
                 Item   :    out Ada.Streams.Stream_Element_Array;
                 Last   :    out Ada.Streams.Stream_Element_Offset);

  procedure Write(Stream : in out Stream_Type;
                  Item   : in     Ada.Streams.Stream_Element_Array);

  function Check_Byte(Stream : Stream_Type) return Ada.Streams.Stream_Element;

  function Parity(Stream : Stream_Type) return Boolean;

end Xors;

package body Xors is
  use Ada.Streams;

  procedure Read(Stream : in out Stream_Type; -- nop
                 Item   :    out Stream_Element_Array;
                 Last   :    out Stream_Element_Offset) is
  begin
    Last := Item'First - 1;
  end Read;

  procedure Write(Stream : in out Stream_Type;
                  Item   : in     Stream_Element_Array) is
  begin
    for I in Item'range loop
      Stream.Check_Element := Stream.Check_Element xor Item(I);
    end loop;
  end Write;

  function Check_Byte(Stream : Stream_Type) return Stream_Element is
    Source  : Stream_Element := Stream.Check_Element;
    Target  : Stream_Element := 0;
  begin
    while Source /= 0 loop
      Target := Target xor (Source mod 255);
      -- assume integer'size >= stream_element'size
      Source := Stream_Element(Integer(Source) / 256);
    end loop;
    return Target;
  end Check_Byte;

  function Parity(Stream : Stream_Type) return Boolean is
    Source  : Stream_Element := Check_Byte(Stream);
    Target  : Boolean := False;
  begin
    while Source /= 0 loop
      Target := Target xor ((Source mod 2) = 1);
      Source := Source / 2;
    end loop;
    return Target;
  end Parity;

end Xors;

Re: Parity using 'Write, was Re: Calculate and set Parity

[David C. Hoos]

I think it would be better to return a type Parity_Kind is (Even, Odd),
rather than a Boolean, or else name the function Odd_Parity (or
Even_Parity), so that True and False have obvious meanings.

----- Original Message -----
From: <tmoran@acm.org>
Newsgroups: comp.lang.ada
To: <comp.lang.ada@ada.eu.org>
Sent: Wednesday, September 18, 2002 1:29 PM
Subject: Parity using 'Write, was Re: Calculate and set Parity


> Assuming a reasonable compiler implementation of streams, where extra
> bits from base type expansion are zeros, here's a way to calculate
> the parity (or byte checksum) of an arbitrary record using 'write.
> It accumulates a checksum in a stream object, and uses functions to
> fetch a byte or a parity boolean from that accumulated checksum element.
>   S : aliased Xors.Stream_Type;
>   type something is record ...
>   ...
>   S.Check_Element := 0;
>   Some_Record_Type'Write(S'access, R);
>   Parity := Xors.Parity(S);
>   Checksum_Byte := Xors.Check_Byte(S);
>   ...
>
> with Ada.Streams;
> package Xors is
>
>   type Stream_Type is new Ada.Streams.Root_Stream_Type with record
>     Check_Element: Ada.Streams.Stream_Element := 0;
>   end record;
>
>   procedure Read(Stream : in out Stream_Type; -- nop
>                  Item   :    out Ada.Streams.Stream_Element_Array;
>                  Last   :    out Ada.Streams.Stream_Element_Offset);
>
>   procedure Write(Stream : in out Stream_Type;
>                   Item   : in     Ada.Streams.Stream_Element_Array);
>
>   function Check_Byte(Stream : Stream_Type) return
Ada.Streams.Stream_Element;
>
>   function Parity(Stream : Stream_Type) return Boolean;
>
> end Xors;
>
> package body Xors is
>   use Ada.Streams;
>
>   procedure Read(Stream : in out Stream_Type; -- nop
>                  Item   :    out Stream_Element_Array;
>                  Last   :    out Stream_Element_Offset) is
>   begin
>     Last := Item'First - 1;
>   end Read;
>
>   procedure Write(Stream : in out Stream_Type;
>                   Item   : in     Stream_Element_Array) is
>   begin
>     for I in Item'range loop
>       Stream.Check_Element := Stream.Check_Element xor Item(I);
>     end loop;
>   end Write;
>
>   function Check_Byte(Stream : Stream_Type) return Stream_Element is
>     Source  : Stream_Element := Stream.Check_Element;
>     Target  : Stream_Element := 0;
>   begin
>     while Source /= 0 loop
>       Target := Target xor (Source mod 255);
>       -- assume integer'size >= stream_element'size
>       Source := Stream_Element(Integer(Source) / 256);
>     end loop;
>     return Target;
>   end Check_Byte;
>
>   function Parity(Stream : Stream_Type) return Boolean is
>     Source  : Stream_Element := Check_Byte(Stream);
>     Target  : Boolean := False;
>   begin
>     while Source /= 0 loop
>       Target := Target xor ((Source mod 2) = 1);
>       Source := Source / 2;
>     end loop;
>     return Target;
>   end Parity;
>
> end Xors;
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
>

Re: Parity using 'Write, was Re: Calculate and set Parity

[tmoran]

>I think it would be better to return a type Parity_Kind is (Even, Odd),
>rather than a Boolean, or else name the function Odd_Parity (or
>Even_Parity), so that True and False have obvious meanings.
  Agreed.  Mea culpa.