Dragon's Nest – сайт о драконах и для драконов

Dragon's Nest - главная страница
Гнездо драконов — сайт о драконах и для драконов

 

« — Стасик! Hа твой балкон прилетел маленький золотой дракон!
 — Дай ему поесть, он, наверное, голодный.»
«Стасик»

Дракон в компьютере

Схема Горнера.

Сумма типа 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

На BASIC'е:

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

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

Системы счисления

В большинстве стран мира, несмотря на разные языки, считают по одинаковому, «по-арабски», используя десять цифр (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).

При основании системы больше десяти приходится вводить новые цифры. В качестве них принято использовать латинские буквы (alрha). Так, в семнадцатеричной системе счисления мы бы считали 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). На машинах IBM PС, Macintosh, VAX вместо восьмеричной используется шестнадцатеричная (hexadecimal, сокращенно hex) система счисления.

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

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

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

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

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

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

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

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

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

В математике принято указывать основание системы счисления (с цифрами 012…9ABСD…Z) внизу-справа от числа. При этом основание записывается в десятичной системе счисления. Мы, в текстовых файлах «БАЗЫ», это будем помечать следующим образом: 1FС_16 обозначает 1FС в шестнадцатеричной системе счисления.

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

Укрощение Дракона

Алгоритм перевода из любой системы в десятичную мы называем алгоритмом Укрощения Дракона: X_n->Y_10. Называем потому, что длинная строчка вычисления напоминает спину лежащего дракона, а ответ — голову смирившегося дракона. Он основан на наблюдении, что

34947 = 30000+4000+900+40+7 = 3*10^4 + 4*10^3 + 9*10^2 + 4*10 + 7

То есть число равно сумме его цифр, умноженных на соответствующие степени основания. Переводы чисел 1210_3 и С00L_22:

1210_3 = 1*3^3 + 2*3^2 + 1*3 + 0 = 27 + 18 + 3 = 48_10
С00L_22 = 12*22^3 + 0*22^2 + 0*22 + 21 = 127776 + 21 = 127797

Многие книги эту версию алгоритма Укрощения Дракона используют для определения, что такое системы счисления. Попробуйте попереводить побольше чисел из самых различных систем счисления. Желательно без использования калькулятора, выполняя все арифметические действия в уме или на листочке. Побольше двоичных чисел — они нам еще пригодятся!

Применив схему Горнера, мы получим намного более эффективную версию алгоритма Укрощения Дракона.

1210_3 = ((1*3+2)*3+1)*3+0 = 16*3 = 48

С00L_22 = (((12*22+0)*22+0)*22+21 = 127776 + 21 = 127797

В чем его эффективность? Теперь не требуется операций возведения в степень! При программировании на ассемблере — это просто блеск! Даже на языках высокого уровня программа перевода получается значительно быстрее и короче. Попробуйте составить эту программу, переводящую числа из любой системы счисления на привычный вам десятичный язык. Она почти дублирует программу для схемы Горнера.

Хэкеру нужно постоянно быть в боевой готовности — кто знает, где ему придется демонстрировать Искусство. Вполне возможно, что вас попросят починить или удалить вирус из компьютера в самом странном месте — в супермаркете или дома у вашей девушки. (В фильме «War Games» молодой хэкер Дэвид, подсоединив случайно оказавшийся диктофон к кодовому замку, сумел записать и повторить сигналы открытия двери и убежать из под ареста.)

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

Если под рукой не оказалось даже примитивнейшего калькулятора, то новый алгоритм Укрощения Дракона можно использовать для перевода числа столбиком. Результат одного примера является начальным значением для следующего.

   1     12
  *3    *22
 ---   ----
   3     24
  +2    24
 ---   ----
   5    264
  *3     +0  Конечно, нули я здесь прибавляю лишь для обучения,
 ---   ----  в реальной жизни это делать необязательно. :-)
  15    264
  +1    *22
 ---   ----
  16    528
  *3   528
 ---   ----
  18   5808
  3      +0
 ---   ----
  48   5808
  +0    *22
 ---   ----
  48  11616
     11616
     ------
     127776
        +21
     ------
     127797

Здесь мы Укрощенного Дракона ставим вертикально, мордой вниз. Наверное, чтобы их больше поместилось…

Вот еще один смысл слова «Укрощение». Мы переводим числа из странной записи в обычную. При вводе же в машину чисел требуется обратная ситуация, десятичные числа должны быть переведены в машинный вид. Хотя эта операция обычно выполняется машиной, в нашей Школе ее принято называть «Атакой».

Атака Дракона

Обратное действие, перевод из десятичной системы счисления в произвольную, мы называем Атакой Дракона: Y_10->X_n. Это действие обычно выполняется, когда мы хотим ввести информацию внутрь компьютера. Мы живем в десятичном мире, а компьютер — в каком-нибудь шестнадцатеричным. И для того, чтобы ввести что-нибудь наше в его мир, «Атаковать», нам придется перевести это в чужую систему счисления.

Тут надо уметь делить. :-) Переведем числа, полученные при Укрощении Дракона, обратно, в «родные» системы счисления, последовательно деля их на основание, пока не получится число, меньшее самого основания. Это число столбиком уже не разделишь. :-)

  48 |  3              127797|  22
  -3  +-----+          -110   +------+
  --  |  16 |  3        ---   |  5808|  22
   18   -15 +----+       177    -44  +------+
  -18    -- |  5 |  3   -176     --  |  264 |  22
   --     1   -3 +----   ---     140   -22  +----
    0         -- |  1      197  -132    --  |  12=C
               2          -176   ---     44
                           ---    88    -44
                            21=L -88     --
                                  --      0
                                   0

Результат считывается из последнего частного и остатков, собираемых в обратном порядке. Так в первом случае получаем 1210_3, а во втором — С00L_22.

Попробуйте перевести числа, получившиеся при самостоятельной практике Укрощения, обратно, в их исходные системы счисления. Попробуйте несколько десятичных чисел перевести во всякие странные системы счисления и обратно.

Если вы умеете хорошо делить в уме (или используете калькулятор), то удобнее использовать другую запись:

   48|0  127797|21=L
   16|1    5808| 0
    5|2     264| 0
    1|       12=C

Здесь при каждом делении остаток записывается справа от черты, а частное — внизу. Как всегда, при Атаке ответ считывается в обратном порядке — снизу вверх.

Составьте программу, выполняющую автоматический перевод в любую систему счисления.

Ручной Дракон

Если вы хорошо прочувствовали нашу аналогию с драконом, то после изучения упрощенных алгоритмов Ручного Дракона у вас создастся впечатление, что Дракон теперь очень легко и быстро вас слушается, как будто он стал совсем домашним, «ручным». Но внимание! Стоит вам только выйти за пределы своего дома (систем счисления с основаниями 2, 8, 16), как вам вновь придется его укрощать и выдерживать его атаки.

Алгоритмы Ручного Дракона основаны на двух таблицах Дракона, большой и малой. Вот они:

   +------+---+----+      +-----+---+
   | 0000 | 0 |  0 |      | 000 | 0 |
   | 0001 | 1 |  1 |      | 001 | 1 |
   | 0010 | 2 |  2 |      | 010 | 2 |
   | 0011 | 3 |  3 |      | 011 | 3 |
   | 0100 | 4 |  4 |      | 100 | 4 |
   | 0101 | 5 |  5 |      | 101 | 5 |
   | 0110 | 6 |  6 |      | 110 | 6 |
   | 0111 | 7 |  7 |      | 111 | 7 |
   | 1000 | 8 |  8 |      +-----+---+
   | 1001 | 9 |  9 | Малая таблица Дракона
   | 1010 | A | 10 |
   | 1011 | B | 11 |
   | 1100 | C | 12 |
   | 1101 | D | 13 |
   | 1110 | E | 14 |
   | 1111 | F | 15 |
   +------+---+----+
Большая таблица Дракона


Когда мы рисуем их на бумаге, мы обычно отчеркиваем в Большой таблице Дракона ту часть, которая совпадает с Малой и получаем две таблицы в одной. Большая таблица Дракона больше пригодится при работе с шестнадцатеричными машинами типа IBM PС, а Малая — при работе с восьмеричными машинами, например, серии БК.

Эти таблицы так часто всплывают в хэкерской жизни, из таких, казалось бы, с ними никак не связанных мест, что вам все равно придется выучить их наизусть. Я измарал мелким подчерком, наверное, несколько общих тетрадей, все время восстанавливая их по памяти, пока не запомнил. Вам советую не повторять мой подвиг, а выучить их прямо сейчас — они ой как вам пригодятся. :-)

Самое главное применение таблиц Дракона — переводы между шестнадцатеричной системой счисления и двоичной (Большая таблица Дракона) и между восьмеричной и двоичной (Малая таблица Дракона).

Как известно, существуют родственные языки. Например, древнеславянский и русский, русский и украинский. Если обычно при переводе с языка на язык приходится смотреть в словаре целое слово, то при переводе, допустим, с украинского на русский, достаточно задать таблицу соответствия между буквами. Например, менять букву 'i' на 'и', а 'и', в свою очередь, на 'ы'.

Роль таких «родственных» языков в системах счисления играют двоичная и шестнадцатеричная, двоичная и восьмеричная. А таблицей перевода и являются таблицы Дракона. Итак, разберем все случаи. Следите за нами, здесь есть подводные камни!

16->2

Ну это просто. Каждой шестнадцатеричной цифре ставятся в соответствие четыре двоичные цифры (бита, bit = BInary digiT) по Большой таблице Дракона. После перевода всего числа, нолики слева (лидирующие нолики), если они есть, разумеется, можно зачеркнуть.

12FС_16 = 0001 0010 1111 1100_2 = 1001011111100_2
2->16

Немногим сложнее. Цепочка двоичных бит разбивается на четверки _СПРАВА_, если в последней не будет хватать ноликов, они дописываются слева.

1011001011_2 = 0010 1100 1011_2 = 2СB_16
8<->2

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

276_8 = 010 111 110_2 = 10111110_2
1011001011_2 = 001 011 001 011_2 = 1313_8

ВНИМАНИЕ! Алгоритмы Упрощенного Дракона существуют лишь для переводов 16<->2 и 8<->2. Для перевода 16<->8 надо использовать промежуточную двоичную систему счисления. Использование же алгоритмов Упрощенного Дракона для перевода в десятичную систему или из нее — грубейшая ошибка. За нее вы будете выгнаны с аттестации коленкой под зад!

Вообще, запомните формулу Упрощенного Дракона: 8<->2<->16.

ВНИМАНИЕ! Распространенное заблуждение!

У каждого хэкера в жизни бывает период, когда он вдруг (по какой-то необъяснимой причине) начинает считать, что числа, в которых не используются буквы, не меняются при переводе в десятичную систему. То есть, например, 123_16=123_10. Так вот, ЭТО НЕ ТАК! Подумайте, почему. Посчитайте, чему равно 123_16 по алгоритму Укрощения.

Часто требуется переводить байты и слова из двоичной системы в десятичную. Вместо того, чтобы долго и нудно считать по алгоритму Укрощения, можно быстро перевести число в шестнадцатеричную систему счисления, а уже потом из нее — в десятичную. Экономится куча времени.

1010 1001_2 = A9_16 = 10*16+9 = 169_10

Байт переводится мгновенно и в уме!

Обозначения

На самом деле, такую глобальную роль шестнадцатеричная и восьмеричная системы счисления играют исключительно благодаря алгоритмам Ручного Дракона. Внутри машина считает исключительно «по двоичному». Шестнадцатеричная (или восьмеричная, на DEС'овских машинах) система счисления позволяет вместо длинных цепочек ноликов и единиц писать короткие числа, делает хэкерскую жизнь более разнообразной. Эти системы — промежуточное звено между машиной и человеком, между двоичной и десятичной системами счисления.

Роль систем счисления огромная. К примеру, права доступа к файлу в системе UNIX изменяются из shell'а командой chmod. И эта команда требует задания аргумента (прав доступа) в восьмеричной системе счисления! Так команда

chmod 666 /etc/рasswd

Открывает доступ на чтение и запись всем пользователям к файлу паролей в системе UNIX. Вы видите теперь, что даже самые тупые системные администраторы должны разбираться в восьмеричной системе счисления. Так чего же говорить о хэкерах!

В различных языках программирования числа в этих системах обозначаются по разному. Вот сводная таблица для основных языков:

+-------------+-------+--------+--------+----------------+
|             | C/C++ | Pascal |  BASIC |    Assembler   |
+-------------+-------+--------+--------+--------+-------+
| DECimal     |   12  |    12  |  12    | 12,12d |   12T |
| HEXadecimal |  0xC  |    $C  | &hC    |   0Ch  |       |
| OCTal       |  014  |   ОЕФ  | &o14   |   14o  |   14Q |
| BINary      |  ОЕФ  |   ОЕФ  | &b1100 | 1100b  | 1100Y |
+-------------+-------+--------+--------+--------+-------+

В Схеме Горнера мы отметили, что нули в начале числа не влияют на его значение. Создатели языка С решили по другому. Поскольку никто в здравом уме не начинает числа с нуля — кому охота набивать лишнии нулики, ноль в начале они используют для обозначения восьмеричного числа.

При всех способах записи регистр букв неважен. Даже строгий на регистры С позволяет начинать шестнадцатеричные числа как с 0x, так и с 0X. Кстати, гуру Киевского Центра нашей Школы, Сергей Головко (2:463/140), сообщил, что в ранних версиях компиляторов С различных фирм шестнадцатеричные числа надо было начинать с 0x0, иначе они глюкали.

При программировании на ассемблере если шестнадцатеричное число начинается с буквы, перед ним обязательно должен ставится ноль. Иначе ассемблер подумает, что вы имели в виду переменную Сh, а не число С_16. Ряд людей с низким уровнем интеллекта, не способным вместить это правило, ставят ноль впереди всех шестнадцатеричных чисел. Хуже всего, когда такие люди начинают писать учебники…

[IBM PС teaching on]

Суффиксы T, Q и Y введены в ассемблер MASM сравнительно недавно. Дело в том, что с помощью директивы .RADIX ассемблер позволяет менять систему счисления, действующую по умолчанию. Раньше, когда систему счисления изменяли на шестнадцатеричную, числа вроде 12D, которые с первого взгляда являются обычными шестнадцатеричными, интерпретировались как 12_10. Это порождало сеть мелких незаметных психоделических ошибок, мешавших чайникам использовать .RADIX 16.

[IBM PС teaching off]

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

Для перевода чисел в BASIС'е из десятичной системы счисления в шестнадцатеричную, двоичную и восьмеричную используются функции HEX$, BIN$ и OСT$.

Для перевода чисел из этих систем в десятичную надо воспользоваться хитростью.

?VAL(«&hFС»)

Информация с сайта http://hscool.netclub.ru/
hscool@netclub.ru