Упаковка данных полями переменной длины

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

Рассмотрим пример программы на упаковку и распаковку положительных целых переменных различной размерности char, short, int в байтовый массив.

Для того чтобы «вынести за скобки» часть программы, работающую с отдельными битами и их полями, и учитывая тот факт, что биты записываются и извлекаются только последовательно, разработаем две функции добавления putbit и выделения getbit очередного бита по заданному номеру. Он будет передаваться ссылкой на переменную - счетчик очередного бита, увеличиваемый при каждом вызове функции.

Функция getword, извлекающая последовательность битов числа младшими разрядами вперед, производит повторную сборку их в машинное слово заданной размерности с использованием операций сдвига и поразрядного ИЛИ.

Функция упаковки слова putword выделяет последовательность битов, начиная с младшего, использует операцию сдвига и вызывает функцию записи.

Последующие действия связаны уже с форматом представления данных - наличием управляющих полей и полей данных взаимосвязанной размерности. В них поразрядные операции могут вообще отсутствовать. Это видно на примере функций упаковки pack и распаковки unpack целых переменных различной размерности char, short, int: перед каждым числом размещаются 2 бита, определяющие размерность числа: 00 - конец последовательности, 01 - char, 10 - short, 11 - int. После них размещаются разряды самого числа.

//Листинг 12.4

#include <iostream>

using namespace std;

 

//Извлечение бита

// c[] - массив байтов, n - номер бита

long getbit(char c[], int &n) {

int nb = n/8; // Номер байта в массиве байтов

int ni = n%8; // Номер бита в байте

n++;

// Сдвинуть к младшему биту и выделить

return (c[nb]>>ni) & 1; }

 

//Запись бита

// c[] - массив байтов, n - номер бита

void putbit(char c[], int &n, int v)

{ int nb = n/8; // Номер байта в массиве байтов

int ni = n%8; // Номер бита в байте

n++;

c[nb]=c[nb] & ~(1 << ni) | ((v & 1) <<ni);}

 

//Извлечение слова заданной размерности

// c[] - массив байтов

//n - номер бита,

//с которого производится извлечение

//sz - количество битов в извлекаемом слове

unsigned getword(char c[], int &n, int sz)

{

unsigned v = 0;

for(int i = 0; i<sz; i++)

v|= getbit(c,n)<<i;

return v; }

//Упаковка слова заданной размерности

// c[] - массив байтов

//n - номер бита,

//с которого производится упаковывание

//sz - количество битов в упаковываемом слове

//v - число, которое упаковывается

void putword(char c[], int &n, int sz, int v)

{

//Пока количество битов не равно нулю

while(sz--!=0)

{ putbit(c, n, v&1);

v>>= 1;}

}

//Распаковка переменных различной размерности

void unpack(char c[])

{

int n = 0;

int vv;

while(1){

// Извлечение 2-разрядного кода

int mode=getword(c,n,2);

//Переключение no типу переменной

switch(mode){

case 0: return;

// 01 извлечь байт (char)

case 1: vv=getword(c,n,8); break;

// 10 извлечь short

case 2: vv=getword(c,n,16);break;

// 11 извлечь int

case 3: vv=getword(c,n, 32); break;

}

cout<<vv<<'\n';

}

}

//Упаковка переменных различной размерности

void pack(char c[])

{

int n=0;

long vv;

do {

cin>>vv;

// Запись 2-разрядного кода 00

if(vv==0) putword(c,n,2,0);

else

if (vv < 256) {

 

// Запись 2-разрядного кода 01

putword(c,n,2,1);

// Запись 8-разрядного кода числа

putword(c,n,8,vv);}

else

if (vv < 32768) {

// Запись 2-разрядного кода 10

putword(c,n,2,2);

//Запись 16-разрядного кода числа

putword(c,n,16,vv);}

else {

//Запись 2-разрядного кода 11

putword(c,n,2,3);

//Запись 32-разрядного кода числа

putword(c,n,32,vv);}

}

while (vv!=0);

}

 

int main(){

setlocale(LC_CTYPE,"Russian");

char kod[20];

cout<<"Упаковка переменных различной размерности в байтовый массив\n"

<<"Введите положительные числа (для окончания ввода нужно ввести 0):\n";

pack(kod);

cout<<"Распаковка переменных различной размерности из байтового массива\n";

unpack(kod);

return 0;

}

Результаты выполнения программы:

Упаковка переменных различной размерности в байтовый массив

Введите положительные числа (для окончания ввода нужно ввести 0):

Распаковка переменных различной размерности из байтового массива