Это не задание, это «прохождение» первой половины ЛР № 4 и вспомогательные материалы ко второй половине. Фрагменты кода могут содержать ошибки (не специально).
print_in_*() (под руководством)Разобьем задачу на более простые части.
Начнем с print_in_hex(). Байт — это 8 бит, то есть две цифры
в шестнадцатеричной системе. Чтобы напечатать байт, нужно напечатать цифру,
соответствующую его старшей и младшей половине (они называются nibble).
Любой блок данных (по адресу в нетипизированном указателе void*) — это массив
байт; нужно только указать компилятору рассмотреть void* как uint8_t*.
Очевидно, чтобы напечатать массив байт, нужно напечатать каждый байт в цикле.
Перевод байта в двоичную запись можно делать целиком, дробить байт нет смысла. Печать массива байт в двоичном виде по сути не отличается от печати их в шестнадцатеричной системе счисления.
Итак, элементарные задачи:
void* в uint8_t*.size элементов массива по адресу в uint8_t* (hex).size элементов массива по адресу в uint8_t* (binary).Напишем вспомогательную функцию, которая будет представлять значение от 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 и т. д.).
Важный момент — самопроверка. В стандартном заголовочном файле <cassert>
есть полезный макрос assert(). Если передать в assert() выражение,
и оно окажется ложным, программа аварийно завершится, и будет напечатано
это выражение. Если же оно истинно, ничего сделано не будет. Чтобы проверить
работу 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(), добавив assert(0x0 <= i && i <= 0xf)
в начало функции.
На этом шаге каждый должен реализовать тот вариант, который приглянулся, и проверить его работу.
Задача сводится к тому, чтобы из восьми бит четыре младших оставить такими,
как есть, а четыре старших обнулить. Типовое решение — наложить битовую маску.
Битовая маска следующая: 0b00001111, или 0x0f, — в ней единицы стоят в тех
позициях, биты в которых нужно извлечь. Логическое «И» (&) бита x с нулем
дает 0, а с единицей - x, то есть byte & mask даст искомый младший nibble.
Решение для математиков — взять остаток от деления байта на 32 (0b00010000).
Можно разбить эту задачу еще на две: выделение старших разрядов байта и их
перемещение (сдвиг) на позиции младших разрядов. Какая маска подойдет
для выделения? Очевидно, 0xf0 (0b11110000). Сдвиг вправо на 4 разряда
делается оператором >>: byte >> 4. По стандарту C++, старшие биты
результата будут равны 0, поэтому на самом деле выделять старшие биты
не нужно. Сдвиг вправо на 4 позиции математически равносилен делению
на 2⁴, но при работе с битами сдвиг лучше выражает суть дела.
На этом шаге каждый должен реализовать print_in_hex() для байта:
void
print_in_hex(uint8_t byte) {
cout << nibble_to_hex(byte >> 4)
<< nibble_to_hex(byte & 0xf);
}
Для самопроверки следует попробовать напечатать байты 0x0, 0xab, 0xff.
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<const uint8_t*>(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';
Известен способ перевода в двоичную систему путем взятия остатков от деления
на два, однако, порядок остатком получается обратным порядку бит. В программе
проще проверять биты, начиная со старшего, и печатать 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);
}
}
На этом шаге каждый должен перенести код в свою программу. Самопроверка: перевести в двоичное представление и напечатать числа из лекционного слайда про двоичные операции (исходные два числа и результаты всех действий).
Очевидно, что приведение типов не отличается от случая для шестнадцатеричной
системы. Каждый должен написать и проверить по аналогии с 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 << ' ';
}
}
}
После выполнения у каждого контролируются результаты.
В двоичной системе 0x42 будет 0b00101010. Этот байт должен стоять первым
при печати целого числа любой длины, а за ним — байты с нулями.
На этом шаге каждый должен выполнить пункт 2 задания на ЛР № 4 с сайта, продемонстрировать корректную работу программы и занести код и результаты в отчет в виде текста.
Вопрос: почему 1025 (0b00000100'00000001, 0x0401) представлено байтами
01 04, а не наоборот?
Ответ: потому что на x86 (Intel) порядок байт от младшего к старшему (little-endian), то есть младший байт в памяти расположен первым.
Решим задачу: считать содержимое текстового файла целиком в память, затем разбить его на строки, причем пустые строки не учитывать, наконец, освободить всю выделенную в процессе память.
Укрупненный алгоритм таков:
На данном этапе имеет смысл решить, какие ресурсы будет использовать программа (подо что нужно выделять участки памяти), и какие части программы будут управлять ими (выделять и освобождать).
Область памяти под текст файла должна выделяться перед тем, как в нее будут занесены данные, а освобождаться не раньше, чем текст будет разбит на строки, то есть уже не в той части, где ведется работа с файлом.
Под каждую строку нужен отдельный участок памяти, который затем нужно будет освободить, то есть сохранять указатель на него. Количество таких указателей заранее неизвестно, поэтому под них нужен динамический массив — еще один участок памяти. Его нужно будет освободить после освобождения всех участков под строки.
Чтобы упростить программу, а также для разнообразия, выделим отдельно подсчет непустых строк и отдельно — деление текста на них. Тогда можно выделять массив указателей на строки сразу после их подсчета и передавать указатель на эту область памяти в функцию, которая разделит текст на строки.
Вот как может выглядеть программа, если изолировать оговоренные части в функции:
auto text = load_file(path);
auto line_count = count_nonempty_lines(text);
auto lines = allocate_lines(line_count);
to_lines(text, lines);
deallocate(text, lines);
Вместо всех типов использовано auto, но стоит выбрать их прямо сейчас,
чтобы получить прототип программы, который будет хотя бы просто компилироваться.
Исходными данными для загрузки текста является путь к файлу, результатом -
указатель на загруженные в память символы, изменять ничего не нужно:
const char* load_file(const char* path);.
Функция подсчета непустых строк принимает текст, который не изменяет,
а возвращает количество: size_t count_nonempty_lines(const char* text);.
Каждое предложение — это цепочка символов, char*. Массив предложений —
это область памяти с началами цепочек, то есть массив char*,
то есть char**, который нужно выделить, зная его длину:
char** allocale_lines(size_t line_count);.
Функция деления текста на строки не изменяет текст, а также принимает
массив указателей, содержимое которого меняет, поэтому const не нужно:
void to_lines(const char* text, char** lines);.
При освобождении памяти нужно работать с переменными, тип которых нами
уже определен: void deallocate(const char* text, const char* lines);.
Функции этой не нужно изменять содержимое массивов, нужны только их адреса.
На этом шаге каждый должен перенести к себе прототип программы и убедиться, что он компилируется:
main(), заменив auto на конкретные типы;nullptr.Чтобы считать содержимое файла в память, необходимо:
В случае невозможности загрузки будем возвращать нулевой указатель. Итак,
const char*
load_file(const char* path) {
В стандартной библиотеке C++ имеется класс ifstream (файл <fstream>)
для чтения файлов. Путь к файлу передается в конструктор при создании объекта.
Ниже объявляется переменная input класса ifstream, которая соответствует
открытому для чтения файлу по пути path:
ifstream input(path);
Объекты ifstream (как и другие потоки) имеет метод bad(), который возвращает
false после ошибок, в том числе при невозможности открыть файл. Им можно
воспользоваться для проверки:
if (input.bad()) {
return nullptr;
}
Поток файлового ввода позволяет перемещаться по файлу, то есть продолжить чтение с произвольной позиции в файле. Позиция может быть указана с начала файла, с конца файла или относительно текущей, которая может быть получена. Тогда определить размер файла можно, переместившись в конец и узнав текущую позицию:
input.seekg(ios::end, 0);
auto size = input.tellg();
Для дальнейшей работы нужно переместиться обратно в начало файла:
input.seekg(ios::beg, 0);
Выделение памяти производится оператором new. Какой объем памяти необходим
под строки C с текстом файла длиной size? Строки C, помимо полезных символов,
включают также и завершающий '\0', значит, нужно (size + 1) элементов:
char* data = new char[size + 1];
У ifstream есть метод для считывания заданного количества байт в область
памяти:
input.read(data, size);
Завершающий '\0' — это особенность C, в файле этого символа нет, поэтому его
нужно записать в массив самостоятельно:
data[size] = 0;
Работа с файлом закончена. Можно закрыть его методом close() в ifstream,
но нет необходимости: он будет вызван в деструкторе объекта input, поэтому
можно просто завершить функцию:
return data;
}
Самопроверка: записать полностью функцию load_file() и проверить
её работу, напечатав текст после его считывания. Путь к файлу можно вводить
и через std::string, чтобы преобразовать её к const char*, нужен метод
c_str().
В начале файла могут быть пустые строки, очевидно, их нужно пропустить, то есть,
взяв указатель на начало текста, получить другой указатель — на начало первой
не пустой строки. Пустые строки — это непрерывная последовательность символов
'\n'. Если таких строк нет, пусть это будет указатель на конец текста,
то есть на его завершающий '\0'. Далее необходимо найти конец строки,
то есть указатель на первый встреченный в ней символ '\n'. Если после этого
пропустить все пустые строки, мы вернемся к тому же состоянию, что и перед
началом очередной строки, то есть выделение не пустой строки можно выполнять
циклически. Итого, алгоритм:
Если считать, что уже реализована функция пропуска пустых строк
const char* skip_empty_lines(const char* text) и функция поиска конца строки
const char* find_line_end(const char* text), реализация может быть такой:
size_t
count_nonempty_lines(const char* text) {
size_t count = 0;
const char* line_start = skip_empty_lines(text);
while (*line_start != '\0') {
count++;
const char* line_end = find_line_end(line_start);
line_start = skip_empty_lines(line_end);
}
return count;
}
Для поиска конца строки нужно проверять символ за символом, пока очередной
не окажется '\n' или завершающим '\0'. В любом случае нужно вернуть
адрес того символа, до которого дошел поиск:
const char*
find_line_end(const char* text) {
size_t i = 0;
while (text[i] != '\0' && text[i] != '\n') {
i++;
}
return &text[i];
}
Пропуск пустых строк, то есть подряд идущих символов '\n', тривиален:
const char*
skip_empty_lines(const char* text) {
size_t i = 0;
while (text[i] == '\n') {
i++;
}
return &text[i];
}
Отдельной проверки на окончание строки не требуется, потому что '\0' != '\n',
и цикл прервется автоматически.
Выделение памяти делается оператором new. Функция allocate_lines() носит
практически декоративный характер:
char**
allocate_lines(size_t line_count) {
return new char* [line_count];
}
Результат — адрес области памяти с указателями, то есть еще потребуется выделять блоки под сами строки, указатели на которые и будут сохраняться в динамическом массиве.
Разделение текста на предложения похоже на их подсчет, но вместо простого увеличения счетчика нужно выделять память под предложение и копировать в нее часть текста.
void
to_lines(const char* text, char** lines) {
size_t count = 0;
const char* line_start = skip_empty_lines(text);
while (*line_start != '\0') {
const char* line_end = find_line_end(line_start);
const size_t line_length = line_end - line_start;
lines[count] = new char[line_length + 1];
strncpy(lines[count], line_start, line_length);
count++;
line_start = skip_empty_lines(line_end);
}
return count;
}
Необходимо освободить в функции deallocate():
Текст, загруженный из файла:
delete[] text;
Каждую из строк, скопированных из текста.
for (size_t i = 0; i < line_count; i++) {
delete[] lines[i];
}
Массив указателей на строки (уже освобожденные):
delete[] lines;
Необходимое значение line_count нужно добавить в параметры функции
и передавать из main(); также вместо deallocate() вписать её код
в конец main().
На этом шаге каждый должен завершить программу и проверить её работу, добавив после разбиения текста на строки их печать:
for (size_t i = 0; i < line_count; i++) {
cout << lines[i] << '\n';
}
Необходимо разбивать текст не на строки, а на предложения — участки текста,
ограниченные '.', '!' или '?' (возможно, подряд: "...", "?!").
Затем необходимо подсчитать количество слов в каждом предложении;
слова разделяются одним или несколькими пробелами или запятыми.
Например, вот два предложения, из шести и трех слов:
News,from beyond the Narrow Sea. Haven't you heard?!
↑ ↑↑
нет пробела два пробела
Наконец, требуется напечатать предложения в порядке убывания количества слов.
В конце программы все выделенная память должна освобождаться через delete[].
По сути, нужно обобщить уже реализованные функции, чтобы они могли делить текст не только по символу конца строки, а по любому символу из набора (который можно представить как строку C):
const char* find_any(const char* text, const char* what_to_find);
const char* skip_any(const char* text, const char* what_to_skip);
На самом деле, похожие функции уже есть в стандартной библиотеке:
strpbrk() и strspn() из <cstring>. Можно воспользоваться ими.
Функция для подсчета частей текста (ранее строк, теперь — между разделителями) понадобится и чтобы выделить предложения, и чтобы подсчитать слова в них:
size_t count_parts(const char* text, const char* delimiters);
Функция деления текста останется почти неизменной, только добавится параметр для указания разделителей:
void split(const char* text, const char* delimiters, char** parts);
Каждый должен продемонстрировать код и работу итоговой программы и занести это в отчет в виде текста.
При наличии времени имеет смысл пройтись по вопросам защиты ЛР № 4, по крайней мере, кто не будет знать, что делать, может заняться этим.
Козлюк Д. А. для кафедры Управления и информатики НИУ «МЭИ», 2016 г.