Представление знака в числах.

Методов представления чисел со знаком «плюс» или «минус» несколько, но в компьютерах обычно применяется метод «дополнительный код» или «two’s complement».

Разница в подходе к знаковым/без знаковым числам, собственно, нужна потому что, например, если представить 0xFFFFFFFE и 0x00000002 как без знаковое, то первое число (4294967294) больше второго (2). Если их оба представить как знаковые, то первое будет −2, которое, разумеется, меньше чем второе (2). Вот почему инструкции для условных переходов представлены в обоих версиях — и для знаковых сравнений (например, JG, JL) и для без знаковых (JA, JB).

Для простоты, вот что нужно знать:

• Числа бывают знаковые и без знаковые.

Знаковые типы в Си/Си++:

– int64_t (-9,223,372,036,854,775,808..9,223,372,036,854,775,807) (- 9.2.. 9.2 квинтиллионов) или

0x8000000000000000..0x7FFFFFFFFFFFFFFF),

– int (-2,147,483,648..2,147,483,647 (- 2.15.. 2.15Gb) или 0x80000000..0x7FFFFFFF),

– char (-128..127 или 0x80..0x7F),

– ssize_t.

Без знаковые:

– uint64_t (0..18,446,744,073,709,551,615 (18 квинтиллионов) или 0..0xFFFFFFFFFFFFFFFF),

– unsigned int (0..4,294,967,295 (4.3Gb) или 0..0xFFFFFFFF),

– unsigned char (0..255 или 0..0xFF),

– size_t.

 

• У знаковых чисел знак определяется самым старшим битом: 1 означает «минус», 0 означает «плюс».

• Преобразование в большие типы данных обходится легко:

Конвертирование 32-битного значения в 64-битное. Нужно просто выставить в 0 все биты в старшей части. Но для знаковых типов это не подходит: знак числа должен быть скопирован в старшую часть числа-результата.

• Изменить знак легко:

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

находится на другой стороне на том же расстоянии от нуля. Прибавление единицы необходимо из-за присутствия нуля посредине.

• Инструкции сложения и вычитания работают одинаково хорошо и для знаковых и для без знаковых значений. Но для операций умножения и деления, в x86 имеются разные инструкции: IDIV / IMUL для знаковых и DIV / MUL для без знаковых.

• Еще инструкции работающие с знаковыми числами: CBW/CWD/CWDE/CDQ/CDQE, MOVSX, SAR.

 

Порядок байт (Endianness)

Endianness (порядок байт) это способ представления чисел в памяти.

Big-endian (от старшего к младшему).

Число 0x12345678 представляется в памяти так:

Адрес в памяти	Значение байта
+0	0х12
+1	0х34
+2	0х56
+3	0х78

Таблица 4. Представление в памяти.

CPU с таким порядком включают в себя Motorola 68k, IBM POWER.

Little-endian (от младшего к старшему).

Число 0x12345678 представляется в памяти так:

Адрес в памяти	Значение байта
+0	0х78
+1	0х56
+2	0х34
+3	0х12

Таблица 5.

CPU с таким порядком байт включают в себя Intel x86.

Bi-endian (переключаемый порядок).

CPU поддерживающие оба порядка, и его можно переключать, включают в себя ARM, PowerPC, SPARC, MIPS, IA64, и т.д.

Конвертирование.

Инструкция BSWAP может использоваться для конвертирования.

Сетевые пакеты TCP/IP используют соглашение big-endian, вот почему программа, работающая на little-endian архитектуре должна конвертировать значения.

Обычно, используются функции htonl() и htons().

Порядок байт big-endian в среде TCP/IP также называется, «network byte order», а порядок байт на компьютере «host byte order». На архитектуре Intel x86, и других little-endian архитектурах, «host byte order» это little-endian, а вот на IBM POWER это может быть big-endian, так что на последней, htonl() и htons() не меняют порядок байт.

 

Виды памяти.

Есть три основных типа памяти:

 

• Глобальная память AKA «static memory allocation». Нет нужды явно выделять, выделение происходит просто при объявлении переменных/массивов глобально. Это глобальные переменные расположенные в сегменте данных или констант. Доступны глобально (поэтому считаются анти-паттерном). Не удобны для буферов/массивов, потому что должны иметь фиксированный размер. Переполнения буфера, случающиеся здесь, обычно перезаписывают переменные или буферы расположенные рядом в памяти.

 

• Стек AKA «allocate on stack», «выделить память в/на стеке». Выделение происходит просто при объявлении переменных/массивов локально в функции. Обычно это локальные для функции переменные. Иногда эти локальные переменные также доступны и для нисходящих функций (callee-функциям, если функция-caller передает указа-

тель на переменную в функцию-callee). Выделение и освобождение очень быстрое, достаточно просто сдвига SP. Но также не удобно для буферов/массивов, потому что размер буфера фиксирован, если только не используется alloca() (или массив с переменной длиной). Переполнение буфера обычно перезаписывает важные структуры стека.

 

• Куча (heap) AKA «dynamic memory allocation», «выделить память в куче». Выделение происходит при помощи вызова malloc()/free() или new/delete в Си++. Самый удобный метод: размер блока может быть задан во время исполнения. Изменение размера возможно (при помощи realloc()), но может быть медленным. Это самый медленный метод выделения памяти: аллокатор памяти должен поддерживать и обновлять все управляющие структуры во время выделения и освобождения. Переполнение буфера обычно перезаписывает все эти структуры. Выделения в куче также ведут к проблеме утечек памяти: каждый выделенный блок должен быть явно освобожден, но кто-то может забыть об этом, или делать это неправильно. Еще одна проблема — это «использовать после освобождения» — использовать блок памяти после того как free() был вызван на нем, это тоже очень опасно.

 

 

Предсказатели переходов.

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

Необходимость предсказания адреса «целевой» инструкции вызвана тем, что этот адрес может быть извлечён из x86-инструкции перехода и вычислен только на финальной стадии декодирования, с большой задержкой. Более того, даже простое выделение инструкций переменной длины из считанного блока и поиск среди них инструкций перехода займёт какое-то время. Поэтому в процессорах архитектуры x86 предсказание производят по целому блоку, без разбиения его на составляющие инструкции.

В современных процессорах для предсказания адреса перехода обычно используют специальную таблицу адресов переходов BTB (Branch Target Buffer). Эта таблица устроена подобно ЭШу и содержит адреса инструкций, на которые ранее производились переходы. Например, в процессоре P-III таблица BTB имеет размер 512 элементов и организована в виде 128 наборов с ассоциативностью 4. Для адресации набора используются младшие разряды адреса 16-байтового блока инструкций (b10-4). Если в этом блоке есть инструкции перехода, и если эти инструкции отрабатывали ранее, то алгоритм предсказания может очень быстро найти адрес целевой инструкции в таблице BTB и начать считывание блока, содержащего эту инструкцию. Адреса целевых инструкций помещаются в BTB в момент отставки соответствующих инструкций перехода.

В других современных процессорах размер таблицы BTB достигает 2048 элементов (K8) и 4096 элементов (P-4). Организация данной подсистемы в процессоре K8 несколько отличается от классической и основывается на предварительной разметке блоков инструкций в так называемых массивах селекторов перед помещением их в I-кэш. Эти селекторы привязаны к положению инструкций в I-кэше и при их вытеснении оттуда сохраняются в L2-кэше (в так называемых ECC-битах, предназначающихся для коррекции ошибок). Элементы таблицы BTB также привязаны к положению инструкций в I-кэше и теряются при их вытеснении. Это несколько снижает эффективность предсказания адресов переходов в процессоре K8.

Для предсказания направления условного перехода используется другой механизм, основанный на изучении поведения переходов в программе в процессе её выполнения (своего рода «сбор статистики»). Этот механизм учитывает как локальное поведение конкретной инструкции перехода (например, «как правило, переходит», «как правило, не переходит»), так и глобальные закономерности («чередуется по определённому закону» и т.п.). История поведения инструкций условного перехода записывается в специальных структурах, обычно называемых «таблицами истории переходов» (Branch History Table, BHT). Современные механизмы предсказания переходов обеспечивают правильное предсказание более чем в 90 процентах случаев.

 

Хеш-функции.

Простейший пример это CRC32, алгоритм «более мощный» чем простая контрольная сумма, для проверки целостности данных. Невозможно восстановить оригинальный текст из хеша, там просто меньше информации: ведь текст может быть очень длинным, но результат CRC32 всегда ограничен 32 битами. Но CRC32 не надежна в криптографическом смысле: известны методы как изменить текст таким образом, чтобы получить нужный результат. Криптографические хеш-функции защищены от этого. Такие функции как MD5, SHA1, и т.д., широко используются для хеширования паролей для хранения их в базе. Действительно: БД форума в интернете может и не хранить пароли (иначе злоумышленник получивший доступ к БД сможет узнать все пароли), а только хеши. К тому же, скрипту интернет-форума вовсе не обязательно знать ваш пароль, он

только должен сверить его хеш с тем что лежит в БД, и дать вам доступ если cверка проходит. Один из самых простых способов взлома — это просто перебирать все пароли и ждать пока результат будет такой же как тот что нам нужен. Другие методы намного сложнее.