3

I'm trying to find all numbers on two block devices that start with a # character, are between 1635700000 and 1653699999, and end either with a null character (\0) or a linux newline (\0xA).

I came up with this grep that certainly isn't elegant:

grep --only-matching --byte-offset --text -Pa '#1635[7-9][0-9]{5}(\x0|$)|#163[6-9][0-9]{6}(\x0|$)|#164[0-9]{7}(\x0|$)|#165[0-2][0-9]{6}(\x0|$)|#1653[0-6][0-9]{5}(\x0|$)' /dev/device

Even though it can't be typed and executed like this, here's the same statement with some newlines to make it more readable.

grep --only-matching --byte-offset --text -Pa '
 #1635[7-9][0-9]{5}(\x0|$)
|#163[6-9][0-9]{6}(\x0|$)
|#164[0-9]{7}(\x0|$)
|#165[0-2][0-9]{6}(\x0|$)
|#1653[0-6][0-9]{5}(\x0|$)
' /dev/device

This worked on one of the block devices, but on the other after some but not all output, it stopped with the error:

grep: exceeded PCRE's line length limit

I'm guessing the failing block device has a longer stretch of bytes that don't have a \0 or \0xA character, crossing the line length limit threshold.

So, I tried changing NULL characters to newlines:

sed 's/\x0/\n/g' /dev/device | grep ...

But, it stopped for about the same reason:

sed: regex input buffer length larger than INT_MAX

How can I find what I'm trying to find on this second block device? Pretty sure it will need to be a different utility that either uses a larger input buffer or that doesn't read full lines, or perhaps even a custom perl/python/C/C++ program.

I do need the output to be one line per match found, including the byte offset and number found.

Modifying the block device is not an option. There's going to be tens of thousands of results, so searching by hand in something like a hex editor isn't an option either.

9
  • It looks like there is bgrep for exactly this situation, although I've never tried it. I also wonder if the problem would reproduce if you were to not use the PCRE engine.
    – larsks
    Jun 19, 2022 at 13:44
  • What if you replace # by \n# and remove the rest of the lines after 11 bytes using sed or perl? The lines to grep will then be very short...
    – choroba
    Jun 19, 2022 at 14:03
  • @larsks I will look at bgrep. I'm using Perl because that's the only way I could find to grep for a NULL character. Jun 19, 2022 at 14:14
  • @choroba I unfortunately can't assume anything about what will be before the # character. sed has the same type of issue, since I ran into the sed: regex input buffer length larger than INT_MAX issue. Jun 19, 2022 at 14:20
  • @larsks Unfortunately, it looks like bgrep can't look for a regex. It can do a bit more than fixed strings either by hex byte or ASCII, but it doesn't look like it can look for a number within a range like I need. Jun 19, 2022 at 14:30

2 Answers 2

2

In a comment above, @terdon gave the key insight about reducing the search space first. By using the extended grep pattern syntax to reduce the maximum line length given to the perl (PCRE) grep pattern syntax, I was able to get this to work.

grep --only-matching --byte-offset --text -E '#[0-9]{10}.' /dev/device | grep --only-matching --text -P '[0-9]*:#1635[7-9][0-9]{5}(\x0|$)|[0-9]*:#163[6-9][0-9]{6}(\x0|$)|[0-9]*:#164[0-9]{7}(\x0|$)|[0-9]*:#165[0-2][0-9]{6}(\x0|$)|[0-9]*:#1653[0-6][0-9]{5}(\x0|$)' /dev/device

Even though it can't be typed and executed like this, here's the same statement with some newlines to make it more readable.

grep --only-matching --byte-offset --text -E 
   '#[0-9]{10}.'
   /dev/device
| grep --only-matching --text -P '
    [0-9]*:#1635[7-9][0-9]{5}(\x0|$)
   |[0-9]*:#163[6-9][0-9]{6}(\x0|$)
   |[0-9]*:#164[0-9]{7}(\x0|$)
   |[0-9]*:#165[0-2][0-9]{6}(\x0|$)
   |[0-9]*:#1653[0-6][0-9]{5}(\x0|$)
   ' /dev/device

The extended grep pattern syntax engine doesn't have a line length limitation that I ran into, and reduces the maximum line length given to the perl (PCRE) pattern syntax engine.

2
  • If there's something like #1635700000 with a newline after, that first grep won't find it, since the . in the regex can't match the newline. You could probably preprocess the file with e.g. tr '\0' '\n' to change NULs to newlines, and then use grep -E '#[0-9]{10}$'. (tr works a byte (or character) at a time, and doesn't care about lines, so it shouldn't have a length limit.) Also, it'd be easier to check if number is in the required range with something like awk: no need for the complex regex, just something like awk -F: '$2 >= 1635700000 && $2 <= 1653699999'
    – ilkkachu
    Jun 20, 2022 at 21:21
  • @ilkkachu Thanks, whoops, I was missing some results! Changing the first grep to #[0-9{10}(.|$) seems to also do the trick, but I'll try using your way too, and it's certainly more elegant. Thanks also for the awk. I definitely need to start learning that. Jun 21, 2022 at 23:02
0

Here is a solution using bash(1), grep(1), and perl(1):

 1  #!/bin/bash
 2  grep -P -a -b -o '#\d{10}(\000|$)' \
 3  | perl -ne '/(\d{10})/; print if 1635700000 <= $1 && $1 <= 1653699999' \
 4  | perl -pe 'chop; /\000/ ? do {chop; $_ .= "\\000\n"} : do {$_ .= "\\n\n"}'

Line 1 tells the shell this is a Bash script.

Lines 2-4 form a command pipeline.

Line 2 invokes grep(1):

  • Option '-P' specifies that the pattern should be interpreted as a Perl-compatible regular expression.

  • Option '-a' specifies that binary input should be processed as text.

  • Option '-b', combined with '-o', specifies that the byte offset of the matching part should be printed before each line of output.

  • Option '-o' specifies that only the matched parts should be printed.

  • Argument '#\d{10}($|\000)' is a regular expression pattern -- a number sign, followed by ten decimal digits, followed by either end-of-line or NUL. On Unix/ Linux, the regular expression end-of-line '$' meta-character matches ASCII carriage return (problem statement '\0xA'). The regular expression may fail to find ASCII carriage returns when run on platforms with different newline encoding (e.g. CR-LF on MS-DOS, LF on classic Mac OS, etc.).

Line 3 is a Perl one-line filter that only passes lines whose numeric part is within the desired range.

Line 4 is a Perl one-liner that makes the terminating newline or NUL visible.

Here is a sample run:

52:#1647787407\n
70:#1644931194\n
84:#1651134631\000
154:#1646920743\n

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .