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