ДСв18_03-представление-с-точкой (1238934), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

int имеет разрядность ≤ 53 бит§ int → float§ Округляется в соответствии в режимом§¢x86: вычисления выражения в 80-битном представлении33Головоломки плавающей точки¢Для каждого следующего выражения Си объясните:§ либо почему оно верно для любых значений аргументов§ либо почему неверно• x == (int)(float) x• x == (int)(double) xint x = …;float f = …;double d = …;Принять, чтони d ни f не есть NaN• f == (float)(double) f• d == (float) d• f == -(-f);• 2/3 == 2/3.0⇒• d < 0.0((d*2) < 0.0)• d > f-f > -d⇒• d * d >= 0.0• (d+f)-d == f34Плавающая точка¢¢¢¢¢¢Основы: Двоичные дробиСтандарт «плавающей точки» IEEE : ОпределениеПримеры и свойстваОкругление, сложение, умножениеПлавающая точка в CиСводка35Сводка¢¢¢Плавающая точка IEEE имеет ясные математическиесвойства.

Почти!Представимы числа вида (-1)S M x 2EОперации независимы от реализации§ Если все выполнены с двоной точностью и затем округлены¢Не совпадают с вещественной арифметикой§ Нарушены свойства ассоциативности/дистрибутивности§ Создаёт сложности для разработчиков компиляторов иответственных численных приложений36Дополнения37Создание числа с плав. точкой¢Шаги§ Нормализовать до получения старшей 1§ Округлить до укладывания в мантиссу§ Перенормализовать для учёта округления¢Пример§ Преобразовать 8 битовые беззнаковые числа в формат сплавающей точкой128131533351386310000000000011010000111100010001000100111000101000111111sexpfrac14 бита3 бита38НормализацияЗначение12815171913863Двоичное100000000000111100010001000100111000101000111111sexpfrac14 бита3 битаДробь1.00000001.11100001.00010001.00110001.00010101.1111100Порядок73447539Округление1.BBGRXXXGuard bitSticky bit: ИЛИ остальных битRound bit: 1-й удалённый¢Правила округления§ Round = 1, Sticky = 1 ➙ > 0.5§ Guard = 1, Round = 1, Sticky = 0 ➙ округление к четномуЗначение12815171913863ДробьGRSДобав.Округлённое1.00000001.11100001.00010001.00110001.00010101.1111100000100010110011111NNNYYY1.0001.1111.0001.0101.00110.00040Перенормализация¢Проблема§ Округление может вызвать переполнение§ Решается сдвигом одиночным сдвигом вправо и увеличениемпорядкаЗначение128151719138636)Округленное1.0001.1111.0001.0101.00110.000Пор.734475Уточнённое1.000Результат12815162013464 (пор.41Интересные числа{одинарные,двойные}ОписаниеexpfracЧисленное значение¢ Ноль00…00 00…000.0¢ Наименьшее денормализ.

00…0000…012– {23,52} x 2– {126,1022}§ Одинарное ≈ 1.4 x 10–45§ Двойное ≈ 4.9 x 10–324¢ Наибольшее денормализ.00…00 11…11(1.0 – ε) x 2– {126,1022}§ Одинарное ≈ 1.18 x 10–38§ Двойное ≈ 2.2 x 10–308¢ Наименьшее нормализ.00…01 00…001.0 x 2– {126,1022}§ Ближайшее большее наибольшего денормализованного¢ Единица01…11 00…001.0¢Наибольшее нормализ.11…10 11…11(2.0 – ε) x 2{127,1023}§ Одинарное ≈ 3.4 x 1038§ Двойное ≈ 1.8 x 1030842Приложение булевой алгебры¢Клодом Шенноном применена к цифровым системам§ Диплом MIT 1937 год§ Рассмотрены схемы реле§Замкнутый контакт кодируется как 1, разомкнутый как 0A&~BAКонтакт есть если~BA&~B | ~A&B~AB~A&B= A^B43Пример небезопасного кода/* Участок памяти ядра содержит данные доступные пользователю */#define KSIZE 1024char kbuf[KSIZE];/* Копируем не более maxlen байт из области ядра в буфер пользователя */int copy_from_kernel(void *user_dest, int maxlen) {/* Счётчик байт len – минимальное из размера буфера и maxlen */int len = KSIZE < maxlen ? KSIZE : maxlen;memcpy(user_dest, kbuf, len);return len;}Аналог кода найденного в реализации getpeername FreeBSD’s¢ Легионы способных людей пытаются находить уязвимости впрограммах¢44Типичное применение/* Участок памяти ядра содержит данные доступные пользователю */#define KSIZE 1024char kbuf[KSIZE];/* Копируем не более maxlen байт из области ядра в буфер пользователя */int copy_from_kernel(void *user_dest, int maxlen) {/* Счётчик байт len – минимальное из размера буфера и maxlen */int len = KSIZE < maxlen ? KSIZE : maxlen;memcpy(user_dest, kbuf, len);return len;}#define MSIZE 528void getstuff() {char mybuf[MSIZE];copy_from_kernel(mybuf, MSIZE);printf(“%s\n”, mybuf);}45Вредоносное применение/* Определение библиотечной функции memcpy */void *memcpy(void *dest, void *src, size_t n);/* Участок памяти ядра содержит данные доступные пользователю */#define KSIZE 1024char kbuf[KSIZE];/* Копируем не более maxlen байт из области ядра в буфер пользователя */int copy_from_kernel(void *user_dest, int maxlen) {/* Счётчик байт len – минимальное из размера буфера и maxlen */int len = KSIZE < maxlen ? KSIZE : maxlen;memcpy(user_dest, kbuf, len);return len;}#define MSIZE 528void getstuff() {char mybuf[MSIZE];copy_from_kernel(mybuf, -MSIZE);.

. .}46Математические свойства UAdd¢Сложение по модулю образует абелеву группу§ Замкнута относительно сложения§§§§0 ≤ UAddw(u , v) ≤ 2w –1КоммутативнаUAddw(u , v) = UAddw(v , u)АссоциативнаUAddw(t, UAddw(u , v)) = UAddw(UAddw(t, u ), v)0 является нейтральным элементомUAddw(u , 0) = uЛюбому элементу есть обратный§ LetUCompw (u ) = 2w – uUAddw(u , UCompw (u )) = 047Математичские свойства TAdd¢Группа изоморфная беззнаковым с UAdd§ TAddw(u , v) = U2T(UAddw(T2U(u ), T2U(v)))§¢т.к.

битовые преобразования идентичныДополнительны коды с TAdd образуют группу§ Замкнута, коммутативна, ассоциативна, 0 – нейтральный элемент§ Для каждого элемента есть обратныйì-uTCompw (u) = íîTMinwu ¹ TMinwu = TMinw48Определение TAdd¢Функциональность§ Полное суммированиетребует w+1 бит§ Отбрасывание MSB§ Интерпретацияоставшихся бит какцелого числа вдополнительном коде⎧ u + v + 2w⎪⎪TAddw (u,v) = ⎨ u + v⎪wu+v−2⎪⎩ПоложительноепереполнениеTAdd(u , v)>0v<0<0Отрицательноепереполнениеu>0u + v < TMinwПереполнениеотрицательнымиTMinw ≤ u + v ≤ TMaxwTMaxw < u + vПереполнениеположительными49Изменение знака: Инверсия и увеличение¢Утверждение: для дополнительного кода верно~x + 1 == -x¢Инверсия§ Важно: ~x + x == 1111…111 == -1x+10011101~x 0 1 1 0 0 0 1 0-11111111150Примеры инверсии и увеличенияx = 15213x~x~x+1yДесятичное15213-15214-15213-15213Шестнадцатиричное3B 6DC4 92C4 93C4 93Двоичное00111011 0110110111000100 1001001011000100 1001001111000100 10010011x=00~0~0+1Десятичное0-10Шестнадцатиричное00 00FF FF00 00Двоичное00000000 0000000011111111 1111111100000000 0000000051Пример небезопасного кода №2¢Библиотека SUN XDR§ Широко применяется для межмашинного обмена даннымиvoid* copy_elements(void *ele_src[], int ele_cnt, size_t ele_size);ele_srcmalloc(ele_cnt * ele_size)52Код XDRvoid* copy_elements(void *ele_src[], int ele_cnt, size_t ele_size) {/** Занимаем буфер для ele_cnt объектов, каждый ele_size байт* и копируем с места указанного ele_src*/void *result = malloc(ele_cnt * ele_size);if (result == NULL)/* Ошибка malloc */return NULL;void *next = result;int i;for (i = 0; i < ele_cnt; i++) {/* Копирование объектов по назначению */memcpy(next, ele_src[i], ele_size);/* Перемещение указателя на следующую позицию в памяти */next += ele_size;}return result;}53Уязвимость XDRmalloc(ele_cnt * ele_size)¢Что если:§ ele_cnt§ ele_size§ Выделится¢= 220 + 1= 4096 = 212= ??Как сделать функцию безопасной?54Компилированный код умноженияФункция Cиint mul12(int x){return x*12;}Арифметические операциив результате компиляцииleal (%eax,%eax,2), %eaxsall $2, %eax¢Пояснениеt <- x+x*2return t << 2;Компилятор Cи автоматически создаёт код сдвига исложения при умножении на константу55Компилированный код делениябеззнаковогоФункция Cиunsigned udiv8(unsigned x){return x/8;}Арифметические операциив результате компиляцииshrl $3, %eax¢¢Пояснение# Логический сдвигreturn x >> 3;Для беззнаковых используется логический сдвигДля пользователей Явы§ Логический сдвиг пишется как >>>56Деление сдвигом знаковогона степень двойки¢Частное от деления знакового на степень двойки§ x >> k даёт ⎣x/2k⎦§ Использует арифметический сдвиг§ Округляет в неверном направлении при u < 0x/ k2Операнды:Полное частное:Результат:yy >> 1y >> 4y >> 8x / 2k⎣x / 2k⎦k•••Двоичная точка•••0•••0••••••0••••••ПолноеРезультатчастное-15213-15213-7606.5-7607-950.8125-951-59.4257813-600 1 0Шестн.C4E2FCFF934949C4•••0 0.•••Двоичный110001001110001011111100111111111001001101001001010010011100010057Правильное деление на степень двойки(1)¢Частное от деления знакового на степень двойки§ Необходимо ⎣x/2k⎦(Округление к 0)§ Вычисляется как ⎣(x+2k-1)/2k⎦В Cи: (x + (1<<k)-1) >> k§ Смещение делимого к 0§Вариант 1: Без округленияx 1Делимое: +2k –1x+2k –1/2kДелитель:⎡x / 2k ⎤0••••••1•••k0•••0 00 0 1•••1 11•••11•••0 00•••0 1 010•••1 1 1•••Двоичная точка.

1•••11Смещение не имеет эффекта58Правильное деление на степень двойки(2)Вариант 2: округлениеДелимое:x+k2 –1x+2k –1/Делитель:2k⎡x / 2k⎤10••••••1k0 0 1•••••••••1 1•••Увеличено на 10•••0 1 010•••1 1 1Двоичная точка•••0 0•••.•••Увеличено на 1Смещение добавляет 1 к результату59Компилированный код делениязнаковогоФункция Cиint idiv8(int x){return x/8;}Арифметические операциив результате компиляцииtestl %eax, %eaxjsL4L3:sarl $3, %eaxretL4:addl $7, %eaxjmp L3Поясненияif x < 0x += 7;# Арифметический сдвигreturn x >> 3;¢¢Арифметический сдвиг intДля пользователей Ява§ Арифм. сдвиг пишется как >>60Арифметика: основные правила(2)¢¢Беззнаковые и знаковые в доп.коде – изоморфные кольца:изоморфизм = преобразование типовСдвиг влево§ Беззнаковые: умножение на 2k§ Всегда логический сдвиг¢Сдвиг вправо§ Беззнаковые: логический сдвиг, деление на 2k с округлением к 0§ Знаковые: арифметический сдвигПоложительные: деление на 2k с округлением к 0§ Отрицательные: деление на 2k с округлением от 0используется смещение для исправления§61Свойства арифметики беззнаковых¢Умножение и сложение беззнаковых образуюткоммутативное кольцо§ Сложение – коммутативная группа§ Замкнутая относительно умножения§§§§0 ≤ UMultw(u , v) ≤ 2w –1Умножение – коммутативноUMultw(u , v) = UMultw(v , u)Умножение – ассоциативноUMultw(t, UMultw(u , v)) = UMultw(UMultw(t, u ), v)1 – нейтральный элемент умноженияUMultw(u , 1) = uУмножение дистрибутивно относительно сложенияUMultw(t, UAddw(u , v)) = UAddw(UMultw(t, u ), UMultw(t, v))62Свойства арифметики знаковых в доп.коде¢Изморфные алгебры§ Беззнаковые умножение и сложенияОкращаются до w§ Two’s complement multiplication and addition§ Truncating to w bits§¢Обе образуют кольца§ Изоморфные кольцу вычетов по модулю 2w¢Сравнение с арифметикой (математических) целых§ И там, и там – кольца§ Целые обладают свойствами упорядоченности, т.е.,u>0⇒ u+v>vu > 0, v > 0⇒ u·v>0§ Этими свойствами не обладают беззнаковые в доп.кодеTMax + 1== TMin15213 * 30426 == -10030(для 16-битных слов)63Чтение байт в обратном порядке¢Результат дизассемблирования§ Текстовое представление машинного кода§ Выдаётся программой читающей машинный код¢Пример фрагментаАдрес8048365:8048366:804836c:¢Машинный код5b81 c3 ab 12 00 0083 bb 28 00 00 00 00Представление на Ассемблереpop%ebxadd$0x12ab,%ebxcmpl$0x0,0x28(%ebx)«Расшифровка» значени駧§§Значение:Размещение в слове (32 бита):Разделение на байты:Переупорядочение:0x12ab0x000012ab00 00 12 abab 12 00 0064.

Характеристики

Список файлов лекций