4
\$\begingroup\$

Here is a challenge:

What is the shortest possible compiled program? Writing one line programs are fun, but they often lean on language libraries that get pulled into the final bits. How lean can you get the 'scaffolding' that supports and hooks into the compiled instructions? This seems like an interesting question because then the smallest possible program for problem 'X' is going to be: (Smallest scaffolding bytecode size) + (smallest instructions to solve probem 'x")

The code must run on a common modern OS, such as *nix or windows (no embedded hex that runs on 1970s era mobos and chips). Doesn't matter if you are just exiting immediately, what language / platform produces the smallest bytecode? If you can get bytecode that is below a few dozen bytes, show your output.

I'll kick this off by setting a (very) low bar:

int main() 
{
    return 0;
}

This compiled in VS Pro 2022 as a release build c++ app with no changes to the default build flags produces an 11k exe that runs in windows. I think I might be able to get this smaller by playing with the build flags and possibly by building it as a 32 bit c app. I'm digging into some ASM docs to see if you can still hand write exes that run on a modern OS

Lets say that IL output is fair game, but non-compiled script languages need not apply...

A FEW ADDITIONAL NOTES

I used the definition of a 'modern' OS as one of the criteria. People are getting this right, but I am talking about either a 32 bit or 64 bit build. I think that 32 bit is generally going to be smaller in size, but feel free to try out 64 bit builds if you are so inclined.

Be sure that you aren't making debug builds in your compiler, as this will probably include additional debugging symbols. No need for debugging these apps, they are going to run perfectly on the first try, right?

\$\endgroup\$
8
  • 2
    \$\begingroup\$ −1 Since code length is almost negligible, it seems the challenge focuses on tweaking compiler parameters. \$\endgroup\$ Oct 6, 2023 at 21:15
  • 5
    \$\begingroup\$ Might want to read muppetlabs.com/~breadbox/software/tiny/teensy.html \$\endgroup\$ Oct 6, 2023 at 21:43
  • 2
    \$\begingroup\$ I think there needs to be a scoring mechanism aside from the output size. I don't think @KaiBurghardt's reason for downvoting really describes the actual problem here; I think this would be a great challenge if, e.g., you also had to try to minimize the size of the args passed to the compiler (with scoring designed carefully in such a way that that can't be trivially bypassed, ofc) \$\endgroup\$ Oct 7, 2023 at 2:48
  • 1
    \$\begingroup\$ Might want to specify what exactly would be a valid submission. You mention that IL output is allowed—does that mean LLVM IR or C-- are allowed? The title suggests "no", but it's left unclear in the question itself. \$\endgroup\$ Oct 7, 2023 at 5:51
  • \$\begingroup\$ @SuperStormer, I wanted to explore the question of how small can you make an executable, and there are many examples all over the net of people doing crazy things with a scant few assembly instructions. When you start working small, you start to notice that a lot of compilers seem to gen a lot of 'wrapper' on the actual bytecode that is being run, and I started to ask, 'How small can you get the boiler plate for one of these apps'? I nixed scripting languages because they depend on an interpreter to run, and are sort of dodging the core problem of truly minimal code. \$\endgroup\$
    – Roger Hill
    Oct 7, 2023 at 23:59

5 Answers 5

6
\$\begingroup\$

x86 assembly DOS .COM file 1 byte

ret # assembles to 0xC3

COM files are executable and have no header or other mandatory content. An empty COM file produces an error, so the shortest executable COM file consists of just the RET instruction.

One way of testing this is by using DEBUG from the DOS prompt, tested using MSDOS 6.22 via pcjs. The following are typed as sequential lines (including a blank line after ret). However, this should also run under 32-bit Windows 7 or 10 which are ‘modern’ OSes.

DEBUG
n c:\test.com
a
ret

rcx
1
w
q
C:\test.com

Mathias Bynen’s small GitHub repo is also a useful resource for this.

\$\endgroup\$
3
  • \$\begingroup\$ 'COM files are executable and have no header or other mandatory content.' This is really interesting stuff. \$\endgroup\$
    – Roger Hill
    Oct 7, 2023 at 23:40
  • 1
    \$\begingroup\$ I went back and read about the history of .com files. I have know that they were executable files came from the old days (I started coding in as a kid the 80's) but I didn't know that they came from the VAX era. Apparently, they were supported for backwards compatibility purposes. It makes sense in this context that they would have very little in the way of headers to allow for portability. I could see this level of simplicity being required given the costs and limitations of hardware of the era. Very cool. \$\endgroup\$
    – Roger Hill
    Oct 10, 2023 at 6:28
  • \$\begingroup\$ having run that program once, you could then run a zero-byte program without error. \$\endgroup\$ Oct 17, 2023 at 18:45
4
\$\begingroup\$

FASM (32-bit ELF executable), 87 bytes

Larger than the final ELF-file in the blog post linked in the comments of the question, but less than a third of the size of the smallest output they were able to generate without directly creating the ELF-file, and a few bytes shorter than the shortest program without overlapping sections in the ELF-file

format ELF executable 3 ; 32 bit elf
segment readable executable
entry $
  inc   eax   ; eax and ebx default to 0
  int   0x80  ; syscall 1 (exit) with exit code 0

produces the following (statically linked, 32-bit) ELF-executable:

457f 464c 0101 0301 0000 0000 0000 0000
0002 0003 0001 0000 8054 0804 0034 0000
0000 0000 0000 0000 0034 0020 0001 0028
0000 0000 0001 0000 0000 0000 8000 0804
8000 0804 0057 0000 0057 0000 0005 0000
1000 0000 cd40 0080

As far as I can tell the actual code takes only 3 bytes, so the main way for reducing the file size would be to somehow convince the assembler to make the different parts of the ELF-file overlap (like in the blog post)

\$\endgroup\$
2
  • \$\begingroup\$ −1 The challenge is stripping down the basic skeleton in compiled programming languages. Compilation means translation from a more powerful programming language (e. g. Java) to a less powerful programming language (e. g.  Java Bytecode or another Intermediate Language). Evidently this is not the case with assembly languages. The assembly mnemonics directly correspond to instructions in machine code, so assembly language is just as capable of describing an algorithm as machine code is. \$\endgroup\$ Oct 7, 2023 at 9:20
  • \$\begingroup\$ This is pretty cool. The last four bytes looks like your syscall. and the eax/ebx register ref looks like the prior four bytes. It looks to me like there is ~81 bytes of header for the OS to read. I am really curious to know what these 81 bytes are telling the OS to do. \$\endgroup\$
    – Roger Hill
    Oct 8, 2023 at 0:08
4
\$\begingroup\$

Python 3.4.10 (.pyc file), 63 bytes

00000000: ee0c 0d0a 50a6 2265 0000 0000 6300 0000  ....P."e....c...
00000010: 0000 0000 0000 0000 0001 0000 0043 0000  .............C..
00000020: 00f3 0200 0000 4753 a900 a900 a900 a900  ......GS........
00000030: a900 da00 da00 0100 0000 f300 0000 00    ...............

Generation script:

import marshal
import types

# taken from a pyc file generated from a blank file
header = b'\xee\x0c\r\nP\xa6"e\x00\x00\x00\x00'

open("c.pyc","wb").write(
    header + 
    # b'\x47S' == LOAD_BUILD_CLASS + RETURN_VALUE
    # shorter than LOAD_CONST None and allows for empty co_consts tuple
    marshal.dumps(types.CodeType(0,0,0,1,67,b'\x47S',(),(),(),'','',1,b''))
    # replace TYPE_REF to empty string w/ TYPE_SHORT_ASCII_INTERNED b/c it's shorter
    .replace(b'r\x02\x00\x00\x00',b'\xda\x00')
    # replace TYPE_REF to empty tuple w/ empty TYPE_SMALL_TUPLE
    .replace(b'r\x01\x00\x00\x00',b'\xa9\x00'))

I believe that Python 3.4-3.5 .pyc files should be the shortest for Python 3, as they have TYPE_SHORT_ASCII and TYPE_SMALL_TUPLE (both 3.4+) and don't have co_posonlyargcount (3.8+), PEP 552 (3.7+), nor fixed 2-byte opcodes (3.6+).

Python 2.7.18 (.pyc file), 79 bytes

00000000: 03f3 0d0a 4496 2265 6300 0000 0000 0000  ....D."ec.......
00000010: 0001 0000 0043 0000 0073 0400 0000 6400  .....C...s....d.
00000020: 0053 2801 0000 004e 2800 0000 0028 0000  .S(....N(....(..
00000030: 0000 2800 0000 0028 0000 0000 7400 0000  ..(....(....t...
00000040: 0052 0000 0000 0100 0000 5200 0000 00    .R........R....

Generation script:

import marshal
import types
header = '\x03\xf3\r\nD\x96"e'
# b"d\x00\x00S" == LOAD_CONST 0 + RETURN_VALUE
code = types.CodeType(0, 0, 1, 67, b"d\x00\x00S", (None,), (), (), "", "", 1, "")
# TYPE_STRING and TYPE_STRINGREF are the same length in Python 2.7
open("a.pyc", "w").write(header + marshal.dumps(code))

Unsure if this is the shortest Python 2 version; I don't have access to any earlier Python 2 versions to test.


Thanks to https://github.com/python/cpython/blob/3.4/Python/marshal.c and https://github.com/fedora-python/marshalparser/

\$\endgroup\$
3
\$\begingroup\$

All from the blog post linked in the question comments; this is not my work, all credit goes to Brian Raiter: https://www.muppetlabs.com/~breadbox/software/tiny/return42.html

NASM (32-bit Linux x86 ELF), 45 bytes

BITS 32
  
        org 0x00010000
  
        db  0x7F, "ELF"
        dd  1
        dd  0
        dd  $$
        dw  2
        dw  3
        dd  _start
        dd  _start
        dd  4
_start: mov bl, 42          ; set ebx to exit code 42
        xor eax, eax        ; set eax to 1 (exit syscall)
        inc eax
        int 0x80            ; and exit
        db  0
        dw  0x34
        dw  0x20
        db  1
  
filesize    equ $ - $$

(https://www.muppetlabs.com/~breadbox/software/tiny/tiny-i386.asm.txt)

NASM (64-bit Linux x86 ELF), 80 bytes

BITS 64

        org 0x500000000

        db  0x7F            ; e_ident
_start: db  "ELF"           ; 3 REX prefixes (no effect)
        and eax, 0x00000101
        lea edi, [rax + 42] ; rdi = exit code
        mov al, 60          ; rax = syscall number
        syscall             ; exit(rdi)
        dw  2               ; e_type
        dw  62              ; e_machine
        dd  1               ; e_version
phdr:   dd  1               ; e_entry   ; p_type
        dd  5               ; p_flags
        dq  phdr - $$       ; e_phoff   ; p_offset
        dq  phdr            ; e_shoff   ; p_vaddr
        dd  0               ; e_flags   ; p_paddr
        dw  0x40            ; e_ehsize  
        dw  0x38            ; e_phentsize
        dw  1               ; e_phnum   ; p_filesz
        dw  0x40            ; e_shentsize
        dw  0               ; e_shnum
        dw  0               ; e_shstrndx
        dq  0x00400001      ; p_memsz
        dq  0               ; p_align

(https://www.muppetlabs.com/~breadbox/software/tiny/tiny-x64.asm.txt)

NASM (Linux x86 a.out), 35 bytes

BITS 32

        org     0x1000
                            ; a.out header
        dd      0x006400CC  ;   a_info
        dd  filesize        ;   a_text
        dd      0           ;   a_data
_start:     mov bl, 42      ; set exit code ;   a_bss
        jmp short part2
        dd  0               ;   a_syms
        dd  _start          ;   a_entry
        dd  0               ;   a_trsize
        dd  0               ;   a_drsize

part2:  inc eax             ; set syscall number
        int 0x80            ; exit(ebx)

filesize    equ $ - $$

(https://www.muppetlabs.com/~breadbox/software/tiny/tiny-aout.asm.txt)

\$\endgroup\$
1
  • \$\begingroup\$ This was a truly amazing read you found. It is certainly the most clever solution to the problem. \$\endgroup\$
    – Roger Hill
    Oct 15, 2023 at 9:27
2
\$\begingroup\$

C (GCC, Linux, x86 32-bit), 260 bytes

Feel free to edit this answer if you find ways to improve the score

source code:

int _start(void){    // using libc significantly increases the score -> need to use _start instead of main
  asm("inc  %eax;"
      "int  $0x80"); // exit program seems to be the only way to exit a program without using the standard library
}

compiler options: gcc -nostdlib -Oz small.c -Qn -m32 -static -s -N -Wl,--build-id=none -fno-asynchronous-unwind-tables

hexdump:

00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 0300 0100 0000 7480 0408 3400 0000  ........t...4...
00000020: 8c00 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
00000030: 0300 0200 0100 0000 7400 0000 7480 0408  ........t...t...
00000040: 7480 0408 0400 0000 0400 0000 0700 0000  t...............
00000050: 0100 0000 51e5 7464 0000 0000 0000 0000  ....Q.td........
00000060: 0000 0000 0000 0000 0000 0000 0600 0000  ................
00000070: 1000 0000 40cd 80c3 002e 7368 7374 7274  [email protected]
00000080: 6162 002e 7465 7874 0000 0000 0000 0000  ab..text........
00000090: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000b0: 0000 0000 0b00 0000 0100 0000 0700 0000  ................
000000c0: 7480 0408 7400 0000 0400 0000 0000 0000  t...t...........
000000d0: 0000 0000 0100 0000 0000 0000 0100 0000  ................
000000e0: 0300 0000 0000 0000 0000 0000 7800 0000  ............x...
000000f0: 1100 0000 0000 0000 0000 0000 0100 0000  ................
00000100: 0000 0000                                ....
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Problem with the alignment requirements is that the code has to be in an executable page and the data in a writeable page and some processors don't allow a page to be both executable and writeable. \$\endgroup\$
    – Neil
    Oct 8, 2023 at 23:33
  • \$\begingroup\$ I recall hearing that most modern processors only allocate memory in 4k chunks. The observation that @Neil made about an executable and data page might be evidence of this fact. Perhaps the compiler is padding out the pages? \$\endgroup\$
    – Roger Hill
    Oct 9, 2023 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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