From 7f6002caba3f0a6749820c2772161caf55b8d267 Mon Sep 17 00:00:00 2001 From: neonloop Date: Fri, 7 May 2021 20:00:12 +0000 Subject: Initial commit (uqm-0.8.0) --- src/libs/decomp/lzencode.c | 468 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 468 insertions(+) create mode 100644 src/libs/decomp/lzencode.c (limited to 'src/libs/decomp/lzencode.c') diff --git a/src/libs/decomp/lzencode.c b/src/libs/decomp/lzencode.c new file mode 100644 index 0000000..e26f344 --- /dev/null +++ b/src/libs/decomp/lzencode.c @@ -0,0 +1,468 @@ +//Copyright Paul Reiche, Fred Ford. 1992-2002 + +/* + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + + /* + * LZHUF.C English version 1.0 + * Based on Japanese version 29-NOV-1988 + * LZSS coded by Haruhiko OKUMURA + * Adaptive Huffman Coding coded by Haruyasu YOSHIZAKI + * Edited and translated to English by Kenji RIKITAKE + */ + +#include +#include "lzh.h" +#include "libs/reslib.h" + +static UWORD match_position, match_length; +static SWORD *lson; +static SWORD *rson; +static SWORD *dad; +static SWORD *encode_arrays; + +#define AllocEncodeArrays() \ + HCalloc ( \ + (((N + 1) + (N + 257) + (N + 1)) \ + * sizeof (lson[0]))) +#define FreeCodeArrays HFree + +static BOOLEAN +InitTree (void) +{ + if ((encode_arrays = AllocEncodeArrays ()) == NULL) + { + FreeCodeArrays (encode_arrays); + encode_arrays = NULL; + return (FALSE); + } + else + { + SWORD i; + + lson = encode_arrays; + rson = lson + (N + 1); + dad = rson + (N + 257); + + for (i = N + 1; i <= N + 256; i++) + rson[i] = NIL; /* root */ + for (i = 0; i < N; i++) + dad[i] = NIL; /* node */ + + return (TRUE); + } +} + +static void +InsertNode (SWORD r) +{ + SWORD p, cmp; + BYTE *lpBuf; + + cmp = 1; + lpBuf = _lpCurCodeDesc->text_buf; + p = N + 1 + lpBuf[r]; + rson[r] = lson[r] = NIL; + match_length = 0; + for (;;) + { + UWORD i; + + if (cmp >= 0) + { + if (rson[p] != NIL) + p = rson[p]; + else + { + rson[p] = r; + dad[r] = p; + return; + } + } + else + { + if (lson[p] != NIL) + p = lson[p]; + else + { + lson[p] = r; + dad[r] = p; + return; + } + } + + i = F; + { + SWORD _r, _p; + + _r = r; + _p = p; + while (--i && (cmp = lpBuf[++_r] - lpBuf[++_p]) == 0) + ; + } + if ((i = F - i) > THRESHOLD) + { + if (i > match_length) + { + match_position = ((r - p) & (N - 1)) - 1; + if ((match_length = i) >= F) + break; + } + else if (i == match_length) + { + if ((i = ((r - p) & (N - 1)) - 1) < match_position) + { + match_position = i; + } + } + } + } + dad[r] = dad[p]; + lson[r] = lson[p]; + rson[r] = rson[p]; + dad[lson[p]] = r; + dad[rson[p]] = r; + if (rson[dad[p]] == p) + rson[dad[p]] = r; + else + lson[dad[p]] = r; + dad[p] = NIL; /* remove p */ +} + +static void +DeleteNode (SWORD p) +{ + SWORD q; + + if (dad[p] == NIL) + return; /* unregistered */ + if (rson[p] == NIL) + q = lson[p]; + else if (lson[p] == NIL) + q = rson[p]; + else + { + q = lson[p]; + if (rson[q] != NIL) + { + do + { + q = rson[q]; + } while (rson[q] != NIL); + rson[dad[q]] = lson[q]; + dad[lson[q]] = dad[q]; + lson[q] = lson[p]; + dad[lson[p]] = q; + } + rson[q] = rson[p]; + dad[rson[p]] = q; + } + dad[q] = dad[p]; + if (rson[dad[p]] == p) + rson[dad[p]] = q; + else + lson[dad[p]] = q; + dad[p] = NIL; +} + +static void +Putcode (SWORD l, UWORD c) +{ + _workbuf |= c >> _workbuflen; + if ((_workbuflen += l) >= 8) + { + OutChar ((BYTE)(_workbuf >> 8)); + ++_lpCurCodeDesc->StreamIndex; + if ((_workbuflen -= 8) >= 8) + { + OutChar ((BYTE)(_workbuf)); + ++_lpCurCodeDesc->StreamIndex; + _workbuflen -= 8; + _workbuf = c << (l - _workbuflen); + } + else + { + _workbuf <<= 8; + } + _workbuf &= 0xFFFF; + } +} + +static void +EncodeChar (UWORD c) +{ + UWORD i; + SWORD j, k; + + i = 0; + j = 0; + k = _lpCurCodeDesc->prnt[c + T]; + + /* search connections from leaf node to the root */ + do + { + i >>= 1; + + /* + if node's address is odd, output 1 + else output 0 + */ + if (k & 1) + i += 0x8000; + + j++; + } while ((k = _lpCurCodeDesc->prnt[k]) != R); + Putcode (j, i); + _update (c + T); +} + +static void +EncodePosition (UWORD c) +{ + UWORD i; + /* + * Tables for encoding/decoding upper 6 bits of + * sliding dictionary pointer + */ + /* encoder table */ + static const BYTE p_len[64] = + { + 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05, + 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06, + 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, + 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, + 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, + 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, + 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08 + }; + + static const BYTE p_code[64] = + { + 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68, + 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C, + 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC, + 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE, + 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE, + 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE, + 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, + 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF + }; + + /* output upper 6 bits with encoding */ + i = c >> 6; + Putcode (p_len[i], (UWORD)p_code[i] << 8); + + /* output lower 6 bits directly */ + Putcode (6, (c & 0x3f) << 10); +} + +static void +UninitTree (void) +{ + if (_workbuflen) + { + OutChar ((BYTE)(_workbuf >> 8)); + ++_lpCurCodeDesc->StreamIndex; + } + + FreeCodeArrays (encode_arrays); + encode_arrays = NULL; + lson = NULL; + rson = NULL; + dad = NULL; +} + +static void +_encode_cleanup (void) +{ + UWORD r, s, last_match_length, len; + + _StreamType = _lpCurCodeDesc->StreamType; + _Stream = _lpCurCodeDesc->Stream; + _workbuf = _lpCurCodeDesc->workbuf; + _workbuflen = _lpCurCodeDesc->workbuflen; + + r = _lpCurCodeDesc->buf_index; + s = _lpCurCodeDesc->restart_index; + last_match_length = _lpCurCodeDesc->bytes_left; + if (_lpCurCodeDesc->StreamLength >= F) + len = F; + else + { + UWORD i; + + for (i = 1; i <= F; i++) + InsertNode (r - i); + InsertNode (r); + + len = (UWORD)_lpCurCodeDesc->StreamLength; + } + + while (1) + { + while (last_match_length--) + { + DeleteNode (s); + if (--len == 0) + { + BYTE lobyte, hibyte; + UWORD loword, hiword; + + UninitTree (); + + _lpCurCodeDesc->StreamIndex += 4; + /* rewind */ + if (_lpCurCodeDesc->StreamType == FILE_STREAM) + SeekResFile ((uio_Stream *)_Stream, + -(int)_lpCurCodeDesc->StreamIndex, SEEK_CUR); + else /* _lpCurCodeDesc->StreamType == MEMORY_STREAM */ + _Stream = (BYTE*)_Stream - _lpCurCodeDesc->StreamIndex; + + loword = LOWORD (_lpCurCodeDesc->StreamLength); + lobyte = LOBYTE (loword); + hibyte = HIBYTE (loword); + OutChar (lobyte); + OutChar (hibyte); + hiword = HIWORD (_lpCurCodeDesc->StreamLength); + lobyte = LOBYTE (hiword); + hibyte = HIBYTE (hiword); + OutChar (lobyte); + OutChar (hibyte); + + return; + } + s = (s + 1) & (N - 1); + r = (r + 1) & (N - 1); + InsertNode (r); + } + if (match_length > len) + match_length = len; + if (match_length <= THRESHOLD) + { + match_length = 1; + EncodeChar (_lpCurCodeDesc->text_buf[r]); + } + else + { + EncodeChar (255 - THRESHOLD + match_length); + EncodePosition (match_position); + } + last_match_length = match_length; + } +} + +COUNT +cwrite (const void *buf, COUNT size, COUNT count, PLZHCODE_DESC lpCodeDesc) +{ + UWORD r, s, last_match_length; + BYTE *lpBuf; + const BYTE *lpStr; + + if ((_lpCurCodeDesc = lpCodeDesc) == 0 + || (size *= count) == 0) + return (0); + + _StreamType = lpCodeDesc->StreamType; + _Stream = lpCodeDesc->Stream; + _workbuf = lpCodeDesc->workbuf; + _workbuflen = lpCodeDesc->workbuflen; + lpStr = (const BYTE *) buf; + lpBuf = lpCodeDesc->text_buf; + + r = lpCodeDesc->buf_index; + s = lpCodeDesc->restart_index; + last_match_length = lpCodeDesc->bytes_left; + if (last_match_length) + { + lpCodeDesc->StreamLength += size; + goto EncodeRestart; + } + else if (lpCodeDesc->StreamLength < F) + { + UWORD i; + + if ((i = (UWORD)lpCodeDesc->StreamLength) == 0) + { + if (!InitTree ()) + return (0); + + _lpCurCodeDesc->StreamIndex = 0; + lpCodeDesc->CleanupFunc = _encode_cleanup; + } + + lpCodeDesc->StreamLength += size; + + for (; i < F && size; ++i, --size) + lpBuf[r + i] = *lpStr++; + if (i < F) + goto EncodeExit; + + for (i = 1; i <= F; i++) + InsertNode (r - i); + InsertNode (r); + if (size == 0) + goto EncodeExit; + } + else + lpCodeDesc->StreamLength += size; + + do + { + if (match_length > F) + match_length = F; + if (match_length <= THRESHOLD) + { + match_length = 1; + EncodeChar (lpBuf[r]); + } + else + { + EncodeChar (255 - THRESHOLD + match_length); + EncodePosition (match_position); + } + last_match_length = match_length; +EncodeRestart: + while (last_match_length && size) + { + BYTE c; + + --size; + --last_match_length; + + DeleteNode (s); + c = *lpStr++; + lpBuf[s] = c; + if (s < F - 1) + lpBuf[s + N] = c; + s = (s + 1) & (N - 1); + r = (r + 1) & (N - 1); + InsertNode (r); + } + } while (last_match_length == 0); + +EncodeExit: + lpCodeDesc->buf_index = r; + lpCodeDesc->restart_index = s; + lpCodeDesc->bytes_left = last_match_length; + + lpCodeDesc->Stream = _Stream; + lpCodeDesc->workbuf = _workbuf; + lpCodeDesc->workbuflen = _workbuflen; + + return (count); +} + -- cgit v1.2.3