001: /*
002: * @(#)BitArray.java 1.14 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package sun.security.util;
029:
030: import java.io.ByteArrayOutputStream;
031:
032: /**
033: * A packed array of booleans.
034: *
035: * @author Joshua Bloch
036: * @author Douglas Hoover
037: * @version 1.7 02/02/00
038: */
039:
040: public class BitArray {
041:
042: private byte[] repn;
043: private int length;
044:
045: private static final int BITS_PER_UNIT = 8;
046:
047: private static int subscript(int idx) {
048: return idx / BITS_PER_UNIT;
049: }
050:
051: private static int position(int idx) { // bits big-endian in each unit
052: return 1 << (BITS_PER_UNIT - 1 - (idx % BITS_PER_UNIT));
053: }
054:
055: /**
056: * Creates a BitArray of the specified size, initialized to zeros.
057: */
058: public BitArray(int length) throws IllegalArgumentException {
059: if (length < 0) {
060: throw new IllegalArgumentException(
061: "Negative length for BitArray");
062: }
063:
064: this .length = length;
065:
066: repn = new byte[(length + BITS_PER_UNIT - 1) / BITS_PER_UNIT];
067: }
068:
069: /**
070: * Creates a BitArray of the specified size, initialized from the
071: * specified byte array. The most significant bit of a[0] gets
072: * index zero in the BitArray. The array a must be large enough
073: * to specify a value for every bit in the BitArray. In other words,
074: * 8*a.length <= length.
075: */
076: public BitArray(int length, byte[] a)
077: throws IllegalArgumentException {
078:
079: if (length < 0) {
080: throw new IllegalArgumentException(
081: "Negative length for BitArray");
082: }
083: if (a.length * BITS_PER_UNIT < length) {
084: throw new IllegalArgumentException(
085: "Byte array too short to represent "
086: + "bit array of given length");
087: }
088:
089: this .length = length;
090:
091: int repLength = ((length + BITS_PER_UNIT - 1) / BITS_PER_UNIT);
092: int unusedBits = repLength * BITS_PER_UNIT - length;
093: byte bitMask = (byte) (0xFF << unusedBits);
094:
095: /*
096: normalize the representation:
097: 1. discard extra bytes
098: 2. zero out extra bits in the last byte
099: */
100: repn = new byte[repLength];
101: System.arraycopy(a, 0, repn, 0, repLength);
102: if (repLength > 0) {
103: repn[repLength - 1] &= bitMask;
104: }
105: }
106:
107: /**
108: * Create a BitArray whose bits are those of the given array
109: * of Booleans.
110: */
111: public BitArray(boolean[] bits) {
112: length = bits.length;
113: repn = new byte[(length + 7) / 8];
114:
115: for (int i = 0; i < length; i++) {
116: set(i, bits[i]);
117: }
118: }
119:
120: /**
121: * Copy constructor (for cloning).
122: */
123: private BitArray(BitArray ba) {
124: length = ba.length;
125: repn = (byte[]) ba.repn.clone();
126: }
127:
128: /**
129: * Returns the indexed bit in this BitArray.
130: */
131: public boolean get(int index) throws ArrayIndexOutOfBoundsException {
132: if (index < 0 || index >= length) {
133: throw new ArrayIndexOutOfBoundsException(Integer
134: .toString(index));
135: }
136:
137: return (repn[subscript(index)] & position(index)) != 0;
138: }
139:
140: /**
141: * Sets the indexed bit in this BitArray.
142: */
143: public void set(int index, boolean value)
144: throws ArrayIndexOutOfBoundsException {
145: if (index < 0 || index >= length) {
146: throw new ArrayIndexOutOfBoundsException(Integer
147: .toString(index));
148: }
149: int idx = subscript(index);
150: int bit = position(index);
151:
152: if (value) {
153: repn[idx] |= bit;
154: } else {
155: repn[idx] &= ~bit;
156: }
157: }
158:
159: /**
160: * Returns the length of this BitArray.
161: */
162: public int length() {
163: return length;
164: }
165:
166: /**
167: * Returns a Byte array containing the contents of this BitArray.
168: * The bit stored at index zero in this BitArray will be copied
169: * into the most significant bit of the zeroth element of the
170: * returned byte array. The last byte of the returned byte array
171: * will be contain zeros in any bits that do not have corresponding
172: * bits in the BitArray. (This matters only if the BitArray's size
173: * is not a multiple of 8.)
174: */
175: public byte[] toByteArray() {
176: return (byte[]) repn.clone();
177: }
178:
179: public boolean equals(Object obj) {
180: if (obj == this )
181: return true;
182: if (obj == null || !(obj instanceof BitArray))
183: return false;
184:
185: BitArray ba = (BitArray) obj;
186:
187: if (ba.length != length)
188: return false;
189:
190: for (int i = 0; i < repn.length; i += 1) {
191: if (repn[i] != ba.repn[i])
192: return false;
193: }
194: return true;
195: }
196:
197: /**
198: * Return a boolean array with the same bit values a this BitArray.
199: */
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: */
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: public Object clone() {
224: return new BitArray(this );
225: }
226:
227: private static final byte[][] NYBBLE = {
228: { (byte) '0', (byte) '0', (byte) '0', (byte) '0' },
229: { (byte) '0', (byte) '0', (byte) '0', (byte) '1' },
230: { (byte) '0', (byte) '0', (byte) '1', (byte) '0' },
231: { (byte) '0', (byte) '0', (byte) '1', (byte) '1' },
232: { (byte) '0', (byte) '1', (byte) '0', (byte) '0' },
233: { (byte) '0', (byte) '1', (byte) '0', (byte) '1' },
234: { (byte) '0', (byte) '1', (byte) '1', (byte) '0' },
235: { (byte) '0', (byte) '1', (byte) '1', (byte) '1' },
236: { (byte) '1', (byte) '0', (byte) '0', (byte) '0' },
237: { (byte) '1', (byte) '0', (byte) '0', (byte) '1' },
238: { (byte) '1', (byte) '0', (byte) '1', (byte) '0' },
239: { (byte) '1', (byte) '0', (byte) '1', (byte) '1' },
240: { (byte) '1', (byte) '1', (byte) '0', (byte) '0' },
241: { (byte) '1', (byte) '1', (byte) '0', (byte) '1' },
242: { (byte) '1', (byte) '1', (byte) '1', (byte) '0' },
243: { (byte) '1', (byte) '1', (byte) '1', (byte) '1' } };
244:
245: private static final int BYTES_PER_LINE = 8;
246:
247: /**
248: * Returns a string representation of this BitArray.
249: */
250: public String toString() {
251: ByteArrayOutputStream out = new ByteArrayOutputStream();
252:
253: for (int i = 0; i < repn.length - 1; i++) {
254: out.write(NYBBLE[(repn[i] >> 4) & 0x0F], 0, 4);
255: out.write(NYBBLE[repn[i] & 0x0F], 0, 4);
256:
257: if (i % BYTES_PER_LINE == BYTES_PER_LINE - 1) {
258: out.write('\n');
259: } else {
260: out.write(' ');
261: }
262: }
263:
264: // in last byte of repn, use only the valid bits
265: for (int i = BITS_PER_UNIT * (repn.length - 1); i < length; i++) {
266: out.write(get(i) ? '1' : '0');
267: }
268:
269: return new String(out.toByteArray());
270:
271: }
272:
273: }
|