LibreDWG - News: Revealing unknown DWG classes

Revealing unknown DWG classes

Item posted by Reini Urban <reini_urban> on Fri 13 Jul 2018 10:11:01 PM UTC.

I implemented three major buzzwords today in some trivial ways.

• massive parallel processing
• asynchronous processing
• machine-learning: a self-improving program

The problem is mostly trivial, and the solutions also.  I need to
reverse-engineer a binary closed file-format, but got some hints from
a related ASCII file-format, DWG vs DXF.

I have several pairs of files, and a helper library to convert the
ASCII data to the binary representation in the DWG. There are various
variants for most data values, and several fields are unknown, they
are not represented in the DXF, only in the DWG.  So I wrote an example
program called unknown, which walks over all unknown binary blobs and
tries to find the matching known values. If a bitmap is found only
once, we have a unique match, if it's found multiple times, we have
several possibilities the fields could be laid out or if it is not
found, we have a problem, the binary representation is wrong.

When preparing the program called unknown, I decided to parse to log
files in perl and store the unknown blobs as C `.inc` files, to be
compiled into unknown as array of structs.

Several DWG files are too large and either produce too large log files
filling my hard disc or cannot be parsed properly leading to overly huge
mallocs and invalid loops, so these files need to be killed after some
timeout of 10s.

So instead of

    for d in test/test-data/*.dwg; do
        log=`basename "$d" .dwg`.log
        echo $d
        programs/dwgread -v5 "$d" 2>$log
    done

I improved it to

    for d in test/test-data/*.dwg; do
        log=`basename "$d" .dwg`.log
        echo $d
        programs/dwgread -v5 "$d" 2>$log &
        (sleep 10s; kill %1 2>/dev/null) &
    done

The dwgread program is put into the background, with %1 being its PID,
and `sleep 10s; kill %1` implements a simple timeout via bash, not via
perl. Both processes are in the background and the second optionally
kills the first. So with some 100 files in test-data, this is
*massive parallelization*, as the dwgread processes immediately
return, and it's output appears some time later, when the process is
finished or killed. So it's also *asynchronous*, as I cannot see the
result of each individual process anymore, which returned SUCCESS,
which returned ERROR and which was killed. You need to look at the
logfiles, similar to debugging hard real-world problems, like
real-time controllers.  This processing is also massively faster, but
mostly I did it to implement a simple timeout mechanism in bash.

The next problem with the background processing is that I don't know
when all the background processes stopped, so I had to add one more
line:

    while pgrep dwgread; do sleep 1; done

Otherwise I would continue processing the logfiles, creating my C
structs from these, but some logfiles would still grow and I would
miss several unknown classes.

The processed data is ~10GB gigabyte large, so massive parallel
processing saves some time. The log files are only temporarily needed
to extract the binary blobs and can be removed later.

Eventually I turnned off the massive parallelization using another
timeout solution:

    for d in test/test-data/*.dwg; do
        log=`basename "$d" .dwg`.log
        echo $d
        timeout -k 1 10 programs/dwgread -v5 "$d" 2>$log
    done

I could also use GNU [parallel](https://www.gnu.org/software/parallel/parallel_tutorial.html) with timeout instead to re-enable the
parallelization though and collect the async results properly.

    parallel timeout 10 programs/dwgread -v5 {} \2\>{/.}.log ::: test/test-data/*.dwg
    cd test/test-data
    parallel timeout 10 ../../programs/dwgread -v5 {} \2\>../../{/.}_{//}.log ::: \*/\*.dwg

So now the other interesting problem, the machine-learning part.
Let me show you first some real data I'm creating.

Parsing the logfiles and DXF data via some trivial perl scripts creates an array of such structs:

    { "ACDBASSOCOSNAPPOINTREFACTIONPARAM", "test/test-data/example_2000.dxf", 0x393, /* 473 */
      "\252\100\152\001\000\000\000\000\000\000\074\057\340\014\014\200\345\020\024\126\310\100", 176, NULL },

    /* ACDBASSOCOSNAPPOINTREFACTIONPARAM 393 in test/test-data/example_2000.dxf */
    static const struct _unknown_field unknown_dxf_473[] = {
        {   5, "393", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        { 330, "392", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        { 100, "AcDbAssocActionParam", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {   1, "", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        { 100, "AcDbAssocCompoundActionParam", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "1", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        { 360, "394", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        { 330, "0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        { 100, "ACDBASSOCOSNAPPOINTREFACTIONPARAM", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  90, "1", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        {  40, "-1.0", NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1} },
        { 0,    NULL, NULL, 0, BITS_UNKNOWN, {-1,-1,-1,-1,-1}}
    };

I prefer the data to be compiled in, so it's not on the heap but in
the .DATA segment as const.  And from this data, the programs creates
this log:

    ACDBASSOCOSNAPPOINTREFACTIONPARAM: 0x393 (176) test/test-data/example_2000.dxf
      =bits: 010101010000001001010110100000000000000000000000000000000000000000000
      0000000000000111100111101000000011100110000001100000000000110100111000010000
      0101000011010100001001100000010
      handle 0.2.393 (0)
      search 5:"393" (24 bits of type HANDLE [0]) in 176 bits
      =search (0): 010000001100000011001001
      handle 4.2.392 (0)
      search 330:"392" (24 bits of type HANDLE [1]) in 176 bits
      =search (0): 010000101100000001001001
      handle 8.0.0 (393)
      search 330:"392" (8 bits of type HANDLE [1]) in 176 bits
      =search (0): 00000001
    330: 392 [HANDLE] found 3 at offsets 75-82, 94, 120 /176
    100: AcDbAssocActionParam
      search 90:"0" (2 bits of type BL [3]) in 176 bits
      =search (0): 00
    90: 0 [BL] found >5 at offsets 8-9, 9, 10, 11, 12, ... /176
      search 1:"" (2 bits of type TV [4]) in 176 bits
      =search (0): 00
    1:  [TV] found >5 at offsets 8-9, 9, 10, 11, 12, ... /176
    100: AcDbAssocCompoundActionParam
      search 90:"0" (2 bits of type BL [6]) in 176 bits
      =search (0): 00
    90: 0 [BL] found >5 at offsets 8-9, 9, 10, 11, 12, ... /176
      search 90:"0" (2 bits of type BL [7]) in 176 bits
      =search (0): 00
    90: 0 [BL] found >5 at offsets 8-9, 9, 10, 11, 12, ... /176
      search 90:"1" (10 bits of type BL [8]) in 176 bits
      =search (0): 0000001000
    field 90 already found at 176
      search 90:"1" (10 bits of type BL [8]) in 7 bits
      =search (169): 0000001000
      search 90:"1" (10 bits of type BS [8]) in 7 bits
      =search (169): 0000001000
      handle 3.2.394 (0)
      search 360:"394" (24 bits of type HANDLE [9]) in 176 bits
      =search (0): 010011001100000000101001
      handle 2.2.394 (393)
      search 360:"394" (24 bits of type HANDLE [9]) in 176 bits
      =search (0): 010001001100000000101001
      handle 3.2.394 (393)
      search 360:"394" (24 bits of type HANDLE [9]) in 176 bits
      =search (0): 010011001100000000101001
      handle 4.2.394 (393)
      search 360:"394" (24 bits of type HANDLE [9]) in 176 bits
      =search (0): 010000101100000000101001
      handle 5.2.394 (393)
      search 360:"394" (24 bits of type HANDLE [9]) in 176 bits
      =search (0): 010010101100000000101001
      handle 6.0.0 (393)
      search 360:"394" (8 bits of type HANDLE [9]) in 176 bits
      =search (0): 00000110
    360: 394 [HANDLE] found 2 at offsets 109-116, 122-129 /176
      search 90:"0" (2 bits of type BL [10]) in 176 bits
      =search (0): 00
    90: 0 [BL] found >5 at offsets 8-9, 9, 10, 11, 12, ... /176
      search 90:"0" (2 bits of type BL [11]) in 176 bits
      =search (0): 00
    90: 0 [BL] found >5 at offsets 8-9, 9, 10, 11, 12, ... /176
      handle 4.0.0 (0)
      search 330:"0" (8 bits of type HANDLE [12]) in 176 bits
      =search (0): 00000010
    330: 0 [HANDLE] found 2 at offsets 8-15, 168-175 /176
    100: ACDBASSOCOSNAPPOINTREFACTIONPARAM
      search 90:"0" (2 bits of type BL [14]) in 176 bits
      =search (0): 00
    90: 0 [BL] found >5 at offsets 8-9, 9, 10, 11, 12, ... /176
      search 90:"1" (10 bits of type BL [15]) in 176 bits
      =search (0): 0000001000
    field 90 already found at 168
      search 90:"1" (10 bits of type BL [15]) in 7 bits
      =search (169): 0000001000
      search 90:"1" (10 bits of type BS [15]) in 7 bits
      =search (169): 0000001000
      search 40:"-1.0" (66 bits of type BD [16]) in 176 bits
      =search (0): 000000000000000000000000000000000000000000000000001111001111010000
    40: -1.0 [BD] found 1 at offset 32-97 /176
    66/176=37.5%
    possible: [        8....8187        7......xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
    xxxxxxxxxxxxxxxxxxxxxxxxxxxx..81  77  7....8118.........9211 77   7..7 7...7   7..7
    7..7 77  xxxxxxxx]

It converts each blob into bits of 0 or 1, converts each DXF field to
some binary types, also logged as bits, then some handwritten *membits()*
search similar to `memmem()` or `strstr()` searches the bitmask in the blob
and records all found instances. In the printed *possible [ ]* array the
xxxx represents unique finds, `1-9` and `.` multiple finds and space
holes for unknown fields, not represented in the DXF, DWG only
fields. These can be guessed from the documentation and some thinking.

Most fields itself are specialized run-length bit-encoded, so a 0.0
needs only 2 bits 10, an empty string needs the same 2 bits 10, the
number 0 as BL (bitlong) needs 2 bits 10, and 90:"1", i.e. the number
1 as BL (bitlong) needs 10 bits 0010000000. So you really need unique
values in the sample data to get enough unique finds. In this bad
example, which so far really is the best example in my data I get 37.5% of
exact matches, with 6x 90:0, i.e. 6 times the number 0. You won't know
which binary 00 is the the real number 0.  Conversion from
strings to floats is also messy and inprecise. While representing a
double as 64 binary bits is always properly defined in Intel chips,
the reverse is not true, respresenting the string as double can lead
to various representations and I search various variants cutting off
the mantissa precision to find our matching binary double.

What I'll be doing then is to shuffle the values a bit in the DXF to
represent uniquely identifiable values, like 1,2,3,4,5,6, convert this
DXF back to a DWG, and analyse this pair again. This is e.g. what I did to
uniquely identify the position of the header variables in earlier DWG
versions.

Bad percentages are not processed anymore and removed from the
program.  So I create a constant feedback loop, with the program
creating these logs, and a list of classes to skip and permute to
create better matches. I could do this within my program for a
complete self-learning process, but I rather create logfiles,
re-analyse them, adjust the data structures shown above, re-compile
the program and run it again. Previously I did such a re-compilation
step via shared modules, which I can compile from within the program,
dlload and dlunload it, but this is silly. Simple C structs on disc
are easier to follow than shared libs in memory.  I also store the
intermediate steps in git, so I can check how the progress of the
self-improvement evolves, if at all. Several such objects were getting
worse and worse deviating to 0%, because there were no unique values
and finds anymore.  Several representations are also still wrong, some
text values are really values from some external references, such as
the layer name.

So this was a short intro into massive parallel processing,
asynchronous processing, and machine-learning: a self-improving program.
The code in question is here:
https://github.com/LibreDWG/libredwg/tree/master/examples
All the `*.inc` and `*.skip` files are automatically created by make -C examples regen-unknown.

The initial plan was to create a more complex backtracking solver to
find the best matches for all possible variants, but step-wise
refinement in controllable loops and usage of several trivial tools is
so far much easier than real AI. AI really is trivial if you do it
properly.

Followed by https://savannah.gnu.org/forum/forum.php?forum_id=9203 for the actual AI part with picat.