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/update.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 115 insertions(+)
 create mode 100644 src/libs/decomp/update.c

(limited to 'src/libs/decomp/update.c')

diff --git a/src/libs/decomp/update.c b/src/libs/decomp/update.c
new file mode 100644
index 0000000..13de988
--- /dev/null
+++ b/src/libs/decomp/update.c
@@ -0,0 +1,115 @@
+//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.
+ */
+
+#include <string.h>
+#include "lzh.h"
+
+static void
+reconst (void)
+{
+	COUNT i, j;
+
+	/* halven cumulative freq for leaf nodes */
+	j = 0;
+	for (i = 0; i < T; i++)
+	{
+		if (_lpCurCodeDesc->son[i] >= T)
+		{
+			_lpCurCodeDesc->freq[j] = (_lpCurCodeDesc->freq[i] + 1) >> 1;
+			_lpCurCodeDesc->son[j] = _lpCurCodeDesc->son[i];
+			j++;
+		}
+	}
+	/* make a tree : first, connect children nodes */
+	for (i = 0, j = N_CHAR; j < T; i += 2, j++)
+	{
+		SWORD k;
+		UWORD f, l;
+
+		k = i + 1;
+		f = _lpCurCodeDesc->freq[j] = _lpCurCodeDesc->freq[i] + _lpCurCodeDesc->freq[k];
+		for (k = j - 1; f < _lpCurCodeDesc->freq[k]; k--)
+			;
+		k++;
+		l = (j - k);
+		
+		memmove (_lpCurCodeDesc->freq + k + 1, _lpCurCodeDesc->freq + k,
+				sizeof(_lpCurCodeDesc->freq[0]) * l);
+		_lpCurCodeDesc->freq[k] = f;
+		memmove (_lpCurCodeDesc->son + k + 1, _lpCurCodeDesc->son + k,
+				sizeof(_lpCurCodeDesc->son[0]) * l);
+		_lpCurCodeDesc->son[k] = i;
+	}
+	/* connect parent nodes */
+	for (i = 0; i < T; i++)
+	{
+		if ((j = _lpCurCodeDesc->son[i]) >= T)
+			_lpCurCodeDesc->prnt[j] = i;
+		else
+			_lpCurCodeDesc->prnt[j] = _lpCurCodeDesc->prnt[j + 1] = i;
+	}
+}
+
+
+/* update freq tree */
+
+void
+_update (COUNT c)
+{
+	PLZHCODE_DESC lpCD;
+
+	if ((lpCD = _lpCurCodeDesc)->freq[R] == MAX_FREQ)
+		reconst ();
+
+	c = lpCD->prnt[c];
+	do
+	{
+		COUNT i, l;
+
+		i = ++lpCD->freq[c];
+
+		/* swap nodes to keep the tree freq-ordered */
+		if (i > lpCD->freq[l = c + 1])
+		{
+			COUNT j;
+
+			while (i > lpCD->freq[++l])
+				;
+			l--;
+			lpCD->freq[c] = lpCD->freq[l];
+			lpCD->freq[l] = i;
+
+			i = lpCD->son[c];
+			j = lpCD->son[l];
+			lpCD->son[l] = i;
+			lpCD->son[c] = j;
+
+			lpCD->prnt[i] = l;
+			if (i < T)
+				lpCD->prnt[i + 1] = l;
+
+			lpCD->prnt[j] = c;
+			if (j < T)
+				lpCD->prnt[j + 1] = c;
+
+			c = l;
+		}
+	} while ((c = lpCD->prnt[c]) != 0); /* do it until reaching the root */
+}
+
+
-- 
cgit v1.2.3