J3/05-274
Date: 21-Oct-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 default 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.
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. Code involving
BITS objects with KIND values equal to small integer multiples of
NUMERIC_STORAGE_SIZE may be singled out for more aggressive
optimization.
[end note]
Bits compatible types
---------------------
The category of nonnumeric types is expanded to include bits and
numeric sequence types is expanded to include components of type
default bits. A <> is BITS, LOGICAL, a numeric
type, or a numeric sequence type. The bit size of a an object is
provided by the intrinsic function COMPATIBLE_BITS_KIND. A reference
to this function is an initialization expression which may be used as
a kind value in a declaration statement.
A nonpointer scalar object of type default BITS occupies a single
numeric storage unit. A nonpointer 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.
Two objects with the same bit size occupy the same amount of storage.
Note: A nonpointer 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.
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. [end note]
***Discussion issue: An alternate definition of the bit size for BITS
objects could be based on storage sizes rather than values. With
that definition the 8-bit integers above would be compatible with a
BITS(32) object because 32 bits of storage are used for the
integers. Additional discussion of this alternative is at the end
of this paper.
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 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 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., 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 .and., .or., and .xor. operators are defined for one bits and one
integer operand. The integer operand value is converted to a bits
value of the same bit size and the operation is performed for the two
bits values.
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 converted to a
its 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 cast 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 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
-------------------------------------------------
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 subroutine shall be of type real
or bits. If the argument is of type bits, the result value consists
of a random pattern of KIND(HARVEST) 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.
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.
If WG5 decides to not include RU-008 proposal, and the IALL, IANY,
IPARITY and PARITY functions above are not included in f08, then
changes to PRODUCT, CO_PRODUCT, SUM, CO_SUM, DOT_PRODUCT, and MATMUL
could be included as an alternative. These 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 the 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.
Additional new intrinsic functions:
-----------------------------------
COMPATIBLE_BITS_KIND(X) : Result: default salar 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 numeric or LOGICAL type, the result value is
the number of bits of storage used by the processor to represent
values 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, 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
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
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
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 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 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 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 is value bits are all 0. 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 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 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 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 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 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 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
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 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..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 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.
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
===================================================================
Discussion issue related to the example:
Assume that the processor supports an integer kind with the range -128
through 127, and uses an integer radix of 2, requiring 8 bits to
represent values of of kind byte. Assume also that the implementation
stores these integers in a 32 bit memory word. By the rules above, a
bits object with the same bit size as this integer would also be
stored using 32 bits.
If the bit size of an object is based on values then the value of
cbk_byte will be 8 and the output will be
0F
0F
0F
If the bit size of an object is based on storage size then the value
of cbk_byte will be 32 and the output will be
0000000F
000000FF
000000FF
If the bit size of an object is based on storage size, then the
COMPATIBLE_BITS_SIZE intrinsic is equivalent to the proposed
STORAGE_SIZE intrinsics.
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)