SUBROUTINE P7(A,L,NZ,START,LENGTH,NN,ERR) c ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Benchmark #7 -- Bit Twiddle c c *** This version assumes that the BIT MATRIX MULTIPLY *** c *** functional unit is not available *** c c Parameters: c Provided by the calling routine: c A = Input bit stream c L = Number of 64 bit words in bit stream A c NZ = Minimum length of zeros before reporting results c c Returned by this routine: c START = Starting position of each stretch of zeros c LENGTH = Length of each stretch of zeros c NN = Number of stretches of zeros found c ERR = Flag indicating whether there is array overflow c cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c c Basic algorithm c c The benchmark has three parts to it: c 1) The calculation of streams B and C c 2) The calculation of streams D and DXORC (to be defined later) c 3) The calculation of stream E and the locating of sequences of c zeros in E c c Each part of this problem has a different algorithm, which c will be described below. c cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c USE LIMITS USE POP_N_LEADZ IMPLICIT INTEGER (A-Z) c C--CVS variable declaration TYPE CVS sequence character( 160 ) string integer stringend END TYPE CVS C--CVS initilaize variables TYPE( CVS ),save :: CVS_INFO = $ CVS("BMARKGRP $Date: 2005/01/10 20:45:00 $ $Revision: 1.2 $" // $ "$RCSfile: p7.f,v $ $Name: rel_5 $", 0) c c c Cc Uncomment the following for machines without the POPCNT intrinsic. Cc Also, uncomment the code for INITPC and POPCNT in the UTIL routine Cc and the call to INITPC in M7. c C COMMON /POPS/POPS(0:65535) c c c Cc Uncomment the following for machines without the LEADZ intrinsic. Cc Also, uncomment the code for INITLZ in the UTIL routine Cc and the call to INITLZ in M7. c C COMMON /LZCNT/LZCNT(0:65535) c c c c Length of the A stream buffer in 64 bit words PARAMETER (MN= B7_MLW) c c Number of buffers to use PARAMETER (NBUF=2) c c Number of contiguous bits to take to form streams B and C; this c code assumes that this is 5 PARAMETER (LENBC=5) c c Number of bits between beginning bits of a LENB-bit or LENC-bit group; c this code assumes that this is 11 PARAMETER (INC=11) c c Maximum number of 64-bit words in streams B, C, D, DXORC, and E PARAMETER (BLEN=(MN*LENBC)/INC) c c Number of bits in a word; this code assumes that this is 64 PARAMETER (WS=64) c c Number of blocks of INC words. PARAMETER (BLOCK = MN/INC) c c Distance between 1st and 2nd positions in DXORC for XORing together PARAMETER (OFF1=37) c c Distance between 1st and 3rd positions in DXORC for XORing together PARAMETER (OFF2=100) c DIMENSION A(INC,BLOCK,NBUF) c c Buffer to hold the B and C streams before packing PARAMETER (LBUF = 8192) DIMENSION BBUF(INC,LBUF), CBUF(INC,LBUF) c c To hold the B stream DIMENSION B(LENBC,BLOCK), BB(-3:LENBC*BLOCK) EQUIVALENCE (B(1,1),BB(1)) c c To hold the C stream DIMENSION C(LENBC,BLOCK), CC(-3:LENBC*BLOCK) EQUIVALENCE (C(1,1),CC(1)) c c To hold the DXORC stream DIMENSION DXORC(-1:LENBC*BLOCK) c c To hold a segment of the full DXORC stream, and of the E stream DIMENSION TDXORC(-1:3) DIMENSION TE(-1:1) c c Arrays to hold the results DIMENSION START(1),LENGTH(1) c c Masks for Part 1 c DIMENSION MASKB1(INC), MASKB2(INC), MASKB3(INC), MASKB4(INC) DATA MASKB1 /Z'F81F03E07C0F81F0', Z'3E07C0F81F03E07C', $ Z'0F81F03E07C0F81F', Z'03E07C0F81F03E07', $ Z'C0F81F03E07C0F81', Z'F03E07C0F81F03E0', $ Z'7C0F81F03E07C0F8', Z'1F03E07C0F81F03E', $ Z'07C0F81F03E07C0F', Z'81F03E07C0F81F03', $ Z'E07C0F81F03E07C0'/ DATA MASKB2 /Z'FFC003FF000FFC00', Z'3FF000FFC003FF00', $ Z'0FFC003FF000FFC0', Z'03FF000FFC003FC0', $ Z'FE001FF8007FE001', Z'FF8007FE001FF800', $ Z'7FE001FF8007FE00', Z'1FF8007FE001FF80', $ Z'07FE001FF8007FC0', Z'FC003FF000FFC003', $ Z'FF000FFC003FF000'/ DATA MASKB3 /Z'FFFFF000000FFC00', Z'3FFFFC000003FF00', $ Z'0FFFFF000000FFC0', Z'03FFFFC000003FC0', $ Z'FFFF8000007FF000', Z'FFFFE000001FF800', $ Z'7FFFF8000007FE00', Z'1FFFFE000001FF80', $ Z'07FFFF8000007FC0', Z'FFFF000000FFF000', $ Z'FFFFC000003FF000'/ DATA MASKB4 /Z'FFFFFFFC00000000', Z'3FFFFFFF00000000', $ Z'0FFFFFFFC0000000', Z'03FFFFFFC0000000', $ Z'FFFFFFF000000000', Z'FFFFFFF800000000', $ Z'7FFFFFFE00000000', Z'1FFFFFFF80000000', $ Z'07FFFFFFC0000000', Z'FFFFFFF000000000', $ Z'FFFFFFF000000000'/ c DIMENSION MASKC1(INC), MASKC2(INC), MASKC3(INC), MASKC4(INC) c DATA MASKC1 /Z'07C0F81F03E07C0F', Z'81F03E07C0F81F03', $ Z'E07C0F81F03E07C0', Z'F81F03E07C0F81F0', $ Z'3E07C0F81F03E07C', Z'0F81F03E07C0F81F', $ Z'03E07C0F81F03E07', Z'C0F81F03E07C0F81', $ Z'F03E07C0F81F03E0', Z'7C0F81F03E07C0F8', $ Z'1F03E07C0F81F03E'/ c DATA MASKC2 /Z'07FE001FF8007FC0', Z'FC003FF000FFC003', $ Z'FF000FFC003FF000', Z'FFC003FF000FFC00', $ Z'3FF000FFC003FF00', Z'0FFC003FF000FFC0', $ Z'03FF000FFC003FC0', Z'FE001FF8007FE001', $ Z'FF8007FE001FF800', Z'7FE001FF8007FE00', $ Z'1FF8007FE001FF80'/ c DATA MASKC3 /Z'07FFFF8000007FC0', Z'FFFF000000FFF000', $ Z'FFFFC000003FF000', Z'FFFFF000000FFC00', $ Z'3FFFFC000003FF00', Z'0FFFFF000000FFC0', $ Z'03FFFFC000003FC0', Z'FFFF8000007FF000', $ Z'FFFFE000001FF800', Z'7FFFF8000007FE00', $ Z'1FFFFE000001FF80'/ c DATA MASKC4 /Z'07FFFFFFC0000000', Z'FFFFFFF000000000', $ Z'FFFFFFF000000000', Z'FFFFFFFC00000000', $ Z'3FFFFFFF00000000', Z'0FFFFFFFC0000000', $ Z'03FFFFFFC0000000', Z'FFFFFFF000000000', $ Z'FFFFFFF800000000', Z'7FFFFFFE00000000', $ Z'1FFFFFFF80000000'/ c DIMENSION SRB(INC), SRC(INC), SLB(INC), SLC(INC) DATA SRB /0, -28, -56, -20, -54, -18, -46, -10, -38, -8, -36/ DATA SLB /0, 0, 8, 0, 10, 0, 18, 0, 26, 0, 0/ DATA SRC /0, -29, -57, -21, -49, -13, -41, -11, -39, -3, -31/ DATA SLC /5, 0, 7, 0, 15, 0, 23, 0, 25, 0, 0/ c c Variables used to switch between buffers INTEGER FGBUF, BGBUF, TMP c c Generate mask for Part 3 c c Set up mask of valid bits in partial E stream OFF3 = OFF2 - WS IMSK = Z'7FFFFFFFFFFFFFFE' MSKIT = IAND(IMSK, ISHFT(IMSK,OFF1-WS)) MSKIT = IAND(MSKIT, ISHFT(IMSK,OFF3 - WS)) KK = MAX(0, 2*WS - NZ - 2) MSKIT = IAND(MSKIT,ISHFT(IMSK,-KK)) c NN = 0 c c Check number of check bits in this mask IF(POPCNT(MSKIT) .LT. 10) THEN PRINT 5, OFF1, OFF2, NZ, MSKIT, POPCNT(MSKIT) 5 FORMAT(//,'There are too few check bits for the chosen',/, $ ' values of OFF1, OFF2, NZ. Code asumes at least 10',/, $ 'OFF1 = ',I5,/, $ 'OFF2 = ',I5,/, $ 'NZ = ',I5,/, $ 'MSKIT = ',Z16,/, $ 'Density = ',I5) STOP ENDIF c c To prevent problems at the beginning of the streams, set the first few c words preceeding the actual data of both the B and C streams to 0 BB(-3) = 0 BB(-2) = 0 BB(-1) = 0 BB(0) = 0 CC(-3) = 0 CC(-2) = 0 CC(-1) = 0 CC(0) = 0 c c Used to prevent positions past the end of the stream. LEND = L*LENBC*WS/INC - NZ c c ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Basic algorithm for Part 1: c c Notice that for all machines except for ones whose word size is a c multiple of 11, every eleventh word of A has the same bits moved to c the same output locations. Therefore if the inner loop is unrolled c so that each iteration works on 11 words of stream A, the masks c and shift counts will be the same for each iteration, allowing c vectorization and/or parallelization. c c The basic idea is to mask off the bits of a word going to either c B or C, push them together, and then shift them into place c for packing into the output words. c c There are up to seven fields of 5 contiguous bits in each 64-bit c word that need to be compressed to form the output stream. Using a c BIT MATRIX MULTIPLY, one could mask and shift each one of these to c the correct position for output. Without this operation, the most c efficient approach is a divide and conquer approach whereby first c neighboring fields are put together, and then all the bits from the c word are put together near the front of the word. These bits are c then shifted into place for output. The result is that only about c 13 operations (instead of 20) are needed per word for a straight c forward approach. c c This version assumes that the BIT MATRIX MULTIPLY functional unit c is not available. c c Certain masks and shiftcounts are needed for Part 1 to perform its c calculations. The first mask which needs to be generated is the one c marking off the first 5 bits, skipping 6, marking the next 5, etc., c for the B stream. It is contained in array MASKB1. MASKC1 contains c a similar array for the C stream. c c Since we're using the divide and conquer approach, we need masks not c just for the positions of the bits in the 11 original words, but c also for 10-bit groups, for the 20-bit groups, and for the final c up to 30-bit groups. These are contained in arrays MASKB2 through c MASKB4 for the B stream, and in MASKC2 through MASKC4 for the C c stream. These are created in data statements at the beginning of c this subroutine. c cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Generate the stream B by compressing and shifting into position the c 5-bit groups from stream A. This loop assumes that LENBC = 5 and that c the wordsize is 64. c SKIPBC = INC - LENBC c c There may be so little data that we didn't use the secondary storage IF(MN .GE. L) THEN MM = L MMNXT = 0 c Secondary storage was needed ELSE MM = MN MMNXT = MIN(MN, L-MN) ENDIF c c Rewind the secondary storage file IF (L .GT. MN) THEN CALL SKTMP(1,0) CALL SYNTMP(1) ENDIF c c Initialize buffer variables FGBUF = 1 BGBUF = 2 TMP = -1 c IF (L .GT. MN) THEN CALL RDTMP(1,A(1,1,FGBUF),MM) CALL SYNTMP(1) ENDIF c c Set flag to test for array overflow ERR = 0 c c For each buffer's worth of data DO 200 JBUF = 1,L,MN c c Try to overlap reads with the work IF(MMNXT .GT. 0) THEN CALL RDTMP(1,A(1,1,BGBUF),MMNXT) ENDIF c c Process the current data LL = 1 + (MM-1)/INC c c For each buffer length DO 50 K=0,LL-1,LBUF c LLBUF = MIN(LBUF, LL-K) c DO 30 J=1,INC c DO 20 I = 1, LLBUF TB = IAND( A(J,I+K,FGBUF), MASKB1(J)) TC = IAND( A(J,I+K,FGBUF), MASKC1(J)) c c Compress 5-bit groups together TB = IAND(TB + ISHFT(TB, SKIPBC), MASKB2(J)) TC = IAND(TC + ISHFT(TC, SKIPBC), MASKC2(J)) c c Now compress every other resulting 10-bit group together TB = IAND(TB + ISHFT( TB, 2*SKIPBC), MASKB3(J)) TC = IAND(TC + ISHFT( TC, 2*SKIPBC), MASKC3(J)) c BBUF(J,I) = IAND(TB + ISHFT( TB, 4*SKIPBC), MASKB4(J)) CBUF(J,I) = IAND(TC + ISHFT( TC, 4*SKIPBC), MASKC4(J)) c 20 CONTINUE 30 CONTINUE c DO 40 I=1, LLBUF c c c Now pack up the B stream into single words c c c Move word 2 into position TB = ISHFT(BBUF(2,I), SRB(2)) TB = BBUF(1,I) + TB c c Move first part of word 3 into position and output 1st word of output B(1,I+K) = TB + ISHFT(BBUF(3,I), SRB(3)) c c Move last part of word 3 into position TB = ISHFT(BBUF(3,I), SLB(3)) c c Move word 4 into position TB = TB + ISHFT(BBUF(4,I), SRB(4)) c c Move first part of word 5 into position and output 2nd word of output B(2,I+K) = TB + ISHFT(BBUF(5,I), SRB(5)) c c Move last part of word 5 into position TB = ISHFT(BBUF(5,I), SLB(5)) c c Move word 6 into position TB = TB + ISHFT(BBUF(6,I), SRB(6)) c c Move first part of word 7 into position and output 3rd word of output B(3,I+K) = TB + ISHFT(BBUF(7,I), SRB(7)) c c Move last part of word 7 into position TB = ISHFT(BBUF(7,I), SLB(7)) c c Move word 8 into position TB = TB + ISHFT(BBUF(8,I), SRB(8)) c c Move first part of word 9 into position and output 4th word of output B(4,I+K) = TB + ISHFT(BBUF(9,I), SRB(9)) c c Move last part of word 9 into position TB = ISHFT(BBUF(9,I), SLB(9)) c c Move word 10 into position TB = TB + ISHFT(BBUF(10,I), SRB(10)) c c Move word 11 into position and output 5th word B(5,I+K) = TB + ISHFT(BBUF(11,I), SRB(11)) c c c Now pack up the C stream into single words c c c Move word 1 into position TC = ISHFT(CBUF(1,I), SLC(1)) c c Move first part of word 2 into position TC = TC + ISHFT(CBUF(2,I), SRC(2)) c c Move word 3 into position into position and output 1st word of output C(1,I+K) = TC + ISHFT(CBUF(3,I), SRC(3)) c c Move last part of word 3 into position TC = ISHFT(CBUF(3,I), SLC(3)) c c Move word 4 into position TC = TC + ISHFT(CBUF(4,I), SRC(4)) c c Move first part of word 5 into position and output 2nd word of output C(2,I+K) = TC + ISHFT(CBUF(5,I), SRC(5)) c c Move last part of word 5 into position TC = ISHFT(CBUF(5,I), SLC(5)) c c Move word 6 into position TC = TC + ISHFT(CBUF(6,I), SRC(6)) c c Move first part of word 6 into position and output 3rd word of output C(3,I+K) = TC + ISHFT(CBUF(7,I), SRC(7)) c c Move last part of word 7 into position TC = ISHFT(CBUF(7,I), SLC(7)) c c Move word 8 into position TC = TC + ISHFT(CBUF(8,I), SRC(8)) c c Move first part of word 9 into position and output 4th word of output C(4,I+K) = TC + ISHFT(CBUF(9,I), SRC(9)) c c Move last part of word 9 into position TC = ISHFT(CBUF(9,I), SLC(9)) c c Move word 10 into position TC = TC + ISHFT(CBUF(10,I), SRC(10)) c c Move word 11 into position and output 5th word of output C(5,I+K) = TC + ISHFT(CBUF(11,I), SRC(11)) c 40 CONTINUE 50 CONTINUE c c ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Basic algorithm for Part 2: c c Assume DXORC[i] = C[i] XOR D[i]. Because c E[i] = C[i] XOR D[i] XOR C[i+37] XOR D[i+37] XOR C[i+100] XOR D[i+100] c = DXORC[i] XOR DXORC[i+37] XOR DXORC[i+100] , c what we really want to compute in Part 2 is DXORC. c c DXORC[i] = C[i] XOR D[i] c = C[i] XOR ( (C[i] ^ B[i+1]) XOR (~C[i] ^ B[i-1]) ) c = ( C[i] ^ ~B[i+1] ) XOR (~C[i] ^ B[i-1]) c The rest is relatively straightforward. Shifts are used to align c bits within words for logical operations. c c Since, in most cases, it is not necessary to compute every bit of c the E stream (and thus of the DXORC stream) in order to reject the c hypothesis of NZ consecutive zeros in the E stream (though it will c be necessary to compute these bits when confirming this hyphothesis) c only the middle 62 bits of each word of DXORC will be computed at c this point. This results in a savings of four operations out of c the 11 needed to compute DXORC completely. c cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Calculate D and DXORC DO 60 I = -1,LENBC*LL TEMP1 = NOT(ISHFT(BB(I),1)) TEMP2 = IAND(CC(I),TEMP1) TEMP3 = ISHFT(BB(I),-1) DXORC(I) = IEOR(TEMP2,IAND(NOT(CC(I)),TEMP3)) 60 CONTINUE c c ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Basic algorithm for Part 3: c c Notice that for wordsize WS, NZ-WS+1 bits starting at any location c in the word must be zero before there can be NZ zeroes in a row. c Since E does not need to be saved, some work can be eliminated by only c computing a portion of each word, looking for all zeroes in that c portion. The portion should be longer than 10 bits, otherwise too many c false starts will happen, and shorter than N-WS bits, otherwise some c sequences might be missed. Once an all zero portion is found, local c words of DXORC and E are computed in full to determine if there c are N consecutive zeroes. c c This code assumes that NZ, OFF1 and OFF2 are such that at least 10 c bits of check are obtained. It is also assumed that OFF1 and c OFF2 - WS are both greater than 32. If not, it might be better to c take the check bits from the left end of the word of E, rather than c from the right(as is done in the following code). For the given c values of OFF1 and OFF2, NZ must be at least 74, to provide 10 c bits of check. c cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Test for potential zero stretches. The "non-structured" coding is to c increase efficiency when the probability of the IF statement is c very rare. c I=-1 100 CONTINUE DO 110 I = I,LENBC*LL - 2 TEMP1 = ISHFT(DXORC(I+1),OFF1-WS) TEMP2 = ISHFT(DXORC(I+2),OFF3-WS) TEMP3 = IEOR(TEMP2,IEOR(TEMP1,DXORC(I))) IF (IAND(TEMP3,MSKIT) .EQ. 0) GOTO 120 110 CONTINUE GOTO 150 c c If an all-zero portion was found, check to see if NZ zeroes are there. c Calculate the full values of DXORC for 5 words around this position. c 120 CONTINUE DO 130 J=-1,3 TEMP1 = ISHFT(BB(I+J),1) + ISHFT(BB(I+J+1),1-WS) TEMP2 = ISHFT(BB(I+J),-1) + ISHFT(BB(I+J-1), WS-1) TDXORC(J) = IEOR(IAND(CC(I+J),NOT(TEMP1)), $ IAND(NOT(CC(I+J)),TEMP2)) 130 CONTINUE c c Now calculate the full E stream for 3 words around this position c DO 140 J=-1,1 TEMP1 = ISHFT(TDXORC(J+1),OFF1-WS) + ISHFT(TDXORC(J),OFF1) TEMP2 = ISHFT(TDXORC(J+2),OFF3-WS) + ISHFT(TDXORC(J+1),OFF3) TE(J) = IEOR(TEMP2,IEOR(TEMP1,TDXORC(J))) 140 CONTINUE c c If the current word is all zeros, get trailing zero c count of previous word c ZEROES = WS - POPCNT(TE(0)) IF (ZEROES .EQ. WS) THEN ZEROES = WS - (1 + POPCNT(IEOR(TE(-1),-TE(-1)))) IF (ZEROES .EQ. WS) THEN ZEROES = 2*WS ELSE ZEROES = WS + ZEROES ENDIF c c Else get trailing zeros of current word c ELSE ZEROES = WS - (1 + POPCNT(IEOR(TE(0), -TE(0)))) ENDIF c c Now add in the leading zeros of the following word and get start c position STRT = ((JBUF-1)*LENBC/INC + I)*WS - ZEROES ZEROES = ZEROES + LEADZ(TE(1)) c c Store start position and length; will also look for overlapped c regions of zeros and clean up the results c IF (ZEROES .GE. NZ) THEN IF(NN .GT. 0) THEN JJ = START(NN) + LENGTH(NN) ELSE JJ = -1 ENDIF c c Check for overlapped regions in results, and collapse IF(STRT .LE. JJ) THEN LENGTH(NN) = STRT + ZEROES - START(NN) ELSE c No overlap c Check that section is not off the end of the actual stream. IF(STRT .LE. LEND) THEN NN = NN+1 c c Check to prevent overwriting an array IF(NN .GT. 1000) THEN ERR = 1 ELSE START(NN) = STRT LENGTH(NN) = ZEROES ENDIF ENDIF ENDIF ENDIF I = I+1 IF(I .LE. (LENBC*LL - 2)) GOTO 100 150 CONTINUE c c Handle possible shorter length for last pass MM = MMNXT IF(L+1 - (JBUF+2*MN) .LT. MN) THEN MMNXT = L+1 - (JBUF+2*MN) ENDIF c c Remember last two words of the B and C streams to next buffer BB(-1) = BB(LENBC*BLOCK - 1) BB(0) = BB(LENBC*BLOCK) CC(-1) = CC(LENBC*BLOCK - 1) CC(0) = CC(LENBC*BLOCK) c c Switch buffers and check to see that the read has completed TMP = FGBUF FGBUF = BGBUF BGBUF = TMP IF (L .GT. MN) THEN CALL SYNTMP(1) ENDIF 200 CONTINUE c RETURN END