Задачка об уникальных тетрадах

Тема в разделе "WASM.A&O", создана пользователем Black_mirror, 11 мар 2010.

  1. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    слушайте, покажите условие последнего обсуждения, ато, похоже оно уже не из #1. а рыть все 4 стр лениво
     
  2. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    qqwe
    Всё то же.

    Без переходов 85 байт
    Код (Text):
    1. movd     xmm0,eax
    2. shufps   xmm0,xmm0,0
    3. mov      cl,4
    4. rol      eax,cl
    5. push     eax
    6. rol      eax,cl
    7. push     eax
    8. rol      eax,cl
    9. push     eax
    10. rol      eax,cl
    11. push     eax
    12. movups   xmm1,[esp]
    13. xorps    xmm0,xmm1
    14. movaps   xmm1,xmm0
    15. psllq    xmm1,2
    16. orps     xmm0,xmm1
    17. movaps   xmm1,xmm0
    18. psllq    xmm1,1
    19. orps     xmm0,xmm1
    20. movaps   xmm1,xmm0
    21. psllq    xmm1,4
    22. andps    xmm0,xmm1
    23. pmovmskb eax,xmm0
    24. add      esp,16
    25. add      ax,1
    26. sbb      eax,eax
     
  3. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    murder, mov cl,4 в конечном итоге спасает 2 байта, что не так принципиально;
    можете пустить коммент по коду: интересно?
     
  4. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    У нас не sse4.1 - не проверю:
    Код (Text):
    1.         rol     eax,4
    2.         pinsrd  xmm1,eax,3
    3.         rol     eax,4
    4.         pinsrd  xmm1,eax,2
    5.         rol     eax,4
    6.         pinsrd  xmm1,eax,1
    7.         rol     eax,4
    8.         pinsrd  xmm1,eax,0
     
  5. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    sizeof(pinsrd xmm,xmm,imm8)=6 <-ого
     
  6. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    edemko
    Там в принципе то же, что и в #93

    Приводим регистры к виду

    eax = 87654321h
    xmm0 = 87654321876543218765432187654321h
    xmm1 = 76543218654321875432187643218765h

    Потом ксорим xmm0 c xmm1 и находим нулевые тетрады.
     
  7. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    меня прет
     
  8. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    Код (Text):
    1. mov     eax,$87654321 ; пример без совпадений
    2.  
    3. movd     xmm0,eax     ; $87654321
    4. shufps   xmm0,xmm0,0  ; $87654321'87654321'87654321'87654321
    5. mov      cl,4
    6. rol      eax,cl       ; $76543218
    7. push     eax
    8. rol      eax,cl       ; $65432187
    9. push     eax
    10. rol      eax,cl       ; $54321876
    11. push     eax
    12. rol      eax,cl       ; $43218765
    13. push     eax
    14. movups   xmm1,[esp]   ; $76543218'65432187'54321876'43218765
    15. add      esp,16       ; стек дальше не используем
    16. xorps    xmm0,xmm1    ; $87654321'87654321'87654321'87654321
    17.                       ; $76543218'65432187'54321876'43218765
    18.                       ; xor-тетрады 8(остальные аналогично):
    19.                       ;  7      1 6     2  5    3   4   4
    20.  
    21. /*                    ; дальше пошел спать
    22. movaps   xmm1,xmm0
    23. psllq    xmm1,2
    24. orps     xmm0,xmm1
    25. movaps   xmm1,xmm0
    26. psllq    xmm1,1
    27. orps     xmm0,xmm1
    28. movaps   xmm1,xmm0
    29. psllq    xmm1,4
    30. andps    xmm0,xmm1
    31. pmovmskb eax,xmm0
    32. add      ax,1
    33. sbb      eax,eax
    34. */
     
  9. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Код (Text):
    1. movaps   xmm1,xmm0
    2. psllq    xmm1,2    ;Совмещаем старшую половину каждой тетрады с младшей
    3. orps     xmm0,xmm1 ;получаем пары битов (3 or 1, 2 or 0)
    4. movaps   xmm1,xmm0
    5. psllq    xmm1,1    ;Совмещаем старшую половину каждой пары с младшей
    6. orps     xmm0,xmm1 ;получаем логическую сумму битов тетрады 3 or 1 or 2 or 0
    7.                    ;Таким образом если тетрада равна 0, то получаем 0 иначе 1
    8. movaps   xmm1,xmm0
    9. psllq    xmm1,4    ;совмещаем суммы так, чтобы они оказались в старшем бите
    10. andps    xmm0,xmm1 ;Если одна из сумм равна 0, то в старшем бите одного из байтов окажется 0
    11. pmovmskb eax,xmm0
    12. add      ax,1      ;если ax=-1, то eax=-1
    13. sbb      eax,eax   ;иначе eax=0
     
  10. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Мастер! Работает, я проверил :) Я то алгоритм поиска нулевых тетрад взял по аналогии с алгоритмом Фогнера, для поиска конца строки. А вот, что можно проверять не старший, а младший бит тетрады не додумался.
     
  11. Medstrax

    Medstrax Забанен

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    673
    56 байт, чуть улучшенный код Black_Mirror'а
    Код (Text):
    1.  
    2.         xor edx,edx
    3.         mov cl,4
    4.         bts edx,eax
    5. repeat 7
    6.         shr eax,cl
    7.         bts edx,eax
    8. end repeat
    9.         shrd eax,edx,16
    10.         and eax,edx
    11.         popcnt eax,eax
    12.         ror eax,cl
    13.         cdq
    14.         xchg eax,edx
     
  12. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    medstrax1
    и оно работает?! если and eax,edx даёт не 0, значит были совпадающие тетрады, мне кажется далее должен быть dec eax, а не ror, но тогда получается 55 байт
     
  13. Medstrax

    Medstrax Забанен

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    673
    Да, код действительно нерабочий, сори, поторопился. Правильнее будет вместо
    shrd eax,edx,16
    and eax,edx
    писать
    shld eax,edx,16
    xor eax,edx
    cwde
    Увы, те же 57 байт... ;)
     
  14. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Мой вариант, пока 66 (65 - edited) байт - работаю над инициализацией...

    Код (Text):
    1.   ; EAX - DWORD with 8 nibbles
    2.   ; result: eax is 0 if there are at least two the same nibbles - -1 overwise
    3.   ; Part I: convert nibbles into bytes and create temp array on stack
    4. @@IsSameNibbles:
    5.   mov  ebx,eax
    6.   mov  ecx,0F0F0F0Fh
    7.   shr  ebx,4
    8.   and  ebx,ecx
    9.   and  eax,ecx
    10.   mov  esi,esp
    11.   mov  edi,esp
    12.   push 7*2
    13.   pop  ecx
    14.   std
    15.   stosd
    16.   xchg eax,ebx
    17.   stosd
    18.   rep  movsd
    19.   cld
    20.   stosd ; any junk
    21.   stosd ; any junk
    22.   dec  ecx
    23.   ; Part II: try to find each nibble in next "array"
    24. @@IsSameNibbles2:
    25.   lodsb
    26.   inc  edi
    27.   repne scasb
    28.   lodsb
    29.   inc  edi
    30.   repne scasb
    31.   lodsb
    32.   inc  edi
    33.   repne scasb
    34.   lodsb
    35.   inc  edi
    36.   repne scasb
    37.   lodsb
    38.   inc  edi
    39.   repne scasb
    40.   lodsb
    41.   inc  edi
    42.   repne scasb
    43.   lodsb
    44.   inc  edi
    45.   repne scasb
    46.   ; Obtain result
    47. @@IsSameNibbles3:
    48.   inc  edi
    49.   sub  edi,esp
    50.   cmc
    51.   sbb  eax,eax
    52. @@IsSameNibbles4:
     
  15. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Пока что только достиг 59 байт...

    Код (Text):
    1.   ; EAX - DWORD with 8 nibbles
    2.   ; result: eax is 0 if there are at least two the same nibbles - -1 overwise
    3.   ; Part I: convert nibbles into bytes and create temp array on stack
    4.   push 7*2+1
    5.   mov  edi,esp
    6.   pop  ecx
    7.   mov  esi,edi
    8.   std
    9.   stosd
    10.   and  eax,0F0F0F0F0h
    11.   xor  [esi],eax
    12.   shr  eax,4
    13.   stosd
    14.   rep  movsd
    15.   cld
    16.   dec  ecx
    17.   ; Part II: try to find each nibble in next "array"
    18.   lodsb
    19.   mov  edi,esi ; Initialization
    20.   repne scasb
    21.   lodsb
    22.   inc  edi
    23.   repne scasb
    24.   lodsb
    25.   inc  edi
    26.   repne scasb
    27.   lodsb
    28.   inc  edi
    29.   repne scasb
    30.   lodsb
    31.   inc  edi
    32.   repne scasb
    33.   lodsb
    34.   inc  edi
    35.   repne scasb
    36.   lodsb
    37.   inc  edi
    38.   repne scasb
    39.   ; Obtain result
    40.   inc  edi
    41.   sub  edi,esp
    42.   cmc
    43.   sbb  eax,eax