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

Бредисловие

Возрадуйтесь, братья по безумию: вышел очередной выпуск рассылки. В связи с обилием материала постинг будет совершаться частями. Предложения, замечания... матюгальники, угрозы, гнилые помидоры, тухлые яйца, напильники, консервные банки, камни, грязь, пыль, опилки и пр. бросать сюда: Книга Жалоб и Предложений. Также напоминаем, что данная рассылка произведена в соответствии с ч.4 ст.29 Конституции РФ - ваш адрес взят из публичных источников. Отписаться от этого спама можно здесь, самый крутой в рунете программерский сайт находится здесь, а кучу ссылок на бесплатную порнуху можно найти здесь.

В предыдущий номер вкрались многочисленные (и немногочисленные, а также целочисленные, с плавающей запятой и другие) ошибки, очевидно вследствии распития и смешивания дZенских напитков членами редколлегии. Временно исполнявший обязанности главного редактора расстрелян, авторы повешены... в общем, соответствующие сигналу экзекуции были проведены. К счастью (а может и к несчастью) некоторым удалось выжить - только за счет полной остановки жизнедеятельности (благо, как только пошла фибриляция, Serrgio успел достать из банки малосольный катетер и провести ускоренную помощь в лучших традициях ER).

#В номере

• COMPO#01 [Myst, Edmond] экстрим программирование для Дzenствующих.
• Генератор паролей [Serrgio]. Посредством описанной в статье методы можно провести экспериментальную проверку некоторых математических, астрофизических и философских теорий и в конце концов получить ответ на самый глобальный вопрос современности - почему двери в психушку открываются исключительно внутрь.
• Сам себе компилятор [FatMoon]. В детстве автор пробовал на вкус акварельные "медовые" краски, пытался залить чернила в стержень авторучки, приносил домой гусениц, кормил их листьями и вылуплял бабочек... А разве писать на ассемблере под WINDOWS не извращение?
• Записки дZeнствующего [Edmond]. Настоящая статья призвана расставить некоторые точки над О... Ну и что с того, шта над О точек отродясь не было? Наши точки, где хотим там и ставим! Автор не пытается рассказать в корне что-то новое, но лишь отполировать старое. Кстати, знаете, почему у Евы пупка не было? Стерся :(
• FPU посвящается, часть 2 [Edmond]. Мы снова перед могуществом FPU. Ещё немного, и мы заглянем в его суть. Ассистент, скальпель. Ассистент, топор! Ассистент, бензопилу!! Ах да... ассистент, наркоз...
• Пишем фильтр для Photoshop [Masquer]. С этим вы намучаетесь по полной программе, но не расстраивайтесь - фотошопу придется еще хуже :).
• Аппроксимация данных [Chingachguk]. "Полагаем, никто не подвергает сомнению следующие основополагающие тезисы программерского дзена: 1). После первой не закусывают. 2). Между первой и второй промежуток небольшой 3). Третий - за прекрасных дам... А вот что может случится после двенадцатой, если учесть тот прискорбный факт, что Ленка, начав танцевать на столе стриптиз сразу же после седьмой, до сих пор не может остановиться? Именно таким вопросом задался протрезвевший автор, размял занемевший пальцы, и...

#Новости проекта WASM

За прошедший месяц с хвостиком на сайте произошли приятные (но вполне ожиданные ;) добавления:

• раздел "Инструменты" пополнился известным компилятором FASM, который теперь можно скачать здесь
• в "Инструментах-модификаторах" появился подарок от CyberManiak'a. Называется он Sign of Mizery, и я понятия не имею, что это такое. ;)) Желающим разобраться - сюда
• наконец-то выложены все статьи из цикла 'Путеводитель по написанию вирусов под Win32' Billy Belcebu в переводе Aquila. Между прочим, все это удовольствие собрано в один chm и ждет читателей.
• начат цикл статей "Программирование игр на ассемблере" by Chris Hobbs. Несмотря на своеобразное введение - "Сегодня, дети, я начну рассказ о том, как сделать ядерную бомбу своими руками. Начнем с теории. Итак, строение ядра… Ну, там нейтроны, протоны, а вокруг электроны… Ну, вы должны это знать. Закончим с теорией":), весьма интересные статьи. Рекомендую сразу перейти на вторую часть и начать делать ядерную… тьфу! :) игру на ассемблере под Win32.
• Начат новый COMPO#01, который опубликован в этом номере.

Whould you like to know more?

#Codesise compo на Qоруме WASM.RU

Итак, у нас уже есть свои компо :)… Кодесайз - это значит оптимизация, оптимизация и еще раз она же. По размеру. Когда очень маленькая программа делает весьма большие дела (например, форматирует ваш винт J), это не может не вызвать удивления… восхищения… а если это ваша собственная программа - то и гордости. Вообще, программирование - это разновидность магии. Нет, черт возьми, это и есть магия! "Интеллектуальное воздействие на окружающую среду" - вполне подходит под определение и того, и другого. Главное - не переступить черту: когда ваша программа занимает считанные байты - вы хороший программист. Когда вы говорите себе "Я прекрасно себя чувствую, я свеж и полон сил" - это аутотренинг. А когда вы начинаете делать себе волшебную палочку из орешника, покрываете ее каббалистическими письменами, начинаете ей махать и говорить странные слова - вот это уже шизофрения ;)) Итак, (взмах палочки - шарик от мыши на конце электрода) мы ведем трансляцию (шепот странных слов "Kernel bugis - bitus nulis") С ЧЕМПИОНАТА ПО КВИДДИШУ (мда, явно брат этой палочки оставил отметку на моей голове…)

Задание на COMPO#0 было довольно простым. Требуется написать программу, выдающую на стандартное устройство вывода (экран) свой исходник, пригодный для компиляции TASM'om. После этого должна получиться та же программа. Компилятор может выдавать предупреждения - главное, чтобы не ошибки. Срок был определен на 27 октября, все участники должны были выслать скомпилированный прог и исходник судье (Myst'у).
Написание самопечатающейся проги... Первое, что приходит в голову: в конце через db "..." добавлен весь исходник, а программа печатает его дважды: сначала как программу, а потом как данные. Приблизительный размер такого кода (+текст) около 1К. Очевидны недостатки: данный прием весьма объемен. То же относится к самодельному дизассемблеру, который выдаст себя же дизассемблированного - тут размер кода будет около того же 1К + громадный набор инструкций х86 в текстовом виде. Ясно, что такой сложный проект не годится в качестве задания к COMPO.
Прокрутив в голове все эти соображения, ясно, что надо выдавать свой "листинг" в виде
db <code>,<code>,<code>...
Однако кроме перевода опкодов в пригодные для печати значения необходимо также добавить несколько строк данных, которые также будут занимать место. Возможны следующие варианты:

Наличие этих директив обязательно для успешной компиляции и линковки. Учитывая, что имена программ и сегментов могут состоять из одной буквы, а в случае С открытый сегмент можно не закрывать - куда он денется? - и убрать слово "ends", ... все три варианта по длине примерно одинаковы :) (хотя С немного короче)
Сама программа должна либо последовательно напечатать заголовок, потом в цикле переведенные в ASCII опкоды через запятую, потом слово "end", либо... Либо подготовить где-то в памяти одну длинную строку, дописывая опкоды после заголовка и добавив "end" в конце, после чего напечатать все это одним хлопом. Очевидно, возможны оба варианта, хотя второй представляется более коротким.

Перевод в ASCII вид возможен в разных системах исчисления. Опять же, учитывая возможности компиляторов,

1. десятичный формат. Очень легко переводится в пригодные для печати символы добавлением 30h. Сложность в выделении десятичных цифр.
2. двоичный формат. Каждый код нашей программы придется прокрутить 8 раз, выделяя по биту. И не забыть добавить в конце числа "b".
3. шестнадцатиричный. Наиболее на первый взгляд оптимальный, но при ближайшем рассмотрении - требует ведущего нуля (перед буквами. Не будет ошибкой 000h, но BAh не проходит), символа "h" в конце и главное - перевод в ASCII не совсем линеен - от 0 до 9 надо прибавить 30h, а от A до F - 37h.

Ну и очевидно, что вместо "0D,0A" для перехода на следующую строку можно обойтись только 0Ah, для компилятора это достаточно. Пару байт в данных это съэкономит.

Учитывая все эти соображения, читатель вполне может сам попробовать свои силы. Победителями стали

1. Black Mirror: перевод в двоичные числа, формирование одной строки (70 байт);
2. Chingachguk: перевод в десятичные, формирование одной строки (70 байт);
3. 90210: перевод в десятичные, вывод "db <opcode>" в цикле (72 байта).

Ну, собственно, congratulations! Всем победителям - пиво нетмейлом! ;) Думаю, что исходники будут выложены на сайте и желающие смогут с ними познакомиться.
И - очередное COMPO#1...

####################### W A S M . R U #######################

C()MP()#1

В поисках степени 10b

Для участия в конкурсе вышлите письмо с архивом *.zip по адресу compo@wasm.ru

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

.model tiny
.code
.386
org 100h

start:

#С()DEсловие

include lyrics.inc

Что наша жизнь? Нет, это не ЧТО, ГДЕ, КОГДА!!! Это простой вопрос, на который не стоит давать ответ. Что она? Это успеть родиться, добежать, ухватить, укусить, устроиться, родить, вырастить, прокормить, умереть. Но почему-то никому не удается -- выполнить все пункты длинного списка судьбы. Поэтому приходится выбирать лучшее. То есть: добежать, ухватить, укусить, жениться.... не как-нибудь, а лучше чем все. И сердцу приятней, и душа радуется..., и другим завидно.

Но есть такие люди -- асмовцы..., вернее это не люди, и даже не программисты -- это инопланетяне, которых всё ещё ищут глупый Маудер и Скалли. А x86 -- это название НЛО...

Для этих людей существует ещё один пункт -- CODE... Пусть не всегда им удается лучше других добежать, ухватить, залезть, устроиться... Пусть их жизнь не оптимизирована в этом мире, но есть code, который быстрее, меньше, прекрасней, нежели у других.

Добро пожаловать в WASM.COMPO...

#Alg()ритм

Рассмотрим несложный алгоритм.

1. Дано n -- целое 0<n<1'000'000
2. Вывод n
3. Цикл пока n>1 (i счётчик цикла и первоначально 1)
   1. Если n чётное: n = n/2; вывод n
   2. Иначе n = 3*n+1; вывод n
   3. i++;
4. Вывод i

Например для n = 22, мы будем иметь такую последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Обратите внимание что первое значение n = 22 так же входит в список, и учитываеться i = 1.

Считатется, что цикл описанный выше, завершится для любого n. В действительности алгоритм будет завершён, как только комплекс функций n=n/2 и 3*n+1 приведёт к n = 2^x. Несмотря на простоту алгоритма нет аналитического доказательства, что для любого n_{начальное} данный алгоритм при неогранниченном числе итераций приведёт к n = 2^x, то есть к числу степени двойки. Однако этот факт проверен для целых чисел 0<n<1'000'000 ( и на самом деле для более больших чисел).

Таким образом для каждого числа n существует i -- длинна цикла -- количество цифр, которые будут напечатанны, или число итераций плюс 1 до достижения n значения еденицы.

#Pr()blem

Вы должны определить максимальную длинну цикла для всех целых чисел между i , j - которые являются входными данными.

#С()nditi()n

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

Основные условия тестирования

Вы можете скачать необходимый набор файлов для COMPO здесь

Эти условия являются главными, на них строятся другие требования. Но от учасника COMPO требуется выполнить только Основные условия тестирования:

Программа тестируеться при помощи bat файла:

@echo off

%1 <test.in >test.tmp

fc test.tmp test.out

del *.tmp

pause

где файл test.in содержит входные значения, файл test.out является образцовым с правильными значениями, а test.tmp содержит результаты работы вашей программы.

• Для каждой пары входных чисел i и j следует вывести j и i, и максимальное число циклов.
• Три числа обязаны быть отделены одним пробелом и помещены в одну строку вывода.
• Ввод осуществляется через STDIN
• Вывод осуществляется через STDOUT
• Программа обязана корректно завершаться по окончании ввода
• Гарантируется что входные значения i и j -- целые числа в диапазоне 0<n<1'000'000
• Гарантируется что i < j или i = j
• Формат ввода гарантируется таким как показано ниже
• Формат вывода обязан соответствовать образцу (смотреть далее)

Программа считаеться правильно работающей, если при запуске из командной строки test.bat program.com файлы test.out и test.tmp признаны идентичными. При этом программа должна завершиться самостоятельно.

Данное условие является единственным критерием оценки программы!!!

Формат входным значений гарантирован:

Формат ввода

(последняя строка без 0dh 0ah !!!)

пример правильного ввода:

123 124
1 2
9999 9999

пример некорретного ввода:

0123 123
123          123
123 * 123

Формат вывода

пример правильного вывода

123 123 40

  1 999999 525

пример неправильного вывода

123       123       20

  000123 001243 012

Вы можете скачать необходимый набор файлов для COMPO здесь

#Условия компиляции и критерии оценки

1. Программа должна быть программой *.com
2. Лучшей считается та программа, которая имеет меньший размер
3. Программа должна компилироваться tasm.exe при помощи командной строки
   tasm.exe <имя>.asm
   tlink.exe /t <имя>.obj
4. При наличии любых проблемм с компиляцией программа к конкурсу не допускается

Для участия в конкурсе вышлите письмо с архивом *.zip по адресу compo@wasm.ru

Содержание архива *.zip:

1. Исходник asm
2. Программа com

#Сроки проведения

20-Nov-02 --Start of compo.
10 -Dec-02 @ 11:59 (Msk)--Deadline for entry submission.
14-Dec-02 --Start of public judgement.
18-Dec-02 @ 11:59 (Msk)--End of public judgement.
20-Dec-02 --Final results.

ret

end start

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

HI-TECH (R) COMPO Version 1.0.0000
Edit by Edmond [HI-TECH] in the year 2002
Copyright (C) Myst 2002. All rights reserved.

#Вдогонку к прошлому номеру:

Вот только что получил этот талмуд под номером #29
Глаза резануло:
> Открываем толстый талмуд, и выясняем, что если команда ret имеет операнд,
> то при этом еще и увеличивается значение регистра esp на число 2*операнд.
Таки ведь esp увеличивается на 'операнд' байт (типа без 2*)
(С) Dr. Golova, издранно из RTFM_Helpers

#Послесловие

И хорошая новость: появился новый (в)редактор, в совершенстве знающий русский язык. Теперь то, что вы будете читать (и прочитали только шта) стилистически выдержано и грамотно. Надеюсь, что в тест не вкрались скрипты остановки нервной деятельности, и все еще живы, бодры и полны сил...
И да пребудут силы с вами!

##########################################################################
Подготовленно к выпуску 19.11.2002
HI-TECH group
##########################################################################