The PPK Tiny Programming Results

← Back to Stories (view on slashdot.org)

The PPK Tiny Programming Results

Posted by timothy on Wednesday December 4, 2002 @05:33AM from the nano-nano dept.

mikemacd writes "As mentioned before the folks over at properkernel.com ran a programming challenge. The results are in. Hopefuly they will post code too."

23 comments

Min score:

Reason:

Sort:

fp by CableModemSniper · 2002-12-04 05:40 · Score: 0, Offtopic

the robot loses again

--
Why not fork?
Hmmm by greenhide · 2002-12-04 05:40 · Score: 2

The text that had to be output was "The deep gray mouse runs after the holy yellow cheese."

Given that the winner used only 102 bytes, this means that his main code took up only 48 bytes. Wow.

--
Karma: Chevy Kavalierma.
1. Re:Hmmm by jo-do-cus · 2002-12-04 05:48 · Score: 3, Interesting
  
  correct me if i'm wrong, but it's quite easy to store this text, including the code to extract it to ASCII, in a lot less than 55 bytes...
2. Re:Hmmm by addaon · 2002-12-04 05:51 · Score: 2
  
  You're right, of course. In addition, I'm quite certain that the winners used at least some overlap between binary and text.
  
  --
  
  I've had this sig for three days.
3. Re:Hmmm by sporty · 2002-12-04 06:13 · Score: 3, Interesting
  
  Remember, it has to be done as an ELF binary. So you have to write a minimal header, then print a string :)
  
  -s
  
  --
  -
  ping -f 255.255.255.255 # if only
4. Re:Hmmm by Scarblac · 2002-12-04 07:09 · Score: 5, Interesting
  
  So you have to write a minimal header, then print a string.
  
  For some perspective: the normal ELF header is 52 bytes long, and the string including line feed is 55 bytes. The winner did it in 102, less than the sum of those. Wow.
  
  The next thought: why in heck didn't they print source (as if he didn't build that binary by hand), the binaries, or any info at all about how they did this!! It's stupid to look at the results only, so many questions, so few answers...
  
  --
  I believe posters are recognized by their sig. So I made one.
5. Re:Hmmm by sporty · 2002-12-04 07:23 · Score: 2
  
  Well, the source would be in assembler ;) Just need a good assembly editor and the binary. :)
  
  --
  -
  ping -f 255.255.255.255 # if only
6. Re:Hmmm by kernelistic · 2002-12-04 10:59 · Score: 1
  
  You might want to refresh the page. It appears as if the winning entries have been published. I'd love to see the rest of them released too.
  
  Wow!
Smallest web browser yet? by Matey-O · 2002-12-04 06:30 · Score: 2

Pipe http://server/message | stdout

They didn't SAY components couldn't live elsewhere, did they?

--
"Draco dormiens nunquam titillandus."
1. Re:Smallest web browser yet? by mikemacd · 2002-12-04 06:56 · Score: 1
  
  No they didn't but a 99byte solution I posted (which took the output string as a command line argument) didn't get mentioned so I guess it actually was a condition.
2. Re:Smallest web browser yet? by Scarblac · 2002-12-04 07:11 · Score: 2
  
  Pipe http://server/message | stdout
  
  That's not an ELF binary. Can you make a binary that does that in 102 bytes?
  
  --
  I believe posters are recognized by their sig. So I made one.
Any particular reason why... by sudog · 2002-12-04 07:53 · Score: 2, Insightful

This tutorial wasn't the end-all be-all of such a programming contest?

And why is the shortest entry an incredibly huge 102 bytes when the above link does something similar in .. 45 is it?

It would've been more of a contest if the program was supposed to do something more than output a string like that.
1. Re:Any particular reason why... by jericho4.0 · 2002-12-04 09:08 · Score: 2
  
  I was wondering about that also. My original predidction for this contest was about 50-60 bytes. The executable shown by that paper does something very simaler.
  I also think it would be a more interesting contest if the binary had to do something usefull. That would have meant more interesting optimization.
  
  --
  "A language that doesn't affect the way you think about programming, is not worth knowing" - Alan Perlis
2. Re:Any particular reason why... by ninewands · 2002-12-04 09:10 · Score: 2
  
  IIRC, the 45 byte programming example in the tutorial only output 2 bytes, while the winner had to output 55 bytes. Offhand, I'd say that would give an apparent THEORETICAL minimum size for the contest program of somewhere on the order of 97 bytes for an ELF binary with header. Given that the winner got within 5 bytes of the theoretical minimum size I think I'd still call it an impressive achievement.
  
  --
  utter rubbish
3. Re:Any particular reason why... by kernelistic · 2002-12-04 10:50 · Score: 1
  
  The paper only returns a value of 42 to the operating system.
  
  The contest actually required that a number of arguments to be set up, a syscall be called, AND control be returned to the operating system. Though this might seem trivial, it still adds overall bytes to the program. (Think of it this way, the string is 55ish bytes long then you have to add the ELF header and the code!)
4. Re:Any particular reason why... by sudog · 2002-12-09 08:15 · Score: 1
  
  No.. It was a hello world output, that was the whole point.
My 155 byte entry by mikemacd · 2002-12-04 10:03 · Score: 2, Informative

For anyone who cares, this was my entry which compiles to 155 bytes. Compile with (nasm -f bin -o tiny tiny.asm), and make executable (chmod o+x tiny), execute (./tiny) I use al,bl,cl,dl instead of eax,ebx,ecx,edx because they are only one byte wide instead of 4 bytes saving 3 whole bytes per use !!! ; Created by Michael MacDonald (mikemacd@sympatico.ca) ; ; Thanks to: http://www.muppetlabs.com/~breadbox/software/tiny/ teensy.html for tips on shrinking the code. BITS 32 org 0x00001000 ehdr: ; Elf32_Ehdr db 0x7F, "ELF", 1, 1, 1 ; e_ident times 9 db 0 dw 2 ; e_type dw 3 ; e_machine dd 1 ; e_version dd _start ; e_entry dd phdr - $$ ; e_phoff dd 0 ; e_shoff dd 0 ; e_flags dw ehdrsize ; e_ehsize dw phdrsize ; e_phentsize dw 1 ; e_phnum dw 0 ; e_shentsize dw 0 ; e_shnum dw 0 ; e_shstrndx ehdrsize equ $ - ehdr phdr: ; Elf32_Phdr dd 1 ; p_type dd 0 ; p_offset dd $$ ; p_vaddr dd $$ ; p_paddr dd filesize ; p_filesz dd filesize ; p_memsz dd 5 ; p_flags dd 0x1000 ; p_align phdrsize equ $ - phdr section data msg db "The deep gray mouse runs after the holy yellow cheese.", 0x0A len equ $-msg _start: mov dl, len ;message length mov cx, msg ;message to write mov bl, 1 ;file descriptor (stdout) mov al, 0x4 ;system call number (sys_write) int 0x80 ;system call mov al,1 ;system call number (sys_exit) int 0x80 ;system call filesize equ $ - $$
Elf binary? Bah! by Jonboy+X · 2002-12-04 10:10 · Score: 4, Funny

I wrote a Java class that does it in ...2.3 meg ...and uses half my RAM ...and takes 30 seconds to load ...oh never mind.

--

"In a 32-bit world, you're a 2-bit user. You've got your own newsgroup, alt.total.loser." -Weird Al
My 99 byte entry (with cheat) by mikemacd · 2002-12-04 10:17 · Score: 1

This entry cheats by taking the output string as an argument on the command line. When a program is run the stack is prepopulated with a few useful bits of data specifically (for those familiar with C) argc, the argv[] array, and the env array. So I pass in the string which is known to be a specific (55) length. Compile (nasm -f bin -o tiny2 tiny2.asm), make executable (chmod o+x tiny2), and execute (./tiny2 "The deep gray mouse runs after the holy yellow cheese.\ ") *Note the carriage return in the argument, and again I use al,bl,cl,dl instead of eax,ebx,ecx,edx because they are only one byte wide instead of 4 bytes saving 3 whole bytes per use. ; Created by Michael MacDonald (mikemacd@sympatico.ca) ; ; Thanks to: http://www.muppetlabs.com/~breadbox/software/tiny/ teensy.html for tips on shrinking the code. BITS 32 org 0x08048000 ehdr: ; Elf32_Ehdr db 0x7F, "ELF", 1, 1, 1 ; e_ident times 9 db 0 dw 2 ; e_type dw 3 ; e_machine dd 1 ; e_version dd _start ; e_entry dd phdr - $$ ; e_phoff dd 0 ; e_shoff dd 0 ; e_flags dw ehdrsize ; e_ehsize dw phdrsize ; e_phentsize dw 1 ; e_phnum dw 0 ; e_shentsize dw 0 ; e_shnum dw 0 ; e_shstrndx ehdrsize equ $ - ehdr phdr: ; Elf32_Phdr dd 1 ; p_type dd 0 ; p_offset dd $$ ; p_vaddr dd $$ ; p_paddr dd filesize ; p_filesz dd filesize ; p_memsz dd 5 ; p_flags dd 0x1000 ; p_align phdrsize equ $ - phdr _start: pop eax pop ecx pop ecx mov dl,55 ;message length mov bl,1 ;file descriptor (stdout) mov al,4 ;system call number (sys_write) int 128 ;system call mov al,1 ;system call number (sys_exit) int 128 ;system call filesize equ $ - $$
Code and bins for the entries... by kernelistic · 2002-12-04 11:06 · Score: 2, Informative

I guess this is where they stashed the code for the entries.
Not a winner? by fava · 2002-12-04 12:34 · Score: 4, Informative

It looks like the winning entry actually does not output the required string. If you look at the winning entries code it is actually outputting the string:
'The deep ' 0x0 0x1 0x0 ' gray mouse runs after the holy yellow cheese.' 0xA
Where the 0x0 0x1 0x0 are required fields in the ELF header that splits the message into two halves. The output might appear to be correct when displayed on a terminal but if you redirect it to a file you will see the extra bytes.

Modifying the code to not output the extra bytes would add 9 bytes to the program and it would larger than the next smallest binary, assuming that the 104 byte entry didn't use the same trick.
Yay! I got on the high scores! by andfarm · 2002-12-04 18:09 · Score: 2, Informative

I'm in the list, and pretty close to the optimum value, too! (169 bytes for me. The lowest was 101, and they sort of cheated.)
The source (yes, nasm input == source) to my entry is available here.

--
TANSTAAFI: There Ain't No Such Thing As A Free iPod.
Cody P. article by kernelistic · 2002-12-13 05:23 · Score: 1

The winner wrote an article detailing the technique that he used to create the winning entry. It can be found here.