Перейти к основному содержимому

Строковые инструкции и таблицы поиска

ОБЯЗАТЕЛЬНО
Разработчику

Контекст: x86/x86-64, NASM. Краткая таблица мнемоник есть в справочнике; здесь — как ими пользоваться осознанно.

Идея "строковых" команд​

Play ITЗагрузка интерактивного демо…

Группа инструкций с суффиксом B/W/D/Q (байт, слово, dword, qword) работает с парой адресов, заданных неявно:

РегистрРоль
RSI (или ESI, SI)источник — "откуда читаем"
RDI (или EDI, DI)приёмник — "куда пишем" или "что сканируем"
RCXсчётчик повторений (с префиксом REP)
AL / AX / EAX / RAXоперанд для STOS, SCAS, LODS

Одна мнемоника без REP выполняется один раз и сдвигает RSI/RDI на размер элемента. С префиксом REP / REPE / REPNE — в цикле, пока RCX ≠ 0 и (для E/NE) пока выполняется условие по ZF.

Эти инструкции особенно полезны, когда нужно писать компактный и понятный "побайтовый" код — копирование, сканирование, заполнение буфера, простые парсеры. Они не всегда абсолютные чемпионы по скорости, но часто дают хороший баланс между размером кода и читаемостью.

Направление — CLD и STD​

Play ITЗагрузка интерактивного демо…

Флаг DF (Direction Flag) в RFLAGS:

  • CLD — DF = 0: после операции RSI и RDI увеличиваются (обход вперёд).
  • STD — DF = 1: указатели уменьшаются (удобно при копировании с конца буфера).

Перед любым блоком строковых команд задайте направление явно, обычно CLD.

Копирование с конца буфера (когда области пересекаются):

; rsi = src, rdi = dst, rcx = count
    std
    mov rsi, src_end
    mov rdi, dst_end
    rep movsb
    cld                         ; вернуть DF=0 для последующего кода

Разбор:

  • std устанавливает Direction Flag: после movsb указатели уменьшаются.
  • src_end и dst_end — адреса после последнего байта (src + count, dst + count).
  • rep movsb копирует с конца в начало, как в memmove при перекрытии вперёд.
  • cld в конце обязателен: иначе следующие строковые инструкции пойдут "назад" по ошибке.
  • Без std/cld легко получить тихий баг в смешанном коде.

Копирование блока — MOVSB / MOVSD​

Эквивалент memcpy для непересекающихся областей:

; rsi = src, rdi = dst, rcx = байт (для movsb)
    cld
    rep movsb

Разбор:

  • Комментарий фиксирует входные данные — источник в RSI, приёмник в RDI, число байт в RCX.
  • cld сбрасывает Direction Flag, поэтому указатели двигаются вперёд.
  • rep movsb копирует по одному байту из [RSI] в [RDI], автоматически инкрементируя оба регистра.
  • Инструкция повторяется RCX раз, после чего RCX становится нулём.
  • Это компактный низкоуровневый эквивалент memcpy для непересекающихся областей.

Для выровненных блоков кратных 4 или 8 байтам быстрее rep movsd / rep movsq, если границы позволяют.

Современные CPU часто быстрее на mov из обычного цикла или внутренней memcpy libc из-за микрокода и предвыборки; строковые инструкции остаются компактными в коде и полезны в ядрах, загрузчиках и учебных примерах.

Заполнение буфера — STOSB​

; rdi = начало, rcx = длина, al = байт-заполнитель
    cld
    rep stosb

Разбор:

  • RDI указывает на начало заполняемой области памяти.
  • В AL хранится байт, которым будет заполнен буфер.
  • RCX задаёт количество повторений, то есть длину области в байтах.
  • cld включает движение вперёд по памяти.
  • rep stosb последовательно записывает AL в память и увеличивает RDI до полного заполнения.

Обнуление области: xor al, al + rep stosb.

Полная подготовка перед rep movsb:

section .bss
    buf_dst resb 64

section .rodata
    buf_src db 'copy me', 0

section .text
    lea rsi, [rel buf_src]
    lea rdi, [rel buf_dst]
    mov rcx, 7                  ; 7 байт без терминатора
    cld
    rep movsb

Разбор:

  • lea rsi, [rel buf_src] и lea rdi, [rel buf_dst] задают источник и приёмник.
  • mov rcx, 7 — явная длина копирования (не включает завершающий 0, если он есть).
  • cld фиксирует движение указателей вперёд.
  • После rep movsb в buf_dst лежат первые 7 байт строки 'copy me'.
  • RSI и RDI сдвинуты на 7, RCX обнулён — регистры "израсходованы" префиксом REP.

Обнуление буфера:

    lea rdi, [rel buf_dst]
    mov rcx, 64
    xor al, al
    cld
    rep stosb

Разбор:

  • xor al, al формирует заполнитель 0 быстрее, чем mov al, 0.
  • rep stosb записывает ноль в 64 байта подряд — аналог memset(buf, 0, 64).
  • После операции RDI указывает на байт сразу за концом буфера.

Длина C-строки — SCASB​

Поиск нулевого терминатора:

; rdi = строка, al = 0
    cld
    xor rcx, rcx
    not rcx              ; rcx = -1 (максимальный счёт)
    xor al, al
    repne scasb
    not rcx
    dec rcx              ; rcx = число байт до (не включая) '\0'

Разбор:

  • cld задаёт прямое направление сканирования строки.
  • xor rcx, rcx затем not rcx устанавливают RCX = -1, то есть максимально длинный лимит поиска.
  • xor al, al подготавливает искомый байт 0 (терминатор C-строки).
  • repne scasb сравнивает AL с байтами по адресу RDI и двигается вперёд, пока байты не совпадут.
  • После выхода RCX содержит остаток счётчика, поэтому not rcx и dec rcx преобразуют его в длину строки без \0.
  • Приём повторяет классический алгоритм strlen на строковых инструкциях x86.

REPNE SCASB останавливается, когда найден AL или исчерпан "длинный" счётчик.

Поиск символа в буфере​

; rdi = буфер, rcx = известная длина, al = '?'
    cld
    repne scasb
    je  .found
    ; не найдено (ZF=0 после repne scasb если не совпало на последнем)
.found:
    ; rdi указывает на байт *после* совпадения

Разбор:

  • Поиск ограничен известной длиной буфера в RCX, поэтому выход за границы исключается.
  • AL содержит искомый символ, например '?'.
  • repne scasb идёт по байтам, пока не найдёт совпадение или пока не обнулится счётчик.
  • je .found срабатывает только если установлен ZF=1, то есть совпадение найдено.
  • После нахождения RDI уже сдвинут на позицию после найденного байта, это важно для последующей логики.

Проверяйте ZF после REPNE: совпадение — ZF=1.

Сравнение двух блоков — CMPSB​

    cld
    repe cmpsb          ; пока равны и rcx > 0
    jne .not_equal

Разбор:

  • cmpsb сравнивает байт по [RSI] с байтом по [RDI] и продвигает оба указателя.
  • Префикс repe повторяет сравнение, пока байты равны (ZF=1) и RCX ещё не ноль.
  • Если найдено различие, ZF сбрасывается и цикл останавливается.
  • jne .not_equal переводит выполнение в ветку неравенства.
  • Если переход не выполнен, либо все байты равны, либо сравнение завершилось по лимиту RCX.

Таблица поиска (lookup table)​

Частая задача: по коду символа или индексу 0..255 получить значение из статической таблицы (классификация, шифр подстановки, палитра).

Подход 1 — явный индекс (64-бит):

section .rodata
    ; 256 байт: class_table[i] = категория символа i
    class_table:
        db 0, 0, 0, 0, 0, 0, 0, 0    ; 0..7
        ; ... остальные 248 байт ...

section .text
    movzx rax, byte [rdi]       ; rdi -> входной байт
    lea   rbx, [rel class_table]
    mov   al, [rbx + rax]

Разбор:

  • Таблица class_table хранит предвычисленную категорию для каждого байта 0..255.
  • movzx rax, byte [rdi] читает входной байт и расширяет его до 64-битного индекса.
  • lea rbx, [rel class_table] получает базовый адрес таблицы в позиционно-независимом стиле.
  • mov al, [rbx + rax] извлекает значение таблицы по индексу.
  • Такой lookup заменяет длинные цепочки cmp/jcc и даёт O(1)-доступ.

Подход 2 — XLATB (историческая мнемоника):

    mov rbx, table_base     ; в 64-битном режиме база таблицы в RBX
    mov al, [rsi]           ; индекс в AL (0..255)
    xlatb                   ; AL := byte [RBX + AL]

Разбор:

  • RBX задаёт базовый адрес таблицы преобразования.
  • AL содержит индекс, поэтому диапазон ограничен 0..255.
  • xlatb автоматически читает байт по адресу RBX + AL и возвращает его в AL.
  • Инструкция удобна для компактного кода, но скрывает адресацию и хуже читается в современных проектах.

XLATB эквивалентен mov al, [rbx + al] с ограничением индекса байтом. В новом коде чаще пишут явную форму — читаемее и проще для отладки.

Таблица слов (не байт): индекс умножают на размер элемента:

    mov eax, [index]
    lea rbx, [rel words_table]
    mov edx, [rbx + rax*4]

Разбор:

  • mov eax, [index] загружает индекс элемента таблицы.
  • lea rbx, [rel words_table] получает базу массива 32-битных слов.
  • Масштаб *4 в адресации учитывает размер одного dword.
  • mov edx, [rbx + rax*4] читает нужный элемент таблицы в EDX.
  • Подход подходит для таблиц int32, переходов состояний и заранее подготовленных коэффициентов.

См. типы данных про endianness и выравнивание.

Где lookup table реально полезна​

Типовые практические кейсы:

  1. Быстрая классификация символов (digit, space, delimiter) в парсере.
  2. Замена длинной цепочки cmp/je на O(1) доступ по индексу.
  3. Табличная конвертация (например, hex-символ -> значение 0..15).
  4. Лёгкие конечные автоматы, где состояние и вход дают индекс в таблицу переходов.

Если логика повторяется для диапазона значений, таблица почти всегда выигрывает в простоте.

Таблица цифры '0'–'9' → значение 0..9:

section .rodata
digit_val:
    times '0', db -1
    db 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
    times 256 - ('9' + 1), db -1

section .text
    movzx rax, byte [rdi]       ; rdi -> символ, например '7'
    lea   rbx, [rel digit_val]
    movsx eax, byte [rbx + rax] ; eax = 7 или -1

Разбор:

  • times '0', db -1 заполняет байты 0..47 значением "ошибка" (-1 как signed byte).
  • Десять байт 0..9 соответствуют кодам символов '0'..'9'.
  • Хвост times 256 - ('9' + 1), db -1 помечает все остальные коды как недопустимые.
  • Индекс — ASCII-код символа, доступ digit_val[code] за O(1).
  • movsx eax, byte [...] даёт знаковый результат: -1 легко проверить через js / cmp eax, 0.
  • Для hex добавляют ещё диапазон 'A'..'F' и 'a'..'f' в ту же таблицу 256 байт.

Чтение следующего байта — LODSB:

    mov rsi, src_ptr
    lodsb                       ; al = [rsi], rsi++

Разбор:

  • LODSB загружает байт из [RSI] в AL и увеличивает RSI (при DF=0).
  • Удобно в ручных парсерах, где нужно идти по входному буферу без явного mov/inc.
  • Перед циклом с lodsb обычно вызывают cld.
  • RSI в Linux x86-64 — caller-saved; при вызовах функций его нужно сохранять или использовать после всех call.

Соглашения и осторожности​

ТемаЗамечание
Перекрытие src/dst при movsпри пересечении регионов поведение как у memmove — нужен другой алгоритм
RSI/RDI в вызовах ABIв Linux x86-64 RSI/RDI — аргументы; сохраняйте callee-saved или используйте после настройки вызова
RCXcaller-saved; REP портит счётчик
Строки UTF-8побайтовый разбор; один символ — 1–4 итерации, не один SCAS

Связанные материалы​

Содержание