1 /***********************************************************************
2 * This file is part of HA, a general purpose file archiver.
3 * Copyright (C) 1995 Harri Hirvola
4 * Modified by Ketmar // Invisible Vector
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 ***********************************************************************/
28 /******************************************************************************/
35 /******************************************************************************/
36 #define POSCODES (31200)
41 #define LENCODES (SLCODES+LLCODES*LLLEN)
42 #define LTCODES (SLCODES+LLCODES)
46 #define MAXLT (750*LTSTEP)
48 #define MAXCT (1000*CTSTEP)
50 #define MAXPT (250*PTSTEP)
52 #define MAXTT (150*TTSTEP)
54 #define TTOMASK (TTORD-1)
55 #define LCUTOFF (3*LTSTEP)
56 #define CCUTOFF (3*CTSTEP)
61 /******************************************************************************/
62 #define RD_BUF_SIZE (32*1024)
65 uint16_t ltab
[2*LTCODES
];
66 uint16_t eltab
[2*LTCODES
];
67 uint16_t ptab
[2*PTCODES
];
68 uint16_t ctab
[2*CTCODES
];
69 uint16_t ectab
[2*CTCODES
];
70 uint16_t ttab
[TTORD
][2];
71 uint16_t accnt
, pmax
, npt
;
76 uint8_t dict
[POSCODES
];
78 uint16_t dict_pair_len
;
79 uint16_t dict_pair_pos
;
81 uint16_t ari_h
, ari_l
, ari_v
;
83 int16_t ari_gpat
, ari_ppat
;
86 haunp_bread_fn_t reader
;
87 uint8_t rd_buf
[RD_BUF_SIZE
];
91 int no_more
; /* high-level flag: don't call read callback anymore */
92 /* for unpack-from-mem */
104 /******************************************************************************/
106 static int haunp_buf_reader (void *buf
, int buf_len
, void *udata
) {
107 haunp_t hup
= (haunp_t
)udata
;
108 if (hup
->buf_left
> 0) {
109 if (buf_len
> hup
->buf_left
) buf_len
= hup
->buf_left
;
110 memcpy(buf
, hup
->buf
, buf_len
);
112 hup
->buf_left
-= buf_len
;
119 /******************************************************************************/
120 static inline void tabinit (uint16_t t
[], uint16_t tl
, uint16_t ival
) {
122 for (i
= tl
; i
< 2*tl
; ++i
) t
[i
] = ival
;
123 for (i
= tl
-1, j
= (tl
<<1)-2; i
; --i
, j
-= 2) t
[i
] = t
[j
]+t
[j
+1];
127 static inline void tscale (uint16_t t
[], uint16_t tl
) {
129 for (i
= (tl
<<1)-1; i
>= tl
; --i
) if (t
[i
] > 1) t
[i
] >>= 1;
130 for (i
= tl
-1, j
= (tl
<<1)-2; i
; --i
, j
-= 2) t
[i
] = t
[j
]+t
[j
+1];
134 static inline void tupd (uint16_t t
[], uint16_t tl
, uint16_t maxt
, uint16_t step
, uint16_t p
) {
136 for (i
= p
+tl
; i
; i
>>= 1) t
[i
] += step
;
137 if (t
[1] >= maxt
) tscale(t
, tl
);
141 static inline void tzero (uint16_t t
[], uint16_t tl
, uint16_t p
) {
143 for (i
= p
+tl
, step
= t
[i
]; i
; i
>>= 1) t
[i
] -= step
;
147 static inline void ttscale (haunp_t hup
, uint16_t con
) {
148 hup
->ttab
[con
][0] >>= 1;
149 if (hup
->ttab
[con
][0] == 0) hup
->ttab
[con
][0] = 1;
150 hup
->ttab
[con
][1] >>= 1;
151 if (hup
->ttab
[con
][1] == 0) hup
->ttab
[con
][1] = 1;
155 /******************************************************************************/
156 /* return number of bytes copied (can be less thatn olen) */
157 static inline int swd_do_pair (haunp_t hup
, uint8_t *obuf
, int olen
) {
158 int todo
= (olen
> hup
->dict_pair_len
? hup
->dict_pair_len
: olen
), res
= todo
;
159 hup
->dict_pair_len
-= todo
;
161 hup
->dict
[hup
->dict_pos
] = hup
->dict
[hup
->dict_pair_pos
];
162 *obuf
++ = hup
->dict
[hup
->dict_pair_pos
];
163 if (++hup
->dict_pos
== POSCODES
) hup
->dict_pos
= 0;
164 if (++hup
->dict_pair_pos
== POSCODES
) hup
->dict_pair_pos
= 0;
170 /******************************************************************************/
171 /* Arithmetic decoding */
172 /******************************************************************************/
173 /* read next byte (buffered) */
174 #define getbyte(bto) do { \
175 if (hup->rd_pos >= hup->rd_max && !hup->no_more) { \
177 hup->rd_max = hup->reader(hup->rd_buf, hup->rd_size, hup->udata); \
178 hup->no_more = (hup->rd_max <= 0); \
179 if (hup->rd_max < 0) longjmp(hup->errJP, ERR_READ); \
181 bto = (!hup->no_more ? hup->rd_buf[hup->rd_pos++] : -1); \
185 #define getbit(b) do { \
186 hup->ari_gpat <<= 1; \
187 if (!(hup->ari_gpat&0xff)) { \
188 getbyte(hup->ari_gpat); \
189 if (hup->ari_gpat&0x100) { \
190 hup->ari_gpat = 0x100; \
192 hup->ari_gpat <<= 1; \
193 hup->ari_gpat |= 1; \
196 b |= (hup->ari_gpat&0x100)>>8; \
200 static void ac_in (haunp_t hup
, uint16_t low
, uint16_t high
, uint16_t tot
) {
202 if (tot
== 0) longjmp(hup
->errJP
, ERR_BAD_DATA
);
203 r
= (uint32_t)(hup
->ari_h
-hup
->ari_l
)+1;
204 hup
->ari_h
= (uint16_t)(r
*high
/tot
-1)+hup
->ari_l
;
205 hup
->ari_l
+= (uint16_t)(r
*low
/tot
);
206 while (!((hup
->ari_h
^hup
->ari_l
)&0x8000)) {
213 while ((hup
->ari_l
&0x4000) && !(hup
->ari_h
&0x4000)) {
215 hup
->ari_l
&= 0x7fff;
217 hup
->ari_h
|= 0x8001;
219 hup
->ari_v
^= 0x8000;
225 static inline uint16_t ac_threshold_val (haunp_t hup
, uint16_t tot
) {
226 uint32_t r
= (uint32_t)(hup
->ari_h
-hup
->ari_l
)+1;
227 if (r
== 0) longjmp(hup
->errJP
, ERR_BAD_DATA
);
228 return (uint16_t)((((uint32_t)(hup
->ari_v
-hup
->ari_l
)+1)*tot
-1)/r
);
232 /******************************************************************************/
233 int haunp_reset_io (haunp_t hup
, haunp_bread_fn_t reader
, void *udata
) {
235 memset(hup
, 0, sizeof(*hup
));
236 hup
->reader
= reader
;
238 /* init dictionary */
245 hup
->npt
= hup
->pmax
= 1;
246 for (int i
= 0; i
< TTORD
; ++i
) hup
->ttab
[i
][0] = hup
->ttab
[i
][1] = TTSTEP
;
247 tabinit(hup
->ltab
, LTCODES
, 0);
248 tabinit(hup
->eltab
, LTCODES
, 1);
249 tabinit(hup
->ctab
, CTCODES
, 0);
250 tabinit(hup
->ectab
, CTCODES
, 1);
251 tabinit(hup
->ptab
, PTCODES
, 0);
252 tupd(hup
->ptab
, PTCODES
, MAXPT
, PTSTEP
, 0);
253 /* init arithmetic decoder */
257 hup
->ari_init_done
= 0; /* defer initialization */
259 hup
->rd_size
= RD_BUF_SIZE
;
267 int haunp_reset_buf (haunp_t hup
, const void *buf
, int buf_len
) {
269 haunp_reset_io(hup
, haunp_buf_reader
, NULL
);
272 hup
->buf_left
= (buf_len
> 0 ? buf_len
: 0);
273 hup
->no_more
= (hup
->buf_left
== 0);
280 haunp_t
haunp_open_io (haunp_bread_fn_t reader
, void *udata
) {
281 haunp_t hup
= calloc(1, sizeof(*hup
));
282 if (hup
!= NULL
) haunp_reset_io(hup
, reader
, udata
);
287 haunp_t
haunp_open_buf (const void *buf
, int buf_len
) {
288 haunp_t hup
= calloc(1, sizeof(*hup
));
289 if (hup
!= NULL
) haunp_reset_buf(hup
, buf
, buf_len
);
294 int haunp_close (haunp_t hup
) {
295 if (hup
!= NULL
) free(hup
);
300 /******************************************************************************/
301 static void libha_unpack (haunp_t hup
, uint8_t *obuf
, int olen
) {
302 //uint16_t l, p, tv, i, lt;
304 if (hup
->no_more
) return;
305 /* complete defered ari initialization */
306 if (!hup
->ari_init_done
) {
308 hup
->ari_init_done
= 1;
315 /* if we have some data in dictionary, copy it */
316 if (hup
->dict_pair_len
) {
317 int d
= swd_do_pair(hup
, obuf
, olen
);
319 if ((olen
-= d
) == 0) return;
322 /* main unpacking loop; olen is definitely positive here */
325 uint16_t tv
= ac_threshold_val(hup
, hup
->ttab
[hup
->ttcon
][0]+hup
->ttab
[hup
->ttcon
][1]+1);
326 uint16_t i
= hup
->ttab
[hup
->ttcon
][0]+hup
->ttab
[hup
->ttcon
][1];
327 if (hup
->ttab
[hup
->ttcon
][0] > tv
) {
328 ac_in(hup
, 0, hup
->ttab
[hup
->ttcon
][0], i
+1);
329 hup
->ttab
[hup
->ttcon
][0] += TTSTEP
;
330 if (i
>= MAXTT
) ttscale(hup
, hup
->ttcon
);
331 hup
->ttcon
= (hup
->ttcon
<<1)&TTOMASK
;
332 tv
= ac_threshold_val(hup
, hup
->ctab
[1]+hup
->ces
);
333 if (tv
>= hup
->ctab
[1]) {
334 ac_in(hup
, hup
->ctab
[1], hup
->ctab
[1]+hup
->ces
, hup
->ctab
[1]+hup
->ces
);
335 tv
= ac_threshold_val(hup
, hup
->ectab
[1]);
339 if (lt
+hup
->ectab
[l
] <= tv
) { lt
+= hup
->ectab
[l
]; ++l
; }
340 if (l
>= CTCODES
) { l
-= CTCODES
; break; }
343 ac_in(hup
, lt
, lt
+hup
->ectab
[CTCODES
+l
], hup
->ectab
[1]);
344 tzero(hup
->ectab
, CTCODES
, l
);
345 if (hup
->ectab
[1] != 0) hup
->ces
+= CTSTEP
; else hup
->ces
= 0;
346 for (i
= (l
< CPLEN
? 0 : l
-CPLEN
); i
< (l
+CPLEN
>= CTCODES
-1 ? CTCODES
-1 : l
+CPLEN
); ++i
) {
347 if (hup
->ectab
[CTCODES
+i
]) tupd(hup
->ectab
, CTCODES
, MAXCT
, 1, i
);
353 if (lt
+hup
->ctab
[l
] <= tv
) { lt
+= hup
->ctab
[l
]; ++l
; }
354 if (l
>= CTCODES
) { l
-= CTCODES
; break; }
357 ac_in(hup
, lt
, lt
+hup
->ctab
[CTCODES
+l
], hup
->ctab
[1]+hup
->ces
);
359 tupd(hup
->ctab
, CTCODES
, MAXCT
, CTSTEP
, l
);
360 if (hup
->ctab
[CTCODES
+l
] == CCUTOFF
) hup
->ces
-= (CTSTEP
< hup
->ces
? CTSTEP
: hup
->ces
-1);
361 /* literal char from dictionary */
362 hup
->dict
[hup
->dict_pos
] = l
;
363 if (++hup
->dict_pos
== POSCODES
) hup
->dict_pos
= 0;
365 if (hup
->accnt
< POSCODES
) ++hup
->accnt
;
371 ac_in(hup
, hup
->ttab
[hup
->ttcon
][0], i
, i
+1);
372 hup
->ttab
[hup
->ttcon
][1] += TTSTEP
;
373 if (i
>= MAXTT
) ttscale(hup
, hup
->ttcon
);
374 hup
->ttcon
= ((hup
->ttcon
<<1)|1)&TTOMASK
;
375 while (hup
->accnt
> hup
->pmax
) {
376 tupd(hup
->ptab
, PTCODES
, MAXPT
, PTSTEP
, hup
->npt
++);
379 tv
= ac_threshold_val(hup
, hup
->ptab
[1]);
383 if (lt
+hup
->ptab
[p
] <= tv
) { lt
+= hup
->ptab
[p
]; ++p
; }
384 if (p
>= PTCODES
) { p
-= PTCODES
; break; }
387 ac_in(hup
, lt
, lt
+hup
->ptab
[PTCODES
+p
], hup
->ptab
[1]);
388 tupd(hup
->ptab
, PTCODES
, MAXPT
, PTSTEP
, p
);
390 for (i
= 1; p
; i
<<= 1, --p
) ;
392 l
= (i
== hup
->pmax
>>1 ? hup
->accnt
-(hup
->pmax
>>1) : i
);
393 p
= ac_threshold_val(hup
, l
);
394 ac_in(hup
, p
, p
+1, l
);
397 tv
= ac_threshold_val(hup
, hup
->ltab
[1]+hup
->les
);
398 if (tv
>= hup
->ltab
[1]) {
399 ac_in(hup
, hup
->ltab
[1], hup
->ltab
[1]+hup
->les
, hup
->ltab
[1]+hup
->les
);
400 tv
= ac_threshold_val(hup
, hup
->eltab
[1]);
404 if (lt
+hup
->eltab
[l
] <= tv
) { lt
+= hup
->eltab
[l
]; ++l
; }
405 if (l
>= LTCODES
) { l
-= LTCODES
; break; }
408 ac_in(hup
, lt
, lt
+hup
->eltab
[LTCODES
+l
], hup
->eltab
[1]);
409 tzero(hup
->eltab
, LTCODES
, l
);
410 if (hup
->eltab
[1] != 0) hup
->les
+= LTSTEP
; else hup
->les
= 0;
411 for (i
= l
< LPLEN
? 0 : l
-LPLEN
; i
< (l
+LPLEN
>= LTCODES
-1 ? LTCODES
-1 : l
+LPLEN
); ++i
) {
412 if (hup
->eltab
[LTCODES
+i
]) tupd(hup
->eltab
, LTCODES
, MAXLT
, 1, i
);
418 if (lt
+hup
->ltab
[l
] <= tv
) { lt
+= hup
->ltab
[l
]; ++l
; }
419 if (l
>= LTCODES
) { l
-= LTCODES
; break; }
422 ac_in(hup
, lt
, lt
+hup
->ltab
[LTCODES
+l
], hup
->ltab
[1]+hup
->les
);
424 tupd(hup
->ltab
, LTCODES
, MAXLT
, LTSTEP
, l
);
425 if (hup
->ltab
[LTCODES
+l
] == LCUTOFF
) hup
->les
-= (LTSTEP
< hup
->les
? LTSTEP
: hup
->les
-1);
426 if (l
== SLCODES
-1) {
428 } else if (l
>= SLCODES
) {
429 i
= ac_threshold_val(hup
, LLLEN
);
430 ac_in(hup
, i
, i
+1, LLLEN
);
431 l
= ((l
-SLCODES
)<<LLBITS
)+i
+SLCODES
-1;
434 if (hup
->accnt
< POSCODES
) {
436 if (hup
->accnt
> POSCODES
) hup
->accnt
= POSCODES
;
438 /* pair from dictionary */
439 if (hup
->dict_pos
> p
) {
440 hup
->dict_pair_pos
= hup
->dict_pos
-1-p
;
442 hup
->dict_pair_pos
= POSCODES
-1-p
+hup
->dict_pos
;
444 hup
->dict_pair_len
= l
;
445 goto do_pair
; /* recursive tail call */
448 /*ac_in(hup, i, i+1, i+1); don't need this*/
456 /* return number of bytes read (<len: end of data) or -1 on error */
457 int haunp_read (haunp_t hup
, void *buf
, int len
) {
458 if (buf
== NULL
&& len
< 1) return 0;
460 volatile int jr
= setjmp(hup
->errJP
);
463 libha_unpack(hup
, buf
, len
);
471 /******************************************************************************/
472 #ifndef LIBHAUNP_DISABLE_CRC
473 static const uint32_t crctab
[16] = {
474 0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,
475 0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
476 0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,
477 0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c,
481 unsigned int haunp_crc32 (const void *src
, int len
) {
482 uint32_t crc
= 0xffffffffUL
;
483 if (src
!= NULL
&& len
> 0) {
484 const uint8_t *buf
= (const uint8_t *)src
;
487 crc
= crctab
[crc
&0x0f]^(crc
>>4);
488 crc
= crctab
[crc
&0x0f]^(crc
>>4);
491 return crc
^0xffffffffUL
;
495 unsigned int haunp_crc32_begin (void) {
500 unsigned int haunp_crc32_end (unsigned int crc
) {
501 return crc
^0xffffffffUL
;
505 unsigned int haunp_crc32_part (unsigned int crc
, const void *src
, int len
) {
506 if (src
!= NULL
&& len
> 0) {
507 const uint8_t *buf
= (const uint8_t *)src
;
510 crc
= crctab
[crc
&0x0f]^(crc
>>4);
511 crc
= crctab
[crc
&0x0f]^(crc
>>4);