disasm-based executable's filter

[Bulat Ziganshin]

https://sourceforge.net/tracker/?fun...49&atid=373088 :

I've written a (relatively) small preprocessor/filter for compiled x86 code
that is completely reversible and typically increases compression ratio for
executable files by about 10% compared to the default filter (BCJ) used by
7Zip/LZMA for .EXE files. I guess this might be interesting for NSIS (in
terms of reducing download sizes), but I have no clue about NSIS internals,
so I'm not in the position to submit a full patch that adds this
functionality . Adding it as a feature request seemed like a reasonable
compromise. I've put the code online here:
http://www.farbrausch.de/~fg/code/disfilter/ (written using VC++, but it
should be trivial to get working with other compilers). The actual
algorithm is in dis.cpp, the rest is mainly a small (Windows) demo app.

I've placed the code in the public domain; no strings attached. If you're
interested but have questions about the code or integration problems, feel
free to contact me (my email address is mentioned in readme.txt).

[Bulat Ziganshin]

as source file says, it's filter from kkrunchy, published by the author

firefox.exe: 7,620,696 bytes
all 3 filters, further compressed with lzma:max:
none: 3,004,746 +5.1%
bcj: 2,858,179 --- baseline
bcj2: 2,782,313 -2.7%
dis: 2,591,514 -9.3%
durilca'light: 3,066,324 -> 2,509,209, i.e. its disasm filter improved compression by 18.2%

skype.exe 19,490,344 bytes
none: 8,060,598 +2.6%
bcj/bcj2: 7,856,207 --- baseline
dis: 8,279,426 +5.4%
durilca'light: 9,114,835 -> 8,105,689, i.e. its disasm filter improved compression by 11.1%

probably skype is too complex for this over-smart algorithm

ps: http://freearc.org/download/testing/dispack.exe

[IsName]

as source file says, it's filter from kkrunchy, published by the author

skype.exe 19,490,344 bytes
none: 8,060,598 +2.6%
bcj/bcj2: 7,856,207 --- baseline
dis: 8,279,426 +5.4%
durilca'light: 9,114,835 -> 8,105,689, i.e. its disasm filter improved compression by 11.1%

probably skype is too complex for this over-smart algorithm

ps: http://freearc.org/download/testing/dispack.exe

probably skype.exe is so protected that some assumptions made by this algo are false

[Bulat Ziganshin]

it seems that freearc.exe is protected too: http://forum.ru-board.com/topic.cgi?...&start=1100#14

i rather think that these executables use some untypical coding techniques. at least freearc is written in haskell and this compiler generates code that's somewhat unlike to C compilers output

[JangoFatXL]

it seems that freearc.exe is protected too

[jethro]

Bulat do you plan to incorporate these filters into freearc? Is it possible to use durilca'light exe filter?

[Shelwien]

As to durilca filter, its likely that:
http://www.compression.ru/ds/disasm32.rar
with some additional preprocessing for stored numbers
(results can be compared with durilca -l)

Just that like all Shkarin's sources its posted in incomplete form,
so some work is required to make it usable and reversible.

Also, I kinda don't understand why'd people stop at that level
(splitting the instructions into streams by field type) - its one
thing when its a first ever implementation (like Shkarin's), and
another when there're already a few here and there (like in winrk,paq8 etc).

Anyway, thanks for posting this link, as I wasn't aware of it,
and there're some readable comments inside.

[Bulat Ziganshin]

durilca is closed-source

i will slowly work on integrating dispack into freearc. btw, what's the good name for this filter?

[PAQer]

what's the good name for this filter?

DSM?

[Shelwien]

> durilca is closed-source

disasm32 is not, and adding a decoding mode to it should
be fairly straight-forward, as its a nearly symmetric case.

Also, afaik, the main improvement for it in durilca is the
mentioned number coding, optimized for PPM.
Eg., we have an offset 0x00412300. Plain disasm32
would store it as 00 23 41 00 into a corresponding
stream. While if we'd store it as
0x10 0x20 0x34 0x41 0x52 0x63 0x70 0x80 or
0x34 0x41 0x52 0x63 0x70 0x80 or even
0x34 0x41 0x52 0x63
there would be an improvement with bytewise (or bitwise)
coders, as normally they don't have a 32-bit alignment,
but such preprocessing provides it.

> i will slowly work on integrating dispack into freearc.

That'd be cool.
Especially if you could automatically detect where to switch it on/off :)

> btw, what's the good name for this filter?

Something like "x86 splitter"?

Update:
to be specific, i meant this:
(its an actual stream from durilca 02 preprocessing of acrord32)

Z:\0001e8.019
00000000:  00 01 11 21 31 41 51 6A │ 75 00 CC 00 A1 00 A1 00    
!1AQju ╠ б б
00000010:  01 11 21 31 41 51 6A 75 │ 00 01 11 21 33 41 51 62   
!1AQju 
!3AQb
00000020:  7A 00 09 11 21 31 41 51 │ 61 73 00 01 11 21 31 41   z !1AQas 
!1A
00000030:  51 69 71 00 01 11 27 32 │ 42 52 64 76 00 01 11 27   Qiq 
'2BRdv 
'
00000040:  3B 4E 5B 6D 71 00 01 11 │ 27 33 44 5B 6A 7D 00 01   ;N[mq 
'3D[j} 

00000050:  11 27 32 42 52 68 7D 00 │ 01 11 27 33 44 5B 6A 7D   '2BRh} 
'3D[j}
00000060:  00 01 11 27 32 42 52 6C │ 7A 00 A3 00 A4 00 01 11    
'2BRlz г д 

00000070:  27 37 4E 54 64 7D 00 01 │ 11 21 31 41 55 61 7A 00   '7NTd} 
!1AUaz
00000080:  01 11 27 32 42 52 6F 7D │ 00 F4 00 FD 00 01 11 27   
'2BRo} Ї ? 
'
00000090:  32 42 53 65 79 00 01 11 │ 27 32 42 53 69 7D 00 F4   2BSey 
'2BSi} Ї
000000A0:  00 01 11 21 31 41 52 61 │ 75 00 01 11 21 40 41 51    
!1ARau 
!@AQ
000000B0:  64 80 00 09 11 21 31 41 │ 51 61 72 00 A1 00 01 11   dА !1AQar б 

000000C0:  27 32 42 53 6C 75 00 01 │ 11 26 3A 44 56 67 74 00   '2BSlu 
&:DVgt
000000D0:  01 11 25 31 42 5D 70 78 │ 00 09 11 25 36 49 59 61   
%1B]px %6IYa
000000E0:  71 00 A1 00 A1 00 01 11 │ 26 3A 44 56 67 74 00 01   q б б 
&:DVgt 

000000F0:  11 25 31 43 51 61 71 00 │ 01 11 27 32 42 54 64 79   %1CQaq 
'2BTdy

Update2:
Also, here's an example of what I meant with disasm32:
http://nishi.dreamhosters.com/u/DisAsm32_sh0.rar
It splits the 32-bit "displacements" and "immediates" into
separate streams, and there's already some gain with
rar's ppmd vH:

7.rar  907291 // rar a -m5 -mdg -s- -mce- -mct+ 7 0001e8
8.rar  895807 // rar a -m5 -mdg -s- -mce- -mct+ 8 *.zzz

Unfortunately, its not so easy to apply directly to executables -
disasm32 happily splits non-x86 data as well (text etc), so
segmentation has to be applied first, and only x86 segments
processed. And then, E8 also has to be applied first, because
it can't be applied to already split streams.
Also, it seems that durilca produces a lot more streams - like 20.
These are probably instruction-specific or something.

[Bulat Ziganshin]

DSM?

BSM

Eugene, why you think that it will be better to work starting with disasm32? dispack already provides splitting into 19 streams and decoding

[Shelwien]

> Eugene, why you think that it will be better to work starting with disasm32?

I don't Surely this dispack is more readable and would be easier to integrate.
I just posted what I know about durilca's exe filter

And considering the name, I'd still reserve the "disasm" derivatives for
something more advanced that should appear eventually.
For example, its usually possible to restrict jmp/call targets to instruction
starts only, and detect intrinsics interleaved with other code, etc.

[Bulat Ziganshin]

one more test: icl executables, 64,466,576 bytes

compression with exefilter+delta+lzma:max:
none: 14,004,381 bytes
bcj: 13,137,337 bytes
bcj2: 12,243,408 bytes
dispack: 11,714,439 bytes

[encode]

skype.exe 19,490,344 bytes
none: 8,060,598 +2.6%
bcj/bcj2: 7,856,207 --- baseline
dis: 8,279,426 +5.4%
durilca'light: 9,114,835 -> 8,105,689, i.e. its disasm filter improved compression by 11.1%

probably skype is too complex for this over-smart algorithm

Quite probably, that Skype contains lots of graphics/image resources - it's to big for code-only EXE. Try to test on EXEs that contains really big amount of a code - photoshop.exe, UT3.exe (Unreal Tournament 3 Game executable)...

[Bulat Ziganshin]

dispack processes only code section. but it seems that even this section contains something unusual in skype (and freearc itself)

[evg]

used mencoder executable as it is quite large and contains mostly code

12231468 mencoder.exe.bcj2
12222615 mencoder.exe.bcj
12222608 mencoder.exe.paq8px
12222483 mencoder.exe
12067731 mencoder.exe.dis
 5229585 mencoder.exe.bcj.quad
 5173892 mencoder.exe.paq8px.quad
 5144346 mencoder.exe.bcj2.quad
 5013292 mencoder.exe.bcj.balz
 4980072 mencoder.exe.quad
 4937866 mencoder.exe.paq8px.balz
 4880998 mencoder.exe.bcj.lzpm
 4846274 mencoder.exe.bcj2.balz
 4819259 mencoder.exe.paq8px.lzpm
 4783326 mencoder.exe.balz
 4733565 mencoder.exe.bcj2.lzpm
 4703066 mencoder.exe.dis.quad
 4685316 mencoder.exe.lzpm
 4437036 mencoder.exe.dis.balz
 4435922 mencoder.exe.bcj.lzma2
 4435237 mencoder.exe.bcj.lzma1
 4389096 mencoder.exe.lzma2
 4388421 mencoder.exe.lzma1
 4359169 mencoder.exe.paq8px.rzm
 4352200 mencoder.exe.dis.lzpm
 4267609 mencoder.exe.paq8px.lzma2
 4266954 mencoder.exe.paq8px.lzma1
 4265914 mencoder.exe.bcj2.lzma2
 4265260 mencoder.exe.bcj2.lzma1
 4264786 mencoder.exe.bcj.mcomp2-f3x
 4217834 mencoder.exe.bcj.rzm
 4198041 mencoder.exe.mcomp2-f3x
 4113134 mencoder.exe.bcj2.rzm
 4069037 mencoder.exe.bcj2.mcomp2-f3x
 4057161 mencoder.exe.rzm
 4049583 mencoder.exe.paq8px.mcomp2-f3x
 3934852 mencoder.exe.dis.lzma2
 3934236 mencoder.exe.dis.lzma1
 3853420 mencoder.exe.dis.rzm
 3760805 mencoder.exe.dis.mcomp2-f3x

used:
 quad 1.12 -x
 balz 1.15 ex
 lzpm 0.16 ex
 xz   0.49b --lzma1,2=dict=16M,nice=273,depth=10000 -F raw --suffix=.lzma1,2
 rzm  0.07h
 mcomp2 2.3 -mf3x -M256m

best regards
evg

[Bulat Ziganshin]

Now i'm adding DisPack to FreeArc.of course, there is problem of executable code detection. Now i split data into 16 kb blocks and use the following filter:

EXETYPE detect (BYTE *buf, int len)
{
  double e8=0, exe=0, obj=0;
  for (BYTE *p=buf; p+4<buf+len; p++)
  {
    if (*p == 0xE8)
    {
      e8++;
      if (p[4]==0xFF)
        exe++;
      if (p[4]==0)
        obj++;
    }
  }
  return  e8/len >= 0.002  &&  (exe+obj)/e8 >= 0.20  &&  exe/e8 >= 0.01?  CODE : DATA;
}

i've attached code&executable

what's the better ways to detect x86 code? in particular how to find exact boundaries of code, not aligned to 16 kb chunks? now i think about searching in boundary chunks for first/last E8 instruction with argument of form 0x00... or 0xFF...

[Shelwien]

First, some real stats with explanations:

  266237 - 74  // JZ short
  270527 - C0  // frequent modr/m byte, like for xor eax,eax
  287474 - FE  // eg. 8B8DE4FEFFFF mov ecx,[ebp][-0000011C]
  295194 - 0F  // extension byte, eg. 0FB7C0 movzx eax,ax
  317843 - 85  // 85D2 test edx,edx (test for zero)
  326395 - 4D  // modr/m with ecx and ebp: 8B4DF8 mov ecx,[ebp][-08] (likely VS specific)
  351547 - 04
  400960 - 6A  // push byte: 6A01 push 001
  407908 - 50  // push eax
  407956 - 83  // arithmetics: 83E010 and eax,010; 83C820 or eax,020; also add,sub,cmp
  437390 - 08
  481820 - 8D  // 8D45CC lea eax,[ebp][-34]
  489930 - 45  // modr/m with eax and ebp: 89450C mov [ebp][0C],eax
  538288 - 02
  562981 - E8  // call
  656140 - 89  // mov mem,reg: 894610 mov [esi][10],eax
  838642 - 01
  839087 - 90  // nop
 1864004 - FF
 1950362 - 8B  // mov reg,reg: 8BF9 mov edi,ecx
 4492195 - 00  // FE,FF,00,01,02,04,08 are mostly from constants, not really code-specific
31752798 - total


   90185 - 6A 01 // 6A01 push 001
   90282 - 89 45 // 89450C mov [ebp][0C],eax
   90326 - FA 02 // sample-specific
   91292 - 5D C2 // 5D C20400  pop ebp; retn 00004
   92554 - 83 C4 // 83C414 add esp,014
   92807 - 85 C0 // 85C0 test eax,eax
   96856 - 90 8B
   97879 - C7 45 // C745D401000000 mov d,[ebp][-2C],000000001
  113417 - 00 90
  119613 - 8B 45 // 8B4508 mov eax,[ebp][08]
  132747 - 02 00
  143732 - 45 FC // [ebp-4]: 8B45FC mov eax,[ebp][-04]
  173247 - 8B 4D // 8B4D0C mov ecx,[ebp][0C] (VS specific; ebp stack frame + ecx="this")
  184642 - FF 8B // C745FCFFFFFFFF 8BC6 mov d,[ebp][-04],0FFFFFFFF mov eax,esi
  207634 - 01 00
  242310 - 00 8B // 8B9098000000 8BCE mov edx,[eax][00000098] mov ecx,esi
  599218 - 90 90 // nop nop
  797362 - FF FF
 2456286 - 00 00
31752798 - total

> what's the better ways to detect x86 code?

There's no perfect way even with complex reverse-engineering tools,
but for a rough estimation it seems reasonable to parse the section
layouts in exe headers - at least it allows to discard data sections.

> in particular how to find exact boundaries of code,
> not aligned to 16 kb chunks?

Why, by disassembling - x86 parsing can be done by a simple
state machine, so its not really slow or anything.

> now i think about searching in boundary chunks for
> first/last E8 instruction with argument of form 0x00...
> or 0xFF...

There're also function prologs/epilogs and alignment paddings
(with "nops" of various lengths).
E8 is actually much less necessary for the code - there's
FF15 for import calls, so its not unlikely to encounter
a case with lots of (eg.unrolled) code and no E8.