So, is it possible?

Note: I’m also learning. If you find any wrong or misleading information, please write to me.
Note: All the code you may find at my github

Okey, okey, okey. Of course it is possible! But it is not so easy when we are talking about fully compiled languages as C. In python it is so much easier! So in case you don’t want to know how to do it in C, just go ahead and try it in some scripting language (but where is the fun?!). Inspired by this masterpiece, I wanted to create more than just printing out the number and this great paper give me enough knowledge and ispiration to do it!

Just to give you quick example, here are the sizes of the Hello World in C and Python (3.x):

As you can see the hello.c is 70 bytes, the hello.py is 21(!) bytes, but the compiled executable elf file hello_c is 8608 bytes!
How on earth it is even possible?!
That was exactly what I was thought when I first saw it. Now it is clear why people competing in such challange use Python, isn’t it?

But we are ain’t people who takes the easy way, we love a little struggle. Let me explain why it is so large. In C and in general in fully compiled languages the process of compilation looks something like this:

1. Preprocessor does the job.
2. The actual compilation.
3. Assemblation.
4. Linking.

Long story short - preprocess changes all of the constants and makros to what they’re refer, compilation translates code to assembler and assemblation changes the assembler to machine code and then the linker copies any code to which it find refrences in input code.
It is of course big, big simplification. The gcc makes much more (try -fdump-tree-all option ;) ). All of those steps make your code bigger and it is something we have to take into consideration!

So now we know that even Hello World is more than 8 times larger than we want, so the simple game would be much, much bigger! And this is true. Now we have a moment to thing what can we do to make it lighter.
The first thing would be to get rid of any library which is copied to our executable.

Woooow wait a minute! So how the hell will you be able to even print something if it uses std!

If you asked, now it is the proper time to say hello to a system calls!
The simplest explanation look like this - the system call is the way the program comunicates with the kernel. And basically it’s everything you need to know. There are hundreds of system calls in Linux and complete list of them with the specific registers which they use can be found here.
At this point you should understand that functions from std like printf are just wrappers to system calls. In fact, everything is just a wrapper to system calls, because it is the only way for the program to “speak” with the OS kernel. Don’t believe me? Let’s trace it!
As you may know (or not) there is a tool wich helps you to trace the system calls and it’s called strace! So let’s do it on out simple hello world!

// lots of text we can omit
brk(NULL)                               = 0x1bd9000
brk(0x1bfa000)                          = 0x1bfa000
write(1, "Hello World!", 12Hello World!)            = 12
exit_group(0)                           = ?
+++ exited with 0 +++

As you can see there is system call write which (as you may know) writes the content of buffer to specific descriptor (first parameter). In my case this is standard output so there is value of 1. Other parameters are pointer to our string and size of it.
So now we know we can print something without using std library, but we want to write a game, so there should be some interaction with the user. And for this we have got the read system call!
At this point I need to have something to which we can compare every new version of my application, so let’s write the actual game!
It won’t be difficult, in fact it will be very, very easy, and basically it can be play once. I’m writing the simple game where you have to guess the number the computer “thinks” of. The range is from 0 to 10 and to get everything small I do not generate random number, but just hardcoded it in the code.

Great game…

But hey! It’s still a game! Let’s write this simple game! Remember that all this code is available at my GitHub!

#include<stdio.h>

int main(){
  char number = 5, input, ans = 0;
  puts("Hi! Can you guess about which number I'm thinking of? I can give you a hint! It's from range [0, 9].");
  while(ans != 1){
    scanf("%hhi", &input);
    (input == number) ? (ans = 1) : puts("Unfortunately no. Try again!");
  }
  puts("That's right! Congratulations!");
  return 0;
}

So game written in pure C is 8720 bytes:

So it seems we have got lots of work to do! The first thing as I said, we are going to get rid of the stdio. Let’s use syscalls! To do that I needed to change some code as now there are 2 chars read from stdin - my guess and enter. Here’s the fixed version:

#include<unistd.h>

int main(){
  char number = 5, ans = 0;
  short input;
  write(1, "Hi! Can you guess about which number I'm thinking of? I can give you a hint! It's from range [0, 9].", 100);
  while(ans != 1){
    read(0, &input, 2);
    ((input & 0x0F) == number) ? (ans = 1) : write(1, "Unfortunately no. Try again!", 28);
  }
  write(1, "That's right! Congratulations!", 30);
  return 0;
}

Lets compile it and check it’s size!

What?! Again 8720 bytes? Ok, ok. It is possible because all of those write, read in unistd are also wrappers to original syscalls. There is one more, provided by Linux itself method - sys/syscall.h. It is a little bit different when we want to call write for example. It needs to use syscall(SYS_<<which syscall>>, and, then, parameters). Now it looks like this:

#include<sys/syscall.h>

int main(){
  char number = 5, ans = 0;
  short input;
  syscall(SYS_write, 1, "Hi! Can you guess about which number I'm thinking of? I can give you a hint! It's from range [0, 9].", 100);
  while(ans != 1){
    syscall(SYS_read,0, &input, 2);
    ((input & 0x0F) == number) ? (ans = 1) : syscall(SYS_write, 1, "Unfortunately no. Try again!", 28);
  }
  syscall(SYS_write, 1, "That's right! Congratulations!", 30);
  return 0;
}

What is the result?

So much work just for 8 bytes?! At this moment I was thinking it is impossible. And then it hits me like a rock. I even write this earlier! … The gcc makes much more …. We need to create the object file first and link it with ld. To create the .o file we can use gcc with a -c option. After this I received this beautiful number:

Nice, nice. From 8k to 3k, just by replacing the whole path in gcc with manual linkling of the object file. But it is still not enough :C
What else can I do? If I do not use any std and only strings and syscalls maybe I can do it in assembler? Sure I can!
First I have to get myself familiar with syscall calling on x86-64. I know that on x86 there was int 80h (and I know I can use it here as well). But on 64-bits there is dedicated solution! It can be found at 4-668 Vol. 2B of Intel Manuals and it is called (you will not believe) syscall! So let’s try to write in in assembler using the System Call Table I have paste you before. We need two syscalls - read and write. In Linux syscall table we can see that read and write have numbers 0 and 1 and use rax, rdi, rsi and rdx.
Easy! This is how write looks in x86-64 assembly:

; write
  mov rax, 1
  mov rdi, 1 
  lea rsi, [address_of_string]
  mov rdx, 101
  syscall

And read:

; read
  mov rax, 0
  mov rdi, 0 
  mov rsi, input
  mov rdx, 2
  syscall

That’s it! Now it’s time to write game in asm using above syscalls. For me it looks something like this:

segment .text
  global _start

_start:
  mov rax, 1
  mov rdi, 1 
  lea rsi, [welcome]
  mov rdx, 101
  syscall

game:
  mov rax, 0
  mov rdi, 0 
  mov rsi, input
  mov rdx, 2
  syscall
  
  mov rax, [input]
  cmp al, 0x35
  je end
  mov rax, 1
  mov rdi, 1 
  lea rsi, [failure]
  mov rdx, 28
  syscall
  jmp game
 
end:
  mov rax, 1
  mov rdi, 1 
  lea rsi, [success]
  mov rdx, 30
  syscall
  mov rax, 60
  xor rdi, rdi
  syscall

segment .bss
  input resb 2

segment .data
  success db "That's right! Congratulations!", 0xa
  failure db "Unfortunately no. Try again!", 0xa
  welcome db "Hi! Can you guess about which number I'm thinking of? I can give you a hint! It's from range [0, 9].", 0xa

As you can see we are using only syscalls to read and write to the buffers. The game in this shape has size:

Oh yes! We’re on the good path! 1400 bytes it is almost the size we need! Lets check it out what’s in this elf file, by using the readelf and we may see there is lots of unnecessary stuff (don’t believe me just try it!) especially in Section Headers.

So can we omit them?

Oh hell yes and we are going to do it in the most insane way! We will emit specific bytes in our assembler code and create the elf64 file!
But how does ELF look inside? For 32 bit you may check it here and for 64bit the Wikipedia is great source of knowlegde! And the way of doing it in asm is presented in [1]. So I did it:

BITS 64

org 0x400000

elf_hdr:
  db 0x7f, 'E', 'L', 'F', 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ;e_indent[EI_NIDENT]
  dw 2 ;e_type
  dw 0x3e ;e_machine
  dd 1 ;e_version
  dq _start ;e_entry
  dq phdr - $$ ;e_phoff;
  dq 0 ;e_shoff
  dd 0 ;e_flags
  dw 0x40 ;e_ehsize
  dw phdrsize ;e_phentsize
  dw 1 ;e_phnum
  dw 0 ;e_shentsize
  dw 0 ;e_shnum
  dw 0 ;e_shstrndx

phdr:
  dd 1 ;   p_type
  dd 7 ;p_flags
  dq 0 ;   p_offset
  dq $$ 
  dq $$ ;   p_paddr
  dq filesize ;   p_filesz
  dq filesize ;   p_memsz
  dq 0   ;   p_align

phdrsize equ $ - phdr

_start:
  mov rax, 1
  mov rdi, 1 
  lea rsi, [welcome]
  mov rdx, 101
  syscall

game:
  mov rax, 0
  mov rdi, 0 
  mov rsi, input
  mov rdx, 2
  syscall
  
  mov rax, [input]
  cmp al, 0x35
  je end
  mov rax, 1
  mov rdi, 1 
  lea rsi, [failure]
  mov rdx, 28
  syscall
  jmp game
 
end:
  mov rax, 1
  mov rdi, 1 
  lea rsi, [success]
  mov rdx, 30
  syscall
  mov rax, 60
  xor rdi, rdi
  syscall

  input resb 2
  success db "That's right! Congratulations!", 0xa
  failure db "Unfortunately no. Try again!", 0xa
  welcome db "Hi! Can you guess about which number I'm thinking of? I can give you a hint! It's from range [0, 9].", 0xa

  filesize equ $ - $$

And create flat binary file using nasm and guess what…

… now it is 409 bytes! I cutted 8311 bytes only using methods described above! And I have got more than 500 bytes more to do some upgrades in the game!

I hope you enjoyed reading this post as much as I enjoyed doing all those experiments! It was great fun and I recommend it to you all!

[1]. http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html
[2]. http://blog.rchapman.org/posts/Linux_System_Call_Table_for_x86_64/