使用 Common Lisp 识别二进制流中是否存在给定序列

Question

使用标准 Common Lisp 技术（如果库提供更简单或更快的可能性，则可以接受），类似的方法是什么

(search "bar" "foobarbaz")

，其中“bar”是给定的 字节序列，“foobarbaz”是 流？具体来说，我试图在我打开的文件中进行搜索

(unsigned-byte 8)

。了解我要查找的字符 (

4d 54 68 64

) 位于文件中的位置会很有帮助。

我知道这个类比不成立，因为流与集合不是同一类型的对象。但必须有一种相对简单的方法来读取我使用

with-open-file

打开的文件的一些内容。

我梳理了 CL Cookbook 和 Practical Common Lisp，其中有一个关于读/写二进制文件的很好的部分，但我无法找到一个快速而肮脏的解决方案。

Answer 1

执行此操作的一种方法是从流中读取数据以重复填充缓冲区，在缓冲区中搜索所需的序列，直到找到它或直到流耗尽。每次填充和搜索缓冲区但未找到匹配项时，都会检查最后 n 字节，其中 n 是所查找序列中的字节数。因此，在补充缓冲区后，需要检查最后 n-1 字节。这可以通过在从流中重新填充缓冲区之前将最后 n-1 字节移动到缓冲区的前面来完成。

下面的示例代码定义了一个

stream-find

函数，该函数采用

needle

参数表示要搜索的序列，以及

stream

参数表示要搜索的流。它使用无符号字节数组作为缓冲区。

keep

是缓冲区重新填充之间要保留的字节数，

refill-length

是每次重新填充后要搜索的新字节数。如果

needle

序列大于缓冲区，则会引发错误。

创建一个局部函数

check-buffer

，递归调用该函数来填充缓冲区并搜索

needle

。

check-buffer

函数采用

keeping

参数来跟踪上次搜索中保留的字节数，以及

checked

参数来跟踪迄今为止搜索的字节总数。第一次调用

check-buffer

时，这些值都为零。

当调用

check-buffer

时，如果调用保留先前搜索中的字节，则会将缓冲区的末尾复制到缓冲区的前面。然后，从最后保留的字节开始将流的内容读入缓冲区。然后在缓冲区中搜索

needle

，并将结果位置保存在

found

中。

如果找到

needle

，则将找到的位置与之前检查的字节数相结合，以返回

needle

在流中的字节位置。如果对

read-sequence

的调用在到达缓冲区末尾之前终止，则流已耗尽而未找到

needle

，因此它不在流中，并且返回

nil

。否则流未耗尽，因此再次调用

check-buffer

，从缓冲区末尾保留 n-1 字节并更新

checked

中的字节数。

(defun stream-find (needle stream)
  (let* ((buffer-length 1024)
         (buffer (make-array buffer-length
                             :element-type '(unsigned-byte 8)))
         (needle-length (length needle))
         (keep (- needle-length 1))
         (refill-length (- buffer-length keep)))
    (when (> needle-length buffer-length)
      (error "buffer must be able to contain needle"))
    (labels ((check-buffer (keeping checked)
               (when (> keeping 0)                          ; copy end of buffer to front
                 (map-into buffer #'identity
                           (subseq buffer refill-length)))
               (let* ((last (read-sequence buffer stream :start keeping)) ; fill buffer
                      (found (search needle buffer)))                     ; search buffer
                 (cond (found (+ found checked))                          ; found it
                       ((< last buffer-length) nil)                       ; not found
                       (t (check-buffer keep
                                        (+ checked refill-length)))))))   ; keep looking
      (check-buffer 0 0))))

这里有一些示例用法

testfile.txt

。请注意，此处的 repl 代码使用 SBCL 扩展

sb-ext:string-to-octets

来方便地创建用于针的字节向量：

_________
__**_____
_________
__***____

CL-USER> (with-open-file (stream "c:/code/lisp/scratch/testfile.txt"
                                 :element-type '(unsigned-byte 8))
           (stream-find (sb-ext:string-to-octets "**") stream))
13
CL-USER> (with-open-file (stream "c:/code/lisp/scratch/testfile.txt"
                                 :element-type '(unsigned-byte 8))
           (stream-find (sb-ext:string-to-octets "***") stream))
35