{ Типы данных для реализации метода сжатия Хафмана }
{---------------------------------------------------------------------------
(c) Copyright	 Aleksandrov O.E., 1999

   Molecular Physics department, USTU, Ekaterinsburg, K-2, 620002, RUSSIA
   phone 75-47-15
   E-mail: aleks@dpt.ustu.ru

(c) Copyright Александров О.Е., 1999

   620002, Екатеринбург, К-2, УГТУ, Кафедра молекулярной физики
   тел. 75-47-15
   E-mail: aleks@dpt.ustu.ru
----------------------------------------------------------------------------}
Unit HufTypes;

INTERFACE

type
  { Порция данных, которыми будем оперировать (далее именуется байт).
   В данном случае это байт, но можно использовать и слово (WORD - два байта).}
  tByte=byte;
{  tByte=word;}

  { ВНИМАНИЕ! использование WORD не тестировалось и ассемблерные процедуры
   требуют переработки для работы с WORD.}

const
  { Размер tByte в битах}
  cSizeOftByteInBits=8*SizeOf(tByte);


type
  tByteBitsCounter=0..cSizeOftByteInBits;
{  tDByte=0..(High(tByte) shl cSizeOftByteInBits+High(tByte));}

{ Типы для буфера данных ------------------- }
const
  { Максимальная длина обрабатываемого буфера }
  cMaxBufferLength={$IfDef Delphi}(High(integer)-1024)
		   {$Else}        (High(word)-16){$EndIf} div SizeOf(tByte);

  cMaxByteBufferLength={$IfDef Delphi}(High(integer)-1024)
		   {$Else}        (High(word)-16){$EndIf};
type
  { Максимальное целое }
  tLargestInt={$IfDef Delphi}int64{$Else}longint{$EndIf};
  { Номер порции данных в буфере }
  tBufferIndex=0..cMaxBufferLength;
  tByteBufferIndex=0..cMaxByteBufferLength;
  { Буфер для сжатия данных }
  tBuffer=array[tBufferIndex] of tByte;
  tPBuffer=^tBuffer;
  tByteBuffer=array[tByteBufferIndex] of byte;
  tPByteBuffer=^tByteBuffer;
  { Счетчик частот вхождений байта в буфер }
  tFriquency=tBufferIndex;

{ Типы для буфера данных --END----------------- }

{ Типы для узлов таблицы ------------------- }

const
  { Число узлов в исходной таблице частот }
  cBaseNodeCount=High(tByte)+1;
  { Максимальное число узлов в дереве,
  включая исходную таблицу частот и доп. узлы}
  cMaxNodeCount=2*cBaseNodeCount-1;

type
  { Номер узла в массиве узлов }
  tNodeIndex=0..(cMaxNodeCount-1);
  { Номер узла исходной таблицы }
  tBaseNodeIndex=0..(cBaseNodeCount-1);
  { Ссылка на номер узла для построения дерева, -1 = пустая ссылка}
  tNodeReference=-1..High(tNodeIndex);

  { Номер индекса в массиве индексов (ссылок на узлы) }
  tIndex=tNodeIndex;

{ Типы для узлов таблицы  ---END---------------- }


{ Типы данных для хранения двоичных кодов  ------------------- }
const
  { максимальная длина битовой цепочки }
  cMaxCodeLengthInBits=High(tByte);
  { максимальная длина кода в словах }
  cMaxCodeLengthInWords=(cMaxCodeLengthInBits+15) div 16;
  { максимальная длина кода в байтах }
  cMaxCodeLengthInBytes=(cMaxCodeLengthInBits+7) div 8;
  { максимальная длина кода в максимальных порциях  }
  cMaxCodeLengthInMaxPortions=(cMaxCodeLengthInBits+15) div {$IfDef Delphi} 32 {$else} 16 {$endif};

type
  { Длина кода в битах }
  tCodeLength=0..cMaxCodeLengthInBits;
  { Массив слов для хранения кода }
  tCodeWords=array[0..Pred(cMaxCodeLengthInWords)] of word;
  { Массив байт для хранения кода }
  tCodeByteIndex=0..Pred(cMaxCodeLengthInBytes);
  tCodeBytes=array[tCodeByteIndex] of byte;
  { Массив максимальных порций для хранения кода }
  tCodeMaxPortion={$IfDef Delphi} cardinal {$else} word {$endif};
  tPCodeMaxPortion=^tCodeMaxPortion;
  tCodeMaxPortionIndex=0..Pred(cMaxCodeLengthInMaxPortions);
  tCodeMaxPortions=array[tCodeMaxPortionIndex] of tCodeMaxPortion;
  tCodeMaxPortionLength=0..SizeOf(tCodeMaxPortion)*8;
  tCodeBits=set of byte;

  { Битовый код символа }
  tCodeData=record
    case byte of
      0:(Words:tCodeWords; AdditionalByte:byte); {последовательность слов кода}
      1:(Bytes:tCodeBytes); {последовательность байт кода}
      2:(FirstByte:byte);   {первый байт кода}
      3:(MaxPortions:tCodeMaxPortions); {последовательность макс. порций кода}
      4:(Bits:tCodeBits);   {последовательность бит  кода}
  end;
  tPCodeData=^tCodeData;

  { Данные по двоичной кодировке }
  tCode=packed record
     Length:tCodeLength; { длина битового кода в битах}
     Code:tCodeData;     { битовый код }
  end;
  tPCode=^tCode;

  { Массив кодов для исходой таблицы }
  tCodes=packed array[tBaseNodeIndex] of tCode;
  tPCodes=^tCodes;

  { Данные по двоичной кодировке }
  tCode8=packed record
     Node:tNodeReference;
     Length:tCodeLength; { длина битового кода в битах}
     Code:byte;     { битовый код }
  end;
  tPCode8=^tCode8;

  { Массив кодов для исходой таблицы }
  tCodes8=packed array[tBaseNodeIndex] of tCode8;

{ Типы данных для хранения двоичных кодов  ---END---------------- }

type
{ Типы данных для хранения дерева ------------------- }

{ Формат данных для двоичного дерева метода Хаффмана:

Двоичное дерево метода Хаффмана (далее дерево) состоит из узлов.
  Максимальное возможное число узлов дерева равно удвоенной длине ПОЛНОЙ
исходной таблицы символов минус 1. Для байта (0..255 - всего 256 различных
значений) максимальное число узлов дерева равно 2*256-1 = 511 узлов.
  Поскольку желательно максимальное быстродействие при генерации дерева и
размер максимального дерева невелик, то программа размещает статический
массив узлов максимального размера. Элементы массива используются для
построения дерева.
  Так как для декодировки необходима информация о дереве и желательно
минимального размера (ее приходится записывать вместе с
кодированным буфером), то реально данные размещаются в виде двух массивов
а) часть, необходимая для декодировки (см. типы данных tNode, tNodes и
массив Nodes в tHuffman) и б) доп. данные, необходимые для построения дерева
и вычисления кода (см. типы данных tNodeData, tNodesData и массив NodesData
в tHuffman).

   Nodes
N:  0       1       2                                         511
  ┌───────┬───────┬───────┬────────────     ────────────────┬─────────┐
  │       │       │       │                                 │         │
  └───────┴───────┴───────┴────────────      ───────────────┴─────────┘
  NodesData
N:  0       1       2                                         511
  ┌───────┬───────┬───────┬────────────     ────────────────┬─────────┐
  │       │       │       │                                 │         │
  └───────┴───────┴───────┴────────────      ───────────────┴─────────┘

  ДАЛЕЕ МЫ БУДЕМ НАЗЫВАТЬ ОБА ЭТИХ МАССИВА "массив узлов дерева", не
различая частей.
N:  0       1       2                 255      256            511
  ┌───────┬───────┬───────┬─────  ──┬────────╥───────┬─  ───┬────────┐
  │       │       │       │         │        ║       │      │        │
  ╞═══════╪═══════╪═══════╪═════   ═╪════════╬═══════╪═  ═══╪════════╡
  │       │       │       │         │        ║       │      │        │
  └───────┴───────┴───────┴────   ──┴────────╫───────┴───  ─┴────────┘
  │            исходная таблица              ║     двоичное дерево   │
  └──────────────────────────────────────────╨───────────────────────┘

  Узлы с 0 по 255 используются как исходная таблица метода Хаффмана, а
узлы с 256 по 511 - для построения двоичного дерева. Ссылка на узел
производится по его номеру, узлы в массиве никогда не изменяют своего порядка.
  Каждый узел содержит следующие данные

  tNode
  ┌───────────────────────────────────────┐
  │  ссылка на предыдущий левый узел      │ (для узлов исходной таблицы = -1,
  ├───────────────────────────────────────┤ что интерпретируется программой
  │  ссылка на предыдущий правый узел     │ как "отсутствует предыдущий узел".
  ╞═══════════════════════════════════════╡
  │  частота вхождений для узла           │
  ├───────────────────────────────────────┤
  │  ссылка на следующий узел             │
  └───────────────────────────────────────┘

  В процессе построения дерева удобнее работать с упорядоченной по
возрастанию частоты вхождений последовательностью узлов. Для организации
упорядоченного списка узлов без изменения порядка в массиве узлов
используется индексный массив Indexes (см. типы данных tIndexes и
массив Indexes в tHuffman). Массив индексов представляет собой
последовательность ссылок на узлы (номеров узлов в массиве узлов),
расположенных в порядке возрастания частот вхождений.

Indexes
N:  0       1                                                  511
  ┌───────┬───────┬──────────────────────────────────────────┬───────┐
  │   Ni  │  Nj   │                                          │  Nk   │
  └───────┴───────┴──────────────────────────────────────────┴───────┘

Проще говоря для узлов любых двух индексов i<j выполняется:
частота вхождения для Nodes[Indexes[i]] меньше или равна частота вхождения
для Nodes[Indexes[j]].

  Алгоритм построения дерева следующий:

  1) Массив узлов заполняется начальными значениями

   Nodes
N:  0        1        2                                        511
  ┌───────┐┌───────┐┌───────┐┌───────┐┌───────┐              ┌───────┐
  │  -1   ││  -1   ││  -1   ││  -1   ││  -1   │              │  -1   │
  ├───────┤├───────┤├───────┤├───────┤├───────┤              ├───────┤
  │  -1   ││  -1   ││  -1   ││  -1   ││  -1   │              │  -1   │
  ╞═══════╡╞═══════╡╞═══════╡╞═══════╡╞═══════╡ ...          ╞═══════╡
  │  0    ││  0    ││  0    ││  0    ││  0    │              │  0    │
  ├───────┤├───────┤├───────┤├───────┤├───────┤              ├───────┤
  │  -1   ││  -1   ││  -1   ││  -1   ││  -1   │              │  -1   │
  └───────┘└───────┘└───────┘└───────┘└───────┘              └───────┘

  2) Массив индексов заполняется начальными значениями

Indexes
N:  0       1       2                                          511
  ┌───────┬───────┬──────┬───────────────────────────────────┬───────┐
  │   0   │  1    │  2   │                                   │  511  │
  └───────┴───────┴──────┴───────────────────────────────────┴───────┘

  4) Подсчитываются частоты вхождений для байтов в исходной таблице
  (узел[0]..узел[255]).

  5) Сортируется по возрастанию частот вхождений часть массива индексов,
  соответствующая исходной таблице (индекс[0]..индекс[255]).

Indexes
N:  0       1                            255     256           511
  ┌───────┬───────┬───────── ──────────┬───────╥───────┬── ──┬───────┐
  │  Ni   │  Nj   │                    │  Nk   ║ 256   │     │  511  │
  └───────┴───────┴───────── ──────────┴───────╨───────┴──── ┴───────┘

  3) Устанавливаются указатели (индексы)
     а) на первый ненулевой индекс (ссылающийся на узел со счетчиком вхождений
     большим 0) - далее IndexFirst.
     б) на максимальный индекс (ссылающийся на узел с максимальным счетчиком
     вхождений) - далее IndexLast.
     Данные индексы соответствуют началу и концу исходной таблицы.

Indexes
N:  0       1                                    255
  ┌───────┬───────┬─ ──────╥──────┬───── ──────┬───────╖   ──┬───────┐
  │  Ni   │  Nj   │        ║  Nl  │            │ Nk    ║     │ 511   │
  ├───────┴───────┴─ ──────╫──────┴──── ───────┴───────╢  ───┴───────┘
  │ ссылки на нулевые узлы ║   исходная таблица        ║
  └────────────────── ─────╫──────┬────── ─────┬───────╢
			   ║ First│            │ Last  ║
			   ╙──────┘            └───────╜
    Ссылки на нулевые узлы более не участвуют в построении дерева.

  4) Из исходной таблицы (индекс[IndexFirst]..индекс[IndexLast]) выбираются
  два левых узла: индекс[IndexFirst] и индекс[IndexFirst+1]
  (это узлы с минимальными частотами вхождений) и объединяются в новый узел.
  В качестве нового узла используется узел с номером индекс[IndexLast+1].

Indexes
N:  First First+1      Last    Last+1             511
 ─╥──────┬──────┬─ ───┬───────╥───────┬─      ──┬───────┐
  ║  Nf  │ Nf1  │     │ Nk    ║Last+1 │         │ 511   │
 ─╨──────┴──────┴── ──┴───────╨───────┴─     ───┴───────┘
    │ исходная│таблица            │ новый
    └┐        └───┐               │ узел
     │            │               │

Nodes
  ┌───────┐    ┌───────┐      ┌──────────┐
  │  -1   │    │  -1   │      │  Nf      │
  ├───────┤    ├───────┤      ├──────────┤
  │  -1   │    │  -1   │      │  Nf1     │
  ╞═══════╡ +  ╞═══════╡ ──>  ╞══════════╡
  │  ЧВ1  │    │  ЧВ2  │      │ЧВ=ЧВ1+ЧВ2│
  ├───────┤    ├───────┤      ├──────────┤
  │Last+1 │    │Last+1 │      │  -1      │
  └───────┘    └───────┘      └──────────┘

  5) Создается новая таблица частот.
    а) Два левых узла исходной таблицы удаляются, путем установки
       указателя IndexFirst:=IndexFirst+2.
    б) Новый узел добавляется в таблицу, путем установки указателя
       IndexLast:=IndexLast+1.
    в) Новая таблица (индекс[IndexFirst]..индекс[IndexLast]) сортируется по
       возрастанию частот вхождений (в программе применен метод
       вставки нового узла в упорядоченный массив делением пополам, а
       не прямая сортировка).

  6) Проверяется, количество узлов в таблице (IndexLast-IndexFirst+1), если
  это число больше 1, то повторяются шаги с пункта 4), иначе построение
  дерева считается законченным и индекс[IndexLast] указывает на корневой
  узел двоичного дерева. В массиве узлов узлы (0..255) содержат информацию
  по первоначальной таблице, а (256..IndexLast) содержат минимальную
  информацию по двоичному дереву, необходимую для декодировки.

  7) Вычисляются коды для элементов первоначальной таблицы (узлы(0..255)).

-------ПОСТРОЕНИЕ ДЕРЕВА ЗАКОНЧЕНО.

Детальное описание процедур см. текст програмы.
}

  { Ссылка на предыдущие узлы дерева }
  tUpNodesReference=packed record
    case byte of
     0:(Left,Right:tNodeReference); {левый,правый предыдущие узлы, если =-1, то нет преддыдущих}
     1:(Refs:array[0..1] of tNodeReference);
  end;

  { Узел (минимальные данные) для построения двоичного дерева.
  Это минимальная информация, необходимая для задания двоичного дерева и
  декодировки. }
  tNode=record
     UpperNodes:tUpNodesReference; { индексы предыдущих узлов,
				   если =-1, то нет преддыдущих }
  end;
  tPNode=^tNode;

  { Массив узлов для построения дерева }
  tNodes=array[tNodeIndex] of tNode;
  tPNodes=^tNodes;

  { Массив узлов дерева, без исходной таблицы.
  Это минимальный набор данных, необходимый для декодировки.}
  tTreeData=array[tBaseNodeIndex] of tNode;
  tPTreeData=^tTreeData;

  { Узел (дополнительные данные) для построения двоичного дерева.
  Счетчик и дополнительная информация, необходимая для вычисления кодов
  прямым проходом по дереву. }
  tNodeData=packed record
     Counter:tFriquency; { счетчик числа вхождений байта}
     NextNode:tNodeReference; { ссылка на следущий узел дерева }
     {$IfDef Delphi}Alignment:word;{т√Ёртэштрэшх фы  рёёхьсыхЁр}{$EndIf}
  end;
  tPNodeData=^tNodeData;

  { Массив доп. данных по узлам для построения дерева и вычисления кодов.}
  tNodesData=array[tNodeIndex] of tNodeData;
  tPNodesData=^tNodesData;

  { Массив индексов узлов для создания упорядоченной по возрастанию частот
  таблицы.}
  tIndexes=packed array[tIndex] of tNodeIndex;
  tPIndexes=^tIndexes;

  { Массив индексов БАЗОВЫХ узлов для создания упорядоченной по возрастанию частот
  таблицы.}
  tBaseIndexes=packed array[tBaseNodeIndex] of tBaseNodeIndex;
  tPBaseIndexes=^tBaseIndexes;

  tTreeIndexes=record
    { индекс корневого узла дерева }
    Root:tIndex;
    {номер узла с кодом минимальной длины }
    MinCode:tBaseNodeIndex;
    {номер узла с кодом максимальной длины }
    MaxCode:tBaseNodeIndex;
  end;

  tHuffmanBaseTreeData=record
    {массив узлов для построения дерева -
    минимальная информация, необходимая для декодировки }
    Nodes:tNodes;
    { индексы таблицы и дерева (начало, конец и т.п.)}
    TreeIndexes:tTreeIndexes
  end;

  tHuffmanFullTreeData=record
    BaseTree:tHuffmanBaseTreeData;
    {доп. данные по узлам}
    NodesData:tNodesData;
    {коды символов }
    Codes:tCodes;
  end;

{ Типы данных для хранения дерева ---END---------------- }

{ Типы данных для хранения таблицы-ускорителя декодировки ------------------- }
  tAccLen=tCodeLength;
  tDecodeAccelerator=packed record
    Node:tNodeReference;
    Length:tAccLen;
    Alignment:byte; {для выравнивания на 4 байта }
  end;
  tDecodeAccelerators=packed array[byte] of tDecodeAccelerator;

{ Типы данных для хранения таблицы-ускорителя декодировки ---END---------------- }

  tPointer=record
    Ofs,Seg:word;
  end;

  { Упакованное дерево }
  tPackedTreeHeader=record
    SizeInNodes:tByte;
  end;

const
{  cCode0:tCode=(Length:0; Code:(Words:(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0); AdditionalByte:0));}
{  cCode80:tCode8=(Node:-1; Length:0; Code:0);}
  cNode0:tNode=(UpperNodes:(Left:-1; Right:-1));

  cSizeOfNode =SizeOf(tNode);
  cSizeOfTByte=SizeOf(tByte);
  cSizeOfTCode=SizeOf(tCode);


IMPLEMENTATION

END.