Why We Need Unsigned Integers in Ada AI-00600/00 1
88-11-08 ST RE
!standard 03.05.04 (00) 88-11-08 AI-00600/00
!class study 88-11-08
!status received 88-11-08
!topic Why We Need Unsigned Integers in Ada
!summary 88-11-08
!question 88-11-08
!recommendation 88-11-08
!discussion 88-11-08
!appendix 88-09-28
*****************************************************************************
!section 03.05.04 (00) Ivar Walseth 88-08-19 83-01020
!version 1983
!topic Why We Need Unsigned Integers in Ada
*
Sivilingenior Kjell G. Knutsen, A.S.
P.O. Box 95
N-4520 SOR-AUDNEDAL
Norway
19th August 1988
Dave Emery
MITRE
MS A156
Bedford, MA 01730
Why We Need Unsigned Integers in Ada
During the last year I've managed a project where we are implementing
communication protocols in Ada (protocols specified in the CCITT
recommendations X.213, X.214, X.215, X.224, X.225, X.409, X.410,
X.411, X.420).
In the communictions world they operate with octets. Each octet
contains 8 bits, and all bit combinations should be available. For
this purpose it is of course possible to define the type:
type octet is range 0..255;
for octet'size use 8; -- optionally
So far so good. The need for a standardized unsigned integer facility
in Ada arises when we are using this octet type for generating
Why We Need Unsigned Integers in Ada AI-00600/00 2
88-11-08 ST RE
checksums (according to X.224, Appendix I). This algorithm requires
modulo 255 arithmetic. For this purpose we have of course implemented
our own slow machine-independent arithmetic operators.
The next problem arises when the protocol specificiations says that bit
number 6 has some special meaning (as defined in table 2 in X.409). To
fetch (and store) this value we use logical operators such as "and"
"or" and shift-functions. These are implemented in a
compiler-dependent way. We could of course have used some tricky
records or multiply and division operators, but we didn't find these
solutions better when it comes to portability and performance.
In addition to the use of octets, other parts of the protocols need
bitwise operations on bigger unsigned integers (ref. tag and length
coding of X.409-units). My wish for Ada 9X is therefore either the 3
types unsigned_8, unsigned_16 and unsigned_32, where the number
specifies the number of bits of the variable, or a more general type
unsigned from which my own types might be created. In the latter case
Ada should guarantee at least 32 bits are available in the type.
For the chosen type I'm hoping for the following functions and
operators:
- arithmetic without overflow (appropriate modulo arithmetic)
- bitwise logical operators : and, or, xor, not
- shift-functions without bit rotation (optionally separate
functions with the more rare shift-variants)
- operators for comparisons
- procedures for fetching and storing single bits
- conversion between unsigned and "normal" integer types
The various HW-manufacturers like to number the bits of a byte
differently. In the CCITT world the octet has 8 bits numbered from 1
to 8 where the leftmost bit is MSB and has the number 8. I suggest
the same numbering in Ada.
Best Regards,
per Siv.ing. Kjell G Knutsen A/S
/signed/
Ivar Walseth
*****************************************************************************
!section 03.05.04 (07) 88-09-28 83-01021
!version 1983
!topic Unsigned Arithmetic
!reference AI-0597, 83-00974
Bryce lists the following goals for unsigned numbers in Ada: (my summary)
1. Non-negative integer range that exploits available hardware
(and that supports full range address arithmetic)
Why We Need Unsigned Integers in Ada AI-00600/00 3
88-11-08 ST RE
2. Numeric literals in arbitrary bases, to the full range of
the unsigned type.
3. Provide efficient support for modular arithmetic.
4. Provide straightforward and efficient logical operators
(including shifts, rotates and masks) on bits of unsigned types.
I fully support the first three goals, but I cannot support the
fourth. Unsigned integers are integers, and there is no arithmatic
definition of shifts, rotates and masks on integers (signed or
unsigned). On the other hand, I think it is probably necessary to
support conversion between integers (unsigned and signed) and some
representation of bit arrays on which shifts, rotates and masks can be
supported. (this conversion should be more than Unchecked_Conversion,
because there is no guarantee that U.C. does what you want.) I guess
there needs to be a function that converts between integer types and
appropriately sized bitmaps, something like:
type bitmap is array (positive range <>) of boolean;
pragma pack (bitmap); -- NOTE: this should work (i.e
-- bitmap(1..32)'size should be 32)
function to_bitmap (i : some_integer_type)
return bitmap; -- raises constraint_error if i'size >
-- bitmap'size. does something TBD
-- (maybe zero fill) if i'size < bitmap'size
function to_integer (bitmap_32)
return some_integer_type; -- can raise constraint_error if
-- conversion would result in a
-- value out of the range of
-- some_integer
-- define appropriate shift, rotate and mask operations on
-- the bitmap type
There is no reason to restrict this conversion to unsigned integers.
I think I like Bryce's distinction between UNSIGNED_INTEGER and
CARDINAL_INTEGER. My feeling is that these should be added to
Standard, and that implementations should provide types like
UNSIGNED_32 and CARDINAL_32, with efficient implementations of
appropriate operations, in package SYSTEM. Such types are clearly
system-dependent.
I guess the goals I'd set for unsigneds include the first 3 goals
provided by Bryce, plus a fourth goal:
4. (emery's goal) Types derived from unsigned types
behave correctly and reasonably.
Here's a place where this would be important: Steve Litvintchouk has
been looking at the Joint Frequency Hopping Specification. It has
lots of bit-packed fields, like X is a 3 bit integer range 0..7. So
I'd like to be able to do the following:
type X is new unsigned_integer range 0..7;
for X'size use 3;
and get all appropriate operations, including (in this case) modular
arithmetic.
Why We Need Unsigned Integers in Ada AI-00600/00 4
88-11-08 ST RE
dave emery
emery@mitre-bedford.arpa
*