ДСв19_07-машинный-уровень-4-Данные (1238941)

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

Текст из файла

Машинный уровень 4: ДанныеОсновы информатикиКомпьютерные основы программированияu.to/DbCmFAНа основе CMU 15-213/18-243:Introduction to Computer Systemsu.to/XoKmFAЛекция 7, 05 апреля, 2019Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Ещё машинный уровеньУправление и сложные данные¢Массивы§ Одномерные§ Многомерные (массивы массивов)§ Многоуровневые¢Структуры§ Размещение§ Доступ§ Выравнивание¢¢¢ОбъединенияРаспределение памятиО переполнении буфера2Размещение массивов¢Основные принципыT A[L];§ Массив данных типа T и длинны L§ Вплотную занятый фрагмент длиной L * sizeof(T) байтchar string[12];xx + 12int val[5];xx+4x+8x + 12x + 16x + 20double a[3];xx+8xx+8x + 16x + 24char *p[3];x + 16x + 243Доступ к массиву¢Основные принципыT A[L];§ Массив данных типа T и длиной L§ Идентификатор A можно использовать как указатель на элемент синдексом 0: Type T*1int val[5];x¢5x+42x+8ОбращениеТипЗначениеval[4]valval+1&val[2]val[5]*(val+1)val + iintintintintintintint3xx+4x+8??5x+4i****1x + 123x + 16x + 204Пример массива#define ZLEN 5typedef int zip_dig[ZLEN];zip_dig cmu = { 1, 5, 2, 1, 3 };zip_dig mit = { 0, 2, 1, 3, 9 };zip_dig ucb = { 9, 4, 7, 2, 0 };1zip_dig cmu;16200zip_dig mit;3656¢2242409zip_dig ucb;¢5281444601323487643952268365607276Объявление zip_dig cmu эквивалентно int cmu[5]Память занимается блоками по 20 байт вплотную?§ Выполнение в общем случае не гарантируется!5Пример доступа к массиву1zip_dig cmu;16520224128int get_digit(zip_dig z, int digit){return z[digit];}x86-64# %rdi = z# %rsi = digitmovl (%rdi,%rsi,4), %eax332nn# z[digit]36В %rdi - начальныйадрес массиваВ %rsi - индекс массиваnЦелевой адрес4*%rdi + %rsinОбращение к памяти(%rdi,%rsi,4)6Пример цикла с массивомvoid zincr(zip_dig z) {size_t i;for (i = 0; i < ZLEN; i++)z[i]++;}# %rdi = zmovl$0,jmp.L3.L4:addl$1,addq$1,.L3:cmpq$4,jbe.L4rep; ret%eax#i = 0#goto middle# loop:(%rdi,%rax,4) #z[i]++%rax#i++# middle%rax#i:4#if <=, goto loop7Многомерные массивы массивов¢ОбъявлениеA[0][0]T A[R][C];§ 2D массив данных типа T§ R строк, C столбцов§ Элемент типа T длиной K байт¢Размер массива•••• • •A[0][C-1]•••A[R-1][0] • • • A[R-1][C-1]§ R * C * K байт¢Организация§ Построчное упорядочениеint A[R][C];A[0][0]AA• • • [0] [1][C-1] [0]A• • • [1][C-1]•••AA[R-1] • • • [R-1][0][C-1]4*R*C байт8Пример массива массивов#define PCOUNT 4zip_dig pgh[PCOUNT] ={{1, 5, 2, 0, 6},{1, 5, 2, 1, 3 },{1, 5, 2, 1, 7 },{1, 5, 2, 2, 1 }};zip_digpgh[4];1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 176¢96116136156zip_dig pgh[4] эквивалентно int pgh[4][5]§ Переменная pgh: массив из 4 эл-тов, размещённых вплотную§ Каждый эт-т массив из 5 int-ов, размещённых вплотную¢Гарантируется построчное размещение9Доступ к строке массива массивов¢Строки, составляющие массив§ A[i] – массив из C элементов§ Каждый элемент типа T длиной K байт§ Начальный адрес A + i * (C * K)int A[R][C];A[0]A[0][0]A•••A[i]A[0][C-1]• • •A[i][0]•••A+(i*C*4)A[R-1]A[i][C-1]• • •A[R-1][0]•••A[R-1][C-1]A+((R-1)*C*4)10Доступ к элементам массива массивов¢Элементы массива§ A[i][j] элементы типа T , длиной K bytes§ Адрес A + i * (C * K) + j * K = A + (i * C + j)* Kint A[R][C];A[0]A[0][0]A•••A[i]A[0][C-1]• • ••••A[i][j]A[R-1]•••• • •A+(i*C*4)A+(i*C*4)+(j*4)A[R-1][0]•••A[R-1][C-1]A+((R-1)*C*4)11Пример многоуровневого массива¢zip_dig cmu = { 1, 5, 2, 1, 3 };zip_dig mit = { 0, 2, 1, 3, 9 };zip_dig ucb = { 9, 4, 7, 2, 0 };¢#define UCOUNT 3int *univ[UCOUNT] = {mit, cmu, ucb};cmuuniv160361681617856mit1165200ucb 36224240956¢128144460Переменная univ - массивиз 3-х эл-товКаждый эл-т – указатель§ 8 байтКаждый указывает намассив int-ов32348764395226836560727612Доступ к элементам многоуровневогомассиваint get_univ_digit(size_t index, size_t digit){return univ[index][digit];}salqaddqmovlret¢$2, %rsi# 4*digituniv(,%rdi,8), %rsi # p = univ[index] + 4*digit(%rsi), %eax# return *pВычисления§ Доступ к элементу Mem[Mem[univ+8*index]+4*digit]§ Необходимы два обращения к памятиПервое даёт указатель на массив-строку§ Следующее доступается к элементу в массиве§13Обращения к элементам массивовМногоуровневый массивМассив массивовint get_pgh_digitint get_univ_digit(size_t index, size_t digit)(size_t index, size_t digit){{return pgh[index][digit];return univ[index][digit];}}Обращения выглядят одинаково в Cи,но вычисление адресов различается:Mem[pgh+20*index+4*dig]Mem[Mem[univ+4*index]+4*dig]14Кодматрицы N x N¢Фиксированныеразмеры§ Значение N известно прикомпиляции¢Переменные размеры,явное индексирование§ Традиционный способреализации динамическихмассивов¢Переменные размеры,неявноеиндексирование§ Поддерживается gcc#define N 16typedef int fix_matrix[N][N];/* Получить элемент a[i][j] */int fix_ele(fix_matrix a,size_t i, size_t j){return a[i][j];}#define IDX(n, i, j) ((i)*(n)+(j))/* Получить элемент a[i][j] */int vec_ele(size_t n, int *a,size_t i, size_t j){return a[IDX(n,i,j)];}/* Получить элемент a[i][j] */int var_ele(size_t n, int a[n][n],size_t i, size_t j) {return a[i][j];}15Доступ к матрице 16 x 16¢Элементы массива§ Адрес A + i * (C * K) + j * K§ C = 16, K = 4/* Получить элемент a[i][j] */int fix_ele(fix_matrix a, size_t i, size_t j) {return a[i][j];}# a in %rdi, i in %rsi, j insalq$6, %rsiaddq%rsi, %rdimovl(%rdi,%rdx,4), %eaxret%rdx# 64*i# a + 64*i# M[a + 64*i + 4*j]16Доступ к матрице n X n¢Элементы массива§ Адрес A + i * (C * K) + j * K§ C = n, K = 4§ Необходимо целочисленное умножение/* Получить элемент a[i][j] */int var_ele(size_t n, int a[n][n], size_t i, size_t j){return a[i][j];}# n in %rdi, a in %rsi, i inimulq%rdx, %rdileaq(%rsi,%rdi,4), %raxmovl(%rax,%rcx,4), %eaxret%rdx, j in %rcx# n*i# a + 4*n*i# a + 4*n*i + 4*j17Ещё машинный уровеньУправление и сложные данные¢Массивы§ Одномерные§ Многомерные (массивы массивов)§ Многоуровневые¢Структуры§ Размещение§ Доступ§ Выравнивание¢¢¢ОбъединенияРаспределение памятиО переполнении буфера18Размещение структурыstruct rec {int a[4];size_t i;struct rec *next;};¢ra0i16next2432Структура представляется участком памяти§ Достаточно большим для размещения всех полей¢Поля размещены в порядке объявления§ Даже если иной порядок даст более плотное размещение¢Компилятор определяет общий размер и размещение полей§ Машинный код не имеет представления о структурах исходного кода19Создание указателя на поле структурыstruct rec {int a[4];size_t i;struct rec *next;};¢Создание указателя наполе структуры§ Сдвиг каждого поля отначала структурывычисляется прикомпиляции§ Считается как r + 4*idxrr+4*idxa0i16next2432int *get_ap(struct rec *r, size_t idx){return &r->a[idx];}# r in %rdi, idx in %rsileaq (%rdi,%rsi,4), %raxret20struct rec {int a[3];int i;struct rec *next;};Проход связного списка¢Код Сиrvoid set_val(struct rec *r, int val){while (r) {int i = r->i;r->a[i] = val;r = r->next;}}.L11:movslqmovlmovqtestqjneai160next2432Элемент iРегистрЗначение%rdir%rsival# loop:16(%rdi), %rax#i = M[r+16]%esi, (%rdi,%rax,4) #M[r+4*i] = val24(%rdi), %rdi#r = M[r+24]%rdi, %rdi#Проверка r.L11#if !=0 goto loop21Структуры и выравниваниеДанные без выравнивания¢ci[0]p p+1i[1]p+5vp+9p+17struct S1 {char c;int i[2];double v;} *p;Данные с выравниванием¢§ Если простой тип данных - длиной K байт§ То адреса должны быть кратны Kc 3 байтаp+0i[0]p+4Кратно 4Кратно 8i[1]p+8v4 байтаp+16p+24Кратно 8Кратно 822Принципы выравнивания¢Выровненные данные§ Если простой тип данных - длиной K байт,…§ …то адрес должен быть кратен K§ Обязательно на некоторых машинах, рекомендовано на x86-64¢Зачем выравнивать данные§ Доступ в память производится выровненными фрагментами по 4или 8 байт (в зависимости от системы)§ Неэффективно обращение к элементу данных, пересекающемуграницу четверного слова§ Работа виртуальной памяти резко усложняется для элементаданных находящегося в 2-х страницах¢Компилятор§ Для правильного выравнивания полей добавляет в структуру зазоры23Варианты выравнивания (x86-64)¢1 байт: char, …§ Любой адрес¢2 байта: short, …§ 1 младший бит адреса должен быть нулевым 02¢4 байта: int, float, …§ 2 младших бита адреса должны быть нулевыми 002¢8 байт: double, long, char *, …§ 2 младших бита адреса должны быть нулевыми 0002¢16 байт: long double (GCC on Linux)§ 2 младших бита адреса должны быть нулевыми 0000224Выравнивание структур¢Внутри структуры:§ Выравнивается каждое поле¢Размещение всей структуры§ Структура выравнивается на границу K байтstruct S1 {char c;int i[2];double v;} *p;K = крупнейшее выравнивание среди всех полей§ Начальный адрес и размер структуры должны быть кратны K§¢Пример:§ K = 8, из-за поля doublec 3 байтаp+0i[0]p+4кратно 4кратно 8i[1]p+8v4 байтаp+16p+24кратно 8кратно 825Выравнивание всей структуры¢¢Для крупнейшего выравнивания KРазмер всей структуры кратен Kvp+0i[0]p+8i[1]struct S2 {double v;int i[2];char c;} *p;c7 байтp+16p+24кратно K=826Массив структур¢¢struct S2 {double v;int i[2];char c;} a[10];Размер всей структурыкратен KВыравнивается каждыйэлемент массиваa[0]a+0a[1]a+24va+24i[0]a+32• • •a[2]a+48i[1]a+72ca+407 байтa+4827Доступ к элементам массиваВычислить сдвиг в массиве 12*idx¢struct S3 {short i;float v;short j;} a[10];§ sizeof(S3), включая заполнители выравниванияПоле j сдвинуто на 8 от начала структурыАссемблер даст сдвиг a+8¢¢§ Выполняется при редактировании связей (линковке)• • •a[0]a+0a+12ia+12*idxshort get_j(int idx){return a[idx].j;}a[idx]• • •a+12*idx2 байтаvj2 байтаa+12*idx+8# %rdi = idxleaq (%rdi,%rdi,2),%rax # 3*idxmovzwl a+8(,%rax,4),%eax28Экономия пространства¢Поместим вначале длинные данныеstruct S5 {int i;char c;char d;} *p;struct S4 {char c;int i;char d;} *p;¢Результат (K=4)c 3 байтаiic dd 3 байта2 байта29Ещё машинный уровеньУправление и сложные данные¢Массивы§ Одномерные§ Многомерные (массивы массивов)§ Многоуровневые¢Структуры§ Размещение§ Доступ§ Выравнивание¢¢¢ОбъединенияРаспределение памятиО переполнении буфера30Размещение объединений¢Размещается как наибольший элементunion U1 {char c;int i[2];double v;} *up;ci[0]vup+0struct S1 {char c;int i[2];double v;} *sp;csp+03 байтаsp+4i[1]i[0]i[1]sp+8up+44 байтаsp+16up+8vsp+2431Доступ к битовым наборамtypedef union {float f;unsigned u;} bit_float_t;uf04float bit2float(unsigned u){bit_float_t arg;arg.u = u;return arg.f;}unsigned float2bit(float f){bit_float_t arg;arg.f = f;return arg.u;}Совпадает с (float)u ?Совпадает с (unsigned)f ?32Сводка¢Массивы в C觧§§¢Размещение в памяти вплотнуюУдовлетворяют требованиям по выравниваниюУказатель на первый элементГраницы не контролируютсяСтруктуры§ Размещает байты в запрошенном порядке§ Зазоры в середине и конце для выравнивания¢Объединения§ Поля наложены друг на друга§ Способ обойти систему контроля типов33Ещё машинный уровеньУправление и сложные данные¢Массивы§ Одномерные§ Многомерные (массивы массивов)§ Многоуровневые¢Структуры§ Размещение§ Доступ§ Выравнивание¢¢¢ОбъединенияРаспределение памятиО переполнении буфера34Распределение памятиНе в масштабеx86-64 Linux00007FFFFFFFFFFFStack¢Stack (стек)8MB§ Стек времени исполнения (макс.

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

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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