Утилита для извлечения битов из байтового массива в новый байт [] - PullRequest
Новая
       45

Утилита для извлечения битов из байтового массива в новый байт []

1 голос
/ 12 июля 2019

Я пытаюсь создать служебный класс, чтобы сделать побитовые манипуляции и преобразования более читабельными.В настоящее время я застрял в создании метода для извлечения битов из байтового массива и формирования из них нового байта [].Излишне говорить, что я не очень хорошо разбираюсь в побитовых операциях.

Я полагаю, что этого можно достичь с помощью BitSet, но было бы слишком много преобразований, и реализация была бы специфичной для Java.Было бы неплохо иметь понятный алгоритм, который позже можно было бы легко перенести на другие языки.

До сих пор я дошел до этого: 

    public static byte[] toBytes(int offset /*full bytes*/, int bitsOffset /*bytes + bits*/, int bitsCount, byte... bytes) {
        int bytesCount = bitsCount / 8;
        int paddingBits = bitsCount % 8;
        int partialBits = 8 - paddingBits;

        if (paddingBits > 0) {
            bytesCount++;
        }

        byte[] data = new byte[bytesCount];

        return data;
    }

Я прокомментировал вышеи временно заменил его на 

    public static byte[] toBytes(int offset, int bitsOffset, int bitsCount, byte... bytes) {
        int firstBitIndex = (offset * 8) + bitsOffset;
        return new BigInteger(new BigInteger(1, bytes).toString(2).substring(firstBitIndex, firstBitIndex + bitsCount), 2).toByteArray();
    }

Однако я все же хотел бы иметь правильную реализацию с как можно меньшими накладными расходами и не специфичную для Java (не используются специфичные для Java инструменты, такие как BitSet)

Это подсказка, что я ожидал бы сделать 

   /**
     * [0000 0110   1111 0010] = toBytes(1, 4, 12, [xxxx xxxx   xxxx 0110   1111 0010   xxxx xxxx])
     * [0000 0110   1111 0010] = toBytes(1, 5, 12, [xxxx xxxx   xxxx x011   0111 1001   0xxx xxxx])
     * [0000 0110   1111 0010] = toBytes(1, 6, 12, [xxxx xxxx   xxxx xx01   1011 1100   10xx xxxx])
     */

А вот несколько юнит-тестов 

public class ByteUtilTest {

    @Test
    public void toBytes_sameByte() {
        byte[] result = ByteUtil.toBytes(1, 4, 3,
                toByte("11111111"),
                toByte("11110111"),
                toByte("11111111"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("00000011")), toBinaryString(result));
    }

    @Test
    public void toBytes_sameByte_full() {
        byte[] result = ByteUtil.toBytes(1, 0, 8,
                toByte("11111111"),
                toByte("01110101"),
                toByte("11111111"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("01110101")), toBinaryString(result));
    }

    @Test
    public void toBytes_sameByte_noneWithoutOffset() {
        byte[] result = ByteUtil.toBytes(1, 0, 0,
                toByte("11111111"),
                toByte("01110101"),
                toByte("11111111"),
                toByte("11111111"));

        assertEquals(0, result.length);
    }

    @Test
    public void toBytes_sameByte_noneWithOffset() {
        byte[] result = ByteUtil.toBytes(1, 3, 0,
                toByte("11111111"),
                toByte("01110101"),
                toByte("11111111"),
                toByte("11111111"));

        assertEquals(0, result.length);
    }

    @Test
    public void toBytes_twoBytes_resultWithTwoBytes() {
        byte[] result = ByteUtil.toBytes(1, 2, 11,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011111"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("00000110"), toByte("10110011")), toBinaryString(result));
    }

    @Test
    public void toBytes_twoBytes_resultWithOneByte() {
        byte[] result = ByteUtil.toBytes(1, 2, 7,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011111"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("01101011")), toBinaryString(result));
    }

    @Test
    public void toBytes_twoBytes_firstFull() {
        byte[] result = ByteUtil.toBytes(1, 0, 11,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011111"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("00000011"), toByte("10101100")), toBinaryString(result));
    }

    @Test
    public void toBytes_twoBytes_lastFull() {
        byte[] result = ByteUtil.toBytes(1, 5, 11,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011101"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("00000101"), toByte("10011101")), toBinaryString(result));
    }

    @Test
    public void toBytes_twoBytes_bothFull() {
        byte[] result = ByteUtil.toBytes(1, 0, 16,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011101"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("01110101"), toByte("10011101")), toBinaryString(result));
    }

    @Test
    public void toBytes_threeBytes() {
        byte[] result = ByteUtil.toBytes(1, 2, 19,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011101"),
                toByte("10111111"));

        assertEquals(
                toBinaryString(
                        toByte("00000110"),
                        toByte("10110011"),
                        toByte("10110111")),
                toBinaryString(result));
    }

    @Test
    public void toBytes_threeBytes_firstFull() {
        byte[] result = ByteUtil.toBytes(1, 0, 19,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011101"),
                toByte("10111111"));

        assertEquals(
                toBinaryString(
                        toByte("00000011"),
                        toByte("10101100"),
                        toByte("11101101")),
                toBinaryString(result));
    }

    @Test
    public void toBytes_threeBytes_lastFull() {
        byte[] result = ByteUtil.toBytes(1, 2, 22,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011101"),
                toByte("10111111"));

        assertEquals(
                toBinaryString(
                        toByte("00110101"),
                        toByte("10011101"),
                        toByte("10111111")),
                toBinaryString(result));
    }

    @Test
    public void toBytes_threeBytes_allFull() {
        byte[] result = ByteUtil.toBytes(1, 0, 24,
                toByte("11111111"),
                toByte("01110101"),
                toByte("10011101"),
                toByte("10111111"));

        assertEquals(
                toBinaryString(
                        toByte("01110101"),
                        toByte("10011101"),
                        toByte("10111111")),
                toBinaryString(result));
    }



    @Test
    public void toBytes_bitsOffset_4() {
        byte[] result = ByteUtil.toBytes(1, 4, 12,
                toByte("11111111"),
                toByte("11110110"),
                toByte("11110010"),
                toByte("11111111"));

        assertEquals(toBinaryString(toByte("00000110"), toByte("11110010")), toBinaryString(result));
    }

    @Test
    public void toBytes_bitsOffset_5() {
        byte[] result = ByteUtil.toBytes(1, 5, 12,
                toByte("11111111"),
                toByte("11111011"),
                toByte("01111001"),
                toByte("01111111"));

        assertEquals(toBinaryString(toByte("00000110"), toByte("11110010")), toBinaryString(result));
    }

    @Test
    public void toBytes_bitsOffset_6() {
        byte[] result = ByteUtil.toBytes(1, 6, 12,
                toByte("11111111"),
                toByte("11111101"),
                toByte("10111100"),
                toByte("10111111"));

        assertEquals(toBinaryString(toByte("00000110"), toByte("11110010")), toBinaryString(result));
    }

    private String toBinaryString(byte... data) {
        StringBuilder binaryStr = new StringBuilder();
        String value = Integer.toBinaryString(data[0]);
        if (value.length() > 8) value = value.substring(value.length() - 8);
        else if (value.length() < 8) value = String.format("%8s", value).replace(" ", "0");
        binaryStr.append(value);
        for (int i = 1; i < data.length; i++) {
            value = Integer.toBinaryString(data[i]);
            if (value.length() > 8) value = value.substring(value.length() - 8);
            else if (value.length() < 8) value = String.format("%8s", value).replace(" ", "0");
            binaryStr.append(" ").append(value);
        }

        return binaryStr.toString();
    }


    private String toString(byte[] data) {
        return Arrays.toString(data);
    }

    private byte toByte(String binary) {
        return (byte) Integer.parseInt(binary, 2);
    }
}

1 Ответ

2 голосов
/ 14 июля 2019

Пока у меня есть [...] byte[] data = new byte[bytesCount];

К сожалению, этот подход будет работать только в том случае, если смещение вашего бита кратно 8. Во всех других случаях вы должны делить каждый байт, который вы намереваетесь скопировать. На следующем рисунке показано, как разделить каждый байт и куда поместить разделенные части.

MSB = старший значащий бит
LSB = младший значащий бит

Algorithm illustrated

Реализация алгоритма, показанного выше, немного сложна из-за множества угловых случаев. Следующая реализация проходит все ваши тесты и все мои тесты. Я использовал много переменных, чтобы дать всем вычислениям осмысленные имена в надежде, что им будет легче следовать. Вы можете сократить реализацию, исключив некоторые из этих переменных и рассчитав некоторые значения на месте.

Я позволил себе переименовать вашу функцию от toBytes до bitSubstring. Прежнее имя toBytes казалось не совсем подходящим для метода, который уже принимает байты в качестве входных данных. 

public static byte[] bitSubstring(int byteOffset, int bitOffset,
                                  int lengthInBits, byte... source) {
    return bitSubstring(8 * byteOffset + bitOffset, lengthInBits, source);
}


public static byte[] bitSubstring(int startBit, int lengthInBits,
                                  byte... source) {
    assert startBit >= 0 && startBit < 8 * source.length;
    assert lengthInBits >= 0 && startBit + lengthInBits <= 8 * source.length;

    int lengthInBytes = (int) Math.ceil(lengthInBits / 8.0);
    byte[] target = new byte[lengthInBytes];
    int startByte = startBit / 8;
    int endBitExclusive = startBit + lengthInBits;
    int endByteExclusive = (int) Math.ceil(endBitExclusive / 8.0);
    int sourceBytesToRead = endByteExclusive - startByte;
    int lowerPartSize = 8 * endByteExclusive - endBitExclusive;
    int shiftLowerUp = (8 - lowerPartSize);
    int shiftUpperDown = lowerPartSize;
    int lastSrc = 0;
    if (sourceBytesToRead > lengthInBytes) {
        lastSrc = source[startByte] & 0xFF;
        startByte++;
    }
    for (int targetByte = 0; targetByte < target.length; ++targetByte) {
        int curSrc = source[startByte + targetByte] & 0xFF;
        target[targetByte] |= (lastSrc << shiftLowerUp)
                            | (curSrc >>> shiftUpperDown);
        lastSrc = curSrc;
    }
    int overhang = 8 * lengthInBytes - lengthInBits;
    if (overhang > 0) {
        target[0] &= 0xFF >>> overhang;
    }
    return target;
}

Вышеприведенный алгоритм должен быть довольно быстрым. Однако, если вас интересуют только размер реализации и удобочитаемость, лучше использовать способ, в котором вы копируете по крупицам. 

public static byte[] bitSubstringSlow(int startBitSource, int lengthInBits,
                                      byte... source) {
    byte[] target = new byte[(int) Math.ceil(lengthInBits / 8.0)];
    int startBitTarget = (8 - lengthInBits % 8) % 8;
    for (int i = 0; i < lengthInBits; ++i) {
        setBit(target, startBitTarget + i, getBit(source, startBitSource + i));
    }
    return target;
}

public static int getBit(byte[] source, int bitIdx) {
    return (source[bitIdx / 8] >>> (7 - bitIdx % 8)) & 1;
}

public static void setBit(byte[] target, int bitIdx, int bitValue) {
    int block = bitIdx / 8;
    int shift = 7 - bitIdx % 8;
    target[block] &= ~(1 << shift);
    target[block] |= bitValue << shift;
}

... или менее многоразового использования, но еще короче: 

public static byte[] bitSubstringSlow2(int startBitSource, int lengthInBits,
                                       byte... source) {
    byte[] target = new byte[(int) Math.ceil(lengthInBits / 8.0)];
    int startBitTarget = (8 - lengthInBits % 8) % 8;
    for (int i = 0; i < lengthInBits; ++i) {
        int srcIdx = startBitSource + i;
        int tgtIdx = startBitTarget + i;
        target[tgtIdx / 8] |= ((source[srcIdx / 8] >>> (7 - srcIdx % 8)) & 1)
                              << (7 - tgtIdx % 8);
    }
    return target;
}
...