Формат PNG (англ. portable network graphics) - растровый формат хранения графической информации, использующий сжатие без потерь по алгоритму Deflate.
PNG был создан как свободный формат (замена GIF), поэтому иногда в Интернете встречается расшифровка в качестве рекурсивного акронима "PNG is Not GIF" (PNG не GIF).
04 января 1995 г., Т. Боутелл предложил в ряде конференций Usenet создать свободный формат, который был бы не хуже GIF (дело в том, что до 11 августа 2006 г. GIF был защищен патентами). Через три недели после публикации идеи были разработаны четыре версии нового формата. Вначале он имел название PBF (Portable Bitmap Format), а нынешнее имя получил 23 января 1995 г. Уже в декабре того же года спецификация PNG версии 0.92 была рассмотрена консорциумом W3C, а с выходом 1 октября 1996 г. версии 1.0 - был рекомендован в качестве полноправного сетевого формата.
Структура формата
Общее строение
Файл состоит из подписи (Signature) и некоторого количества блоков (Chunk), которые содержат информацию о изображении.
Блоки данных (Chunks)
Chunks (чанки) - это блоки данных, описывающих записанное изображение, из которых состоит файл. Каждый чанк состоит из 4 секций.
Например:
Критические:
Вспомогательные:
Контрольная сумма CRC-32. (Циклический избыточный код (англ. Cyclic redundancy check) - алгоритм нахождения контрольной суммы, предназначенный проверять целостность данных. CRC является практическим приложением помехоустойчивого кодирования, основанном на определенных математических свойствах циклического кода.)
Минимальный PNG
Как видно из представленного выше большинство чанков не является обязательными. Для формирования "полноценного" файла необходимо иметь минимальный набор блоков:
PNG Signature | IHDR | IDAT | IEND |
Блок данных IHDR содержит следующие поля:
Содержит данные, закодированные, в соответствии с полем метода сжатия.
Сигнализирует о конце файла, блок данных не содержит ничего.
Пример
Разберем в HEX-редакторе. (276 Б)
Список источников
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Расчетно-графическая работа
Тема: «BMP, PCX, PNG – форматы»
По курсу «Сетевые информационные технологии »
Выполнил:
Группа:
АВТ-918
Проверил:
Новосибирск, 2013г.
1. Теоретическая часть
1.1. Введение
1.2. PNG – формат
1.2.1. Общая информация
1.2.2. Область применения
1.2.3. Структура файла
1.2.4. Достоинства
1.2.5. Недостатки
1.3. PCX – формат
1.3.1. Общая информация
1.3.2. Область применения
1.3.3. Структура файла
1.3.4. Достоинства
1.3.5. Недостатки
1.4. BMP – формат
1.4.1. Общая информация
1.4.2. Область применения
1.4.3. Структура файла
1.4.4. Достоинства
1.4.5. Недостатки
1.5. Сравнительная характеристика форматов
2. Практическая часть
- Особенности растровой графики
Растровая графика описывает изображения с использованием цветных точек - пикселей, расположенных на сетке. Например, серфер в море описывается конкретным расположением и цветом каждой точки изображения, примерно, как в мозаике (фотографии, отсканированные рисунки и т. д.). При редактировании растровой графики изменяются пиксели, а не линии. Растровая графика зависит от разрешения, так как информация, описывающая изображение, прикреплена к сетке определенного размера. При изменении размеров данных файлов, качество может измениться, например, приведет к «разлохмачиванию» краев изображения, поскольку пиксели будут перераспределяться. Вывод растровой графики на устройства с более низким разрешением, чем само изображение, понизит его качество.
Применение растровой графики позволяет добиться качественного изображения, фотографического. Но все это создается за счет большого объема файла и работы вручную, т. е. при редактировании приходится поправлять каждую точку. Даже если использовать инструменты типа линии или примитивов (овалов, квадратов), то результат представляет собой изменение пикселей.
При изменении размеров изображений растровой графики качество ухудшается: при уменьшении - исчезают мелкие детали, а при увеличении картинка может превратиться в набор неряшливых квадратов (увеличенных пикселей).
При печати растровой графики или при просмотре на средствах, имеющих недостаточную разрешающую способность, значительно ухудшается восприятие образа.
- Разнообразие форматов растровой графики
Ни одна область применения компьютера не может похвастаться таким многообразием типов форматов файлов, как графика. Многие фирмы, выпуская графическую программу, создают свой собственных формат файлов, в котором редактор должен идеально сохранять все работы, созданные с его помощью. С увеличением количества существующих графических форматов совмещать их становится все труднее. Поэтому появилось несколько определенных форматов, ставших стандартами. Так, например, для изображений в Интернете в большинстве случаев используются форматы JPG и GIF, а в издательском деле царствует TIFF.
Многие растровые форматы обладают способностью нести дополнительную информацию: различные цветовые модели изображения, вектора, альфа-каналы (дополнительный канал, с помощью которого можно сохранять выделенные или прозрачные области изображения), слои различных типов, интерлиньяж (возможность чересстрочного показа изображения), анимацию, возможности сжатия и многое другое.
Достоинства растровых изображений: способность передать тончайшие нюансы изображения, возможность редактировать индивидуально каждый пиксель, изменяя его параметры. Ну, а принципиальный недостаток один - очень большие размеры полученного файла.
Формат PNG (P ortable N etwork G raphics ) представляет собой растровый формат хранения графической информации, использующий сжатие без потерь по алгоритму Deflate . Данный формат был создан как свободный формат для замены GIF.
Днём рождения PNG можно считать 4 января 1995 года, когда Т. Боутелл предложил в ряде конференций Usenet создать свободный формат, который был бы не хуже GIF. И уже через три недели после публикации идеи были разработаны четыре версии нового формата. Вначале он имел название PBF (Portable Bitmap Format ), а нынешнее имя получил 23 января 1995 года. Уже в декабре того же года спецификация PNG версии 0.92 была рассмотрена консорциумом W3C , а с выходом 1 октября 1996 года версии 1.0 PNG был рекомендован в качестве полноправного сетевого формата.
Формат PNG спроектирован для замены устаревшего и более простого формата GIF, а также, в некоторой степени, для замены значительно более сложного формата TIFF (см. официальный сайт PNG или хронологическую страницу для дополнительной информации).
Формат GIF был разработан фирмой CompuServe в 1987 году и изначально был недоступен для свободного использования. До окончания в 2004 году действия патентов на алгоритм сжатия LZW , принадлежавших Unisys и используемых в GIF, его применение в свободном программном обеспечении было затруднено. На данный момент такие затруднения сняты. PNG же с самого начала использует открытый, непатентованный алгоритм сжатия Deflate , бесплатные реализации которого доступны в Интернете. Этот же алгоритм используют многие программы компрессии данных, в том числе PKZIP и gzip (GNU zip ).
Для передачи анимированных изображений был разработан расширенный формат MNG, опубликованный в середине 1999 года и уже поддерживаемый в различных приложениях, однако пока так и не ставший общепринятым.
Некоторые - в частности, разработчики Mozilla Foundation - критиковали MNG за сложность и большой размер реализации, и отсутствие обратной совместимости с PNG. В 2004 году они разработали формат APNG, который не был принят в качестве официального стандарта разработчиками PNG и MNG, но его поддержка к 2008 году была реализована в тестовых сборках некоторых браузеров и некоторых программах просмотра изображений.
Формат PNG предназначен, прежде всего, для использования в Интернете и редактирования графики.
Формат позволяет хранить три типа изображений: greyscale (для описания изображения используется один канал - белый), indexed-colour (используется палитра цветов, как в GIF) и truecolor (используется три канала - RGB). При этом он хранит графическую информацию в сжатом виде, и это сжатие производится без потерь, в отличие, например, от JPEG.
Формат PNG является хорошим форматом для редактирования изображений, даже для хранения промежуточных стадий редактирования, так как восстановление и пересохранение изображения проходят без потерь в качестве. Также, в отличие, например, от TIFF, спецификация PNG не позволяет авторам реализаций выбирать, какие возможности они собираются реализовать. Поэтому любое сохранённое изображение PNG может быть прочитано в любом другом приложении, поддерживающем PNG.
Файл PNG состоит из блоков данных, называющихся chunk "ами. C hunk в общем случае имеет переменную длину. Чтобы отличить один от другого, в каждом chunk "е есть поле типа.
Минимальный PNG-файл должен содержать как минимум сигнатуру и три chunk "a:
IHDR -- заголовок файла
IDAT -- данные, собственно картинка
IEND -- конец файла
Chunk состоит из четырёх полей:
Length -- длина поля данных chunk"а (4 байта)
Type -- поле типа (4 байта)
Data -- поле данных, может быть нулевой длины
CRC -- поле с проверочным кодом для полей Type, Data
Сигнатура PNG-файла содержит всегда 8 байт:
* (decimal) 10 26 10
* (hexadecimal)e 47 0d 0a 1a 0a
* (ASCII C notation) \211 P N G \r \n \032 \n
Сигнатура не является стандартным chunk "ом.
IHDR chunk
Этот chunk содержит основную информацию о картинке: ширина и высоту в пикселях, количество битов на сэмпл (не на пиксель) или количество бит, определяющее размер палитры и т. п.
IEND chunk
Это chunk сигнализирует о конце PNG-файла.
IDAT chunk
Этот chunk содержит данные с графической информацией. Эти данные запакованы в zlib формат. Данные, запакованные в zlib формат, запакованы в формат DEFLATE, который в общем случае предусматривает сжатие информации. Но один из вариантов DEFLATE позволяет хранить данные в контейнерах DEFLATE без сжатия.
Графическая информация, хранящаяся в IDAT chunk "ах, представляет собой набор строк (scanlines ). В формате PNG для более эффективного сжатия предусмотрена фильтрация строк. Для указания используемого фильтра перед данными строки должен следовать один байт. Содержимое означает, какой фильтр используется. В самой простой реализации фильтр можно не использовать (ведь и сжатия никакого не планируется). В этом случае этот байт должен быть равен 0.
Как вариант, одна строка графической информации может упаковываться в один IDAT chunk . Так, например, сделано в Беркут-ЕТ: файл содержит 240 IDAT chunk "ов.
Алгоритмы упаковки данных без сжатия в zlib и deflate форматы очень просты для реализации во встраиваемых системах, поскольку они сводятся к простому формированию заголовков и подсчёту контрольной суммы adler32.
Рис. 1. Структура PNG -файла
На рисунке изображена последовательность chunk "ов, образующих файл PNG. Как уже говорилось, в chunk "и IDAT "укладываются" 240 строк. Перед каждой строкой следует байт, указывающий тип фильтра (значение 0).
На рисунке используются следующие обозначения:
CH - chunk header , содержит длину поля данных и тип chunk "а IDAT
ZH - zlib header ,
DH - DEFLATE header, содержит 5 байт
CC - контрольная сумма crc32 для chunk "a
ZA - контрольная сумма adler32 для данных, упакованных DEFLATE алгоритмом.
Важно, что CC считается для каждого chunk "a, а ZA считается для всего вектора данных, упакованного алгоритмом DEFLATE.
- zlib header
Он содержит 2 байта: 0x78, 0x01
Байт 0х78 означает, что для компрессии данных используется DEFLATE с окном до 32 Кбайт.
Байт 0х01 содержит проверочный бит для первого байта и определяет уровень сжатия "без сжатия".
DEFLATE header
DEFLATE header содержит 5 байт . Первый байт содержит информацию о типе компрессии и о последнем блоке. Если используется тип компрессии "no compression", то первый и последующие блоки должны иметь первый байт 0x00, а последний блок 0x01.
Ещё четыре байта используются для указания длины блока (первые 2 байта) и проверочного поля для длины блока (вторые 2 байта). Другими словами -- LEN и NLEN, где NLEN = 0xffff - LEN.
- png check
PNG check -- это утилита, упрощающая жизнь программисту при отладке кода, создающего PNG. Она проверяет правильность формирования PNG и сообщает, если что-то не так. Например, утилита может отследить, что не сходится контрольная сумма или отсутствует какой-нибудь chunk , и т. п.
PNG обладает более высокой степенью сжатия для файлов с большим количеством цветов, чем GIF, но разница составляет около 5-25 %;
Так же самое главное преимущество формата PNG - это новые алгоритмы сжатия. В отличие от формата GIF, который эффективно сжимает только горизонтальные одноцветные области, формат PNG этим не ограничивается. Для сравнения приведено два изображения в разных форматах. Очевидно, что при почти десятикратной эффективности сжатия потерь в качестве не замечено.
Рис. 2. PNG (372 байта) Рис. 3. GIF (2, 5 Кбайт)
Еще одним важным преимуществом является фильтрация строк (scanline filtering , или delta filters ), благодаря которой PNG-упаковщик может получить гораздо более удобные данные для сжатия.
Например, есть изображение 5×5 пикселей с горизонтальным градиентом. Схематично отобразим, как оно может быть сохранено в файле (каждое число - уникальный цвет).
Рис. 4. Схематичное отображение
Как видно из примера, GIF-кодировщик отдал бы на сжатие строки, которые плохо упаковываются по горизонтали (потому что одинаковые цвета распространяются по вертикали). А вот как может преобразовать эти данные PNG-кодировщик:
Рис. 5. Схематичное отображение (PNG -кодировщик)
Перед каждой строкой появилась цифра 2. Это - фильтр, который был применен к строке. В данном случае это фильтр Up , который говорит декодеру: «Для текущего пикселя возьми значение пикселя выше и прибавь к нему текущее значение». В нашем случае это 0, потому что цвета текущего и верхнего пикселей не отличаются. А эти данные можно эффективней упаковать, если у нас достаточно большое изображение.
К недостаткам формата можно отнести :
а. Не все веб-браузеры одинаково отображают содержимое png-файла. Узким местом являются:
Частичная прозрачность (альфа-канал);
Поддержка прозрачности в палитре;
Гамма-коррекция.
Поддержка расширений PNG с анимацией.
Цветовая коррекция (ICC).
б. Существует одна особенность GIF, которая в PNG не реализована - поддержка множественного изображения, особенно анимации; PNG изначально был предназначен лишь для хранения одного изображения в одном файле.
PCX (PCExchange ) - стандарт представления графической информации, разработанный компанией ZSoft Corporation. Использовался графической программой ZSoft PC Paintbrush (одной из первых популярных графических программ) для MS-DOS, текстовыми процессорами и настольными издательскими системами, такими как Microsoft Word и Ventura Publisher .
Данный формат является не столь популярным аналогом BMP, хотя поддерживается специфическими графическими редакторами, такими как Adobe Photoshop, Corel Draw, GIMP и др. В настоящее время вытеснен форматами, которые поддерживают лучшее сжатие: GIF, JPEG и PNG.
Тип формата - растровый. Большинство файлов такого типа использует стандартную палитру цветов, но формат был расширен из расчета на хранение 24-битных изображений.
PCX - аппаратно-зависимый формат. Предназначается для хранения информации в файле в таком же виде, как и в видеоплате. Для совместимости со старыми программами необходима поддержка EGA-режима видеоконтроллером.
Формат предполагает использование простейшего алгоритма сжатия (Run Length Encoding, RLE) без потерь информации. Алгоритм такого сжатия очень быстрый и занимает небольшой объём памяти, однако не очень эффективен, непрактичен для сжатия фотографий и более детальной компьютерной графики. При сохранении изображения, подряд идущие пиксели одинакового цвета объединяются, и вместо указания цвета для каждого пикселя указывается цвет группы пикселей и их количество. Такой алгоритм хорошо сжимает изображения, в которых присутствуют области одного цвета.
Область применения данного формата сокращается, поскольку вытесняется другими форматами. Имеет больше историческое значение, нежели практическое.
Однако, благодаря поддержке многими приложениями и простоте перезаписи, данный формат нередко используется разработчиками при работе с растровой графикой.
Так же данный формат используют многие графические редакторы, в частности Paint . Вместе с форматом TIFF формат PCX является одним из наиболее распространённых форматов, которые используют сканеры.
Файл изображения PCX начинается с заголовка длиной 128 байт. Затем идут закодированные графические данные.
При кодировании используется простой алгоритм, основанный на методе длинных серий. Если в файле запоминается несколько цветовых слоев, каждая строка изображения запоминается по цветовым слоям. Согласно документации Zsoft , это выполняется по приведенной ниже схеме (R - красный слой, G - зеленый слой, B - синий слой, I - слой интенсивности)
Строка изображения 0:
RRR...
GGG...
BBB...
III...
Строка изображения 1:
RRR...
GGG...
BBB...
III...
(и т. д.)
Запоминание по слоям проводится, как правило, для 16-цветных изображений EGA. При стандартной палитре EGA, которая устанавливается по умолчанию BIOS"ом, нулевой слой видео памяти содержит СИНЮЮ компоненту цвета, а не красную. Если же палитра отлична от стандартной, то говорить о том, что слои видео памяти, соотносятся с компонентами цвета вообще затруднительно.
Метод кодирования состоит в следующем:
ДЛЯ каждого байта X, прочитанного из файла. ЕСЛИ оба старших бита X равны 1, то <повторитель> = значению, хранящемуся в 6 младших битах X <данные> = находятся в следующем байте за X. ИНАЧЕ <повторитель> = 1 <данные> = X
Поскольку для насыщения данного алгоритма требуется в среднем 25% неповторяющихся данных и, по меньшей мере, наличие смещения между повторяющимися данными, то размер получаемого файла, как правило, оказывается приемлемым.
Смещение | Обозначение | Длина | Описание / комментарий |
Manufacturer | Постоянный флаг 10 = ZSoft. PCX |
||
Version | Информация о версии: |
||
Encoding | 1 = PCX кодирование длинными сериями |
||
Bits per pixel | Число бит на пиксел в слое |
||
Window | Размеры изображения (Xmin, Ymin) – (Xmax, Ymax) в пикселах включительно |
||
Hres | Горизонтальное разрешение создающего устройства |
||
Vres | Вертикальное разрешение создающего устройства |
||
Colormap | |||
Reserved | |||
NPlanes | Число цветовых слоев |
||
Bytes per Line | Число байт на строку в цветовом слое (для PCX-файлов всегда должно быть четным) |
||
Palette Info | Как интерпретировать палитру: |
||
Filler | Заполняется нулями до конца заголовка |
||
Возможность создания ограниченной палитры цветов (например, 16 или 256 цветов);
Поддерживается большим количеством приложений;
Сжатие производится без потерь.
Не поддерживает цветовые системы, отличные от RGB;
Многочисленные варианты, особенно при работе с цветами, могут делать работу с файлом невозможным;
Неудобная схема сжатия в действительности может увеличивать размеры некоторых файлов.
BMP (от англ. Bitmap Picture) - формат хранения растровых изображений, разработанный компанией Microsoft.
С форматом BMP работает огромное количество программ, так как его поддержка интегрирована в операционные системы Windows и OS/2. Файлы формата BMP могут иметь расширения. bmp, .dib и. rle. Кроме того, данные этого формата включаются в двоичные файлы ресурсов RES и в PE-файлы.
Компания Microsoft также разработала для своих нужд форматы ICO и CUR, которые имеют похожую на BMP структуру. Кроме этого, структуры из этого формата используются некоторыми WinAPI-функциями подсистемы GDI.
Глубина цвета в данном формате может быть 1, 4, 8, 16, 24, 32, 48 бит на пиксель. При этом для глубины цвета меньше 16 бит используется палитра с полноцветными компонентами глубиной 24 бита.
В формате BMP изображения могут храниться, как есть или же с применением некоторых распространённых алгоритмов сжатия. В частности, формат BMP поддерживает RLE-сжатие без потери качества, а современные операционные системы и программное обеспечение позволяют использовать JPEG и PNG (эти форматы встраиваются в BMP как в контейнер).
Из-за большого объема изображения и редкого использования сжатия, файлы в данном формате весят слишком много для использования в сети.
Однако же, не смотря на свою «старость», данный формат широко используется для работы в пределах одной машины благодаря интегрированной поддержке в ОС Windows . С данным форматом работают практически все известные программы .
BMP - стандартный формат графических файлов Windows. Подавляющее большинство BMP-файлов хранится без сжатия, что облегчает работу с ними.
BMP-файлы состоят из трех основных частей:
Заголовок содержит информацию о файле и находящемся в нем графическом изображении. Здесь хранятся параметры изображения (ширина, высота, глубина пикселей), а также количество цветов в нем.
Палитра присутствует только в BMP-файлах, содержащих палитровые изображения (с глубиной пикселей 8 бит и менее). К 8-битным изображениям прикладывается палитра, состоящая не более чем из 256 элементов.
Графические данные - это и есть само изображение. Формат этих данных зависит от глубины пикселей. 8-битные BMP-файлы могут использоваться для работы с 8-битными поверхностями, а 24-битные - для беспалитровых поверхностей.
- Структура заголовка
Данные заголовка BMP-файла хранятся в двух структурах:
BITMAPFILEHEADER и BITMAPINFOHEADER .
Структура BITMAPFILEHEADER присутствует в начале любого BMP-файла и содержит информацию о самом файле. Для нас в этой структуре представляет интерес лишь одно поле - bfType , сигнатура BMP-файла. В BMP-файлах это поле содержит буквы BM (обе буквы - прописные). По содержимому этого поля мы будем убеждаться в том, что выбранные файлы действительно имеют формат BMP.
Структура BITMAPINFOHEADER содержит информацию об изображении, хранящемся в BMP-файле. Эта структура объявляется так:
typedef struct tagBITMAPINFOHEADER {
DWORD biSize;
LONG biWidth;
LONG biHeight;
WORD biPlanes;
WORD biBitCount;
DWORD biCompression;
DWORD biSizeImage;
LONG biXPelsPerMeter;
LONG biYPelsPerMeter;
DWORD biClrUsed;
DWORD biClrImportant;
} BITMAPINFOHEADER, FAR *LPBITMAPINFOHEADER, *PBITMAPINFOHEADER;
Первое поле, biSize , определяет размер структуры BITMAPINFOHEADER в байтах. Если ваша программа создает BMP-файл, это поле заполняется тривиально - достаточно определить размер структуры функцией sizeof . Однако при чтении BMP-файла по содержимому этого поля приходится рассчитывать позицию файла, на которой структура заголовка кончается. Эта мера обеспечивает обратную совместимость, благодаря ей Microsoft в будущем сможет увеличить размер структуры BITMAPINFOHEADER , не нарушая работы существующих приложений.
Поля biWidth , biHeight и biBitCount определяют размеры изображения. Содержимое поля biCompression позволяет узнать, хранится ли изображение в сжатом виде. Поскольку мы не собираемся работать со сжатыми BMP-файлами, необходимо проверить, имеет ли это поле значение BI_RGB (а не BI_RLE8 , свидетельствующее о сжатии файла).
В поле biSizeImage хранится размер графических данных (в пикселях). Однако учтите, что это поле часто оказывается незаполненным (содержит нулевое значение). В таких случаях нам придется самостоятельно вычислять размер графических данных.
Наконец, поле biClrUsed определят количество цветов в палитре (для палитровых изображений). Как и поле biSizeImage , оно часто может быть равно нулю. Это означает, что палитра содержит максимальное количество элементов (256 для 8-битных изображений).
- Палитра
Палитра в BMP-файлах хранится в виде списка структур RGBQUAD , где каждый элемент представляет отдельный цвет. Структура RGBQUAD объявляется так:
typedef struct tagRGBQUAD {
BYTE rgbBlue;
BYTE rgbGreen;
BYTE rgbRed;
BYTE rgbReserved;
} RGBQUAD;
В первых трех полях хранятся цветовые RGB-составляющие. На поле rgbReserved мы не будем обращать внимания (предполагается, что оно равно нулю). Как я упоминал выше, количество структур RGBQUAD в BMP-файле определяется полем biClrUsed . Тем не менее обычно 8-битные BMP-файлы содержат 256 структур RGBQUAD . В 24-битных RGB-файлах структуры RGBQUAD отсутствуют.
- Графические данные
Графические данные в основном представляют собой список пикселей, из которых состоит изображение. Однако каждая горизонтальная строка пикселей должна занимать блок памяти, выровненный по границе параграфа. Следовательно, если количество байт, необходимых для хранения строки пикселей, не кратно четырем, в каждую строку включается от одного до трех дополняющих байт.
При этом для работы с графическими данными BMP-файлов используется концепция шага. Отличие состоит в том, что для графических данных BMP-файлов значение шага программисту придется считать самостоятельно. Впрочем, это не так уж сложно, потому что шаг всегда попадает на ближайшую границу параграфа за концом блока памяти, необходимого для хранения строки пикселей.
Изображения хранятся в BMP-файлах в перевернутом виде, так что первая строка пикселей файла на самом деле является нижней строкой настоящего изображения.
Возможность редактирования почти в любой программе, как стандартной, так и специальной;
Высокое качество изображения.
Абсолютно не подходит для сети Интернет;
Крайне неудачный выбор для последующей распечатки;
Аппаратно-зависимый формат.
JPEG | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Потери при сжатии | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Максимальное число бит на пиксел | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Прозрачность | альфа-канал | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Гамма-коррекция | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Множественное изображение | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Алгоритм сжатия | Deflate(LZ 77) | JPEG | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Размер изображения | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Проблемы отображения браузерами | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Цветовая схема | Все доступные | Не поддерживает CMYK | Все доступные | Не поддерживает Indexed color , со CMYK вероятны проблемы при чтении |
Общаясь со своими коллегами на различных семинарах и в студии, я пришел к выводу, что для многих единственным преимуществом формата PNG является наличие честной полупрозрачности. Если поискать в интернете информацию об этом формате, несложно заметить, что веб-разработчики разделились на два лагеря. Первые пишут о том, какой этот формат замечательный, оперируя чисто техническими данными, непонятными обычным кодерам и дизайнерам (к примеру, о превосходстве deflate-алгоритмов сжатия над LZW), другие же оставляют комментарии разной степени глупости о бесполезности PNG, не потрудившись даже вникнуть в суть вещей, описанных в спецификации. Попробуем разобраться, какие преимущества дает этот формат, чтобы научиться ими пользоваться при подготовке иллюстраций для веба. Начнем с терминологии. Предполагаю, что большинство читателей пользуются фотошопом и встречали там названия PNG-8 и PNG-24. Это не два разных формата, а всего лишь вариации одного и того же PNG. Формат позволяет хранить три типа изображений: greyscale (для описания изображения используется один канал — белый), indexed-colour (используется палитра цветов, как в GIF) и truecolor (используется три канала — RGB). Самое главное преимущество формата PNG — это, конечно же, новые алгоритмы сжатия. Все помнят, что GIF эффективно сжимает только горизонтальные одноцветные области? Про это ограничение теперь можно забыть:
Вторым важным преимуществом является фильтрация строк (scanline filtering, или delta filters), благодаря которой PNG-упаковщик может получить гораздо более удобные данные для сжатия. Рассмотрим на примере, как они работают. Возьмем изображение 5×5 пикселей с горизонтальным градиентом и схематично отобразим, как оно может быть сохранено в файле (каждое число — уникальный цвет). Как видно из примера, GIF-кодировщик отдал бы на сжатие строки, которые плохо упаковываются по горизонтали (потому что одинаковые цвета распространяются по вертикали). А вот как может преобразовать эти данные PNG-кодировщик: Перед каждой строкой появилась цифра 2. Это — фильтр, который был применен к строке. В данном случае это фильтр Up, который говорит декодеру: «Для текущего пикселя возьми значение пикселя выше и прибавь к нему текущее значение». В нашем случае это 0, потому что цвета текущего и верхнего пикселей не отличаются. А эти данные можно эффективней упаковать, если у нас достаточно большое изображение. Почему я написал может ? Потому что в нашем идеализированном случае более эффективной была бы такая схема: Тут применен фильтр 1 под названием Sub, который говорит декодеру: «Возьми значение пикселя левее текущего и прибавь ему текущее значение». В данном случае 1. После фильтрации все строки (вместе со значениями фильтров) объединяются в одну последовательность, которая затем сжимается deflate-алгоритмами (их обсуждение выходит за рамки этой статьи). Проверим работу фильтров: Внимательный читатель может заметить, что фильтры применяются не ко всему файлу целиком, а к строкам. Это значит, что каждая строка может иметь свой фильтр. Получается, что способов фильтрации одного изображения может быть 5 высота картинки. В общем-то, задача хорошего кодировщика как раз заключается в том, чтобы подобрать такие значения фильтров, при которых объем файла будет минимальным. К сожалению, фотошоп не всегда хорошо справляется со своей работой, поэтому на помощь приходят различные утилиты вроде и , которые в большое количество проходов подбирают разные способы фильтрации и стратегии сжатия данных, значительно сокращая тем самым объем некоторых сложных изображений. Однако стоит помнить, что эти программы не гарантируют уменьшение объема для каждого файла, они всего лишь пытаются найти оптимальный способ кодирования данных. Еще один больной укол фотошопу за то, что он не умеет сохранять изображения в greyscale-режиме, то есть не умеет понижать глубину цвета. Тут нас опять спасут вышеозначенные утилиты, которые по возможности снижают глубину цвета, не ухудшая при этом качества картинки.
Преимущества greyscale над truecolor очевидны: к примеру, белый цвет в первом случае записывается (в десятичной системе счисления) числом 255, а во втором — 16777215. Теперь, вооружившись знаниями о хранении данных в формате PNG, мы можем применять их в подготовке изображений для веба. Об этом — в следующих статьях. Привет! В этой статье я познакомлю вас с устройством изображений в формате PNG, а так же с механизмом работы алгоритма Deflate. Мы на примере рассмотрим все аспекты этой темы. Надеюсь, вам будет интересно. ДисклеймерДанный материал не призван быть максимально объективным и академически верным. Автор статьи (в дальнейшем — я и другие личные местоимения первого лица) мог упускать некоторые моменты, а некоторые рассматривать лишь с одной стороны. Статья была рождена на свет исключительно из спортивного интереса, а также желания лучше понимать то, с чем я работаю каждый день. Если ты, дорогой читатель, не согласен со мной или считаешь, что я забыл дописать что-то очень важное, то, пожалуйста, напиши об этом в комментариях. Этим сотрудничеством мы сможем добиться ликвидации пробелов в знаниях и, быть может, сделать мир чуточку лучше. Пример изображенияВнутреннее устройство PNG мы будем разбирать на примере маленького изображения 2 x 2 пикселя. Ссылку на него я оставлю в разделе «материалы» в нижней части страницы. Долой длинные вступления. Начинаем! Структура PNGНе буду грузить читателя описанием формата, историей его появления и прочими вещами, которые никаким образом не относятся к теме статьи, а сразу же без всяких прелюдий перейду к рассмотрению структуры. Любой файл PNG начинается со следующей последовательности байтов (в шестнадцатеричном представлении): 89 50 4E 47 0D 0A 1A 0A Это так называемая подпись PNG (PNG file signature). 50 4E 47 — как раз и соответствуют символам P N и G из таблицы ASCII. Наличие данной строки указывает программе-декодеру, что она имеет дело с классическим изображением формата PNG, которое состоит из последовательности чанков (об этом ниже), первый из которых — это IHDR, а последний — IEND. Отчасти именно эта подпись позволяет большинству программ преспокойно прочитать изображение PNG, даже если у него в качестве расширения указан, скажем, JPEG. PNG имеет удивительно логичную и лаконичную структуру, что позволяет без лишних затруднений читать, изменять и создавать изображения в этом формате. Как я уже выше упомянул, в основе структуры любого PNG-изображения лежит последовательность чанков (от англ. «chunk» — кусок, ломоть; я буду использовать именно это слово, вместо соблазнительного «блок», так как это позволит избежать путаницы), которые следуют друг за другом. Каждый чанк состоит из следующих обязательных частей: Все чанки можно разделить на обязательные (critical) и вспомогательные (ancillary). Самые догадливые уже всё поняли, но я, всё же, опишу несколькими словами их различия. Обязательные чанки должны присутствовать в любом PNG-изображении, а вспомогательные — нет (вот это новость!). Отсутствие обязательного чанка вызовет ошибку, а вот отсутствие вспомогательного, даже если на него ссылается какой-нибудь другой чанк, декодер проигнорирует. Названия обязательных чанков всегда начинаются с прописной буквы, а вспомогательных — со строчной (например IDAT — обязательный, а вот tIME — нет). К обязательным чанкам относятся: Перечень вспомогательных чанков можно найти в документации PNG (ссылка #1), а обязательные мы разберем немного подробнее: IHDRЭто самый первый из обязательных чанков. Важно запомнить, что он должен располагаться в самом начале документа. Состоит из 13 байт: Наиболее важными для нас являются 9 и 10 байты. Давайте рассмотрим их чуть подробнее. Color typeИспользуемая цветовая модель. Может принимать следующие значения:
В виде таблицы:
Глубина цветаЦветовая глубина — значение, представляющее собой количество битов, которое необходимо для кодирования одного канала. Например, если у нас color type равен RGB, а глубина цвета — 8 бит, то количество битов, необходимое для кодирования 1 пикселя будет равняться 24. То, что я написал выше, очень важно запомнить или записать, так как эта информация обязательно пригодится нам при расшифровке чанка IDAT. В нашем случае чанк IHDR является следующей строкой (в шестнадцатеричном представлении): 00 00 00 02 00 00 00 02 10 02 00 00 00 Теперь нам совершенно не составит труда всё это расшифровать: Что же это означает? Color type равняется 2, значит используется цветовая модель RGB, т.е. комбинация красного, зелёного и синего каналов. Глубина цвета равняется 16, а значит каждый из этих каналов закодирован парой байтов. Отсюда также несложно понять, что для кодирования одного пикселя изображения используется 48 бит или 6 байт. Идём дальше. PLTEСчитается обязательным чанком, но фактически является таковым только для color type 3. PLTE содержит от 1 до 256 трёхбайтовых цветов: Подробно на нём останавливаться я не собираюсь, так как на практике color type 3 встречается очень редко. Самые любознательные смогут найти исчерпывающую информацию в спецификации PNG (ссылка #1). IDATНаконец-то мы добрались до содержимого нашего изображения. Чанк IDAT начинается с 4 байтов — 49 44 41 54, которые, собственно, и декодируется в «IDAT». Согласно спецификации PNG, содержимое IDAT сжато методом Deflate и упаковано в формат zlib. В общем случае чанк состоит из следующих обязательных частей:
Давайте немного подробнее. Zlib headerСпецификация RFC 1950 говорит нам, что zlib header должен состоять из двух байтов. Первый байт – это Compression Method and Flags (CMF), который в свою очередь содержит:
Второй байт — Flags (FLG), содержит:
Схематично Zlib header можно изобразить так:
В нашем случае: 78 DA или в двоичном представлении 0111100011011010:
Проверим. Для удобства переведём всё это в десятичную систему: CMF: \({ 78 }_{ 16 }={ 120 }_{ 10 }\) \(120\times 256+192=30912\) Получилось 26. Это и есть наш FCHECK. Всё правильно. Изучаем сжатые данныеЭто самый скучный и однообразный процесс. Внутри этих блоков мы ожидаем увидеть последовательность строк, каждая из которых начинается со значения FILTER — фильтра (речь о фильтрации, используемой при сжатии для увеличения его эффективности). FILTER может принимать значения от 0 до 4, которые носят названия «None», «Sub», «Up», «Average», «Paeth». Для чего это нужно? При больших размерах файла фильтрация может помочь сократить занимаемое изображением пространство. Например, фильтр «Sub» означает, что нужно сложить значение текущего пикселя со значениями предыдущих пикселей в строке. Вот так выглядит формула для декомпрессии с использованием «Sub»: \(Raw(x)=Sub(x)+Raw(x-bpp)\), Считываем блоки, помня про спецификацию RFC 1950, которая гласит, что блок начинается с трёхбитного заголовка:
Внимательность: каждый байт рассматривается в виде последовательности битов, идущих от младшего к старшему. Например, байт 11100001 мы прочитаем как 10000111. В работе будем использовать таблицу фиксированных кодов Хаффмана (для фиксированных значиний, разумеется), таблицу смещений и таблицу длин. Давайте их и рассмотрим. Таблица фиксированных кодов ХаффманаКак мы будем её использовать? Очень просто, на самом деле. Сначала берём первые 7 битов (минимальное значение, см. таблицу), после этого смотрим на префикс нашей получившейся последовательности. Префиксом называется подстрока, начинающаяся с 1 символа. Таблица кодов Хаффмана построена таким образом, чтобы по ней можно было однозначно декодировать наше значение, так как ни один из кодов не является подстрокой для другого кода. Это позволит нам по префиксу восстановить правильное значение. Для тех, кто не очень понял, объясню на примере: \(1100110\_ >10111111\) Нижними подчёркиваниями я обозначил любые значения, ибо они нам в данный момент безразличны. \(110010000\lt1100110\_\_\lt111111111\) А вот тут уже интереснее. Значение действительно попадает в промежуток. Теперь смотрим во второй столбец и видим, что необходимое количество битов — 9. Значит берём еще два бита, после чего наша измученная последовательность выглядит так: 110011000. \(V=D-B+L\) Код 256 — признак конца блока, символы 286 и 287 лишние. Таблицы длин и обратных смещенийТут тоже нет ничего сложного. Если код, который мы высчитали по предыдущей таблице попадает в промежуток от 257 до 285 (то есть, 3 и 4 случаи, исключая код 256, 286 и 287), то наше итоговое значение будет высчитываться по длине и обратному смещению. Но что же это? А это и есть результат работы Deflate. Название таблицы говорит само за себя. Когда мы натыкаемся на подобную команду, нужно отступить назад на количество битов, равное обратному смещению и взять количество битов, равное длине. Код 285 обозначает длину 258 Внимательность: пара замечаний по таблице. Я так понимаю, она была сгруппирована по доп. битам и сделано это лишь с целью экономии места. Поэтому немного объясню. Первая колонка содержит диапазоны кодов, а вторая — соответствующие им диапазоны длин. То есть, например, коду 265 соответствуют длины 11-12, 266 — 12-13, 267 — 13-14, ну и так далее со всеми остальными. Дополнительные биты нужны для того, чтобы в этом диапазоне длин выбрать нужное значение. Если, например, у нас длины равны 12-13 и есть 1 дополнительный бит, то 0 будет указывать на 12, а 1 — на 13. Думаю, логика примерно ясна. Таблица обратных смещений:
Логика здесь точно такая же. После того, как мы нашли значение длины, считываем еще 5 битов (от младшего к старшему, естественно), переводим в десятичное представление для удобства. Этот код находим в таблице, используем дополнительные биты при необходимости и находим обратное смещение. Поехали дальше, начнём разбирать наш код. ПриступаемДля удобства переведём всю последовательность в двоичный код (можно написать программу для этого, можно сделать вручную, а можно воспользоваться калькулятором, которых в Интернете полно; лично я предпочитаю первый вариант). Итак, у нас получается код (не забывайте про нули, их здесь может и не быть, но каждый байт обязательно является двоичным восьмибитным числом): 01100010 01011000 10110001 1010100 1000001 10100001 10100000 11100000 11111111 11111111 11111111 11111111 11111111 11111111 1100111 10000000 1010000 10000 | 100001 01000000 00000000 00000000 00000000 11111111 11111111 11011100 01000111 00010000 11001111 1001001 1000101 1001110 1000100 Выглядит эффектно, правда? На самом деле, тут всё просто. Начинаем: 1. Считываем первые 3 бита, заголовок первого блока. 2. На этом этапе нужно брать минимум 7 битов, определять префикс. Далее уже переводить в число, либо считать смещения и длины. Что же мы стоим? Вперёд! 2.1 Берём первые 7 битов: |00110 00| 011010 \(F=00110000-00110000+0\) Таким же образом проделываем всю остальную работу. Мы помним, что для кодирования 1 пикселя в нашем случае используется 6 байтов. Считаем их всех, а потом ненадолго остановимся: … : |1101 001| 01| 010 … : |010 1000| 0| 010 … : |010 1000|0| 101 … : |101 0000|0|101 … : |101 0000|0|111 Самые смышлёные тут опять же вспомнят, что в данном изображении используется цветовая модель RGB с глубиной цвета 16 бит. Каждый их трёх каналов закодирован двумя байтами. Чтобы получить 16-битное значение мы должны просто конкатенировать два байта. Далее, если мы захотим преобразовать их в 8-битный аналог, то я предлагаю решить следующую пропорцию. Можно, конечно же, просто отбросить второй байт, но тогда есть небольшая вероятность того, что полученное значение будет искажено. Поехали: Переводим и соединяем: Отсюда x: Символами \(\lceil\) \(\rceil\) обозначают потолок, то есть округление до целого в большую сторону. Получилось, что R в нашем случае равен 168. Если мы проделаем то же самое с G и B-каналами, то получим, что цвет нашего первого пикселя в RGB-представлении равен (168, 32, 112). Теперь посмотрим на скриншот: Мы движемся в верном направлении. А это значит, что нет смысла останавливаться! Второй пиксель декодируем так: Сразу же можно предугадать сколько битов нам понадобится: Путём несложных вычислений получаем наш код: RGB(255, 255, 255) — белый цвет. Всё верно. На этом строка заканчивается, так как её ширина составляет всего 2 пикселя. Приступаем ко второй (и последней) строке: … : | 00110 00 | 0 | 00001 … : | 00001 00 |00101 | 0 | Значение попадает в третий промежуток, давайте разбираться. По формуле получим следующий код: \({ 0000100 }_{ 2 }-{ 0000000 }_{ 2 }+{ 256 }_{ 10 }={ 260 }_{ 10 }\) Заглянем в таблицу длин и получим значения: Теперь считываем следующие 5 битов, которые являются обратным смещением: \(00101=5\) А вот тут самое интересное. Наш «курсор» находится сразу же после байта со значением FILTER (который равен 0). Вернёмся на 7 байтов назад (обратное смещение) и скопируем 6 байтов (это как раз байты последнего пикселя первой строки): \({ R }_{ 1 }=511-400+144=255\) \({ R }_{ 2 }=511-400+144=255\) \({ G }_{ 1 }=511-400+144=255\) \({ G }_{ 2 }=511-400+144=255\) \({ B }_{ 1 }=511-400+144=255\) \({ B }_{ 2 }=511-400+144=255\) Вот и всё. Ничего тут страшного нет. Цвет первого пикселя второй строки — RGB(255, 255, 255), что правда. Ух, надо идти вперёд! Я буду краток: 3-й промежуток. Код — 260: Смещение: | 0 1000 | 010 | 0 1. Доп. биты — 3 Смещение = \(17+2=19\) Получаем: \({ R }_{ 1 }=424-400+144=168\) \({ R }_{ 2 }=421-400+144=165\) \({ G }_{ 1 }=80-48+0=32\) \({ G }_{ 2 }=80-48+0=32\) \({ B }_{ 1 }=160-48+0=112\) \({ B }_{ 2 }=160-48+0=112\) Цвет — RGB(168, 32, 112). В принципе, может показаться, что это всё. Но на самом деле, нет. Считываем дальше: |0 000000|00 256 — признак конца блока. Мы закончили. Итак, что у нас получилось? Две строки по два пикселя. Первый имеет цвет RGB(168, 32, 112), второй RGB(255, 255, 255), третий и четвёртый — RGB(255, 255, 255) и RGB(168, 32, 112) соответственно. Если вы вспомните изображение, то поймете, что это недалеко от правды. Значит, мы всё делаем правильно, что внушает надежду на светлое будущее. Судя по всему, начало нового блока? Ладно. Сжатия нет, блок последний. Здесь самый простой вариант — без сжатия. В этом случае после заголовка идёт выравнивание на границу байта (то есть мы должны взять оставшееся количество битов в этом байте). Потом два байта — LEN и еще 2 — NLEN. 00000000 00000000 — LEN Как мы видим, всё действительно так. Единственное, что LEN = 0, т.е. данных нет. Зачем это сделано — непонятно. Ну и наконец, в самом конце чанка IDAT следует четырёхбайтовая хеш-сумма несжатых данных, высчитанная по алгоритму Adler-32. В нашем случае, хеш-сумма в двоичном представлении выглядит так: 11011100 01000111 00010000 11001111 Adler-32Подробную информацию о том, как работает Adler-32 можно найти по ссылке #5. А мы пока возьмем последовательность расшифрованных байтов и захешируем её. Последовательность (в десятичном представлении): 0 168 165 32 32 112 112 255 255 255 255 255 255 0 255 255 255 255 255 255 168 165 32 32 112 112 Я набросал на PHP простенький код: $array = explode(" ", $uncompressed); $start_1 = 1; foreach($array as $num) $temp_1 = $start_1 + trim($num); $start_1 = $temp_1; $hash = sprintf("%016b", $temp_2 % 65521) . sprintf("%016b", $temp_1 % 65521); Переменная $hash после выполнения кода содержит строку: 11011100010001110001000011001111 Найдите 10 отличий. Хеш-суммы совпадают, а поэтому с полной уверенностью заявляю, что мы сделали всё верно! Со следующего байта уже начинается чанк IEND, с IDAT же мы наконец-то закончили. Стоит признать, что это было довольно просто. В пункте про алгоритм Deflate мы также рассмотрим декодирование строки (да, для примера возьмем обычную строку) с динамическими кодами Хаффмана. IENDОбязательный чанк, который должен следовать после всех остальных. Символизирует окончание PNG-документа и не содержит какой-либо информации. DeflateЧтобы сильно не утомлять моего читателя, который к этому моменту мог уже слегка подустать, расскажу лишь то, что встречалось выше. Данные в PNG хранятся в формате zlib и представляют собой последовательность блоков, сжатых при помощи Deflate. Deflate — это алгоритм сжатия, комбинирующий LZ77 и метод Хаффмана. Если очень коротко, то несжатая последовательность обрабатывается при помощи LZ77, после чего получившиеся коды упаковываются при помощи алгоритма Хаффмана. LZ77Сам алгоритм довольно сложный, поэтому объясню его принцип, что называется, «на пальцах». LZ77 — это алгоритм сжатия без потерь, основанный на принципе «скользящего окна» (помните я писал про размер окна?), призванный заменять последовательности, встречающиеся чаще одного раза, на ссылки, указывающие на самые ранних из них. Что я имею в виду? Программа поочерёдно считывает последовательность битов, держа «в голове» (то есть в буфере) информацию об уже прочитанных битах. Когда программа натыкается на последовательность, которая уже содержится в буфере, то она полностью заменяется ссылкой, которая представляет собой сведения о смещении и длине последовательности. Смещение может быть как прямым (то есть начинаться от начала окна, либо от произвольной точки), так и обратным (отсчитываться смещение будет в обратном порядке относительно обрабатываемого бита). На самом деле, я не особо уверен в существовании прямого смещения, так как на практике не встречал, но в разных документах я видел упоминания о нём . Проще говоря, программа-интерпретатор получает указания отступить на n шагов назад и взять m байтов. Размер окна — это и есть размер нашего буфера, то есть расстояние от первого бита, который программа еще помнит, до первого бита, который программа уже помнит. Во время кодирования, программа без проблем может заменять комбинации, которые пока еще лежат за пределами окна. Алгоритм ХаффманаЕще один алгоритм сжатия без потерь, заменяющий все символы входящей последовательности на специальные коды таким образом, что самые часто встречающие символы образуют самые короткие коды. Алгоритм пробегается по строке, подсчитывая частоту вхождения каждого символа, потом выстраивается очередь с приоритетом, где самыми первыми встраиваются элементы с наименьшей частотой. После чего выстраивается бинарное дерево, в котором каждый символ является концевой вершиной. В конце концов каждый символ получает свой код исходя из того, насколько далеко он располагается относительно корня. Есть смысл объяснять подробнее? Ладно, уговорили. Допустим, у нас есть строка: «Hello, World!». Поехали: 1. Сначала выстраиваем список «Символ — частота»: H - 1 e - 1 l - 3 o - 2 , - 1 W - 1 r - 1 d - 1 ! - 1 2. Сортируем его по частоте и создаем очередь. Приоритетом является частота. При этом, элементы с самым низким приоритетом выстраиваются в самом начале: | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | | H | e | , | W | r | d | ! | o | l | 3. Теперь создаем бинарное дерево. Алгоритм такой: Берем первые два элемента и формируем из них мини-дерево, где листьями будут наши элементы. В таблицу записываем сумму приоритетов, помещая его в нужное место: | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | | , | W | r | d | ! | o | / \ | l | H e Таким же образом делаем со всеми остальными. В итоге получается такое дерево: | 11 | / \ /\ / \ l /\ /\ /\ o /\ , w r w H e Общий приоритет — 11. Теперь присвоим коды. Каждая левая ветка — 0, правая — 1. В итоге получается что-то вроде этого: L - 00 o - 010 H - 0110 e - 0111 , - 100 w - 101 r - 110 d - 111 Теперь нужно заменить нашу последовательность полученными кодами и выстроить таблицу, чтобы интерпретатор мог без проблем её декодировать. В принципе, это всё. Ближе к темеЯ уже выше писал, но напомню еще раз. Данные состоят из блоков, следующих друг за другом последовательно. Каждый из них содержит заголовок, состоящий из 3 битов (RFC 1950):
«Без сжатия» означает, что данные представлены в нетронутом виде. Мы рассмотрели работу с подобными данными в подпункте IDAT пункта «структура PNG». Для урока я взял простую последовательность, которая не включает в себя длины и смещения. Тем не менее, работать с подобными данными мы уже умеем, так как это было рассмотрено выше, а метод сжатия значения не имеет, ибо всё происходит точно так же. Также уточню, что строка ниже не содержит заголовка zlib и контрольной суммы. Мы рассматриваем только Deflate. Пример Deflate с динамическими кодами ХаффманаПредположим, у нас есть следующая последовательность: 05 A0 61 0B 00 00 18 86 2E 68 8F EA D9 3D AE C7 B4 9B 10 E8 FF 40 21 07 14 56 5A DA В двоичном представлении: 00000101 10100000 01100001 00001011 00000000 00000000 00011000 10000110 00101110 01101000 10001111 11101010 11011001 00111101 10101110 11000111 10110100 10011011 00010000 11101000 11111111 01000000 00100001 00000111 00010100 01010110 01011010 11011010 Считываем по байтам, биты от младшего к старшему. Первые 3 байта — заголовок: HLIT — 5 бит, которое равно: количество_длин_и_символов минус 257. В нашем случае, 0, значит количество длин и символов — 257. Давайте ненадолго остановимся и рассмотрим всё это. Блок с динамическими кодами состоит из следующих частей (исключая заголовок и описание длин): 1. Сначала следуют трёхбитовые длины команд и кодов, которых FCLEN + 4. Длины нам помогут декодировать наши значения. Длина - код 2 - 00 3 - 010 4 - 0110 4 - 0111 4 - 1000 Еще раз, если не очень понятно. Если у нас одна длина, то увеличиваем значение на 1. Если длина меняется — увеличиваем на единицу и дописываем 0. Таким образом мы избавляемся от префиксов, то есть мы уверены, что ни один из кодов не является подстрокой для другого. А это позволяет интерпретатору однозначно декодировать значения. Удобно, правда? Внимательность: в первой части мы получаем лишь длины, которые в последствии пригодятся при декодировании. Мы получаем длины тем же способом, что я описал выше. Коды и команды следуют в следующем порядке: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15. 2. Далее идёт последовательность из HLIT + 257 команд и значений закодированных символов, которые можно найти, исходя из их позиции в потоке данных (на примере я объясню этот момент). В предыдущем блоке мы получили их длины. Теперь же мы сможем сопоставить распакованное значение и длину кода, которым оно закодировано. Используя приведённый выше алгоритм, зная длины кодов и их значения, мы без проблем найдем сами коды. 3. Последним идёт блок со сжатыми данными. На этом этапе мы уже знаем коды и их значения (или длины и смещения). Поэтому без проблем можем декодировать строку. Если у вас каша в голове, то не переживайте, сейчас на примере мы всё разберём. Поехали! Итак, берём HCLEN + 4 (15) трёхбитовых значений: |16 | 17 | 18 | 0 | 8 | 7 | 9 | 6 | 10 | 5 | 11 | 4 | 12 | 3 | 13 | 2 | |000 | 011 | 011 | 010 | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 011 | 000 | 011 | 000 | 010 | Отбросим все значение, где длина равна 0 и переведём в десятичную систему: 0 - 2 2 - 2 3 - 3 4 - 3 17 - 3 18 - 3 Теперь восстанавливаем коды длин: 0 - 00 2 - 01 3 - 100 4 - 101 17 - 110 18 - 111 Затем у нас следуют 257 длин и команд. Здесь мы и применяем наши длины символов и команд. Давайте я покажу как найти значение. Допустим, возьмём первый код. Благодаря тому, что у нас отсутствуют префиксы, мы можем правильно определить коды. Первый код в нашем потоке — это 111. Смотрим выше и понимаем, что 111 соответствует 18. Смотрим еще выше и вспоминаем, что 18 это команда. Нам требуется еще 7 битов, возьмем же их — 0100000 (32). Это значит, что нам нужно повторить значение 0 32 раза. Самый первый символ имеет позицию 0. Если мы «передвинемся» по нашей последовательности на 32 бита вправо (включая 0), то окажемся на 31 бите. Это всё. Длина/команда - значение/повторения. Если 0 - просто делаем еще один шаг. | 18 | 32 | 4 - 32 | 4 - 33 | 18 - 10 | 4 - 44 | 18 - 27 | 4 - 72 | 18 - 14 | 4 - 87 | 18 - 12 | 4 - 100 | 4 - 101 | | 111 | 0100000 | 101 | 101 | 111 0001010 | 101 | 111 0011011 | 101 | 111 0001110 | 101 | 111 0001100 | 101 | 101 | | 17 - 6 | 2 - 108 | 0 | 0 | 3 - 111 | 0 | 0 | 4 - 114 | 18 - 138 | 0 | 0 | 0 | 256 | 0 | 110 110 | 01 | 00 | 00 | 100 | 00 | 00 | 101 | 111 1111111 | 00 | 00 | 00 | 101 | 00 | В мы рассматривали, как с помощью регулярных выражений можно восстановить данные даже после переформатирования накопителя. Эта статья посвящена анализу структуры файла — второму подходу, используемому в режиме «черновое восстановление». Он намного более точен в определении начала файла и, в зависимости от формата, позволяет узнать полный размер, целостность и размер целой части файла. Возьмем форматы BMP и PNG, которые используются для хранения растровых изображений, и на их примере рассмотрим какие возможности могут быть получены с помощью анализа структуры. Формат BMPОписание формата можно найти, например, на сайте Microsoft или в Wikipedia (русская и английская). Если оставить только значимые для нас подробности, то файл BMP выглядит следующим образом: Упрощенная структура файл BMP Где Bitmap File Header – это структура следующего вида: Здесь важно, что
Благодаря заголовку мы можем:
С помощью полей этой структуры можно выполнить дополнительные проверки, которые снизят шанс ложного срабатывания:
Большую часть файла занимают данные изображения. В большинстве случаев, это несжатые данные. Цвет каждого пикселя кодируется определенным числом бит, а затем они записывают последовательно друг за другом. Это, к сожалению, означает, что данные могут быть произвольными и их проверить никак нельзя. Подведем итог. Формат BMP позволяет достаточно точно находить начало файлов и точно определять их полный размер, даже для поврежденных файлов. Но нет возможности узнать целый файл или нет, а также узнать размер валидной части, если он поврежден. Формат PNGPNG – еще один формат хранения растровых изображений, но уже со сжатием (но без потери качества как в jpeg). Его спецификацию можно найти на сайте W3C . Она занимает не один десяток печатных страниц. Однако, для восстановления данных достаточно знать совсем немного. Любой файл PNG начинается с последовательности из 8 байт: 89 50 4E 47 0D 0A 1A 0A. Затем идет последовательность chunk’ов - кусочков на которые разбит весь png файл. Упрощенная структура файла PNG Структура chunk’а: То есть, для каждого chunk’а указаны:
И последнее, что нужно знать -последовательность chunk’ов не может быть произвольной. В спецификации приведены 2 схемы следования chunk’ов друг за другом: Последовательность chunk’ов с PLTE Последовательность chunk’ов без PLTE Внутри прямоугольника записан тип chunk’а. Черта «|» означает, что должен быть или один или другой chunk. А символы сверху обозначают сколько раз он может встречаться:
Такой формат очень удобен для поиска и проверки файла:
В отличии же от формата BMP, для поврежденного файла нельзя узнать его полный размер. С каким размером сохранять найденные файлы?Мы разобрались с тем, какие возможности для восстановления данных заложены в форматах BMP и PNG. Рассмотрим теперь различные случаи с целыми и поврежденными файлами. Это поможет нам правильно интерпретировать результаты поиска. При поиске по шаблону GREP мы выставляли размер до следующего найденного заголовка, другого способа узнать размер у нас не было. Анализ структуры может дать больше информации, но и логика принятия решения здесь сложнее. Когда мы находим файл BMP, мы имеем информацию только о его полном размере и можем проверить лишь небольшую часть в начале. Нельзя ручаться за данные, которые находятся после проверенного размера. Если файл, например, фрагментирован, то следующий заголовок может быть найден уже внутри «полного размера»: В этой ситуации размер файла при сохранении из режима ограничивается смещением до следующего заголовка, чтобы наверняка захватить целую часть (ее мы не можем определить автоматически). Если внутри «полного размера» других заголовков не найдено, то он и будет использован, т.к. сохранять больше данных нет смысла. Возможно это целый файл, для которого схема будет выглядеть уже так: Если мы нашли целый PNG файл, то все очень просто. Мы проверили его от начала до конца, знаем его размер и уверены, что он целый. Более сложная ситуация, если PNG файл поврежден. Нам не удалось проверить очередной chunk, поэтому известно, что файл поврежден. Проверенный размер будет покрывать все целые chunk’и. Целая часть может оказаться больше. Файл будет сохранен до следующего заголовка, т. к. полный размер неизвестен (его можно получить только проверив успешно файл до конца). Форма «чернового восстановления»Форма режима «черновое восстановление» С помощью анализа структуры мы можем получить значительно больше информации чем при простом поиске по шаблонам GREP. Рассмотрим как она отображается на форме чернового восстановления. В «черновом восстановлении» файлы ищутся как с помощью шаблонов GREP, так и с помощью анализа структуры. Поле GREP на панели с категориями заполнено только у первых. Записи на панели с результатами тоже отличаются.
В режиме есть панель «метаданные», в нее попадает различная полезная информация, полученная при анализе файла по структуре. Например, для Boot NTFS (на скриншоте) можно узнать размер раздела, размер кластера, кластер с MFT0 и его копией. Пример с картой памяти из фотоаппаратаВ прошлой статье был пример с отформатированной картой памяти. Тогда мы не использовали анализ внутренней структуры файлов. Теперь выполним поиск с параметрами по-умолчанию. Результаты выполнения «чернового восстановления» Мы нашли такое же количество файлов JPEG. Однако результата стал намного более наглядным и точным:
ЗаключениеНа примере форматов BMP и PNG мы разобрали как в «черновом восстановлении» ищутся файлы на основе знаний о структуре. Очевидно, что такой подход дает намного более качественный результат, чем поиск с помощью регулярных выражений. Но алгоритмы проверки - это часть комплекса, и их нельзя добавить также легко как очередной шаблон GREP. Изначально, режим «черновое восстановление» разрабатывался как последний рубеж при восстановлении данных. Он применялся лишь в тех случаях, когда остальные методы не дали удовлетворительных результатов. Но с развитием комплекса режим стал находить все больше применений при решении самых разных задач. О них мы обязательно напишем в следующих статьях. Леоненко Александр Статьи по теме:
Надоела стандартная раскладка клавиш?
Приложения для Android: обучающие программы для детей
Power bi отчет с 1с. BI - системы. Критерии для оценки качества IT-решения
Почему не работают USB порты на компьютере?
Как Zello рация для Андроид помогает водителям
Новое:
Популярное:
|