BitSequence.java

/*
 * Copyright (c) 2025, Stein Eldar Johnsen
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied. See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package net.morimekta.collect.util;

/**
 * A Bit Sequence is a sequence of single bit values represented by
 * boolean values.
 * <p>
 * Bit strings have a canonical bit representation using one octet
 * as a count of unused bits in the last octet, and the rest is
 * encoding the bits in order:
 * <p>
 * There are two concrete implementation of {@link BitSequence}:
 * <ul>
 *     <li>
 *         The final and immutable {@link BitString}, which can be used in a
 *         similar fashion as {@code String}.
 *     </li>
 *     <li>
 *         The mutable {@link BitStringBuilder}, which can be used in a similar
 *         fashion to {@code StringBuilder}, to generate a
 *     </li>
 * </ul>
 * <p>
 * Also see
 * <a href="https://www.javadoc.io/doc/net.morimekta.utils/io/latest/net.morimekta.io/net/morimekta/io/BitPackingOutputStream.html">
 *     <code>net.morimekta.io.BitPackingOutputStream</code>
 * </a> and
 * <a href="https://www.javadoc.io/doc/net.morimekta.utils/io/latest/net.morimekta.io/net/morimekta/io/BitPackingInputStream.html">
 *     <code>net.morimekta.io.BitPackingInputStream</code>
 * </a>
 */
public abstract class BitSequence {
    protected BitSequence() {
    }

    /**
     * Get the size of the bit string. This represent the number of bits
     * contained.
     *
     * @return The number of bits.
     */
    public abstract int size();

    public abstract boolean bitAt(int pos);

    public abstract boolean[] toBitArray();

    public abstract byte[] toByteArray();

    public abstract String toBitString();

    protected abstract void writeTo(boolean[] out, int off);

    @Override
    public String toString() {
        return getClass().getSimpleName() + "{" + toBitString() + "}";
    }

    // ---- Private ----

    private static boolean safeGet(boolean[] data, int i) {
        if (i >= data.length) return false;
        return data[i];
    }

    protected static byte[] toByteArrayInternal(boolean[] data, int size) {
        var byteSize = size / 8 + (size % 8 == 0 ? 0 : 1);
        var unused   = (byteSize * 8 - size) % 8;
        var buffer   = new byte[1 + byteSize];
        buffer[0] = (byte) unused;
        for (int i = 0; i < byteSize; i++) {
            var pos = i * 8;
            var b = (safeGet(data, pos) ? 128 : 0) |
                    (safeGet(data, pos + 1) ? 64 : 0) |
                    (safeGet(data, pos + 2) ? 32 : 0) |
                    (safeGet(data, pos + 3) ? 16 : 0) |
                    (safeGet(data, pos + 4) ? 8 : 0) |
                    (safeGet(data, pos + 5) ? 4 : 0) |
                    (safeGet(data, pos + 6) ? 2 : 0) |
                    (safeGet(data, pos + 7) ? 1 : 0);
            buffer[i + 1] = (byte) b;
        }
        return buffer;
    }

    protected static boolean[] fromByteArrayInternal(byte[] bytes, int start, int end) {
        if (start < 0 || start > end || bytes.length < end) {
            throw new IndexOutOfBoundsException("Index: [" + start + ".." + end + "] of byte[" + bytes.length + "]");
        }

        int unused   = bytes[start] & 0x0F;
        int bitCount = ((end - start) * 8) - 8 - unused;

        var buf = new boolean[bitCount];
        for (int i = 0, pos = -1; i < bitCount; i++) {
            if (i % 8 == 0) {
                ++pos;
            }
            var mask = 128 >> (i % 8);
            buf[i] = (bytes[1 + pos] & mask) != 0;
        }
        return buf;
    }

    protected static String toStringFromBits(boolean[] bits, int bitCount) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < bitCount; i++) {
            if ((i % 8) == 0 && i > 0) {
                sb.append("_");
            }
            sb.append(bits[i] ? "1" : "0");
        }
        return sb.toString();
    }
}