Побитовые операции над котятами

О чем статья

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

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

Вы узнаете как запаковать JSON:
{ "color": "ginger", "age": 3, "tailStripes": true, "backStripes": true, "faceStripes": true } в число 807

Задача

Давайте представим, что мы работаем над игрой — симулятором сильных независимых женщин, — и получаем от отдела дизайна задание по добавлению котят в игру. На момент постановки задачи котята бывают 5 цветов, но в дальнейшем их может стать больше (не больше 10).

Кроме разных цветов у котят могут появляться полоски на мордашках, хвостиках и спинках:

Помимо цвета и полосок котята могут взрослеть, но не могут быть старше 6 месяцев. Возраст отражается в длине их тушек:

Реализация

Начнем с того, что опишем простой класс Kitten с полями под необходимые данные: цвет, полоски, возраст:

class Kitten 
{
    constructor(color, age, tailStripes, backStripes, faceStripes) {
        this.color = color;
        this.age   = age;
        this.tailStripes = tailStripes;
        this.backStripes = backStripes;
        this.faceStripes = faceStripes;
    }
}

Так как мы работаем над уже «существующей» игрой, попросим движок вывести на экран несколько котят, чтобы убедиться в правильности выполнения задачи:

const colors = ["devil","black","white","gray","ginger"];

for(let i = 0; i < 5; i++) {
    kitten_render(new Kitten(
        colors[i],  // цвета от Devil до Ginger
        i + 2,      // возраст от 2 до 6
        i % 2 != 0, // каждый второй котенок без полосок на хвосте
        i % 3 == 0, // каждый третий котенок с полосками на спинке
        i % 2 == 0  // каждый второй котенок с полосками на мордочке
    ));
}

Запускаем код и видим, что задача выполнена, и можно идти отдыхать.

Оптимизация

Но на следующий же день из отдела QA\техлида\сторонника оптимизации, приходит задача в таск-менеджер: Оптимизировать загрузку комнаты. В подробном описании говорится, что появился заметный лаг при входе в комнату сильной независимой женщины.

При изучении проблемы становится понятно, что время загрузки увеличилось пропорционально времени загрузки JSON данных по сети, так как в среднем в комнате по 40-50 котят, и объекты Kitten занимают много места:

{
    "color": "ginger",
    "age": 3,
    "tailStripes": true,
    "backStripes": true,
    "faceStripes": true
}

Количество котят уменьшать нельзя, нужно оптимизировать формат сохранения. Можно сократить названия ключей, но есть вариант лучше: сохранять новорожденного дьявольского котенка без полосок как 0, а новорожденного черного котенка с полосками на хвостике как 1 и т.д. со всеми вариантами котят. Чтобы получать из объекта Kitten целочисленное значение и не составлять таблицу всех возможных котят, мы воспользуемся битовыми операциями.

Упаковка данных

Для эффективной запаковки данных мы будем использовать битовые операции над целочисленными значениями. Чтобы понять процесс, давайте разберемся, что такое целочисленное значение для компьютера. Все данные компьютер воспринимает как набор двоичных значений: 0 и 1, а целочисленные значения как совокупность 32-х двоичных значений (актуально для js и Int32 в строго типизированных языках).
Приведу табличку значений от 0 до 8 и их двоичное представление:

0000 0000 0000 0000 0000 0000 0000 0000 0
0000 0000 0000 0000 0000 0000 0000 0001 1
0000 0000 0000 0000 0000 0000 0000 0010 2
0000 0000 0000 0000 0000 0000 0000 0011 3
0000 0000 0000 0000 0000 0000 0000 0100 4
0000 0000 0000 0000 0000 0000 0000 0101 5
0000 0000 0000 0000 0000 0000 0000 0110 6
0000 0000 0000 0000 0000 0000 0000 0111 7
0000 0000 0000 0000 0000 0000 0000 1000 8

И отдельно для значения 16:

0000 0000 0000 0000 0000 0000 0001 0000 16

Прошу вас обратить особое внимание на двоичное представление значений 1, 2, 4, 8 и 16. Их объединяет особенность: все двоичные значения, кроме одного, равны 0. Чем это удобно для нас? Мы можем сказать, что первый бит — это полоски на хвостике, второй — на спинке, а третий - мордашка. Тогда для котенка с полосками на спинке и хвостике первый и второй бит будут равны 1, а третий - 0. Получим: 0000 0011 или 3 в десятичном представлении. Давайте посмотрим в виде таблицы:

Место
Хвостик	0	1	0
Cпинка	0	1	1
Мордашка	1	1	0
Итого (бинарно)	`100`	`111`	`010`
Итого (десятично)	4	7	2

Давайте начнем записывать формат запаковки в комментариях к объекту Kitten:

 ХХХ
 ││└ Tail stripes flag
 │└─ Back stripes flag
 └── Face stripes flag

Используя полученные знания, уже можно сократить объем данных до: { "color": "ginger", "age":3, "stripes": 3 }, это заметно сократит объем передаваемых данных, но наша цель — одно целочисленное значение.

Цвет в отличие от полосок может быть только один, то есть дьявольско-рыжего котенка в игре быть не может, а так же цветов не больше 10. Так как 9 (считаем вместе с 0) в двоичной системе это: 1001, для хранения нам нужно 4 бита. Учтивая, что 1111 - это 15, у нас будет запас на 6 дополнительных цветов.

Так как котята в нашем случае не могут быть старше 6 месяцев, для записи возраста хватит трех битов (111 - это 7). Учитывая цвет и возраст, дополняем наш формат запаковки данных:

 ZZZYYYYХХХ                      10 bits
 └┬┘└─┬┘││└ Tail stripes flag     1 bit
  │   │ │└─ Face stripes flag     1 bit
  │   │ └── Back stripes flag     1 bit
  │   └──── Color data            4 bits
  └──────── Age data              3 bit

Поэкспериментируем со значениями. В какулятор ниже попробуйте получить значение для котенка с полосками на хвостике и мордашке, серого цвета и 4-х месяцев от роду:
101 – флаги для полосок
0011 – цвет котенка (3)
100 – возраст котенка (4)

Запишите последовательно все значения в калькулятор (1000011101):

Получите 541 в десятичном представлении. То есть для сохранения указанного выше котенка нужно будет записать в JSON 541, а не: {"color": "gray", "age":4, "tailStripes":true, "backStripes":true, "faceStripes":false }.

Запись значений в бинарные данные

В ручную у нас вышло получить 541 из котенка, давайте теперь разберемся как это сделать в коде. Самое замечательное, что битовые операции (bitwise) во всех мне известных языках имеют одинаковый синтаксис, и пример на JS можно использовать в C#, Java, C++.

Единственный (pascal не в счет) известный мне синтаксис битовых операций выглядит следующим образом (что он делает и как - разберем дальше):

a & b    // Побитовое И 
a | b    // Побитовое ИЛИ
a ^ b    // Побитовое НЕ И (исключающее ИЛИ)
~a       // Побитовое НЕ 
a << b   // Сдвиг влево 
a >> b   // Сдвиг вправо

Для записи значений со смещением воспользуемся сдвигом.

Побитовые сдвиги

Сдвиги бывают в два направления: влево и вправо. Работают очень просто: берут двоичное представление и двигают биты в указанное направление, отбрасывая биты, выходящие за границы:

    |                                       | borders
XXXX 0000 0000 0000 0000 0000 0000 0000 0001 XXXX original is ONE
XXXX 0000 0000 0000 0000 0000 0000 0000 0000 1XXX shift right (1 is outside)
XXXX 0000 0000 0000 0000 0000 0000 0000 0000 XXXX final is ZERO

XXXX 0000 0000 0000 0000 0000 0000 0000 0001 XXXX original is ONE
XXXX 0000 0000 0000 0000 0000 0000 0000 0010 XXXX shift left
XXXX 0000 0000 0000 0000 0000 0000 0000 0010 XXXX final is TWO

Попробуйте поставить несколько бит в целочисленное значение и подвигать:

Когда я сказал, что мы будем записывать значения со смещением, я лукавил, мы будем их писать в начало, а после сдвигать в отведенное для них место. Например, цвет, согласно нашей схеме, должен находиться в данных со сдвигом на три бита влево, сразу после флагов полосок. Давайте попробуем сдвинуть серый цвет (3 или 011)

const a = 3;      // 00000011
const b = a << 3; // 00011000

Аналогично с цветом, получим значения со сдвигом для всех данных о котенке:


const KITTEN_COLOR_CODES = {
    devil:      0,
    black:      1,
    white:      2,
    gray:       3,
    ginger:     4
};

const KITTEN_TAIL_OFFSET  = 0;
const KITTEN_FACE_OFFSET  = 1;
const KITTEN_BACK_OFFSET  = 2;
const KITTEN_COLOR_OFFSET = 3;
const KITTEN_AGE_OFFSET   = 7;

class Kitten 
{
    // CONSTRUCTOR

    pack() {
        const tailData  = this.tailStripes               << KITTEN_TAIL_OFFSET;
        const faceData  = this.faceStripes               << KITTEN_FACE_OFFSET; 
        const backData  = this.backStripes               << KITTEN_BACK_OFFSET;
        const ageData   = this.age                       << KITTEN_AGE_OFFSET;
        const colorData = KITTEN_COLOR_CODES[this.color] << KITTEN_COLOR_OFFSET;

        // should return packed data of instance
        return 0;
    }
}

Теперь предстоит полученные бинарные данные склеить в одно, склеивать данные можно оператором ИЛИ.

Побитовое ИЛИ

Чтобы понять побитовые ИЛИ, И и НЕ И, проще всего представить двоичные значения как массивы значений Boolean. А использование битовых операторов воспринимать как операции сравнения (&&, ||, !=) логических типов (boolean) и запись результатов в третий массив.

Давайте разберемся на примере:

У нас есть значения 0110 (6) и 0011 (3), но мы представляем их как [false, true, true, false] и [false, false, true, true]. В цикле for(let i = 0; i < 4; i++) сравним left[i] и right[i] оператором ||, а результат запишем в result[i].

const left  = [false, true, true, false];
const right = [false, false, true, true];
let result  = [];

for(let i = 0; i < 4; i++) {
    result[i] = left[i] || right[i];
}

Надеюсь, что табличка ниже поможет разобраться.

┌──────────────────┬───────────────────┬───────────────────┐
│    Значения A    │    Значения Б     │ Результат при ИЛИ │
│  bin      bool   │  bin      bool    │  bin      bool    │
├───────┼──────────┼───────┼───────────┼───────┼───────────┤
│   0   │   false  │   0   │   false   │   0   │   false   │
│   1   │   true   │   0   │   false   │   1   │   true    │
│   1   │   true   │   1   │   true    │   1   │   true    │
│   0   │   false  │   1   │   true    │   1   │   true    │
└───────┴──────────┴───────┴───────────┴───────┴───────────┘

Ну и результат вместе:

Как видите оператор ИЛИ «склеивает» два значения в одно, а это именно то, что нам нужно в задаче с котятами. Просто надо взять и побитово склеить все значения и вернуть как результат метода pack():

pack() {
    const tailData  = this.tailStripes               << KITTEN_TAIL_OFFSET;
    const faceData  = this.faceStripes               << KITTEN_FACE_OFFSET; 
    const backData  = this.backStripes               << KITTEN_BACK_OFFSET;
    const ageData   = this.age                       << KITTEN_AGE_OFFSET;
    const colorData = KITTEN_COLOR_CODES[this.color] << KITTEN_COLOR_OFFSET;

    return tailData | backData | faceData | colorData | ageData;
}

Выведем на экран вместе со спрайтом котенка его запакованное значение:

Как видим у каждого котенка запакованное значение уникально и теперь можно сохранять котят как массив целочисленных значений, что существенно сократит размер JSON данных, но нужно научиться их распаковывать.

Распаковка данных

Теперь от сервера мы получаем информацию о котенке как целочисленное значение. Например, 423 для трехмесячного рыжего котенка с полосками на хвостике, спинке и мордашке.

В двоичном представлении 423 это: 0000 0000 0000 0000 0000 0000 1110 0111. Нас же интересуют только последние 10 бит, где 0-2 - полоски, 3-6 - цвет, а 7-9 - возраст. В случае 423, полоски — это 111, цвет — 0100 (4), возраст — 0011 (3).

Чтобы вычленить нужные нам биты, будем использовать оператор И и уже знакомые нам сдвиги.

Оператор И

Как мы уже видели выше, побитовые И, ИЛИ и НЕ И можно воспринимать как привычное сравнение булевых значений в цикле, но в отличие от ИЛИ, для И мы бы использовали оператор &&. Другими словами, result[i] == left[i] && right[i]; и принимает true только когда оба значения true.

Для извлечения части битов из данных применим оператор И вместе с маской явно указывающей на интересующие данные. В случае с цветом, применение битового оператора & для двоичного значения котенка 423 (011 0100 111) и маски цвета 120 (000 1111 000) вернет 000 0100 000. Осталось только сдвинуть вправо полученное значение и мы видим, что это интересующий нас рыжий (ginger) цвет, или 4 в десятичном представлении.

Создавать битовые можно следующей операцией:
((1 << bitCount) - 1) << offset

Как это работает: маска 1111 0000 — это 1111 со сдвигом влево на 4 бита, а 1111 — это 15 или 16 - 1. 16 — это степерь двойки или 1 << 4. Таким образом искомая маска — это ((1 << 4) - 1) << 4.

Подготовим необходимые для извлечения данных маски:

function bitMask(bitCount, offset) {
    return ((1 << bitCount) - 1) << offset;
}

const KITTEN_TAIL_MASK    = bitMask(1, KITTEN_TAIL_OFFSET);
const KITTEN_FACE_MASK    = bitMask(1, KITTEN_FACE_OFFSET);
const KITTEN_BACK_MASK    = bitMask(1, KITTEN_BACK_OFFSET);
const KITTEN_COLOR_MASK   = bitMask(4, KITTEN_COLOR_OFFSET);
const KITTEN_AGE_MASK     = bitMask(3, KITTEN_AGE_OFFSET);

Теперь когда у нас есть сдвиги и маски, мы можем получить из данных интересующую нас информацию, например, возраст: (data & KITTEN_AGE_MASK) >> KITTEN_AGE_OFFSET, но чтобы не писать всю конструкцию для каждого поля данных, сделаем вспомогательную функцию bitData:

function bitData(value, mask, offset) {
    return (value & mask) >> offset;
}

В реальном проекте советую создать для методов bitMask, bitData отдельный модуль и использовать его методы везде где они требуются.

Для разработки на Unity вы можете найти все методы работы с бинарными данными в моей библиотеке Uniful, что доступна на github

Создадим в классе Kitten метод для распаковки значений


const KITTEN_COLOR_NAMES = [
    "devil",
    "black",
    "white",
    "gray",
    "ginger"     
];

class Kitten 
{
    // constructor

    // pack()


    static unpack(data) {
        let instance = new Kitten();

        instance.tailStripes =            !!bitData(data, KITTEN_TAIL_MASK,  KITTEN_TAIL_OFFSET);
        instance.faceStripes =            !!bitData(data, KITTEN_FACE_MASK,  KITTEN_FACE_OFFSET);
        instance.backStripes =            !!bitData(data, KITTEN_BACK_MASK,  KITTEN_BACK_OFFSET);
        instance.color = KITTEN_COLOR_NAMES[bitData(data, KITTEN_COLOR_MASK, KITTEN_COLOR_OFFSET)];
        instance.age =                      bitData(data, KITTEN_AGE_MASK,   KITTEN_AGE_OFFSET);

        return instance;
    }
}

Теперь наша система готова! Можем проверить вывод пяти котят: [791, 540, 135, 288, 0]

Концепция изменилась

Раз уж у нас статья максимально приближенна к реальности, то без заветной фразы «концепция поменялась» она будет неполной.

Гордые за проделанную работу мы отмечаем задачу в таск-менеджере как завершенную, но видим, что появилась новая: Изменения котят, а тело задачи говорит:

Исследования показали, что сильные независимые женщины предпочитают ограниченную палитру цветов, но любят сочетания цветов!

Нужно сделать так, чтобы котята могли быть двух-цветными: один цвет для тела, второй для мордочки.

Новых цветов добавлять не нужно!

Изменение данных

Сценарий внесения изменений у нас будет таким же как и реализация первой версии:

Подготовим объект со всеми полями для данных
Составим схему хранения данных
Напишем реализацию для упаковки и распаковки данных

Добавим в класс Kitten поле faceColor:

class Kitten 
{
    constructor(color, age, tailStripes, backStripes, faceStripes, faceColor) {
        this.color = color;
        this.faceColor = faceColor;
        this.age = age;        
        this.tailStripes = tailStripes;
        this.backStripes = backStripes;
        this.faceStripes = faceStripes;
    }
}

Так уж получилось, что в рамках статьи мы инженеры по упаковке данных и магическим образом движок игры уже умеет рисовать разноцветных котят. Поэтому сразу перейдем к обновлению схемы.

Что изменилось в данных? Во первах, цветов теперь меньше. То есть мы можем хранить цвет в 3-х битах, вместо 4-х изначально выделенных под увеличение палитры. Во вторых, нужно выделить еще 3 бита под дополнительный цвет. Обновим нашу схему запаковки данных:

 FFFZZZYYYXХХ                      12 bits
 └┬┘└┬┘└┬┘││└ Tail stripes flag     1 bit
  │  │  │ │└─ Face stripes flag     1 bit
  │  │  │ └── Back stripes flag     1 bit
  │  │  └──── Color data            3 bits
  │  └─────── Age data              3 bits
  └────────── Face color data       3 bits

Изменим константы KITTEN_COLOR_MASK, KITTEN_AGE_OFFSET и добавим две новые для хранения сдвига цвета мордашек: KITTEN_FCOLOR_OFFSET и KITTEN_FCOLOR_MASK:

const KITTEN_AGE_OFFSET    = 6;
const KITTEN_FCOLOR_OFFSET = 9;

const KITTEN_COLOR_MASK  = bitMask(3, KITTEN_COLOR_OFFSET);
const KITTEN_FCOLOR_MASK = bitMask(3, KITTEN_FCOLOR_OFFSET);

По аналогии с основным цветом, добавим упаковку и распаковку цвета мордашки:

pack() {

    const tailData   = this.tailStripes                   << KITTEN_TAIL_OFFSET;
    const faceData   = this.faceStripes                   << KITTEN_FACE_OFFSET; 
    const backData   = this.backStripes                   << KITTEN_BACK_OFFSET;
    const ageData    = this.age                           << KITTEN_AGE_OFFSET;
    const colorData  = KITTEN_COLOR_CODES[this.color]     << KITTEN_COLOR_OFFSET;

    // FACE COLOR
    const fcolorData = KITTEN_COLOR_CODES[this.faceColor] << KITTEN_FCOLOR_OFFSET;

    return tailData | backData | faceData | colorData | ageData | fcolorData;
}

static unpack(data) {
    let instance = new Kitten();

    instance.tailStripes =                !!bitData(data, KITTEN_TAIL_MASK,   KITTEN_TAIL_OFFSET);
    instance.faceStripes =                !!bitData(data, KITTEN_FACE_MASK,   KITTEN_FACE_OFFSET);
    instance.backStripes =                !!bitData(data, KITTEN_BACK_MASK,   KITTEN_BACK_OFFSET);
    instance.color     = KITTEN_COLOR_NAMES[bitData(data, KITTEN_COLOR_MASK,  KITTEN_COLOR_OFFSET)];
    instance.age =                          bitData(data, KITTEN_AGE_MASK,    KITTEN_AGE_OFFSET);


    // FACE COLOR
    instance.faceColor = KITTEN_COLOR_NAMES[bitData(data, KITTEN_FCOLOR_MASK, KITTEN_FCOLOR_OFFSET)];

    return instance;
}

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

gamedev article unity javascript

2016-09-30

test