From b616e8f5773631945962d4b1256f8f2d575e0da1 Mon Sep 17 00:00:00 2001
From: pacien
Date: Mon, 3 Dec 2018 18:16:04 +0100
Subject: optimise lzss prefix lookup with custom hashmap

---
 src/lzss/matchring.nim | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
 create mode 100644 src/lzss/matchring.nim

(limited to 'src/lzss/matchring.nim')

diff --git a/src/lzss/matchring.nim b/src/lzss/matchring.nim
new file mode 100644
index 0000000..a2d45f7
--- /dev/null
+++ b/src/lzss/matchring.nim
@@ -0,0 +1,37 @@
+# gzip-like LZSS compressor
+# Copyright (C) 2018  Pacien TRAN-GIRARD
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU Affero General Public License as
+# published by the Free Software Foundation, either version 3 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 Affero General Public License for more details.
+#
+# You should have received a copy of the GNU Affero General Public License
+# along with this program.  If not, see <https://www.gnu.org/licenses/>.
+
+const matchLimit* = 4
+
+type MatchRing* = object
+  offset, size: int
+  indices: array[matchLimit, int]
+
+proc initMatchRing*(): MatchRing =
+  MatchRing()
+
+proc addMatch*(ring: var MatchRing, index: int) =
+  if ring.size < matchLimit:
+    ring.indices[ring.size] = index
+    ring.size += 1
+  else:
+    let ringIndex = (ring.offset + ring.size) mod matchLimit
+    ring.indices[ringIndex] = index
+    ring.offset = (ring.offset + 1) mod ring.indices.len
+
+iterator items*(ring: MatchRing): int {.closure.} =
+  for i in countdown(ring.size - 1, 0):
+    yield ring.indices[(ring.offset + i) mod ring.indices.len]
-- 
cgit v1.2.3