optimise lzss prefix lookup with custom hashmap

1 files changed, 15 insertions, 17 deletions

diff --git a/src/lzss/matchtable.nim b/src/lzss/matchtable.nim
index cc04f49..879f47d 100644
--- a/src/lzss/matchtable.nim
+++ b/src/lzss/matchtable.nim
@@ -15,25 +15,23 @@
 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
 import tables
+import matchring
 
-type MatchTable*[K, V] = ref object
-  matchLimit: int
-  table: TableRef[K, seq[V]]
+const matchGroupLength = 3
+const hashShift = 5
+const tableHeight = 0b1 shl 15
 
-proc initMatchTable*[K, V](keyType: typedesc[K], valueType: typedesc[V], matchLimit = 5): MatchTable[K, V] =
-  MatchTable[K, V](matchLimit: matchLimit, table: newTable[K, seq[V]]())
+type MatchTable* = object
+  table: array[tableHeight, MatchRing]
 
-proc len*[K, V](matchTable: MatchTable[K, V]): int =
-  matchTable.table.len
+proc initMatchTable*(): MatchTable =
+  result = MatchTable()
 
-proc matchList*[K, V](matchTable: MatchTable[K, V], pattern: K): seq[V] =
-  if matchTable.table.hasKey(pattern):
-    matchTable.table[pattern]
-  else:
-    newSeqOfCap[V](matchTable.matchLimit)
+proc hash(pattern: array[matchGroupLength, uint8]): int =
+  ((pattern[0].int shl (hashShift * 2)) xor (pattern[1].int shl hashShift) xor pattern[2].int) mod tableHeight
 
-proc addMatch*[K, V](matchTable: MatchTable[K, V], pattern: K, value: V) =
-  var matchList = matchTable.matchList(pattern)
-  if matchList.len >= matchTable.matchLimit: matchList.del(matchList.len - 1)
-  matchList.insert(value)
-  matchTable.table[pattern] = matchList
+proc addMatch*(matchTable: var MatchTable, pattern: array[matchGroupLength, uint8], index: int) =
+  matchTable.table[hash(pattern)].addMatch(index)
+
+proc candidates*(matchTable: MatchTable, pattern: array[matchGroupLength, uint8]): MatchRing =
+  matchTable.table[hash(pattern)]