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