Newbie question : types , representation

Newbie question : types , representation

[Jos De Laender]

Hi,

I'm trying to learn ADA on my own. 

My background is C programming (sorry ;-) ) and VHDL hardware
programming. The latter helps a lot , as VHDL inherited a lot of ADA.

I'm having trouble with following very simple problem , at least in
doing it portable and clean.

In base64 decoding , each ASCII character must be translated to 6 'bit'.
4 characters translate then to 3 bytes. The problem and algorithms are
trivial. In C I could do it within 5 minutes.

It would involve some bitmanipulation (shifting , anding , oring ) on
the character itself and then outputting. That's it.

However, what's unclear is how to do this in ADA types : A character
cannot be bit manipulated , and so needs some explicit translation to a
'byte' or something.
How is this usually done ? I would guess to use a modular type 2**8 ? If
I declare such a type , and I want a byte , is this guaranteed by 2**8
or do I have explicitly  to attribute it with a 'for Byte'size use 8' ?
Also I will need some kind of assignment to that modular type, say aVar
:= 2#00000011#. This will assign the value 3 to aVar ? Is this
guaranteed to have that bit pattern ? Or could I imagine a (probably
exotic) machine on which 3 is represented with another bit pattern ?
Does ADA guarantee ?
If I output aVar with a write function , is the bitpattern guaranteed ?

Thanks for all clarifications.

Jos

RE: Newbie question : types , representation

[Wilhelm Spickermann]

On 22-Aug-99 Jos De Laender wrote:

> ...
> In base64 decoding , each ASCII character must be translated to 6
> 'bit'.
> 4 characters translate then to 3 bytes. The problem and algorithms
> ...

I think there are two different problems:
  - converting 8 bit characters to 6 Bit somethings
  - packing over the byte borders

That 6-bit-something is:
type Char_64 is mod 2**6;
for Char_64'Size use 6;

The Conversion may be done using a simple Table:
type Conversion_Table_Type is array (Character) of Char_64;
Conversion_Table: constant Conversion_Table_Type := {0,1,2,3,...};

The second problem may be solveable using the following parts
(look into Cohen: Ada as a second language, 2nd Ed.; Part 19.4.5
where he solved the problem of working with Microsofts FAT12 (12 Bit
numbers in a packed array))

type Char_64_Array is array (Sometype) of Char_64;
type Packed_Char_64_Array is new Char_64_Array;
for Packed_Char_64_Array'Component_Size use 6;
pragma Pack (Packed_Char_64_Array);

Now we can use both types - the packed and the unpacked
one - in the normal way. But access to the unpacked one is much more
efficient and conversion is easy:

Packed_One: Packed_Char_64_Array;
Unpacked_One: Char_64_Array;
...
-- now we can fill the unpacked array efficiently
...
-- and now we pack them:
Packed_One := Packed_Char_64_Array(Unpacked_One);

Wilhelm

Re: Newbie question : types , representation

[Simon Wright]

Wilhelm Spickermann <wilhelm.spickermann@t-online.de> writes:

> type Char_64_Array is array (Sometype) of Char_64;
> type Packed_Char_64_Array is new Char_64_Array;
> for Packed_Char_64_Array'Component_Size use 6;
> pragma Pack (Packed_Char_64_Array);

I would be very surprised if this didn't depend on the endianness of
your target machine (eg, probably OK on x86, probably not on SPARC)

Re: Newbie question : types , representation

[Martin C. Carlisle]

You need to be very careful with the below.  This works fine if, like
Cohen, you are ONLY interested in these two representations.  I just
implemented a Base-64 converter this weekend, and I found the bit order
on Win 98 to be frustrating, and GNAT didn't support changing it (or
else I was doing it wrong).  The modular type worked best for me.
Here's what the bits looked like:

yyxxxxxx zzzzyyyy wwwwwwzz

Note the six bits making up y and z aren't even contiguous.

--Martin

In article <XFMail.990822164551.wilhelm.spickermann@t-online.de>,
Wilhelm Spickermann  <wilhelm.spickermann@t-online.de> wrote:
>The second problem may be solveable using the following parts
>(look into Cohen: Ada as a second language, 2nd Ed.; Part 19.4.5
>where he solved the problem of working with Microsofts FAT12 (12 Bit
>numbers in a packed array))
>
>type Char_64_Array is array (Sometype) of Char_64;
>type Packed_Char_64_Array is new Char_64_Array;
>for Packed_Char_64_Array'Component_Size use 6;
>pragma Pack (Packed_Char_64_Array);
-- 
Martin C. Carlisle, Asst Prof of Computer Science, US Air Force Academy
carlislem@acm.org, http://www.usafa.af.mil/dfcs/bios/carlisle.html
DISCLAIMER:  This content in no way reflects the opinions, standards or 
policy of the US Air Force Academy or the United States Government.

Re: Newbie question : types , representation

[Martin Dowie]

there is a predefined package in Ada95 called 'Interfaces' which defines
modular types and a whole heap of operations to manipulate them as you
require.

try following this link -

http://www.adahome.com/rm95/rm9x-B-02.html#3

Jos De Laender wrote:

> Hi,
>
> I'm trying to learn ADA on my own.
>
> My background is C programming (sorry ;-) ) and VHDL hardware
> programming. The latter helps a lot , as VHDL inherited a lot of ADA.
>
> I'm having trouble with following very simple problem , at least in
> doing it portable and clean.
>
> In base64 decoding , each ASCII character must be translated to 6 'bit'.
> 4 characters translate then to 3 bytes. The problem and algorithms are
> trivial. In C I could do it within 5 minutes.
>
> It would involve some bitmanipulation (shifting , anding , oring ) on
> the character itself and then outputting. That's it.
>
> However, what's unclear is how to do this in ADA types : A character
> cannot be bit manipulated , and so needs some explicit translation to a
> 'byte' or something.
> How is this usually done ? I would guess to use a modular type 2**8 ? If
> I declare such a type , and I want a byte , is this guaranteed by 2**8
> or do I have explicitly  to attribute it with a 'for Byte'size use 8' ?
> Also I will need some kind of assignment to that modular type, say aVar
> := 2#00000011#. This will assign the value 3 to aVar ? Is this
> guaranteed to have that bit pattern ? Or could I imagine a (probably
> exotic) machine on which 3 is represented with another bit pattern ?
> Does ADA guarantee ?
> If I output aVar with a write function , is the bitpattern guaranteed ?
>
> Thanks for all clarifications.
>
> Jos

Re: Newbie question : types , representation

[Robert Dewar]

In article <37BFC251.601ADF8F@village.uunet.be>,
  Jos De Laender <De_Laender-De_Winter@village.uunet.be> wrote:
> In C I could do it within 5 minutes.

Probably by making unwarranted assumptions :-)

> It would involve some bitmanipulation (shifting , anding ,
> oring ) on
> the character itself and then outputting. That's it.
>
> However, what's unclear is how to do this in ADA types : A
> character
> cannot be bit manipulated , and so needs some explicit
> translation to a
> 'byte' or something.
> How is this usually done ? I would guess to use a modular type
2**8 ? If
> I declare such a type , and I want a byte , is this guaranteed
by 2**8
> or do I have explicitly  to attribute it with a 'for Byte'size
use 8' ?

Is char guaranteed to be 8 bits in C, answer no ...

> Also I will need some kind of assignment to that modular type,
say aVar
> := 2#00000011#. This will assign the value 3 to aVar ? Is this
> guaranteed to have that bit pattern ?

nope, and of course there is no such guarantee in C either

> Or could I imagine a (probably
> exotic) machine on which 3 is represented with another bit
pattern ?

If you want to imagine such machines, your imagination is
equally relevant in C or Ada.

> Does ADA guarantee ?
> If I output aVar with a write function , is the bitpattern
guaranteed ?

nope, and neither does C

> Thanks for all clarifications.

Bottom line here: Don't get carried away by the formalism here.
Write reasonable code with reasonable assumptions, as you would
in C. Your low level bit twiddling stuff may be a target
dependent, at least from a theoretical point of view, but that's
not a terrible crime (and certainly no worse a crime in Ada
than in C :-)


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Newbie question : types , representation

[Wolfgang Jeltsch]

Robert Dewar wrote:

> [...]
> > Also I will need some kind of assignment to that modular type,
> say aVar
> > := 2#00000011#. This will assign the value 3 to aVar ? Is this
> > guaranteed to have that bit pattern ?
>
> nope, and of course there is no such guarantee in C either
> [...]

Oops! I thought shifting on modular types would not work with the internal
representation of the value but with its binary representation so that these
operations would be platform independent. Is this really not the case? If not
wouldn't this mean that the shift operations are useless if you want to write
portable code?

Wolfgang

************************************************************************
Wolfgang Jeltsch
    jeltsch@tu-cottbus.de
        http://www-user.tu-cottbus.de/~jeltsch
************************************************************************

Re: Newbie question : types , representation

[tmoran]

From an old base64 decoder, slightly modified from Ada 83 to Ada 95:

  type bytes is mod 256;
  for bytes'size use 8;
  package out_io is new sequential_io(bytes);

  subtype base64s is integer range 0 .. 63;
  a_byte:bytes:=0;
  next_byte:bytes:=0;
  type slots is mod 4;
  pack_di:slots:=0;

  procedure put(n:in base64s) is
  begin
    case pack_di is
      when 0 => a_byte:=bytes(n)*4;
      when 1 => out_io.write(f_output, a_byte+bytes(n/16));
                a_byte:=bytes((n mod 16)*16);
      when 2 => out_io.write(f_output, a_byte+bytes(n/4));
                a_byte:=bytes(n mod 4)*64;
      when 3 => out_io.write(f_output, a_byte+bytes(n));
    end case;
    pack_di:=pack_di+1;
  end put;

Re: Newbie question : types , representation

[jdla]

In article <7ppdon$j3p$1@nnrp1.deja.com>,
  Robert Dewar <robert_dewar@my-deja.com> wrote:
> In article <37BFC251.601ADF8F@village.uunet.be>,
>   Jos De Laender <De_Laender-De_Winter@village.uunet.be> wrote:
> > In C I could do it within 5 minutes.
>
> Probably by making unwarranted assumptions :-)

For sure. But I don't think I would have much to assume except for the
char being 8 bits.
The remainder of operations I could do on that level.
Of course I would also have to include some #ifdef 's ;-)

>
> > It would involve some bitmanipulation (shifting , anding ,
> > oring ) on
> > the character itself and then outputting. That's it.
> >
> > However, what's unclear is how to do this in ADA types : A
> > character
> > cannot be bit manipulated , and so needs some explicit
> > translation to a
> > 'byte' or something.
> > How is this usually done ? I would guess to use a modular type
> 2**8 ? If
> > I declare such a type , and I want a byte , is this guaranteed
> by 2**8
> > or do I have explicitly  to attribute it with a 'for Byte'size
> use 8' ?
>
> Is char guaranteed to be 8 bits in C, answer no ...

No, I know.

The point is however that when for a compiler/architecture it is 8 bits,
it would be 8 bits for all instances of a char , isn't it ?

Does this same property hold for modular types like 2**8 , i.e. is it
allowed that one instance takes 8 bits and another 16 bits , due to
other optimization ?

How does the use 'size influence this ?

>
> > Also I will need some kind of assignment to that modular type,
> say aVar
> > := 2#00000011#. This will assign the value 3 to aVar ? Is this
> > guaranteed to have that bit pattern ?
>
> nope, and of course there is no such guarantee in C either

Again I know. But in C I would start from characters with known
representation (i.e. ascii) and do bitlevel operations. I would not need
the assignment on that level.

>
> > Or could I imagine a (probably
> > exotic) machine on which 3 is represented with another bit
> pattern ?
>
> If you want to imagine such machines, your imagination is
> equally relevant in C or Ada.

For me this isn't _that_ imaginery. I constructed already (small)
processing units in which the representation was quite different for
power reasons. Luckily I didn't have to construct compilers for it ...

>
> > Does ADA guarantee ?
> > If I output aVar with a write function , is the bitpattern
> guaranteed ?
>
> nope, and neither does C
>
> > Thanks for all clarifications.
>
> Bottom line here: Don't get carried away by the formalism here.
> Write reasonable code with reasonable assumptions, as you would
> in C. Your low level bit twiddling stuff may be a target
> dependent, at least from a theoretical point of view, but that's
> not a terrible crime (and certainly no worse a crime in Ada
> than in C :-)

Thanks for the answer. ADA has as least the advantage that it makes you
_think_ about those issues. But I didn't see however too much of
practical answers how to do, in a ADA way and without spoiling to much
processor cycles in converting hence and back. But I'll find out for
sure ...

>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Newbie question : types , representation

[Matthew Heaney]

In article <7ptsgn$nvp$1@nnrp1.deja.com> , jdla@my-deja.com  wrote:

> But I didn't see however too much of practical answers how to do, in a ADA way
> and without spoiling to much processor cycles in converting hence and back.

What makes you think that the "Ada way" is more expensive wrt processor
cycles?  How do you know that Ada isn't faster than C?

Re: Newbie question : types , representation

[Jos De Laender]

Matthew Heaney wrote:
> 
> In article <7ptsgn$nvp$1@nnrp1.deja.com> , jdla@my-deja.com  wrote:
> 
> > But I didn't see however too much of practical answers how to do, in a ADA way
> > and without spoiling to much processor cycles in converting hence and back.
> 
> What makes you think that the "Ada way" is more expensive wrt processor
> cycles?  How do you know that Ada isn't faster than C?

I didn't claim that ! I'm not starting one of those stupid 'this
language is better wars'. I'm just asking how I can express the problem
equally elegant/fast in ADA.

What I do know that in C, I can do all of my operations (shifting,
anding ..) on chars.
It's ugly in the sense that I'm mixing really semantics of chars and
bytes and integers and whatever. But on compiler output I can expect a
fairly optimal implementation.

In ADA , I think (but this was part of the question) , I have to go
through some tables and through some conversion functions. Although it
is not necessarily so , there is at least the increased risk of less
optimal implementation, because the compiler has to find out those
things. I didn't say this is not possible, I asked how one could write
it without having this risk.

Best regards,

Jos De Laender

Re: Newbie question : types , representation

[Brian Rogoff]

On Tue, 24 Aug 1999, Jos De Laender wrote:
> What I do know that in C, I can do all of my operations (shifting,
> anding ..) on chars.

In Ada (we always mean Ada 95 here when we say Ada, a situation unlike the 
VHDL world ;-) the package Interfaces contains the Shift_Left,
Shift_Right, and other operations you're looking for, as well as types
like Unsigned_8, Unsigned_16, etc. These are probably what you're looking
for. I rather wish there were operators (<<, >>) for this, as in C, but
it is not a problem, just my syntactic preference. I won't even start 
talking about <<= :-)

> It's ugly in the sense that I'm mixing really semantics of chars and
> bytes and integers and whatever. But on compiler output I can expect a
> fairly optimal implementation.

I guess I don't find it (C) that ugly here, but my tastes are my own. C is
a very low level language compared to Ada, so it is to be expected that it 
would be this way. C declaration syntax is ugly IMO.

> In ADA , I think (but this was part of the question) , I have to go
> through some tables and through some conversion functions. Although it
> is not necessarily so , there is at least the increased risk of less
> optimal implementation, because the compiler has to find out those
> things. I didn't say this is not possible, I asked how one could write
> it without having this risk.

If you know that characters are the same size as your "byte" type, be it
an Interfaces.Unsigned_8 or a System.Storage_Element then it should be OK 
to use Unchecked_Conversion if you're worried about the overhead of a
conversion function, but I really can't imagine any overhead even from a 
safe type conversion if you turn checking off, which you really must do if 
you want to compare with C. I don't understand why you think there is some 
table lookup involved.

Part of the problem with C and Ada comparisons is that every C operation is  
unchecked, whereas in Ada everything is checked by default. You have to
know enough about your Ada compiler to turn off those checks when doing
the performance comparisons.

-- Brian

Re: Newbie question : types , representation

[Jos De Laender]

    Thanks,

this was really very to the point for what concerns my problem !
I learned from it.
Some small comments furtheron between your text.

Best regards,

Jos

Brian Rogoff wrote:

> If you know that characters are the same size as your "byte" type, be it
> an Interfaces.Unsigned_8 or a System.Storage_Element then it should be OK
> to use Unchecked_Conversion if you're worried about the overhead of a
> conversion function, but I really can't imagine any overhead even from a
> safe type conversion if you turn checking off, which you really must do if
> you want to compare with C. I don't understand why you think there is some
> table lookup involved.

I think here I was partly wrong. The table lookup is needed for the original
algorithm where I got the problem (base64 decoding) , but it is equally needed
in C as in ADA. So forget indeed this one ...

>
>
> Part of the problem with C and Ada comparisons is that every C operation is
> unchecked, whereas in Ada everything is checked by default. You have to
> know enough about your Ada compiler to turn off those checks when doing
> the performance comparisons.

I realize this extremely well ! As I told you I do know VHDL quite well , and I
have to use always this same explanation to explain the 'C is faster crowd'
that when comparing the same functionality , including the checking , it isn't.

>
>
> -- Brian

  Jos De Laender

Re: Newbie question : types , representation

[tmoran]

> In base64 decoding , each ASCII character must be translated to 6 'bit'.
> 4 characters translate then to 3 bytes. The problem and algorithms are
> trivial. In C I could do it within 5 minutes.

Given modern RAM sizes, how about the initally mentioned table lookup
   type Base64 is range 0 .. 63;
   type Base64_String is array(integer range <>) of Base64;
   subtype Base64_Quad is Base64_String(1 .. 4);

   type Byte is range 0 .. 255;
   type Byte_String is array(integer range <>) of Byte;
   subtype Byte_Triple is Byte_String(1 .. 3);

   To_Base64 : array(Byte, Byte, Byte) of Base64_Quad;
   From_Base64 : array(Base64, Base64, Base64, Base64) of Byte_Triple;
   -- initialize the arrays once, at start time

   -- timing test
   data: Base64_String(1 .. 200);
   result : Byte_String(1 .. 150);
   si,di : positive;
begin
  for i in 1 .. 100_000 loop
    si := 1;
    di := 1;
    for j in 1 .. data'length/4 loop
      result(di .. di+2) := From_Base64(Data(si), Data(si+1),
                                        Data(si+2), Data(si+3));
      di := di+3;
      si := si+4;
    end loop;
  end loop;

On my P200, this sort of thing executes at a rate of about 6 Base64
characters, or 4 Byte's, converted each microsecond.  Using a
modern fast CPU you would approach being I/O bound.

Re: Newbie question : types , representation

[Florian Weimer]

tmoran@bix.com writes:

>    From_Base64 : array(Base64, Base64, Base64, Base64) of Byte_Triple;

> On my P200, this sort of thing executes at a rate of about 6 Base64
> characters, or 4 Byte's, converted each microsecond.  Using a
> modern fast CPU you would approach being I/O bound.

You are kidding, aren't you?

From_Base64 is an array which is at least 48 MB in size.  If you're
encoding a compressed binary file, there will be a lot of cache misses,
which are terribly expensive.  And by the time the array has been
initialized, other methods will already have finished the conversion.

Re: Newbie question : types , representation

[David C. Hoos, Sr.]

Geoff Bull <gbull@acenet.com.au> wrote in message
news:37C621F3.C6C0DC3A@acenet.com.au...
>
>
> Jos De Laender wrote:
> >
>
> > In base64 decoding , each ASCII character must be translated to 6 'bit'.
> > 4 characters translate then to 3 bytes. The problem and algorithms are
> > trivial. In C I could do it within 5 minutes.
>
> The Ada only takes 5 minutes also:
>
> with Ada.Text_IO; use Ada.Text_IO;
>
Since the purpose of base64 encoding is usually to produce characters in
the printable set (i.e. Character'Val (32) .. Character'Val (95)), you
need to add 32 to each of your result values.

Also, to have a working program, one would need to deal with input
lengths not evenly divisible by 3.

Here's another approach:

with Ada.Unchecked_Conversion;
function Base64_Encoding (Input : String) return String
is
   type Bit is mod 2;
   for Bit'Size use 1;
   type Bit_Array is array (Positive range <>) of Bit;
   pragma Pack (Bit_Array);
   Input_Copy : String (1 .. 3 * ((Input'Length + 2) / 3));
   The_Bits : Bit_Array (1 .. 8 * Input_Copy'Length);
   for The_Bits'Address use Input_Copy'Address;
   Output : String (1 .. 4 * ((Input'Length + 3) / 4));
   type Mod_64 is mod 64;
   for Mod_64'Size use 6;
   type Six_Bits is array (1 .. 6) of Bit;
   pragma Pack (Six_Bits);
   function To_Mod_64 is new Ada.Unchecked_Conversion
     (Source => Six_Bits,
      Target => Mod_64);
begin
   Input_Copy (1 .. Input'Length ) := Input;
   -- Pad the input length with NUL characters to a length evenly
   -- divisible by 3.
   for C in Input'Length + 1 .. Input_Copy'Length loop
      Input_Copy (C) := Character'Val (0);
   end loop;
   for C in Output'Range loop
      Output (C) := Character'Val
        (32 + Integer
         (To_Mod_64 (Six_Bits (The_Bits (6 * C - 5  .. 6 * C)))));
   end loop;
   return Output;
end Base64_Encoding;