Мелкие задачки для крупных мозгов 9

Тема в разделе "WASM.ZEN", создана пользователем The Svin, 5 мар 2005.

  1. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    Дан указатель на память (в байтах разумеется) и два индекса бита (младший и старший - относительно указателя на память.) В выходном значении

    в 0 бите отразить выравнен ли младший индекс по двойному

    слову (1 - не выравнен)

    в 1 бите отразить является ли старший бит старшим битом двойного слова. (1 - не является)

    во 2 бите отразить принадлежат ли оба бита одному и тому же двойному слову. (1 - принадлежат)



    Нетрудно заметить что бин и унбин в выходном значении отражают принадлежит ли битовый диапозон диапозону выравненому по двойным словам.

    (т.е. младший бит является битом двойного слова и размер

    в битах кратен 32ум)



    Задача разумеется для "крупных" или по крайней мере "пытливых" мозгов, т.е. избегайте (после того как представите мат. лог. модель) тупых чрезмерных проверок.



    Большое спасибо тем кто учавствует.

    И не ленитесь писать тесты, опять мне что-ли писать?
     
  2. _BC_

    _BC_ БЦ

    Публикаций:
    0
    Регистрация:
    20 янв 2005
    Сообщения:
    759
    -- under construction --
    Код (Text):
    1.     xor eax, eax
    2.     mov edx, hiindex
    3.     bts eax, edx
    4.     mov ecx, loindex
    5.     xor edx, ecx
    6.     cmp edx, 32
    7.     setalc
    8.     rol eax, 2
    9.     bts eax, ecx




    пока не идеально ...
     
  3. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Код (Text):
    1. index_test:;(index_low +4, index_high +8)
    2.     xor eax,eax
    3.     mov edx,[esp+4];i_l
    4.     and edx,-32
    5.     cmp edx,[esp+4]
    6.     rcr eax,1
    7.     mov ecx,[esp+8];i_h
    8.     or ecx,31
    9.     cmp [esp+8],ecx
    10.     rcr eax,1
    11.     xor ecx,edx
    12.     cmp ecx,32
    13.     rcl eax,3
    14.     ret 8
     
  4. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    А что если указатель на память не выравнен по двойному слову? Вы как то проигнорировали сам указатель.
     
  5. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    The Svin

    Самое простое решение которое я вижу: прибавить два младших бита указателя к индексу бита, сдвинув их на 3 разряда. [delete]Но я не уверен в правильности ответа, если произойдёт переполнение.[/delete]


    Код (Text):
    1. index_test:;(index_low +4, index_high +8, array +12)
    2.     mov eax,[esp+12]
    3. ;        and eax,3 - эта команда не нужна
    4.     shl eax,3
    5.     add [esp+4],eax; даже в случае переполнения
    6.     add [esp+8],eax; ответ будет правильный
    7.     xor eax,eax
    8.     mov edx,[esp+4];i_l
    9.     and edx,-32
    10.     cmp edx,[esp+4]
    11.     rcr eax,1
    12.     mov ecx,[esp+8];i_h
    13.     or ecx,31
    14.     cmp [esp+8],ecx
    15.     rcr eax,1
    16.     xor ecx,edx
    17.     cmp ecx,32
    18.     rcl eax,3
    19.     ret 12
     
  6. _BC_

    _BC_ БЦ

    Публикаций:
    0
    Регистрация:
    20 янв 2005
    Сообщения:
    759
    Ver. 2.0 ;) loindex = dword ptr [esp+4], hiindex = ...+8


    Код (Text):
    1.  
    2. loindex = dword ptr [esp+4], hiindex = ...+8, array = ...+0Ch
    3.     xor eax, eax
    4.     cdq
    5.     mov ebp, array
    6.     mov ebx, hiindex
    7.     lea ebx, [ebx+ebp*8]
    8.     bts eax, ebx
    9.     mov ecx, loindex
    10.     lea ecx, [ecx+ebp*8]
    11.     xor ebx, ecx
    12.     cmp ebx, 32
    13.     rcl eax, 1
    14.     adc eax, eax
    15.     inc edx
    16.     inc ecx
    17.     ror edx, cl
    18.     adc eax, eax
     
  7. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    _BC_

    Спасибо за варианты, но ты б обратил внимание на мой пост, пожалуйста. Нельзя игнорировать указатель. Указатель то в байтах, значит биты выравнены по восьми, а требуется внимание к двойным словам, значение в указателе влияет на выравненность по словам, одних индексов недостаточно.

    Гиганты в главном правы, а валятся на мелочах.

    Пожалуйста, повнимательней к мелочам. They matter.
     
  8. _BC_

    _BC_ БЦ

    Публикаций:
    0
    Регистрация:
    20 янв 2005
    Сообщения:
    759
    Добавил указатель. Подсчитаем байтики ? ;)
     
  9. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Код (Text):
    1.               ; eax = ptr to data
    2.               ; ecx = lower index
    3.               ; edx = higher indeh
    4. 8D0CC1        lea     ecx, [ecx+eax*8]
    5. 8D14C2        lea     edx, [edx+eax*8]
    6. 8BC1          mov     eax, ecx
    7. 33C2          xor     eax, edx
    8. C1E8 05       shr     eax, 5
    9. 0F94C0        sete    al
    10. 83CA E0       or      edx, -20h
    11. 83C2 01       add     edx, 1
    12. 10C0          adc     al, al
    13. 83E1 1F       and     ecx, 1Fh
    14. 83E9 01       sub     ecx, 1
    15. 10C0          adc     al, al
    16. 34 03         xor     al, 3
    17. 0FB6C0        movzx   eax, al


    ЗЫ: долго думал, но так и не понял, правильно ли работает код %)
     
  10. _BC_

    _BC_ БЦ

    Публикаций:
    0
    Регистрация:
    20 янв 2005
    Сообщения:
    759




    Надо тестировать (лучше под отладчиком). Твой код работает неверно.
     
  11. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    The Svin




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



    mov eax,memory

    mov ecx,eax

    add eax,l_index

    add ecx,h_index

    or eax,ecx

    and eax,3

    jz переход если диапазон выровнен по двойному слову (кратен 32-м битам)
     
  12. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    Неа. Должен получится индекс "кейса". Один из восьми возможных.

    000 оба выравнены и не принадлежат одному двойному слову

    100 оба выравнены но принадлежат одному двойному слову

    и т.д.

    Воображаемому обработчику нужно знать, какие биты выравнены какие не выравнены и принадлежат ли они двойному слову.
     
  13. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine




    Тогда нужен ещё бит, у нас есть бит для
    , а для старшего индекса нет? Или достаточно знать выравнены ли оба бита (весь диапазон)?
     
  14. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia
    Так в условиях задачи и есть - установить состояние трёх бит. Нулевой, первый и второй.

    Пожалуйста, прочитай ещё раз условия в первом посте.

    Нулевой бит - состояние невыравнености младшего индекса

    Первый бит - старшего (является ли старшим дворда тут нельзя сказать выравненость, просто имеется есть ли в этом дворде после него ещё что-то)

    Второй бит - принадлежность обоих одному.
     
  15. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Я просто подумал, что второй бит проверка является ли старший индекс - старшим, т.е:



    401004 ; memory = 401000 l_index = 4

    401008 ; memory = 401000 h_index = 8



    Здесь 0 (старший больше младшего)



    401008 ; memory = 401000 l_index = 8

    401004 ; memory = 401000 h_index = 4



    Здесь 1 (старший меньше младшего, диапазон неверен)



    А третий бит проверяет, не оба ли индекса в одном дворде



    401004 ; memory = 401000 l_index = 4

    401005 ; memory = 401000 h_index = 5



    Здесь оба в одном дворде, (втором от memory)



    По-этому был не ясен смысл первого бита, если он проверяет только младший бит, при таком условии у меня получилась огромная фигня :)
    Код (Text):
    1. mov   eax,memory+l_index
    2. mov   ecx,memory+h_index
    3.  
    4. mov   ebx,ecx
    5. cmp   eax,ecx
    6. sbb   edx,edx
    7. and   ecx,edx
    8. xor   edx,-1
    9. and   edx,eax
    10. or    edx,ecx   ; edx = max index
    11. sub   ebx,eax
    12. sbb   ecx,ecx
    13. and   ecx,ebx
    14. xor   ebx,ecx
    15. cmp   ebx,1
    16. sbb   ebx,ebx
    17. and   ebx,2 ; установить 2 бит в ebx если h_index < l_index
    18. add   eax,ecx   ; eax = min index
    19. sub   edx,eax
    20. cmp   edx,4
    21. sbb   ecx,ecx
    22. and   ecx,4 ; установить 3 бит в ecx если memory+l_index & memory+h_index в одном дворде
    23. and   eax,3
    24. setnz al    ; установить 1 бит в eax если memory+l_index не выровнен на 4
    25. xor   eax,ebx   ; копировать 2 бит в eax
    26. xor   eax,ecx   ; копировать 3 бит в eax
     
  16. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    _BC_ >




    Разве не видно, что код прямо из Olly?

    Он работает, но правильно ли я понял условие задачи - это и есть вопрос :).



    И хорошо было бы не ограничиться
    , а привести пример входных данных дающий ошибочный результат.



    Вот, например, мои результаты:
    Код (Text):
    1.  
    2. prt = 0, lo = 0,   hi = 31,  result = 4 = 100b  // 7
    3. ptr = 2, lo = 16,  hi = 47,  result = 4 = 100b  // 7
    4. ptr = 1, lo = 10,  hi = 23,  result = 5 = 101b  // 6
    5. ptr = 3, lo = 8,   hi = 40,  result = 2 = 010b  // 9
    6. ptr = 3, lo = 280, hi = 311, result = 4 = 100b  // 9
    В последней колонке приведены ответы твоего кода. Как видно, они отличаются от моих.

    Но я склоняюсь к тому, что верные именно мои, тк у тебя почему-то 3й бит = 1 ;)





    Лично меня смущает необходимость последнего xor в моём коде.

    очевидно, что The Svin уже имеет решение, и поскольку

    результат используется для табличного перехода, не важно, чему конкретно равны биты (0 или 1).

    Значит арифметика у меня какая-то не та ;)

    Единственное сравнение (условную установку байта) я оставил - при чистой арифметике на 3 байта больше получается.
     
  17. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia




    Что то непонятно что это memory+h_index.

    Указатель он в байтах а индекс относительно него в битах.



    Ребята, я никак слов не могу подобрать, всё намекаю, намекаю :) Фиговый я намекальщик :))

    Ну почему сразу отвергать анализ, что может изменится при прибавлении указателя, какие биты могут, какие нет. как это повлиять может. Вы как-то изначально предмет байты+биты в сторону откинули и с головой ушли в поиски машинной команд покороче, и никак мне внимание не удаётся привлечь. Ну вспомните segment+offset и тучку других вещей с накладыванием чисел друг на друга.

    Задачка не обязательно должна быть решена минимально с точки размера, вообще индексные переводы делаются чаще для того чтобы побыстрее выполнить управление.

    Предположите к примеру (просчитайте) какие входящие вероятней и попытайтесь от входных данных построить наибыстрейшую модель при средне-ожидаемом входе.
     
  18. The Svin

    The Svin New Member

    Публикаций:
    0
    Регистрация:
    6 июл 2003
    Сообщения:
    665
    Адрес:
    Russia


    Не лучше так к этому не относится :))

    Нет решений пока не показали.

    Можно вообще предположить что я эксплуатирую бесплатные мозги, чтобы они делали для меня домашнюю работу, а сам загребаю по 30000 евро per month с какой-нить зарубежной компани.

    С другой стороны даже в этом случае будет польза - потренироваться и проверить себя на задачках за которые платят 30000 евро per month.
     
  19. _BC_

    _BC_ БЦ

    Публикаций:
    0
    Регистрация:
    20 янв 2005
    Сообщения:
    759
    Бл%$# !!!

    Я невнимательно прочитал условие. Я сделал 1 в ответе, если выравнен, 0 если наоборот. Но это элементарно правится ценой 2х байтов.



    Про цифру 9 в моих результатах -- это нормально. Ты просто не цифру бери, а три младших бита. В условии не сказано про судьбу битов 31-3 ответа. Главное, что биты 2-0 содержат то что надо.

    Да, и в последней строке... там 000b, а не 9. Не знаю как ты 9 (1) там получил. Я прогнал у себя с 3/280/311 и получил 000b (на не исправленном).



    Тогда вот так:

    ; ebp = base, ecx = low index, ebx = high index
    Код (Text):
    1.     xor eax, eax
    2.     cdq
    3.     lea ebx, [ebx+ebp*8]
    4.     bts eax, ebx
    5.     lea ecx, [ecx+ebp*8]
    6.     xor ebx, ecx
    7.     cmp ebx, 32
    8.     rcl eax, 1
    9.     adc eax, eax
    10.     inc edx
    11.     inc ecx
    12.     ror edx, cl
    13.     adc eax, eax
    14.     xor al, 011b


    Можно даже лучше сделать. Хотя и так мой код пока самый маленький.
     
  20. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    The Svin



    Я твой намёк еще во втором своём сообщении учёл, только код там был не правильный, вот теперь правильный вариант:


    Код (Text):
    1. it_2:;(array +4, index_low +8, index_high +12)
    2.     mov ecx,[esp+8]
    3.     mov edx,[esp+12]
    4.     mov eax,ecx
    5.     mov ebx,edx
    6.  
    7.     shr eax,3; sar eax,3 правильному варианту потребовались исправления ;)
    8.     shr ebx,3; sar ebx,3 но теперь должно работать
    9.  
    10.     add eax,[esp+4];адрес байта с младшим битом
    11.     add ebx,[esp+4];адрес байта со старшим битом
    12.     and ecx,7;номер младшего бита в байте
    13.     and edx,7;номер старшего бита в байте
    14.     lea ecx,[ecx+eax*8]
    15.     lea edx,[edx+ebx*8]
    16.     and eax,-4;адрес младшего двойного слова
    17.     and ebx,-4;адрес старшего двойного слова
    18.     and ecx,31;номер младшего бита в двойном слове
    19.     and edx,31;номер старшего бита в двойном слове
    20.     cmp eax,ebx
    21.     setz al
    22.     cmp edx,31
    23.     rcl eax,1
    24.     cmp ecx,1
    25.     cmc
    26.     rcl eax,1
    27.     ret 12




    All

    А что ваш код говорит при base=XXXXXXX1h
    Код (Text):
    1. index_low index_high
    2. 7FFFFFD8h,7FFFFFF7h ; 4
    3. 7FFFFFF8h,80000017h ; [b]0[/b] у вас здесь получился? [added]ноль должен быть не здесь[/added]
    4. 80000018h,80000037h ; 4


    [added]

    а здесь:

    base=2,index_low=0FFFFFFF0h,index_high=00000000Fh

    [/added]