summaryrefslogtreecommitdiff
path: root/src/libs/decomp/lzencode.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/libs/decomp/lzencode.c')
-rw-r--r--src/libs/decomp/lzencode.c468
1 files changed, 468 insertions, 0 deletions
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 <stdio.h>
+#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);
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-06 12:35:18 +0000