Те же но в кепках. Задача похожа на 10ю, но здесь бинарный массив может состоит из большего количества бит. Дан адрес бинарного массива, размер, указатель на память по которой нужно заполнить длины строк (единичных и нулевых) в бинарном массиве. Приоритет - скорость. Нужно иметь ввиду что во всех до сих пор предъявленных задачках предметная область - передача данных последовательным сигналом. В таких передачах часто полезная передача сменяется состоянием ожидания - т.е. длинными низкими или высокими сигналами. Допустим очень длинная единичная подстрока, затем "всплеск" чередования намного более коротких единичных и нулевых подстрок, затем например длинная нулевая подстрока сменяющаяся долгой единичной подстрокой до следующего "всплеска".
При таких условиях может подойдет принцип такого "предсказывания" (т.к. не известен максимальный размер строки, я выбрал размер DWORD для заполнения длин строк)? Код (Text): mov esi,long_binary_string mov edi,memory_pointer xor ecx,ecx align 16 ; цикл всего 2 такта на PIII @@: mov eax,dword [esi] add ecx,32 ; в ecx собираем длину хорошей строки add esi,4 xor eax,dword [esi] jz @B ; хорошая строка закончилась sub ecx,32 ; вычтем упреждение mov dword [edi],ecx ; запишем собранную длину sub esi,4 ; add edi,4 ; ; теперь считаем любым способом из 10-й задачи
bogrus > "add edi,4 ;теперь считаем любым способом из 10-й задачи" Не все так просто: add edi,4 нужно делать по условию (ecx > 0) & (eax and 1 = 1), т.е. "хорошая строка" была и закончилась на границе dword'а. Ну примерно так: Код (Text): sub ecx,32 mov [edi],ecx setnz cl and eax,1 and al,cl lea edi,[edi+eax*4] sub esi,4 Хотя если хотя бы два дворда совпали, то и sub ecx и sub esi можно не делать - нужно только как-то учесть особенность первого прохода (т.к. при первом совпадении мы сразу имеем длину строки = 64, а последующее приращение идет по 32). Ну и еще вопрос: как из побитового сравнения возвращаться в режим сравнения по dword - сразу после первого прохода или через несколько проходов или анализировать совпадения X >= 32 бит.
Кстати и первый dword не мешало бы проверить на 0 или -1. Может так: Код (Text): mov esi,long_binary_string mov edi,memory_pointer mov eax,[esi] cdq sub edx,eax jne bybit xor ecx,ecx @@: add esi,4 add ecx,32 mov edx,[esi] cmp edx,eax je @B mov [edi],ecx xor eax,edx and eax,1 lea edi,[edi+eax*4] bybit:
Если старший бит текущего двойного слова совпадает с младшим битом следующего слова то битовая строка "продолжается" в следующем я не увидел учёта этого. Решения из 10ой задачи ещё нужно "ассиммилировать" с условиями данной и это кстати одно из алгоритмических "узких горлышек". Также переход с "полезного" на "ожидающий" активный и пассивный сигнал может быть в дампе сделан несколько раз а не только в начале.
The Svin > битовая строка "продолжается"..я не увидел учёта этого Мое замечание как раз к этому и относилось. В последнем варианте приращение edi делается только в случае несовпадения младшего бита следующего слова с текущим состоянием "ожидающего" сигнала. Еще вопрос по 10й задачке: изначально массив длин обнулен или нет ? А то все напрашиваются решения с простым икрементом без предварительного обнуления.
Его же можно "обнулить" самому если это даст ощутимый эффект. Для упрощения задачи можно считать 1. Дамп большой (т.е. константную фиксированную оптимизацию, вне цикла, - можно игнорировать) Пусть дамп будет от 2^17 до 2^27 бит. 2. Дамп и выронен битово по 32ум (по двойным словам) и имеет размерность в целом количестве двойных слов. Цикл на бит никуда не годится - ЮСовские ракеты успеют вас сбить пока вы будете переваривать сигнал, бензин потечёт из бака пока ваш анализатор разберётся что его хватит, самолёт не учтя деферента анализируя отражённый сигнал врежется в аэровокзал. Поскольку подсчёт длин это лишь кусок такого вооброжаемого анализатора, то время на сам анализ может расти от него экспонально и даже факториально в зависимости от задачи, т.е. не надейтесь на несколько гигогерцевые процы (тем более это г.. обычно очень глючное и на серьёзные задачи не ставится, а то перегреется в самый не подходящий момент) ищите алгоритм. Для примера представьте что нить вроде азбуки Морзе переданный таким сигналом. Длинная едица - ожидание. Строб передаваемый сменой единичных - нулевых (размером 4-8 бит допустим 9 изменений) - пауза, единичная в 210-300 бит после строба - начинаю передавать новую информацию, после неё далее чередующиеся "точка - тире" разделенные описанным стробом, на точку 40-50 единиц на тире 70-80. Нужно потом будет учесть допуски уже после считывания длин, сигнал "полуизвестный" подводные атомные акулы кравожандых хрюкодавов меняют постоянно коды хрюкеры - кодбрейкеры с красными от бессоницы глазами с последней хрупкой надеждой смотрят на вас ожидая суперсчиталки длин сигнала.
leo Да, я хотел "пробить" подойдет ли такой принцип, а потом уже можно бы делать обвязку (согласование с 10-й задачей), а то вдруг там километровые строки бит, тогда не грех MMX прикрутить, чтобы "упреждать" не 32 бита, а например сразу 512 The Svin Те циклы что из 10-й? Мне кажется их нереально сделать существенно быстрее
The Svin Лирическое ИМХО: Анализ длин это хорошо, но к возможным катастрофам он имеет отдаленное отношение. Если понимать задачу в лоб - подсчитывать длины с точностью до бита, то это скорее задачка из области исследования (радиоразведки), которая не обязательно должна решаться в реальном времени. В реальных задачах связи и управления с дискретными сигналами большую роль играет различимость сигналов. Чем больше различие между используемыми сигналами, тем система устойчивее к внешним и внутренним помехам и тем ниже требования к точности извлечения информационного параметра, а отсюда и простота и скорость обработки. Приведенный тобой пример это лишний раз подтверждает: длительности точки и тире различаются не менее чем на 20 бит, т.е. на 2-3 байта. А это уже гораздо проще анализировать на компьютере, т.к. с родными единицами - байтами он работает гораздо быстрее, чем с битами. Строб, насколько я понимаю, не несет никакой полезной информации и играет вспомогательную роль - запуск и настройка приема (синхронизация и\или уровень нуля), хотя нельзя исключать вариант, когда строб несет в себе адрес приемника. В любом случае, строб сильно отличается от точек и тире и обнаружить его можно также побайтным, а не побитовым анализом. А посему, если речь идет о "полуизвестном" сигнале с приведенными параметрами, то возможно и считалка длин не нужна. А если хочется уточнить параметры сигнала, то можно это делать и не в реальном времени, сохранив куски дампа выделенные грубым побайтным анализатором. Хотя для приведенного примера состояния 0\1 меняются не часто и возможно использование инструкции BSF обеспечит удовлетворительную скорость при подсчете длин с точностью до бита.
> "с последней хрупкой надеждой смотрят на вас ожидая суперсчиталки длин сигнала" Все еще ждем-с ? На "супер" ес-но не тянет, но хоть что-то для затравки: Код (Text): mov ebp,bitstring_size mov esi,bitstring_ptr mov edi,destarray_ptr add ebp,esi xor ecx,ecx mov eax,[esi] ;первый дворд сигнала mov [edi],ecx ;обнуляем первую длину cdq ;edx = старшему биту eax cmp edx,eax ;контроль наличия переходов 0\1 jne scan dloop: ;подсчитываем дворды add esi,4 cmp esi,ebp jae exit add ecx,32 mov eax,[esi] cmp eax,edx je dloop mov [edi],ecx ;сохраняем длину xor ecx,ecx mov [edi+4],ecx ;обнуляем следующую длину xor edx,eax ;проверяем продолжение подстроки and edx,1 lea edi,[edi+edx*4] ;если нет продолжения, то инкремент edi scan: ;выделяем переходы xor ebx,ebx ;позиция предыдущего перехода mov edx,eax add edx,edx xor edx,eax and edx,-2 jz skip ;нет переходов ;сканируем переходы bsf ecx,edx bsloop: sub ebx,ecx ;длина подстроки с обр.знаком btr edx,ecx sub [edi],ebx mov ebx,ecx add edi,4 mov [edi],0 ;обнуляем следующую длину bsf ecx,edx jnz bsloop skip: ;запись длины последней подстроки sub ebx,32 sub [edi],ebx xor ecx,ecx mov [edi+4],ecx ;обнуляем следующую длину ;следующий dword add esi,4 cmp esi,ebp jae exit cdq ;сохраняем старший бит пред.слова в edx mov eax,[esi] xor edx,eax ;контроль продолжения строки and edx,1 lea edi,[edi+4*edx] ;проверка наличия переходов ;(возможны другие варианты, например просто jmp scan ) cdq cmp edx,eax jne scan jmp dloop exit: ;конец строки - подсчитываем размер массива длин mov eax,edi sub eax,destarray_ptr shr eax,2 cmp [edi],1 sbb eax,0 ;в eax - длина число элементов массива длин
