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