Bit manipulation facilities in Ada

Bit manipulation facilities in Ada

[Robert T. Sagris]

I'm thinking about taking an Data Security and Encryption course.
The language for programming projects is open to the students.



I was wondering if any one could recommend any books that demonstrate
low level bit manipulation in Ada.

I already have 

    Ada as a Second Language
    By: Cohen

    Ada 95: Problem Solving and Program Design
    By: Feldman and Koffman

    Ada Programming and Methodology
    By: Findlay etc.

None of which seem to cover this in any detail.

The Professor has already recommended C for its built in Bit operators.
But I would like to try it in Ada, as I've never used in a class.
I could use the practice.

Robbi Sagris

Re: Bit manipulation facilities in Ada

[Srinivasan, R]

I wish I could take this course. Compression and Cryptology are two of my
pet interests. I have written a fair bit of code in Ada in this arena. IMHO
Ada is perfect for this purpose.

C in particular is horrible IMHO -- if you ever want to go back and study
the programs sometime later on. In spite of the years of C programming
experience, I find even code from reputable journals like Dr Dobbs are
somewhat unintelligble.

If you would like some samples, I will be happy to send them.

Robert T. Sagris wrote in message <36573C4D.DA431821@physics.purdue.edu>...
>I'm thinking about taking an Data Security and Encryption course.
>The language for programming projects is open to the students.
>
>
>
>I was wondering if any one could recommend any books that demonstrate
>low level bit manipulation in Ada.
>
>I already have
>
>    Ada as a Second Language
>    By: Cohen
>
>    Ada 95: Problem Solving and Program Design
>    By: Feldman and Koffman
>
>    Ada Programming and Methodology
>    By: Findlay etc.
>
>None of which seem to cover this in any detail.
>
>The Professor has already recommended C for its built in Bit operators.
>But I would like to try it in Ada, as I've never used in a class.
>I could use the practice.
>
>Robbi Sagris

Re: Bit manipulation facilities in Ada

[The Ludwig Family]

Look in the index for "modular integers" and look under "arrays", in 
particular one-dimensional boolean arrays.  For both of these categories, 
the operators "and", "or", "xor", and "not" are available.

If you cannot directly use either of these categories of types, you will 
need either to use Unchecked_Conversion (look up in the index) between your 
types and one of these types or to overload the "and", "or", "xor", and 
"not" operators to apply to your own types (the definitions of the over-
loadings perhaps using Unchecked_Conversion and the modular or boolean-array 
operators).

This is not particularly difficult, and the type-checking helps you keep 
straight what you are working with, whereas C basically allows you to hack 
around at the bits in a rather uncontrolled (and less safe) fashion.

Howard W. LUDWIG, Ph.D.

Robert T. Sagris wrote:
> 
> I'm thinking about taking an Data Security and Encryption course.
> The language for programming projects is open to the students.
> 
> I was wondering if any one could recommend any books that demonstrate
> low level bit manipulation in Ada.
> 
> I already have
> 
>     Ada as a Second Language
>     By: Cohen
> 
>     Ada 95: Problem Solving and Program Design
>     By: Feldman and Koffman
> 
>     Ada Programming and Methodology
>     By: Findlay etc.
> 
> None of which seem to cover this in any detail.
> 
> The Professor has already recommended C for its built in Bit operators.
> But I would like to try it in Ada, as I've never used in a class.
> I could use the practice.
> 
> Robbi Sagris

Re: Bit manipulation facilities in Ada

[Matthew Heaney]

In article <36573C4D.DA431821@physics.purdue.edu>, "Robert T. Sagris"
<robs@physics.purdue.edu> wrote:

>I'm thinking about taking an Data Security and Encryption course.
>The language for programming projects is open to the students.
>
>
>
>I was wondering if any one could recommend any books that demonstrate
>low level bit manipulation in Ada.

Here are some ideas.

o In general, if you want to explicitly manipulate bits, then you probably
want a modular type or a bit array.  (But realize that Ada also provides
higher-level ways of achieving the same goal, but without explicit bit
manipulation.)  Of course, you can manipulate bits on types other than
modular types or bit arrays.

o Read section B.2 of the RM95, which describes the package Interfaces. 
There are types in that package that have operations for shifting and
rotating, etc. 

o Note that your compiler may have more operations in package Interfaces
than are described in the RM.  See what extra operations are declared
there, and whether there are additional, vendor-specific children of
package Interfaces.

o Your compiler may provide ways (via pragma Import, and pragma Intrinsic)
to give bit manipulation operations (like shifting and rotating) to types
other than those declared in package Interfaces.

o Read about modular types.  Modular types have predefined operations for
and'ing and or'ing etc.

o Combine and'ing (to mask a range of bits) with shifting to get the bits
you want.

o Read about bit arrays.  Arrays whose component type is Boolean come with
predefined operations for and'ing and or'ing, etc.  Of course, you can have
bit arrays whose component type is not Boolean (but that don't come with
predefined and'ing and or'ing -- though you can get that by converting to a
modular type, or to a bit array whose component type is Boolean).

o Read about pragma Pack.

o With a bit array, you don't have to mask and shift -- the compiler will
do that for you:

   O : Bit_Array_32;
begin
   O (19) := True;

o Read about representation clauses for records.  (Rep clauses for records
are analogous to bit fields in C, but are much more general and powerful.) 
By using a rep clause on a record, the language does all the bit
manipulation automatically.

o Note that you can convert between representations using
Unchecked_Conversion.  So if you have a (non-modular) integer type --for
which and'ing and or'ing are not predefined operations-- then you can
convert it to a modular type or bit array type which does have those
operations.

o If your professor recommended the language C, then he may not realize
that Ada can do any bit manipulation that C can do, but better.  Ada is a
systems programming language like C/C++, but preserves type safety.  For
example, your professor may not realize that if you use a rep clause on a
record, then no explicit bit manipulation by the client is required.

Re: Bit manipulation facilities in Ada

[dewarr]

> Robert T. Sagris wrote in message
> <36573C4D.DA431821@physics.purdue.edu>...
> I'm thinking about taking an Data Security and
> Encryption course.
> The language for programming projects is open to the
> students.
>
> The Professor has already recommended C for its built in
> Bit operators.
> But I would like to try it in Ada, as I've never used in
> a class.
> I could use the practice.
>
> Robbi Sagris


Ada is far better than C for this purpose. In addition to
all the general (and quite correct) propaganda about the
general superiority of Ada, there is one particular feature
that is missing in Ada, namely packed bit arrays. In C you
have to program this your self, as an array of bytes, which
you then do bit manipulation on.

This is less efficient than the Ada code, results in much
more obscure code, and is much more error prone.

Undoubtedly the Professor's recommendation simply comes
from ignorance of this feature of Ada!

Regarding other facilities, Ada and C are pretty much
equivalent in terms of low level facilities. Both give the
choice of using bit operations on integer values, or of
declaring records with bit fields.

But for the applications in question here, the packed array
feature is a very critical one. You will find it far easier
to program these problems in Ada, even if you are less
familiar with Ada than with C (the effort of learning Ada
will easily be repaid!).

Robert Dewar

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Bit manipulation facilities in Ada

[dewarr]

In article
<matthew_heaney-ya023680002111981903250001@news.ni.net>,
  matthew_heaney@acm.org (Matthew Heaney) wrote:


> For example, your professor may not realize that if you
> use a rep clause on a
> record, then no explicit bit manipulation by the client
> is required.

That's a weak point, since C can also do the equivalent of
rep clauses on records, or close to it, with bit field
specifications (indeed for quite a while GNAT translated
all record rep clauses to corresponding C structs with bit
fields).


-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Bit manipulation facilities in Ada

[Simon Wright]

dewarr@my-dejanews.com writes:

> Ada is far better than C for this purpose. In addition to
> all the general (and quite correct) propaganda about the
> general superiority of Ada, there is one particular feature
> that is missing in Ada, namely packed bit arrays. In C you
          ^^^^^^^ 'present', I think?
> have to program this your self, as an array of bytes, which
> you then do bit manipulation on.

Re: Bit manipulation facilities in Ada

[Robert T. Sagris]

I would like to thank everyone who has responded so far.
I think I can safely say, now, that I will be able at least
implement all the projects in Ada.

I would however like to say that Prof. Wagstaff probably was only 
recommending C as the better of the two languages that are taught in
any of classes at Purdue, other being FORTRAN. I would hate to imply
that my future professor didn't know what he was talking about when
he recommended C. ;)

Thanks again

Robbi Sagris

Re: Bit manipulation facilities in Ada

[Marin David Condic]

I'll agree that Ada has as-good-as-or-better features for bit manipulation
than C. The original question, however, was to find a good source for
learning how to do this. The Ada Reference Manual certainly spells out all
the operators and declarations necessary to do bit-twiddling - but not all
conveniently in one section. I'd think that you might find some of this in
a "Ada for Recovering C Programmers" text, but myself, not being a
Recovering C programmer, I've never read any of these texts. Try looking at
www.adahome.com in the bibliography - you might locate something there.

MDC

dewarr@my-dejanews.com wrote:

> > Robert T. Sagris wrote in message
> > <36573C4D.DA431821@physics.purdue.edu>...
> <snip>
> > The Professor has already recommended C for its built in
> > Bit operators.
> > But I would like to try it in Ada, as I've never used in
> > a class.
> > I could use the practice.
> >
> > Robbi Sagris
>
> Ada is far better than C for this purpose. In addition to
> all the general (and quite correct) propaganda about the
> general superiority of Ada, there is one particular feature
> that is missing in Ada, namely packed bit arrays. In C you
> have to program this your self, as an array of bytes, which
> you then do bit manipulation on.
> <snip>

--
Marin David Condic
===========================================================
    "A government that is big enough to give you all you want is big
    enough to take it all away."

        --  Barry Goldwater
===========================================================

Re: Bit manipulation facilities in Ada

[dennison]

In article <36575D47.43905794@bellsouth.net>,
  The Ludwig Family <ludwigs@bellsouth.net> wrote:
> Look in the index for "modular integers" and look under "arrays", in
> particular one-dimensional boolean arrays.  For both of these categories,
> the operators "and", "or", "xor", and "not" are available.

This point is worth emphasising, as it seems to be suprisingly little-known.
This feature is very important for writing C and OS bindings as well. Create
yourself an enumerated type with suitably descriptive names for each bit. Then
create a packed array of booleans indexed by that type, and suddenly bit field
operations actually become readable.

--
T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Bit manipulation facilities in Ada

[Robert I. Eachus]

In article <36573C4D.DA431821@physics.purdue.edu> "Robert T. Sagris" <robs@physics.purdue.edu> writes:

 > I'm thinking about taking an Data Security and Encryption course.
 > The language for programming projects is open to the students.

 > I was wondering if any one could recommend any books that demonstrate
 > low level bit manipulation in Ada.

   I think that the problem is that bit manipulation is not low-level
in Ada, it is high level, but just as efficient.  For most modern
symmetric key algorithms that use Feistel networks you end up writing
one line of code that looks very much like the original definition:

   Block(1) := F(Block(2) xor Key(N)) xor Count;
   (Chosen to look real but not from any known algorithm. ;-)

  > None of which seem to cover this in any detail.

   Once you know that in Ada, Boolean operations are supported on
Booleans and arrays of Booleans, and in Ada 95 on unsigned integer
types, what more do you need to know.  (Other than in symmetric block
algorithms, you often want to declare the block type as an array of
sub-blocks, and the sub-blocks as unsigned or boolean arrays depending
on the algorithm.

  > The Professor has already recommended C for its built in Bit operators.
  > But I would like to try it in Ada, as I've never used in a class.
  > I could use the practice.

   The standard random number packages in Ada 95 will do fine for
testing algorithms, but if you really need cryptographic security, you
will need to collect your own random bits, and possibly use the
built-in PRNG for whitening.  Whitening is the process of taking
possibly biased (non-pseudo) random data and converting it into fewer,
but unbiased random bits.

   There is one other thing you may need.  In public key encryption,
you often need a way to do arithmetic on very large integer types.
Most Ada compilers supply such a package, as they need it internally,
but you may need to add X to the power Y mod Z as a primitive to get
any reasonable performance.

   The best choice is to use a cryptographic bignum package and create
a (high-level) interface to it.
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Bit manipulation facilities in Ada

[dewarr]

In article <x7vaf1j3bbw.fsf@pogner.demon.co.uk>,
  Simon Wright <simon@pogner.demon.co.uk> wrote:

> there is one particular feature
> that is missing in Ada, namely packed bit arrays. In C
> you
>         ^^^^^^^ 'present', I think?


Yes indeed Simon, thanks for noticing this, I did indeed
mean present. Some evil C witch must have put a spell on
my fingers as I typed this message.

Robert Dewar

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Bit manipulation facilities in Ada

[Ole-Hjalmar Kristensen]

dewarr@my-dejanews.com writes:

> > Robert T. Sagris wrote in message
> > <36573C4D.DA431821@physics.purdue.edu>...
> > I'm thinking about taking an Data Security and
> > Encryption course.
> > The language for programming projects is open to the
> > students.
> >
> > The Professor has already recommended C for its built in
> > Bit operators.
> > But I would like to try it in Ada, as I've never used in
> > a class.
> > I could use the practice.
> >
> > Robbi Sagris
> 
> 
> Ada is far better than C for this purpose. In addition to
> all the general (and quite correct) propaganda about the
> general superiority of Ada, there is one particular feature
> that is missing in Ada, namely packed bit arrays. In C you
> have to program this your self, as an array of bytes, which
> you then do bit manipulation on.
> 

Ever heard of bit fields in C?

> This is less efficient than the Ada code, results in much
> more obscure code, and is much more error prone.
> 
> Undoubtedly the Professor's recommendation simply comes
> from ignorance of this feature of Ada!
> 

Agreed.

> Regarding other facilities, Ada and C are pretty much
> equivalent in terms of low level facilities. Both give the
> choice of using bit operations on integer values, or of
> declaring records with bit fields.
> 
> But for the applications in question here, the packed array
> feature is a very critical one. You will find it far easier
> to program these problems in Ada, even if you are less
> familiar with Ada than with C (the effort of learning Ada
> will easily be repaid!).
> 
> Robert Dewar
> 
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Bit manipulation facilities in Ada

[John McCabe]

Ole-Hjalmar Kristensen <ohk@maestro.clustra.com> wrote:
>dewarr@my-dejanews.com writes:

<..snip..>

>> there is one particular feature
>> that is missing in Ada, namely packed bit arrays. In C you
>> have to program this your self, as an array of bytes, which
>> you then do bit manipulation on.

>Ever heard of bit fields in C?

Of course it is true that you can use bit fields to perform this 
function, but this would be done in a structure like:

  typedef struct
  {
     int bit_0:1;
     int bit_1:1;
     int bit_2:1;
     :
     :
  } BOOLEAN_ARRAY_TYPE;

Compared with Ada's:

  type Bit_Boolean is new Boolean;
  for Bit_Boolean'size use 1;

  type Boolean_Array_Type is array (<some_range>) of Bit_Boolean;
  pragma pack (Boolean_Array);


Handling an object of these types (say examining each bit in turn) would 
be something like:

In C:

  BOOLEAN_ARRAY_TYPE Boolean_Array;

  if (Boolean_Array.Bit_0)
  {
    <do something>
  }

  if (Boolean_Array.Bit_1)
  {
    <do something>
  }

  :
  :
  etc.

In Ada:

  Boolean_Array : Boolean_Array_Type;

  for Bit_Number in <some_range> loop
    if (Boolean_Array (Bit_Number)) then
      <do something>
    end if;
  end loop;

So, the main consideration really (as far as I see it) is if the number 
of bits you need changes, or you need to check each bit in turn many 
times. The Ada version is flexible as it can handle looping around while 
checking each bit and adjusting the size of the array is not going to 
affect this. In C one would have to add another declaration to the struct 
and the code to handle it.

I would guess that in C perhaps you could do something like:

  typedef struct
  {
    int bit:1;
  } SINGLE_BIT;

then declare an object such as:

  SINGLE_BIT Boolean_Array [8];

but I would expect that this would not do what you want as it is highly 
unlikely that the compiler would pack such an array unless it provided a 
specific implementation defined pragma to allow this.

-- 
Best Regards
John McCabe
---------------------------------------------------------------------
Marconi Electronic Systems
Simulation & Training Division
=====================================================================
Not necessarily my company or service providers opinions.
=====================================================================

Re: Bit manipulation facilities in Ada

[P.S. Norby]

dewarr@my-dejanews.com wrote:
> 
> In article <x7vaf1j3bbw.fsf@pogner.demon.co.uk>,
>   Simon Wright <simon@pogner.demon.co.uk> wrote:
> 
> > there is one particular feature
> > that is missing in Ada, namely packed bit arrays. In C
> > you
> >         ^^^^^^^ 'present', I think?
> 
> Yes indeed Simon, thanks for noticing this, I did indeed
> mean present. Some evil C witch must have put a spell on
                     ^^^^^^^^^^^^ 

We will all expect to see this character in the next gala!  ;-)



> my fingers as I typed this message.
> 
> Robert Dewar
> 
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own

-- 
P.S. Norby

"No excuses.  No embarrasment.  No apologies...
 Ada -- the most trusted and powerful programming language
 on earth, or in space." -- S. Tucker Taft
 
\\\    \\\    \\\    \\\    \\\    \\\    \\\    \\\    \\\ 
( :)   ( :)   ( :)   ( :)   ( :)   ( :)   ( :)   ( :)   ( :)
///    ///    ///    ///    ///    ///    ///    ///    /// 
(Speaking only for myself)

Re: Bit manipulation facilities in Ada

[Stephen Leake]

"Robert T. Sagris" <robs@physics.purdue.edu> writes:

> I'm thinking about taking an Data Security and Encryption course.
> The language for programming projects is open to the students.
> 
> I was wondering if any one could recommend any books that demonstrate
> low level bit manipulation in Ada.
> 
> I already have 
> 
>     Ada as a Second Language
>     By: Cohen

If this is the second edition (subtitled "based on Ada 95"), see page
118. He discusses bit-wise operations on modular types. I didn't find
anything on packed Boolean arrays, which is another way to do bit
manipulation. If you don't have the Ada 95 edition, go get it!

I don't have the other books you mentioned.

-- Stephe