Системное программное обеспечение вычислительных машин

http://

алгоритм архиватор программа

Целью курсового проекта является разработка собственного алгоритма сжатия и восстановления данных, то есть «Архиватор».

Актуальность темы

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

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

Характеристики архиваторов:

1. По степени сжатия;

2. По скорости сжатия.

Эти характеристики — обратно зависимые величины. То есть, чем больше скорость сжатия, тем меньше степень сжатия, и наоборот.

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

На данный момент существует масса архиваторов и компрессоров, которые осуществляют сжатие и восстановление данных:

1. Свободные и открытые (7-Zip, Ark, File, Roller, FreeArc, Info-ZIP, KGB, Archiver, PeaZip, The Unarchiver, Xarchiver);

2. Бесплатные (DGCA, Filzip, GCA, HaoZip, IZArc, QuickZip, StuffIt Expander, TUGZip, Universal Extractor, WinUHA, Zipeg, ZipGenius, ZipItFree);

3. Коммерческие (ALZip, Archive Utility, MacBinary, PowerArchiver, Squeez, StuffIt, WinAce, WinRAR, WinRK, WinZip);

4. Командная строка (ARC, ARJ, bzip2, compress, gzip, Info-ZIP, JAR, LHA, lzip, lzop, PAQ, PKZIP, RAR, SBC, UPX).

Для достижения цели, поставленной в курсовом проекте, необходимо решение следующих задач:

? выполнить постановку задачи и описать функции сжатия и восстановления;

? сделать выбор среды разработки, а также привести обоснование этого выбора;

? провести тестирование созданной программы;

1. АНАЛИЗ ИСХОДНЫХ ДАННЫХ

Архиватор будет реализован с использованием возможностей языка C++. C++ — компилируемый статически типизированный язык программирования общего назначения.

Поддерживает такие парадигмы программирования как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование. Обеспечивает модульность, раздельную компиляцию, обработку исключений, абстракцию данных, объявление типов объектов, виртуальные функции. Стандартная библиотека включает, в том числе, общеупотребительные контейнеры и алгоритмы. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником — языком C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. 1]

C++ широко используется для разработки программного обеспечения. Он является одним из самых популярных языков программирования. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (игр). Существует множество реализаций языка C++, как бесплатных, так и коммерческих и для различных платформ. Например, на платформе x86 это GCC, Visual C++, Intel C++ Compiler, Embarcadero (Borland) C++ Builder и другие. C++ оказал огромное влияние на другие языки программирования, в первую очередь на Java и C#. Синтаксис C++ унаследован от языка C. Одним из принципов разработки было сохранение совместимости с C. Тем не менее, C++ не является в строгом смысле надмножеством C; множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико, но не включает все возможные программы на C. 2]

Реализовывать моё приложение я буду с помощью платформы Visual C++. Microsoft Visual C++ (MSVC) — интегрированная среда разработки приложений на языке C++, разработанная фирмой Microsoft и поставляемая либо как часть комплекта Microsoft Visual Studio, либо отдельно в виде бесплатного функционально ограниченного комплекта Visual C++ Express Edition. Сменила интегрированную среду разработки Microsoft QuickC. Visual C++ поддерживает перечень приложений как на Managed C++ и C++/CLI, так и на обычном C++, и тем самым позволяет генерировать код как для платформы .NET Framework, так и для исполнения в среде «чистой» Windows. В этом отношении Visual C++ является уникальным среди других языковых средств, предоставляемых средой Visual Studio, поскольку ни Visual Basic .NET, ни Visual J# не способны генерировать код для чистого Win32, в отличие от предыдущих версий (Visual Basic и Visual J++ соответственно).

Так как я работаю как на операционной системе Linux (дистрибутив Ubuntu 14.04 LTS), так и на Windows 7, то мой алгоритм будет работать на этих ОС.

Microsoft Windows — семейство проприетарных операционных систем корпорации Microsoft, ориентированных на применение графического интерфейса при управлении. Изначально Windows была всего лишь графической надстройкой для MS-DOS. По состоянию на август 2014 года под управлением операционных систем семейства Windows (по данным ресурса NetMarketShare (Net Applications)) работает более 91% персональных компьютеров. Windows работает на платформах x86, x86−64, IA-64 и ARM. Существовали также версии для DEC Alpha, MIPS, PowerPC и SPARC.

Windows 7 — пользовательская операционная система семейства Windows NT, следующая по времени выхода за Windows Vista и предшествующая Windows 8. Операционная система поступила в продажу 22 октября 2009 года — меньше, чем через три года после выпуска предыдущей операционной системы, Windows Vista. Партнёрам и клиентам, обладающим лицензией Volume Licensing, доступ к RTM был предоставлен 24 июля 2009 года. В интернете оригинальные установочные образы финальной версии системы были доступны с 21 июля 2009 года.

По данным веб-аналитики от W3Schools, на апрель 2015 года доля Windows 7 среди используемых в мире операционных систем для доступа к сети Интернет составила 52,1%. По этому критерию она находится на первом месте, превзойдя в августе 2011 предыдущего лидера — Windows XP. В Windows 7 реализована более гибкая настройка User Account Control (UAC), которая в отличие от Windows Vista имеет ещё два промежуточных состояния — «Уведомлять, только при попытках программ внести изменения в компьютер» (положение по умолчанию), «Уведомлять, только при попытках программ внести изменения в компьютер (не затемнять рабочий стол)».

Внесены изменения в технологию шифрования BitLocker и добавлена функция шифрования съёмных носителей BitLocker to go, позволяющая шифровать съёмные носители, причём даже при отсутствии модуля TPM. Добавлена возможность защиты данных на USB-накопителях с помощью Enhanced Storage. Улучшения коснулись и брандмауэра Windows: вернулась функция уведомления пользователя о блокировке программы, которая пытается получить доступ к сети.

С помощью групповой политики и функции AppLocker можно запретить запуск определенных приложений. Функция DirectAccess позволяет устанавливать безопасное соединение с сервером в фоновом режиме, в отличие от VPN, которому требуется участие пользователя. Также DirectAccess может применять групповые политики до входа пользователя в систему. Из состава Windows 7 были исключены приложения, разработанные для Windows Vista: Inkball, DreamScene, Ultimate Extras, приложения, имеющие аналоги в Windows Live (Почта Windows, Календарь Windows и пр.), технология Microsoft Agent, Windows Meeting Space. Из меню «Пуск» исчезла возможность вернуться к классическому меню (но если установить Classic Shell, то можно к нему вернуться), а также автоматическая пристыковка браузера и клиента электронной почты.

Linux, также Лиинукс — общее название Unix-подобных операционных систем, основанных на одноимённом ядре. Ядро Linux создаётся и распространяется в соответствии с моделью разработки свободного и открытого программного обеспечения.

Поэтому общее название не подразумевает какой-либо единой «официальной» комплектации Linux; они распространяются в основном бесплатно в виде различных готовых дистрибутивов, имеющих свой набор прикладных программ и уже настроенных под конкретные нужды пользователя. На начальном этапе Linux бесплатно разрабатывался только энтузиастами-добровольцами, но с успехом Linux и его массовым коммерческим использованием дорабатывать ОС и вносить свой вклад стали и компании, со временем став значительной силой. Подавляющее большинство ПО в современных дистрибутивах по-прежнему доступно по свободным лицензиям, как правило, за исключением небольшого количества проприетарных компонентов. В 2008 году расчёты показывали, что для того, чтобы «с нуля» разработать систему, аналогичную Fedora 9, потребовалось бы затратить 10,8 млрд долл.

Совокупная себестоимость ядра Linux оценена в более чем 1 млрд евро (около 1,4 млрд долл.). Только за 2008 год себестоимость ядра Linux увеличилась на 225 млн евро. В системе Linux воплощён труд в эквиваленте 73 тыс. человеко-лет. В настоящее время системы Linux лидируют на рынках смартфонов (Android занимает 85% рынка), интернет-серверов (60%), самых мощных суперкомпьютеров (97%), а также, согласно Linux Foundation, в дата-центрах и на предприятиях, занимают половину рынка встраиваемых систем, имеют значительную долю рынка нетбуков (32% на 2009 год). На рынке домашних компьютеров Linux прочно занимает 3 место (по разным данным, от 1 до 5%).

Согласно исследованию Goldman Sachs, в целом, рыночная доля Linux среди электронных устройств составляет около 42%. С тех пор, как ядро Linux было создано для x86-ПК, оно было портировано на множество платформ, включая x86−64, PowerPC и ARM. Linux работает в роутерах, телевизорах и игровых приставках. ОС на ядре продолжают быстро совершенствоваться (например, новая версия ядра выпускается каждые 2—3 месяца, с 2005 года в разработке ядра принимают участие более 7800 разработчиков из более чем 800 различных компаний) и набирает популярность (за 9 месяцев с мая 2011 по январь 2012 доля Linux выросла на 64%). Наиболее популярными дистрибутивами являются (расположены в алфавитном порядке названия их пакетных форматов): deb-based (Debian, Mint, Ubuntu), pacman-based (Arch Linux, Chakra, Manjaro), RPM-based (RedHat, Fedora, Mageia, OpenSUSE), source-based (Slackware, Gentoo).

Ubuntu — операционная система, основанная на Debian GNU/Linux. Основным разработчиком и спонсором является компания Canonical. В настоящее время проект активно развивается и поддерживается свободным сообществом. По утверждениям Canonical, Ubuntu используется примерно 20 миллионами пользователей.

Он является 4-м в списке самых популярных дистрибутивов Linux для веб-серверов. По версии DistroWatch.com (на 2014 год) занимает 2-е место по популярности для десктопов. Обычно новые версии дистрибутива выходят каждые полгода и поддерживаются обновлениями безопасности в течение 9 месяцев (начиная с версии 13.04, до этого поддержка осуществлялась в течение полутора лет). Версии LTS, выпускаемые раз в 2 года, поддерживаются в течение 5 лет — как серверные, так и десктопные варианты. (До версии 12.04 LTS срок поддержки для десктопных LTS-версий составлял 3 года.)

На другие дистрибутивы LTS семейства ubuntu действует полная поддержка в 3 года, а для основы системы (ядро, Xorg и прочие компоненты) — 5 лет. Ubuntu поставляется с подборкой программного обеспечения для серверов и рабочих станций. Она устанавливается на настольные персональные компьютеры c помощью LiveCD (версия Desktop), LiveUSB или текстового установщика (версия Alternate, предоставлялась до версии Ubuntu 12.04.2). В версии LiveDVD присутствуют несколько большие возможности — начиная от установки не только в графическом, но и в текстовом режимах, загрузки в режиме восстановления системы и заканчивая полной локализацией и большим количеством пакетов на диске. Есть версии для официально поддерживаемых архитектур, таких как i386, amd64, ARM. Кроме того, с 2013 года начата разработка специальной версии Ubuntu для смартфонов на архитектуре ARM и x86. Ubuntu ориентирована на удобство и простоту использования. Она включает широко распространённое использование утилиты sudo, которая позволяет пользователям выполнять администраторские задачи, не запуская потенциально опасную сессию суперпользователя. Ubuntu, кроме того, имеет развитую интернационализацию, обеспечивающую максимальную доступность для представителей разных языковых групп. С версии 5.04 кодировкой по умолчанию является UTF-8. Ubuntu для работы рекомендуется от 512 мегабайт RAM и, при установке на жёсткий диск, от пяти гигабайт свободного пространства, а предельно минимальные требования гораздо ниже. Ubuntu (до версии 11.04) была основана на системе рабочего стола GNOME, которая разработана, чтобы обеспечить свободный, простой и интуитивный интерфейс, предлагая полный диапазон современных настольных приложений. Помимо тех приложений, которые включены в GNOME, Ubuntu выходит с дополнительным программным обеспечением, включая LibreOffice (OpenOffice.org до версии 11.04), web-браузер Mozilla Firefox. Версия 6.06 и более поздние объединяют LiveCD и установочный CD в один компакт-диск. Этот диск загружает рабочий стол со всеми возможностями, давая пользователям возможность видеть, поддерживаются ли их аппаратные средства, и экспериментировать с доступными приложениями, и уже затем устанавливать Ubuntu на жёсткий диск, используя графический инсталлятор Ubiquity («вездесущность»). Инсталляционный процесс сохраняет документы, созданные на «живом» рабочем столе. Альтернативная установка, использующая debian-installer, доступна для скачивания и нацелена на людей, разбирающихся в системе на более глубоком уровне, администраторов, устанавливающих много систем, и для сложного разбиения дисков, включая использование LVM или RAID, а также для установки с объёмом оперативной памяти менее 192 мегабайт. Также в дистрибутив входит программа создания загрузочного LiveUSB на базе USB Flash-диска, обладающего всеми возможностями LiveCD и установочного CD. Это удобно для использования, например, на нетбуках. Однако на старых компьютерах не всегда есть опция загрузки с USB-флеш-накопителя. Пользовательский интерфейс по умолчанию в ранних версиях характеризовался оттенками коричневого и оранжевого цветов. Ubuntu имеет дополнительный пакет, названный ubuntu-calendar, который загружает новые обои, соответствующие коричневой цветовой теме, каждый месяц. В прошлом на этих обоях присутствовали частично обнажённые люди, поэтому они критиковались как рискованные. Это приводило к созданию таких прозвищ, как «Linuxxx». В интерфейсе Ubuntu проведён ребрендинг, заметный с версии 10.04: изменён логотип, цветовая гамма изменена с оттенков коричневого и оранжевого в сторону чёрного и фиолетового. По мнению некоторых пользователей, новый интерфейс Ubuntu стал напоминать интерфейс Mac OS X. При разработке компонентов Ubuntu активно используется язык программирования Python. Каждый релиз имеет кодовое имя и версию, основанную на годе и месяце выхода. Кодовые имена версий состоят из двух английских слов: прилагательного и названия животного, начинающихся на одну и ту же букву. Начиная с 6.06 LTS Dapper Drake, первые буквы слов кодового имени меняются в соответствии с латинским алфавитом.

Ubuntu 14.04 LTS — Trusty Tahr (надёжный Тар).

2. РАЗРАБОТКА АЛГОРИТМА ПРОГРАММЫ алгоритм архиватор программа В рамках данного курсового проекта будет реализован архиватор. Привязанности к определённой ОС данный алгоритм иметь не будет, то есть будет без проблем работать как на Linux, так и на Windows. Задача сводится к созданию простого алгоритма для сжатия и восстановления данных, а также понятного пользовательского интерфейса, так как в данном случае приложение будет консольным.

На основании выбранного метода решения можно выделить следующие функциональные части:

· процедура вывода информационной заставки на экран;

· организация интерфейса с возможностью ввода данных;

· процедура архивации;

· процедура извлечения;

· процедура выхода из программы;

Рассмотрим первую функциональную часть — вывод информационной заставки. Данная функциональная часть представлена в программе как инструкция для пользователя, содержащая информацию о том «где вы находитесь» и как пользоваться данным приложением.

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

Процедура извлечения и архивации выполняется с помощью ввода определённых параметров, с которыми пользователь познакомится из инструкции, в основном — это путь к архивируемым файлом или архиву.

В любой программе должна быть возможность выхода. Выход будет осуществляться с помощью клавиши ESC. 3]

3. РАЗРАБОТКА ПРОГРАММЫ Программа для большей наглядности и структурированности состоит из функциональных частей, реализованные в виде подпрограмм, и меню, которое используется для облегчения работы с программой.

В ходе реализации данной программе используются стандартные библиотеки языка C++:, ,, и другие.

iostream — заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++.

string — заголовочный файл с классами, функциями и переменными для организации работы со строками в языке программирования C++. 4]

Для наибольшего удобства мы создадим один класс «Zipper», который будет отвечать за все, что происходит внутри архиватора. Содержание класса (рис. 3.1).

class Zipper{

private:

vector files; // набор файлов

string path; // путь

string real_bin_file; // имя выходного файла-архива (используется при архивации)

public:

Zipper (vector &vec, string p)

{

if (vec.size ()>0) files. assign (vec.begin (), vec. end ());

path = p+" «;

real_bin_file=path+" bin. zz" ;

}

}

void getInfo (); // Метод для получения информации о файлах на этапе архивации

void InCompress (); // Архивация данных

void OutCompress (string binary); // Распаковка данных (binary — путь до архива)

// Статический метод для выделения имени файла из полного пути.

static string get_file_name (string fn){return fn. substr (fn.find_last_of («»)+1,fn.size ());}

};

Рисунок 3.1 Содержание класса Распаковка данных из архива тесно связана с тем, что происходит при архивации. Архивация же будет происходить в два этапа:

1. Получение информации об архивируемых файлах;

2. Создание единого файла архива, содержащего блок информации обо всех файлах внутри себя и все файлы в бинарном представлении.

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

||||||||||…||||

Затем текстовый файл побайтно будет переписан в начало файла-архива и удален. Ну, а после блока с информацией мы просто переписываем все архивируемые файлы побайтно в наш архив.

Также продемонстрирую часть кода, отвечающего за получение информации об архивируемом файле:

FILE *info = fopen ((this->path + «info.txt»).c_str (), «rb»);

while (!feof (info))

{

if (fread (byte, 1, 1, info) == 1) fwrite (byte, 1, 1, main);

}

fclose (info);

remove ((this->path + «info.txt»).c_str ());

Процесс распаковки состоит всего из одного этапа, содержащего два подэтапа:

1. Разборка блока с информацией о том, что содержится в архиве;

2. Чтение «месива» байт всех файлов внутри архива по правилам, указанным в информационной секции.

Для работы с файлами использовались процедуры fread, fwrite и fclose. Ниже приведём пример их использования в тексте программы:

FILE *curr = fopen (full_path, «wb»);

for (int r = 1; r <= _sz; r++)

{

if (fread (byte, 1, 1, bin) == 1) fwrite (byte, 1, 1, curr);

}

fclose (curr);

В программе часто используются циклы, такие как while и for. Кроме примеров выше, продемонстрирую работу цикла while для завершения работы программы при запросе у пользователя:

cout << endl << «Желаете продолжить?» << endl << endl;

cout << «Да (Space), Нет (Esc)» << endl << endl;

while (1){

if (getch () == 32){ goto m; }

if (getch () == 27){

cout << endl << «Good Bye «<< endl << endl;

Sleep (1000); exit (1); }

cout << «Нажмите Space или Esc» << endl;

}

4.ТЕСТИРОВАНИЕ И АНАЛИЗ РЕЗУЛЬТАТОВ Первый запуск и выход из программы После запуска программы на экран выведется информационная заставка (рис. 4.1):

Рисунок 4.1 Информационная заставка После этого следует нажать клавишу Esc и после вывода сообщения программа завершит свою работу (рис. 4.2):

Рисунок 4.2 Завершение работы Ввод параметра

Пробуем ввести параметр. Если введём правильно — на экране появится информация для дальнейшей работы, иначе должно появиться сообщение об ошибке и просьбе повторного ввода (рис. 4.3):

Рисунок 4.3 Проверка ввода параметра Ввод пути После того как мы верно указали параметр, нам придётся вводить путь (место сохранения архива, какой файл архивировать и др.). Путь следует вводить согласно примеру, однако при неправильном вводе выведется сообщение об ошибке (рис. 4.4). Если путь указан верно продолжим работу (рис. 4.5).

Рисунок 4.4 Ошибка ввода Рисунок 4.5 Продолжение работы

Проверка работы архивации файлов

После ввода параметра pack начинается процесс архивации. Посмотрим детально его работу (рис. 4.6). Проверим, создался ли файл по нужному пути (рис. 4.7), если да, то попробуем его открыть любым текстовым редактором, например блокнотом (рис. 4.8).

Рисунок 4.6 Успешный процесс архивации

Рисунок 4.7 Архив bin. zz

Рисунок 4.8 Изучение содержимого bin. zz

Проверка работы извлечение данных После ввода параметра unpack начинается процесс извлечения данных из нашего архива (рис. 4.9). Извлечение должно произойти в указанную папку, а данные после извлечения не повреждены (рис. 4.10).

Рисунок 4.9 Процесс извлечения данных Рисунок 4.10 Извлечение данных в указанное место

Заключение

В данном курсовом проекте были рассмотрены следующие вопросы:

· изучение базовых алгоритмов решения задач информатики и практической апробацией изучаемых структур данных и алгоритмов решения задач.

· разработка алгоритмов и программы обработки данных на алгоритмических языках

· организация архиватора, базовыми структурами данных языков программирования В результате проделанной работы был разработан алгоритм и написана сама программа, реализующая процесс сжатия и восстановления данных. Данная программа имеет довольно «гибкий» код, что позволяет его усовершенствовать.

В будущем можно добавить ряд дополнений:

· для более удобного пользования приложение можно сделать в графическом режиме;

· усовершенствовать алгоритм сжатия;

· возможность установки пароля на архив;

· возможность разделения архива на несколько томов для большей безопасности.

1 Дейтел Х. М., Дейтел П.Дж. Как программировать на С.

Введение

в С++ Москва: БИНОМ 2009 г. 908 с.

2 Липпман С., Лажойе Ж. С++ для начинающихСПБ: Невский диалект 2003 г. 1406 с.

3 Базенков Т. Н., Дереченик С. С. СТ БПИ — 02 — 98. Графическая конструкторская документация электронной аппаратуры в курсовых и дипломных проектах (работах): Общие требования к разработке и правила оформления. — Брест, 1998.

4 Электронный портал http://ru.wikipedia.org/ http://ru.wikipedia.org/wiki/Стандартная_библиотека_языка_C++ - Дата доступа 25.04.2015