Tiny code: CRC, Gnome Sort etc…25.11.2021 03:02

025224aa136f422502f58a7399582310

В этой статье представлены некоторые известные алгоритмы, которые как смог, переработал до крошечного вида. Данные образцы оптимизированы по размеру, но не по скорости выполнения.

         mov esi, text           ; адрес начала строки
         mov ecx, 6              ; длина строки
         xor eax, eax            ; инициализация линии задержки единицами
         dec eax                 ; выставляем все биты в 1
loading: xor al, [esi]           ; складываем по модулю 2, символ с линией
         inc esi                 ; получаем адрес следующего символа
         mov ebx, 8              ; будем сдвигать восемь бит
b8:      shr eax, 1              ; сдвиг вправо на 1 бит
         jnc @f                  ; пропустим если младший бит не выпал
         xor eax, 0EDB88320h     ; складываем линию с полиномом
@@:      dec ebx                 ; счётчик битов уменьшаем на 1
         jnz b8                  ; повторим сдвиг битов
         loop loading            ; повторим действие со следующим символом
         not eax                 ; инверсия результата
         ret                     ; выходим
         
text: db "CRC-32"

  • CRC-64 ECMA 182

      xor eax, eax                 ; инициализация лини задержки нулями
      mov rsi, text                ; адрес начала строки
      mov ebx, 14                  ; длина строки
      mov rdx, 42F0E1EBA9EA3693h   ; зеркальный полином
ld:   mov ecx, 8                   ; число бит в байте
      bswap rax                    ; переворачиваем линию
      xor al, byte [esi]           ; складываем по модулю 2, линию и символ
      inc esi                      ; адрес следующего символа
      bswap rax                    ; возвращаем линию 
shf:  shl rax, 1                   ; сдвигаем линию вправо на 1 бит
      jnc @f                       ; младший бит выпал?
      xor rax, rdx                 ; да, складываем полином с линией задержки
@@:   loop shf                     ; нет, повторим сдвиг оставшихся битов
      dec ebx                      ; уменьшаем счётчик оставшихся символов на 1
      jnz ld                       ; повторим цикл со следующим символом
      ret                          ; выходим, если символы закончились

text: db "CRC64_ECMA_182"
      mov    esi, array          ; адрес начала сортируемых однобайтовых данных  
      mov    edi, esi            ; дублируем адрес
next: inc    edi                 ; увеличиваем адрес для следующего символа
back: mov    ax, [esi]           ; берём два смежных символа
      cmp    al, ah              ; сравниваем их
      cmovbe esi, edi            ; если они отсортированы, будем брать следующий
      jbe    next                ; переход, если уже отсортированы
      cmp    edi, last           ; сравниваем текущий адрес с концом массива
      jae    exit                ; выходим, если дошли до последнего байта
      xchg   al, ah              ; обменяем местами 2 неотсортированных байта
      mov    [esi], ax           ; сохраним их
      dec    esi                 ; будем шагать на один символ назад
      jmp    back                ; повторим цикл
exit: ret                        ; выходим

db 0
array: db "Gnome optimized sort algorithm"
last:

© Habrahabr.ru