' Compression: RLE, dictionary, entropy estimation
#COMPILE EXE
#DIM ALL

FUNCTION RLEncode(BYVAL text AS STRING) AS STRING
    LOCAL i  AS LONG
    LOCAL count  AS LONG
    LOCAL prev  AS STRING
    LOCAL curr  AS STRING
    LOCAL result AS STRING
    result = ""
    IF LEN(text) = 0 THEN FUNCTION = "": EXIT FUNCTION
    prev = MID$(text, 1, 1)
    count = 1
    FOR i = 2 TO LEN(text)
        curr = MID$(text, i, 1)
        IF curr = prev AND count < 255 THEN
            count = count + 1
        ELSE
            result = result + CHR$(count) + prev
            prev = curr
            count = 1
        END IF
    NEXT i
    result = result + CHR$(count) + prev
    FUNCTION = result
END FUNCTION

FUNCTION RLDecode(BYVAL encoded AS STRING) AS STRING
    LOCAL i  AS LONG
    LOCAL count  AS LONG
    LOCAL result AS STRING
    result = ""
    i = 1
    LOCAL k AS LONG
    DO WHILE i < LEN(encoded)
        count = ASC(MID$(encoded, i, 1))
        FOR k = 1 TO count
            result = result + MID$(encoded, i + 1, 1)
        NEXT k
        i = i + 2
    LOOP
    FUNCTION = result
END FUNCTION

FUNCTION SimpleChecksum(BYVAL data AS STRING) AS LONG
    LOCAL i  AS LONG
    LOCAL sum  AS LONG
    sum = 0
    FOR i = 1 TO LEN(data)
        sum = (sum + ASC(MID$(data, i, 1))) MOD 65536
    NEXT i
    FUNCTION = sum
END FUNCTION

FUNCTION EstimateEntropy(BYVAL text AS STRING) AS DOUBLE
    LOCAL i  AS LONG
    LOCAL c  AS LONG
    LOCAL freq(0 TO 255) AS DOUBLE
    LOCAL total  AS DOUBLE
    LOCAL entropy  AS DOUBLE
    LOCAL p  AS DOUBLE
    total = LEN(text)
    IF total = 0 THEN FUNCTION = 0.0: EXIT FUNCTION
    FOR i = 1 TO total
        c = ASC(MID$(text, i, 1))
        freq(c) = freq(c) + 1.0
    NEXT i
    entropy = 0.0
    FOR i = 0 TO 255
        IF freq(i) > 0 THEN
            p = freq(i) / total
            entropy = entropy - (p * LOG(p) / LOG(2.0))
        END IF
    NEXT i
    FUNCTION = entropy
END FUNCTION

FUNCTION CompressionPercent(BYVAL orig AS STRING, comp AS STRING) AS DOUBLE
    IF LEN(orig) = 0 THEN FUNCTION = 1.0: EXIT FUNCTION
    FUNCTION = LEN(comp) / LEN(orig) * 100.0
END FUNCTION

FUNCTION TestRLE(BYVAL text AS STRING) AS STRING
    LOCAL enc  AS STRING
    LOCAL dec  AS STRING
    enc = RLEncode(text)
    dec = RLDecode(enc)
    IF dec = text THEN
        FUNCTION = "RLE: " + FORMAT$(LEN(text)) + " -> " + FORMAT$(LEN(enc)) + " (" + FORMAT$(CompressionPercent(text, enc), "##0.0") + "%) PASS"
    ELSE
        FUNCTION = "RLE: FAIL"
    END IF
END FUNCTION

FUNCTION PBMAIN() AS LONG
    LOCAL text  AS STRING
    LOCAL enc  AS STRING
    LOCAL dec  AS STRING
    PRINT "=== String Compression ==="
    PRINT
    PRINT TestRLE("AAABBBCCCDDDAAABBBCCCDDD")
    PRINT TestRLE("AAAAAAAAAAAAAAAAAAAAAAAAAA")
    PRINT TestRLE("ABABABABABABABABAB")
    PRINT TestRLE("The quick brown fox jumps over the lazy dog")
    PRINT
    text = "TOBEORNOTTOBEORTOBEORNOT"
    enc = RLEncode(text)
    dec = RLDecode(enc)
    PRINT "RLE of '" + text + "': " + FORMAT$(LEN(text)) + "->" + FORMAT$(LEN(enc)) + " bytes"
    PRINT "RLE verify: "
    IF dec = text THEN PRINT "PASS" ELSE PRINT "FAIL"
    PRINT
    text = "The quick brown fox jumps over the lazy dog"
    PRINT "Entropy: " + FORMAT$(EstimateEntropy(text), "#0.000") + " bits/char"
    text = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
    PRINT "Low entropy: " + FORMAT$(EstimateEntropy(text), "#0.000") + " bits/char"
    PRINT
    PRINT "Checksum of 'Hello': " + FORMAT$(SimpleChecksum("Hello"))
    PRINT "Checksum of 'World': " + FORMAT$(SimpleChecksum("World"))
    PRINT
    PRINT "Compression tests complete."
    FUNCTION = 0
END FUNCTION
