////////////////// class BitOutputStream ////////////////////////////// package bitio; import java.io.ByteArrayInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.OutputStream; import java.util.Arrays; import java.util.Objects; /** * A BitOutputStream is a buffered stream designed to write an arbitrary * (up to limit of 32) number of bits. The bits are first written to an * internal bit buffer (an int) and then copied into an internal byte * buffer if the bit buffer is full. The bits in the byte buffer are * written to the underlying stream whenever the byte buffer reaches its * capacity, the BitOutputStream is closed, or is explicitly flushed. * Since BitOutputStream is already buffered, there is no need for * a BufferedOutputStream. * * It should be noticed that BitInputStream is not thread-safe. None of * the methods are synchronized. * * @author Ulf Uttersrud, Oslo Metropolitan University * @version 2.5 12.09.2017 */ public class BitOutputStream extends OutputStream { private static final int DEFAULT_BUFFER_SIZE = 4096; /** * The internal byte array where the bytes are temporarily stored. */ private byte buf[]; /** * The size of the internal byte array. */ private int bufSize; /** * The current position in the byte buffer. That is the position in * the byte array buf where the next byte will be written. The value * is always in the range 0 through buf.length and elements buf[0] * through buf[pos-1] contain valid bytes. The byte array is full, * and hence has to be emptied, if pos >= buf.length. */ private int pos; /** * An int used as an internal bit buffer. */ private int bits; /** * The number of valid (the rightmost) bits in the bit buffer. */ private int bitSize; /** * The underlying output stream. */ private OutputStream out; /** * Creates a BitOutputStream with the specified size as the length of * the internal byte array and saves its other argument, the output * stream, for later use. * * @param out * the underlying output stream. * @param size * the length of the byte buffer. * @exception IllegalArgumentException * if size <= 0. * @exception NullPointerException * if the output stream is not defined. */ public BitOutputStream(OutputStream out, int size) { if (out == null) throw new NullPointerException("The stream out is null"); if (size <= 0) throw new IllegalArgumentException("The size(" + size + ") <= 0"); buf = new byte[bufSize = size]; this.out = out; } /** * Creates a BitOutputStream and saves its argument, the output stream, * for later use. A default value DEFAULT_BUFFER_SIZE is used as * a buffer length. * * @param out * the underlying output stream. * @exception NullPointerException * if the the output stream is not defined. */ public BitOutputStream(OutputStream out) { this(out, DEFAULT_BUFFER_SIZE); } /** * Creates a BitOutputStream with the specified file name and with * size as the length of the internal byte array. * * @param fileName * the name of the file. * @param size * the length of the internal byte array. * @exception FileNotFoundException * if the file does not exist. * @exception IllegalArgumentException * if size <= 0. */ public BitOutputStream(String fileName, int size) throws FileNotFoundException { this(new FileOutputStream(fileName), size); } /** * Creates a BitOutputStream with the specified file name. A default * value DEFAULT_BUFFER_SIZE is used as the length of the internal * byte array. * * @param fileName * the name of the file. * @exception FileNotFoundException * if the file does not exist. */ public BitOutputStream(String fileName) throws FileNotFoundException { this(new FileOutputStream(fileName), DEFAULT_BUFFER_SIZE); } /** * A method that creates and returns a BitOutputStream with * the specified file name and a default value as a buffer length. * * @param fileName * the name of the file. * @exception FileNotFoundException * if the file can not be created. * @return * the created BitOutputStream */ public static BitOutputStream toFile(String fileName) throws FileNotFoundException { return new BitOutputStream(new FileOutputStream(fileName)); } /** * A factory method that creates and returns a BitOutputStream with * the specified filename. If the second argument append is true, then * bits will be written to the end of the file rather than the beginning. * A default value is used as a buffer length. * * @param fileName * the name of the file. * @param append * if true, then bits will be written to the end of the file rather * than the beginning. * @exception FileNotFoundException * if the file cannot be created or opened. * @return * the created BitOutputStream */ public static BitOutputStream toFile(String fileName, boolean append) throws FileNotFoundException { return new BitOutputStream(new FileOutputStream(fileName, append)); } /** Flushes the internal byte buffer */ private void flushBuffer() throws IOException { if (out == null) throw new IOException("The stream is closed!"); if (pos > 0) { out.write(buf, 0, pos); pos = 0; } } // end flushBuffer /** * Writes one bit (i.e. the rightmost bit of the argument bit) to * the output stream. * * @param bit * containing the bit * @exception IOException * if an I/O error occurs. */ public void writeBit(int bit) throws IOException { bits <<= 1; // a bit can now be added bits |= (bit & 1); // the last bit of the parameter bit is added bitSize++; // bitSize is updated if (bitSize >= 8) // a byte can be moved to the byte buffer { bitSize = 0; // the byte buffer is flushed if it is full if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) bits; // a byte is moved } } // end writeBit /** * Writes a 0-bit to the output stream. * * @exception IOException * if an I/O error occurs. */ public void write0Bit() throws IOException { bits <<= 1; // adds a 0-bit bitSize++; // bitSize is updated if (bitSize >= 8) // a byte can be moved to the byte buffer { bitSize = 0; // the byte buffer is flushed if it is full if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) bits; // a byte is moved } } // end write0Bit /** * Writes a 1-bit to the output stream. * * @exception IOException * if an I/O error occurs. */ public void write1Bit() throws IOException { bits <<= 1; // a bit can now be added bits |= 1; // adds a 1-bit bitSize++; // bitSize is updated if (bitSize >= 8) // a byte can be moved to the byte buffer { bitSize = 0; // the byte buffer is flushed if it is full if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) bits; // a byte is moved } } // end write1Bit /** * Writes 8 bits (a byte) (i.e. the rightmost 8 bits of the argument b) to the * output stream. * * @param b * containing the byte * @exception IOException * if an I/O error occurs. */ @Override public void write(int b) throws IOException { bits <<= 8; // 8 bits can now be added bits |= (b & 0xff); // adds the 8 rightmost bits of b // the byte buffer is flushed if it is full if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); // a byte is moved } // end write /** * Writes the requested (rightmost) numberOfBits from the argument value to * the output stream. An IllegalArgumentException is thrown if the requested * number of bits is is not in the range [0,32]. No bits are written if * numberOfBits is equal to 0. * * @param value * containing the bits * @param numberOfBits * the (rightmost) number of bits from value to be written * @exception IOException * if an I/O error occurs. * @exception IllegalArgumentException * if numberOfBits is not in the range [0,32] */ public void writeBits(int value, int numberOfBits) throws IOException { if (numberOfBits < 0) throw new IllegalArgumentException("Cannot write " + numberOfBits + " bits!"); if (numberOfBits <= 25) // the most common case { bits <<= numberOfBits; // will not create overflow bits |= (value & ((1 << numberOfBits) - 1)); // the bits are added bitSize += numberOfBits; // the bitsize is updated while (bitSize >= 8) { bitSize -= 8; // the byte buffer is flushed if it is full if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); // a byte is moved } } else if (numberOfBits <= 32) { int k = numberOfBits - 25; // 1 <= k <= 7 bits <<= 25; // 25 bits can now be added bits |= (value >> k) & 0x1ffffff; // 25 bits are added bitSize += 25; // bitSize is updated // the bit buffer contains at least 25 bits, // 24 of them are moved to the byte buffer bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); bits <<= k; // k bits can now be added bits |= (value & ((1 << k) - 1)); // the rightmost k bits of value bitSize += k; // bitSize is updated if (bitSize >= 8) // 2 <= bitSize <= 15 { bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); // a byte is moved } } else throw new IllegalArgumentException("Cannot write " + numberOfBits + " bits!"); } // end writeBits /** * Writes the significant binary digits (bits) of <code>value</code> * to the output stream. All 32 digits are written if <code>value</code> * is negative. If value is equal to 0, then a 0-digit is written. This * coincides with the "digits/bits" returned by the method * <code>Integer.toBinaryString(value)</code>. * * @param value * containing the bits * @exception IOException * if an I/O error occurs. */ public void writeBits(int value) throws IOException { // must find the number of significant bits of value int signifcantBits = 31, v = value; if (v >>> 16 == 0) { signifcantBits -= 16; v <<= 16; } if (v >>> 24 == 0) { signifcantBits -= 8; v <<= 8; } if (v >>> 28 == 0) { signifcantBits -= 4; v <<= 4; } if (v >>> 30 == 0) { signifcantBits -= 2; v <<= 2; } signifcantBits += v >>> 31; bitSize += signifcantBits; if (bitSize <= 32) { bits <<= signifcantBits; // will not create overflow bits |= value; // the signifcantBits are added while (bitSize >= 8) { bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); } } else { int k = bitSize - 32; bits <<= signifcantBits - k; bits |= value >>> k; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> 24); if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> 16); if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> 8); if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) bits; bits = value; bitSize = k; } } // end writeBits /** * Writes the requested (leftmost) numberOfBits from the argument value to * the output stream. An IllegalArgumentException is thrown if the requested * number of bits is outside the range [0,32]. No bits are written if * numberOfBits is equal to 0. * * @param value * containing the bits * @param numberOfBits * the (leftmost) number of bits from value to be written * @exception IOException * if an I/O error occurs. * @exception IllegalArgumentException * if numberOfBits is outside the range [0,32] */ public void writeLeftBits(int value, int numberOfBits) throws IOException { if (numberOfBits < 0) throw new IllegalArgumentException("Cannot write a negative (" + numberOfBits + ") number of bits!"); if (numberOfBits <= 25) // the most common case { bits <<= numberOfBits; // will not create overflow bits |= (value >>> (32 - numberOfBits)); // the bits are added bitSize += numberOfBits; // the bitsize is updated while (bitSize >= 8) { bitSize -= 8; // the byte buffer is flushed if it is full if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); // a byte is moved } } else if (numberOfBits <= 32) { bits <<= 25; // 25 bits can now be added bits |= (value >>> 7); // 25 bits are added bitSize += 25; // bitSize is updated // the bit buffer contains at least 25 bits, // 24 of them are moved to the byte buffer bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); int k = numberOfBits - 25; // 1 <= k <= 7 bits <<= k; // the missing k bits can now be added bits |= ((value >>> (32 - numberOfBits)) & ((1 << k) - 1)); bitSize += k; // bitSize is updated if (bitSize >= 8) // 2 <= bitSize <= 15 { bitSize -= 8; if (pos >= bufSize) flushBuffer(); buf[pos++] = (byte) (bits >> bitSize); // a byte is moved } } else throw new IllegalArgumentException("Cannot write " + numberOfBits + " bits!"); } // end writeBits /** * Writes the leftmost significant bits of the argument value (the bits * to the left of the trailing zeros) to the output stream. If value is * equal to 0, nothing is written. * * @param value * containing the bits * @exception IOException * if an I/O error occurs. */ public void writeLeftBits(int value) throws IOException { writeLeftBits(value, 32 - Integer.numberOfTrailingZeros(value)); } // end writeBits /** * Flushes this buffered output stream. This forces any buffered output * bits to be written to the underlying output stream. If the number of * buffered output bits is not a multiple of 8, then a sufficient number * of 0-bits are added. * * @exception IOException * if an I/O error occurs. */ @Override public void flush() throws IOException { if (bitSize > 0) { // the byte buffer is written to the ouput stream if it is full if (pos >= bufSize) flushBuffer(); // 0-bits are added to create a full byte buf[pos++] = (byte) (bits <<= (8 - bitSize)); bitSize = 0; } flushBuffer(); out.flush(); } // end flush() /** * Returns the number of bits missing in order to fill the last byte. * If the method is called previous to a close (or a flush), the return * value tells how many 0-bits are shifted into the last byte. * * @throws IOException * if an I/O error occurs. * * @return the number of bits missing in order to fill the last byte. */ public int missingBits() throws IOException { if (out == null) throw new IOException("The stream is closed!"); return bitSize == 0 ? 0 : 8 - bitSize; } /** * Closes the underlying output stream and releases any system resources * associated with the stream. The internal buffers are emptied (the method * flush() is called) before the underlying stream is closed. Any method call * subsequent to a close will result in an IOException with the message "The * stream is closed!". * * @exception IOException * if an I/O error occurs. */ @Override public void close() throws IOException { // a second call to close will have no effect if (out == null) return; flush(); out.close(); // The variables out and buf are set to null, pos and bufSize to -1 // and bitSize to 8. This will prevent any method call subsequent to // a close. Such an effort will result in an IOException with // the message "The stream is closed!". out = null; buf = null; pos = bufSize = -1; bitSize = 8; } // end close() /** * Converts a byte array b to a string of '0'- and '1'-characters. * The boolean parameter space decides if there will be a space * between to bytes or not. * * An example: the byte array {-1, 15} has "11111111 00001111" as * a result. The purpose of the method is give the programmer an * opportunity to observe the behavior of the write methods * by for instance using a ByteArrayOutputStream as the * underlying stream. * * @param b the byte array * @param space decides space or not between groups * @return the byte array turned into a string of * characters ('0' or '1') */ public static String toBitStringWithSpace(byte... b) { StringBuilder builder = new StringBuilder(); String[] fourBits = {"0000","0001","0010","0011","0100","0101","0110","0111", "1000","1001","1010","1011","1100","1101","1110","1111"}; if (b.length > 0) { builder.append(fourBits[(b[0] & 255) >> 4]); builder.append(fourBits[b[0] & 15]); } for (int i = 1; i < b.length; i++) { builder.append(' '); builder.append(fourBits[(b[i] & 255) >> 4]); builder.append(fourBits[b[i] & 15]); } return builder.toString(); } /** * Converts a byte array b to a string of '0'- and '1'-characters. * An example: the byte array {-1, 15} will be converted * to the string "1111111100001111". The purpose of this method * is give the programmer an opportunity to observe the behavior of * the write methods by for instance using a ByteArrayOutputStream * as the underlying stream. * * @param b the byte array * @return the byte array turned into a string of * characters ('0' or '1') */ public static String toBitString(byte... b) { StringBuilder builder = new StringBuilder(); String[] fourBits = {"0000","0001","0010","0011","0100","0101","0110","0111", "1000","1001","1010","1011","1100","1101","1110","1111"}; if (b.length > 0) { builder.append(fourBits[(b[0] & 255) >> 4]); builder.append(fourBits[b[0] & 15]); } for (int i = 1; i < b.length; i++) { builder.append(fourBits[(b[i] & 255) >> 4]); builder.append(fourBits[b[i] & 15]); } return builder.toString(); } /** * Converts a byte array b to a partitioned string of '0'- * and '1'-characters. Each element of the array partition * must be in the interval [1,31]. * * An example: (byte)-1 = 11111111 and (byte)15 = 00001111. * Let the byte array b be given by {(byte)-1,(byte)15} and * the partition array part by {4,4,4,4}. Then * toBitString(b, part) will return the partitioned string * "1111 1111 0000 1111". If instead part = {1,2,3,4,5,6}, * then we get the string "1 11 111 1100 00111 1" (ending * with only one bit since there are 16 bits all together). * * The method can, by using a ByteArrayOutputStream as the * underlying stream, "visualize" the behavior of the write * methods. Example: * ByteArrayOutputStream buf = new ByteArrayOutputStream(); * BitOutputStream out = new BitOutputStream(buf); * out.writeBits(5,3); // 101 * out.writeBits(0,2); // 00 * out.writeBits(6,3); // 110 * out.close(); * int[] part = {3,2,3}; * String s = * BitOutputStream.toBitString(buf.toByteArray(),part); * System.out.println(s); // 101 00 110 * * @param b the byte array * @param part the partition array * @return the byte array turned into a partitioned * string of characters ('0' or '1') * @throws java.lang.NullPointerException if b is null * @throws java.lang.NullPointerException if part is null */ public static String toBitString(byte[] b, int[] part) { Objects.requireNonNull(b, "Argument b is null!"); Objects.requireNonNull(part, "Argument part is null!"); StringBuilder build = new StringBuilder(); try (BitInputStream in = new BitInputStream(new ByteArrayInputStream(b))) { for (int i = 0; i < part.length; i++) { int numberOfBits = part[i]; int bits = in.readBits(numberOfBits); if (bits == -1) // fewer than numberOfBits left in the stream { numberOfBits = in.availableBits(); if (numberOfBits == 0) break; bits = in.readBits(numberOfBits); // the rest of the bits } for (int filter = 1 << (numberOfBits - 1); filter > 0; filter >>= 1) { build.append((filter & bits) != 0 ? '1' : '0'); } if (numberOfBits > 0) build.append(' '); } in.close(); } catch (IOException io) {} // removes an unnecessary space at the end if (build.length() > 0) build.deleteCharAt(build.length() - 1); return build.toString(); } /** * Converts a byte array b to a partitioned string of '0'- * and '1'-characters. The parameter numberOfBits gives * the size of each part. The value must be from 1 to 31. * * An example: (byte)-1 = 11111111 and (byte)15 = 00001111. * Let the byte array b be given by b = {(byte)-1,(byte)15} * and numberOfBits = 5. Then toBitString(b, numberOfBits) * will return the partitioned string "11111 11100 00111 1" * (ending with only one bit since there are 16 = 3*5 + 1 bits). * The purpose of the method is give the programmer a mean to * study the behavior of the write methods by for instance using * a ByteArrayOutputStream as the underlying stream. * * @param b the byte array * @param numberOfBits the length of each group * @return the byte array turned into a partitioned string of * characters ('0' or '1') * @throws java.lang.NullPointerException if b is null * @throws java.lang.IllegalArgumentException * if numberOfBits is outside [1,31] */ public static String toBitString(byte[] b, int numberOfBits) { if (numberOfBits < 1 || numberOfBits > 31) throw new IllegalArgumentException("NumberOfBits is illegal!"); Objects.requireNonNull(b, "Argument b is null!"); int n = 8 * b.length, q = n / numberOfBits; int[] part = q * numberOfBits == n ? new int[q] : new int[q + 1]; Arrays.fill(part, numberOfBits); return toBitString(b, part); } } // End of class BitOutputStream