![]() |
![]() | #18 |
Бакалавр Join Date: 03 2002 Location: Detroit, MI, USA
Posts: 482
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
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.
__________________ Hovhannes Tumanyan, CISSP |
![]() |
![]() | #19 | |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
Все правильно, загоняю в левый угол, при этом беру очередной байт из входного массива, и ценные биты concat-ирую к полученной цепочке. если же в конце не все биты помещаются(иф р!=8), то прибавляю сколько поместится, корректирую значение к, и продолжаю процесс. Вообще то когда говорят первые биты, я понимаю те что слева. Правильнее использовать higher/lower терминологию. Но поскольку ты даже там нарисовал, я все таки понял что ты имеешь ввиду the "rightmost bits"=="младшие биты". Алгоритм именно так и работает, берет правые биты. Переменная К динамично меняет свое значение, а К1 никогда не меняется. Тем не менее я все еще не уверен правильно ли все работает, и признаю что написано не самым элегантным образом ![]() Quote:
| |
![]() |
![]() | #20 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]()
тааааааак, будет мне чем заняться на перерыв, ка я посмотрю ![]() to Dark Abyss of Yerevan> код кажись того, не пашет. ![]() Hovo, код твой я с удовольствием посмотрю, а насчет идейки - при чем здесь зависимость выхода от входа с учетом текущего состояния ? Ты эту зависимость уже вроде имплементировал - в таблицах выход всегда зависит от входа (индексов) ![]() anyway, поживем - увидим.. ![]() |
![]() |
![]() | #21 |
Бакалавр Join Date: 03 2002 Location: Detroit, MI, USA
Posts: 482
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
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. |
![]() |
![]() | #22 |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
Не пашет? Вот редиска ![]() Будет время попробую исправить ![]() |
![]() |
![]() | #24 |
Дошкольник Join Date: 01 2002 Location: hell
Posts: 124
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]() Code: #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); } |
![]() |
![]() | #25 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]()
сегодня остался до 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-кодеки. ![]()
__________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/ |
![]() |
![]() | #26 |
Бакалавр Join Date: 03 2002 Location: Detroit, MI, USA
Posts: 482
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
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 |
![]() |
![]() | #27 |
Бакалавр Join Date: 03 2002 Location: Detroit, MI, USA
Posts: 482
Downloads: 0 Uploads: 0
Reputation: 0 | 0 | ![]()
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... Code: 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; } } } |
![]() |
![]() | #28 |
Академик Join Date: 09 2001 Location: inside myself
Posts: 5,369
Downloads: 0 Uploads: 0
Reputation: 18 | 5 | ![]()
>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 байт. Code: 1: while ( f>=k1 && (input+1<max_input)) { 2: t|=(BYTE)((*++input)<<(8-k1))>>(8-f); 3: f-=k1; } } line2: 2 substractions, 2 shifts == 2A 2B line3: 1 substraction == 1A ![]() Ох не знаю я метода хранения разреженных таблиц - надо будет литературу посмотреть.. ![]() Н-да, имплементация очень удачная, на мой взгляд. Мое почтение ![]() P.S. udachi s rabotoj; privet Lene ![]() |
![]() |
Sponsored Links |