1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.bloomfilter;
18
19 /**
20 * Contains functions to convert {@code int} indices into Bloom filter bit positions and visa versa.
21 *
22 * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
23 * in memory as a little-endian long value. This matches the requirements of the BitMapExtractor interface.</p>
24 *
25 * @since 4.5.0-M2
26 */
27 public class BitMaps {
28
29 /** A bit shift to apply to an integer to divided by 64 (2^6). */
30 private static final int DIVIDE_BY_64 = 6;
31
32 /**
33 * Checks if the specified index bit is enabled in the array of bit maps.
34 * <p>
35 * If the bit specified by bitIndex is not in the bit map false is returned.
36 * </p>
37 *
38 * @param bitMaps The array of bit maps.
39 * @param bitIndex the index of the bit to locate.
40 * @return {@code true} if the bit is enabled, {@code false} otherwise.
41 * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
42 */
43 public static boolean contains(final long[] bitMaps, final int bitIndex) {
44 return (bitMaps[getLongIndex(bitIndex)] & getLongBit(bitIndex)) != 0;
45 }
46
47 /**
48 * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit
49 * longs to store bits starting at index 0. The returned value is a {@code long} with only
50 * 1 bit set.
51 *
52 * <p>The index is assumed to be positive. For a positive index the result will match
53 * {@code 1L << (bitIndex % 64)}.</p>
54 *
55 * <p><em>If the input is negative the behavior is not defined.</em></p>
56 *
57 * @param bitIndex the bit index (assumed to be positive)
58 * @return the filter bit
59 */
60 public static long getLongBit(final int bitIndex) {
61 // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
62 // using 0x3f (63) or compute bitIndex % 64.
63 // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
64 // this will identify an incorrect bit.
65 return 1L << bitIndex;
66 }
67
68 /**
69 * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs
70 * to store bits starting at index 0.
71 *
72 * <p>The index is assumed to be positive. For a positive index the result will match
73 * {@code bitIndex / 64}.</p>
74 *
75 * <p><em>The divide is performed using bit shifts. If the input is negative the behavior
76 * is not defined.</em></p>
77 *
78 * @param bitIndex the bit index (assumed to be positive)
79 * @return the index of the bit map in an array of bit maps.
80 */
81 public static int getLongIndex(final int bitIndex) {
82 // An integer divide by 64 is equivalent to a shift of 6 bits if the integer is
83 // positive.
84 // We do not explicitly check for a negative here. Instead we use a
85 // signed shift. Any negative index will produce a negative value
86 // by sign-extension and if used as an index into an array it will throw an
87 // exception.
88 return bitIndex >> DIVIDE_BY_64;
89 }
90
91 /**
92 * Performs a modulus calculation on an unsigned long and a positive integer divisor.
93 *
94 * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)}
95 * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive,
96 * that is a strictly positive integer size.
97 *
98 * <p><em>If the divisor is negative the behavior is not defined.</em></p>
99 *
100 * @param dividend an unsigned long value to calculate the modulus of.
101 * @param divisor the divisor for the modulus calculation, must be strictly positive.
102 * @return the remainder or modulus value.
103 * @throws ArithmeticException if the divisor is zero
104 * @see Long#remainderUnsigned(long, long)
105 */
106 public static int mod(final long dividend, final int divisor) {
107 // See Hacker's Delight (2nd ed), section 9.3.
108 // Assume divisor is positive.
109 // Divide half the unsigned number and then double the quotient result.
110 final long quotient = (dividend >>> 1) / divisor << 1;
111 final long remainder = dividend - quotient * divisor;
112 // remainder in [0, 2 * divisor)
113 return (int) (remainder >= divisor ? remainder - divisor : remainder);
114 }
115
116 /**
117 * Creates a new bitmap for the number of bit maps (longs) required for the numberOfBits parameter.
118 *
119 * <p><em>If the input is negative the behavior is not defined.</em></p>
120 *
121 * @param numberOfBits the number of bits to store in the array of bit maps.
122 * @return a new bitmap.
123 */
124 static long[] newBitMap(final int numberOfBits) {
125 return new long[numberOfBitMaps(numberOfBits)];
126 }
127
128 /**
129 * Creates a new bitmap for given shape parameter.
130 *
131 * @param shape the shape.
132 * @return a new bitmap.
133 */
134 static long[] newBitMap(final Shape shape) {
135 return newBitMap(shape.getNumberOfBits());
136 }
137
138 /**
139 * Calculates the number of bit maps (longs) required for the numberOfBits parameter.
140 *
141 * <p><em>If the input is negative the behavior is not defined.</em></p>
142 *
143 * @param numberOfBits the number of bits to store in the array of bit maps.
144 * @return the number of bit maps necessary.
145 */
146 public static int numberOfBitMaps(final int numberOfBits) {
147 return (numberOfBits - 1 >> DIVIDE_BY_64) + 1;
148 }
149
150 /**
151 * Calculates the number of bit maps (longs) required for the shape parameter.
152 *
153 * @param shape the shape.
154 * @return the number of bit maps necessary.
155 */
156 static int numberOfBitMaps(final Shape shape) {
157 return numberOfBitMaps(shape.getNumberOfBits());
158 }
159
160 /**
161 * Sets the bit in the bit maps.
162 * <p><em>Does not perform range checking</em></p>
163 *
164 * @param bitMaps The array of bit maps.
165 * @param bitIndex the index of the bit to set.
166 * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
167 */
168 public static void set(final long[] bitMaps, final int bitIndex) {
169 bitMaps[getLongIndex(bitIndex)] |= getLongBit(bitIndex);
170 }
171
172 /** Do not instantiate. */
173 private BitMaps() {
174 }
175 }