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