Blog. Just Blog

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

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

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

26.05.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
Сортировка перемешиванием, она же шейкерная или двунаправленная сортировка - оптимизированная разновидность алгоритма пузырьковой сортировки. В процессе сортировки выполняется многократный проход по массиву, соседние элементы сравниваются и, в случае необходимости, меняются местами. Массив просматривается поочередно справа налево и слева направо, из-за этого алгоритм получил свое название. В результате каждого прогона крупные и мелкие элементы массива поочередно перемещаются в конец и начало массива соответственно. Границы рабочей части массива, то есть той части массива, где происходит движение, устанавливаются в месте последнего обмена на каждой итерации.
  1. ;----------------------------------------------------------------
  2. ; Функция сортировки массива DWORD перемешиванием
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc shaker_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         mov     esi,[lpArray]
  13.         ; left
  14.         mov     eax,1
  15.         ; right
  16.         mov     ebx,[dLen]
  17.         cmp     ebx,2
  18.         jb      .loc_ret
  19.  
  20.         dec     ebx
  21.  
  22. .loc_loop_main:
  23.         ; swap_flag = false
  24.         xor     edi,edi
  25.  
  26.         mov     ecx,eax
  27. .loc_loop_1:
  28.         cmp     ecx,ebx
  29.         ja      .loc_done_1
  30.  
  31.         mov     edx,dword [esi+ecx*4-4]
  32.         cmp     dword [esi+ecx*4],edx
  33.         ; Для сортировки по возрастанию заменить на ja
  34.         jna     @f
  35.  
  36.         push    dword [esi+ecx*4-4]
  37.         push    dword [esi+ecx*4]
  38.         pop     dword [esi+ecx*4-4]
  39.         pop     dword [esi+ecx*4]
  40.  
  41.         ; swap_flag = true
  42.         inc     edi
  43. @@:
  44.         inc     ecx
  45.         jmp     .loc_loop_1
  46. .loc_done_1:
  47.         dec     ebx
  48.  
  49.         mov     ecx,ebx
  50. .loc_loop_2:
  51.         cmp     ecx,eax
  52.         jb      .loc_done_2
  53.  
  54.         mov     edx,dword [esi+ecx*4]
  55.         cmp     dword [esi+ecx*4-4],edx
  56.         ; Для сортировки по возрастанию заменить на jb
  57.         jnb     @f
  58.  
  59.         push    dword [esi+ecx*4-4]
  60.         push    dword [esi+ecx*4]
  61.         pop     dword [esi+ecx*4-4]
  62.         pop     dword [esi+ecx*4]
  63.  
  64.         ; swap_flag = true
  65.         inc     edi
  66. @@:
  67.         dec     ecx
  68.         jmp     .loc_loop_2
  69. .loc_done_2:
  70.         inc     eax
  71.  
  72.         or      edi,edi
  73.         jnz     .loc_loop_main
  74.  
  75. .loc_ret:
  76.         popa
  77.         ret
  78. endp
Как и с любыми другими разновидностями пузырьковой сортировки, время выполнения сильно зависит от упорядоченности исходного массива и от количества элементов в нем. Но в любом случае при сортировке перемешиванием сумма сравнений одинакова с пузырьковой сортировкой, а сумма обменов меньше.

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

Запись в архивы RAR5 без помощи архиватора

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

Формат RAR5 появился с выходом 5-й версии архиватора WinRAR. Он очень сильно отличается от старого формата архивов RAR, изменились структуры заголовков, появились дополнительные поля, некоторые поля вовсе исчезли, превратившись в самостоятельные блоки данных. Одним из главных нововведений, которое приходится учитывать, это появление данных так называемого формата vint - "variable length integer". Это последовательности байт заранее неизвестной длины в количестве от 1 до 10, чего достаточно для манипуляций с 64-битными числами. Как написано в документации, если понадобится, то максимальная длина последовательностей может быть увеличена. Каждый байт последовательности vint имеет только 7 младших значащих битов, старший 8-й бит является информационным. Если он равен 1, то требуется обрабатывать следующий байт последовательности, если 0, то это последний байт данных в текущей последовательности. Оставшиеся значащие биты слепляются в полноценные байты, из которых формируется итоговое целочисленное значение.

100011010 01011011 => 000001101 01011011
В некоторых случаях я могу оправдать такой подход, например, размер файла может быть как несколько терабайт, так и несколько байт, длина vint-последовательности для хранения таких значений будет разной. Хотя и тут можно поспорить, я не думаю, что размер бытовых файлов не поместится в 64-битное число, а для архивирования петабайт данных этих ваших интернетов наверняка есть какие-то более другие решения. Если взять всякую мелочевку типа флагов, идентификатора заголовка, атрибутов файла и подобного, почему нельзя было оставить фиксированные значения? Вряд ли автор совершит столь большие прорывы в разработке WinRAR, что понадобится QWORD для флагов или WORD для типов заголовков. А в документации сплошь и рядом поля формата vint. Но это создает проблемы в основном при чтении имеющегося архива, тогда как при записи можно позволить себе определенные упрощения, зафиксировав размер некоторых полей.

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

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

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

Алгоритм работает следующим образом. Массив разделяется на две части: отсортированную (в начале пустая) и неотсортированную. На каждом шаге выбирается элемент из неотсортированной части массива. Этот элемент вставляется в отсортированную часть массива так, чтобы отсортированная часть оставалась упорядоченной. Граница между отсортированной и неотсортированной частями смещается, и процесс повторяется для оставшихся элементов. После выполнения всех шагов весь массив становится отсортированным.
  1. ;----------------------------------------------------------------
  2. ; Функция сортировки массива DWORD методом вставок
  3. ; by ManHunter / PCL (www.manhunter.ru)
  4. ;----------------------------------------------------------------
  5. ; Параметры:
  6. ;   lpArray - указатель на массив DWORD
  7. ;   dLen - количество элементов в массиве
  8. ;----------------------------------------------------------------
  9. proc insertion_sort lpArray:DWORD, dLen:DWORD
  10.         pusha
  11.  
  12.         mov     esi,[lpArray]
  13.  
  14.         mov     ecx,[dLen]
  15.         xor     edi,edi
  16.         inc     edi
  17. .loc_loop_1:
  18.         mov     ebx,dword [esi+edi*4]
  19.  
  20.         mov     edx,edi
  21.         dec     edx
  22. .loc_loop_2:
  23.         cmp     edx,0
  24.         jb      @f
  25.         cmp     dword [esi+edx*4],ebx
  26.         jbe     @f
  27.  
  28.         push    dword [esi+edx*4+4]
  29.         push    dword [esi+edx*4]
  30.         pop     dword [esi+edx*4+4]
  31.         pop     dword [esi+edx*4]
  32.  
  33.         dec     edx
  34.         jmp     .loc_loop_2
  35. @@:
  36.         mov     dword [esi+edx*4+4],ebx
  37.  
  38.         inc     edi
  39.         cmp     edi,ecx
  40.         jb      .loc_loop_1
  41. .loc_ret:
  42.         popa
  43.         ret
  44. endp
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время потребуется для выполнения сортировки. Также на время выполнения влияет исходная упорядоченность массива.

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

Получение названий трекерных композиций на Ассемблере

01.05.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter

Получение названий трекерных композиций на Ассемблере

Трекерная музыка занимает промежуточное место между цифровым звуком и нотной записью. Она популярна еще со времен MS-DOS, ее часто используют при оформлении различных патчей и кейгенов, а также в демосцене. Как правило, внутренний формат у этих музыкальных файлов не очень сложный и потому не поддерживает привычные метаданные. Тем не менее, информация о названии трека в них чаще всего содержится. В этой статье я расскажу, как можно извлечь эту информацию из наиболее популярных форматов трекерных композиций.

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

Тюнингуем контрол msctls_trackbar32

28.04.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter
За время существования этого сайта тут было доработано уже несколько различных стандартных элементов управления, настало время провести тюнинг контрола msctls_trackbar32. Создается он обычным образом, например, через прописывание в ресурсах. Обязательно надо добавить в импорт библиотеку comctl32.dll и вызвать функцию InitCommonControls. Ну а поскольку мы будем добавлять к контролу различные нестандартные функции, то и делать это будем в специально отведенной процедуре-обработчике. Для этого воспользуемся субклассированием. Действия стандартные, примеров субклассирования на этом сайте предостаточно.
  1.         ; Настройки ползунка
  2.         invoke  GetDlgItem,[hwnddlg],IDC_PROGRESS
  3.         mov     [track],eax
  4.  
  5.         ; Установить наш собственный обработчик
  6.         invoke  SetWindowLong,[track],GWL_WNDPROC,TrackProc
  7.         ; Сохранить хэндл предыдущего обработчика
  8.         invoke  SetWindowLong,[track],GWL_USERDATA,eax
Теперь немного расскажу о расширенном функционале, который будет добавлен к ползунку. Во-первых, мне не нравится рамка, которая появляется при получении фокуса контролом. Конечно, это вроде как стандартное поведение, вроде так и должно быть, но мне все равно не нравится. Во-вторых, мне не нравится поведение ползунка при прокрутке контрола колесиком мыши. Лично я считаю, что поворот колесика мыши вперед должно увеличивать прогресс чего-либо, а поворот назад, соответственно, уменьшать. Стандартное же поведение ползунка ровно противоположное. Ну и третье, главное, что клик на полоске не переносит ползунок точно в эту позицию, а только сдвигает его на установленный шаг в указанном направлении.

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

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