如何用Lisp在二进制流中查找指定字节序列？

问题描述 #

我想实现类似(search "bar" "foobarbaz")的功能，不过这里的"bar"是指定的字节序列，"foobarbaz"对应二进制流。具体来说，我需要在以(unsigned-byte 8)模式打开的文件中，查找字节序列4d 54 68 64的位置。

我知道流和集合对象不一样，但肯定有相对简便的方法，通过with-open-file读取文件内容来实现。我查过CL Cookbook和《Practical Common Lisp》（里面有二进制文件读写的优质章节），但没找到快速解决方案。

补充说明 #

我更新了标题以适配更通用场景：使用任意Lisp解决该问题。目前已经有不少Common Lisp的解决方案示例，但最简单的方案似乎是借助Racket的端口及内置正则表达式支持。相关Racket文档内容如下：

• Racket端口参考
• Racket正则表达式参考
• Racket正则表达式指南

Common Lisp 实现方案 #

原生滑动窗口实现

无需额外库，通过维护匹配缓冲区逐字节对比：

(defun find-byte-sequence (sequence stream)
  (let* ((seq-length (length sequence))
         (buffer (make-array seq-length :element-type '(unsigned-byte 8)))
         (position 0)
         (match-index 0))
    (loop for byte = (read-byte stream nil nil)
          while byte do
            (setf (aref buffer match-index) byte)
            (incf position)
            (if (equalp (subseq buffer 0 (1+ match-index))
                        (subseq sequence 0 (1+ match-index)))
                (incf match-index)
                (setf match-index 0))
            (when (= match-index seq-length)
              (return (- position seq-length))))))

;; 使用示例：查找文件中4d 54 68 64的起始位置
(with-open-file (stream "目标文件.bin" :element-type '(unsigned-byte 8))
  (find-byte-sequence #(77 84 104 100) stream)) ; 十六进制4d/54/68/64对应十进制值

借助cl-ppcre库实现

如果允许使用第三方库，cl-ppcre可以简化实现：

;; 先加载库
(ql:quickload :cl-ppcre)

(defun find-byte-sequence-with-ppcre (sequence file-path)
  (let* ((byte-array (with-open-file (stream file-path :element-type '(unsigned-byte 8))
                       (let ((buf (make-array (file-length stream) :element-type '(unsigned-byte 8))))
                         (read-sequence buf stream)
                         buf)))
         (pattern (coerce sequence 'list)))
    (cl-ppcre:scan pattern byte-array)))

Racket 实现方案 #

借助Racket内置的端口操作和正则表达式支持，代码更简洁：

#lang racket

(define (find-byte-sequence-in-file target-seq file-path)
  (call-with-input-file file-path
    (lambda (in)
      (port-count-lines! in)
      (define byte-re (byte-regexp target-seq))
      (regexp-match-positions byte-re in))))

;; 使用示例：查找文件中4d 54 68 64的位置
(find-byte-sequence-in-file #"\x4d\x54\x68\x64" "目标文件.bin")

内容的提问来源于stack exchange，提问作者Pliny Suetonious