№29.6. Экстрим программированние для дZенствующих. Результаты COMPO

№29.6. Экстрим программированние для дZенствующих. Результаты COMPO

############################################

C()MP()#01

###################################################

Результаты

# В п()исках степени 01b

Кто знает, рок судьбы или нет, но только видимо Edmond, выбирая название COMPO, зло подшутил над самим собой. Сперва очень просто обнаружилась ошибка знакового переполнения, принадлежащая С-программе. А методом последовательного приближения (в народе: «тыка») было, установлено исходное число. Все праздновали победу, когда вдруг, «неожиданно» оказалось, что хитрый алгоритм не хочет уложиться в пределы 32-х бит. Таким образом, степень 01b, оказалась по-серьёзному затерянной в неизвестности высших разрядов. Её долго искали при помощи фонариков и других инструментов подобного характера. Причём искали все, как авторы COMPO, так и участники.

В конце концов, авторы, скрипя сердцем, и хлопая дверью, договорились считать предположение об отсутствии переполнения. Но даже, несмотря на все «блины» вышедшие комом, COMPO состоялось, И теперь мы станем свидетелями Великой победы человека над глупостью машины, и даже над Глупостью человека, например, такого как Edmond ? :)).

#П()БЕДИТЕЛИ

По главному критерию COMPO – перед нами один абсолютный победитель, ему удалось обогнать соперников не на один байт, или даже десяток. Это рыцарь Дзена – xBlackCat, который смог отрубить голову дракону, укоротив его до 109 байт.

Второе почётное место досталось почтенному Shur, заметим, который замахнулся, мечём на 145 байт. (Что лучше тестового примера Edmondа, не удержавшегося вспомнить чёрный экран DOS, пусть и под заклятиями NTVDM).

WASM.RU поёт отважным песню славы, и приглашает всех желающих испить чашу вина, и насладится кодом победителей.

#C()DE LISTING

Исходник Shur ( с его комментариями)

;       by Shur


; 123 bytes
; корректно работает для n из диапазона 0 < n < 159'487

  .model tiny
     .code
.386 org 100h start:
call _read_number ;Читаем первое число. mov edi,ecx ;его в edi, т.к. в ecx будем читать второе call _read_number ;Читаем второе число. ;---------------------------------------------------------------- ;в edi - нижняя граница, в ecx - верхняя граница ;начнем с верхней ;в ax будет текущий максимум итераций ;он в ax, потому что его потом придется выводить, сконвертировав в ;десятичнаю форму, а делить можно только ax ;посему, чтобы потом его не перемещать, сразу поместим его в ax xor ax,ax _go: mov edx,ecx ;Берем очередное число. ;прямо с ecx работать нельзя, надо запомнить, ;какое последнее число обрабатывали xor si,si ;это счетчик итераций ;--------------------------------------------------------------- ;в случае четного n => n=n/2; it++; ( то бишь n=n>>1 ) ;в случае нечетного => n=(3*n+1)/2; n+=2; ( то бишь n=(n>>1)+n+1 ) ;--------------------------------------------------------------- _inc: inc si ;it++ в любом случае mov ebx,edx ;сохраняем n на случай нечетного shr edx,1 ;тут одной командой происходит как тестирование ;n на 1, так и на четность !!! ;правда, я не сам до этого додумался, а подсмотрел в TESTASM.EXE :))) ;Edmond: ;Ну вот, прокололся ещё раз :))) ;Хотя а что ж это за асмовец, который не подсмотрит код в exe. ;Мы так не любим смотреть исходники друг друга, зато обожаем копатся в битах. jz short _end ;это если edx был 1 jnc _inc ;это случай четного n ;а это в случае нечетного. здесь CF=1, ebx=n, edx=n>>1 adc edx,ebx inc si jmp _inc ;достигли n=1, si содержит количество итераций. _end: cmp si,ax ;обновляем текущий максимум jb short _no_new_maximum xchg ax,si ;реально нужен mov, но xchg короче _no_new_maximum: dec ecx ;готовимся обработать следующее число cmp ecx,edi jnb _go ;------------------------------------------------------------ ;теперь в ax - максимум итераций для текущего диапазона ;конвертируем в десятичный вид и выводим. ;в ecx - количество циферок. xor cx,cx mov bl,0ah ;перед делением проверки нет, т.к. ax гарантировано отлично от 0 ;т.е. хоть одна цифра обязательно будет выведена. ;вообще это тоже не моё - это из статьм Serrgio - Программирование под ДОС ;но ничего короче я не придумал - только заменил команды на более короткие ;Edmond: ;Человек не придумывает новое, он просто открывает существующее. ; (с)... _nz: inc cx cwd div bx push dx test ax,ax jnz _nz _out_cipher: pop dx add dl,30h call _out_byte loop _out_cipher ;а это вывод 0ah mov dl,0ah call _out_byte jmp start ;ну и все - пара обработана ;----------------------------------------------------------------- ;Процедура чтения числа из входного потока ;1.Пытается прочитать число ;2.Сразу выводит его ;3.Выводит после него пробел ;4.Завершает программу, когда при чтении первого числа достигнут конец потока. _read_number: ;число будем собирать в ecx xor ecx,ecx _read_digit: ;читаем следующий символ ;я пользовался функцией 06h, просто потому, что ей можно как ввести байт, ;так и вывести. ;а может просто, потому что она первой на глаза попалась. mov dl,0ffh call _in_byte ;переход выполняется 2 раза. Первый раз на второй вызов _read_number, когда ;в ecx назодится второе число последней строки. ;но программу пока завершить нельзя, т.к. эта пара значений еще не обработана ;второй раз уже после обработки последней пары jz short _put_space ;0ah мы просто игнорируем, а по пробелу или 0dh - заканчиваем ввод cmp al,0ah jz _read_digit ;здесь в al либо цифра, либо пробел, либо 0dh ;цифра - это 0011xxxxb, ;пробел - 00100000b, ; 0dh - 00001101b, ;10h - 00010000b. ;этот test позволяет отделить цифру от остальных случаев одним сравнением test al,10h ;Если не цифра - то на выход, печатать пробел ;В ecx в этом случае точно не ноль ;правда, ничего страшного не будет, если написать jz short _put_space jz short _put_space_1 ;Прочитали цифру. сразу её выводим. mov dl,al int 21h ;теперь добавляем её к читаемому числу movzx eax,dl sub al,30h imul ecx,0ah add ecx,eax ;-------------------------------------------------------------------------- ;P.S. - тут я несколько стормозил. на кой было гнать цифру в eax, ;когда значитеьно проще и короче на 2 байта: ; and edx,0fh ; imul ecx,0ah ; add ecx,edx ;Вообще-тот до вызова int 21h в al тот-же символ, что и в dl, ;но после почему-то уже нет. ;-------------------------------------------------------------------------- ;И идем читать следующий символ jmp _read_digit _put_space: ;Входной поток кончился. Возможно, придется выйти. mov ah,4ch ;Если в ecx ноль - тогда остается только выйти. ;т.е. либо входной файл совсем пустой, либо последнее число уже было считано ;предыдущим вызовом jecxz _int_21h ;вот чтобы воспользоваться jecxz, я и собирал число именно в ecx ;если-бы последняя строка тоже заканчивалась 0dh,0ah - тогда по отсутствию ;символа во входном потоке можно было-бы сразу закончить программу. _put_space_1: ;Если-же в ecx не ноль, то значит мы прочитали число, и уже вывели его. ;Теперь выводим за ним пробел. mov dl,20h _in_byte: _out_byte: ;Конец процедуры будет использован как самостоятельная процедура. ;Для ввода символа, и для вывода mov ah,06h _int_21h: int 21h ret end start ;-------------------------------------------------------------------------- ;Ну и еще одно - 0ah после максимума можно было вывести проще - затолкнув ;его в стек перед преобразованием, а затем выведя вместе с цифрами одним циклом. ;Сэкономили бы еще 2 байта: ; ; push 0ah-30h ;потом 30h прибавится ; mov cx,1 ;а это вместо xor cx,cx ; mov bl,0ah ; ... далее преобразование и вывод ; ;В-общем, можно было уложиться в 119 байт. как меньше - я пока не знаю ;-------------------------------------------------------------------------- ;кстати, версия, корректно работающая с n из 0 < n < 1'000'000, ;у меня "уложилась" в 129 байт ;--------------------------------------------------------------------------
Исходник победителя XBlackCat

   ;By xBlackCat

  p386
ideal
model tiny
CODESEG
        org     100h
Start:
        mov     bl,10
StartCikl:
        xor     edi,edi
        mov     ah,06h
CiklRN:
        mov     dx,0FFh
        int     21h
        mov     dl,al
        test    al,10h
        jz      short ExitRN

        imul    edi,edi,5
        lea     edi,[edx+2*edi-30h]
        int     21h

        jmp     CiklRN

ExitRN:
        cmp     al,20h
        jne     short NumbersReaded

        int     21h
        mov     esi,edi
        jmp     StartCikl

NumbersReaded:
        xor     bp,bp

CiklMain:
        xor     ax,ax
        mov     ecx,esi
        inc     esi

CiklFunc:
        inc     ax
        shr     ecx,1
        jnc     CiklFunc
        jz      short EndCiklFunc

        inc     ax
        lea     ecx,[ecx+2*ecx+2]
        jmp     CiklFunc

EndCiklFunc:
        cmp     bp,ax
        jae     short NextStepCiklFunc

        xchg    ax,bp

NextStepCiklFunc:
        cmp     edi,esi
        ja      CiklMain

        xchg    ax,bp

        mov     cl,3
        db      6Ah     ; push 0FFh
        db      0FFh    ; -=\*/=-
        push    bx

Cikl:
        inc     cx
        cwd
        div     bx
        add     dl,30h
        push    dx
        or      ax,ax
        jnz     Cikl

        push    20h
        mov     ah,06h
CiklOutNumber:
        pop     dx
        int     21h
        loop    CiklOutNumber
        jnz     StartCikl

        ret
        END     Start

#Ан()нс

В преддверии нового года WASM.RU желает приятно встретить новый, и проводить старый год. И повторить процедуру минимум два раза для закрепления эффекта.

Пусть в новый год войдут ваши лучшие идеи, оставляя позади (но, не забывая) ошибки прежнего года.

Мне хочется верить, что там, за границей двенадцати ударов часов и двенадцати ударов хрустальных фужеров кроется несколько приятных сюрпризов, новых ошибок (ибо они - путь к совершенству), и новых творений, что украсят сказочную жизнь представителя низкоуровневого мира asm.

Как всегда мы ждём предложения и необычные идеи COMPO сюда: compo@wasm.ru

###################################################

© Edmond :: HI-TECH group

© wasm.ru 2002

###########################################################