This topic was archived here:

https://web.archive.org/web/20230000000000fw_/https://www.zenhax.com/viewtopic.php?t=18125

lvlrk, posted Sun Mar 05, 2023 1:37 am (75676)

---

Can someone please explain included/lzss.c in QuickBMS source version 7.6

edit:
GitHub mirror: https://github.com/gameCrackTools/quickBMS/blob/master/src/included/lzss.c

atom0s, posted Mon Mar 06, 2023 7:28 am (75710)

---

The code itself is pretty well commented. I would suggest you ask more specific questions if you are looking for help in regard to something specific in the code.

lvlrk, posted Mon Mar 06, 2023 3:57 pm (75719)

---

@atom0s
why is using a node tree useful for lzss compression

atom0s, posted Mon Mar 06, 2023 10:09 pm (75726)

---

Would suggest first making sure you understand how LZSS works. You can find a wiki article covering the algorithm here:
https://moddingwiki.shikadi.net/wiki/LZSS_compression

With that, LZSS uses a sliding window approach to walk the data being compressed and look for matches that 'qualify' against a minimum set length of when the data should be substituted. When this happens, it is building a 'dictionary' of results that have already been processed and will be reused in said substitutions. The means of doing the lookups into that dictionary are where a performance hit can be found, which using a binary node tree can greatly improve said performance.

You can find an example of LZSS implementation from Michael Dipperstein here on GitHub:
https://github.com/MichaelDipperstein/lzss

His code demonstrates several methods of handling that lookup (in his code it is referred to as 'FindMatch') such as:

- Brute forcing. (brute.c)
- KMP (kmp.c) (Knuth-Morris-Pratt algorithm: http://en.wikipedia.org/wiki/Knuth-Morr ... _algorithm)
- Linked List (list.c)
- Hash Table (hash.c)
- Binary Tree (tree.c)

He also did a write-up in regards to the algorithm on his site here:
https://michaeldipperstein.github.io/lzss.html

With a focus on the binary tree implementation here:
https://michaeldipperstein.github.io/lz ... inary_tree