Как стать автором
Обновить

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

Время на прочтение2 мин
Количество просмотров2.2K

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

  • 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)
Теги:
Хабы:
Всего голосов 8: ↑8 и ↓0+8
Комментарии2

Публикации

Истории

Ближайшие события