Поиск подстроки битов в 1024-битовой строке

[Mikl___]

Наткнулся на достаточно интересное "студенческое" задание

Разработать программу поиска кодовой комбинации в строке 1024 бит. Кодовая комбинация задана в виде строки длиной не более 16 бит
Например: строка для поиска: 0110010101101110... ...00101000100110010010010010110111 100100100
Кодовая комбинация для поиска: 010011
Результат получить в виде номера разряда, с которого начинается кодовая комбинация в строке.

По виду, похоже чем-то на поиск подстроки в строке в алгоритме Бойера-Мура, но может быть найдутся и другие интересные решения

[Stilet]

Как-то не понял сам алгоритм, но если это биты, то что мешает делать сравнение по маске, сдвигать регистр и опять сравнивать?

[Mikl___]

Здравствуйте, Stilet!
если делать сравнения по маске, сдвигать и опять сравнивать, то для поиска 6 разрядов в 1024-разрядной строке потребуется 1024-6=1018 сравнений в худшем случае, хотелось бы чего-нибудь более быстрого. Например, потратить 1024/6=170 сравнений в худшем случае

[Stilet]

Стоп, а речь идет не о самом решении, а о нахождении наиболее шустрого алгоритма?

[f.hump]

Stilet дело говорит.

LEA rsi, [str_ptr]
MOVZX rdx, WORD PTR [code_val]
MOVZX rcx, BYTE PTR [code_length]

MOV r8, 120

MOV r9, 1
SHL r9, cl
DEC r9

MOV rax, [rsi]
LEA rsi, [rsi+8]

XOR rcx, rcx

align 16
    search_loop:
        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHL r9, 1
        SHL rdx, 1
        INC rcx

        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHL r9, 1
        SHL rdx, 1
        INC rcx

        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHL r9, 1
        SHL rdx, 1
        INC rcx

        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHL r9, 1
        SHL rdx, 1
        INC rcx

        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHL r9, 1
        SHL rdx, 1
        INC rcx

        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHL r9, 1
        SHL rdx, 1
        INC rcx

        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHL r9, 1
        SHL rdx, 1
        INC rcx

        MOV r10, r9
        AND r10, rax
        XOR r10, rdx
        JZ search_done
        SHR r9, 7
        SHR rdx, 7
        INC rcx

        
        LODSB
        ROR rax, 8
    DEC r8
    JNZ serach_loop

   

align 16
    search_done:
        MOV rax, rcx

думаю такое будет быстрее любой дополнительной логики.
(бит-стрим читается справа-налево)

// последние 8 байт непроверенными получились, можно сделать еще один цикл без LODSB и r8 = 8

[Mikl___]

Сообщение от Stilet

Стоп, а речь идет не о самом решении, а о нахождении наиболее шустрого алгоритма?

Конечно, решение здесь вторично...
допустим, подстрока начинается с нуля, составляем массив индексов положения нулей в 1024-строке, подставляем подстроку к каждому нулю и проверяем на совпадение со следующим от нуля битами, ну это так, на уровне бреда

[Stilet]

ну это так, на уровне бреда

Эт вообще-то Fulltext поиск. Везде используется, правда места ему много надо в памяти и ресурсоемок он при создании. Если важна только скорость отбора, то он подходит, а если от начала до конца разбор то нет.

[Mikl___]

Stilet,
это также на уровне бреда, здесь в поисковой подстроке на 6 бит соотношение нулей и единиц 0,5; делим 1024-строку на участки по 6 бит и смотрим соотношение нулей и единиц, если больше или меньше - пропускаем

[R71MT]

..сори, но для чего может понадобится поиск 6-битного значения?!
Если это маска, то должна быть минимум 8 бит (с нулями впереди), а так - где можно применить значение в 6-бит? Просто интересно..

[Smitt&Wesson]

Сообщение от R71MT

минимум 8 бит (с нулями впереди), а так - где можно применить значение в 6-бит? Просто интересно..

Чё-чё чё? Ещё раз, подробнее. . Ой. Уже умираю от смеха.