1 /******************************************************************************
2 *
3 * Copyright (C) 2009, The Gentee Group. All rights reserved.
4 * This file is part of the Gentee open source project - http://www.gentee.com.
5 *
6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT").
7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS
8 * ACCEPTANCE OF THE AGREEMENT.
9 *
10 * Author: Alexey Krivonogov ( gentee )
11 *
12 ******************************************************************************/
13
14 #ifndef _HUFFMAN_
15 #define _HUFFMAN_
16
17 #include "../gea.h"
18
19 #ifdef __cplusplus
20 extern "C" {
21 #endif // __cplusplus
22
23 //--------------------------------------------------------------------------
24
25 struct hufleaf_tag;
26 typedef struct hufleaf_tag * pshufleaf;
27
28 // лист дерева для символа алфавита
29 typedef struct hufleaf_tag
30 {
31 // word code; // значение литеры
32 dword freq; // частота вхождения
33 pshufleaf up; // указатель на верхний элемент
34 pshufleaf left; // указатель на левый элемент
35 pshufleaf right; // указатель на правый элемент
36 } shufleaf;
37
38 // Хафман
39 typedef struct
40 {
41 dword numcode; // размер алфавита
42 dword allcode; // общее количество узлов
43 pshufleaf root; // верхний элемент дерева
44 pshufleaf tree; // дерево алфавита
45
46 pbyte stack; // Стэк вывода
47 dword min; // Минимальная глубина элементов
48 dword max; // Максимальная глубина элементов
49 // dword pretree; // 1 если pretree хафмана
50 pbyte ptr; // Указатель вывода
51 dword bit; // Номер бита
52 dword fixed; // Упаковывать дерево фиксированными кодами
53 // Иначе строим еще одно дерево длин
54 pbyte prevlen; // Предыдущие длины
55
56 pdword normalize; // Для huf_normalize
57 pdword freq; // Для huf_detree
58 } shuf, * pshuf;
59
60 #define PRET_MAXCODE 15 // Максимально кодируемая глубина
61 #define PRET_ALPHABET 20 // Алфавит дерева упаковки
62 //#define PRET_MAXZERO 47 // Максимальный повтор 0
63 #define PRET_MAXZERO 87 // Максимальный повтор 0
64
65 #define PRET_OFF1 4
66 #define PRET_OFF2 8
67 #define PRET_OFF3 24
68
69 #define PRET_ZERO2 16 // Следом идет 2 bit для 0 4 - 7
70 //#define PRET_ZERO3 16 // Следом идет 3 bit для 0 4 - 11
71 //#define PRET_ZERO3 17 // Следом идет 3 bit для 0 8 - 15
72 #define PRET_ZERO4 17 // Следом идет 4 bit для 0 8 - 23
73 //#define PRET_ZERO5 18 // Следом идет 5 bit для 0 16 - 47
74 #define PRET_ZERO6 18 // Следом идет 6 bit для 0 24 - 87
75 #define PRET_BIG 19 // Следом идет bits для длины > PRET_MAXCODE
76
77
78 //--------------------------------------------------------------------------
79 /* Формат записи дерева Хаффмана
80 [1] 3 b - сколько бит отводить на значения min, max - min + 1
81 0 - не менять дерево
82 [1] b - Минимальная глубина дерева
83 [1] b - Диапазон глубин
84
85 fixed
86 numcode * [1] - глубины для всех символов
87
88 not fixed
89
90
91 20 * [1] b - длины pre-tree
92
93 2 b - Сдвиг значений длин. Добавляется к ненулевой длине.
94 0 1 2 3
95
96 */
97 //--------------------------------------------------------------------------
98 // Common fucntions
99 pshuf STDCALL huf_new( pshuf huf, dword alphabet );
100 void STDCALL huf_destroy( pshuf huf );
101 void STDCALL huf_normilize( pshuf huf );
102
103 // Compression functions
104 void STDCALL huf_build( pshuf huf );
105 void STACKAPI huf_outbits( pshuf huf, dword item );
106 dword STACKAPI huf_bits( pshuf huf, dword item );
107 void STACKAPI huf_incfreq( pshuf huf, dword item );
108 void STACKAPI huf_packnum( pshuf huf, dword val, dword bits );
109
110 // Decompression functions
111 void STDCALL huf_detree( pshuf huf );
112 dword STACKAPI huf_inbits( pshuf huf );
113 dword STACKAPI huf_unpacknum( pshuf huf, dword bits );
114
115
116 //--------------------------------------------------------------------------
117
118 #ifdef __cplusplus
119 }
120 #endif // __cplusplus
121
122 #endif // _HUFFMAN_