Bit packing best algorithm

[greka]

Во, народ, интересная задачка - паковка бит-стримов:

in general: есть входной массив Input данных (скажем, массив байтов (1 байт == 8 бит))

есть выходной массив Output данных (скажем, WORD-ов. 1 WORD == 2 Bytes == 16 bits).

Во входном массиве Input данные содержатся тока в первых "К" битах, остальные биты содержат мусор.

Надо эти ценные для нас биты упаковать в выходной массив Output.

Смысл паковки - все ценные биты из массива Input биты ложатся в ряд друг за другом.


Итак.....

[greka]

да, кстати: распаковка тож должна быть написана.
а то однобоко получится

[z0mbie]

vot primerno tak(poka ne proveryal,mozhet est' oshibki)

 
#include <windows.h> 
#include <math.h>

BOOL GetBit(BYTE bitfield,int bitn){return (bitfield&(int)pow(2,bitn))?1:0;}

void SetBit(WORD * bitfield,int bitn,BOOL value){
if(value) *bitfield|=(int)pow(2,bitn);
 else *bitfield&=(int)(pow(2,sizeof(int)*8)-pow(2,bitn));
}
   
BYTE in[]={....}   ;
UINT k=5;   
   
int main(){

BOOL val;
int bn=0;
BYTE* pIn=in;
WORD* pOut=new WORD[k*sizeof(in)/sizeof(WORD)];

for(int i=0;i<sizeof(in);i++){
	for(int j=0;j<k;j++){
		val=GetBit(*pIn,j);
		SetBit(pOut,bn++,val);
		if(bn>=sizeof(WORD)){
			pOut+=sizeof(WORD);	
			bn=0;
		}
	}
	pIn+=sizeof(BYTE);		
 }           
  
  
}

[acid]

eto ty uzhe do CodeBook-ov doshel?

[z0mbie]

Originally posted by acid:
eto ty uzhe do CodeBook-ov doshel?

eto tы mne ? :]

[greka]

ne, eto on mne..

eto vezde est', Acid jan . , ne toka v 723-m..

zombie, eto oooooooochen' medlennyj algoritm.

xotja by potomu, chto vmesto "pow(2, x)" mojno bylo by primenit'
"1<<x"


dalee..GetBit izvlekaet po odnomu bitu ?

neeeeee, eto katastrofa dlja processora.

predstav': v sekundu tebe prixodit 10 (ili 100) Megabit - eto ne primer s Luny, eto prostaja setevaja karta.

[SMoKE]

ete chisht em haskacel...
const MAX_ARRAY=10;
type DataArray=ARRAY [1..MAX_ARRAY] OF BYTE;

Procedure GetArray(IAataArray; var OAataArray; BitsNum:integer; var OASize:integer);
var TmpOAataArray;
begin
for i:=1 to (BitsNum div 8) do
TmpOA[i]:=IA[i];
TmpOA[(BitsNum div 8)+1]:=(IA[(BitsNum div 8)+1] and (256-(1 shl (8-(BitsNum mod 8))))) shr (8-(BitsNum mod 8));
OASize:=(BitsNum div 8)+1;
OA:=TmpOA;
end;

nayum enq te qani byte e stacvum K biteric (K div 8), heto mnacac (K mod 8) bitern el hajord byte-ic filtracia enq anum.
patasxan@ stacvuma byte-erov, bayc shat hesh karelia da poxel word-eri...
DW[i]:=(DB[i] shl 8) + DB[i+1];

[Aram Hambardzumyan]

Originally posted by Greco El:
zombie, eto oooooooochen' medlennyj algoritm.

xotja by potomu, chto vmesto "pow(2, x)" mojno bylo by primenit'
"1<<x"


dalee..GetBit izvlekaet po odnomu bitu ?

neeeeee, eto katastrofa dlja processora.

а сколько времени еще компиляция ентого windows.h займет...

[Dark Abyss of Yerevan]

Не знаю правильно ли я все понял, но тем не менее..

 
 deleted by author.

по моему так.. memcpy работает так же быстро как и rep movsb/movsw
(memcpy по моему и есть movsw или movsw+movsb, в зависимости от четности
длины копируемого участка), а использование shl/shr и вовсе делает прогу
очень быстрой. Можно и на АСМ е написать.

Greco, clarify the task plz.

[greka]

неееееее, народ, не пойдет.

так, поясню задачу:

имеем 1 елемент (далее: "Е"), длиной в 1 байт.
в этом байте нам нужны не все 8 бит, а всего лишь первые 3 бита.

далее.

таких вот элементов "Е" у нас целый массив, который называется "Input".

Этот "Input"-массив нужно преобразовать в выходной массив "Output" таким образом, чтоб в выходном массиве были ТОЛЬКО "нужные" нам биты из массива "Input".

То есть массив "Input":
xxxxxBBB xxxxxBBB xxxxxBBB xxxxxBBB ...
должен превратиться в:
"Output":
BBBBBBBBBBBB ...

P.S. будьте гуманны, пишите комментарии к коду своему

[greka]

Dark Abyss of Yerevan: думаю, моего уточнения достаточно.

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

А использование "gugush := (BitsNum div 8);"
сделало бы код гораздо читабельнее - оно встречается там несколько раз.....

[Dark Abyss of Yerevan]

ок, понял. будет.

Originally posted by Greco El:
Dark Abyss of Yerevan: думаю, моего уточнения достаточно.

[Dark Abyss of Yerevan]

бррррр.... ужас. Так вот, если K=1,2,4 или 8 - задача решается очень просто.
Например, если k=4,

	mov ah, input[0]; 
	mov al, input[1];
	mov cl,4; 
	shl al,cl; 
	shl ax,cl;
	mov output[0],ah;

если k=3,5 или 7 этот метод не проходит.

Я хотел на ассемблере написать, используя RCR/RCL (выполняется за 2 такта), но потом
почему то передумал. А зря.

Короче, не знаю заработает ли ЭТО, но зато точно знаю что я иду спать

#include <stdio.h>

typedef unsigned char BYTE;

// input_size (IN) must be given in bytes
// output_size (OUT) is given in bits.

BYTE * bitpack(BYTE* input, size_t input_size, size_t *output_size, BYTE k){

	unsigned int l;				// length of the output buffer in bytes
	BYTE * output = new BYTE(l=(7+input_size*k)>>3);
	*output_size=input_size*k;
	BYTE r,t,k1=k;				// temp variables. save k (k1 is fixed)

	for (unsigned int i=0;i<l;i++){		// do for each byte of the output buffer
		t=*input;			// take the first byte from the input
		t<<=(8-k);			// shift left (8-k) bits
	
		r=k;						
		while (r<=8-k1){		// if it is possible to add new bit chunk
						// to the byte that is being processed, do it.
			t|=(BYTE)((*++input)<<(8-k1))>>r;
			r+=k1;
		}

		if (r != 8){			// some bits are still unprocessed, so add them
						// to the current byte(t), and arrange k
			t|=(BYTE)((*(input+1))<<(8-k1))>>r;
			k-=8-r;
		}
		*output=t;			// write processed byte
		input++;
		output++;

	}					// end for

	return output;
}



void main(){

	BYTE inp[]={100,100,100};
	BYTE *out;
	size_t out_s;
	out=bitpack(inp,3,&out_s,5);


}

[greka]

Уважаемый Dark Abyss of Yerevan, позвольте прокомментировать код завтра - я тож хочу спать

как я понял, ты пакуешь биты, загоняя в левый угол Output-массива - так, как и требуется.

как помнишь,нам нужны ПЕРВЫЕ "k" битов каждого Input-элемента. "первые биты" == "младшие биты" (или это еще одно уточнение с моей стороны?), LSBs

не успел сегодня посмотреть, но на первый взгляд:

		if (r != 8){			// some bits are still unprocessed, so add them
						// to the current byte(t), and arrange k
note1:			t|=(BYTE)((*(input+1))<<(8-k1))>>r;
			k-=8-r;
		}

неточность в "note1": во-первых, ты используешь "k1" для сдвигов, а прибавляешь "k" - кажись, тебе очень хотелось спать.

Ладно, мне тож пора - до связи и успехов с битами !!

[Tumanyan]

Vot i moi 2c (Tol'ko sil'no ne pinajte, ya poka eshe do konce vse ne obdumal. Tak chto esli chto netak - izvinite):

Dumayu, v dannom algoritme spaseniem budet ispol'zovanie zaranee raschitannoj tablicy s
vyxodnymi znacheniyami, sootvetstvuyushimi vxodnym.
Krome togo, nado uchityvat' sdvijku vydernutyx bitov. T.e. poluchaem dvuxmernuyu tablicu, odno izmerenie kotoroj - znacheniya vxoda, drugoe - sdvijki (0 - 7). V uzlax tablicy sidyat znacheniya, kotorye doljny byt' peredanny na vyxod.
Pravda, tablica poluchaetsya bol'shaya. Priblizitel'no - 256 * 9 bytes, dlya sluchaya, kogda schityvaem so vxoda bajty. Esli je popytat'sya sdelat' algorithm eshe bystree (maximum - kogda za odnu iteraciyu obrabatyvaetsya kol-vo bayt ekvivalentnoe razryadnosti processora), tablica sootvetstvenno vyrastet.

Koroche govorya, vot source, kotoryj ya nabrosal. Daje ne uspel polnostyu proverit' (gonyal na korotkix posledovatel'nostyax. Ne bylo vremeni xoroshen'ko potestirovat).

S udovol'stviem vyslushayu zamechaniya po algorithmu.

void set_pattern(char chBegin, char chLen);
void init_table();
void process(unsigned char *in, unsigned long isize, unsigned char *out, unsigned long osize);
char magic(unsigned char pos, unsigned char val);

int main(int argc, char* argv[])
{
	unsigned char out[128];
	unsigned char in[128];

	/*
		Init internal constants. Main goal is to
		create input mask. Mask is stored in g_Mask
	*/
	set_pattern(3, 3);

	/*
		Create magic table.
	*/
	init_table();

	/* 
		Fill input vector with sample data.
		We're putting numbers in range 0...8.
		That is, because we're trying to extract 3 bits, 
		starting from position 3. I.e. input numbers are
		00000000
		00000100
		00001000
		00001100
		00010000
		.........
		.........
		e.t.c
	*/

	for (int i = 0; i < 8; i++)
		in[i] = i << 2;

	/*
		Process input sequence
	*/

	process(in, 8, out, sizeof(out)/sizeof(unsigned char));

	return 0;
}

/*
	Every position, which needs to be extracted
	in input sequence, contains 1-bit in mask.
*/
void set_pattern(char chBegin, char chLen)
{
	unsigned char ch;
	unsigned short sh;
	
	sh = 1;
	ch = 0;

	/*
		Determine lowest 1-bit.
		For case, when 3 bits will be extracted
		starting from position 3, it will be

		00000100
	*/
	sh = sh << (8 - chBegin - chLen);

	for (unsigned char i = chBegin + chLen; i > chBegin; i--)
	{
		/*
			Move one position left and add to accumulated value.
		*/

		ch += sh;
		sh = sh << 1;
	}

	g_Mask = ch;
	g_chBegin = chBegin;
	g_chLen = chLen;
}

/*
	Initialize magic table. 
	
	Here is a basic idea of my algorithm:

	First of all, note, that input could be a
	number 0...255.
	Necessary bits could be easely extracted using
	bit-mask.
	The problem is, that algorithm should place extracted
	bits to dynamically calculated position in output byte.
	Simplest solution is to use shifts for position adjustment.
	But it is very slow, because requires bit manipulation.

	Another approach is to calculate output values for all possible 
	inputs and shifts.
	Result of calculation could be stored in the body of program
	as an array of constants. (Actually, that's what crc does).
	In this case, all we should do dynamically, is to copy
	values from table to output.

	Note, that this algorithm could be faster in case of larger table.

	Init table creates magic table based on parameters set by
	setpattern function.
	
*/
void init_table()
{
	char chNorm = 8 - g_chBegin - g_chLen;
	char posMax = 8 - g_chLen;
	char chShift = 0;

	for (int i = 0; i < 256; i++)
		for (unsigned char pos = 0; pos < 7 + g_chLen; pos++)
			g_Table[i][pos] = magic(pos, i);
}

/*
	Calculate the value of magic table entry.
	Each entry correcponds to particular value in particular position.

	Table looks like:

					Values
			000	001	010	011	100	101	110	111
	S	0	
	h	1	
	i	2	
	f	3	
	t	4	
	s	5	
		6	
		7	
		8	
		9	

*/

char magic(unsigned char pos, unsigned char val)
{
	char chNorm;
	char chShift;

	chNorm = 8 - g_chBegin - g_chLen;

	chShift = 7 - pos;

	val = val >> chNorm;

	if (chShift < 0)
		val = val >> (-chShift);
	else
		val = val << chShift;

	return val;
}

void process(unsigned char *in, unsigned long isize, unsigned char *out, unsigned long osize)
{
	char pos;
	int j;

	/*
		Note, that position is tracked by last significant bit.
		That's why, initial value is g_chLen - 1
	*/
	pos = g_chLen - 1;
	
	j = 0;
	out[j] = 0;

	for (unsigned long i = 0; i < isize; i++)
	{
		/*
			Fill current byte
		*/
		out[j] = out[j] | g_Table[in[i]][pos];

		/*
			Move one step forward.
		*/
		pos += g_chLen;

		/*
			pos > 7 means, that tail of current input piece is
			out ouf current output byte's boundaries.
			This is special code for borders processing.
		*/
		if (pos > 7)
		{
			i++;
			/*
				Update taail of current output byte
			*/
			out[j] = out[j] | g_Table[in[i]][pos];
			/*
				Calculate position within next byte
			*/
			pos -= 8;
			/*
				Copy remaining piece
			*/
			out[++j] = g_Table[in[i]][pos];
			/*
				Move forward
			*/
			pos += g_chLen;
		}
	}
}