15

I want to count how many times a certain sequence of bytes happens inside a file that I have. For example, I want to find out how many times the number \0xdeadbeef occurs inside an executable file. Right now I am doing that using grep:

#/usr/bin/fish
grep -c \Xef\Xbe\Xad\Xde my_executable_file

(The bytes are written in reverse order because my CPU is little-endian)

However, I have two problems with my approach:

  • Those \Xnn escape sequences only work in the fish shell.
  • grep is actually counting the number of lines that contain my magic number. If the pattern occurs twice in the same line it will only count once.

Is there a way to fix these problems? How can I make this one liner run in Bash shell and accurately count number of times the pattern occurs inside the file?

  • some help: unix.stackexchange.com/q/231213/117549 -- specifically, grep -o – Jeff Schaller Dec 16 '16 at 18:57
  • 1
    grep is the wrong tool to use. Consider bgrep or bgrep2. – fpmurphy Dec 16 '16 at 18:58
  • 3
    If the sequence to search for is 11221122, what should be returned on an input like 112211221122? 1 or 2? – Stéphane Chazelas Dec 16 '16 at 21:53
  • I would be OK with reporting 2 or 3 matches in that case. Whichever would be simpler to implement. – hugomg Dec 16 '16 at 23:37
14

This is the one-liner solution requested (for recent shells that have "process substitution"):

grep -o "ef be ad de" <(hexdump -v -e '/1 "%02x "' infile.bin) | wc -l

If no "process substitution" <(…) is available, just use grep as a filter:

hexdump -v -e '/1 "%02x "' infile.bin  | grep -o "ef be ad de" | wc -l

Below is the detailed description of each part of the solution.

Byte values from hex numbers:

Your first problem is easy to resolve:

Those \Xnn escape sequences only work in the fish shell.

Change the upper X to a lower one x and use printf (for most shells):

$ printf -- '\xef\xbe\xad\xde'

Or use:

$ /usr/bin/printf -- '\xef\xbe\xad\xde'

For those shells that choose to not implement the '\x' representation.

Of course, translating hex to octal will work on (almost) any shell:

$ "$sh" -c 'printf '\''%b'\'' "$(printf '\''\\0%o'\'' $((0xef)) $((0xbe)) $((0xad)) $((0xde)) )"'

Where "$sh" is any (reasonable) shell. But it is quite difficult to keep it correctly quoted.

Binary files.

The most robust solution is to transform the file and the byte sequence (both) to some encoding that has no issues with odd character values like (new line) 0x0A or (null byte) 0x00. Both are quite difficult to manage correctly with tools designed and adapted to process "text files".

A transformation like base64 may seem a valid one, but it presents the issue that every input byte may have up to three output representations depending if it is the first, second or third byte of the mod 24 (bits) position.

$ echo "abc" | base64
YWJjCg==

$ echo "-abc" | base64
LWFiYwo=

$ echo "--abc" | base64
LS1hYmMK

$ echo "---abc" | base64        # Note that YWJj repeats.
LS0tYWJjCg==

Hex transform.

Thats why the most robust transformation should be one that starts on each byte boundary, like the simple HEX representation.
We can get a file with the hex representation of the file with either any of this tools:

$ od -vAn -tx1 infile.bin | tr -d '\n'   > infile.hex
$ hexdump -v -e '/1 "%02x "' infile.bin  > infile.hex
$ xxd -c1 -p infile.bin | tr '\n' ' '    > infile.hex

The byte sequence to search is already in hex in this case.
:

$ var="ef be ad de"

But it could also be transformed. An example of a round trip hex-bin-hex follows:

$ echo "ef be ad de" | xxd -p -r | od -vAn -tx1
ef be ad de

The search string may be set from the binary representation. Any of the three options presented above od, hexdump, or xxd are equivalent. Just make sure to include the spaces to ensure the match is on byte boundaries (no nibble shift allowed):

$ a="$(printf "\xef\xbe\xad\xde" | hexdump -v -e '/1 "%02x "')"
$ echo "$a"
ef be ad de

If the binary file looks like this:

$ cat infile.bin | xxd
00000000: 5468 6973 2069 7320 efbe adde 2061 2074  This is .... a t
00000010: 6573 7420 0aef bead de0a 6f66 2069 6e70  est ......of inp
00000020: 7574 200a dead beef 0a66 726f 6d20 6120  ut ......from a 
00000030: 6269 0a6e 6172 7920 6669 6c65 2e0a 3131  bi.nary file..11
00000040: 3232 3131 3232 3131 3232 3131 3232 3131  2211221122112211
00000050: 3232 3131 3232 3131 3232 3131 3232 3131  2211221122112211
00000060: 3232 0a

Then, a simple grep search will give the list of matched sequences:

$ grep -o "$a" infile.hex | wc -l
2

One Line?

It all may be performed in one line:

$ grep -o "ef be ad de" <(xxd -c 1 -p infile.bin | tr '\n' ' ') | wc -l

For example, searching for 11221122 in the same file will need this two steps:

$ a="$(printf '11221122' | hexdump -v -e '/1 "%02x "')"
$ grep -o "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ') | wc -l
4

To "see" the matches:

$ grep -o "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ')
3131323231313232
3131323231313232
3131323231313232
3131323231313232

$ grep "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ')

… 0a 3131323231313232313132323131323231313232313132323131323231313232 313132320a


Buffering

There is a concern that grep will buffer the whole file, and, if the file is big, create a heavy load for the computer. For that, we may use an unbuffered sed solution:

a='ef be ad de'
hexdump -v -e '/1 "%02x "' infile.bin  | 
    sed -ue 's/\('"$a"'\)/\n\1\n/g' | 
        sed -n '/^'"$a"'$/p' |
            wc -l

The first sed is unbuffered (-u) and is used only to inject two newlines on the stream per matching string. The second sed will only print the (short) matching lines. The wc -l will count the matching lines.

This will buffer only some short lines. The matching string(s) in the second sed. This should be quite low in resources used.

Or, somewhat more complex to understand, but the same idea in one sed:

a='ef be ad de'
hexdump -v -e '/1 "%02x "' infile.bin  |
    sed -u '/\n/P;//!s/'"$a"'/\n&\n/;D' |
        wc -l
  • 2
    Note that if you put all the text on one line, that means grep will end up loading it whole in memory (here twice the size of the original file + 1 because of the hex encoding), so in the end, it ends up being more overhead than the python approach or the perl one with -0777. You also need a grep implementation that supports lines of arbitrary length (those that support -o generally do). Good answer otherwise. – Stéphane Chazelas Dec 17 '16 at 9:01
  • 1
    Your hex versions match nibble-shifted values ?e fb ea dd e? in addition to the desired bytes. od -An -tx1 | tr -d '\n' or hexdump -v -e '/1 " %02x"' with a search string also containing spaces avoid this, but I see no such fix for xxd. – dave_thompson_085 Dec 17 '16 at 9:49
  • @dave_thompson_085 Answer edited. I believe that the answer will only match byte boundaries now, Thanks again. – sorontar Dec 17 '16 at 18:11
  • @StéphaneChazelas Could you review the proposed option of using an unbuffered sed. Thanks. – sorontar Dec 18 '16 at 6:37
  • sed -u (where available) is for unbuffer. That means it will read one byte at a time on input, and output its output straight away without buffering. In anycase, it will still need to load the whole line in the pattern space, so won't help here. – Stéphane Chazelas Dec 18 '16 at 9:55
7

With GNU grep's -P (perl-regexp) flag

LC_ALL=C grep -oaP '\xef\xbe\xad\xde' file | wc -l

LC_ALL=C is to avoid problems in multi-byte locales where grep would otherwise try to interpret sequences of bytes as characters.

-a treats binary files equivalent to text files (instead of the normal behavior, where grep only prints out whether there's at least one match or not)

  • This solution is always giving me 0 matches instead of the correct number. – hugomg Dec 16 '16 at 20:28
  • @hugomg, could it be that you need to reverse the bytes passed to grep to get it to match? – iruvar Dec 16 '16 at 20:33
  • I don't think it is the order. The other two answers to this question work correctly. – hugomg Dec 16 '16 at 21:32
  • 2
    @hugomg, it's the locale. See edit. – Stéphane Chazelas Dec 16 '16 at 21:41
  • 2
    I'll suggest to include the -a option, otherwise grep will answer with Binary file file.bin matches for any file that grep detects as binary. – sorontar Dec 17 '16 at 18:37
6
PERLIO=:raw perl -nE '$c++ while m/\xef\xbe\xad\xde/g; END{say $c}' file

Which treats the input file(s) as binary (no translation for linefeeds or encodings, see perlrun) then loops over the input file(s) not printing incrementing a counter for all matches of the given hex (or whatever form, see perlre).

  • 2
    Note that you can't use that if the sequence to search for contains the byte 0xa. In that case, you can use a different record separator (with -0ooo). – Stéphane Chazelas Dec 16 '16 at 21:54
  • 1
    @StéphaneChazelas you can use the sequence of interest itself as $/, with a slightly different tradeoff (memory usage proportional to the maximum distance between such sequences): perl -nE 'BEGIN { $/ = "\xef\xbe\xad\xde" } chomp; $c++ unless eof && length; END { say $c }' – hobbs Dec 17 '16 at 0:21
  • @StéphaneChazelas Please read my answer for a solution for any byte values. – sorontar Dec 17 '16 at 2:25
  • 1
    @hobbs, in any case, even here, memory usage will be proportional to the maximum distance between two 0xa bytes which for non-text files could be arbitrarily large. – Stéphane Chazelas Dec 17 '16 at 9:05
5

The most straight-forward translation I see is:

$ echo $'\xef\xbe\xad\xde' > hugohex
$ echo $'\xef\xbe\xad\xde\xef\xbe\xad\xde' >> hugohex
$ grep -F -a -o -e $'\xef\xbe\xad\xde' hugohex|wc -l
3

Where I've used $'\xef' as the bash ANSI-quoting (originally a ksh93 feature, now supported by zsh, bash, mksh, FreeBSD sh) version of fish's \Xef, and used grep -o ... | wc -l to count the instances. grep -o outputs each match on a separate line. The -a flag makes grep behave on binary files the same way it does on text files. -F is for fixed strings so you don't need to escape regex operators.

Like in you fish case, you can't use that approach though if the sequence to look for includes the bytes 0 or 0xa (newline in ASCII).

  • Using printf '%b' $(printf '\\%o ' $((0xef)) $((0xbe)) $((0xad)) $((0xde))) > hugohex' would be the most portable "pure shell" method. Of course: printf "efbeadde" | xxd -p -r > hugohex seems like the most practical method. – sorontar Dec 17 '16 at 2:27
5

With GNU awk, you can do:

LC_ALL=C awk -v 'RS=\xef\xbe\xad\xde' 'END{print NR - (NR && RT == "")}'

If any of the bytes are ERE operators, they would have to be escaped though (with \\). Like 0x2e which is . would have to be entered as \\. or \\\x2e. Other than that, it should work with arbitrary byte values including 0 and 0xa.

Note that it's not as simple as just NR-1 because there are a couple of special cases:

  • when the input is empty, NR is 0, NR-1 would give -1.
  • when the input ends in the record separator, an empty record is not created after that. We test for that with RT=="".

Also note that in the worst case (if the file doesn't contain the search term), the file will end up being loaded whole in memory).

4

You can use Python's bytes.count method to get the total number of non-overlapping substrings in a bytestring.

python -c "print(open('./myexecutable', 'rb').read().count(b'\xef\xbe\xad\xde'))"

This one-liner will load the entire file into memory, so not the most efficient, but works and is more legible than Perl ;D

  • 'more legible than Perl' is only one step up from TECO -- which IINM is: 239I$ 190I$ 173I$ 222I$ HXA ERfile$Y 0UC <:S^EQA$; %C$> QC= (gd&r) – dave_thompson_085 Dec 17 '16 at 10:14
  • You can mmap() a file in Python; that would reduce the memory commit. – Toby Speight Jan 18 '17 at 11:58
1
tr "$(printf \\0xef)\n" \\n\\0 < infile |
grep -c "^$(printf "\0xbe\0xad\0xde")"

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.