Ближайшая степень 2

С недавних пор помешался на асме и оптимизации
Взялся оптимизировать свой ацкий алгоритм начала прошлого года. Алгоритм много раз вызывал функцию нахождения ближайшей к произвольному числу степени 2. А в ней было использовано последовательное возведение в степень и инкремент, если меньше Ну тык вот, дооптимизировался я до нижеприведённого кода (вход/выход через EAX). В связи с чем вопрос: ведь вот чувствую, что сие можно ещё улучшить, только не пойму, как. Помогёте?

Код (Text):

1.   MOV EDX, 1;
2.   BSR ECX, EAX;
3.   JE @exit;
4.   SHL EDX, CL;
5.   SUB EAX, EDX;
6.   ADD EAX, EAX;
7.   CMP EAX, EDX;
8.   MOV EAX, EDX;
9.   JLE @exit; <---- JL, если до большего (как в случае EAX=6)
10.   ADD EAX, EAX;
11.   @exit:

 

Ближайщая степень двойки - это номер старшего бита в числе, как я понимаю.

Код (Text):

1. mov eax,[number]
2. mov ebx,31
3. @@:
4.   bt eax,ebx
5.   jc @F
6.   dec ebx
7.   jmp @B
8. @@:
9.    ;В ebx - степень

А до меньшего ещё надо dec ebx сделать. [del]

 

Ну, не совсем так. Есть у нас, скажем, число 190. Оно лежит в промежутке от 128 до 256. Нужно определить, к какому из двух "концов" оно ближе. В данном случае - к 128. Его и пишем. А если мы наткнёмся на 193, то оно тяготеет более к 256. Можете сами проверить. А 192 - это среднее арифметическое 128 и 256. Возникает особая ситуация, которая командой JLE трактуется в сторону 128, JL - в сторону 256 (см. коммент). А в коде из [1] берётся просто старший ненулевой бит числа.

 

Код (Text):

1.         mov     eax, 6
2.         bsr     ecx, eax
3.         shr     eax, cl
4.         adc     ecx, 0
5.         shl     eax, cl

но не думаю что лучший вариант

 

хм... По памяти улучшение налицо! И решение интересное (мне бы и в голову не пришло юзать здесь ADC)! Однако по скорости оптимизации, увы, нет: четыре данные операции (не считая загрузку числа в ЕАХ) выполняются в среднем за 890 мс на 10^8 проходов, а исходные 10 - за 520. Наверняка сказывается тормознутость ADC. Однако всё равно спасибо!
ЗЫЖ Забыл сказать: код "затачивается" под Celeron 2400.
Предлагайте ещё варианты =)

 

Смысл в том, чтобы воспользоваться bsr, а затем проверить следующий бит.

bsr ecx,eax
mov edx, [table+ecx*4]
test eax, edx
jz @f
add ecx, 1
@@:
mov eax,ecx


table:
dd 0
dd 1
dd 2
dd 4
...


Я не помню точно поведение bsr, а доков нет, поэтому table придётся поправить

 

ага, а еще про bt

Код (Text):

1. bsr     ecx, eax
2. add     eax, eax
3. bt      eax, ecx
4. mov     eax, 0
5. adc     ecx, 0
6. bts     eax, ecx

но опять же, одна команда от другой зависит

 

На основании нескольких вышеприведённых сырцов (респект за идею) было написано это:

Код (Text):

1.   BSR ECX, EAX;
2.   SHR EAX, CL;
3.   JNC @skip;
4.   ADD ECX, EAX; <---- EAX = 1
5.   @skip:
6.   SUB EAX, 1;
7.   BTS EAX, ECX;

И - о чудо! - минус 100 миллисекунд! 420 вместо 520! Однако вся проблема в том, что в "спорных" случаях этот (и вышеуказанные) алгос приводит число к большему! А нужно - к меньшему =( Видимо, всё-таки придётся пользовать таблицы...

 

Код (Text):

1. bsr ecx,eax
2. mov edx, [table+ecx*4]
3. test eax, edx
4. jz @f
5. add ecx, 1
6. @@:
7. mov eax,ecx
8.  
9. table:
10. dd 0
11. dd 1
12. dd 2
13. dd 4
14. ...

угу.
ИМХО составление таблицы средних арифметических 0x01, 0x02, 0x03, 0x06, 0x0C, 0x18, 0x30, 0x60, 0xC0, ... и сравнение с eax побыстрее будет.

Код (Text):

1. bsr ebx, eax
2. xor ecx, ecx
3. cmp eax, [table + ebx*4]
4. setg(e) cl
5. add ebx, ecx

результат в ebx.

 

Куда подевался TheSvin? Думаю у него бы был умный ответ

 

Нам нравится вариант от KeSqueer
Только если в исходном регистре ноль, то bsr даёт undefined результат в destination.
Так что так (вход, выход - eax):

Код (Text):

1. xor edx, edx
2. bsr ecx, eax
3. setz    dl
4. sub dl, 1
5. add eax, eax
6. bt  eax, ecx
7. adc ecx, 0
8. and ecx, edx
9. mov eax, ecx

А что, правда bt настолько тормозная, что выгоднее через таблицу делать?

 

Код (Text):

1. dec     eax
2. bsr     ecx, eax
3. shr     eax, cl
4. adc     ecx, 0
5. ;and     ecx, 0x1F

либо второй вариант, тоже с dec eax вначале

 

Тогда лучше без adc и btX. Что-то типа

Код (Text):

1. bsr ecx,eax
2. jz @F
3. mov edx,-1
4. mov ebx,1
5. shl edx,cl
6. sub ecx,1
7. jle @F
8. shl ebx,cl
9. lea eax,[eax+ebx-1]
10. and eax,edx
11. @@: