J3/05-274r2
Date: 10-Nov-2005
To: J3
From: Bill Long
Subject: BITS feature J3-047, Specs and Syntax.
References: J3/03-278r1, J3/04-244, J3/05-150r1, J3/05-188
-----------------------------------------------------------------
Note: This paper incorporates the change to the BITS proposal decided
at J3 meeting 173 to make the KIND of a BITS literal constant be
determined by the form of the constant.
Summary:
========
A new data type, BITS, is added. Variables and constants of type BITS
are ordered sequences of bits. They simplify and enhance the use of
Fortran for several 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. A method for declaring objects of type
BITS is provided as well as rules on how such objects interact with
existing Fortran objects. Associated intrinsic procedures are also
provided. The BITS proposal introduces two incompatibilities with the
Fortran 2003 standard. The new type name could conflict with the name
of an existing user defined type, and the new operator, .xor., with a
priority just above that of a user defined operator, could conflict
with an existing user defined operator.
Specification and Syntax:
=========================
Discussion of objects of type BITS requires a concept of the size of
an object in number of bits. The term "bit size" is used to denote the
number of bits in an object. The named constant NUMERIC_STORAGE_SIZE
is defined in the ISO_FORTRAN_ENV intrinsic module.
Declarations and constants
--------------------------
The bits type has values that are contiguous, ordered sequences of
bits. The <> of an object of type bits 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 NUMERIC_STORAGE_SIZE. 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 for a BITS variable, the
default kind value is NUMERIC_STORAGE_SIZE, and the type specified is
default bits.
If the kind parameter is not specified for a BITS literal constant,
the kind value is assumed from the form of the constant. If the
constant is a the kind value is the number of
characters. If the constant is an the kind
value is three times the number of characters. If the constant
is a the kind value is four times the number of
characters.
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.
A trailing is allowed for a BOZ constant. If the
specified has a value greater than the kind assumed from
the number of s or s in the constant, the constant
is padded on the left with enough 0 bits to create a constant of kind
. If the specified has a value smaller than
the kind assumed from the number of s or s in the
constant, bits on the left are removed to create a constant of kind
.
Note: Though the processor is required to provide bit sizes up to four
times NUMERIC_STORAGE_SIZE, it is expected that the actual size limit
is much larger, based on system capacity constraints. Use of BITS
objects with KIND values equal to small integer multiples of
NUMERIC_STORAGE_SIZE should result in more aggressive optimization.
[end note]
Bits compatible types
---------------------
The category of nonnumeric types is expanded to include bits and
numeric sequence types are expanded to include components of type
default bits. A <> is BITS, LOGICAL, a numeric
type, or a numeric sequence type. The bit size of an object is
provided by the intrinsic function COMPATIBLE_BITS_KIND. A reference
to this function is an initialization expression that may be used as a
kind value in a declaration statement.
A nonpointer nonallocatable scalar object of type default BITS
occupies a single numeric storage unit. A nonpointer nonallocatable
scalar object of type BITS with a kind value that is an integer
multiple of the kind value of default bits occupies that multiple of
consecutive numeric storage units. The ordering of these consecutive
numeric storage units is processor dependent. A nonpointer
nonallocatable scalar BITS object with nondefault KIND occupies an
unspecified storage unit as described in item (6) of the list in
16.4.3.1.
Two objects with the same bit size occupy the same amount of storage.
Note: A nonpointer nonallocatable scalar BITS object with a KIND value
that is not an integer multiple of the bit size of a numeric storage
unit may be stored in a memory region larger than the minimum required
to represent the value. This allows for data alignments that may be
needed for efficient execution. Each element of a BITS array has the
same padding in memory as a scalar BITS object of the same
kind. Padding is not allowed for BITS objects with a KIND value that
is an integer multiple of the bit size of a numeric storage unit.
As an example, an integer kind might be provided with a range of -128
through +127, requiring 8 bits to represent values on a system using
an integer radix of 2. The bit size of an such an integer would be
8. The compatible bits kind would be BITS(8). If the implementation
uses 32 bits of storage for this kind of integer (including 24 bits of
pad) then the implementation shall also use 32 bits of storage for a
BITS(8) object. In that case, an array of type BITS(8) and size 10
would occupy 40 bytes of memory.
[end note]
Assignment
----------
A bits intrinsic assignment statement is an intrinsic assignment
statement for which the variable or the expression is of type BITS.
Intrinsic assignment of a bits expression to a bits compatible type
variable of the same bit size moves the bits from the expression value
to the variable without data conversions. Intrinsic assignment of a
bits compatible type 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 a 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 right 32 bits, and 0 in the left 32 bits. Bits assignment
does not depend on which endian the processor's memory system uses.
[end note]
Intrinsic operations
--------------------
The .and., .or., .xor., .eqv., .neqv., 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 one
with the smaller bit size is padded on the left with zero bits before
the operation is performed. The result bit size is that of the larger
operand.
The .and., .or., and .xor. operators are defined for one bits and one
integer operand. The integer operand value is interpreted as a bits
value of the same bit size and the operation is performed for the two
bits values.
The .xor. operator is defined for LOGICAL operands. The result is of
type LOGICAL and has the value .false. if both operand are .false. or
both operands are .true. and has the value .true. otherwise.
The .eq., .ne., .lt., .le., .gt., .ge., ==, /=, <, <=, >, and >=
operators are defined for bits operands. If the operands are of
unequal bit size, the one with the smaller bit size 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.
The .eq., .ne., .lt., .le., .gt., .ge., ==, /=, <, <=, >, and >=
operators are defined for one bits operand and one non-bits operand of
a bit compatible type. The non-bits operand value is interpreted as a
bits value of the same bit size and the operation is performed for the
two bits values.
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 converted to an appropriate type with a type conversion
intrinsic function.
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 w and d have
reasonable processor-dependent values. At least one character shall be
output. For list directed input, hexadecimal constants are used 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.
Integration Note: The final description for the G0 edit descriptor
will need to account for BITS i/o list items.
Procedure actual and dummy arguments and pointers
-------------------------------------------------
BITS pointers may be associated with bits compatible type targets that
have the same bit sizes and compatible rank.
A BITS object is TKR compatible with a bits compatible type object
with the same bit size and the same rank. Thus, BITS dummy arguments
of non-intrinsic procedures may be associated with bits compatible
type actual arguments having the same rank and bit size. BITS actual
arguments to non-intrinsic procedures may be associated with bits
compatible type dummy arguments having the same rank and bit size. A
BITS dummy argument and a bits compatible dummy argument with the same
rank and bit size cannot be used for generic disambiguation.
A generic reference with a BITS actual argument will resolve only to a
specific that has the corresponding argument of type BITS.
A generic reference may resolve to a specific with a BITS dummy
argument if the corresponding actual argument is of bits compatible
type and has the same bit size and rank.
The generic resolution rules for BITS arguments are intended to
preserve the current Fortran philosophy that there is only one
non-intrinsic non-elemental specific to which a generic reference can
resolve.
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.
[end note]
Modification of existing language intrinsics:
---------------------------------------------
Section 13.3 of the standard, describing Bit Models, is modified to
apply to bits quantities. The model parameter is the bit size of
the scalar bits object. A bits object consists of bits in sequence
numbered from right to left from 0 to -1. The specifications for
several intrinsic procedures are modified to allow bits actual
arguments.
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 HARVEST argument of RANDOM_NUMBER shall be of type real or bits.
If the argument is of type bits, the result value consists of a
pattern of KIND(HARVEST) bits, with each bit having a 0.5 probability
of being 1.
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.
New intrinsic procedures from HPF added at the Delft meeting:
-------------------------------------------------------------
The IALL, IANY, IPARITY, and PARITY intrinsics from HPF were moved
from the HPF intrinsics proposal (RU-005, see spec paper 05-185 and
edits paper 05-246r1) to the BITS proposal. They are the same as
described in the HPF 2.0 document except that for IALL, IANY, and
IPARITY, the ARRAY argument may be of type bits as well as type
integer.
IALL is a bitwise analog of the ALL intrinsic, and returns a bitwise
.and. reduction of the elements of the ARRAY argument selected by the
DIM and MASK arguments.
IANY is a bitwise analog of the ANY intrinsic, and returns a bitwise
.or. reduction of the elements of the ARRAY argument selected by the
DIM and MASK arguments.
The PARITY intrinsic has a logical MASK argument and an optional DIM
argument. The result is a .neqv. reduction of the elements of the MASK
argument selected by the DIM argument. Note that this intrinsic is not
related to bits, but is included because the IPARTIY intrinsic is bits
related.
IPARITY is a bitwise analog of the PARITY intrinsic, and returns a
bitwise .xor. reduction of the elements of the ARRAY argument selected
by the DIM and MASK arguments.
Parallel to the extensions added for other reduction intrinsics by the
co-array proposal (UK-001), the functions CO_IALL, CO_IANY, CO_PARITY,
and CO_IPARITY are also added.
Additional new intrinsic functions:
-----------------------------------
COMPATIBLE_BITS_KIND(X) : Result: default scalar integer
X : object of a bits compatible type
The result value is the bit size of a non-pointer scalar object with
the same type and kind as X.
If X is of type bits, the result value is KIND(X).
If X is of type default integer, default real, or default logical the
result value is NUMERIC_STORAGE_SIZE, which is defined in the
ISO_FORTRAN_ENV intrinsic module. IF X is of type double precision or
default complex the result value is 2*NUMERIC_STORAGE_SIZE. If X is of
type complex with the same KIND value as that of double precision the
result value is 4*NUMERIC_STORAGE_SIZE.
If X is of a non-default INTEGER type, the result value is
BIT_SIZE(X).
If X is of a non-default non-integer numeric or LOGICAL type, the
result value is the number of bits of storage used by the processor to
represent scalar objects of that type and kind.
If X is of a numeric sequence type, the result value is the sum of the
bit sizes of the scalar components plus the size of each array
component times the bit size of the corresponding array elements.
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(NUMERIC_STORAGE_SIZE)
[end note]
BITS(A[,KIND]) : Result: bits
A : object of a bits compatible type
KIND : integer initialization expression
The result is a bits value with the same bit pattern as the argument
A, possibly 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 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
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 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 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
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 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
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 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 is greater than the storage size of I in
bits, the result value bits are all 0. SHIFTL is an elemental
function, and it cannot be 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 the bit size of 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 is greater than the storage size of I in
bits, the result value bits are all 0. SHIFTR is an elemental
function, and it cannot be 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 the bit size of 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 is greater than the
storage size of I in bits, the result value bits are all 0 if the
leftmost bit of I is 0, or the result value bits are all 1 if the
leftmost bit of I is 1. SHIFTA is an elemental function, and it cannot
be 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 the bit size of I.
DSHIFTL(I,J,SHIFT) : Result: bits
I : bits or integer
J : same type and kind as I
SHIFT : integer, 0 <= SHIFT <= bit size of 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 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 the bit size of I.
DSHIFTR(I,J,SHIFT) : Result: bits
I : bits or integer
J : same type and kind as I
SHIFT : integer, 0 <= SHIFT <= bit size of 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 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 the bit size of I.
MASKL(I[,KIND]) : Result: bits
I : integer, in range [0..KIND(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
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..KIND(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
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 is 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 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 parameter 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.
Example:
--------
program bits_example
implicit none
integer,parameter :: byte = selected_int_kind(1)
integer(byte) :: i
integer(byte),target :: it
integer,parameter :: cbk_byte = compatible_bits_kind(i)
bits(cbk_byte),pointer :: bp
bits(cbk_byte) :: b
i = z"ff"
it = i
bp => it
b = ishft(ishft(i,4),-4)
print *, b
b = shiftr(shiftl(bp,4),4)
print *, b
b = i
b = shiftr(shiftl(b,4),4)
print *, b
end program bits_example
Execution of this program will produce three lines of output:
0F
0F
0F
History:
========
J3/03-278r1 (initial proposal, meeting 166)
J3/04-244 (updated proposal, meeting 167)
J3/05-150r1 (updated proposal, meeting 171)
J3/05-188 (updated proposal, meeting 172)