CyRax
Упаковка чисел

Что описывается в этой статье

    В данной статье описывается упаковка чисел, применяемая в алгоритме LZW графического файла формата GIF. Сжатие данных по словарю не описывается и будет описано в следующей статье. Алгоритмы программной реализации упаковки и распаковки придуманы мной и могут не соответствовать стандартам Compuserve и Unisys. Напомню, что срок действия патента на технологию LZW истек в этом году.

Что такое упаковка чисел

    Для хранения чисел в ЭВМ существуют специальные отсеки фиксированной длины. Это так называемые переменные, которые на самом деле являются отвлечённым представлением регистров процессора и ячеек памяти. Эти переменные можно сравнить со строками фиксированной длины. То есть в них можно уместить только определённое их границами количество данных.
    Числа в переменных расположены строго упорядочено, и если отсек хранения чисел заполнен не полностью, то оставшееся место просто занимает память. Для одного числа это не существенно, но чем больше используется таких не полностью заполненных отсеков, тем больше остаётся неиспользованного пространства.
    При упаковке чисел данные переменной длины располагаются внутри хранилища данных фиксированного размера. За стандарт такого хранилища принимается ячейка памяти размером в байт.

Что такое данные переменной длины

    Ограничение длины переменных обусловлено физическими характеристиками ЭВМ, в которой для хранения данных используется массив следующих друг за другом ячеек памяти фиксированной длины. При этом условно выбирается сколько таких ячеек выделяется для хранения чисел опять же условных типов данных. Данный алгоритм позволяет отсеку хранения данных расширяться в зависимости от длины поступающих данных. Этот процесс необратим и размер такого хранилища не может сузится до конца работы алгоритма.
    Отсюда следует, что тип переменной расширяется по мере заполнения данных. Назовём такой тип данных расширяемым.
    Вначале расширяемый тип имеет какую то минимальную фиксированную длину. Как только длина данных увеличивается, увеличивается и длина типа.

=
===
=====
=======

Рис. 1 (устройство любого хранилища данных)

    Как видно на рисунке 1, ячейка хранения данных сужена вначале и расширяется по мере углубления в неё данных. Поступающие в ячейку данные тоже расположены в ней не хаотично, а располагаются строго в соответствующем разряде своей длины. Например, единичные числа могут занимать только верхнюю ступеньку хранилища, десятки идут ниже, сотни ещё ниже и так до самого дна. Поступающие данные накапливаются в разряде своей длины до тех пор, пока не наберут массу, критическую для данного разряда. В этом случае данные переходят в более крупный разряд. И если в ячейке фиксированной длины количество разрядов определено заранее, то в расширяющейся ячейке новый, более крупный разряд присоединяется и критические данные предыдущих разрядов переходят в него (рис 2).

0 |
000 |
00000 | 
1111111 <-

Рис. 2 (присоединение разряда)


    Отличие расширяющегося типа от фиксированных типов заключается в поступательном расширении длины такого типа. В расширяющемся типе минимальным стартовым размером является 1 бит. Что, однако, не определяет жесткую нижнюю границу размера расширяемого типа. Стартовый размер типа может иметь любое значение. К примеру, вначале данные хранились как тип Byte, но постепенно тип может изменится на Integer, Long и так далее.
    При расширении типа следует учитывать следующие правила:

• Значение, расширяющее тип, должно находится в диапазоне значений следующего разряда. Например, если текущая длина типа равна 8 битам, то длина значения, расширяющего тип, не должна превышать 9 бит.

• При расширении типа последнее значение "текущего типа" должно равняться пороговому значению для этого типа. Это позволит распаковщику определить позицию расширения типа.
   

Пример: 55...0...24...[99...133]...125...44...178...1...102...[999...

    Данный пример представлен для наглядности. Следует не забывать, что длины разрядов в ЭВМ ориентированы на двоичную систему счисления. И если в примере позиция разряда это число 10 в степени номер разряда (Например, разряд 3 - это 10³ степени), то в ЭВМ это 2 в степени номер разряда (разряд 3 - это 2³ степени).
    Нужно уточнить что при расширении типа должна обязательно идти пара [Максимальное число текущего диапазона... Число следующего диапазона]. Причём Максимальное число текущего диапазона может встречаться в текущем диапазоне только один раз. Сразу же за ним должно идти число, расширяющее тип. В противном случае упаковщик и распаковщик не поймут друг друга. Максимальное число текущего диапазона можно потом применять в следующем диапазоне. Оно уже не повлияет на расширение типа. При паковке данных следует учесть это правило.

Примечание

    Данное правило никак не связанно с алгоритмом LZW, так как в нём данные идут строго последовательно и меньшее число не может идти после большего.
    Поступающие в переменную расширяющегося типа данные равные или меньшие текущей длине типа могут быть любого размера и поступать в любом порядке. Но данные, расширяющие тип (т.е. их длина больше текущей длины типа) должны быть сортированы в порядке возрастания. Это позволит наиболее эффективно упаковывать данные внутри такой переменной. Наиболее эффективным является поступательное расширение типа с шагом 1. Реализованный мной пример именно так и построен.
    Исходя из строения типа можно увидеть что наибольшую пользу можно извлечь из маленьких чисел. Если это допустимо, то желательно группировать числа по их размеру. Это позволит добиться наибольшей степени упаковки. Сначала должны идти самые маленькие числа, затем числа большей длины и так далее. Например, сначала упаковывается массив 2-х битных чисел, затем за ними следуют 3-х битные и т.д.

Упаковка

    Современные ЭВМ не поддерживают типы переменной длины. Поэтому эти типы базированы на минимальных ячейках фиксированной длины.

00000000 00011111 11111000 00000000
00000000 00011111 11111000 00000000
00000000 00011111 11111000 00000000
00000000 00011111 11111000 00000000
Ф Ф П Ф Ф

Рис. 3 Способ расположения данных в ячейках фиксированной длины.

    При заполнении фиксированного отсека данными из расширяющегося типа необходимо учитывать размер фиксированного типа и текущий размер переменного. Фиксированные типы постоянны и не изменяют своего размера. Это значительно облегчает написание алгоритма помещения в них данных.
    Упаковка в пределах приёмника осуществляется справа налево, но цепочка ячеек располагается слева направо. При этом числовые данные не переворачиваются. На рисунке 4 приведён пример упаковки 10-битного числа.

11111111 00000011 00000000 
11111111 00000011 00000000 
11111111 00000011 00000000
11111111 00000011 00000000

Рис. 4 Упаковка 10-ти битного числа.

00000000 11111100 00001111 
00000000 11111100 00001111 
00000000 11111100 00001111 
00000000 11111100 00001111 

Рис. 4.1 Следующее 10-ти битное число (предыдущее условно отсутствует).

    Число помещается в правую часть приёмника, следующее число располагается левее и т.д. до конца фиксированного отсека. Если данные не вместились в длину принимающей ячейки, то они переносятся в начало следующей за ней ячейки. А так как числа упаковываются справа налево, то непоместившаяся часть данных окажется справа (рис 4).

Алгоритм упаковки

Входные данные:
Источник - массив чисел типа Integer (16 битное знаковое целое);
Приёмник - массив чисел типа Byte (8 битное беззнаковое целое);
Длина типа - стартовый размер типа в битах;
Размерности массивов источника и приёмника должны быть определены заранее.

Переменные:
Порог типа - текущее максимально допустимое значение типа. Зависит от количества бит заданных в "Длине типа";
Счётчик байтов - указывает на текущий индекс в байтовом массиве приёмника;
Счётчик битов - указывает на текущий индекс бита в текущем элементе массива приёмника.

Вычисления:
Увеличить Длину типа на 1
Порог типа = (2^{Длина типа})-1

Перебрать массив источника от начала и до конца с шагом 1
    Если значение текущего элемента источника больше Порога типа то
        Увеличить Длину типа
        Занести максимально допустимое значение для этой длины в Порог типа
    Конец Если
        Перебрать биты источника от начала и до Длины типа с шагом 1
    Если бит источника включен то
        Включить бит в приёмнике по текущим позициям счётчиков битов и байтов.
    Конец Если
        Увеличить Счётчик битов приёмника на 1
    Если Счётчик битов приёмника равен 8 (длина байта) то
        Увеличить Счётчик байтов приёмника (перейти на следующий элемент массива)
        Сбросить счётчик битов приёмника
    Конец Если
Продолжить перебор битов источника
Продолжить перебор элементов массива источника
Синхронизировать последние элементы приёмника и источника
Выдать количество использованных байт в приёмнике


Реализация в Visual Basic 6

Function PackNumbers(SrcArray() As Integer, DstArray() As Byte, ByVal BitsCount _
As Byte) As Long
    Dim CodeSize As Integer, DstByteCounter As Long, DstBitCounter As Byte
    BitsCount = BitsCount + 1: CodeSize = (2 ^ BitsCount) - 1

    For EnumValues = 0 To UBound(SrcArray)
        If SrcArray(EnumValues) > CodeSize Then BitsCount = BitsCount + 1
	CodeSize = (2 ^ BitsCount) - 1
        For PackToByte = 0 To BitsCount - 1
            If CBool(SrcArray(EnumValues) And 2 ^ PackToByte) Then
                DstArray(DstByteCounter) = DstArray(DstByteCounter) + (2 ^ DstBitCounter)
            End If
            DstBitCounter = DstBitCounter + 1: If DstBitCounter = 8 Then DstBitCounter = 0
            DstByteCounter = DstByteCounter + 1
        Next PackToByte
    Next EnumValues
    
    If DstArray(DstByteCounter) = 0 And SrcArray(UBound(SrcArray)) > 0 Then _
    DstByteCounter = DstByteCounter - 1
    PackNumbers = DstByteCounter
End Function

Примечание

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

Распаковка

    Напомню, что данные хранятся в цепочке переменных расширяющегося типа, которые в свою очередь упакованы внутри цепочки переменных фиксированного типа Byte.

Данные упакованы следующим образом:
    Имеется стартовая длина типа, и все последующие данные имеют эту длину до тех пор, пока не встретится значение, больше допустимого значения для текущего типа. Тогда длина типа расширяется до такого размера, который позволяет вместить это значение. Все последующие данные будут иметь новую длину до тех пор, пока не встретят значение большего размера.
    Перед расширением типа его значение должно равняться максимально допустимому (пороговому) значению текущего типа, что позволит распаковщику определить позицию, по которой начинаются данные нового размера.


Алгоритм распаковки

Входные данные:
Источник - массив чисел типа Byte (8 битное беззнаковое целое);
Приёмник - массив чисел типа Integer (16 битное знаковое целое);
Длина типа - стартовый размер типа в битах;
Размерности массивов источника и приёмника должны быть определены заранее.


Переменные:
Порог типа - текущее максимально допустимое значение для типа. Зависит от количества бит заданных в "Длине типа";
Счётчик слов - содержит индекс текущего элемента массива;
Счётчик битов - индекс текущего бита текущего элемента массива приёмника.
Промежуточный буфер - переменная типа Long (32 битное знаковое целое) введённая для преодоления искусственных ограничений (установленных разработчиком модификации языка) типа Integer в VB6. Может быть заменена на беззнаковое 16-битное целое или знаковое с полной поддержкой диапазона значений.

Вычисления:
Увеличить Длину типа на 1
Порог типа = (2^{Длина типа})-1
Перебрать в цикле все элементы источника с шагом 1
Перебрать в цикле все биты текущего элемента источника (от 0 до 7)
    Если текущий бит текущего элемента источника = Истина то
        Установить текущий бит Промежуточного буфера в истину
    Конец Если
Увеличить счётчик битов Промежуточного буфера на 1
    Если счётчик битов Промежуточного буфера = Длине типа то
        Увеличить Длину типа
        Порог типа = (2^Длина типа)-1
    Конец Если
    Если значение Промежуточного буфера = Порог типа то
        Переслать значение из Промежуточного буфера в текущий элемент массива приёмника
        Очистить Промежуточный буфер
        Сбросить счётчик битов приёмника
        Увеличить счётчик слов приёмника на 1
    Конец если
Продолжить перебор битов в источнике
Продолжить перебор элементов массива источника
Синхронизировать последние элементы приёмника и источника
Выдать количество использованных слов в приёмнике


Реализация в Visual Basic 6

Function UnPackNumbers(SrcArray() As Byte, DstArray() As Integer, ByVal BitsCount As Byte) _
As Long
    Dim CodeSize As Long
    BitsCount = BitsCount + 1: CodeSize = (2 ^ BitsCount) - 1
    Dim IntBitsCounter As Byte, IntArrayIdx As Long, Buffer As Long
    
    For EnumValues = 0 To UBound(SrcArray)
        For RestoreBits = 0 To 7
            If CBool(SrcArray(EnumValues) And 2 ^ RestoreBits) Then
                Buffer = Buffer + (2 ^ IntBitsCounter)
            End If
            IntBitsCounter = IntBitsCounter + 1
            If IntBitsCounter = BitsCount Then
            If Buffer = CodeSize Then BitsCount = BitsCount + 1: CodeSize = (2 ^ BitsCount) - 1
                CopyMemory ByVal VarPtr(DstArray(IntArrayIdx)), ByVal VarPtr(Buffer), 2
                Buffer = 0
                IntBitsCounter = 0: IntArrayIdx = IntArrayIdx + 1
            End If
        Next RestoreBits
    Next EnumValues
If DstArray(IntArrayIdx) = 0 And SrcArray(UBound(SrcArray)) > 0 Then IntArrayIdx = _
IntArrayIdx - 1
UnPackNumbers = IntArrayIdx
End Function

Примечания

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

Автор: CyRax (BASIC Production)