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(IA:DataArray; var OA:DataArray; BitsNum:integer; var OASize:integer);
var TmpOA:DataArray;
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 такта), но потом
почему то передумал. А зря.

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

#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;
}
}
}

[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 никогда не меняется.
Тем не менее я все еще не уверен правильно ли все работает, и признаю что
написано не самым элегантным образом :D но идея проста.

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]

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

[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 .. :(

;)

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

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