Blog. Just Blog

Образ мышления: Assembler

То, что не удается запрограммировать на Ассемблере, приходится паять
Образ мышления: Assembler - RSS-канал Образ мышления: Assembler - Карта сайта

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

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). На выходе получаем отсортированный массив указателей.

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

Рекурсивный обход дерева каталогов

19.01.2009 | Категория: Образ мышления: Assembler | Автор: ManHunter
Обход дерева каталогов является одной из классических прикладных задач на применение рекурсии. В Windows штатных API-функций для этого нет, поэтому поиск файлов выполняется при помощи пары API-функций FindFirstFile и FindNextFile. Совершенно непонятно, почему разработчики Windows не дали возможность точно настраивать критерии поиска, ограничившись только маской имени файла. Даже в MS-DOS для решения аналогичной задачи можно было задать по крайней мере атрибуты файлов, например для поиска только каталогов. Более расширенные возможности для поиска предоставляет API-функция FindFirstFileEx, но она доступна только в операционной системе Windows 2000 и выше.

Для рекурсивного обхода дерева каталогов я написал следующую функцию. Она сканирует дерево каталогов, начиная с указанного, и передает все найденные имена файлов в заданную функцию-обработчик. Все действия с найденными файлами выполняются уже в ней.
  1. ;------------------------------------------------------------------
  2. ; Функция рекурсивного обхода дерева каталогов
  3. ; (C) ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;
  6. ; Параметры вызова:
  7. ; lpFStr - указатель на начальный каталог без завершающего слеша.
  8. ;          он должен быть в буфере размером не менее MAX_PATH байт
  9. ; lpProc - указатель на callback-функцию для передачи имен файлов,
  10. ;          это обязательный параметр
  11. ; dFlag  - флаг "передавать в callback-функцию имена найденных
  12. ;          каталогов" (TRUE/FALSE)
  13. ;------------------------------------------------------------------
  14. proc    FindFileRecursive lpFStr:dword,lpProc:dword,dFlag:dword
  15.         local   hFind:DWORD     ; Локальный хэндл текущего поиска
  16.  
  17.         locals
  18.         FndData WIN32_FIND_DATA ; Локальная структура WIN32_FIND_DATA
  19.         endl
  20.  
  21.         ; Сохранить изменяемые регистры
  22.         push    ebx ecx edx
  23.  
  24.         ; Добавить к пути поиска '\*.*'
  25.         invoke  lstrcat,[lpFStr],ff_mask
  26.  
  27.         ; Найти первый файл
  28.         lea     eax,[FndData]
  29.         push    eax
  30.         invoke  FindFirstFile,[lpFStr]
  31.         ; В случае ошибки полностью прекратить дальнейшее сканирование
  32.         cmp     eax,INVALID_HANDLE_VALUE
  33.         jne     @f
  34.         xor     eax,eax
  35.         jmp     ff_exit
  36. @@:
  37.         ; Сохранить хэндл текущего поиска
  38.         mov     [hFind],eax
  39.  
  40. ff_chk_file:
  41.         ; Проверить имя файла на недопустимое
  42.         lea     eax,[FndData.cFileName]
  43.         push    eax
  44.         ; Имя файла '.'
  45.         invoke  lstrcmp,ff_skip1
  46.         or      eax,eax
  47.         ; Да, пропустить
  48.         jz      ff_next_file
  49.  
  50.         lea     eax,[FndData.cFileName]
  51.         push    eax
  52.         ; Имя файла '..'
  53.         invoke  lstrcmp,ff_skip2
  54.         or      eax,eax
  55.         ; Да, пропустить
  56.         jz      ff_next_file
  57.  
  58.         ; Если установлен флаг dFlag=TRUE, то передавать в callback-процедуру
  59.         ; все найденные результаты, в том числе и каталоги
  60.         cmp     [dFlag],0
  61.         jne     @f
  62.  
  63.         ; Установлен флаг передавать только файлы. Проверить атрибуты
  64.         ; найденного файла
  65.         mov     eax,[FndData.dwFileAttributes]
  66.         and     eax,FILE_ATTRIBUTE_DIRECTORY
  67.         ; Это каталог, пропустить
  68.         jnz     ff_do_not_callback
  69. @@:
  70.         ; Вычислить длину текущей строки поиска и обрезать '*.*'
  71.         invoke  lstrlen,[lpFStr]
  72.         sub     eax,3
  73.         add     eax,[lpFStr]
  74.         mov     byte [eax],0
  75.         push    eax
  76.  
  77.         ; Дописать к пути имя найденного файла или каталога
  78.         lea     eax,[FndData.cFileName]
  79.         push    eax
  80.         invoke  lstrcat,[lpFStr]
  81.         ; Передать имя файла в callback-функцию
  82.         stdcall [lpProc],[lpFStr]
  83.  
  84.         ; Вернуть маску поиска на место
  85.         pop     ecx
  86.         mov     dword [ecx],'*.*'
  87.  
  88.         ; Если callback-функция вернула 0, то прекратить сканирование
  89.         or      eax,eax
  90.         jz      ff_stop_scan
  91.  
  92.         ; Это каталог?
  93.         mov     eax,[FndData.dwFileAttributes]
  94.         and     eax,FILE_ATTRIBUTE_DIRECTORY
  95.         je      ff_next_file
  96.  
  97. ff_do_not_callback:
  98.         ; Вычислить длину текущей строки поиска и обрезать '*.*'
  99.         invoke  lstrlen,[lpFStr]
  100.         sub     eax,3
  101.         add     eax,[lpFStr]
  102.         mov     byte [eax],0
  103.         push    eax
  104.  
  105.         ; Дописать к пути имя найденного каталога
  106.         lea     eax,[FndData.cFileName]
  107.         push    eax
  108.         invoke  lstrcat,[lpFStr]
  109.  
  110.         ; Рекурсивный вызов поиска файлов в новом каталоге
  111.         stdcall FindFileRecursive,[lpFStr],[lpProc],[dFlag]
  112.  
  113.         ; Вернуть маску поиска на место
  114.         pop     ecx
  115.         mov     dword [ecx],'*.*'
  116.  
  117.         ; Если callback-функция вернула 0, то прекратить сканирование
  118.         or      eax,eax
  119.         jz      ff_stop_scan
  120.  
  121. ff_next_file:
  122.         ; Найти следующий файл
  123.         lea     eax,[FndData]
  124.         push    eax
  125.         invoke  FindNextFile,[hFind]
  126.         or      eax,eax
  127.         ; Файл найден, обработать его
  128.         jnz     ff_chk_file
  129.         ; По умолчанию установить флаг "продолжать сканирование"
  130.         mov     eax,TRUE
  131. ff_stop_scan:
  132.         ; Закрыть хэндл текущего поиска
  133.         push    eax
  134.         invoke  FindClose,[hFind]
  135.         pop     eax
  136. ff_exit:
  137.         ; Восстановить измененные регистры
  138.         pop     edx ecx ebx
  139.  
  140.         ; Возврат из процедуры.
  141.         ; Код возврата EAX=1 - продолжать сканирование, EAX=0 - стоп
  142.         ret
  143.  
  144. ff_mask  db '\*.*',0    ; Маска файлов для поиска
  145. ff_skip1 db '.',0       ; Запрещенное имя файла
  146. ff_skip2 db '..',0      ; Запрещенное имя файла
  147.  
  148. endp
Путь к начальному каталогу должен размещаться в буфере размером не менее определенного в системе MAX_PATH (обычно 256 символов). Обязательным параметром является адрес callback-функции RecursiveFindFileProc, которой поочередно передаются все результаты поиска. Флаг dFlag указывает, будут передаваться в callback-функцию все найденные результаты, включая каталоги, или же будут передаваться только найденные файлы. Код возврата из FindFileRecursive EAX=1 - сканирование было закончено, когда больше ни одного файла не было найдено, EAX=0 - сканирование завершилось аварийно или же было остановлено из callback-функции.

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

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

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

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

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

Запрет запуска нескольких копий программы

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

Первый способ основан на том, что в приложении можно определить расшаренную секцию, данные из которой будут доступны для всех его запущенных экземпляров. Достаточно прописать в ней некоторую переменную и присвоить ей уникальное значение. При старте выполняется проверка, и если значение переменной равно начальному, то считается что это старт первой копии, иначе приложение является второй копией и должно завершить свою работу. Поэтому первая копия приложения сразу после запуска и проверки должна заменить значение переменной на другое.
  1. ; Расшаренная секция, общая для всех копий данного приложения
  2. section '.shared' data readable writeable shareable
  3. started  dd  1       ; Флаг первого запуска
  4.  
  5. ; Сегмент кода
  6. section '.code' code readable executable
  7.         cmp     [started],1       ; Уже запущен экземпляр программы?
  8.         jne     already_started   ; Да, на выход
  9.         xor     eax,eax
  10.         ; Префикс LOCK и команда XCHG используются для предотвращения
  11.         ; возможных конфликтов на многопроцессорных машинах
  12.         lock xchg eax,[started]   ; Сбросить флаг
  13.         ; Нормальный запуск программы 
  14.         ...
  15. already_started:
  16.         ; Выход из программы
  17.         ...
Этот способ будет работать только если приложение запускается из одной и той же папки. Если скопировать его в другую папку, то система будет считать что это совершенно другое приложение и разрешит запуск его второй копии. Впрочем, способ с расшаренной секцией вполне имеет место быть, если требуется запретить именно запуск второй копии приложения из одной и той же папки. Для глобального запрета этот способ не подходит.

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

Задача на применение логических инструкций

16.12.2008 | Категория: Образ мышления: Assembler | Автор: ManHunter
Когда-то кому-то помогал с решением задачи на ассемблере, формулировка задания была такая:


Дан массив из 5 байт. Рассматривая его как массив из восьми 5-битных слов, посчитать количество слов с четным числом единиц в слове.


Алгоритм хитровывернутый, комментарии специально не прописывал, чтобы тупая и ленивая школота не смогла объяснить преподу, откуда взялось такое решение и как оно работает.
  1. ;---------------------------------------------------------------
  2. ; Задача на применение логических инструкций
  3. ;
  4. ; Дан массив из 5 байт. Рассматривая его как массив из восьми
  5. ; 5-битных слов, посчитать количество слов с четным числом
  6. ; единиц в слове.
  7. ;
  8. ; Решение: ManHunter / PCL
  9. ;---------------------------------------------------------------
  10.  
  11. format PE GUI 4.0
  12. entry start
  13.  
  14. include 'win32a.inc'
  15.  
  16. ;---------------------------------------------------------------
  17.  
  18. section '.data' data readable writeable
  19.  
  20. xbytes   db 00111000b ; Данные для задачки, взяты с потолка :)
  21.          db 11111110b
  22.          db 01010101b
  23.          db 00001001b
  24.          db 00000110b
  25.  
  26. mask     db 'Count: %i',13,10,13,10
  27.          db '%i%i%i%i%i - %i%i%i%i%i - %i%i%i%i%i - %i%i%i%i%i',13,10
  28.          db '%i%i%i%i%i - %i%i%i%i%i - %i%i%i%i%i - %i%i%i%i%i',13,10
  29.         db 0
  30.  
  31. title    db 'Solution',0
  32. tmp      rb 100
  33.  
  34. ;---------------------------------------------------------------
  35.  
  36. section '.code' code readable executable
  37. start:
  38.          mov     esi,xbytes+4
  39. loc_1:
  40.          lodsb
  41.          mov     ecx,8
  42. loc_2:
  43.          xor     edx,edx
  44.          test    al,00000001b
  45.          jz      loc_3
  46.          inc     edx
  47. loc_3:
  48.          push    edx
  49.          shr     al,1
  50.          loop    loc_2
  51.  
  52.          dec     esi
  53.          dec     esi
  54.          cmp     esi,xbytes
  55.          jnb     loc_1
  56.  
  57.          xor     eax,eax
  58.          xor     esi,esi
  59. loc_4:
  60.          xor     edi,edi
  61.          mov     ecx,5
  62. loc_5:
  63.          add     edi,[esp+eax*4]
  64.          inc     eax
  65.          loop    loc_5
  66.  
  67.          test    edi,edi
  68.          jz      loc_6
  69.          test    edi,1
  70.          jnz     loc_6
  71.          inc     esi
  72. loc_6:
  73.          cmp     eax,40
  74.          jb      loc_4
  75.  
  76.          invoke  wsprintf,tmp,mask,esi
  77.          add     esp,12+(8*5*4)
  78.  
  79.          invoke  MessageBox,HWND_DESKTOP,tmp,title,MB_OK
  80.          invoke  ExitProcess,0
  81.  
  82. ;---------------------------------------------------------------
  83.  
  84. section '.idata' import data readable writeable
  85.  
  86. library kernel32,"KERNEL32.DLL",\
  87.          user32,"USER32.DLL"
  88.  
  89. include "apia\kernel32.inc"
  90. include "apia\user32.inc"
Исходник и скомпилированный файл прилагаются.

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

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