1 /* 2 * Copyright (c) 1997, 2006, 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 /** 68 * Creates a BitArray of the specified size, initialized from the 69 * specified byte array. The most significant bit of a[0] gets 70 * index zero in the BitArray. The array a must be large enough 71 * to specify a value for every bit in the BitArray. In other words, 72 * 8*a.length <= length. 73 */ BitArray(int length, byte[] a)74 public BitArray(int length, byte[] a) throws IllegalArgumentException { 75 76 if (length < 0) { 77 throw new IllegalArgumentException("Negative length for BitArray"); 78 } 79 if (a.length * BITS_PER_UNIT < length) { 80 throw new IllegalArgumentException("Byte array too short to represent " + 81 "bit array of given length"); 82 } 83 84 this.length = length; 85 86 int repLength = ((length + BITS_PER_UNIT - 1)/BITS_PER_UNIT); 87 int unusedBits = repLength*BITS_PER_UNIT - length; 88 byte bitMask = (byte) (0xFF << unusedBits); 89 90 /* 91 normalize the representation: 92 1. discard extra bytes 93 2. zero out extra bits in the last byte 94 */ 95 repn = new byte[repLength]; 96 System.arraycopy(a, 0, repn, 0, repLength); 97 if (repLength > 0) { 98 repn[repLength - 1] &= bitMask; 99 } 100 } 101 102 /** 103 * Create a BitArray whose bits are those of the given array 104 * of Booleans. 105 */ BitArray(boolean[] bits)106 public BitArray(boolean[] bits) { 107 length = bits.length; 108 repn = new byte[(length + 7)/8]; 109 110 for (int i=0; i < length; i++) { 111 set(i, bits[i]); 112 } 113 } 114 115 116 /** 117 * Copy constructor (for cloning). 118 */ BitArray(BitArray ba)119 private BitArray(BitArray ba) { 120 length = ba.length; 121 repn = ba.repn.clone(); 122 } 123 124 /** 125 * Returns the indexed bit in this BitArray. 126 */ get(int index)127 public boolean get(int index) throws ArrayIndexOutOfBoundsException { 128 if (index < 0 || index >= length) { 129 throw new ArrayIndexOutOfBoundsException(Integer.toString(index)); 130 } 131 132 return (repn[subscript(index)] & position(index)) != 0; 133 } 134 135 /** 136 * Sets the indexed bit in this BitArray. 137 */ set(int index, boolean value)138 public void set(int index, boolean value) 139 throws ArrayIndexOutOfBoundsException { 140 if (index < 0 || index >= length) { 141 throw new ArrayIndexOutOfBoundsException(Integer.toString(index)); 142 } 143 int idx = subscript(index); 144 int bit = position(index); 145 146 if (value) { 147 repn[idx] |= bit; 148 } else { 149 repn[idx] &= ~bit; 150 } 151 } 152 153 /** 154 * Returns the length of this BitArray. 155 */ length()156 public int length() { 157 return length; 158 } 159 160 /** 161 * Returns a Byte array containing the contents of this BitArray. 162 * The bit stored at index zero in this BitArray will be copied 163 * into the most significant bit of the zeroth element of the 164 * returned byte array. The last byte of the returned byte array 165 * will be contain zeros in any bits that do not have corresponding 166 * bits in the BitArray. (This matters only if the BitArray's size 167 * is not a multiple of 8.) 168 */ toByteArray()169 public byte[] toByteArray() { 170 return repn.clone(); 171 } 172 equals(Object obj)173 public boolean equals(Object obj) { 174 if (obj == this) return true; 175 if (obj == null || !(obj instanceof BitArray)) return false; 176 177 BitArray ba = (BitArray) obj; 178 179 if (ba.length != length) return false; 180 181 for (int i = 0; i < repn.length; i += 1) { 182 if (repn[i] != ba.repn[i]) return false; 183 } 184 return true; 185 } 186 187 /** 188 * Return a boolean array with the same bit values a this BitArray. 189 */ toBooleanArray()190 public boolean[] toBooleanArray() { 191 boolean[] bits = new boolean[length]; 192 193 for (int i=0; i < length; i++) { 194 bits[i] = get(i); 195 } 196 return bits; 197 } 198 199 /** 200 * Returns a hash code value for this bit array. 201 * 202 * @return a hash code value for this bit array. 203 */ hashCode()204 public int hashCode() { 205 int hashCode = 0; 206 207 for (int i = 0; i < repn.length; i++) 208 hashCode = 31*hashCode + repn[i]; 209 210 return hashCode ^ length; 211 } 212 213 clone()214 public Object clone() { 215 return new BitArray(this); 216 } 217 218 219 private static final byte[][] NYBBLE = { 220 { (byte)'0',(byte)'0',(byte)'0',(byte)'0'}, 221 { (byte)'0',(byte)'0',(byte)'0',(byte)'1'}, 222 { (byte)'0',(byte)'0',(byte)'1',(byte)'0'}, 223 { (byte)'0',(byte)'0',(byte)'1',(byte)'1'}, 224 { (byte)'0',(byte)'1',(byte)'0',(byte)'0'}, 225 { (byte)'0',(byte)'1',(byte)'0',(byte)'1'}, 226 { (byte)'0',(byte)'1',(byte)'1',(byte)'0'}, 227 { (byte)'0',(byte)'1',(byte)'1',(byte)'1'}, 228 { (byte)'1',(byte)'0',(byte)'0',(byte)'0'}, 229 { (byte)'1',(byte)'0',(byte)'0',(byte)'1'}, 230 { (byte)'1',(byte)'0',(byte)'1',(byte)'0'}, 231 { (byte)'1',(byte)'0',(byte)'1',(byte)'1'}, 232 { (byte)'1',(byte)'1',(byte)'0',(byte)'0'}, 233 { (byte)'1',(byte)'1',(byte)'0',(byte)'1'}, 234 { (byte)'1',(byte)'1',(byte)'1',(byte)'0'}, 235 { (byte)'1',(byte)'1',(byte)'1',(byte)'1'} 236 }; 237 238 private static final int BYTES_PER_LINE = 8; 239 240 /** 241 * Returns a string representation of this BitArray. 242 */ toString()243 public String toString() { 244 ByteArrayOutputStream out = new ByteArrayOutputStream(); 245 246 for (int i = 0; i < repn.length - 1; i++) { 247 out.write(NYBBLE[(repn[i] >> 4) & 0x0F], 0, 4); 248 out.write(NYBBLE[repn[i] & 0x0F], 0, 4); 249 250 if (i % BYTES_PER_LINE == BYTES_PER_LINE - 1) { 251 out.write('\n'); 252 } else { 253 out.write(' '); 254 } 255 } 256 257 // in last byte of repn, use only the valid bits 258 for (int i = BITS_PER_UNIT * (repn.length - 1); i < length; i++) { 259 out.write(get(i) ? '1' : '0'); 260 } 261 262 return new String(out.toByteArray()); 263 264 } 265 truncate()266 public BitArray truncate() { 267 for (int i=length-1; i>=0; i--) { 268 if (get(i)) { 269 return new BitArray(i+1, Arrays.copyOf(repn, (i + BITS_PER_UNIT)/BITS_PER_UNIT)); 270 } 271 } 272 return new BitArray(1); 273 } 274 275 } 276