Query on portable bit extraction

Query on portable bit extraction

[Mark Johnson]

We have code that we want to run on both a big (sgi) and little (pc)
endian machine. As an example, the layout of the data in memory is...
[big_endian bit order]
Byte  0 1 2 3 4 5 6 7
21 -  X X X Y Y Y Y Y
22 -  Y Y Z Z Z Z Z Z
where we need to extract XXX as the "wait code", YYYYYYY as the "value",
and ZZZZZZ is a pad area (don't care).

On the big endian machine it was coded like this...
 Wait := (byte 21) / 2**5;
 T1 := (move bytes from bytes 21 & 22)
 T2 := T1 / 2**6;
 T1 := T2 / 2**7;
 T1 := T1 * 2**7;
 Value := T2-T1;
which won't work on the PC unless we swap the bytes in the first
assignment to T1 and looks ugly as all get out.

Thinking of records & representation specifications, I'd like to be able
to do something like this...
  subtype Wv is Natural range 0..7;
  subtype Vv is Natural range 0..127;
  subtype Pv is Natural range 0..63;
  type Wait_Value is
    record
      Wait : Wv;
      Value : Vv;
      Pad : Pv;
    end record;
  for Wait_Value use
    record
      Wait at 0 range 0..2;
      Value at 0 range 3..9;
      Pad at 1 range 2..7;
    end record;
  for Wait_Value'Bit_Order use System.High_Order_First;
which looks pretty reasonable until I get the following GNAT error
messages on the PC...
 error: attempt to specify non-contiguous field not permitted
 error: (caused by non-standard Bit_Order specified)
Hmm. After drawing it out on the white board - sure enough, the bits are
not contiguous, a byte swap is needed. Assuming I do a byte swap
somewhere, I recode the representation specification to be...
  for Wait_Value use
    record
      Wait at 1 range 5..7;
      Value at 0 range 6..12;
      Pad at 0 range 0..5;
    end record;
(assuming System.Low_Order_First bit order) which works as expected.

So - I can probably code up a portable version based on...
 - byte swap or not based on System.Default_Bit_Order
 - representation specification also based on System.Default_Bit_Order
but is this the best way to do it or should I stick w/ the original
code?

Thanks.
  --Mark Johnson
  <mailto:Mark_H_Johnson@Raytheon.com>

Re: Query on portable bit extraction

[Lutz Donnerhacke]

* Mark Johnson wrote:
>We have code that we want to run on both a big (sgi) and little (pc)
>endian machine. As an example, the layout of the data in memory is...
>[big_endian bit order]
>Byte  0 1 2 3 4 5 6 7
>21 -  X X X Y Y Y Y Y
>22 -  Y Y Z Z Z Z Z Z
>where we need to extract XXX as the "wait code", YYYYYYY as the "value",
>and ZZZZZZ is a pad area (don't care).

>Thinking of records & representation specifications, I'd like to be able
>to do something like this...
>  subtype Wv is Natural range 0..7;
>  subtype Vv is Natural range 0..127;
>  subtype Pv is Natural range 0..63;
>  type Wait_Value is
>    record
>      Wait : Wv;
>      Value : Vv;
>      Pad : Pv;
>    end record;
>  for Wait_Value use
>    record
>      Wait at 0 range 0..2;
>      Value at 0 range 3..9;
>      Pad at 1 range 2..7;
>    end record;
>  for Wait_Value'Bit_Order use System.High_Order_First;

Incorrect code: Value does cross a Storage_Element boundary. Split it into
two parts and combine them later. Example:
http://www.iks-jena.de/mitarb/lutz/ada/net/ --> i.e. IPV4 Header
 
>which looks pretty reasonable until I get the following GNAT error
>messages on the PC...
> error: attempt to specify non-contiguous field not permitted
> error: (caused by non-standard Bit_Order specified)

Correct. for xx'Bit_Order use ... does only define the direction of counting.
It does not swap or correct alignments.

>somewhere, I recode the representation specification to be...
>  for Wait_Value use
>    record
>      Wait at 1 range 5..7;
>      Value at 0 range 6..12;
>      Pad at 0 range 0..5;
>    end record;
>(assuming System.Low_Order_First bit order) which works as expected.

On both systems? Very strange.

Re: Query on portable bit extraction

[Jeffrey Carter]

I would recommend using a collection of bytes and ensuring that the same
bytes contain the same values on all platforms. Then extract the desired
parts of the desired bytes, combining them as required.

You can also, if you're sure the same bytes have the same values,
combine bytes into larger values using type conversions and shifts or
multiplications:

T1 := Shift_Left (Unsigned_16 (Byte_21), 8) or Unsigned_16 (Byte_22);
T2 := Shift_Right (T1, 6) and 2#0111_1111#; -- YYY_YYYY

Both work correctly regardless of endianness;

-- 
Jeff Carter
"I wave my private parts at your aunties."
Monty Python & the Holy Grail

RE: Query on portable bit extraction

[Steven Deller]

The issue with byte ordering actually has more to do with how you got
the data.  If you get the data as a byte stream and define an array of
bytes, then the only issue is bit order within each byte.  On the other
hand, if you get the data 4-bytes at a time "in parallel", you will need
to do byte swapping to get the fields to be adjacent.  If you get the
data one-bit at a time, then no byte swapping is needed and fields will
always be adjacent bits, regardless of the architecture.

I'm *guessing* that for the problem at hand, you received the data byte
by byte on a little-endian machine where you *defined* adjacent bits
(across bytes) using little-endian definitions of what it means to cross
a byte boundary.  If you now take that data 4-bytes at a time and send
that to big-endian machine, you will have to do byte swapping (end for
end) across the word to get fields that are adjacent (and if fields
cross 4-byte boundaries, you will have to do word swapping).  Once you
have done that, you need only count in the correct direction to see the
fields.

Its hard to describe in email, but you can probably figure it out if you
realize that size of units when exchanging data determines what type of
byte swapping is necessary (none, 2-byte pairs, 4-byte quads, 8-byte
octets, etc).

That is why this is a hard problem.  There is no *general* solution
until you know your channel width.

Regards,
Steve

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Jeffrey Carter
> Sent: Friday, October 26, 2001 8:07 PM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: Query on portable bit extraction
> 
> 
> I would recommend using a collection of bytes and ensuring 
> that the same bytes contain the same values on all platforms. 
> Then extract the desired parts of the desired bytes, 
> combining them as required.
> 
> You can also, if you're sure the same bytes have the same 
> values, combine bytes into larger values using type 
> conversions and shifts or
> multiplications:
> 
> T1 := Shift_Left (Unsigned_16 (Byte_21), 8) or Unsigned_16 
> (Byte_22); T2 := Shift_Right (T1, 6) and 2#0111_1111#; -- YYY_YYYY
> 
> Both work correctly regardless of endianness;
> 
> -- 
> Jeff Carter
> "I wave my private parts at your aunties."
> Monty Python & the Holy Grail 
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org 
> http://ada.eu.org/mailman/listinfo/comp.lang.ad> a

Re: Query on portable bit extraction

[Nick Roberts]

To be frank, I think RM95 13.5.3 shows confusion as to what 'big-endian' and
'little-endian' really mean. The RM speaks in terms of storage elements, but
these Swiftian terms - although always informal - have really always
referred to the order of bytes (not bits).

A big-endian machine's (16-bit, 32-bit, and sometimes 64-bit) integers have
the most significant byte at the lower/lowest address; a little-endian
machine's integers have the least significant byte at the lower/lowest
address. I think the terms don't sensibly apply to machines whose
Storage_Unit is not a multiple of 8. I think those machines whose
Storage_Unit is 16, 32, or 64 can be treated as big-endian if they read
bytes from byte-oriented peripherals in the order most significant byte
first.

The AARM (13.5.3 (5.b)) wants to imply that on a big-endian 32-bit machine
with byte memory addressing, bit 0 of byte 3 (the lowest addressed and most
significant byte) is the most significant bit (bit 31) of the word. This is
wrong! By every convention I've ever come across, bit 0 of byte 3 is always
interpreted as bit 24 of the word; it is bit 7 of byte 3 that is bit 31 of
the word. I believe the documentation of processor manufacturers will bear
this out. In other words, ALL architectures (both big-endian and
little-endian) are in fact Low_Order_First.

AI95-133 confirm's this thread's view that the Bit_Order attribute is purely
about how to interpret bit numbers in a record representation clause. As
such, I'm afraid I think it was misconceived. There's no need for it on any
machine, and it doesn't solve the problem that needs solving (that of big
and little endianness). Does anyone have an example where Bit_Order was
actually useful (or vital)?

Perhaps the next revision could introduce a representation attribute
Octet_Order, which would only apply to discrete types of a size which is a
multiple of 8 and greater than 8 (and would have nothing to do with record
representation clauses). The System package would define:

   type Octet_Order is (Low_Octet_First, High_Octet_First);

   Default_Octet_Order: constant Octet_Order;

Although I am pretty certain about my comments in this case, I seem to be
prone to egregious error at times, so please someone put me out of your
misery if I have committed another blunder.

Should I send a comment to ada-comment about this?

Another facility that I believe would be useful would be to be able to
specify multiple places for a component in a record representation clause.
Engineers (being engineers, poor devils ;-) often like to split up a field
returned by their equipment into lots of little pieces dotted around all
over the place.

E.g.:

   type Table_Descriptor is
      record
         Limit: Unsigned_20;
         Base: Unsigned_32;
         Typ: Descriptor_Type;
         Is_Segment: Boolean;
         DPL: Privilege_Level;
         Is_Present: Boolean;
         Is_32_Bit: Boolean;
         Is_Coarse: Boolean;
      end record;

   pragma Assert(System.Storage_Size = 8);

   for Table_Descriptor use
      record
         Limit at all (0..7 => 0 range 0..7,
                        8..15 => 1 range 0..7,
                        16..19 => 6 range 0..3);
         Base at all (0..7 => 2 range 0..7,
                       8..15 => 3 range 0..7,
                       16..23 => 4 range 0..7,
                       24..31 => 7 range 0..7);
         Typ at 5 range 0..4;
         ...
      end record;

This suggested syntax may not be the best way to do it. Implementations
could impose a limit on the number of different places specifiable for one
component. As per the AARM, the storage place attributes would not apply to
discontiguous components.

--
Nick Roberts


"Steven Deller" <deller@smsail.com> wrote in message
news:mailman.1004156810.28692.comp.lang.ada@ada.eu.org...
> The issue with byte ordering actually has more to do with how you got
> the data.  If you get the data as a byte stream and define an array of
> bytes, then the only issue is bit order within each byte.  On the other
> hand, if you get the data 4-bytes at a time "in parallel", you will need
> to do byte swapping to get the fields to be adjacent.  If you get the
> data one-bit at a time, then no byte swapping is needed and fields will
> always be adjacent bits, regardless of the architecture.
>
> I'm *guessing* that for the problem at hand, you received the data byte
> by byte on a little-endian machine where you *defined* adjacent bits
> (across bytes) using little-endian definitions of what it means to cross
> a byte boundary.  If you now take that data 4-bytes at a time and send
> that to big-endian machine, you will have to do byte swapping (end for
> end) across the word to get fields that are adjacent (and if fields
> cross 4-byte boundaries, you will have to do word swapping).  Once you
> have done that, you need only count in the correct direction to see the
> fields.
>
> Its hard to describe in email, but you can probably figure it out if you
> realize that size of units when exchanging data determines what type of
> byte swapping is necessary (none, 2-byte pairs, 4-byte quads, 8-byte
> octets, etc).
>
> That is why this is a hard problem.  There is no *general* solution
> until you know your channel width.
>
> Regards,
> Steve
>
> > -----Original Message-----
> > From: comp.lang.ada-admin@ada.eu.org
> > [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Jeffrey Carter
> > Sent: Friday, October 26, 2001 8:07 PM
> > To: comp.lang.ada@ada.eu.org
> > Subject: Re: Query on portable bit extraction
> >
> >
> > I would recommend using a collection of bytes and ensuring
> > that the same bytes contain the same values on all platforms.
> > Then extract the desired parts of the desired bytes,
> > combining them as required.
> >
> > You can also, if you're sure the same bytes have the same
> > values, combine bytes into larger values using type
> > conversions and shifts or
> > multiplications:
> >
> > T1 := Shift_Left (Unsigned_16 (Byte_21), 8) or Unsigned_16
> > (Byte_22); T2 := Shift_Right (T1, 6) and 2#0111_1111#; -- YYY_YYYY
> >
> > Both work correctly regardless of endianness;
> >
> > --
> > Jeff Carter
> > "I wave my private parts at your aunties."
> > Monty Python & the Holy Grail
> > _______________________________________________
> > comp.lang.ada mailing list
> > comp.lang.ada@ada.eu.org
> > http://ada.eu.org/mailman/listinfo/comp.lang.ad> a
>

Re: Query on portable bit extraction

[Jeffrey Carter]

Nick Roberts wrote:
> 
> AI95-133 confirm's this thread's view that the Bit_Order attribute is purely
> about how to interpret bit numbers in a record representation clause. As
> such, I'm afraid I think it was misconceived. There's no need for it on any
> machine, and it doesn't solve the problem that needs solving (that of big
> and little endianness). Does anyone have an example where Bit_Order was
> actually useful (or vital)?

I think you're mistaken. I recall (a) processor(s?) on which bit 1 was
the MSB and bit 8 the LSB of a byte. Many big-endian machines use lowest
bit # = MSB.

-- 
Jeff Carter
"I unclog my nose towards you."
Monty Python & the Holy Grail

Bit_Order useful [was Query on portable bit extraction]

[Nick Roberts]

I know there are some big-endian machines (the more recent ones, perhaps)
whose manufacturers' documentation number the LSB as 0 and the MSB as 31 or
63. Maybe some of the older ones are as Jeff suggests, although this scheme
strikes me as weird mathematically: doesn't it make sense to have a bit
numbering where the value of bit n (that it contributes, when it is 1, to
the value of the integer it is part of) is 2^n?

In fact, having said that, I think I've managed to convince myself that
Bit_Order is useful anyway.

In the RFCs, the sformat of the IP, TCP, UDP etc headers are (mostly?)
defined in terms of 32-bit words, and the bit numbers in the diagrams have
bit 0 as the MSB and 31 as the LSB. I guess the RFCs can't be considered too
esoteric, and in this case Bit_Order helps one to make the definition of a
record representation clause, e.g.:

   type IP_Header is
      record
         Version: ...
         IHL: ...
         ToS: ...
         Length: ...
         Ident: ...
         Flags: ...
         Offset: ...
         TTL: ...
         Protocol: ...
         Checksum: ...
         Source:      Internet_Address;
         Destination: Internet_Address;
      end record;

   for IP_Header'Bit_Order use High_Order_First;
   W32: constant := 32 / System.Storage_Unit;
   pragma Assert(System.Storage_Unit mod 8 = 0);

   for IP_Header use
      record
         Version      at W32*0 range 0..3;
         IHL          at W32*0 range 4..7;
         ToS          at W32*0 range 8..15;
         Length       at W32*0 range 16..31;
         Ident        at W32*1 range 0..15;
         Flags        at W32*1 range 16..18;
         Offset       at W32*1 range 19..31;
         TTL          at W32*2 range 0..7;
         ...
      end record;

And I think this clause will work on any implementation regardless of its
default bit order, and provided its storage unit is a multiple of 8. Useful
enough for me. Again, someone please say if I'm wrong about this, having
just proved once again that I (often :-) make mistakes.

Otherwise, my apologies. May I please emphasise that my criticism was not
malicious (and never is).

Finally, there's still a need (in terms of significant convenience) for
something like my proposed Octet_Order isn't there?

PS: Bit_Order doesn't solve the problem of a 1-based bit numbering scheme.
Do we need a Bit_Numbering_Base?

--
Nick Roberts


"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3BDB5FB6.94899C3C@acm.org...
> Nick Roberts wrote:
> >
> > AI95-133 confirm's this thread's view that the Bit_Order attribute is
purely
> > about how to interpret bit numbers in a record representation clause. As
> > such, I'm afraid I think it was misconceived. There's no need for it on
any
> > machine, and it doesn't solve the problem that needs solving (that of
big
> > and little endianness). Does anyone have an example where Bit_Order was
> > actually useful (or vital)?
>
> I think you're mistaken. I recall (a) processor(s?) on which bit 1 was
> the MSB and bit 8 the LSB of a byte. Many big-endian machines use lowest
> bit # = MSB.

Re: Bit_Order useful [was Query on portable bit extraction]

[Robert Dewar]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9rhlhr$u11j3$1@ID-25716.news.dfncis.de>...
> I know there are some big-endian machines (the more recent ones, perhaps)
> whose manufacturers' documentation number the LSB as 0 and the MSB as 31 or
> 63. 


This is highly confused if it happens. Bit numbering must
match byte ordering, or you get into a mess. The 68K
was notoriously messed up on this point (see the discussion
of this point in my book on microprocessors).

Certainly in Ada, the bit numbering should match the byte
ordering, or you will end up with non-contiguous fields
and a big mess.

Re: Query on portable bit extraction

[Robert Dewar]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9req9o$tlsg8$1@ID-25716.news.dfncis.de>...

> Should I send a comment to ada-comment about this?

Not before carefully checking the archives for previous
discussions, or you will just recycle. For sure you need
to read Norm Cohen's article.