Bit packing best algorithm

[greka]

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

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

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

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

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

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


Итак.....

[Tumanyan]

2 El Greco:
Kstati, zabyl sprosit', eto chto-to FIAD-noe?
Ne ATM li trafic raskodiruete?

Udachi,
Hovik

[acid]

U menja smutnye predchuvstvija chto eto svjazano s DSP

[Tumanyan]

Kstati, vot eshe odna myslishka poyavilas':
Etu zadachu mojno re****', primenyaya konechnye aftomaty.
Algoritm budet osonvan na tom, chto kajdoe vyxodnoe znachenie zavisit ot tekushego vxodnogo i ot sostoyaniya avtomata (t.e. predydushego (ix) znacheniya (ij) )
T.e., opyat' neobxodima tablica. Tol'ko na etot raz eto budet tablica perexodov, pokazyvayushaya, v kakoe sostoyanie perejdet i kakoj vyxod sgenerit algoritm, pri izvestnom vxodnom znachenii i izvestnom sostoyanii.
Nado, voobshe-to podumat', v kakom sluchae tablica poluchitsya men'she....

Kstati, vot eshe ideya vdogonku. V predydushem sluchae mojno primenit' special'nye struktury dlya xraneniya razrejennyx matric.
Poyasnyu mysl':
Dopustim, nado vydel'yat' 3 bita, nachinaya s pozicii 4.
V takom sluchae, kolichestvo real'no znachashix kombinacij v tablice budet 2^4 = 16. Vse ostal'noe - ballast. No ballast neobxodimyj - inache pridetsya primenyat' shift - y, t.e. vozvrashat'sya obratno k bitovym operaciyam, chego my, s takim trudom (kajetsya), izbejali.

Odnim slovom, zadacha interesnaya... Dumayu, chto porabotav dnya 2-3, mojno budet napisat' otlichnyyu implementaciyu.

[Dark Abyss of Yerevan]

Все правильно, загоняю в левый угол, при этом беру очередной байт из входного
массива, и ценные биты concat-ирую к полученной цепочке. если же в конце не все
биты помещаются(иф р!=8), то прибавляю сколько поместится, корректирую значение
к, и продолжаю процесс.

Вообще то когда говорят первые биты, я понимаю те что слева. Правильнее использовать higher/lower терминологию. Но поскольку ты даже там нарисовал,
я все таки понял что ты имеешь ввиду the "rightmost bits"=="младшие биты". Алгоритм
именно так и работает, берет правые биты.
Переменная К динамично меняет свое значение, а К1 никогда не меняется.
Тем не менее я все еще не уверен правильно ли все работает, и признаю что
написано не самым элегантным образом но идея проста.

Originally posted by Greco El:

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

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

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

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

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

[greka]

тааааааак, будет мне чем заняться на перерыв, ка я посмотрю )

to Dark Abyss of Yerevan> код кажись того, не пашет.


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

anyway, поживем - увидим..

[Tumanyan]

2 El Greco:
Popytayus' poyasnit' svoyu mysl' (eto ya naschet zavisimosti) na primere.

Dopustim, chto pytaemsya vylovit' 3 bita, nachinaya s 3-go. T e.
000xxx00 - nam nado poluchit' xxx i peredat' na vyxod. Samoe vajnoe - vyxod bajtovyj.
Predstav', chto v nachale ravoty algoritma, na vxod prishlo chislo 00000100.
V vyxodnoj bajt pomestim 00100000, i zapomnim pervuyu svobodnuyu poziciyu.
Teper', predstav', esli to je samoe chislo pridet na vxod eshe raz. Na vyxod v etom sluchae pojdet
00000100, kotoroe nado otorit' s predydushim sostoyaniem, t.e. 00100000 | 00000100.
Vsya fishka v tom, chto algoritm, v sluchae odnogo i togo je chisla na vxode doljen generirovat' raznye chisla na vyxode. Estestvenno, eto sledstvie raznyx nachal'nyx pozicij dlya zapisi. T.e. poziciya dlya zapisi i est' vnutrennee sostoyanie.

[Dark Abyss of Yerevan]

Не пашет? Вот редиска
Будет время попробую исправить

[greka]

prinoshu glubochajnshie izvinenija i iskrenne sojaleju o tom, chto ne uspel posmotret' kody vchera.

[Dark Abyss of Yerevan]

 
#include <stdio.h>

typedef unsigned char BYTE;

	/*	input_size (IN) must be given in bytes
		output_size (OUT) is returned 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);
	BYTE * save=output;				// save the output address
	BYTE * max_input=input+input_size;
	BYTE f,t,k1=k;					// temp variables. save k (k1 is fixed)

	*output_size=input_size*k;
	
/*

	k - how many bits do we need in the current input byte(dynamic)
	f - how much free bits left in the current output byte (t)

 */
	
	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
		f=8-k;						// 8-k free bits left in t
		t<<=f;						// shift left (8-k) bits
		

		/*
			if it is possible, add new bit chunk
			to the byte that is being processed.
		*/
		while ( f>=k1 && (input+1<max_input)){	
			t|=(BYTE)((*++input)<<(8-k1))>>(8-f);
			f-=k1;								
		}


		/*
			Next, if there's still free space left, add bits from
			NEXT input byte, and arrange k so when we process this
			byte next time we know that it is alread partially processed.
			
		*/
		if ( (f) && (input+1<max_input)
			t|=(BYTE)((*(input+1))<<(8-k1))>>(8-f);

		k=k1-f;						// arrange k

		*output++=t;				// write processed byte
		input++;

	}
	return save;
}



void main(){

	BYTE inp[]={1,2,3,4};
	BYTE *out;
	size_t out_s;
	out=bitpack(inp,4,&out_s,3);


}

[greka]

сегодня остался до 23:00 специально, чтоб проверить коды и подвести небольшие итоги.

Итак:
Dark Abyss of Yerevan: уважаемый, код твой работает. ..)

Статистику собирал так: НЕ СЧИТАЛ за операции то, что лежало в "for(.., .., ..)" и операции инкремента индексов массива.

обозначим:
+ - через "A"
shifts, ORs, ANDs - через "B"
logical compares - через "C"
кол-во операций на 4 входные элемента таково:
11A 7B 6C ~= 24 элементарные операции

У Hovik -а на 8 входных элементов:
4A 2B 1C ~= 7 элементарных операций

Я попробовал модифицировать код Dark Abyss of Yerevan -а с тем, чтоб использовать таблицы, приблизительно как это было сделано Hovik -ом, и получил:

5A 4C 6D ~= 14 элементарные операции.

При том, что отношение кол-ва операций уменьшился почти вдвое, отношение с кол-вом операций кода Hovik -a все равно почти (1:2) х 2

Офигенно, ничего не скажешь
Мне очешь понравилось - просто, как мясорубка.

Правда, выходные результаты, Hovo, вроде некорректны - на 4-м то ли 5-м элементе вместо 56 получает 57, и т.д. по цепочке, но скорее всего это вопрос индексации таблиц.
Однако было бы неплохо увидеть скорректированный код

Если я ошибся в расчетах, поправьте меня, плз.

Но мне кажется что я могу предложить нечто лучшее, чем код DAofY, медленнее, чем код Hovikа, но без тех ужасающих таблиц в 256*9*8 битов (на embedded-системах память дорога ).

Но это не сегодня - у нас уже 23:30 ..



Что, народ, эти двое смельчаков - весь потенциал идей ???!!


p.s. да, Hovo, FIAD, но не ATM, а пока лишь аудио G-кодеки.

[Tumanyan]

Garik,
Chisla neverny skoree vsrgo iz-za togo, chto ya, povidimomu, namudril s tablicami (dumayu, chto-to propustil v zapolnenii tablic).
Resurs dlya ument'sheniya tablic est': primenenie algoritma xraneniya razryavennyx matric. V etom sluchae tablica poluchitsya
2 ^ (shirina vyrezaemogo kusochka) * 9 bayt. T.e., dlya ssuchaya vyrezaniya 3-x bit poluchaetsya
8 * 9 = 72 bayt, chto, soglasis', ne tak uj i mnogo.
Krome togo, daje v imeyushejsya implementacii razmer tablicy ne takoj uj i bol'shoj. Delo v tom, chto ee neobyazatel'no zranit' v RAM - mojno jestko pro****' v ROM, cena kotorogo namnogo men'she ceny RAM - a.
Dumayu, chto dlya DSP-related task neskol'ko Kb ne takaya uj i bol'shaya cifra.
Naschet privedeniya algoritma v bojeskij vid: postarayus', no ne obeshayu. Chto-to zavalili menya rabotoj v poslednee vremya.

Udachi,
Hovik

[Tumanyan]

Vot uluchshennyj variant koda. Uluchshennyj v tom, smysle, chto ispravlena oshibka vychisleniya, i umen'shen razmer tablicy.
Operacij, pravda, pribavilos', no, zato, teper' mojno perejti na obrabotku 16-bitnyx vxodnyx posledovatel'nostej. Imeetsya vvidu, operirovat' ne bajtami (kak eto sejchas) a wordami. V predydushej versii eto trebovalo cherezmernogo uvelicheniya tablicy.
Kstati, Garik, chto ty schital vxodnym elementom v svoix testax? Imelos' li vvidu kajdyj bit, ili kajdyj vxodnoj bajt?
Opishi, pojalujsta, popodrobnee metodiku svoix raschetov...

  

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 << chBegin;

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

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

	g_Mask = ch;
	g_chBegin = chBegin;
	g_chLen = chLen;
	g_MaxVal = 1 << g_chLen;
}


void init_table()
{
	g_pTable = (unsigned char**)malloc(8 + g_chLen);

	for (unsigned char i = 0; i < 8 + g_chLen; i++)
	{
		g_pTable[i] = (unsigned char*)malloc(g_MaxVal);

		for (unsigned short j = 0; j < g_MaxVal; j++)
			if (i < 8 - g_chLen)
				g_pTable[i][j] = j << (8 - i - g_chLen);
			else
			if (i < 8)
				g_pTable[i][j] = j >> (i - 8 + g_chLen);
			else
			if (i == 8)
				g_pTable[i][j] = 0;//(unsigned char)j;
			else
				g_pTable[i][j] = j << (16 - i);
	}
}

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

	pos = 0;
	k = 0;
	posMax = 8 - (8 % g_chLen);
	*out = 0;

	for (unsigned int i = 0; i < isize; i++)
	{
		out[k] = out[k] | g_pTable[pos][(in[i] & g_Mask) >> g_chBegin];

		pos += g_chLen;

		if (pos > 7)
		{
			//k++;
			out[++k] = g_pTable[pos][(in[i] & g_Mask) >> g_chBegin];
			pos -= 8;
		}
	}
}

[greka]

>Kstati, Garik, chto ty schital vxodnym elementom v svoix testax? Imelos' li vvidu kajdyj bit, ili kajdyj vxodnoj bajt?
Opishi, pojalujsta, popodrobnee metodiku svoix raschetov...

Значит так, Hovo.


На входе считаю 1 элементом 1 байт.

1: while ( f>=k1 && (input+1<max_input))
{
2:	t|=(BYTE)((*++input)<<(8-k1))>>(8-f);
3:	f-=k1;
}				}

line1: 1+1+1 comparison, 1 addition == 3C 1A
line2: 2 substractions, 2 shifts == 2A 2B
line3: 1 substraction == 1A


Ох не знаю я метода хранения разреженных таблиц - надо будет литературу посмотреть..

Н-да, имплементация очень удачная, на мой взгляд.
Мое почтение

P.S. udachi s rabotoj; privet Lene