J3/05-188
To: J3
From: Bill Long
Subject: BITS feature for f03+.
Date: 30-jul-2005
References: J3/03-278r1, J3/04-244, J3/05-150r1
Note: This paper is a revision of the TYPELESS proposal in 05-150r1,
based on changes made at the WG5 meeting in Delft (J3 meeting 172).
The major changes were to change the name to BITS and make the number
of bits selectable by a compile-time type parameter, rather than
being tied to the sizes of existing intrinsic types.
--------------------------------------------------------------------
1) Number: (J3-047)
2) Title: BITS data type for Fortran
3) Submitted By: J3
4) Status: For consideration
5) Basic Functionality:
Objects declared as type BITS have kind and rank attributes, but are
treated as only a sequence of bits, without the higher abstractions
associated with the traditional Fortran intrinsic types. A method for
declaring objects as BITS is provided as well as rules on how such
objects interact with existing Fortran objects. Associated intrinsic
procedures are also provided.
6) Rationale:
Fortran currently lacks support for variables that represent a
sequence of bits independent of the interpretations imposed by the
traditional numeric, logical, and character data types. Various
features have been added to Fortran to facilitate handling sequences
of bits by overloading the INTEGER data type, and through vendor
extensions. This has lead to limitations in the usefulness of these
features as well as awkward wording in the Fortran standard text.
Adding a new intrinsic type specifier, BITS, would simplify and
enhance the use of Fortran for certain types of non-numeric problems,
such as pattern matching, searching and sorting, and low level bit
manipulation, as well as allowing for more clarity in the text of the
standard. A BITS intrinsic data type also provides a way to
standardize several common Fortran language extensions, and provides a
rational method for dealing with BOZ constants.
7) Estimated Impact:
Several edits to the standard would be required to incorporate this
feature, though each would be straightforward. Implementation of the
feature in compilers should be technically straightforward. It is
rated as a 7 on the JKR scale.
8) Detailed Specification:
Discussion of objects of type BITS requires a concept of the size of
an object in number of bits. The term bit_size in lower case letters
is used in this proposal to denote the number of bits in an
object. The name BIT_SIZE in upper case letters refers to the existing
intrinsic function, as extended in this proposal.
Declarations and constants
--------------------------
The bits type has values that are contiguous, ordered sequences of
bits. The bit_size is the number of bits in the sequence, which shall
be greater than or equal to zero. A processor shall provide bits kinds
with bit_size values of zero through at least four times the size of
the default INTEGER storage size in bits (4*BIT_SIZE(0)). Each
provided bit_size is characterized by a value for a type parameter
called the KIND type parameter. The value of the KIND parameter is the
bit_size of the object. The KIND type parameter is of type default
integer. The KIND type parameter value of a bits object is returned by
the intrinsic inquiry function KIND.
The type specifier for the bits type uses the keyword BITS.
If the kind parameter is not specified, the default kind value is
BIT_SIZE(0), and the type specified is default bits.
Any bits value may be represented as a , or a
concatenation of multiple s.
(The f03 description of BOZ constants, [37:1-18], would be moved
to the bits subsection of 4.4, and constraint C410 deleted.)
The digits of octal constants represent triples of bits, and the
digits of hexadecimal constants represent quartets of bits, according
to their numerical representations as binary integers, with leading
zero bits where needed. (Alternatively, a table of the translations
could be provided in the standard.)
A trailing is allowed for a BOZ constant.
A nonpointer scalar object of type default bits occupies a single
numeric storage unit. The category of numeric sequence types is
expanded to include default bits.
Note: Though the processor is required to provide bit sizes up to four
times the size of a numeric storage unit, it is expected that the
actual size limit is much larger, based on system capacity
constraints. Code involving bit sizes corresponding to small integer
multiples of the size of a numeric storage unit may be singled out for
more aggressive optimization.
Assignment
----------
A bits intrinsic assignment statement is an intrinsic assignment
statement for which the variable or the expression is if type BITS.
Intrinsic assignment of a bits expression to a bits, integer,
real, or complex variable of the same bit_size moves the bits from the
expression value to the variable without data conversions. Intrinsic
assignment of a bits, integer, real, or complex expression to a
bits variable of the same bit_size transfers the bits from the
expression value to the variable without data conversion. If the
expression value has a smaller bit_size than that of the variable, the
expression value is padded with bits of zero on the left so that the
bit_sizes are equal. If the expression value has a larger bit_size
than that of the variable, the expression value is truncated on the
left to the bit_size of the variable.
The bits intrinsic assignment rules apply to data initializations
in declaration statements, DATA statements, and default component
initializations.
Note: Bits assignment is not always the same as the result of the
TRANSFER intrinsic. The TRANSFER operation is based on the memory
image of the data, while bits assignment is based on the data
values. For example, if S is an 32-bit integer array of size 8, and R
is a 64-bit bits array of size 8, R = TRANSFER(S,R) will result in
the values of S packed into the first 4 elements of R. The way in
which this packing is done will be different on little endian and big
endian machines. The bits assignment, R = S, will result in all 8
elements of R being defined, where R(i) contains the bits from S(i) in
the lower 32 bits, and 0 in the upper 32 bits. Bits assignment
does not depend on which endian the processor's memory system uses.
Intrinsic operations
--------------------
The .and., .or., .xor., and .not. operators are defined for bits
operands. .xor. is the exclusive or operation. The computations are
bitwise operations. The result of the expression evaluation is
bits. If the operands are of unequal bit_size, the smaller is
padded on the left with zero bits before the operation is performed.
Optional feature: Extend the use of .and., .or., .xor., and .not. to
integer, real, and complex operands, with an implied
cast of those operands to bits before the
operation is performed.
The .eq., .ne., .lt., .le., .gt., .ge., ==, /=, <, <=, >, and >=
operators are defined for bits operands. If the operands are of
unequal bit_size, the smaller is padded on the left with zero bits
before the operation is performed. Operands A and B are equal if their
corresponding bits are the same, and are unequal otherwise. If A and B
are unequal, and the leftmost unequal corresponding bit of A is 1 and
of B is 0, then A > B, otherwise A < B.
Optional feature: Extend the above relational operators to the case
where one operand is bits and the other is real,
integer, or complex, with an implied cast of the
operand that is not bits to bits before the
operation is performed.
The // intrinsic operator is defined for bits operands. The result is
a bits object with a bit_size equal to the sum of the bit sizes of the
operands, and with a value of the concatenation of the bits in the
left and right operands.
The numeric intrinsic operations are not defined for bits
objects. To use a bits object as an operand of a numeric intrinsic
operator, it must first be cast to an appropriate type with a type
conversion intrinsic function. The type conversion functions are
described later.
Formatted Input and Output
--------------------------
The format specifiers for bits objects are I, B, O, and Z. For
output, if the .d part of the Bw.d, Ow.d, or Zw.d specifier is
omitted, the value assumed for d is >= 1 and large enough to represent
the bits in the io list item excluding leading 0 bits. For the I
format specifier, the object value is interpreted as an unsigned base
10 integer. For input using the B, O, and Z edit descriptors, the
character string shall consist of binary, octal, or hexadecimal digits
in the respective input field. For input using the I format, the input
character string shall consist of an unsigned decimal integer.
For list directed output, the format used is Zw.d where d is (bit_size
of the io list item + 3)/4 and w = d+1. For list directed input,
hexadecimal constants are valid for bits io list items. The number
of bits required to represent the input value shall be less than or
equal to the bit_size of the corresponding io list item. If it is
less, the io list item is padded with zero bits on the left.
Procedure actual and dummy arguments and pointers
-------------------------------------------------
Two objects have "compatible kind parameters" if they have the same
bit_sizes.
BITS pointers may be associated with targets that have compatible kind
parameters.
BITS dummy arguments of non-intrinsic procedures are compatible with
actual arguments having compatible kind parameters.
Note: This feature can significantly simplify the interfaces for
procedures that move data in memory, but do not perform any operations
on the data. Classic examples include dusty-deck codes containing MOVE
or COPY routines, as well as some MPI library routines written in C with
dummy arguments of type void.
Modification of existing language intrinsics:
---------------------------------------------
Section 13.3 of the standard, describing Bit Models, is modified to
apply to bits quantities. The specifications for several intrinsic
procedures are modified to allow bits actual arguments. Several of
these have result values described in terms of the bit model in
section 13.3. Minimal changes would be needed in those cases.
The I argument of ACHAR shall be of type integer or bits. If I is
bits, it is interpreted as an unsigned integer value.
The I argument of BIT_SIZE shall be of type integer or bits. If I
is bits, the result value is KIND(I).
The I argument of CHAR shall be of type integer or bits. If I is
bits, it is interpreted as an unsigned integer value.
The X and Y arguments of CMPLX shall be of type integer, real,
complex, or bits. Note that bits is a generalization and
replacement for the current "or a ".
The A arguments of DBLE shall be of type integer, real, complex, or
bits. Note that bits is a generalization and replacement for
the current "or a ".
The X argument of HUGE shall be of type integer, real, or bits.
If X is bits, the result value has all bits set to 1.
The I and J arguments of IAND, IEOR, and IOR shall be of type integer
or bits, and have the same bit_size. The result is of type integer
if one of the arguments is integer, and bits otherwise.
The I argument of BTEST, IBCLR, IBITS, and IBSET shall be of type
integer or bits.
The A argument of INT shall be of type integer, real, complex, or
bits. Note that bits is a generalization and replacement for
the current "or a ". If A is bits, the
result value is that of an intrinsic assignment of A to an integer
variable of the specified KIND.
The I arguments of ISHFT and ISHFTC shall be of type integer or
bits.
The X argument of KIND is specified as "any intrinsic type", so no
change is needed.
The A* arguments of MAX and MIN shall be of type integer, real,
character, or bits. If the arguments are bits, the meaning of
"largest" in the result value description is as specified by the >
operator for bits values.
The ARRAY arguments of MAXLOC, MINLOC, MAXVAL, MINVAL, CO_MAXLOC,
CO_MINLOC, CO_MAXVAL, and CO_MINVAL shall be of type integer, real,
character, or bits.
The FROM and TO arguments of MVBITS shall be of type integer or
bits.
The I argument of NOT shall be of type integer or bits.
The A argument of REAL shall be of type integer, real, complex, or
bits. Note that bits is a generalization and replacement for
the current "or a ". If A is bits, the
result value is that of an intrinsic assignment of A to a real
variable of the specified KIND.
Possible modifications to other intrinsic procedures:
-----------------------------------------------------
Several other intrinsic functions could be reasonably extended to
allow bits arguments.
Changes to PRODUCT, CO_PRODUCT, SUM, CO_SUM, DOT_PRODUCT, and MATMUL
should be included or omitted from the proposal as a group.
PRODUCT and CO_PRODUCT: The result value is an .and. reduction of the
specified elements of the bits ARRAY argument.
SUM and CO_SUM: The result value is an .xor. reduction of the
specified elements of the bits ARRAY argument.
DOT_PRODUCT: The result value is SUM(VECTOR_A .and. VECTOR_B) for
bits arguments VECTOR_A and VECTOR_B.
MATMUL: The value of each result element is SUM(MATRIX_A( )
.and. MATRIX_B( )) where the argument subscripts are as specified for
the other argument types, and MATRIX_A and MATRIX_B are bits. Note
that this is not the same as bit-matrix-multiply operation. That
could be added as a separate pair of intrinsics (for the .or. and
.xor. variants), but it is not currently part of the bits
proposal.
The RANDOM_NUMBER subroutine could allow a bits HARVEST argument
which would return with a value consisting of a random pattern of
bits.
New intrinsic functions:
------------------------
SELECTED_BITS_KIND(Z) : Result: default scalar integer
Z : scalar integer
Z is a number of bits. The result value is Z if the processor supports
bits objects of Z bits, and -1 otherwise.
Note: The default bits kind is SELECTED_BITS_KIND(BIT_SIZE(0))
BITS(A[,KIND]) : Result: bits
A : integer, real, complex, or bits
KIND : integer initialization expression
The result is a bits value with the same bit pattern as the
argument A, possible padded with zero bits on the left, or truncated
on the left if the bit_sizes of A and the result are not equal.
BITS is an elemental function, and it cannot be passed as an
actual argument. If KIND is present, the kind type parameter of the
result is that specified by the value of KIND; otherwise the kind type
parameter of the result is that of default bits.
POPCNT(I[,KIND]) : Result: integer, in range [0..BIT_SIZE(I)]
I : bits or integer
KIND : integer initialization expression
The result is the number of bits set to 1 in the argument. This
function is adopted from HPF and extended to allow bits
arguments. POPCNT is an elemental function, and it cannot be passed as
an actual argument. If KIND is present, the kind type parameter of the
result is that specified by the value of KIND; otherwise the kind type
parameter of the result is that of default integer.
POPPAR(I[,KIND]) : Result: integer, 0 or 1
I : bits or integer
KIND : integer initialization expression
The result is 0 if the number of bits set to 1 in the argument is
even, and 1 if the number of bits set to 1 in the argument is odd.
This function is adopted from HPF and extended to allow bits
arguments. POPPAR is an elemental function, and it cannot be passed as
an actual argument. If KIND is present, the kind type parameter of the
result is that specified by the value of KIND; otherwise the kind type
parameter of the result is that of default integer.
LEADZ(I[,KIND]) : Result: integer, in range [0..BIT_SIZE(I)]
I : bits or integer
KIND : integer initialization expression
The result is the number of leading 0 bits in the argument. This
function is adopted from HPF and extended to allow bits
arguments. LEADZ is an elemental function, and it cannot be passed as
an actual argument. If KIND is present, the kind type parameter of the
result is that specified by the value of KIND; otherwise the kind type
parameter of the result is that of default integer.
TRAILZ(I[,KIND]) : Result: integer, in range [0..BIT_SIZE(I)]
I : bits or integer
KIND : integer initialization expression
The result is the number of trailing 0 bits in the argument. TRAILZ
is an elemental function, and it cannot be passed as an actual
argument. If KIND is present, the kind type parameter of the
result is that specified by the value of KIND; otherwise the kind type
parameter of the result is that of default integer.
SHIFTL(I,SHIFT) : Result: bits
I : bits or integer
SHIFT : integer, >= 0
The result is the value I shifted left by SHIFT bits, with 0 bits
filled on the right. If SHIFT > BIT_SIZE(I), the result is
zero. SHIFTL is an elemental function, and it cannot be passed as an
actual argument. If I is bits, the result KIND is the same as that
of I. If I is integer, the result KIND is BIT_SIZE(I).
SHIFTR(I,SHIFT) : Result: bits
I : bits or integer
SHIFT : integer, >= 0
The result is the value I shifted right by SHIFT bits, with 0 bits
filled on the left. If SHIFT > BIT_SIZE(I), the result is
zero. SHIFTR is an elemental function, and it cannot be passed as an
actual argument. If I is bits, the result KIND is the same as that
of I. If I is integer, the result KIND is If I is integer, the result KIND is BIT_SIZE(I).
SHIFTA(I,SHIFT) : Result: bits
I : bits or integer
SHIFT : integer, >= 0
The result is the value I shifted right by SHIFT bits, with copies of
the leftmost bit filled on the left. If SHIFT > BIT_SIZE(I), the
result is zero if the leftmost bit of I is 0, or HUGE(BITS(I)) if
the leftmost bit of I is 1. SHIFTA is an elemental function, and it
cannot be passed as an actual argument. If I is bits, the result
KIND is the same as that of I. If I is integer, the result KIND is
If I is integer, the result KIND is BIT_SIZE(I).
DSHIFTL(I,J,SHIFT) : Result: bits
I : bits or integer
J : same type and kind as I
SHIFT : integer, 0 <= SHIFT <= BIT_SIZE(I)
The result is the value of I shifted left by SHIFT bits, with the
rightmost SHIFT bits of I replaced by the leftmost SHIFT bits of
J. This is equivalent to concatenating I and J, shifting the combined
value left SHIFT bits, and keeping the left half. If I and J are the
same, the result is the same as a left circular shift. DSHIFTL is an
elemental function, and it cannot be passed as an actual argument. If
I is bits, the result KIND is the same as that of I. If I is integer,
the result KIND is If I is integer, the result KIND is BIT_SIZE(I).
DSHIFTR(I,J,SHIFT) : Result: bits
I : bits or integer
J : same type and kind as I
SHIFT : integer, 0 <= SHIFT <= BIT_SIZE(I)
The result is the value of J shifted right by SHIFT bits, and the
leftmost SHIFT bits of J replaced by the rightmost SHIFT bits of
I. This is equivalent to concatenating I and J, shifting the combined
value right SHIFT bits, and keeping the right half. If I and J are
the same, the result is the same as a right circular shift. DSHIFTR is
an elemental function, and it cannot be passed as an actual
argument. If I is bits, the result KIND is the same as that of I. If
I is integer, the result KIND is If I is integer, the result KIND is
BIT_SIZE(I).
MASKL(I[,KIND]) : Result: bits
I : integer, in range [0..BIT_SIZE(result)]
KIND : integer initialization expression
The result is a bits value with the leftmost I bits set to 1 and
the remaining bits set to 0. The value of I shall be >= 0 and <= the
bit_size of the result. MASKL is an elemental function, and it cannot
be passed as an actual argument. If KIND is present, the kind type
parameter of the result is that specified by the value of KIND;
otherwise the kind type parameter of the result is that of default
bits.
MASKR(I[,KIND] ) : Result: bits
I : integer, in range [0..BIT_SIZE(result)]
KIND : integer initialization expression
The result is a bits value with the rightmost I bits set to 1 and
the remaining bits set to 0. The value of I shall be >= 0 and <= the
bit_size of the result. MASKL is an elemental function, and it cannot
be passed as an actual argument. If KIND is present, the kind type
parameter of the result is that specified by the value of KIND;
otherwise the kind type parameter of the result is that of default
bits.
MERGE_BITS(I,J,MASK) : Result: bits
I : bits
J : bits, same kind as I
MASK : bits, same kind as I
The result of a bits value with bits from I if the corresponding
bits in MASK are 1 and the bits from J if the corresponding bits in
MASK are 0. Equivalent to (I .and. MASK) .or. (J .and. (.not. MASK))
MERGE_BITS is an elemental function, and it cannot be passed as an
actual argument. The kind type parameter of the result is the same as
the kind type parameter of I.
Interoperation with C:
----------------------
Bits objects interoperate with C objects of the same bit_size,
including C unsigned integer objects. If a bits object is the
actual argument corresponding to an unsigned integer dummy argument of
a C function, or the unsigned integer result of a C function is
assigned to a bits variable, the I format can be used to output
the correct form of the C value.
9) History:
J3/03-278r1 (initial proposal, meeting 166)
J3/04-244 (updated proposal, meeting 167, spreadsheet version at 169)
J3/05-150r1 (updated proposal, meeting 171, version in spreadsheet 05-145r3)