![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lzh.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Synchronet] / sbbs / sbbs2 / smb|
Return to lzh.c CVS log | Up to [Synchronet] / sbbs / sbbs2 / smb |
1.1 ! root 1: /* LZH.C */ ! 2: ! 3: /* Rob Swindell's conversion of 1988 LZH (LHarc) encoding functions */ ! 4: /* Based on Japanese version 29-NOV-1988 */ ! 5: /* LZSS coded by Haruhiko Okumura */ ! 6: /* Adaptive Huffman Coding coded by Haruyasu Yoshizaki */ ! 7: ! 8: ! 9: #include <stdio.h> ! 10: #include <stdlib.h> ! 11: #include <string.h> ! 12: #include <ctype.h> ! 13: #ifndef __WATCOMC__ ! 14: #include <alloc.h> ! 15: #endif ! 16: #include "lzh.h" ! 17: ! 18: /****************************************************************************/ ! 19: /* Memory allocation macros for various compilers and environments */ ! 20: /* MALLOC is used for allocations of 64k or less */ ! 21: /* FREE is used to free buffers allocated with MALLOC */ ! 22: /* LMALLOC is used for allocations of possibly larger than 64k */ ! 23: /* LFREE is used to free buffers allocated with LMALLOC */ ! 24: /* REALLOC is used to re-size a previously MALLOCed or LMALLOCed buffer */ ! 25: /****************************************************************************/ ! 26: #if defined(__COMPACT__) || defined(__LARGE__) || defined(__HUGE__) ! 27: #if defined(__TURBOC__) ! 28: #define REALLOC(x,y) farrealloc(x,y) ! 29: #define LMALLOC(x) farmalloc(x) ! 30: #define MALLOC(x) farmalloc(x) ! 31: #define LFREE(x) farfree(x) ! 32: #define FREE(x) farfree(x) ! 33: #elif defined(__WATCOMC__) ! 34: #define REALLOC realloc ! 35: #define LMALLOC(x) halloc(x,1) /* far heap, but slow */ ! 36: #define MALLOC malloc /* far heap, but 64k max */ ! 37: #define LFREE hfree ! 38: #define FREE free ! 39: #else /* Other 16-bit Compiler */ ! 40: #define REALLOC realloc ! 41: #define LMALLOC malloc ! 42: #define MALLOC malloc ! 43: #define LFREE free ! 44: #define FREE free ! 45: #endif ! 46: #else /* 32-bit Compiler or Small Memory Model */ ! 47: #define REALLOC realloc ! 48: #define LMALLOC malloc ! 49: #define MALLOC malloc ! 50: #define LFREE free ! 51: #define FREE free ! 52: #endif ! 53: ! 54: ! 55: ! 56: /* LZSS Parameters */ ! 57: ! 58: #define LZH_N 4096 /* Size of string buffer */ ! 59: #define LZH_F 60 /* Size of look-ahead buffer */ ! 60: #define LZH_THRESHOLD 2 ! 61: #define LZH_NIL LZH_N /* End of tree's node */ ! 62: ! 63: #ifdef LZH_DYNAMIC_BUF ! 64: ! 65: unsigned char *lzh_text_buf; ! 66: short int lzh_match_position, lzh_match_length, ! 67: *lzh_lson, *lzh_rson, *lzh_dad; ! 68: ! 69: #else ! 70: ! 71: unsigned char lzh_text_buf[LZH_N + LZH_F - 1]; ! 72: short int lzh_match_position, lzh_match_length, ! 73: lzh_lson[LZH_N + 1], lzh_rson[LZH_N + 257], lzh_dad[LZH_N + 1]; ! 74: ! 75: #endif ! 76: ! 77: ! 78: void lzh_init_tree(void) /* Initializing tree */ ! 79: { ! 80: short int i; ! 81: ! 82: for (i = LZH_N + 1; i <= LZH_N + 256; i++) ! 83: lzh_rson[i] = LZH_NIL; /* root */ ! 84: for (i = 0; i < LZH_N; i++) ! 85: lzh_dad[i] = LZH_NIL; /* node */ ! 86: } ! 87: ! 88: /******************************/ ! 89: /* Inserting node to the tree */ ! 90: /* Only used during encoding */ ! 91: /******************************/ ! 92: void lzh_insert_node(short int r) ! 93: { ! 94: short int i, p, cmp; ! 95: unsigned char *key; ! 96: unsigned c; ! 97: ! 98: cmp = 1; ! 99: key = lzh_text_buf+r; ! 100: p = LZH_N + 1 + key[0]; ! 101: lzh_rson[r] = lzh_lson[r] = LZH_NIL; ! 102: lzh_match_length = 0; ! 103: for ( ; ; ) { ! 104: if (cmp >= 0) { ! 105: if (lzh_rson[p] != LZH_NIL) ! 106: p = lzh_rson[p]; ! 107: else { ! 108: lzh_rson[p] = r; ! 109: lzh_dad[r] = p; ! 110: return; ! 111: } ! 112: } else { ! 113: if (lzh_lson[p] != LZH_NIL) ! 114: p = lzh_lson[p]; ! 115: else { ! 116: lzh_lson[p] = r; ! 117: lzh_dad[r] = p; ! 118: return; ! 119: } ! 120: } ! 121: for (i = 1; i < LZH_F; i++) ! 122: if ((cmp = key[i] - lzh_text_buf[p + i]) != 0) ! 123: break; ! 124: if (i > LZH_THRESHOLD) { ! 125: if (i > lzh_match_length) { ! 126: lzh_match_position = ((r - p) & (LZH_N - 1)) - 1; ! 127: if ((lzh_match_length = i) >= LZH_F) ! 128: break; ! 129: } ! 130: if (i == lzh_match_length) { ! 131: if ((c = ((r - p) & (LZH_N - 1)) - 1) < lzh_match_position) { ! 132: lzh_match_position = c; ! 133: } ! 134: } ! 135: } ! 136: } ! 137: lzh_dad[r] = lzh_dad[p]; ! 138: lzh_lson[r] = lzh_lson[p]; ! 139: lzh_rson[r] = lzh_rson[p]; ! 140: lzh_dad[lzh_lson[p]] = r; ! 141: lzh_dad[lzh_rson[p]] = r; ! 142: if (lzh_rson[lzh_dad[p]] == p) ! 143: lzh_rson[lzh_dad[p]] = r; ! 144: else ! 145: lzh_lson[lzh_dad[p]] = r; ! 146: lzh_dad[p] = LZH_NIL; /* remove p */ ! 147: } ! 148: ! 149: void lzh_delete_node(short int p) /* Deleting node from the tree */ ! 150: { ! 151: short int q; ! 152: ! 153: if (lzh_dad[p] == LZH_NIL) ! 154: return; /* unregistered */ ! 155: if (lzh_rson[p] == LZH_NIL) ! 156: q = lzh_lson[p]; ! 157: else ! 158: if (lzh_lson[p] == LZH_NIL) ! 159: q = lzh_rson[p]; ! 160: else { ! 161: q = lzh_lson[p]; ! 162: if (lzh_rson[q] != LZH_NIL) { ! 163: do { ! 164: q = lzh_rson[q]; ! 165: } while (lzh_rson[q] != LZH_NIL); ! 166: lzh_rson[lzh_dad[q]] = lzh_lson[q]; ! 167: lzh_dad[lzh_lson[q]] = lzh_dad[q]; ! 168: lzh_lson[q] = lzh_lson[p]; ! 169: lzh_dad[lzh_lson[p]] = q; ! 170: } ! 171: lzh_rson[q] = lzh_rson[p]; ! 172: lzh_dad[lzh_rson[p]] = q; ! 173: } ! 174: lzh_dad[q] = lzh_dad[p]; ! 175: if (lzh_rson[lzh_dad[p]] == p) ! 176: lzh_rson[lzh_dad[p]] = q; ! 177: else ! 178: lzh_lson[lzh_dad[p]] = q; ! 179: lzh_dad[p] = LZH_NIL; ! 180: } ! 181: ! 182: /* Huffman coding parameters */ ! 183: ! 184: #define LZH_N_CHAR (256 - LZH_THRESHOLD + LZH_F) ! 185: /* character code (= 0..LZH_N_CHAR-1) */ ! 186: #define LZH_T (LZH_N_CHAR * 2 - 1) /* Size of table */ ! 187: #define LZH_R (LZH_T - 1) /* root position */ ! 188: #define MAX_FREQ 0x8000 ! 189: /* update when cumulative frequency */ ! 190: /* reaches to this value */ ! 191: ! 192: /* ! 193: * Tables for encoding/decoding upper 6 bits of ! 194: * sliding dictionary pointer ! 195: */ ! 196: /* encoder table */ ! 197: uchar lzh_p_len[64] = { ! 198: 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05, ! 199: 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06, ! 200: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 201: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 202: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 203: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 204: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, ! 205: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08 ! 206: }; ! 207: ! 208: uchar lzh_p_code[64] = { ! 209: 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68, ! 210: 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C, ! 211: 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC, ! 212: 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE, ! 213: 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE, ! 214: 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE, ! 215: 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, ! 216: 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF ! 217: }; ! 218: ! 219: /* decoder table */ ! 220: uchar lzh_d_code[256] = { ! 221: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, ! 222: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, ! 223: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, ! 224: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, ! 225: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, ! 226: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, ! 227: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, ! 228: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, ! 229: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, ! 230: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, ! 231: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, ! 232: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 233: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 234: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 235: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, ! 236: 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, ! 237: 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, ! 238: 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, ! 239: 0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D, ! 240: 0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F, ! 241: 0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11, ! 242: 0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13, ! 243: 0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15, ! 244: 0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17, ! 245: 0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B, ! 246: 0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F, ! 247: 0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23, ! 248: 0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27, ! 249: 0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B, ! 250: 0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F, ! 251: 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, ! 252: 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, ! 253: }; ! 254: ! 255: uchar lzh_d_len[256] = { ! 256: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, ! 257: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, ! 258: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, ! 259: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, ! 260: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, ! 261: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, ! 262: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, ! 263: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, ! 264: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, ! 265: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, ! 266: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 267: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 268: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 269: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 270: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 271: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 272: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 273: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, ! 274: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 275: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 276: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 277: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 278: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 279: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, ! 280: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 281: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 282: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 283: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 284: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 285: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, ! 286: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, ! 287: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, ! 288: }; ! 289: ! 290: #ifdef LZH_DYNAMIC_BUF ! 291: ! 292: unsigned short *lzh_freq=NULL; /* cumulative freq table */ ! 293: ! 294: /* ! 295: * pointing parent nodes. ! 296: * area [LZH_T..(LZH_T + LZH_N_CHAR - 1)] are pointers for leaves ! 297: */ ! 298: short int *lzh_prnt=NULL; ! 299: ! 300: /* pointing children nodes (son[], son[] + 1)*/ ! 301: short int *lzh_son=NULL; ! 302: ! 303: #else /* STATIC */ ! 304: ! 305: unsigned short lzh_freq[LZH_T + 1]; /* cumulative freq table */ ! 306: short int lzh_prnt[LZH_T + LZH_N_CHAR]; ! 307: short int lzh_son[LZH_T + 1]; /* bug fixed by Digital Dynamics */ ! 308: ! 309: #endif ! 310: ! 311: ! 312: unsigned short lzh_getbuf = 0; /* Was just "unsigned" fixed 04/12/95 */ ! 313: uchar lzh_getlen = 0; ! 314: ! 315: int lzh_getbit(uchar *inbuf, long *incnt, long inlen) /* get one bit */ ! 316: { ! 317: short int i; ! 318: ! 319: while (lzh_getlen <= 8) { ! 320: if((*incnt)>=inlen) ! 321: i=0; ! 322: else ! 323: i=inbuf[(*incnt)++]; ! 324: lzh_getbuf |= i << (8 - lzh_getlen); ! 325: lzh_getlen += 8; ! 326: } ! 327: i = lzh_getbuf; ! 328: lzh_getbuf <<= 1; ! 329: lzh_getlen--; ! 330: return (i < 0); ! 331: } ! 332: ! 333: short int lzh_getbyte(uchar *inbuf, long *incnt, long inlen) /* get a byte */ ! 334: { ! 335: unsigned short i; ! 336: ! 337: while (lzh_getlen <= 8) { ! 338: if((*incnt)>=inlen) ! 339: i=0; ! 340: else ! 341: i=inbuf[(*incnt)++]; ! 342: lzh_getbuf |= i << (8 - lzh_getlen); ! 343: lzh_getlen += 8; ! 344: } ! 345: i = lzh_getbuf; ! 346: lzh_getbuf <<= 8; ! 347: lzh_getlen -= 8; ! 348: return i >> 8; ! 349: } ! 350: ! 351: unsigned lzh_putbuf = 0; ! 352: uchar lzh_putlen = 0; ! 353: ! 354: /* output c bits */ ! 355: void lzh_putcode(short int l, unsigned short c, uchar *outbuf, long *outlen) ! 356: { ! 357: lzh_putbuf |= c >> lzh_putlen; ! 358: if ((lzh_putlen += l) >= 8) { ! 359: outbuf[(*outlen)++]=(lzh_putbuf >> 8); ! 360: if ((lzh_putlen -= 8) >= 8) { ! 361: outbuf[(*outlen)++]=lzh_putbuf; ! 362: lzh_putlen -= 8; ! 363: lzh_putbuf = c << (l - lzh_putlen); ! 364: } else { ! 365: lzh_putbuf <<= 8; ! 366: } ! 367: } ! 368: } ! 369: ! 370: ! 371: /* initialize freq tree */ ! 372: ! 373: void lzh_start_huff() ! 374: { ! 375: short int i, j; ! 376: ! 377: lzh_getbuf = 0; /* Added by Digital Dynamics for repeating operations */ ! 378: lzh_getlen = 0; ! 379: lzh_putbuf = 0; ! 380: lzh_putlen = 0; ! 381: ! 382: for (i = 0; i < LZH_N_CHAR; i++) { ! 383: lzh_freq[i] = 1; ! 384: lzh_son[i] = i + LZH_T; ! 385: lzh_prnt[i + LZH_T] = i; ! 386: } ! 387: i = 0; j = LZH_N_CHAR; ! 388: while (j <= LZH_R) { ! 389: lzh_freq[j] = lzh_freq[i] + lzh_freq[i + 1]; ! 390: lzh_son[j] = i; ! 391: lzh_prnt[i] = lzh_prnt[i + 1] = j; ! 392: i += 2; j++; ! 393: } ! 394: lzh_freq[LZH_T] = 0xffff; ! 395: lzh_prnt[LZH_R] = 0; ! 396: } ! 397: ! 398: ! 399: /* reconstruct freq tree */ ! 400: ! 401: void lzh_reconst() ! 402: { ! 403: short int i, j, k; ! 404: unsigned short f, l; ! 405: ! 406: /* halven cumulative freq for leaf nodes */ ! 407: j = 0; ! 408: for (i = 0; i < LZH_T; i++) { ! 409: if (lzh_son[i] >= LZH_T) { ! 410: lzh_freq[j] = (lzh_freq[i] + 1) / 2; ! 411: lzh_son[j] = lzh_son[i]; ! 412: j++; ! 413: } ! 414: } ! 415: /* make a tree : first, connect children nodes */ ! 416: for (i = 0, j = LZH_N_CHAR; j < LZH_T; i += 2, j++) { ! 417: k = i + 1; ! 418: f = lzh_freq[j] = lzh_freq[i] + lzh_freq[k]; ! 419: for (k = j - 1; f < lzh_freq[k]; k--); ! 420: k++; ! 421: l = (j - k) * 2; ! 422: ! 423: /* movmem() is Turbo-C dependent ! 424: rewritten to memmove() by Kenji */ ! 425: ! 426: /* movmem(&lzh_freq[k], &lzh_freq[k + 1], l); */ ! 427: (void)memmove(lzh_freq+k+1,lzh_freq+k, l); ! 428: lzh_freq[k] = f; ! 429: /* movmem(&lzh_son[k], &lzh_son[k + 1], l); */ ! 430: (void)memmove(lzh_son+k+1,lzh_son+k, l); ! 431: lzh_son[k] = i; ! 432: } ! 433: /* connect parent nodes */ ! 434: for (i = 0; i < LZH_T; i++) { ! 435: if ((k = lzh_son[i]) >= LZH_T) { ! 436: lzh_prnt[k] = i; ! 437: } else { ! 438: lzh_prnt[k] = lzh_prnt[k + 1] = i; ! 439: } ! 440: } ! 441: } ! 442: ! 443: /* update freq tree */ ! 444: ! 445: void lzh_update(short int c) ! 446: { ! 447: short int i, j, k, l; ! 448: ! 449: if (lzh_freq[LZH_R] == MAX_FREQ) { ! 450: lzh_reconst(); ! 451: } ! 452: c = lzh_prnt[c + LZH_T]; ! 453: do { ! 454: k = ++lzh_freq[c]; ! 455: ! 456: /* swap nodes to keep the tree freq-ordered */ ! 457: if (k > lzh_freq[l = c + 1]) { ! 458: while (k > lzh_freq[++l]); ! 459: l--; ! 460: lzh_freq[c] = lzh_freq[l]; ! 461: lzh_freq[l] = k; ! 462: ! 463: i = lzh_son[c]; ! 464: lzh_prnt[i] = l; ! 465: if (i < LZH_T) lzh_prnt[i + 1] = l; ! 466: ! 467: j = lzh_son[l]; ! 468: lzh_son[l] = i; ! 469: ! 470: lzh_prnt[j] = c; ! 471: if (j < LZH_T) lzh_prnt[j + 1] = c; ! 472: lzh_son[c] = j; ! 473: ! 474: c = l; ! 475: } ! 476: } while ((c = lzh_prnt[c]) != 0); /* do it until reaching the root */ ! 477: } ! 478: ! 479: unsigned short lzh_code, lzh_len; ! 480: ! 481: void lzh_encode_char(unsigned short c, uchar *outbuf, long *outlen) ! 482: { ! 483: unsigned short i; ! 484: short int j, k; ! 485: ! 486: i = 0; ! 487: j = 0; ! 488: k = lzh_prnt[c + LZH_T]; ! 489: ! 490: /* search connections from leaf node to the root */ ! 491: do { ! 492: i >>= 1; ! 493: ! 494: /* ! 495: if node's address is odd, output 1 ! 496: else output 0 ! 497: */ ! 498: if (k & 1) i += 0x8000; ! 499: ! 500: j++; ! 501: } while ((k = lzh_prnt[k]) != LZH_R); ! 502: lzh_putcode(j, i, outbuf, outlen); ! 503: lzh_code = i; ! 504: lzh_len = j; ! 505: lzh_update(c); ! 506: } ! 507: ! 508: void lzh_encode_position(unsigned short c, uchar *outbuf, long *outlen) ! 509: { ! 510: unsigned short i; ! 511: ! 512: /* output upper 6 bits with encoding */ ! 513: i = c >> 6; ! 514: lzh_putcode(lzh_p_len[i], (unsigned)lzh_p_code[i] << 8, outbuf, outlen); ! 515: ! 516: /* output lower 6 bits directly */ ! 517: lzh_putcode(6, (c & 0x3f) << 10, outbuf, outlen); ! 518: } ! 519: ! 520: void lzh_encode_end(uchar *outbuf, long *outlen) ! 521: { ! 522: if (lzh_putlen) { ! 523: outbuf[(*outlen)++]=(lzh_putbuf >> 8); ! 524: } ! 525: } ! 526: ! 527: short int lzh_decode_char(uchar *inbuf, long *incnt, long inlen) ! 528: { ! 529: unsigned short c; ! 530: ! 531: c = lzh_son[LZH_R]; ! 532: ! 533: /* ! 534: * start searching tree from the root to leaves. ! 535: * choose node #(lzh_son[]) if input bit == 0 ! 536: * else choose #(lzh_son[]+1) (input bit == 1) ! 537: */ ! 538: while (c < LZH_T) { ! 539: c += lzh_getbit(inbuf,incnt,inlen); ! 540: c = lzh_son[c]; ! 541: } ! 542: c -= LZH_T; ! 543: lzh_update(c); ! 544: return c; ! 545: } ! 546: ! 547: short int lzh_decode_position(uchar *inbuf, long *incnt, long inlen) ! 548: { ! 549: unsigned short i, j, c; ! 550: ! 551: /* decode upper 6 bits from given table */ ! 552: i = lzh_getbyte(inbuf,incnt,inlen); ! 553: c = (unsigned)lzh_d_code[i] << 6; ! 554: j = lzh_d_len[i]; ! 555: ! 556: /* input lower 6 bits directly */ ! 557: j -= 2; ! 558: while (j--) { ! 559: i = (i << 1) + lzh_getbit(inbuf,incnt,inlen); ! 560: } ! 561: return c | i & 0x3f; ! 562: } ! 563: ! 564: /* Compression */ ! 565: ! 566: /* Encoding/Compressing */ ! 567: /* Returns length of outbuf */ ! 568: long LZHCALL lzh_encode(uchar *inbuf, long inlen, uchar *outbuf) ! 569: { ! 570: short int i, c, len, r, s, last_match_length; ! 571: long incnt,outlen; /* textsize=0; */ ! 572: ! 573: #ifdef LZH_DYNAMIC_BUF ! 574: ! 575: if((lzh_text_buf=(uchar *)MALLOC(LZH_N + LZH_F - 1))==NULL) ! 576: return(-1); ! 577: if((lzh_freq=(unsigned short*)MALLOC((LZH_T + 1)*sizeof(unsigned short)))==NULL) { ! 578: FREE(lzh_text_buf); ! 579: return(-1); } ! 580: if((lzh_prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) { ! 581: FREE(lzh_text_buf); ! 582: FREE(lzh_freq); ! 583: return(-1); } ! 584: if((lzh_son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) { ! 585: FREE(lzh_text_buf); ! 586: FREE(lzh_prnt); ! 587: FREE(lzh_freq); ! 588: return(-1); } ! 589: if((lzh_lson=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) { ! 590: FREE(lzh_text_buf); ! 591: FREE(lzh_prnt); ! 592: FREE(lzh_freq); ! 593: FREE(lzh_son); ! 594: return(-1); } ! 595: if((lzh_rson=(short *)MALLOC((LZH_N + 257)*sizeof(short)))==NULL) { ! 596: FREE(lzh_text_buf); ! 597: FREE(lzh_prnt); ! 598: FREE(lzh_freq); ! 599: FREE(lzh_son); ! 600: FREE(lzh_lson); ! 601: return(-1); } ! 602: if((lzh_dad=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) { ! 603: FREE(lzh_text_buf); ! 604: FREE(lzh_prnt); ! 605: FREE(lzh_freq); ! 606: FREE(lzh_son); ! 607: FREE(lzh_lson); ! 608: FREE(lzh_rson); ! 609: return(-1); } ! 610: #endif ! 611: ! 612: incnt=0; ! 613: memcpy(outbuf,&inlen,sizeof(inlen)); ! 614: outlen=sizeof(inlen); ! 615: if(!inlen) { ! 616: #ifdef LZH_DYNAMIC_BUF ! 617: FREE(lzh_text_buf); ! 618: FREE(lzh_prnt); ! 619: FREE(lzh_freq); ! 620: FREE(lzh_son); ! 621: FREE(lzh_lson); ! 622: FREE(lzh_rson); ! 623: FREE(lzh_dad); ! 624: #endif ! 625: return(outlen); } ! 626: lzh_start_huff(); ! 627: lzh_init_tree(); ! 628: s = 0; ! 629: r = LZH_N - LZH_F; ! 630: for (i = s; i < r; i++) ! 631: lzh_text_buf[i] = ' '; ! 632: for (len = 0; len < LZH_F && incnt<inlen; len++) ! 633: lzh_text_buf[r + len] = inbuf[incnt++]; ! 634: /* textsize = len; */ ! 635: for (i = 1; i <= LZH_F; i++) ! 636: lzh_insert_node(r - i); ! 637: lzh_insert_node(r); ! 638: do { ! 639: if (lzh_match_length > len) ! 640: lzh_match_length = len; ! 641: if (lzh_match_length <= LZH_THRESHOLD) { ! 642: lzh_match_length = 1; ! 643: lzh_encode_char(lzh_text_buf[r],outbuf,&outlen); ! 644: } else { ! 645: lzh_encode_char(255 - LZH_THRESHOLD + lzh_match_length ! 646: ,outbuf,&outlen); ! 647: lzh_encode_position(lzh_match_position ! 648: ,outbuf,&outlen); ! 649: } ! 650: last_match_length = lzh_match_length; ! 651: for (i = 0; i < last_match_length && incnt<inlen; i++) { ! 652: lzh_delete_node(s); ! 653: c=inbuf[incnt++]; ! 654: lzh_text_buf[s] = c; ! 655: if (s < LZH_F - 1) ! 656: lzh_text_buf[s + LZH_N] = c; ! 657: s = (s + 1) & (LZH_N - 1); ! 658: r = (r + 1) & (LZH_N - 1); ! 659: lzh_insert_node(r); ! 660: } ! 661: /*** ! 662: if ((textsize += i) > printcount) { ! 663: printf("%12ld\r", textsize); ! 664: printcount += 1024; ! 665: } ! 666: ***/ ! 667: while (i++ < last_match_length) { ! 668: lzh_delete_node(s); ! 669: s = (s + 1) & (LZH_N - 1); ! 670: r = (r + 1) & (LZH_N - 1); ! 671: if (--len) lzh_insert_node(r); ! 672: } ! 673: } while (len > 0); ! 674: lzh_encode_end(outbuf,&outlen); ! 675: /* ! 676: printf("input: %ld (%ld) bytes\n", inlen,textsize); ! 677: printf("output: %ld bytes\n", outlen); ! 678: printf("output/input: %.3f\n", (double)outlen / inlen); ! 679: */ ! 680: ! 681: #ifdef LZH_DYNAMIC_BUF ! 682: FREE(lzh_text_buf); ! 683: FREE(lzh_prnt); ! 684: FREE(lzh_freq); ! 685: FREE(lzh_son); ! 686: FREE(lzh_lson); ! 687: FREE(lzh_rson); ! 688: FREE(lzh_dad); ! 689: #endif ! 690: ! 691: return(outlen); ! 692: } ! 693: ! 694: /* Decoding/Uncompressing */ ! 695: /* Returns length of outbuf */ ! 696: long LZHCALL lzh_decode(uchar *inbuf, long inlen, uchar *outbuf) ! 697: { ! 698: short int i, j, k, r, c; ! 699: unsigned long int count; ! 700: long incnt,textsize; ! 701: ! 702: #ifdef LZH_DYNAMIC_BUF ! 703: ! 704: if((lzh_text_buf=(uchar *)MALLOC((LZH_N + LZH_F - 1)*2))==NULL) ! 705: return(-1); ! 706: if((lzh_freq=(unsigned short *)MALLOC((LZH_T + 1)*sizeof(unsigned short))) ! 707: ==NULL) { ! 708: FREE(lzh_text_buf); ! 709: return(-1); } ! 710: if((lzh_prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) { ! 711: FREE(lzh_text_buf); ! 712: FREE(lzh_freq); ! 713: return(-1); } ! 714: if((lzh_son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) { ! 715: FREE(lzh_text_buf); ! 716: FREE(lzh_prnt); ! 717: FREE(lzh_freq); ! 718: return(-1); } ! 719: ! 720: #endif ! 721: ! 722: incnt=0; ! 723: memcpy(&textsize,inbuf,sizeof(textsize)); ! 724: incnt+=sizeof(textsize); ! 725: if (textsize == 0) { ! 726: #ifdef LZH_DYNAMIC_BUF ! 727: FREE(lzh_text_buf); ! 728: FREE(lzh_prnt); ! 729: FREE(lzh_freq); ! 730: FREE(lzh_son); ! 731: #endif ! 732: return(textsize); } ! 733: lzh_start_huff(); ! 734: for (i = 0; i < LZH_N - LZH_F; i++) ! 735: *(lzh_text_buf+i) = ' '; ! 736: r = LZH_N - LZH_F; ! 737: for (count = 0; count < textsize; ) { ! 738: c = lzh_decode_char(inbuf,&incnt,inlen); ! 739: if (c < 256) { ! 740: outbuf[count]=c; ! 741: #if 0 ! 742: if(r>(LZH_N + LZH_F - 1) || r<0) { ! 743: printf("Overflow! (%d)\n",r); ! 744: getch(); ! 745: exit(-1); } ! 746: #endif ! 747: *(lzh_text_buf+r) = c; ! 748: r++; ! 749: r &= (LZH_N - 1); ! 750: count++; ! 751: } else { ! 752: i = (r - lzh_decode_position(inbuf,&incnt,inlen) - 1) ! 753: & (LZH_N - 1); ! 754: j = c - 255 + LZH_THRESHOLD; ! 755: for (k = 0; k < j && count<textsize; k++) { ! 756: c = lzh_text_buf[(i + k) & (LZH_N - 1)]; ! 757: outbuf[count]=c; ! 758: #if 0 ! 759: if(r>(LZH_N + LZH_F - 1) || r<0) { ! 760: printf("Overflow! (%d)\n",r); ! 761: exit(-1); } ! 762: #endif ! 763: *(lzh_text_buf+r) = c; ! 764: r++; ! 765: r &= (LZH_N - 1); ! 766: count++; ! 767: } ! 768: } ! 769: } ! 770: /*** ! 771: printf("%12ld\n", count); ! 772: ***/ ! 773: ! 774: #ifdef LZH_DYNAMIC_BUF ! 775: FREE(lzh_text_buf); ! 776: FREE(lzh_prnt); ! 777: FREE(lzh_freq); ! 778: FREE(lzh_son); ! 779: #endif ! 780: ! 781: return(count); ! 782: } ! 783: ! 784:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.