Challenge: code a disasembler <1 day & <512 Byte's

Index > Main > Challenge: code a disasembler <1 day & <512 Byte's

Author

Thread

DOS386

Joined: 08 Dec 2006
Posts: 1905

DOS386 14 Feb 2010, 14:34

.

.

.

Again a challenge from me, but, at least, this time, it's different from the usual "get the code and find out what useful it is supposed to do" approach Shocked

Task: code a disassembler with less than 512 Byte's of bloat

Rules:

- The raw binary routine counts
- "charout", "spaceout", "eol", "stringout" & "hexout" routines may be outsourced and barred out from bloat counting
- No external/system code may be accessed (except for console output)
- Functional executable (DOS16/DOS32/Win32) with test code is needed, the test code and executable/startup overhead may be barred out from bloat counting (consider that a valid PE can't be < 1 KiB Shocked

)
- Input is a buffer in memory of given size, output is screen
- Get the best of 512 Byte's, beating stuff like OBJCONV & Co is not required (but if you can Idea

...)
- Buffer size must be respected precisely, and there may be no missaligned memory accesses
- Candidates being able to decode at least some types of operands are preferred from those knowing only 1-Byte instructions or throwing just "db"'s ...
- Candidates suggesting a plausible usefulness is "some" cases are preferred from those being apparently useless
- There may be "unknown" instructions, but they have to be handled "reasonably"
- The code must be safe, there may be no input data causing crash, hang, deadloop, reading outside defined buffer, garbage output, ...

No code posted yet, maybe (much) later (I'll be probably busy ...) ... see shot (WtF ???).

14 Feb 2010, 14:34

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20518
Location: In your JS exploiting you and your system

revolution 14 Feb 2010, 15:07

What is with the 'movntq' without the mmx parameters? What was wrong with 'mov' like everybody uses?

14 Feb 2010, 15:07

Plue

Joined: 15 Dec 2005
Posts: 151

Plue 14 Feb 2010, 15:19

You can't fit all the mnemonic strings in 512 bytes.

14 Feb 2010, 15:19

DOS386

Joined: 08 Dec 2006
Posts: 1905

DOS386 14 Feb 2010, 15:19

revolution wrote:

wrong with 'mov'

bloat + 3 Byte's

Quote:

can't fit all the mnemonic

then it will be incomplete Sad

14 Feb 2010, 15:19

Plue

Joined: 15 Dec 2005
Posts: 151

Plue 14 Feb 2010, 15:22

movntq eax, 0 isn't even a legal instruction. The nt part implies it moves to memory, the q part means it moves a quad. You move a long to register so it's doubly wrong.

14 Feb 2010, 15:22

asmmsa

Joined: 06 Feb 2010
Posts: 45

asmmsa 14 Feb 2010, 16:33

ur kidding.
do you have ANY idea how complex is x86 instruction encoding?
first of all database is needed, containing opcodes and translations.

we have about 255 (1b) + 255 (2b) + 2*255 (3b) instructions. +FPU not sure how many.
most of them support modRM and all modrm in 32 and 64 bit have sib.
now add 3 diffrent sections, 16/32/64 bit.

now, lets go.
first you need an array of prefixes. you put 1's to there irefix is.
then opcode, you have 1 escape to 2 bytes, 16 escapes to FPU, in 2 byte you have 2 escapes to 3b. but first you have to specify CR0.PE, EFER.LONG_MODE, and CS.D for default operand and address size. and maybe more if i missed something.

good luck in doing that in 512 bytes. good luck.

iam going to write disasembler, and then debugger. not soon, in few months maybe. first i master architecture and instructions.
i think database will be about < 10kb, not sure yet, must think of nice compatible format. 512 bytes is just a joke, even with crossmodyfing code. its just nearly-impossible. there is no scheme between opcode and its function, and even name, you need database.

14 Feb 2010, 16:33

Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania

Borsuc 14 Feb 2010, 18:26

Maybe the database can be stored in another file and only the code in the executable?

_________________
Previously known as The_Grey_Beast

14 Feb 2010, 18:26

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20518
Location: In your JS exploiting you and your system

revolution 14 Feb 2010, 18:40

Maybe the DB and the executable can be stored in other files and you just have a <512byte loader Razz

14 Feb 2010, 18:40

f0dder

Joined: 19 Feb 2004
Posts: 3175
Location: Denmark

f0dder 15 Feb 2010, 09:50

Borsuc wrote:

Maybe the database can be stored in another file and only the code in the executable?

Perhaps not valid in the context of this challenge, but not a bad idea in and by itself. I'd definitely base a disassembler project off a data source (whether a sqlite database or XML source), and auto-generate tables from that.

_________________

- carpe noctem

15 Feb 2010, 09:50

asmmsa

Joined: 06 Feb 2010
Posts: 45

asmmsa 15 Feb 2010, 10:28

nope, database is bad idea, i think.

better make lookup tables, and process each instruction independly.

lookup table would hold dispatch address and attributes and presence of modrm, support architecture in means of bitmask (each bit = diffrent cpu. set = supported, not set = not suported). or maybe just make it for single cpu, because opcode may be reused for other instruction.

yeah, without support type, just address, and there do what needs to be done, maybe optimizing by call to function like parse_modrm/parse_sib/etc.

15 Feb 2010, 10:28

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20518
Location: In your JS exploiting you and your system

revolution 15 Feb 2010, 13:48

With less than an hour to go before this contest expires I wonder if anyone has a submission. The timeline was very tight. It didn't even fall completely within the weekend.

15 Feb 2010, 13:48

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20518
Location: In your JS exploiting you and your system

revolution 15 Feb 2010, 14:32

With mere seconds to go before the deadline I have a super-duper-uber-special submission. This is so good you won't believe it. And I am posting the source code and everything. Do I win?

Code:

UberDisassembler:
     ;esi=buffer
 ;ecx=length in bytes
    .disassemble_the_next_byte:
 jecxz   .we_are_done
        lodsb
       push    esi ecx
     cmp     al,0x90
     jz      .show_uber_detailed_description_of_this_instruction_with_usage_hints_and_everything
 push    eax
 mov     al,'d'
    call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     mov     al,'b'
    call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     mov     al,' '
    call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     mov     al,'0'
    call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     mov     al,'x'
    call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     shr     al,4
        cmp     al,10
       sbb     al,069h
     das
 call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     pop     eax
 and     al,0xf
      cmp     al,10
       sbb     al,069h
     das
 call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     mov     al,13
       call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     mov     al,10
       call    [TheOSFunctionForPrintingAByteInALToTheConsole]
    .restore_registers_and_disassemble_the_next_byte:
        pop     ecx esi
     jmp     .disassemble_the_next_byte
    .show_uber_detailed_description_of_this_instruction_with_usage_hints_and_everything:
  mov     esi,UberMessage
    .next_byte_of_message:
   lodsb
       test    al,al
       jz      .restore_registers_and_disassemble_the_next_byte
    push    esi
 call    [TheOSFunctionForPrintingAByteInALToTheConsole]
     pop     esi
 jmp     .next_byte_of_message
    .we_are_done:
      jmp     [TheOSFunctionToQuitTheApplication]

UberMessage:     db      'db 0x90',9,';xchg eax,eax, aka "nop", ',\
                           'can be used to fill alignment ',\
                               'gaps or to use up time. Affects',\
                              ' no internal CPU state',13,10

TheOSFunctionForPrintingAByteInALToTheConsole   dd ?
TheOSFunctionToQuitTheApplication               dd ?

The raw binary routine counts [tick]
"charout", "spaceout", "eol", "stringout" & "hexout" routines may be outsourced and barred out from bloat counting [tick]
No external/system code may be accessed (except for console output) [tick]
Functional executable (DOS16/DOS32/Win32) with test code is not needed, the test code and executable/startup overhead may be barred out from bloat counting (consider that a valid PE can't be < 1 KiB) [tick]
Input is a buffer in memory of given size, output is screen [tick]
Get the best of 512 Byte's, beating stuff like OBJCONV & Co is not required (but if you can Idea ...) [not needed]
Buffer size must be respected precisely, and there may be no missaligned memory accesses [tick]
Candidates being able to decode at least some types of operands are preferred from those knowing only 1-Byte instructions or throwing just "db"'s ... [tick]
Candidates suggesting a plausible usefulness is "some" cases are preferred from those being apparently useless [tick]
There may be "unknown" instructions, but they have to be handled "reasonably" [tick]
The code must be safe, there may be no input data causing crash, hang, deadloop, reading outside defined buffer, garbage output, ... [tick]

15 Feb 2010, 14:32

DOS386

Joined: 08 Dec 2006
Posts: 1905

DOS386 17 Mar 2010, 07:32

Well, the long awaited solution Smile

Download now (10'871 Byte's) : id=4878

revolution wrote:

Quote:

And I am posting the source code and everything.

Really ???

Quote:

[*] Functional executable (DOS16/DOS32/Win32) with test code is not needed, the test code and executable/startup overhead may be barred out from bloat counting (consider that a valid PE can't be < 1 KiB) [tick]

There is none, or did someone kick your attachments again ??? Sad

Quote:

Do I win?

NOT this time. Sad

Thank you for your participation, but a few problems:

- You didn't supply a ready-to-self-test binary or complete source code allowing to brew such Sad

- Your "disassembler" seems to support just 1 instruction, and it's a 1-Byte instruction "NOPE" - yours can't decode any operand at all Sad

Mine knows, at least, 18 instructions and 4 types of operands (+ none)

Flaws of my disassembler:

- "INT" instruction ( $CD ) not recognized
- "INT1" instruction ( $F1 ) not recognized
- "MOV EAX, const" instruction ( $B8 ) not recognized
- Some other instructions not recognized
- Buffer size is fixed to 8 Byte's (variable would be better, maybe 1...16 Byte's would be cool, OTOH > 16 would hardly make sense ...)
- Doesn't return the amount of Byte's successfully disassembled before it gave up

What's also missing so far is the evidence of usefulness of my disassembler, I'm going to supply it later (maybe I'll kill at least some of the flaws also).

Everybody who failed to win this time please don't whine, I'm going to invent and post a new challenge occasionally Shocked

_________________
Bug Nr.: 12345

Title: Hello World program compiles to 100 KB !!!

Status: Closed: NOT a Bug

17 Mar 2010, 07:32

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20518
Location: In your JS exploiting you and your system

revolution 17 Mar 2010, 08:29

DOS386 wrote:

Quote:
Do I win?
NOT this time.

17 Mar 2010, 08:29

edemko

Joined: 18 Jul 2009
Posts: 549

edemko 17 Mar 2010, 08:53

hex2str ?

Code:

        and     al,0xf 
        cmp     al,10 
        sbb     al,069h 
        das

17 Mar 2010, 08:53

DOS386

Joined: 08 Dec 2006
Posts: 1905

DOS386 17 Mar 2010, 09:00

serfasm wrote:

hex2str ? and al,0xf cmp al,10 sbb al,069h das

Already IN, RTFS Idea

17 Mar 2010, 09:00

DOS386

Joined: 08 Dec 2006
Posts: 1905

DOS386 18 Mar 2010, 07:08

serfasm wrote, edited 1'000 times and finaly deleted:

Quote:

18 Mar 2010, 07:08

edemko

Joined: 18 Jul 2009
Posts: 549

edemko 18 Mar 2010, 07:20

DOS386, firs time i was a bit boring with you, then i found you humourous and removed the questions as you had ignored 3 of them. BTW i visit some forum pages for several times for fun or with the need to remember smth forgotten, to give a link mostly for the wasm.ru, etc. Good luck, i'll try not to garbage your topics. Use Olly.

18 Mar 2010, 07:20

rugxulo

Joined: 09 Aug 2005
Posts: 2341
Location: Usono (aka, USA)

rugxulo 23 Mar 2010, 15:34

Quote:

http://www.scene.org/file.php?file=/parties/2000/demobit00/256b/selfdasm.zip&fileinfo

256 B Intro
SELF_DISASSEMBLER
RiXtA (3SC)

Code:

Archive:  selfdasm.zip
 Length   Method    Size  Cmpr    Date    Time   CRC-32   Name
--------  ------  ------- ---- ---------- ----- --------  ----
    1813  Defl:X      707  61% 02/26/2000 12:57 63872fb7  SelfDasm.asm
     256  Defl:N      251   2% 02/26/2000 13:01 ab8d73aa  SELFDASM.COM
      43  Stored       43   0% 02/26/2000 13:02 54b66408  SelfDasm.txt
    2017  Defl:X      822  59% 07/25/2000 17:11 0ec4c4cf  scene.org
--------          -------  ---                            -------
    4129             1823  56%                            4 files

23 Mar 2010, 15:34

DOS386

Joined: 08 Dec 2006
Posts: 1905

DOS386 13 May 2010, 02:19

rugxulo wrote:

Quote:

(nothing except quoting ...)

It's buggy, but works almost as supposed at the end.

Fixed bugs, download now: http://board.flatassembler.net/download.php?id=4963 (4'135 Byte's)

Considerably better than revolution's candidate, although not as useful as mine Wink

EDIT : updated attach

_________________
Bug Nr.: 12345

Title: Hello World program compiles to 100 KB !!!

Status: Closed: NOT a Bug

13 May 2010, 02:19

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum