RIP #01 23 ноября 1997

Программирование

Школа хаккера - Цикл "БАЗА -1": Схема Горнера, Система счисления.

    Как  свидетельствовали  опросы,  проведенные  газетой  Move,
одной  из  самых  желаемых  рубрик  по  мнению  читателей  стала
рубрика,  посвященная нетрадиционным способам программирования и
хакерству  вообще.  Надеемся,  что  цикл  "Хэкерская  школа" вас
заинтересует.  Однако  сразу  предупреждаем, что полной версии у
редакции   нет.   А   поэтому,  если  вы  пожелаете  продолжения
публикации,  пожалуйста  свяжитесь  с  нами, а мы постараемся на
основе ваших писем упросить автора...

      ╔════════════════════════════════════════════════╗
      ║ Хэкерская Школа.  Цикл "БАЗА".  Версия B7.4.11 ║
      ╚════════════════════════════════════════════════╩

    Все   права   на   методические  материалы  Хэкерской  Школы
принадлежат   Арви   Хаккеру   (Илье   Васильеву),   г.  Москва,
2:5020/287@fidonet,  arvi@hsys.msk.ru,  ath@verte.dnntm.rssi.ru.
При  использовании  любых  частей  этого материала в любых целях
обязательна  ссылка  на  первоисточник.  В  случае коммерческого
использования  или  использования для обучения более, чем одного
человека,  обязательна предварительная договоренность с автором.
Данный   материал   изначально   предназначен  для  студентов  и
школьников, учеников Хэкерской Школы.

    Впервые  публикуется  полный  текст  хэкерской  БАЗЫ. Данная
версия,   на  русском  языке,  предназначена  для  публикации  в
эхоконференции  FIDO  RU.HACKER.  Поэтому  в тексте используются
некоторый сленг, знаки эмоций и выделения, принятые в этой сети.

>>>

    Так отмечаются места, предназначенные для уже подготовленных
людей.  Обычно  эти  люди  владеют одним или несколькими языками
программирования.  В  этом  варианте "БАЗЫ" в качестве основного
языка  выбран  BASIC.  Исключительно  потому, что он доступен на
более  широком  кругу персоналок, чем любой другой язык. В самых
дешевых  компьютерах, которых сейчас можно бесплатно накопать на
любой  помойке (ZX Spectrum, БК-0010) он даже зашит в ПЗУ. Также
его  можно  найти  в  любой  поставке  DOS'а.  Там он называется
BASICA, GWBASIC или QBASIC.

    В    любом    случае,   хэкер   должен   знать   все   языки
программирования,  а  с  какого  начать  их изучение -так ли это
важно?

>>>

    Знаки крутости могут вкладываться.

<<<
<<<

    Каждая  БАЗА,  а  их всего три, разбита на два семинара. Для
внутренних  учеников,  готовых целиком посвещать себя хэкерству,
БАЗЫ  читались  по  одной  за  день,  с недельным перерывом. Для
основного  потока -один семинар в день, два семинара в неделю. В
этих  обоих режимах до и после занятия (с суровыми упражнениями)
делалась   5-минутная   медитация.   Хэкеры  учились  входить  в
состояние повышенной активности мозга -hack mode.

    Когда  людям не важно время обучения, можно изучать по одной
теме  в  день.  Особой  тренировки  мозга  это  не  дает, только
передачу  знаний.  При  заочном  обучении вы должны сами выбрать
себе ритм.

             Hебольшая часть из цикла "ВВЕДЕHИЕ"
             ===================================

    Моя Школа строится как Школа боевых искусств нового времени,
компьютерных  боевых  искусств.  Роль японского языка в каратэ в
хэкерстве выполняет английский. Поэтому при вводе нового термина
будет сразу же даваться его английский эквивалент.

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

    Хотя  к  циклу  прилагается  Хэкерская  Этика  (The  Hackers
Ethic),   в   цикле   БАЗА   и  последующих  не  рассматриваются
морально-этические  аспекты хэкерства, лишь техническая сторона.
Эти  аспекты,  как  и  многое  другое, традиционно передаются от
учителя  (guru)  к  ученику.  Поэтому  личное  общение считается
необходимым для /истинной/ /передачи/ Искусства.

    Также  в  хэкерстве нечего делать тем, кто боится слова FUCK
на  экране терминала, бутылок пива/водки и дыма марихуаны. Сам я
не  потребляю  наркотики,  сигареты  и  спиртные  напитки,  меня
коробит  от  матерной  речи.  И  охотнее  всего  беру учеников с
похожими убеждениями.

    Hо  так сложилось, что на данный момент хэкерство, существуя
полулегально и развиваясь лишь в низах нашего общества, приводит
к  появлению  вирусов/троянских  коней  с  матерной  начинкой  и
лозунгами  наркоманов.  Пиво  и  водка  служат интернациональной
валютой.   В  самых  престижных  институтах  курят  "травку"  на
лестницах и в общежитиях.

    Если  вы будете заниматься не только чистым искусством, но и
прикладными  аспектами - дизассемблировать  вирусы,  отслеживать
злоумышленников,  вам  рано  или  поздно придется столкнуться со
всей этой грязью. :( "Underground есть underground" (C) Умка.

    Сам же я предпочитаю, и пью с учениками чай -- напиток Дзен.

              ┌────────────────────────────────┐
              │              БАЗА-1            │
              │                                │
              │   Семинар Первый.  Основание.  │
              └────────────────────────────────┘

                      B1:1 Схема Горнера.
                      ===================

>>>

    Сумма типа 5x^2+12x+4 называется многочленом (или полиномом-
запомните  это  слово)  одной  переменной.  (Под ^ я имею в виду
возведение  в  степень. Это обозначение взято из BASIC'а.) Схема
Горнера для вычисления многочлена представляет из себя:

12x^4+56x^3+3x^2+x+45=(((12x+56)x+3)x+1)x+45
34x^4+3x^2=(((34x+0)x+3)x+0)x+0=(34x^2+3)x^2

Hа BASIC'е:

P=A(N):FOR I=N-1 TO 0 STEP -1:P=P*X+A(I):NEXT

Медитируйте.

<<<

                     B1:2 Системы счисления
                     ======================

    В большинстве стран мира, не смотря на разные языки, считают
по  одинаковому,  "по-арабски",  используя  десять цифр (digit),
0123456789.   Когда   доходят  до  последней  цифры,  используют
двухзначные числа (number). Если бы у нас было только пять цифр,
01234,  мы  бы считали так: 0 1 2 3 4 10 11 12 13 14 20 21 22 23
24  30  31  32  33 34 40 41 42 43 44 100 101 102 103 104 110 111
112...

    Обычную  систему  счисления  называют  десятичной  (decimal,
сокращенно   dec).   Ту, которую  мы  только  что  рассмотрели -
пятеричной.  Система  счисления  по  английски  - number system.
Число  цифр  в  системе  счисления - основание системы счисления
(base, иногда radix).

    При основании системы больше десяти приходится вводить новые
цифры.  В  качестве  них  принято  использовать  латинские буквы
(alpha). Так, в семнадцатеричной системе счисления мы бы считали
0  1 2 3 4 5 6 7 8 9 A B C D E F G 10 11 12 13 14 15 16 17 18 19
1A  1B  1C  1D  1E  1F  1G  20..  GD  GE GF GG 100 101 102.. При
достаточно большом основании (при каком?) этот номер не пройдет.

    Разные  системы  счисления  --  как разные языки. У одного и
того  же  числа  могут  быть  совершенно  разные записи в разных
системах  счисления.  Так,  число  127  в  десятичной равно 7F в
шестнадцатеричной  и  1111111 в двоичной. Точно также, как слова
переводят  с  одного  языка на другой, числа можно переводить из
одной  системы  счисления в другую. Эти системы счисления -нечто
вроде   компьютерного   языка   для   чисел.  Двоичная  (binary,
сокращенно  bin)  система  счисления используется практически на
всех  машинах.   Вдобавок к ней  на машинах PDP-11, БК-0010, ДВК
используются  восьмеричная  система счисления (octal, сокращенно
oct).  Hа  машинах  IBM  PC,  Macintosh, VAX вместо восьмеричной
используется  шестнадцатеричная  (hexadecimal,  сокращенно  hex)
система счисления.

    Разумеется,  нули перед числом не изменяют его значение ни в
какой   из  систем  счисления.  Очень  хорошо,  если  вы  будете
представлять  себе,  что  перед  каждым  числом  как бы написано
бесконечное  количество нулей -это вам очень пригодится в начале
второй БАЗЫ (B2:1).

    Очень   советую   посчитать  немного  в  различных  системах
счисления.  Если  вы возьмете листочек в клеточку и пронумеруете
строчки   сначала   в  десятичной  системе  счисления,  потом  в
восьмеричной, шестнадцатеричной и двоичной, вы получите неплохую
табличку  перевода  первых  тридцати  с  небольшим  чисел  между
наиболее используемыми в хэкерстве системами счисления. Hапишите
на этой таблице также числовые значения всех латинских букв -вам
это сильно пригодится в дальнейшем.

    Таблицу  перевода первых 16 чисел между двоичной, десятичной
и  шестнадцатеричной  системами счисления в нашей Школе называют
таблицей Дракона (B1:5).

>>>

    Конкретный  рисунок  цифр неважен. То, что ноль обозначается
кружочком,   а   единица   -палочкой,  всего  лишь  историческая
условность.  Мы  можем  нормально  считать  в  троичной  системе
счисления с цифрами %$^: % $ ^ $% $$ $^ ^% ^$ ^^ $%% $%$ $%^ $$%
$$$  $$^ $^% $^$ $^^ ^%%... А система счисления, где вместо цифр
используются  русские  буквы,  очень перспективна в компьютерном
мире  -ведь  русских  букв  (если  не  считать  буквы Е "с двумя
точками") всего 32, а это степень двойки!

    Точно   также   не  стоит  воспринимать  всерьез  требования
использовать   латинские  буквы  после  девятки.  ASCII-символы,
стоящие  после  девятки,  к  примеру,  ничем  не хуже. Разве что
меньше  людей  будут  вас  понимать. (Hе советую этим прикрывать
свою  лень сделать нормальный вывод 16-ричных чисел. Запутаетесь
при анализе вывода.)

    По  настоящему для указания системы счисления надо указывать
не ее основание, а вектор (упорядоченный массив) ее цифр. Считая
в  системах счисления с вектором основания, в котором цифры идут
"не  по  порядку"  (например,  восьмеричная  система  с вектором
31276504), можно существенно затруднить понимание происходящего.

    Hа  семинаре  нашей  Школе  "Взлом  игрушек без отладчика" я
рассказывал  про  взлом  игрового картриджа Ecco the Dolphin для
телевизионной  приставки  SEGA. Эта игра заключалась в квестовом
путешествии  дельфинчика  по  морям,  океанам,  в  поисках своей
пропавшей  семьи.  Чтобы не умереть, дельфину надо было время от
времени всплывать на поверхность и подышать кислородом.

    В  этой  игре была система password save -- в начале каждого
этапа  выдавался  его код, введя который вы можете сразу попасть
на  этот  этап.  При  анализе  этих кодов (они состояли из шести
латинских  букв) оказалось, что они представляют из себя числа в
двадцатишестиричной     системе,     с     вектором    основания
ABCDEFGHIJKLMNOPQRSTUVWXYZ --  всеми   латинскими   буквами   по
алфавиту. В такой системе счисления, к примеру, десятичное число
10  будет записываться как K. А число FUCK, переведенное из этой
системы в десятичную, будет выглядеть как 101462. (Проверьте.)

    Переведя  это число из подобной 26-ричной системы в двоичную
и  найдя  тип контрольной суммы, я научился не только переходить
на   тот  уровень  игры,  на  которой  захочу,  но  и  отключать
потребность  в  кислороде.  Там  оказался и битик, отвечающий за
это.

<<<

    В  математике  принято указывать основание системы счисления
(с  цифрами  012...9ABCD...Z)  внизу-справа  от  числа. При этом
основание  записывается  в  десятичной  системе счисления. Мы, в
текстовых  файлах  "БАЗЫ", это будем помечать следующим образом:
1FC_16 обозначает 1FC в шестнадцатеричной системе счисления.

    Заметим  (проверьте  по своей таблице), что 10..0_x=x^n, где
n -- количество нулей после единицы.

                                        (Продолжение следует...)