Быстро определить, совпадает ли "строка" хотя бы с одной "строкой" из двух наборов - Assembler

Узнай цену своей работы

Формулировка задачи:

Строки не текстовые. Это просто какая-то последовательность из 32-х байт. Есть адрес первого байта проверяемой строки. Есть адрес первого байта 1-го набора. Первый набор всегда состоит из 1 элемента. Есть адрес первого байта 2-го набора. Количество элементов в этом наборе известно и пока пусть равно 3. Но позже понадобится вариант для размера второго набора в 7 элементов. Разделителей в наборах нет. 32-байтовые последовательности в наборах идут одна за другой. Вот самый простой вариант, скорость работы которого меня не устраивает: 
// Str - адрес проверяемой строки
// N1 - адрес 1-го набора
// N2 - адрес 2-го набора
        MOV     RAX,[Str]
        CMP     RAX,[N1]
        JNE     @ne0
        MOV     RAX,[Str+8]
        CMP     RAX,[N1+8]
        JNE     @ne0
        MOV     RAX,[Str+16]
        CMP     RAX,[N1+16]
        JNE     @ne0
        MOV     RAX,[Str+24]
        CMP     RAX,[N1+24]
        JE      @result_eq
  @ne0:
        MOV     RAX,[Str]
        CMP     RAX,[N2]
        JNE     @ne1
        MOV     RAX,[Str+8]
        CMP     RAX,[N2+8]
        JNE     @ne1
        MOV     RAX,[Str+16]
        CMP     RAX,[N2+16]
        JNE     @ne1
        MOV     RAX,[Str+24]
        CMP     RAX,[N2+24]
        JE      @result_eq
  @ne1:
        MOV     RAX,[Str]
        CMP     RAX,[N2+$20]
        JNE     @ne2
        MOV     RAX,[Str+8]
        CMP     RAX,[N2+$20+8]
        JNE     @ne2
        MOV     RAX,[Str+16]
        CMP     RAX,[N2+$20+16]
        JNE     @ne2
        MOV     RAX,[Str+24]
        CMP     RAX,[N2+$20+24]
        JE      @result_eq
  @ne2:
        MOV     RAX,[Str]
        CMP     RAX,[N2+$40]
        JNE     @result_ne
        MOV     RAX,[Str+8]
        CMP     RAX,[N2+$40+8]
        JNE     @result_ne
        MOV     RAX,[Str+16]
        CMP     RAX,[N2+$40+16]
        JNE     @result_ne
        MOV     RAX,[Str+24]
        CMP     RAX,[N2+$40+24]
        JNE     @result_ne
  @result_eq:
        // есть совпадение
        JMP     @finish
  @result_ne:
        // нет совпадений
  @finish:
        RET
Попытался сэкономить на MOV RAX,[Str...]. Получилась вот такая здоровая фигня: 
// R11 - адрес проверяемой строки
// R12 - адрес первого набора
// T - адрес второго набора
        MOV     R13,[R11]           // 1
        CMP     R13,[R12]           // r0
        JNE     @N_1xxx_xxxx_xxxx             // > ..1 r0- (s0)
        CMP     R13,[T]             // s0
        JNE     @yxxx_N_1xxx_xxxx             // > ..1 r0+ s0- (s1)
        CMP     R13,[T+$20]         // s1
        JNE     @yxxx_yxxx_N_1xxx             // > ..1 r0+ s0+ s1- (r2)
        CMP     R13,[T+$40]         // r2
        JNE     @y2xx_yxxx_yxxx_N_M           // > 2 r2- (r0)
 
        MOV     R13,[R11+8]         // 2
        CMP     R13,[R12+8]         // r0
        JNE     @N_y2xx_yxxx_yxxx             // > ..2 r0- (s0)
        CMP     R13,[T+8]           // s0
        JNE     @yyxx_N_y2xx_yxxx             // > ..2 r0+ s0- (s1)
        CMP     R13,[T+$20+8]       // s1
        JNE     @yyxx_yyxx_N_y2xx             // > ..2 r0+ s0+ s1- (r2)
        CMP     R13,[T+$40+8]       // r2
        JNE     @yy3x_yyxx_yyxx_N_M           // > 3 r2- (r0)
 
        MOV     R13,[R11+16]        // 3
        CMP     R13,[R12+16]        // r0
        JNE     @N_yy3x_yyxx_yyxx             // > ..3 r0- (s0)
        CMP     R13,[T+16]          // s0
        JNE     @yyyx_N_yy3x_yyxx             // > ..3 r0+ s0- (s1)
        CMP     R13,[T+$20+16]      // s1
        JNE     @yyyx_yyyx_N_yy3x             // > ..3 r0+ s0+ s1- (r2)
        CMP     R13,[T+$40+16]      // r2
        JNE     @yyy4_yyyx_yyyx_N_M           // > 4 r2- (r0)
 
        MOV     R13,[R11+24]        // 4
        CMP     R13,[R12+24]        // r0
        JE      @N1N2_Y
        CMP     R13,[T+24]          // s0
        JE      @N1N2_Y
        CMP     R13,[T+$20+24]      // s1
        JE      @N1N2_Y
        CMP     R13,[T+$40+24]      // r2
        JE      @N1N2_Y
        JMP     @N1N2_N
 
  @N_1xxx_xxxx_xxxx:                // < ..1 r0- (s0)
        CMP     R13,[T]             // s0
        JNE     @N_N_1xxx_xxxx      // ..1 r0- s0- (s1)
        CMP     R13,[T+$20]         // s1
        JNE     @N_yxxx_N_1xxx      // ..1 r0- s0+ s1- (r2)
        CMP     R13,[T+$40]         // r2
        JNE     @N_y2xx_yxxx_N      // 2 r0- r2- (s0)
        MOV     R13,[R11+8]         // 2 r0-
  @N_y2xx_yxxx_yxxx:                // < ..2 r0- (s0)
        CMP     R13,[T+8]           // s0
        JNE     @N_N_y2xx_yxxx      // ..2 r0- s0- (s1)
        CMP     R13,[T+$20+8]       // s1
        JNE     @N_yyxx_N_y2xx      // ..2 r0- s0+ s1- (r2)
        CMP     R13,[T+$40+8]       // r2
        JNE     @N_yy3x_yyxx_N      // 3 r0- r2- (s0)
        MOV     R13,[R11+16]        // 3 r0-
  @N_yy3x_yyxx_yyxx:                // < ..3 r0- (s0)
        CMP     R13,[T+16]          // s0
        JNE     @N_N_yy3x_yyxx      // ..3 r0- s0- (s1)
        CMP     R13,[T+$20+16]      // s1
        JNE     @N_yyyx_N_yy3x      // ..3 r0- s0+ s1- (r2)
        CMP     R13,[T+$40+16]      // r2
        JNE     @N_yyyx_yyyx_N      // 4 r0- r2- (s0)
        MOV     R13,[R11+24]        // 4 r0-
        CMP     R13,[T+24]          // s0
        JE      @N1N2_Y
        CMP     R13,[T+$20+24]      // s1
        JE      @N1N2_Y
        CMP     R13,[T+$40+24]      // r2
        JE      @N1N2_Y
        JMP     @N1N2_N
 
  @yxxx_N_1xxx_xxxx:                // < ..1 r0+ s0- (s1)
        CMP     R13,[T+$20]         // s1
        JNE     @yxxx_N_N_xxxx
        CMP     R13,[T+$40]         // r2
        JNE     @yxxx_N_yxxx_N
        MOV     R13,[R11+8]         // 2 s0-
        CMP     R13,[R12+8]         // r0
        JNE     @N_N_yxxx_yxxx
  @yyxx_N_y2xx_yxxx:                // < ..2 r0+ s0- (s1)
        CMP     R13,[T+$20+8]       // s1
        JNE     @yyxx_N_N_yxxx
        CMP     R13,[T+$40+8]       // r2
        JNE     @yyxx_N_yyxx_N
        MOV     R13,[R11+16]        // 3 s0-
        CMP     R13,[R12+16]        // r0
        JNE     @N_N_yyxx_yyxx
  @yyyx_N_yy3x_yyxx:                // < ..3 r0+ s0- (s1)
        CMP     R13,[T+$20+16]      // s1
        JNE     @yyyx_N_N_yyxx
        CMP     R13,[T+$40+16]      // r2
        JNE     @yyyx_N_yyyx_N
        MOV     R13,[R11+24]        // 4 s0-
        CMP     R13,[R12+24]        // r0
        JE      @N1N2_Y
        CMP     R13,[T+$20+24]      // s1
        JE      @N1N2_Y
        CMP     R13,[T+$40+24]      // r2
        JE      @N1N2_Y
        JMP     @N1N2_N
 
  @yxxx_yxxx_N_1xxx:                // < ..1 r0+ s0+ s1- (r2)
        CMP     R13,[T+$40]         // r2
        JNE     @yxxx_yxxx_N_N
        MOV     R13,[R11+8]         // 2 s1-
        CMP     R13,[R12+8]         // r0
        JNE     @N_yxxx_N_yxxx
        CMP     R13,[T+8]           // s0
        JNE     @yyxx_N_N_yxxx
  @yyxx_yyxx_N_y2xx:                // < ..2 r0+ s0+ s1- (r2)
        CMP     R13,[T+$40+8]       // r2
        JNE     @yyxx_yyxx_N_N
        MOV     R13,[R11+16]        // 3 s1-
        CMP     R13,[R12+16]        // r0
        JNE     @N_yyxx_N_yyxx
        CMP     R13,[T+16]          // s0
        JNE     @yyyx_N_N_yyxx
  @yyyx_yyyx_N_yy3x:                // < ..3 r0+ s0+ s1- (r2)
        CMP     R13,[T+$40+16]      // r2
        JNE     @yyyx_yyyx_N_N
        MOV     R13,[R11+24]        // 4 s1-
        CMP     R13,[R12+24]        // r0
        JE      @N1N2_Y
        CMP     R13,[T+24]          // s0
        JE      @N1N2_Y
        CMP     R13,[T+$40+24]      // r2
        JE      @N1N2_Y
        JMP     @N1N2_N
 
  @y2xx_yxxx_yxxx_N_M:              // < 2 r2- (r0)
        MOV     R13,[R11+8]         // 2 r2-
        CMP     R13,[R12+8]         // r0
        JNE     @N_yxxx_yxxx_N
        CMP     R13,[T+8]           // s0
        JNE     @yyxx_N_yxxx_N
        CMP     R13,[T+$20+8]       // s1
        JNE     @yyxx_yyxx_N_N
  @yy3x_yyxx_yyxx_N_M:              // < 3 r2- (r0)
        MOV     R13,[R11+16]        // 3 r2-
        CMP     R13,[R12+16]        // r0
        JNE     @N_yyxx_yyxx_N
        CMP     R13,[T+16]          // s0
        JNE     @yyyx_N_yyxx_N
        CMP     R13,[T+$20+16]      // s1
        JNE     @yyyx_yyyx_N_N
  @yyy4_yyyx_yyyx_N_M:              // < 4 r2- (r0)
        MOV     R13,[R11+24]        // 4 r2-
        CMP     R13,[R12+24]        // r0
        JE      @N1N2_Y
        CMP     R13,[T+24]          // s0
        JE      @N1N2_Y
        CMP     R13,[T+$20+24]      // s1
        JE      @N1N2_Y
        JMP     @N1N2_N
 
  @N1N2_Y:
        // есть совпадение
        JMP     @finish
  @N1N2_N:
        // нет совпадений
  @finish:
        RET
Тут не закончено - не хватает ещё многих меток и текста, который должен следовать за этими метками. Я могу это закончить, просто терпения и времени не хватило пока. Ещё очень большой риск сделать ошибку, которую потом будет нереально отловить. Одна неверная буква в метке и всё. Предполагаю, что написание подобного текста для случая, когда второй набор из 7 элементов займёт многие часы.

Не по теме:

Возможно, с целью защиты от ошибок придётся написать отдельную программу для генерации такого текста.

Так вот, вопрос: есть ли способы

быстро

определить, совпадает ли 32-байтная строка с какой-то строкой из набора? По первому варианту: вроде как можно было бы загружать части строк не в RAX, а в XMM0 и XMM1, но там вроде бы команда сравнения может не сработать, если окажется что часть строки соответствует числу NaN. Или всё-таки можно как-то сравнить значения регистров XMM между собой или с участком памяти для абсолютно любого содержимого? Проц, на котором всё это должно работать не умеет AVX.

Решение задачи: «Быстро определить, совпадает ли "строка" хотя бы с одной "строкой" из двух наборов»

textual
Листинг программы 
mov r9,[Str]
mov r10,[Str+8]
mov r11,[Str+16]
mov r12,[Str+24]

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.714 из 5
Похожие ответы