1 /*

     2  * Copyright 1997-2006 Sun Microsystems, Inc.  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.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any 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 

    45     private static int subscript(int idx) {

    46         return idx / BITS_PER_UNIT;

    47     }

    48 

    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      */

    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      */

    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      */

   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      */

   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      */

   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      */

   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      */

   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      */

   169     public byte[] toByteArray() {

   170         return repn.clone();

   171     }

   172 

   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      */

   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      */

   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 

   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      */

   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 

   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 }