1 /* 2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.security.util; 27 28 import java.io.ByteArrayOutputStream; 29 import java.util.Arrays; 30 31 /** 32 * A packed array of booleans. 33 * 34 * @author Joshua Bloch 35 * @author Douglas Hoover 36 */ 37 38 public class BitArray { 39 40 private byte[] repn; 41 private int length; 42 43 private static final int BITS_PER_UNIT = 8; 44 subscript(int idx)45 private static int subscript(int idx) { 46 return idx / BITS_PER_UNIT; 47 } 48 position(int idx)49 private static int position(int idx) { // bits big-endian in each unit 50 return 1 << (BITS_PER_UNIT - 1 - (idx % BITS_PER_UNIT)); 51 } 52 53 /** 54 * Creates a BitArray of the specified size, initialized to zeros. 55 */ BitArray(int length)56 public BitArray(int length) throws IllegalArgumentException { 57 if (length < 0) { 58 throw new IllegalArgumentException("Negative length for BitArray"); 59 } 60 61 this.length = length; 62 63 repn = new byte[(length + BITS_PER_UNIT - 1)/BITS_PER_UNIT]; 64 } 65 66 /** 67 * Creates a BitArray of the specified size, initialized from the 68 * specified byte array. The most significant bit of {@code a[0]} gets 69 * index zero in the BitArray. The array must be large enough to specify 70 * a value for every bit of the BitArray. i.e. {@code 8*a.length <= length}. 71 */ BitArray(int length, byte[] a)72 public BitArray(int length, byte[] a) throws IllegalArgumentException { 73 this(length, a, 0); 74 } 75 76 /** 77 * Creates a BitArray of the specified size, initialized from the 78 * specified byte array starting at the specified offset. The most 79 * significant bit of {@code a[ofs]} gets index zero in the BitArray. 80 * The array must be large enough to specify a value for every bit of 81 * the BitArray, i.e. {@code 8*(a.length - ofs) <= length}. 82 */ BitArray(int length, byte[] a, int ofs)83 public BitArray(int length, byte[] a, int ofs) 84 throws IllegalArgumentException { 85 86 if (length < 0) { 87 throw new IllegalArgumentException("Negative length for BitArray"); 88 } 89 if ((a.length - ofs) * BITS_PER_UNIT < length) { 90 throw new IllegalArgumentException 91 ("Byte array too short to represent " + length + "-bit array"); 92 } 93 94 this.length = length; 95 96 int repLength = ((length + BITS_PER_UNIT - 1)/BITS_PER_UNIT); 97 int unusedBits = repLength*BITS_PER_UNIT - length; 98 byte bitMask = (byte) (0xFF << unusedBits); 99 100 /* 101 normalize the representation: 102 1. discard extra bytes 103 2. zero out extra bits in the last byte 104 */ 105 repn = new byte[repLength]; 106 System.arraycopy(a, ofs, repn, 0, repLength); 107 if (repLength > 0) { 108 repn[repLength - 1] &= bitMask; 109 } 110 } 111 112 /** 113 * Create a BitArray whose bits are those of the given array 114 * of Booleans. 115 */ BitArray(boolean[] bits)116 public BitArray(boolean[] bits) { 117 length = bits.length; 118 repn = new byte[(length + 7)/8]; 119 120 for (int i=0; i < length; i++) { 121 set(i, bits[i]); 122 } 123 } 124 125 126 /** 127 * Copy constructor (for cloning). 128 */ BitArray(BitArray ba)129 private BitArray(BitArray ba) { 130 length = ba.length; 131 repn = ba.repn.clone(); 132 } 133 134 /** 135 * Returns the indexed bit in this BitArray. 136 */ get(int index)137 public boolean get(int index) throws ArrayIndexOutOfBoundsException { 138 if (index < 0 || index >= length) { 139 throw new ArrayIndexOutOfBoundsException(Integer.toString(index)); 140 } 141 142 return (repn[subscript(index)] & position(index)) != 0; 143 } 144 145 /** 146 * Sets the indexed bit in this BitArray. 147 */ set(int index, boolean value)148 public void set(int index, boolean value) 149 throws ArrayIndexOutOfBoundsException { 150 if (index < 0 || index >= length) { 151 throw new ArrayIndexOutOfBoundsException(Integer.toString(index)); 152 } 153 int idx = subscript(index); 154 int bit = position(index); 155 156 if (value) { 157 repn[idx] |= bit; 158 } else { 159 repn[idx] &= ~bit; 160 } 161 } 162 163 /** 164 * Returns the length of this BitArray. 165 */ length()166 public int length() { 167 return length; 168 } 169 170 /** 171 * Returns a Byte array containing the contents of this BitArray. 172 * The bit stored at index zero in this BitArray will be copied 173 * into the most significant bit of the zeroth element of the 174 * returned byte array. The last byte of the returned byte array 175 * will be contain zeros in any bits that do not have corresponding 176 * bits in the BitArray. (This matters only if the BitArray's size 177 * is not a multiple of 8.) 178 */ toByteArray()179 public byte[] toByteArray() { 180 return repn.clone(); 181 } 182 equals(Object obj)183 public boolean equals(Object obj) { 184 if (obj == this) return true; 185 if (obj == null || !(obj instanceof BitArray)) return false; 186 187 BitArray ba = (BitArray) obj; 188 189 if (ba.length != length) return false; 190 191 for (int i = 0; i < repn.length; i += 1) { 192 if (repn[i] != ba.repn[i]) return false; 193 } 194 return true; 195 } 196 197 /** 198 * Return a boolean array with the same bit values a this BitArray. 199 */ toBooleanArray()200 public boolean[] toBooleanArray() { 201 boolean[] bits = new boolean[length]; 202 203 for (int i=0; i < length; i++) { 204 bits[i] = get(i); 205 } 206 return bits; 207 } 208 209 /** 210 * Returns a hash code value for this bit array. 211 * 212 * @return a hash code value for this bit array. 213 */ hashCode()214 public int hashCode() { 215 int hashCode = 0; 216 217 for (int i = 0; i < repn.length; i++) 218 hashCode = 31*hashCode + repn[i]; 219 220 return hashCode ^ length; 221 } 222 223 clone()224 public Object clone() { 225 return new BitArray(this); 226 } 227 228 229 private static final byte[][] NYBBLE = { 230 { (byte)'0',(byte)'0',(byte)'0',(byte)'0'}, 231 { (byte)'0',(byte)'0',(byte)'0',(byte)'1'}, 232 { (byte)'0',(byte)'0',(byte)'1',(byte)'0'}, 233 { (byte)'0',(byte)'0',(byte)'1',(byte)'1'}, 234 { (byte)'0',(byte)'1',(byte)'0',(byte)'0'}, 235 { (byte)'0',(byte)'1',(byte)'0',(byte)'1'}, 236 { (byte)'0',(byte)'1',(byte)'1',(byte)'0'}, 237 { (byte)'0',(byte)'1',(byte)'1',(byte)'1'}, 238 { (byte)'1',(byte)'0',(byte)'0',(byte)'0'}, 239 { (byte)'1',(byte)'0',(byte)'0',(byte)'1'}, 240 { (byte)'1',(byte)'0',(byte)'1',(byte)'0'}, 241 { (byte)'1',(byte)'0',(byte)'1',(byte)'1'}, 242 { (byte)'1',(byte)'1',(byte)'0',(byte)'0'}, 243 { (byte)'1',(byte)'1',(byte)'0',(byte)'1'}, 244 { (byte)'1',(byte)'1',(byte)'1',(byte)'0'}, 245 { (byte)'1',(byte)'1',(byte)'1',(byte)'1'} 246 }; 247 248 private static final int BYTES_PER_LINE = 8; 249 250 /** 251 * Returns a string representation of this BitArray. 252 */ toString()253 public String toString() { 254 if (length == 0) { 255 return ""; 256 } 257 258 ByteArrayOutputStream out = new ByteArrayOutputStream(); 259 260 for (int i = 0; i < repn.length - 1; i++) { 261 out.write(NYBBLE[(repn[i] >> 4) & 0x0F], 0, 4); 262 out.write(NYBBLE[repn[i] & 0x0F], 0, 4); 263 264 if (i % BYTES_PER_LINE == BYTES_PER_LINE - 1) { 265 out.write('\n'); 266 } else { 267 out.write(' '); 268 } 269 } 270 271 // in last byte of repn, use only the valid bits 272 for (int i = BITS_PER_UNIT * (repn.length - 1); i < length; i++) { 273 out.write(get(i) ? '1' : '0'); 274 } 275 276 return new String(out.toByteArray()); 277 278 } 279 truncate()280 public BitArray truncate() { 281 for (int i=length-1; i>=0; i--) { 282 if (get(i)) { 283 return new BitArray(i+1, repn, 0); 284 } 285 } 286 return new BitArray(1); 287 } 288 289 } 290