![]() |
![]() | #1 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]()
Во, народ, интересная задачка - паковка бит-стримов: in general: есть входной массив Input данных (скажем, массив байтов (1 байт == 8 бит)) есть выходной массив Output данных (скажем, WORD-ов. 1 WORD == 2 Bytes == 16 bits). Во входном массиве Input данные содержатся тока в первых "К" битах, остальные биты содержат мусор. Надо эти ценные для нас биты упаковать в выходной массив Output. Смысл паковки - все ценные биты из массива Input биты ложатся в ряд друг за другом. ![]() Итак..... |
![]() |
![]() | #3 |
» Join Date: 01 2002
Posts: 777
Downloads: 1 Uploads: 0
Reputation: 0 | 0 | ![]()
vot primerno tak(poka ne proveryal,mozhet est' oshibki) Code: #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); } } |
![]() |
![]() | #6 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]() ![]() ![]() eto vezde est', Acid jan . ![]() ![]() 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. ![]()
__________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/ |
![]() |
![]() | #7 |
Младенец Join Date: 10 2001 Location: Yerevan
Posts: 55
Downloads: 7 Uploads: 0
Reputation: 8 | 0 | ![]()
ete chisht em haskacel... const MAX_ARRAY=10; type DataArray=ARRAY [1..MAX_ARRAY] OF BYTE; Procedure GetArray(IA ![]() ![]() var TmpOA ![]() 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. [email protected] stacvuma byte-erov, bayc shat hesh karelia da poxel word-eri... DW[i]:=(DB[i] shl 8) + DB[i+1];
__________________ http://freenet.am/~softland |
![]() |
![]() | #8 | |
The Reloaded Join Date: 01 2002 Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4 Uploads: 0
Reputation: 146 | 4 | ![]() Quote:
| |
![]() |
![]() | #9 |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
Не знаю правильно ли я все понял, но тем не менее.. Code: deleted by author. (memcpy по моему и есть movsw или movsw+movsb, в зависимости от четности длины копируемого участка), а использование shl/shr и вовсе делает прогу очень быстрой. Можно и на АСМ е написать. Greco, clarify the task plz. |
![]() |
![]() | #10 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]()
неееееее, народ, не пойдет. так, поясню задачу: имеем 1 елемент (далее: "Е"), длиной в 1 байт. в этом байте нам нужны не все 8 бит, а всего лишь первые 3 бита. далее. таких вот элементов "Е" у нас целый массив, который называется "Input". Этот "Input"-массив нужно преобразовать в выходной массив "Output" таким образом, чтоб в выходном массиве были ТОЛЬКО "нужные" нам биты из массива "Input". То есть массив "Input": xxxxxBBB xxxxxBBB xxxxxBBB xxxxxBBB ... должен превратиться в: "Output": BBBBBBBBBBBB ... P.S. будьте гуманны, пишите комментарии к коду своему ![]() |
![]() |
![]() | #11 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]()
Dark Abyss of Yerevan: думаю, моего уточнения достаточно. SMoKE: я честно пытаюсь понять, что там написано. если после моих комментариев ты считаешь, что твой код отвечает задаче, то пожалуйста поясни каждый его шаг. ![]() А использование "gugush := (BitsNum div 8);" сделало бы код гораздо читабельнее - оно встречается там несколько раз..... ![]() |
![]() |
![]() | #12 | |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
ок, понял. будет. Quote:
| |
![]() |
![]() | #13 |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
бррррр.... ужас. Так вот, если K=1,2,4 или 8 - задача решается очень просто. Например, если k=4, Code: mov ah, input[0]; mov al, input[1]; mov cl,4; shl al,cl; shl ax,cl; mov output[0],ah; Я хотел на ассемблере написать, используя RCR/RCL (выполняется за 2 такта), но потом почему то передумал. А зря. Короче, не знаю заработает ли ЭТО, но зато точно знаю что я иду спать ![]() Code: #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); } |
![]() |
![]() | #14 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]() ![]() Уважаемый Dark Abyss of Yerevan, позвольте прокомментировать код завтра - я тож хочу спать ![]() как я понял, ты пакуешь биты, загоняя в левый угол Output-массива - так, как и требуется. как помнишь,нам нужны ПЕРВЫЕ "k" битов каждого Input-элемента. "первые биты" == "младшие биты" (или это еще одно уточнение с моей стороны?), LSBs не успел сегодня посмотреть, но на первый взгляд: Code: 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; } ![]() Ладно, мне тож пора - до связи и успехов с битами ![]() |
![]() |
![]() | #15 |
Бакалавр Join Date: 03 2002 Location: Detroit, MI, USA
Posts: 482
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
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. Code: 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; } } }
__________________ Hovhannes Tumanyan, CISSP |
![]() |
Sponsored Links |