Blog. Just Blog

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

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

Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

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

Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта, он же классический "КМП-алгоритм" - один из самых эффективных алгоритмов поиска подстроки в строке. Оптимизация достигается за счет того, что при возникновении несоответствия само искомое слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Скорость работы алгоритма линейно зависит от объема входных данных, то есть невозможно разработать более эффективный алгоритм с точки зрения вычислительной сложности.

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

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

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
Как и с любыми другими разновидностями пузырьковой сортировки, время выполнения сильно зависит от упорядоченности исходного массива и от количества элементов в нем. Но в любом случае при сортировке перемешиванием сумма сравнений одинакова с пузырьковой сортировкой, а сумма обменов меньше.

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

Запись в архивы 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. Но это создает проблемы в основном при чтении имеющегося архива, тогда как при записи можно позволить себе определенные упрощения, зафиксировав размер некоторых полей.

Читать статью целиком »
Просмотров: 361 | Комментариев: 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
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время потребуется для выполнения сортировки. Также на время выполнения влияет исходная упорядоченность массива.

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

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

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

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

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

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

prev 01 02 03 04 05 06 07 08 09 ... 72
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 3 (0.0132 сек.) / Память: 4.5 Mb
Наверх