How do I sort binary key value pairs at fixed byte offsets using the Linux sort utility?

This feels ugly, but it should work:

hexdump -v -e '50/1 "%02x " "\n"' file.bin | sort | xxd -p -r > file-sorted.bin

You do a hexdump grouped by 50 bytes per line, do an ordinary sort of those lines, and reconvert it using xxd -r.

I didn't care about sorting for only the first 30 bytes, because if they are identical, the order is open and I choose to continue sorting by the value.

IMO, easier to manage in a programming language that makes it easy to read/write binary files. For (an esoteric) example, Tcl:

tclsh <<'END_TCL'
    set fh [open file.bin rb]
    while {true} {
        set kv [read $fh 50]
        if {[string length $kv] != 50} break
        lappend kvs $kv
    }
    close $fh

    set fh [open file_sorted.bin wb]
    foreach kv [lsort $kvs] {puts -nonewline $fh $kv}
    close $fh
END_TCL

Here's the input file:

$ ls -l file.bin
-rw-r--r-- 1 glennj glennj 200 Apr 20 16:07 file.bin

$ od -c -w50 file.bin
0000000   T   e   s   t   i   n   g   1   2   3   e  \b  \0   ` 203   k   9   ,   � 213 217   ^   U 226 030   U   � 233 207   �   " 203   �   f   �   �   �   �   �   �   � 036   &   �   )   *   � 020   d   �
0000062 030   �   j   �   }   o   e   k 035   /   C  \r   W   �   �   �   } 201   �   j   m   �   g 224 213   �   # 227   �   � 214   3   N   J   �   + 216   p 026   b 223   �   � 001 026   �   �   ;   �   �
0000144 225   �   � 202   b   �   �   � 004   G   � 177   w   �   :   5 207   �   � 220   B   �   � 006   � 216 237   �   �   �   �   9  \r 235  \r   � 023   � 203   B   �   R 201   . 231   K   K   @   : 026
0000226   z   *   | 223   � 204 035   � 223  \n  \r   �  \a   �   � 236 004   � 236   �   w   �   �   �   g   � 001   � 215 215   L 004   [   �   �  \0   o   �       P   �   �   [   �   �   @ 203   �   �   �
0000310

And the output file:

$ ls -l file_sorted.bin
-rw-r--r-- 1 glennj glennj 200 Apr 20 16:11 file_sorted.bin

$ od -c -w50 file_sorted.bin
0000000 030   �   j   �   }   o   e   k 035   /   C  \r   W   �   �   �   } 201   �   j   m   �   g 224 213   �   # 227   �   � 214   3   N   J   �   + 216   p 026   b 223   �   � 001 026   �   �   ;   �   �
0000062   T   e   s   t   i   n   g   1   2   3   e  \b  \0   ` 203   k   9   ,   � 213 217   ^   U 226 030   U   � 233 207   �   " 203   �   f   �   �   �   �   �   �   � 036   &   �   )   *   � 020   d   �
0000144   z   *   | 223   � 204 035   � 223  \n  \r   �  \a   �   � 236 004   � 236   �   w   �   �   �   g   � 001   � 215 215   L 004   [   �   �  \0   o   �       P   �   �   [   �   �   @ 203   �   �   �
0000226 225   �   � 202   b   �   �   � 004   G   � 177   w   �   :   5 207   �   � 220   B   �   � 006   � 216 237   �   �   �   �   9  \r 235  \r   � 023   � 203   B   �   R 201   . 231   K   K   @   : 026
0000310

for the curious, I created the input file from the question like this (bash):

for hx in \
    54 65 73 74 69 6E 67 31  32 33 65 08 00 60 83 6b \
    39 2c d5 8b 8f 5e 55 96  18 55 e7 9b 87 f0 22 83 \
    a4 66 b6 aa b1 f9 e0 ca  cf 1e 26 b3 29 2a fd 10 \
    64 bb 18 b5 6a c0 7d 6f  65 6b 1d 2f 43 0d 57 bd \
    e7 e4 7d 81 f3 6a 6d d2  67 94 8b bc 23 97 bf e2 \
    8c 33 4e 4a d8 2b 8e 70  16 62 93 cf aa 01 16 bf \
    da 3b b1 ab 95 e0 e4 82  62 b3 ed fe 04 47 b5 7f \
    77 b1 3a 35 87 fb e7 90  42 e3 c4 06 d6 8e 9f d2 \
    c7 f3 f6 39 0d 9d 0d ce  13 fb 83 42 e1 52 81 2e \
    99 4b 4b 40 3a 16 7a 2a  7c 93 c3 84 1d e1 93 0a \
    0d b2 07 f4 eb 9e 04 b5  9e d8 77 d9 a1 a0 67 a1 \
    01 fa 8d 8d 4c 04 5b ee  a3 00 6f b4 20 50 a4 e6 \
    5b b3 cc 40 83 eb b2 ad                         
do printf "\x$hx"; done > file.bin

This dumps your file in hex in readable 30 and 20 bytes strings:

cat mybinaryfile.bin | LC_ALL=C hexdump -v -e '50/1 "%02x " "\n"' | \
while read -r line ; do echo 'K="'"${line::89}"'", V="'"${line:90}"'"' ; done

The LC_ALL is to output in an always readable character set.

The hexdump: -v disables the suppression of identical lines. The -e makes the format string possible, which says 'break it down in 50 byte chunks, print those terminated with a new line (the \n); within the 50 byte block, print 1 byte at the time formatted as hex (the x), two characters wide (the two), if needed prefixed with a leading zero. (If you change the 'x' in '_p' you get printable characters in stead of hex.)

The while reads those 50 byte lines and breaks them down in 30 and 20 byte chunks, which it does by using bash Parameter Expansion, first by cutting off all characters beyond the 89th, the '"line::89}"' and then by cutting off all characters before the 90th, the '"${line:90}"'.

Now the sort. Adding a plain

| sort

Will of course sort on the first column, while a

| sort -t , -k 2,2

will determine the , to be a field separator and the -k 2,2 will direct the sort to sort by the second (value) field.

So the complete command, with readable output, sorted by value, will be:

cat mybinaryfile.bin | LC_ALL=C hexdump -v -e '50/1 "%02x " "\n"' | \
while read -r line ; do echo 'K="'"${line::89}"'", V="'"${line:90}"'"' ; done | \
sort -t , -k 2,2

Cheers.

Example using my kernel:

sudo dd if=/boot/vmlinuz-5.13.0-25-generic bs=512 count=1 2>/dev/null | \
LC_ALL=C hexdump -v -e '50/1 "%_p" "\n"' | while read -r line ; do \
echo 'K="'"${line::29}"'", V="'"${line:30}"'"' ; done | sort -t , -k 2,2
K="..........U.", V=""
K=".........N}..................", V="...... ... ........."
K=".............................", V=".................. ."
K="....>.............. .P`......", V="..................."
K="...........P}.....X..........", V="...................."
K="...............setup...;.....", V=".;.................."
K="MZ.............1....@.. .t...", V="......1............."
K=".P`.reloc.. ....=.. ....=....", V="[email protected]"
K="t. ....=.. ....=.............", V="@..B.text.....}..>.."
K="press any key to reboot......", V="E..d..............."
K="..............Use a boot load", V="r....Remove disk and"

Considering the size of data, I would suggest using a divide and conquer approach.

Divide your file into manageable chunks - for example you can use @glenn jackman's approach, but instead of reading the entire file at once just read the first 10 million key-value pairs (or however many your computer can handle at once), sort them, and dump them to tempfile1. Then clear the data from RAM, read the next chunk, sort it, and dump to tempfile2. Repeat until you are through the 20GB file.

Now you have a bunch of smaller, individually sorted files that we need to put back together. Luckily this step is (relatively) easy, and most importantly don't care about data size.

If you have two sequences that are individually sorted, then all you need to do to combine them into a single sorted sequence is to look at the two top elements and always just take the first-by-sort element. Doing this only requires three open files (the two you are reading from and one for writing the result), and enough memory to hold the two top elements.

Unfortunately I don't know any tools that can do this for you, so you may have to program it yourself.