Интересная задачка на оптимизацию

Тема в разделе "WASM.A&O", создана пользователем Ramakrishna, 5 фев 2005.

  1. Ramakrishna

    Ramakrishna New Member

    Публикаций:
    0
    Регистрация:
    5 фев 2005
    Сообщения:
    6
    Адрес:
    Russia
    В общем как то очень давно видел на одном форуме была такая тема, обсуждали задачку



    а задачка такая:

    нужно написать программу, которая выводит "Hello world!" (без кавычек и со знаком !) и при этом занимает 16 байт! Командную строку использовать нельзя!



    Насколько помню на том форуме так и не додумался никто..

    Я тоже сам пытался, ничего умного так и не придумал..,

    а тут недавно вспомнил про нее и решил запостить сюда..



    кстати, тот человек, что придумал это клялся что это возможно сделать! вот уж незнаю..
     
  2. IceStudent

    IceStudent Active Member

    Публикаций:
    0
    Регистрация:
    2 окт 2003
    Сообщения:
    4.300
    Адрес:
    Ukraine
    Хм.. Из 16 байт 12 занимает строка. 4 байта на её вывод?

    Под Win32 это выглядит невозможным. DOS (tiny)?
     
  3. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
  4. IceStudent

    IceStudent Active Member

    Публикаций:
    0
    Регистрация:
    2 окт 2003
    Сообщения:
    4.300
    Адрес:
    Ukraine
    Гм.. Поиск по форуму и правда рулит :)
     
  5. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Вот, не 16 байт конечно, но в w2k работает :)
    Код (Text):
    1. ;=============================================
    2. format      pe      console
    3. include     '%fasminc%\win32a.inc'
    4. ;=============================================
    5.             push    eax
    6.             push    esp
    7.             push    12
    8.             call    @F
    9.             db      'Hello world!'
    10. @@:         push    7
    11.             call    [WriteFile]
    12.             ret
    13. ;=============================================
    14. data        import
    15. library     kernel32,'kernel32.dll'
    16. include     '%fasminc%\apia\kernel32.inc'
    17. end         data
    18. ;=============================================
     
  6. Ramakrishna

    Ramakrishna New Member

    Публикаций:
    0
    Регистрация:
    5 фев 2005
    Сообщения:
    6
    Адрес:
    Russia
    да, DOS и Tiny, все по минимуму!



    тут так просто не решишь, думаю нужно кодировать каждый символ несколькими битами или как то так..



    честно говоря, если без шуток, реально сложная задачка..
     
  7. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Ну хорошо, для простоты предположим, что каждый символ закодирован 4мя битами (для простоты декодера), таким образом получим 6 байт на текст. вывод символа в ДОС (как я понял) стОит 6 байт. Итого 12. Остаётся 4 байта на декодер, причём 2 из них уйдёт на команду перехода.
     
  8. shoo

    shoo New Member

    Публикаций:
    0
    Регистрация:
    17 июл 2003
    Сообщения:
    1.537
    Адрес:
    Ukraine
    наверно, только на форте:
    Код (Text):
    1. ." Hello world!"


    ;)
     
  9. shoo

    shoo New Member

    Публикаций:
    0
    Регистрация:
    17 июл 2003
    Сообщения:
    1.537
    Адрес:
    Ukraine
    не, наверное, это невозможно в дос/вин32, так как из двух оставшихся байт на "декодер" потребуется как минимум один байт на культурное завершение программы и некий терминатор или счетчик символов, не менее 4 бит, итого - на декодер - 1 нибл ;) в форте тоже не получится - минимум 15 байт шитого кода, но нужно еще 2 байта на команду завершения слова, не считая 3 байт на вызов интерпретатора...



    я встречал в программах со собственными процедурами вывода код вроде следующего:
    Код (Text):
    1.    call print
    2.    db "Hello world!",0
    3.    ... ; продолжение, можно ret
    4.  
    5. print:
    6.    pop si
    7. @@:
    8.    lodsb
    9.    test eax,eax
    10.    jz @F
    11.    call emit_char
    12.    jmp @B
    13. @@:
    14.    jmp [si]


    если программой считать верхний код, тогда как раз укладываемся :)



    не, все равно 17 байт...
     
  10. ash

    ash New Member

    Публикаций:
    0
    Регистрация:
    9 ноя 2004
    Сообщения:
    52
    Адрес:
    Latvia
  11. Ramakrishna

    Ramakrishna New Member

    Публикаций:
    0
    Регистрация:
    5 фев 2005
    Сообщения:
    6
    Адрес:
    Russia
    культурное завершение программы не обязательно,

    главное условие - вывод этой строки
     
  12. IceStudent

    IceStudent Active Member

    Публикаций:
    0
    Регистрация:
    2 окт 2003
    Сообщения:
    4.300
    Адрес:
    Ukraine
    На форуме FASM'a аналогичная задача. Но и там она не решена, хотя есть интересные результаты.
     
  13. green

    green New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    1.217
    Адрес:
    Ukraine
    Ramakrishna

    а можно ещё ослабить условие:
    Код (Text):
    1. вывод программы включает строку "Hello world!"
    ?

    :derisive:
     
  14. green

    green New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    1.217
    Адрес:
    Ukraine
    если серьёзно, то IMHO следует попытаться использовать строку (или её части) как исполняемый код, возможно самомодифицирующийся.
     
  15. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    исполняемый код врядли - там опкоды не те
     
  16. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    а вот что нам Гугл сказал :



    1) 19 байт решение :



    start:

    hello db 'HellO WORLD!$'



    mov dx,si

    mov ah,9

    int 21h



    но здесь используется "SI при старте =100h"



    2) некто заявил, что при старте BP=09XX, т.о. получая



    mov dx,si

    xchg ax,bp

    int 21h



    и это только 18 при уйме доп.ограничений



    P.S. Строка изменена чтобы прийти с правильным выравниванием к первой команде программы без прыжка на нее.
     
  17. alpet

    alpet Александр

    Публикаций:
    0
    Регистрация:
    21 сен 2004
    Сообщения:
    1.221
    Адрес:
    Russia
    Может использовать в качестве части слова - имя исполняемого .com файла. Например WORLD.COM, правда точку придется заменять!$, так что экономии мало. Само имя файла вроде в PSP можно отыскать.
     
  18. Ramakrishna

    Ramakrishna New Member

    Публикаций:
    0
    Регистрация:
    5 фев 2005
    Сообщения:
    6
    Адрес:
    Russia
    решение с форума fasm. Оригинально =)



    сама программа hello.com: 4 байта

    mov ah,0Ah

    int 21h



    текстовый файл text.txt, содержащий "Hello world!": 12 байт



    запускаем так: hello.com < text.txt



    hello.com + text.txt = 16 байт =)
     
  19. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Оригинально, конечно, но решением не является:

     
  20. alpet

    alpet Александр

    Публикаций:
    0
    Регистрация:
    21 сен 2004
    Сообщения:
    1.221
    Адрес:
    Russia
    Мой вариант выводит испорченную строку H llo world!

    Но зато 19 байт и завершает программу.
    Код (Text):
    1.  
    2. B409                      mov    ah,09h
    3. BA0601                    mov    dx,0106h
    4. E948FF                    jmp    0FF50h
    5. 6C                        insb   es:[di],dx
    6. 6C                        insb   es:[di],dx
    7. 6F                        outsw  dx,ds:[si]
    8. 20776F                    and    byte ptr [bx+6F],dh
    9. 726C                      jb     0000007C
    10. 642124                    and    word ptr fs:[si],sp
    11.  


    [​IMG] _1508606853__hw.com