Перестановка бит

Тема в разделе "WASM.ASSEMBLER", создана пользователем sarin, 2 май 2018.

Метки:
  1. sarin

    sarin Member

    Публикаций:
    0
    Регистрация:
    2 июн 2005
    Сообщения:
    30
    Имеем 32-битное значение abcdabcd abcdabcd abcdabcd abcdabcd,
    где a,b,c,d = биты 0 или 1.
    Нужно преобразовать в aaaaaaaa bbbbbbbb cccccccc dddddddd.
    Интересуют варианты для 32- и 16-битного кода.
    Делалость это поочередным сдвигом - RCR/RCL с использованием разных регистров.
    Каки есть ещё варианты? Как это можно сделать наиболее быстро?
     
  2. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    sarin,

    Таблицей зашить, эффективнее варианта нет.
     
  3. acckiitvar

    acckiitvar Member

    Публикаций:
    0
    Регистрация:
    26 сен 2011
    Сообщения:
    71
    Если я вас правильно понял, то есть некий паттерн из 4 бит повторный восемь раз? Тогда взять его и заполнить по нему регистр.
     
  4. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Не, человек, как понимаю, имеет в виду упакованые биты.
    a0 b0 c0 d0 a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3 a4 b4 c4 d4 a5 b5 c5 d5 a6 b6 c6 d6 a7 b7 c7 d7

    Путь это хранится здесь:
    uint32_t x;

    Делаем раз: x = (x & 0xa5a5a5a5) | ((x & 0x0a0a0a0a) << 3) | ((x & 0x50505050) >> 3);

    Получаем: a0 a1 c0 c1 b0 b1 d0 d1 a2 a3 c2 c3 b2 b3 d2 d3 a4 a5 c4 c5 b4 b5 d4 d5 a6 a7 c6 c7 b6 b7 d6 d7

    Делаем два: x = (x & 0xcc33cc33) | ((x & 0x33003300) >> 4) | ((x & 0x00cc00cc) << 4);

    Получаем: a0 a1 a2 a3 b0 b1 b2 b3 c0 c1 c2 c3 d0 d1 d2 d3 a4 a5 a6 a7 b4 b5 b6 b7 c4 c5 c6 c7 d4 d5 d6 d7

    Делаем три: x = (x & 0xf0f00f0f) | ((x & 0x0f0f0000) >> 8) | ((x & 0x0000f0f0) << 8);

    Получаем: a0 a1 a2 a3 a4 a5 a6 a7 c0 c1 c2 c3 c4 c5 c6 c7 b0 b1 b2 b3 b4 b5 b6 b7 d0 d1 d2 d3 d4 d5 d6 d7

    Ну и последний шаг: x = (x & 0xff0000ff) | ((x & 0x00ff0000) >> 8) | ((x & 0x0000ff00) << 8);

    Получаем: a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7 c0 c1 c2 c3 c4 c5 c6 c7 d0 d1 d2 d3 d4 d5 d6 d7

    Должно быть всё ОК, если где-то с масками не налажал.
     
    acckiitvar и Mikl___ нравится это.
  5. sarin

    sarin Member

    Публикаций:
    0
    Регистрация:
    2 июн 2005
    Сообщения:
    30
    // DOS, 16-bit code, 286+ CPU

    Код (ASM):
    1. Lodsw ; Mov Bx,Ax
    2.  Lodsw ; Mov Cx,Ax
    3.  
    4.   mov ax,bx
    5.   shr bx,3
    6.   xor bx,ax
    7.   and bx,0x0a0a
    8.   xor ax,bx
    9.   shl bx,3
    10.   xor bx,ax
    11.  
    12.   mov ax,cx
    13.   shr cx,3
    14.   xor cx,ax
    15.   and cx,0x0a0a
    16.   xor ax,cx
    17.   shl cx,3
    18.   xor cx,ax
    19.  
    20.   mov ax,bx
    21.   shr bx,10
    22.   xor bx,ax
    23.   and bx,0x0033
    24.   xor ax,bx
    25.   shl bx,10
    26.   xor bx,ax
    27.  
    28.   mov ax,cx
    29.   shr cx,10
    30.   xor cx,ax
    31.   and cx,0x0033
    32.   xor ax,cx
    33.   shl cx,10
    34.   xor cx,ax
    35.  
    36.   mov ax,cx
    37.   shr cx,4
    38.   xor cx,bx
    39.   and cx,0x0f0f
    40.   xor bx,cx
    41.   shl cx,4
    42.   xor cx,ax
    На выходе в BX:CX переставленная "как надо" строка.
     
    Последнее редактирование модератором: 28 май 2018
  6. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    BMI2 не подойдёт? :)

    Код (ASM):
    1.         ; source in EAX
    2.         mov ecx,11111111h
    3.         pext ebx,eax,ecx
    4.         shrd edx,ebx,8
    5.         shl ecx,1
    6.         pext ebx,eax,ecx
    7.         shrd edx,ebx,8
    8.         shl ecx,1
    9.         pext ebx,eax,ecx
    10.         shrd edx,ebx,8
    11.         shl ecx,1
    12.         pext ebx,eax,ecx
    13.         shrd edx,ebx,8
    14.         ; result in EDX
     
  7. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    Ну или так (чуток быстрее будет за счёт меньшего кол-ва shrd):
    Код (ASM):
    1.         ; source in EAX
    2.         mov ecx,22222222h
    3.         pext ebx,eax,ecx
    4.         shrd edx,ebx,8
    5.         shl ecx,1
    6.         pext ebx,eax,ecx
    7.         shrd edx,ebx,8
    8.         shl ecx,1
    9.         pext ebx,eax,ecx
    10.         shrd edx,ebx,8
    11.         mov ecx,11111111h  ; или shr ecx,3, но так дольше
    12.         pext eax,eax,ecx
    13.         or eax,edx
    14.         ; result in EAX
     
    Последнее редактирование: 28 май 2018
  8. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    Сдаётся мне, что автор напутал с буквами, и должно быть это так...
    дано: abcdefgh ijklmnop ABCDEFGH IJKLMNOP
    надо: aeimAEIM bfjnBFJN cgkoCGKO dhlpDHLP
    Угадал? :)

    p.s. Вообще, вариант с BMI2 можно ещё ускорить, если использовать esi, edi (возможно и ebp) и перетасовать используемые регистры, чтобы распараллелить работу.
    Но учтите, что это всё НЕ будет работать на компах более 5-летней давности (да и на более свежих, наверное, тоже не на каждом).
     
    Последнее редактирование: 28 май 2018
  9. sarin

    sarin Member

    Публикаций:
    0
    Регистрация:
    2 июн 2005
    Сообщения:
    30
    Возможна ошибка в формулировке задания но мой вариант для 16-битного кода 100% правильный.
    Вот неоптимизированный вариант. Здесь смысл сдвига должен быть понятнее.
    Код (ASM):
    1.  
    2. Lodsw // AX <- DS:[SI]
    3.  
    4. Rol Al,1 // AL to BX:CX
    5. Adc Ch,Ch
    6. Rol Al,1
    7. Adc Cl,Cl
    8. Rol Al,1
    9. Adc Bh,Bh
    10. Rol Al,1
    11. Adc Bl,Bl
    12. Rol Al,1
    13. Adc Ch,Ch
    14. Rol Al,1
    15. Adc Cl,Cl
    16. Rol Al,1
    17. Adc Bh,Bh
    18. Rol Al,1
    19. Adc Bl,Bl
    20.  
    21. Rol Ah,1 // AH to BX:CX
    22. Adc Ch,Ch
    23. Rol Ah,1
    24. Adc Cl,Cl
    25. Rol Ah,1
    26. Adc Bh,Bh
    27. Rol Ah,1
    28. Adc Bl,Bl
    29. Rol Ah,1
    30. Adc Ch,Ch
    31. Rol Ah,1
    32. Adc Cl,Cl
    33. Rol Ah,1
    34. Adc Bh,Bh
    35. Rol Ah,1
    36. Adc Bl,Bl
    37.  
    38. Lodsw // AX <- DS:[SI]
    39.  
    40. Rol Al,1 // AL to BX:CX
    41. Adc Ch,C
    42. Rol Al,1
    43. Adc Cl,Cl
    44. Rol Al,1
    45. Adc Bh,Bh
    46. Rol Al,1
    47. Adc Bl,Bl
    48. Rol Al,1
    49. Adc Ch,Ch
    50. Rol Al,1
    51. Adc Cl,Cl
    52. Rol Al,1
    53. Adc Bh,Bh
    54. Rol Al,1
    55. Adc Bl,Bl
    56.  
    57. Rol Ah,1 // AH to BX:CX
    58. Adc Ch,C
    59. Rol Ah,1
    60. Adc Cl,Cl
    61. Rol Ah,1
    62. Adc Bh,Bh
    63. Rol Ah,1
    64. Adc Bl,Bl
    65. Rol Ah,1
    66. Adc Ch,Ch
    67. Rol Ah,1
    68. Adc Cl,Cl
    69. Rol Ah,1
    70. Adc Bh,Bh
    71. Rol Ah,1
    72. Adc Bl,Bl
    73.  
    74. // Result in BX:CX
    75.  
    В первую очередь мне нужен именно 16-битный алгоритм. В идеале даже 8088/8086+ CPU.
     
    Последнее редактирование: 29 май 2018
  10. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    sarin, это всё, конечно, замечательно, но что у вас в BX:CX лежит изначально?
     
  11. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    Вот ещё вариант (должен быть быстрее вашего с rol, adc, ибо здесь 28 сдвигов против 32 в вашем коде):

    Код (ASM):
    1. ; source in AX
    2.  
    3. ; dddd
    4. mov dx,ax
    5. mov cx,ax
    6. and dx,0101h
    7. and cx,1010h
    8. shl dh,2
    9. shr cl,3
    10. shr ch,1
    11. or dx,cx
    12. or dl,dh
    13.  
    14. ; cccc
    15. mov bx,ax
    16. mov cx,ax
    17. and bx,0202h
    18. and cx,2020h
    19. shl bl,3
    20. ror bh,3
    21. shl ch,2
    22. or bx,cx
    23. or bl,bh
    24. or dl,bl
    25.  
    26. ; bbbb
    27. mov bx,ax
    28. mov cx,ax
    29. and bx,0404h
    30. and cx,4040h
    31. shr bl,2
    32. rol cl,3
    33. shr ch,3
    34. or bx,cx
    35. or bh,bl
    36. mov dh,bh
    37.  
    38. ; aaaa
    39. mov bx,ax
    40. mov cx,ax
    41. and bx,0808h
    42. and cx,8080h
    43. shl bl,1
    44. shr cl,2
    45. shl bh,3
    46. or bx,cx
    47. or bh,bl
    48. or dh,bh
    49.  
    50. ; result in DX

    Что-то я не очень понимаю, как из AX (16 бит) получилось BX:CX (32 бита)?
     
    Последнее редактирование: 29 май 2018
  12. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    А вот табличный метод (кстати, должен быть быстрее, при этом занимает меньше памяти).
    Код (ASM):
    1. ; source in AX
    2.  
    3. mov si,OFFSET Tbl
    4.  
    5. ; dddd
    6. mov bx,ax
    7. and bx,0Fh
    8. shl bx,1
    9. mov dx,[si+bx]
    10.  
    11. ; cccc
    12. shr al,3
    13. and al,not 1
    14. shr dx,1
    15. mov bl,al
    16. or dx,[si+bx]
    17.  
    18. ; bbbb
    19. mov bl,ah
    20. shr dx,1
    21. and bx,0Fh
    22. shl bx,1
    23. or dx,[si+bx]
    24.  
    25. ; aaaa
    26. shr ah,3
    27. and ah,not 1
    28. shr dx,1
    29. mov bl,ah
    30. or dx,[si+bx]
    31.  
    32. ; result in DX
    33.  
    34. Tbl DW 0000h, 0008h, 0080h, 0088h, 0800h, 0808h, 0880h, 0888h, 8000h, 8008h, 8080h, 8088h, 8800h, 8808h, 8880h, 8888h
    Это вариант с таблицей на 32 байта, но можно сделать и на 512 или даже 1024, будет быстрее.
     
  13. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    Вот так лучше всё же:
    Код (ASM):
    1. ; source in AX
    2.  
    3. mov dx,ax
    4. and ax,0F0F0h
    5. and dx,0F0Fh
    6. shr ax,3
    7. shl dx,1
    8. mov cx,ax
    9. ; CH:DH:CL:DL
    10.  
    11. xor bx,bx
    12. mov si,OFFSET Tbl
    13.  
    14. ; aaaa
    15. mov bl,ch
    16. mov ax,[si+bx]
    17.  
    18. ; bbbb
    19. shl ax,1
    20. mov bl,dh
    21. or ax,[si+bx]
    22.  
    23. ; cccc
    24. shl ax,1
    25. mov bl,cl
    26. or ax,[si+bx]
    27.  
    28. ; dddd
    29. shl ax,1
    30. mov bl,dl
    31. or ax,[si+bx]
    32.  
    33. ; result in AX
    34.  
    35. Tbl DW 0000h, 0001h, 0010h, 0011h, 0100h, 0101h, 0110h, 0111h, 1000h, 1001h, 1010h, 1011h, 1100h, 1101h, 1110h, 1111h
    Думаю, это наиболее оптимальный вариант... :)
     
    Последнее редактирование: 29 май 2018
  14. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    Прошу заметить, что AX как основной регистр для операция выбран намеренно, т.к. работа с ним быстрее, чем с другими регистрами (на 8086, по крайней мере).
    И адресация [si+bx] будет быстрее, чем [Tbl+bx].
    p.s. Что ж здесь идущие друг за другом сообщения не объединяются в одно? :meeting:
     
  15. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    18 команд, без дополнительной памяти. Вход - ax, выход - он же. Для вычислений используются ещё два регистра - dx и cx.

    Код (ASM):
    1.  
    2. mov dx, ax
    3. mov cx, ax
    4. and dx, 0x3300
    5. and cx, 0x00cc
    6. and ax, 0xcc33
    7. shr dx, 6
    8. shl cx, 6
    9. or ax, dx
    10. or ax, cx
    11.  
    12. mov dx, ax
    13. mov cx, ax
    14. and dx, 0x5050
    15. and cx, 0x0a0a
    16. and ax, 0xa5a5
    17. shr dx, 3
    18. shl cx, 3
    19. or ax, dx
    20. or ax, cx
    21.  
     
    Jin X нравится это.
  16. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    369
    Адрес:
    Кольца Сатурна
    SadKo, зачёт! :good:
    Но на 8086 будет 32 инструкции (shr dx,6 развернутся в 6 шт shr dx,1; аналогично shr cx,6 и пр.)
    Монжо упростить так:

    Код (ASM):
    1. mov dx, ax
    2. and dx, 0x33cc
    3. and ax, 0xcc33
    4. shl dh, 2
    5. shr dl, 2
    6. or al, dh
    7. or ah, dl
    8.  
    9. mov dx, ax
    10. mov cx, ax
    11. and dx, 0x5050
    12. and cx, 0x0a0a
    13. and ax, 0xa5a5
    14. shr dx, 3
    15. shl cx, 3
    16. or ax, dx
    17. or ax, cx
    16 инструкций (44 байта), а на 8086 будет 22 инструкции (52 байта) :)
     
    Последнее редактирование: 31 май 2018
    SadKo нравится это.