ДЗ КМ-1: КМ-3. Низкоуровневые средства С++ для работы с памятью. Контрольная работа вариант 7

Работа выполнена полностью и зачтена преподавателем. Вариант 7

Методическое пособие к ЛР № 4 «Представление данных в памяти» по РПОСУ

Настоятельно рекомендуется после выполнения каждого пункта данной работы делать коммиты.

1. Функции print_in_*()

Разобьем задачу на более простые части.

Начнем с print_in_hex(). Байт — это 8 бит, то есть две цифры в шестнадцатеричной системе. Чтобы напечатать байт, нужно напечатать цифру, соответствующую его старшей и младшей половине (они называются nibble). Любой блок данных (по адресу в нетипизированном указателе void*) — это массив байт; нужно только указать компилятору рассмотреть void* как uint8_t*. Очевидно, чтобы напечатать массив байт, нужно напечатать каждый байт в цикле.

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

Итак, элементарные задачи:

1. Напечатать шестнадцатеричную цифру для значения от 0 до 15.
2. Извлечь из байта младший nibble как число от 0 до 15.
3. Извлечь из байта старший nibble как число от 0 до 15.
4. Напечатать байт в шестнадцатеричном виде как два nibble.
5. Преобразовать void* в uint8_t*.
6. Напечатать size элементов массива по адресу в uint8_t* (hex).
7. Напечатать байт в двоичном виде.
8. Напечатать size элементов массива по адресу в uint8_t* (binary).

1.1. Напечатать шестнадцатеричную цифру для значения от 0 до 15

Напишем вспомогательную функцию, которая будет представлять значение от 0 до 15 в шестнадцатеричном виде. Что она принимает? Целое число от 0 до 15, для этого достаточно uint8_t. Что она возвращает? Можно сразу печатать результат, тогда не нужно возвращать ничего (void). Но вспомним, что функции желательно делать максимально пригодными для повторного использования, и вовсе не всегда нужно печатать nibble не экране. Поэтому лучше возвращать символ для nibble, то есть char. Итого: char nibble_to_hex(uint8_t i);.

Как реализовать nibble_to_hex()? Очевидный вариант — через switch на 16 вариантов. Есть и более лаконичный вариант: заведем массив цифр char digits[] = "0123456789abcdef"; и будем для значения i возвращать digits[i]. На практике популярен еще один вариант - через коды символов. Вспомним, что символы в памяти хранятся как их коды, например, коды цифр от '0' до '9' — от 48 до 57, а коды букв от 'a' до 'f' — от 97 до 102. Таким образом, если i меньше 10, можно прибавить i к '0' и получить соответствующую цифру; если i больше, нужно прибавить к 'a' столько, на сколько i больше 10 (то есть для 10 — 0, для 11 — 1 и т. д.).

Важный момент — самопроверка. Чтобы проверить работу nibble_to_hex(), добавим в программу функцию-тест, вызываемую в начале main(), из 16 строк:

assert(nibble_to_hex(0x0) == '0');

assert(nibble_to_hex(0x1) == '1');

// ...

assert(nibble_to_hex(0xf) == 'f');

Еще один вопрос — реакция nibble_to_hex() на некорректные значения аргумента. Можно решить его путем защитного программирования: добавить в начало функции

assert(0x0 <= i && i <= 0xf);

1.2. Извлечь из байта младший nibble как число от 0 до 15

Задача сводится к тому, чтобы из восьми бит четыре младших оставить такими, как есть, а четыре старших обнулить. Типовое решение — наложить битовую маску. Битовая маска следующая: 0b00001111, или 0x0f, — в ней единицы стоят в тех позициях, биты в которых нужно извлечь. Логическое «И» (&) бита x с нулем дает 0, а с единицей - x, то есть byte & mask даст искомый младший nibble. Решение для математиков — взять остаток от деления байта на 32 (0b00010000).

1.3. Извлечь из байта старший nibble как число от 0 до 15

Можно разбить эту задачу еще на две: выделение старших разрядов байта и их перемещение (сдвиг) на позиции младших разрядов. Какая маска подойдет для выделения? Очевидно, 0b11110000 (0xf0). Сдвиг вправо на 4 разряда делается оператором >>: byte >> 4. По стандарту C++, старшие биты результата будут равны 0, поэтому на самом деле выделять старшие биты не нужно. Сдвиг вправо на 4 позиции математически равносилен делению на 2⁴, но при работе с битами сдвиг лучше выражает суть дела.

1.4. Напечатать байт как два nibble

Запишем в коде все предыдущие рассуждения:

void

print_in_hex(uint8_t byte) {

cout << nibble_to_hex(byte >> 4)

<< nibble_to_hex(byte & 0xf);

}

Для самопроверки следует попробовать напечатать байты 0x0, 0xab, 0xff.

1.5, 1.6. Преобразовать void* в uint8_t* и напечатать массив этих байт

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

const uint8_t* as_bytes(const void* data);

Здесь важны ключевые слова const. Они означают, что данные по адресу, хранимому в указателе, не могут быть изменены через этот указатель.

Считая, что она реализована, можно записать печать массива сразу:

void

print_in_hex(const void* data, size_t size) {

const uint8_t* bytes = as_bytes(data);

for (size_t i = 0; i < size; i++) {

print_in_hex(bytes[i]);

// Для удобства чтения: пробелы между байтам, по 16 байт на строку.

if ((i + 1) % 16 == 0) {

cout << 'n';

}

else {

cout << ' ';

}

}

}

Указание компилятору, что значение одного типа нужно трактовать как значение другого, называется приведением типов. Из лекций известно, что в данном случае корректна такая реализация:

const uint8_t*

as_bytes(const void* data) {

return reinterpret_cast(data);

}

Самопроверка: завести переменные типа uint8_t, uint16_t, uint32_t и дать им одно и то же значение, 0x42. Напечатать их через новую функцию и убедиться визуально, что единственным ненулевым байтом будет 0x42 в каждом случае, а всего байт будет столько, сколько ожидается. Вторым параметром следует передавать sizeof, например:

uint32_t u32 = 0x42;

cout << "u32 bytes: ";

print_in_hex(&u32, sizeof(u32));

cout << 'n';

1.7. Напечатать байт в двоичном виде

Известен способ перевода в двоичную систему путем взятия остатков от деления на два, однако, порядок остатком получается обратным порядку бит. В программе проще проверять биты, начиная со старшего, и печатать 0, если бит равен 0, и 1, если бит равен 1. Для выделения бита можно воспользоваться маской: старший бит выделяется как 0b10000000, или (0x1 << 7), младший — маской (0x1 << 0). После наложения маски с одним установленным битом в результате останется либо 0 (если соответствующий бит не установлен), либо не-ноль, если установлен. Выделим эту логику в функцию по аналогии с nibble_to_hex():

char

bit_digit(uint8_t byte, uint8_t bit) {

if (byte & (0x1 << bit)) {

return '1';

}

return '0';

}

Сдвиги на 7, 6, ..., 0 бит логично делать циклом. Итого:

void

print_in_binary(uint8_t byte) {

for (uint8_t bit = 7; bit > 0; bit--) {

cout << bit_digit(byte, shift);

}

}

Самопроверка: перевести в двоичное представление и напечатать числа из лекционного слайда про двоичные операции (исходные два числа и результаты всех действий).

1.8. Напечатать блок данных в двоичном виде

Очевидно, что приведение типов не отличается от случая для шестнадцатеричной системы. Напишем и проверим по аналогии с print_in_hex():

void

print_in_binary(const void* data, size_t size) {

const uint8_t* bytes = as_bytes(data);

for (size_t i = 0; i < size; i++) {

print_in_binary(bytes[i]);

// Для удобства чтения: пробелы между байтами, по 4 байта на строку.

if ((i + 1) % 4 == 0) {

cout << 'n';

}

else {

cout << ' ';

}

}

}

В двоичной системе 42 будет 0b00101010. Этот байт должен стоять первым при печати целого числа любой длины, а за ним — байты с нулями.

2. Битовый калькулятор

В отчет нужно занести код и результаты в отчет в виде текста.

Вопрос: почему 1025 (0b00000100'00000001, 0x0401) представлено байтами 01 04, а не наоборот?

Ответ: потому что на x86 (Intel) порядок байт от младшего к старшему (little-endian), то есть младший байт в памяти расположен первым.

3. Исследование представления и размещения данных в памяти

Комментарий к отчету по данному пункту ЛР.

• Необходим вывод программы — все, что нужно напечатать по заданию.
• В распечатанном массиве байт, которые занимает массив структур, нужно отметить, какие байты чему соответствуют (элементам массива, полям структуры).
• Необходима готовность отвечать (пользуясь отчетом), что представляет собой тот или иной участок распечатанного блока памяти, и почему его содержимое именно таково (кроме действительных чисел).

4. Работа со строками C

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

Вместо пошагового выполнения ЛР рассмотрим решение двух типовых задач: ввода и обработки строки C функциями стандартной библиотеки и загрузки текста из файла в строку C. Задание на ЛР представляет собой их комбинацию.

4.1. Ввод строки C и её обработка функциями стандартной библиотеки

Решим задачу: считать строку C и напечатать по отдельности слов в ней (слова разделены пробелами и знаками препинания).

Ввод строки C

Для определенности предположим, что длина строки не превышает некоторой заранее заданной, например, 255 символов. С учетом завершающего '' под строку нужно 256 символов:

const size_t MAX_SIZE = 256;

char text[MAX_SIZE];

Ввести с строку C можно функцией fgets(). Ознакомимся с документацией по ссылке. В документации обычно есть и примеры использования описываемых функций.

Прототип функции:

char* fgets(char* str, int count, std::FILE* stream);

Над прототипом написано: Defined in header — это значит, что для использования функции нужно включить заголовочный файл .

Под прототипом написано, что делает данная функция: считывает не более count - 1 символов и записывает их в массив, на который указывает str; чтение ведется из файлового потока stream.

Нам необходимо считывать строку со стандартного ввода, где взять файловый поток для него? В справочнике std::FILE является ссылкой на статью «C-style file input/output» («Файловый ввод-вывод средствами C»). В конце её в разделе Macros можно найти запись:

stdin expression of type FILE* associated with the input stream

То есть глобальная переменная stdin из и есть нужный поток.

Итак, вызов для чтения строки:

fgets(text, MAX_SIZE, stdin);

Заметим, что на практике, а не в учебных целях, удобнее считывать строки C++:

string text;

getline(cin, text);

Если затем нужен указатель на массив считанных символов, его можно получить как text.c_str() (менять символы с этом массиве нельзя; при необходимости есть метод text.data()).

Разбиение строки на слова

Чтобы напечатать слова строки по отдельности, нужно искать границы слов и печатать часть строки от начала до конца слова. Чтобы найти конец слова, нужно найти первый (от любой позиции внутри слова, в том числе от его начала) символ-разделитель. Разделители могут идти подряд. Вот пример текста:

News,from beyond the Narrow Sea. Haven't you heard?!

↑ ↑↑

нет пробела два пробела

Кроме знаков препинания, разделители включают также пробел и символы перевода строк:

const char* separators = " rn,.!?:;()-";

Функции стандартной библиотеки для работы со строками C — в заголовочном файле . Из обширного списка наиболее подходящими для задачи выглядят описания:

• strspn() — определяет, сколько первых символов строки подряд относятся к множеству, заданному другой строкой;
• strсspn() — определяет, сколько первых символов строки подряд не относятся к множеству, заданному другой строкой (например, сколько символов с начала строки — не разделители слов);

Алгоритм решения:

1. Определить, сколько разделителей находятся в начале строки — strspn().
2. Пропустить их (сместить указатель на начало строки).
3. Если достигнут конец строки (начальный символ — ''), закончить работу.
4. Найти первый разделитель от нового начала строки (или слова), то есть длину слова — strcspn().
5. Напечатать часть строки от начала слова до разделителя (это можно сделать методом cout.write() или функцией fwrite()). Также напечатать символ перевода строки.
6. Сдвинуть начало строки вперед на длину слова.
7. Перейти к пункту 1.

Почти каждый шаг алгоритма — всего одна строка или конструкция. Начало строки (то есть еще не разобранной части) будем хранить в переменной:

const char* start = text;

Алгоритм представляет собой цикл:

while (true) {

1. Определить, сколько разделителей находятся в начале строки:

const size_t separator_count = strspn(start, separators);

2. Пропустить их:

start += separator_count;

3. Если достигнут конец строки, закончить работу.

1. if (start[0] == '') {
2. break;

}

6. Найти первый разделитель от нового начала строки:

const size_t word_length = strcspn(start, separators);

7. Напечатать часть строки от начала слова до разделителя:

cout.write(start, word_length);

Также напечатать символ перевода строки:

cout << 'n';

6. Сдвинуть начало строки вперед на длину слова:

start += word_length;

}

Соединив участки кода в полноценную программу, можно убедиться, что она работает правильно:

echo "News,from beyond the Narrow Sea. Haven't you heard?" | lab04.exe

Вывод:

News

from

beyond

the

Narrow

Sea

Haven't

you

heard