foreign/lzhuf.h

   1 // See the file readme-lzhuf.txt for more information about this file.
   2 // Modifications for Deark are Copyright (C) 2021 Jason Summers, and have the
   3 // same terms of use as the main part of Deark.
   4 // Alternatively, at your option, the modifications for Deark may be treated
   5 // as public domain.
   6
   7 // Intro from the original software:
   8
   9 /**************************************************************
  10                 lzhuf.c
  11                 written by Haruyasu Yoshizaki 11/20/1988
  12                 some minor changes 4/6/1989
  13                 comments translated by Haruhiko Okumura 4/7/1989
  14 **************************************************************/
  15
  16
  17 #define LZHUF_N               4096    /* buffer size */
  18 #define LZHUF_F               60      /* lookahead buffer size */
  19 #define LZHUF_THRESHOLD       2
  20 #define LZHUF_N_CHAR          (256 - LZHUF_THRESHOLD + LZHUF_F)
  21                                                         /* kinds of characters (character code = 0..N_CHAR-1) */
  22 #define LZHUF_T               (LZHUF_N_CHAR * 2 - 1)        /* size of table */
  23 #define LZHUF_R               (LZHUF_T - 1)                 /* position of root */
  24 #define LZHUF_MAX_FREQ        0x8000            /* updates tree when the */
  25                                                                         /* root frequency comes to this value. */
  26
  27 struct lzahuf_ctx {
  28         deark *c;
  29         const char *modname;
  30         struct de_dfilter_in_params *dcmpri;
  31         struct de_dfilter_out_params *dcmpro;
  32         struct de_dfilter_results *dres;
  33         int errflag;
  34         i64 nbytes_written;
  35         i64 textsize;
  36         struct de_lz77buffer *ringbuf;
  37         struct de_bitreader bitrd;
  38
  39         u16 freq[LZHUF_T + 1];   /* frequency table */
  40
  41         i16 prnt[LZHUF_T + LZHUF_N_CHAR];   /* pointers to parent nodes, except for the */
  42                                                         /* elements [T..T + N_CHAR - 1] which are used to get */
  43                                                         /* the positions of leaves corresponding to the codes. */
  44
  45         i16 son[LZHUF_T];             /* pointers to child nodes (son[], son[] + 1) */
  46 };
  47
  48
  49 /* initialization of tree */
  50
  51 static void lzhuf_StartHuff(struct lzahuf_ctx *cctx)
  52 {
  53         int i, j;
  54
  55         for (i = 0; i < LZHUF_N_CHAR; i++) {
  56                 cctx->freq[i] = 1;
  57                 cctx->son[i] = i + LZHUF_T;
  58                 cctx->prnt[i + LZHUF_T] = i;
  59         }
  60         i = 0; j = LZHUF_N_CHAR;
  61         while (j <= LZHUF_R) {
  62                 cctx->freq[j] = cctx->freq[i] + cctx->freq[i + 1];
  63                 cctx->son[j] = i;
  64                 cctx->prnt[i] = cctx->prnt[i + 1] = j;
  65                 i += 2; j++;
  66         }
  67         cctx->freq[LZHUF_T] = 0xffff;
  68         cctx->prnt[LZHUF_R] = 0;
  69 }
  70
  71
  72 /* reconstruction of tree */
  73
  74 static void lzhuf_reconst(struct lzahuf_ctx *cctx)
  75 {
  76         int i, j, k;
  77         UI f, l;
  78
  79         /* collect leaf nodes in the first half of the table */
  80         /* and replace the freq by (freq + 1) / 2. */
  81         j = 0;
  82         for (i = 0; i < LZHUF_T; i++) {
  83                 if (cctx->son[i] >= LZHUF_T) {
  84                         cctx->freq[j] = (cctx->freq[i] + 1) / 2;
  85                         cctx->son[j] = cctx->son[i];
  86                         j++;
  87                 }
  88         }
  89         /* begin constructing tree by connecting sons */
  90         for (i = 0, j = LZHUF_N_CHAR; j < LZHUF_T; i += 2, j++) {
  91                 k = i + 1;
  92                 f = cctx->freq[j] = cctx->freq[i] + cctx->freq[k];
  93                 for (k = j - 1; f < cctx->freq[k]; k--);
  94                 k++;
  95                 l = (j - k);
  96                 de_memmove(&cctx->freq[k + 1], &cctx->freq[k], l*sizeof(cctx->freq[0]));
  97                 cctx->freq[k] = f;
  98                 de_memmove(&cctx->son[k + 1], &cctx->son[k], l*sizeof(cctx->son[0]));
  99                 cctx->son[k] = i;
 100         }
 101         /* connect prnt */
 102         for (i = 0; i < LZHUF_T; i++) {
 103                 if ((k = cctx->son[i]) >= LZHUF_T) {
 104                         cctx->prnt[k] = i;
 105                 } else {
 106                         cctx->prnt[k] = cctx->prnt[k + 1] = i;
 107                 }
 108         }
 109 }
 110
 111
 112 /* increment frequency of given code by one, and update tree */
 113
 114 static void lzhuf_update(struct lzahuf_ctx *cctx, int c)
 115 {
 116         int i, j, l;
 117         UI k;
 118
 119         if (cctx->freq[LZHUF_R] == LZHUF_MAX_FREQ) {
 120                 lzhuf_reconst(cctx);
 121         }
 122         c = cctx->prnt[c + LZHUF_T];
 123         do {
 124                 k = ++cctx->freq[c];
 125
 126                 /* if the order is disturbed, exchange nodes */
 127                 if (k > cctx->freq[l = c + 1]) {
 128                         while (k > cctx->freq[++l]);
 129                         l--;
 130                         cctx->freq[c] = cctx->freq[l];
 131                         cctx->freq[l] = k;
 132
 133                         i = cctx->son[c];
 134                         cctx->prnt[i] = l;
 135                         if (i < LZHUF_T) cctx->prnt[i + 1] = l;
 136
 137                         j = cctx->son[l];
 138                         cctx->son[l] = i;
 139
 140                         cctx->prnt[j] = c;
 141                         if (j < LZHUF_T) cctx->prnt[j + 1] = c;
 142                         cctx->son[c] = j;
 143
 144                         c = l;
 145                 }
 146         } while ((c = cctx->prnt[c]) != 0);   /* repeat up to root */
 147 }
 148
 149 static int lzhuf_DecodeChar(struct lzahuf_ctx *cctx)
 150 {
 151         UI c;
 152
 153         c = cctx->son[LZHUF_R];
 154
 155         /* travel from root to leaf, */
 156         /* choosing the smaller child node (son[]) if the read bit is 0, */
 157         /* the bigger (son[]+1} if 1 */
 158         while (c < LZHUF_T) {
 159                 c += (UI)de_bitreader_getbits(&cctx->bitrd, 1);
 160                 c = cctx->son[c];
 161         }
 162         c -= LZHUF_T;
 163         lzhuf_update(cctx, c);
 164         return c;
 165 }
 166
 167 static int lzhuf_DecodePosition(struct lzahuf_ctx *cctx)
 168 {
 169         UI i, j, c;
 170
 171         /* recover upper 6 bits from table */
 172         i = (UI)de_bitreader_getbits(&cctx->bitrd, 8);
 173         c = (UI)fmtutil_get_lzhuf_d_code(i) << 6;
 174         j = fmtutil_get_lzhuf_d_len(i);
 175
 176         /* read lower 6 bits verbatim */
 177         j -= 2;
 178         i = (i<<j) | (UI)de_bitreader_getbits(&cctx->bitrd, j);
 179         return c | (i & 0x3f);
 180 }
 181
 182 static void lzah_lz77buf_writebytecb(struct de_lz77buffer *rb, u8 n)
 183 {
 184         struct lzahuf_ctx *cctx = (struct lzahuf_ctx*)rb->userdata;
 185
 186         if(cctx->nbytes_written >= cctx->textsize) {
 187                 return;
 188         }
 189         dbuf_writebyte(cctx->dcmpro->f, n);
 190         cctx->nbytes_written++;
 191 }
 192
 193 static void lzhuf_Decode(struct lzahuf_ctx *cctx)  /* recover */
 194 {
 195         int i, j, c;
 196
 197         if(cctx->dcmpro->len_known) {
 198                 cctx->textsize = cctx->dcmpro->expected_len;
 199         }
 200         else {
 201                 de_dfilter_set_generic_error(cctx->c, cctx->dres, cctx->modname);
 202                 goto done;
 203         }
 204
 205         lzhuf_StartHuff(cctx);
 206
 207         cctx->ringbuf = de_lz77buffer_create(cctx->c, LZHUF_N);
 208         cctx->ringbuf->userdata = (void*)cctx;
 209         cctx->ringbuf->writebyte_cb = lzah_lz77buf_writebytecb;
 210         de_lz77buffer_clear(cctx->ringbuf, 0x20);
 211         de_lz77buffer_set_curpos(cctx->ringbuf, LZHUF_N - LZHUF_F);
 212
 213         while(1) {
 214                 if(cctx->nbytes_written >= cctx->textsize) {
 215                         goto done;
 216                 }
 217                 if(cctx->bitrd.eof_flag) {
 218                         goto done;
 219                 }
 220
 221                 c = lzhuf_DecodeChar(cctx);
 222                 if (c < 256) {
 223                         de_lz77buffer_add_literal_byte(cctx->ringbuf, (u8)c);
 224                 }
 225                 else {
 226                         // i is the distance back
 227                         i = lzhuf_DecodePosition(cctx);
 228                         // j is the match length
 229                         j = c - 255 + LZHUF_THRESHOLD;
 230
 231                         de_lz77buffer_copy_from_hist(cctx->ringbuf,
 232                                 (UI)(cctx->ringbuf->curpos - (UI)i - 1), j);
 233                 }
 234         }
 235
 236 done:
 237         de_lz77buffer_destroy(cctx->c, cctx->ringbuf);
 238         cctx->ringbuf = NULL;
 239 }