Реклама

  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_