Tiny code: CRC, Gnome Sort, Counter Sort etc…

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

• CRC-32

         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:

• Сортировка счётчиком двухбайтовых значений

      xor    eax, eax                ; обнулим аккумулятор       mov    esi, array              ; адрес массива сортируемых чисел       mov    edi, esi                ; адрес массива сортируемых чисел       mov    ebx, count              ; массив счётчиков       mov    ecx, (count-array)/2    ; длина массива @@:   lodsw                          ; загружаем число       inc    dword [ebx+eax*4]       ; увеличиваем счётчик повторений       loop   @B                      ; повторим пока не посчитаем все числа       xor    eax, eax                ; обнулим аккумулятор sort: mov    ecx, dword [ebx+eax*4]  ; считываем счётчик текущего числа       rep    stosw                   ; сохраняем текущее число с учётом счётчикаа @@:   inc    ax                      ; увеличиваем число       jne    sort                    ; повторяем пока не пройдёмся по всем числам       ret                            ; выходим array: dw 2,7,2,54,8842,12345,45,0 count: dd 65536 dup (0)