Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

The PPK Tiny Programming Results 23

Posted by timothy 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."
This discussion has been archived. No new comments can be posted.

The PPK Tiny Programming Results More

The PPK Tiny Programming Results

Comments Filter:
  • 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.

    • Re:Hmmm (Score:3, Interesting)

      by jo-do-cus ( 597235 )
      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...
      • You're right, of course. In addition, I'm quite certain that the winners used at least some overlap between binary and text.

      • Re:Hmmm (Score:3, Interesting)

        by sporty ( 27564 )
        Remember, it has to be done as an ELF binary. So you have to write a minimal header, then print a string :)

        -s

        • Re:Hmmm (Score:5, Interesting)

          by Scarblac ( 122480 ) <slashdot@gerlich.nl> on Wednesday December 04, 2002 @03:09PM (#4812101) Homepage

          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...

          • Well, the source would be in assembler ;) Just need a good assembly editor and the binary. :)
          • 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!
  • Pipe http://server/message | stdout

    They didn't SAY components couldn't live elsewhere, did they?
  • This tutorial [muppetlabs.com] 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.
    • 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.

      • 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!)
    • 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.

  • My 155 byte entry (Score:2, Informative)

    by mikemacd ( 84328 )
    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 $ - $$
    • 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 $ - $$

  • Elf binary? Bah! (Score:4, Funny)

    by Jonboy X ( 319895 ) <jonathan.oexnerNO@SPAMalum.wpi.edu> on Wednesday December 04, 2002 @06:10PM (#4814063) Journal
    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.
  • I guess this is where [properkernel.com] they stashed the code for the entries.

  • Not a winner? (Score:4, Informative)

    by fava ( 513118 ) on Wednesday December 04, 2002 @08:34PM (#4815157)
    It looks like the winning entry [properkernel.com] 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.
  • 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 [menloschool.org].

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

Slashdot Top Deals

PURGE COMPLETE.

Close