Отправляет email-рассылки с помощью сервиса Sendsay

Низкоуровневое программирование для дZeнствующих

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "О карьере и профессиональном развитии IT-специалистов" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Декабрь 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Вячеслав Панкратов

Статистика

11.283 подписчиков
+11 за неделю
←   Все выпуски   →

Низкоуровневое программирование для дZeнствующих C()MP() #01 - Результаты


Информационный Канал Subscribe.Ru
C()MP() #01 - Результаты

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

C()MP()#01

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

Результаты

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

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

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

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

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

  • xBlackCat - 109 bytes

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

  • Shur - 123 bytes

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

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

 

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное