1 05/16/86  find_bit_
  2 
  3 This subroutine uses the EIS test character and translate (TCT)
  4 instruction to efficiently perform common bit string search operations.
  5 Entrypoints are provided to return the bit index of the first or last
  6 occurrence of an on bit ("1"b) or off bit ("0"b) in a bit string.
  7 
  8 
  9 This subroutine operates by dividing the bit string into three search
 10 regions:  a group of 9-bit bytes aligned on a byte boundary; bits
 11 preceding these bytes; and bits following the bytes.  Bits preceding or
 12 following the bytes are examined bit-by-bit, using a separate compare
 13 bit (CMPB) instruction for each bit.  The bytes are examined as a
 14 single character string, using one TCT instruction to test all bytes
 15 until a byte containing an on or off bit is found.  For bit strings
 16 longer than 36 bits, this subroutine is significantly faster than the
 17 code generated by the PL/I index builtin function, which test all bits
 18 on a bit-by-bit basis.
 19 
 20 
 21 Entry points in find_bit_:
 22    (List is generated by the help command)
 23 
 24 
 25 :Entry:  first_on:  05/16/86 find_bit_$first_on
 26 
 27 
 28 Function:  This entrypoint returns the index (bit position) of the
 29 first (leftmost) bit which is on ("1"b) in a bit string.
 30 
 31 
 32 Syntax:
 33 declare find_bit_$first_on entry (bit(*)) returns (fixed bin(24))
 34      reducible;
 35 
 36 index = find_bit_$first_on (bit_string);
 37 
 38 
 39 Arguments:
 40 bit_string
 41    is the bit string to be examined.  (In)
 42 index
 43    is the index of the first "1"b bit within the bit string.  If no
 44    "1"b bits are found, then 0 is returned.  (Out)
 45 
 46 
 47 :Entry:  first_off:  05/16/86 find_bit_$first_off
 48 
 49 
 50 Function:  This entrypoint returns the index (bit position) of the
 51 first (leftmost) bit which is off ("0"b) in a bit string.
 52 
 53 
 54 Syntax:
 55 declare find_bit_$first_off entry (bit(*)) returns (fixed bin(24))
 56      reducible;
 57 
 58 index = find_bit_$first_off (bit_string);
 59 
 60 
 61 Arguments:
 62 bit_string
 63    is the bit string to be examined.  (In)
 64 index
 65    is the index of the first "0"b bit within the bit string.  If no
 66    "0"b bits are found, then 0 is returned.  (Out)
 67 
 68 
 69 :Entry:  last_on:  05/16/86 find_bit_$last_on
 70 
 71 
 72 Function:  This entrypoint returns the index (bit position) of the last
 73 (rightmost) bit which is on ("1"b) in a bit string.
 74 
 75 
 76 Syntax:
 77 declare find_bit_$last_on entry (bit(*)) returns (fixed bin(24))
 78      reducible;
 79 
 80 index = find_bit_$last_on (bit_string);
 81 
 82 
 83 Arguments:
 84 bit_string
 85    is the bit string to be examined.  (In)
 86 index
 87    is the index of the last "1"b bit within the bit string.  If no "1"b
 88    bits are found, then 0 is returned.  (Out)
 89 
 90 
 91 :Entry:  last_off:  05/16/86 find_bit_$last_off
 92 
 93 
 94 Function:  This entrypoint returns the index (bit position) of the last
 95 (rightmost) bit which is off ("0"b) in a bit string.
 96 
 97 
 98 Syntax:
 99 declare find_bit_$last_off entry (bit(*)) returns (fixed bin(24))
100      reducible;
101 
102 index = find_bit_$last_off (bit_string);
103 
104 
105 Arguments:
106 bit_string
107    is the bit string to be examined.  (In)
108 index
109    is the index of the last "0"b bit within the bit string.  If no "0"b
110    bits are found, then 0 is returned.  (Out)