Blog. Just Blog

Быстрый поиск

Введите фрагмент названия статьи для поиска

Сортировка массива строк на Ассемблере

29.01.2009 | Категория: Образ мышления: Assembler | Автор: ManHunter
Долго откладывал написание этой функции, но теперь вот прижало. Получилась функция сортировки массива произвольных текстовых строк в формате ASCIIZ усовершенствованным методом "пузырька". Усовершенствование заключается в том, что если при очередном проходе ни одной сортировки не было выполнено, то дальнейшая обработка массива прекращается. В некоторых случаях это дает значительный выигрыш в скорости работы. Однако, алгоритм сортировки "пузырьком" в любом случае является самым медленным, поэтому для очень больших массивов эта функция не подойдет. Но мне для больших объемов ее и не надо, на массиве из нескольких сотен или даже тысяч строк скорость работы функции меня вполне устраивает.
  1. ;------------------------------------------------------------------
  2. ; Функция сортировки массива строк
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;
  6. ; Сортировка выполняется усовершенствованным методом "пузырька"
  7. ; Параметры:
  8. ; lpArray - указатель на массив адресов строк
  9. ; dFlag   - метод сортировки: TRUE - по возрастанию,
  10. ;           FALSE - по убыванию
  11. ; На выходе:
  12. ; отсортированный согласно правилу массив адресов строк
  13. ;------------------------------------------------------------------
  14. proc    SortArray lpArray:dword, dFlag:dword
  15.         pusha
  16.  
  17.         ; Указатель на массив адресов строк
  18.         mov     esi,[lpArray]
  19.  
  20.         mov     ebx,[dFlag]
  21. sa_sort_1:
  22.         ; Проверка на 0 - признак окончания массива
  23.         mov     eax,[esi]
  24.         or      eax,eax
  25.         jz      sa_stop_sort
  26.  
  27.         or      bh,bh
  28.         jnz     sa_stop_sort
  29.  
  30.         ; Сравниваем, начиная со следующего элемента
  31.         lea     edi,[esi+4]
  32.  
  33.         ; Установить флаг, что сортировка не требуется,
  34.         ; если дальнейший остаток массива уже отсортирован
  35.         mov     bh,1
  36. sa_sort_2:
  37.         ; Следующий элемент 0 - массив закончился
  38.         mov     edx,[edi]
  39.         or      edx,edx
  40.         jz      sa_next_sort
  41.  
  42.         ; Сохранить текущие значения указателей
  43.         push    esi edi
  44.  
  45.         ; Указатели на строки
  46.         mov     esi,eax
  47.         mov     edi,edx
  48. sa_compare_string:
  49.         ; Сравнить символы в строках
  50.         mov     cl,byte [edi]
  51.         mov     ch,byte [esi]
  52.         ; Если символы равны, то сравнить следующие
  53.         cmp     cl,ch
  54.         je      sa_equal
  55.  
  56.         ; Проверка больше-меньше в зависимости от флага
  57.         cmp     bl,0
  58.         jz      @f
  59.  
  60.         cmp     cl,ch
  61.         ja      ss_next_string
  62.         jmp     sa_change_offs
  63. @@:
  64.         cmp     cl,ch
  65.         jb      ss_next_string
  66.  
  67. sa_change_offs:
  68.         ; Поменять местами адреса строк
  69.         xchg    eax,edx
  70.         ; Сбросить флаг, что сортировка не требуется
  71.         xor     bh,bh
  72.         jmp     ss_next_string
  73.  
  74. sa_equal:
  75.         ; Если закончилась строка, то перейти к следующей паре
  76.         or      cl,cl
  77.         jz      ss_next_string
  78.  
  79.         ; Перейти к следующей паре символов
  80.         inc     esi
  81.         inc     edi
  82.         jmp     sa_compare_string
  83.  
  84. ss_next_string:
  85.         ; Восстановить значения указателей и записать в них
  86.         ; значения адресов строк, без разницы изменившихся или нет
  87.         pop     edi esi
  88.         mov     [esi],eax
  89.         mov     [edi],edx
  90.  
  91.         ; Перейти к следующему элементу массива
  92.         add     edi,4
  93.         jmp     sa_sort_2
  94.  
  95. sa_next_sort:
  96.         ; Перейти к следующему элементу массива
  97.         add     esi,4
  98.         jmp     sa_sort_1
  99.  
  100. sa_stop_sort:
  101.         popa
  102.         ret
  103. endp
Сортировать сами строки в памяти слишком нерационально, поэтому для сортировки нам понадобится массив DWORD'ов с указателями на строки. Параметр lpArray - указатель на такой массив. Признак окончания массива - DWORD с нулевым значением. Параметр dFlag определяет в каком порядке будет отсортирован массив: по возрастанию (значение TRUE) или по убыванию (значение FALSE). На выходе получаем отсортированный массив указателей.

Читать статью целиком »
Просмотров: 16009 | Комментариев: 7

Функции base64 на Ассемблере

09.01.2009 | Категория: Образ мышления: Assembler | Автор: ManHunter
Алгоритм Base64 может использоваться в пользовательских почтовых приложениях, в качестве одного из уровней защиты шифрованием, для хранения двоичных данных и для решения многих других задачах. В большинстве языков высокого уровня используются штатные функции, в Ассемблере приходится все реализовывать самостоятельно.

Алгоритм Base64 использует две функции - кодирования данных и обратного декодирования. Для обеих функций кодирования и декодирования предварительно инициализируются следующие вспомогательные данные:
  1. section '.data' data readable writeable
  2. ...
  3. base64_table db "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  4.              db "abcdefghijklmnopqrstuvwxyz"
  5.              db "0123456789+/"
  6.  
  7. decode_table rb 100h
  8. ...
А вот сами функции для работы с Base64:
  1. ;---------------------------------------------------------------
  2. ; Функция кодирования Base64
  3. ; Параметры:
  4. ; dFrom - указатель на исходные данные
  5. ; dTo   - указатель на буфер для приема кодированных данных
  6. ; dSize - размер исходных данных
  7. ; Функция ничего не возвращает
  8. ;---------------------------------------------------------------
  9. proc    base64_encode dFrom:dword, dTo:dword, dSize:dword
  10.         push    eax ecx edx esi edi
  11.  
  12.         mov     esi,[dFrom]
  13.         mov     edi,[dTo]
  14.         mov     ecx,[dSize]
  15.  
  16.         or      ecx,ecx
  17.         jz      .r3
  18. .encode_loop:
  19.         lodsd
  20.         mov     edx,eax
  21.         cmp     ecx,3
  22.         jae     .remainder_ok
  23.         and     edx,0ffffh
  24.         cmp     ecx,2
  25.         jae     .remainder_ok
  26.         and     edx,0ffh
  27. .remainder_ok:
  28.         bswap   edx
  29.  
  30.         mov     eax,edx
  31.         shr     eax,26
  32.         and     eax,00111111b
  33.         mov     al,[base64_table+eax]
  34.         stosb
  35.  
  36.         mov     eax,edx
  37.         shr     eax,20
  38.         and     eax,00111111b
  39.         mov     al,[base64_table+eax]
  40.         stosb
  41.         dec     ecx
  42.         jz      .r2
  43.  
  44.         mov     eax,edx
  45.         shr     eax,14
  46.         and     eax,00111111b
  47.         mov     al,[base64_table+eax]
  48.         stosb
  49.         dec     ecx
  50.         jz      .r1
  51.  
  52.         mov     eax,edx
  53.         shr     eax,8
  54.         and     eax,00111111b
  55.         mov     al,[base64_table+eax]
  56.         stosb
  57.  
  58.         dec     esi
  59.         dec     ecx
  60.         jnz     .encode_loop
  61.  
  62.         jmp     .r3
  63. .r2:
  64.         mov     al,'='
  65.         stosb
  66. .r1:
  67.         mov     al,'='
  68.         stosb
  69. .r3:
  70.         xor     eax,eax
  71.         stosb
  72.         pop     edi esi edx ecx eax
  73.         ret
  74. endp
В этой функции все параметры обязательные. Размер буфера-приемника должен быть примерно в 1,5 раза больше исходных данных, это обусловлено особенностями алгоритма кодирования.

Читать статью целиком »
Просмотров: 4734 | Комментариев: 7

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

10.11.2008 | Категория: Образ мышления: Assembler | Автор: ManHunter
Для конвертирования строки в число я использую две функции. Первая предназначена для конвертирования строки десятичных цифр в число:
  1. ;----------------------------------------------------------
  2. ; На входе: указатель на строку
  3. ; На выходе: EAX = число или 0 если не получилось
  4. ;----------------------------------------------------------
  5. proc    str2dec lpStr:dword
  6.         push    ebx edx esi
  7.  
  8.         xor     eax,eax
  9.         mov     esi,[lpStr]
  10. .str2dec_loop:
  11.         movsx   ebx,byte [esi]
  12.         sub     bl,'0'
  13.         ; Для системы счисления с другим основанием замените следующую
  14.         ; строчку на cmp bl,основание_системы
  15.         cmp     bl,10
  16.         jnb     .str2dec_ret
  17.         ; Для системы счисления с другим основанием замените следующую
  18.         ; строчку на imul eax,основание_системы
  19.         imul    eax,10
  20.         add     eax,ebx
  21.         inc     esi
  22.         jmp     .str2dec_loop
  23.  
  24. .str2dec_ret:
  25.         pop     esi edx ebx
  26.         ret
  27. endp
Вторая функция похожа, но обрабатывает шестнадцатеричные цифры:

Читать статью целиком »
Просмотров: 13206 | Комментариев: 5

Вывод QWORD в виде десятичного числа

05.10.2008 | Категория: Образ мышления: Assembler | Автор: ManHunter
Для преобразования и форматированного вывода 32-битных значений в ассемблере используется стандартная API-функция wsprintf, но она бесполезна при работе с большими числами, например QWORD (64 бита). Значит обойдемся совсем без использования API.
  1. ;---------------------------------------------------
  2. ; Преобразование QWORD в десятичное число
  3. ; Параметры вызова:
  4. ; dwHigh - Старшее двойное слово
  5. ; dwLow  - Младшее двойное слово
  6. ; lpBuff - указатель на буфер-приемник
  7. ;---------------------------------------------------
  8. proc    bignum dwHigh:DWORD, dwLow:DWORD, lpBuff:DWORD
  9.         pushad                   ; Сохранить все регистры
  10.         mov     eax,[dwLow]      ; Младшее двойное слово
  11.         mov     edx,[dwHigh]     ; Старшее двойное слово
  12.         mov     edi,[lpBuff]     ; Указатель на буфер-приемник
  13.  
  14.         xchg    esi,edx          ; Сохранить старший dword
  15.         mov     ebx,10           ; Основание системы счисления
  16.         xor     ecx,ecx          ; Счетчик десятичных цифр
  17. .bignum_1:
  18.         xchg    eax,esi          ; Расчитать десятичную цифру
  19.         xor     edx,edx
  20.         div     ebx
  21.         xchg    esi,eax
  22.         div     ebx
  23.         or      dl,'0'           ; Преобразовать результат в символ цифры
  24.         push    edx              ; Сохранить цифру в стеке
  25.         inc     ecx              ; Увеличить счетчик цифр
  26.         or      eax,eax          ; Все преобразовали?
  27.         jnz     .bignum_1
  28.  
  29. .bignum_2:
  30.         pop     eax              ; Записать все цифры из стека в буфер
  31.         stosb
  32.         loop    .bignum_2
  33.         xor     eax,eax          ; Признак окончания строки
  34.         stosb
  35.         popad                    ; Восстановить все регистры
  36.         ret                      ; Ворзврат из процедуры
  37. endp
Пример использования:

Читать статью целиком »
Просмотров: 7849 | Комментариев: 4

Поиск строки в памяти с использованием маски

29.09.2008 | Категория: Образ мышления: Assembler | Автор: ManHunter
Для поиска произвольной строки в блоке памяти с использованием бинарной маски я написал следующую процедуру:
  1. ; ---------------------------------------------
  2. ; Процедура поиска строки в блоке памяти
  3. ; (C) ManHunter / PCL
  4. ; ---------------------------------------------
  5. ; SRCdata - блок памяти в котором выполняется поиск
  6. ; SRCsize - размер блока в котором выполняется поиск
  7. ; PTRdata - строка для поиска
  8. ; PTRsize - длина строки для поиска
  9. ; MSKdata - бинарная маска для поиска или 0 если не используется
  10. ;
  11. ; Возврат: EAX = offset найденной строки
  12. ;          EAX = -1 если ничего не найдено
  13. ; ---------------------------------------------
  14.  
  15. proc scanmem SRCdata:dword, SRCsize:dword, PTRdata:dword,\
  16.              PTRsize:dword, MSKdata:dword
  17.  
  18.         push    esi edi ebx ecx edx
  19.  
  20.         ; Длина паттерна больше длины данных?
  21.         mov     eax,[PTRsize]
  22.         cmp     eax,[SRCsize]
  23.         ; Да, возврат -1
  24.         ja      .scanmem_not_found
  25.  
  26.         mov     esi,[SRCdata]
  27.         mov     edi,[PTRdata]
  28.         mov     edx,[MSKdata]
  29.         mov     ebx,esi
  30.         add     ebx,[SRCsize]
  31.         sub     ebx,[PTRsize]
  32. .scanmem_loop:
  33.         xor     ecx,ecx
  34. .scanmem_test_char:
  35.         or      edx,edx
  36.         jz      .scanmem_no_mask
  37.         cmp     byte [edx+ecx],0
  38.         jz      .scanmem_char_equal
  39.  
  40. .scanmem_no_mask:
  41.         mov     al,[esi+ecx]
  42.         cmp     al,[edi+ecx]
  43.         jne     .scanmem_next_pattern
  44. .scanmem_char_equal:
  45.         inc     ecx
  46.         cmp     ecx,[PTRsize]
  47.         jb      .scanmem_test_char
  48.         jmp     .scanmem_found
  49. .scanmem_next_pattern:
  50.         inc     esi
  51.         cmp     esi,ebx
  52.         jbe     .scanmem_loop
  53.  
  54. .scanmem_not_found:
  55.         ; Строка не найдена
  56.         mov     eax,-1
  57.         jmp     .scanmem_ret
  58.  
  59. .scanmem_found:
  60.         ; Строка найдена
  61.         mov     eax,esi
  62.  
  63. .scanmem_ret:
  64.         pop    edx ecx ebx edi esi
  65.  
  66.         ret
  67. endp
Пример использования процедуры:

Читать статью целиком »
Просмотров: 5844 | Комментариев: 5

Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2020
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.11 сек. / MySQL: 3 (0.0419 сек.) / Память: 4.75 Mb
Наверх