F123 Bit Vector Manipulation Package

Next: F150 Direct or Up: CERNLIB Previous: F122 Search Operations

F123 Bit Vector Manipulation Package

Routine ID: F123
Author(s): F. Antonelli	Library: MATHLIB
Submitter: F. Carminati	Submitted: 27.11.1989
Language: Fortran, IBM Assembler	Revised: 16.08.1994

This package contains high performance procedures to operate with sparse arrays using Bit Vectors instead of ordinary Index Vectors to address the elements of an arrays. The routines are, at present, available only on IBM 3090 VF machines.

Structure:

SUBROUTINE and FUNCTION subprograms
User Entry Names:

YLOSB, IYLOSB, YLOXB, IYLOXB,
GTHRB, SCTTB, ANDB, XORB, NOTB, NANDB, NORB, ORB, BINVEC, ZEROB,
ONEB, CNTOB, CNTZB, RANGB, INTGB, RJCTB, SXPYB, VXPYB, SXYB, XPWZB,
DOTB, SCALB, VSETB, COPYB

Usage:

The arguments in the calling sequences below are defined as follows:

NW: ( INTEGER) Number of elements to process. The index i below runs from 1 to NW.
Y,X,V,W: ( REAL) Arrays of length NW at least.
IX,IY: ( INTEGER) Arrays of length NW at least.
S,T: ( REAL) Variables or expressions.
IS,IT: ( INTEGER) Variables or expressions.
BV,BV1,BV2: Arrays of length $(NW-1)/32 +1$
at least, used to contain the bit vectors.
IFOUND: ( INTEGER) Number of elements which satisfy the condition, or set-bit count, for BV.

The expression X(BV) indicates all these elements of the vector X for which the corresponding bit is set in the bit array BV. BV(i) indicates the i-th bit of the array BV, counted across words boundaries. The expression

BV(i)=1

means that the i-th bit of the array BV is set.
Vector to scalar comparison:
Two SUBROUTINE subprograms are provided for REAL and INTEGER comparison. The subprogram YLOSB is for vectors with REAL elements and the subprogram IYLOSB for vectors with INTEGER elements.

CALL YLOSB(NW,Y,S,BV,IFOUND,'EQ')	$Y(i) = S$
CALL YLOSB(NW,Y,S,BV,IFOUND,'NE')	$Y(i) ≠S$
CALL YLOSB(NW,Y,S,BV,IFOUND,'GT')	$Y(i) > S$
CALL YLOSB(NW,Y,S,BV,IFOUND,'LT')	$Y(i) < S$
CALL YLOSB(NW,Y,S,BV,IFOUND,'GE')	$Y(i) ≥S$
CALL YLOSB(NW,Y,S,BV,IFOUND,'LE')	$Y(i) ≤S$
CALL IYLOSB(NW,Y,S,BV,IFOUND,'EQ')	$IY(i) = IS$
CALL IYLOSB(NW,Y,S,BV,IFOUND,'NE')	$IY(i) ≠IS$
CALL IYLOSB(NW,IY,IS,BV,IFOUND,'GT')	$IY(i) > IS$
CALL IYLOSB(NW,IY,IS,BV,IFOUND,'LT')	$IY(i) < IS$
CALL IYLOSB(NW,IY,IS,BV,IFOUND,'GE')	$IY(i) ≥IS$
CALL IYLOSB(NW,IY,IS,BV,IFOUND,'LE')	$IY(i) ≤IS$

Vector to vector comparison:
Two SUBROUTINE subprograms are provided for REAL and INTEGER comparison. The subprogram YLOXB is for vectors with REAL elements and the subprogram IYLOXB for vectors with INTEGER elements.

CALL YLOXB(NW,Y,X,BV,IFOUND,'EQ')	$Y(i) = X(i)$
CALL YLOXB(NW,Y,X,BV,IFOUND,'NE')	$Y(i) ≠X(i)$
CALL YLOXB(NW,Y,X,BV,IFOUND,'GT')	$Y(i) > X(i)$
CALL YLOXB(NW,Y,X,BV,IFOUND,'LT')	$Y(i) < X(i)$
CALL YLOXB(NW,Y,X,BV,IFOUND,'GE')	$Y(i) ≥X(i)$
CALL YLOXB(NW,Y,X,BV,IFOUND,'LE')	$Y(i) ≤X(i)$
CALL IYLOXB(NW,Y,X,BV,IFOUND,'EQ')	$IY(i) = IX(i)$
CALL IYLOXB(NW,Y,X,BV,IFOUND,'NE')	$IY(i) ≠IX(i)$
CALL IYLOXB(NW,IY,IX,BV,IFOUND,'GT')	$IY(i) > IX(i)$
CALL IYLOXB(NW,IY,IX,BV,IFOUND,'LT')	$IY(i) < IX(i)$
CALL IYLOXB(NW,IY,IX,BV,IFOUND,'GE')	$IY(i) ≥IX(i)$
CALL IYLOXB(NW,IY,IX,BV,IFOUND,'LE')	$IY(i) ≤IX(i)$

Scatter/gather operations:

    CALL GTHRB(NW,X,BV,Y)       Y=X(BV)
    CALL SCTTB(NW,Y,BV,X)       Y(BV)=X

Elements are gathered or scattered from vector X into vector Y according to the bit mask contained in BV. Only words for which the corresponding bit is set are moved.
Logical operations:

Miscellaneous operations:

    CALL BINVEC(NW,BV,IVEC)

is equivalent to

    DO J = 1,NW
       IF bit J of BV is set THEN
          IVEC(IFOUND)=J
       ENDIF
    ENDDO

CALL ZEROB(NW,BV) $BV(i)=0$

CALL ONEB (NW,BV) $BV(i)=1$

CALL CNTOB(NW,BV,IFOUND) $IFOUND=$ Number of set bits
CALL CNTZB(NW,BV,IFOUND) $IFOUND=$ Number of clear bits
CALL RANGB(NW,Y,S,T,BV,IFOUND) $BV(i)=1$ if $S ≤Y(i) ≤T$

CALL INTGB(NW,Y,V,W,BV,IFOUND) $BV(i)=1$ if $V(i) ≤Y(i) ≤W(i)$

    CALL RJCTB(RAN,X,FREJ,Y,BV,NW,NWOUT,ISWTCH)

RAN: Array of random numbers uniformly distributed between zero and the maximum of the rejection function.
X: Array of points where the rejection function is computed.
FREJ: Array of values of the rejection function.
Y: Array of accepted values of X.
BV: Bit vectors of length $(NW-1)/32+1$ at least.
NW: Initial number of values to extract.
NWOUT: Current number of values left to extract.
ISWTCH: Switch to be set to 1 for the first call.

Linear algebra operations:
Let H be an

NW xNC

matrix. The FUNCTION subrogram DOTB is of type REAL.

CALL SXPYB(NW,BV,Y,X,S)	$Y(BV)=Y(BV)+S*X(BV)$
CALL VXPYB(NW,BV,X,Y,V)	$Y(BV)=Y(BV)+V(BV)*X(BV)$
CALL SXYB(NW,BV,X,Y,S)	$Y(BV)=Y(BV)V(BV)S$
CALL XYPWZB(NW,BV,S,X,Y,T,W,Z)	$Y(BV)=SX(BV)Y(BV)+TW(BV)Z(BV)$
RES = DOTB(NW,BV,X,Y)	$DOTB=∑ X(BV)*Y(BV)$
CALL SCALB(NW,BV,Y,S)	$Y(BV)=Y(BV)*S$
CALL VSETB(NW,BV,Y,S)	$Y(BV)=S$
CALL COPYB(NW,BV,Y,X)	$Y(BV)=X(BV)$

$•$

F150

Next: F150 Direct or Up: CERNLIB Previous: F122 Search Operations

Janne Saarela
Mon Apr 3 15:06:23 METDST 1995

YLOSB,	IYLOSB,	YLOXB,	IYLOXB,
GTHRB,	SCTTB,	ANDB,	XORB,	NOTB,	NANDB,	NORB,	ORB,	BINVEC,	ZEROB,
ONEB,	CNTOB,	CNTZB,	RANGB,	INTGB,	RJCTB,	SXPYB,	VXPYB,	SXYB,	XPWZB,
DOTB,	SCALB,	VSETB,	COPYB

CALL ZEROB(NW,BV)	$BV(i)=0$
CALL ONEB (NW,BV)	$BV(i)=1$
CALL CNTOB(NW,BV,IFOUND)	$IFOUND=$ Number of set bits
CALL CNTZB(NW,BV,IFOUND)	$IFOUND=$ Number of clear bits
CALL RANGB(NW,Y,S,T,BV,IFOUND)	$BV(i)=1$ if $S ≤Y(i) ≤T$
CALL INTGB(NW,Y,V,W,BV,IFOUND)	$BV(i)=1$ if $V(i) ≤Y(i) ≤W(i)$