#include "Huffman.au3"


#Region UDF Zeug von Mars
Global $D2BA[256], $D2BB[256], $D2BC[11111112]
Global Const $D2B_DPT = _DecToBinPrefixTable() ; Default Prefix Table

__DecToBinStartup()
#EndRegion



Test()


Func Test()

	; read out the autoitscript.com page as example string
	Local $sString = BinaryToString(InetRead("https://autoitscript.com"))
	ConsoleWrite("Original Size: " & BinaryLen(StringToBinary($sString)) & " Bytes" & @CRLF)

	; precompress at text level by word repetition:
	Local $sStringCompressed = _strcmp_compressByWordRepetition($sString)

	; determine the chars and their specific number inside the string
	Local $aSymbols = _huff_getUniqueCharArray($sStringCompressed)

	; build a normal huff-table out of the symbol list
	Local $aHuffTable = _huff_buildCodeTable($aSymbols)

	; convert Huffmann codes to canonical form
	_huff_convert2CanonicalHuffman($aHuffTable)

	Local $bHuffCompressed = _huff_compressCanonicalHuffTable($aHuffTable)

	ConsoleWrite('TreeCompress1: ' & $bHuffCompressed & @CRLF & 'Len: ' & BinaryLen($bHuffCompressed) & ' Bytes (Type = ' & VarGetType($bHuffCompressed) & ')' & @CRLF)

	Local $bHuffCompressed2 = _huff_compressCanonicalHuffTable2($aHuffTable)

	ConsoleWrite('TreeCompress2: ' & $bHuffCompressed2 & @CRLF & 'Len: ' & BinaryLen($bHuffCompressed2) & ' Bytes (Type = ' & VarGetType($bHuffCompressed2) & ')' & @CRLF)

	; hoffentlich klappts auch andersherum :D

	Local $aHuffDecompressed = _huff_decompressCanonicalHuffTable($bHuffCompressed)

;~ 	_ArrayDisplay($aHuffDecompressed)

	Local $aHuffDecompressed2 = _huff_decompressCanonicalHuffTable2($bHuffCompressed2)

;~ 	_ArrayDisplay($aHuffDecompressed2)

	For $i = 0 To UBound($aHuffDecompressed) - 1 Step 1
		If $aHuffDecompressed[$i][0] <> $aHuffDecompressed2[$i][0] Or _
			$aHuffDecompressed[$i][0] <> $aHuffDecompressed2[$i][0] Or _
			$aHuffDecompressed[$i][0] <> $aHuffDecompressed2[$i][0] Or _
			$aHuffDecompressed[$i][0] <> $aHuffDecompressed2[$i][0] Then
			ConsoleWrite('Error at index: ' & $i & @CRLF)
		EndIf
	Next




	; Mal schauen ob die Kompression ansich noch funktioniert:
	; encode the string with a canonical huffman encoding
	Global $bEncoded = _huff_encodeString2($sStringCompressed)
	ConsoleWrite("Encoded Size:  " & BinaryLen($bEncoded) & " Bytes" & @CRLF & _
		"Compress ratio: " & Round((1 - (BinaryLen($bEncoded) / BinaryLen(StringToBinary($sString)))) * 100.0, 1) & ' %' & @CRLF)

	; decode the string out of the binary
	Global $sStringDecoded = _huff_decodeBinary2($bEncoded)

	; decompress at text level
	$sStringDecoded = _strcmp_decompressByWordRepetition($sStringDecoded)

;~ 	ConsoleWrite($sStringDecoded & @CRLF)

	; check if original and decoded string are the same
	ConsoleWrite("$sString == $sStringDecoded: " & ($sString == $sStringDecoded) & @CRLF)



EndFunc

Func _huff_decodeBinary2(ByRef $bEncoded)
	Local 	$aHuffTable = _huff_decompressCanonicalHuffTable2($bEncoded), _
			$iEndHuffTable = @extended

	; mirror bits of the values
	; Reverse bit direction of the individual values (so that readout works)
	For $i = 0 To UBound($aHuffTable) - 1
		$aHuffTable[$i][$__HUFF_CODEVALUE] = _bin_mirrorBits($aHuffTable[$i][$__HUFF_CODEVALUE], $aHuffTable[$i][$__HUFF_eCODELENGTH])
	Next

	; extract the encoded data from the whole binary
	Local $bCompressedString = BinaryMid($bEncoded, $iEndHuffTable)

	; convert back huff-encoded stream into string
	Return _huff_decodeBinaryToString($bCompressedString, $aHuffTable)

EndFunc

Func _huff_encodeString2(ByRef $sString)

	; determine the chars and their specific number inside the string
	Local $aSymbols = _huff_getUniqueCharArray($sString)
;~ 	_ArrayDisplay($aSymbols, 'aSymbols')

	; build a normal huff-table out of the symbol list
	Local $aHuffTable = _huff_buildCodeTable($aSymbols)
;~ 	_ArrayDisplay($aHuffTable, "Huff-table", "", 64, "|", "char|binary representation|value|bits")

	; convert Huffmann codes to canonical form
	_huff_convert2CanonicalHuffman($aHuffTable)
;~ 	_ArrayDisplay($aHuffTable, "Huff-table canonical", "", 64, "|", "char|binary representation|value|bits")

	; Reverse bit direction of the individual values (so that readout works)
	For $i = 0 To UBound($aHuffTable) - 1
		$aHuffTable[$i][$__HUFF_CODEVALUE] = _bin_mirrorBits($aHuffTable[$i][$__HUFF_CODEVALUE], $aHuffTable[$i][$__HUFF_eCODELENGTH])
	Next
	;~ _ArrayDisplay($aHuffTable, "Huff-table sorted", "", 64, "|", "char|binary representation|value|bits")

	; encode every char of the string with it's huffman-code:
	Local $aStringEncodedTable = _huff_encodeString2CodeArray($aHuffTable, $sString)
	;~ _ArrayDisplay($aStringEncodedTable, "encoded chars of string", "", 64, "|", "value|n bits")

	; convert the value array into a bitstream (= huffman encoded representation of the string)
	Local $bCompressedString = _bin_BitArray2Memory($aStringEncodedTable)
	;~ ConsoleWrite(StringLeft($bCompressedString, 20) & @CRLF)

	; compress the canonical huff-table (list of chars and their huffman-codes in canonical form) into a binary
	Local $bHuffCompressed = _huff_compressCanonicalHuffTable2($aHuffTable)
;~ 	ConsoleWrite($bHuffCompressed & @CRLF)

	; create total compressed data
	Local $tCompressed = DllStructCreate("align 1;Byte Hufftable[" & BinaryLen($bHuffCompressed) & "];Byte StringCompressed[" & BinaryLen($bCompressedString)  & "]")
	DllStructSetData($tCompressed, 1, $bHuffCompressed)
	DllStructSetData($tCompressed, 2, $bCompressedString)

	Return _bin_StructToBin($tCompressed)
EndFunc




Func CompressSymbolList(ByRef $aList)
	; Einfach aus Jux -> Mache eine Permutation daraus und komprimiere die stattdessen :D

	Local $aPerm = GetPermutation($aList)
	Local $sPerm = Compress4($aPerm)
;~ 	ConsoleWrite('Perm:       ' & $sPerm & @CRLF)
;~ 	ConsoleWrite('len: ' & StringLen($sPerm) / 8 & ' Bytes' & @CRLF)
;~ 	ConsoleWrite('randomness: ' & GetRandomness($aPerm) & @CRLF)

	_ArraySort($aList)

	Local $sCompressedSortedList = CompressSortedList($aList)

;~ 	ConsoleWrite('SortedList: ' & $sCompressedSortedList & @CRLF)
;~ 	ConsoleWrite('len: ' & StringLen($sCompressedSortedList) / 8 & ' Bytes' & @CRLF)

;~ 	ConsoleWrite('binary: ' & $sPerm & $sCompressedSortedList & @CRLF)

	Local $sRet = _BinCap8($sPerm & $sCompressedSortedList)

	Local $bRet = DllStructCreate('align 1;Byte Symbols[' & StringLen($sRet) / 8 & ']'), $v
	For $i = 0 To StringLen($sRet) / 8 - 1 Step 1
		DllStructSetData($bRet, 1, _BinToDec(StringMid($sRet, $i * 8 + 1, 8)), $i + 1)
	Next

	Return _bin_StructToBin($bRet)

EndFunc

Func CompressSortedList($aList)

	Local $aCopy[UBound($aList)] = [$aList[0]]
	For $i = 1 To UBound($aList) - 1 Step 1
		$aCopy[$i] = $aList[$i] - $aList[$i-1]
	Next
	Local $iMin = $aCopy[0], $iMax = $iMin
	For $i = 1 To UBound($aList) - 1 Step 1
		If $iMin > $aCopy[$i] Then $iMin = $aCopy[$i]
		If $iMax < $aCopy[$i] Then $iMax = $aCopy[$i]
	Next
	; Min ist quasi immer 1, außer man hat echt seltsamen Input. Aber wir nehmen iMin trotzdem mit.
	; Max ist irgendwo
	Local $sCompressedSortedList = _DecToBinA($iMin) & _DecToBinA($iMax) & _DecToBinA(UBound($aCopy) - 1)

	; etwa 1/x³, ab maximal 10 ist der Wert aber konstant. naja so pi mal daumen.
	Local $aHist[$iMax - $iMin + 1]
	For $i = 0 To UBound($aHist) - 1 Step 1
		$aHist[$i] = 1 / ($i+1)^3
		If $aHist[$i] < 0.001 Then $aHist[$i] = 0.001
	Next

	Local $aLUT = __AHE_SymbolHistogramToLookup($aHist)

	For $i = 0 To UBound($aCopy) - 1 Step 1
		$sCompressedSortedList &= $aLUT[$aCopy[$i] - $iMin]
	Next

	Return $sCompressedSortedList
EndFunc

Func Swap(ByRef $a, ByRef $b)
	Local $_ = $a
	$a = $b
	$b = $_
EndFunc

Func Compress4($P)
	; 4te Version einer Testfunktion. Benutzt quasi inverses lineares Swapsort (also immer Swap(currentIndex, target)
	; und danach currentIndex++) um eine Permutation aus einer "sortierten Liste" (also die Zahlen 0 bis n) zu rekonstruieren.
	; Dabei muss immer nur das target gespeichert werden.
	Local $u = UBound($P), $sRet = _DecToBinA($u), $iBitrate = 0, $mP[$u], $mI[$u]
	For $i = 0 To $u - 1 Step 1
		$mP[$i] = $i
		$mI[$i] = $i ; Inverse Liste (zu Beginn identisch)
	Next
	For $i = 0 To $u - 2 Step 1
		$ii = $mI[$P[$i]] ; Position kann man direkt nachschlagen statt zu suchen -> lineare Laufzeit.
		Swap($mI[$mP[$i]], $mI[$mP[$ii]]) ; Inverse Swap
		Swap($mP[$i], $mP[$ii])
		$iBitrate = ($u - $i) = 0 ? 0 : Ceiling(Log(($u - $i))/Log(2))
		Local $aHist[$u - $i]
		For $j = 0 To UBound($aHist) - 1 Step 1
			$aHist[$j] = 1
		Next
		Local $LUT = __AHE_SymbolHistogramToLookup($aHist)
;~ 		_ArrayDisplay($LUT, $i)
;~ 		ConsoleWrite('RangeToEncode: [0, ' & ($u - $i - 1) & '] -> ' & $iBitrate & ' Bit')
		If $iBitrate > 1 Then
;~ 			ConsoleWrite(' value = ' & ($ii - $i) & @CRLF)
			$sRet &= $LUT[$ii - $i]
		Else
			$sRet &= _DecToBin($ii - $i, $iBitrate)
		EndIf

	Next
	Return $sRet
EndFunc

Func GetPermutation(ByRef $aList)
	; Obacht diese Version hier funktioniert ausschließlich
	; Wenn die Liste jedes Element maximal 1x enthält.
	; Sobald doppelte vorkommen geht das nicht mehr.
	Local $aCopy = $aList, $aPerm[UBound($aList)]
	_ArraySort($aCopy)
	For $i = 0 To UBound($aList) - 1 Step 1
		For $j = 0 To UBound($aList) - 1 Step 1
			If $aList[$i] = $aCopy[$j] Then
				$aPerm[$i] = $j
				ExitLoop
			EndIf
		Next
	Next
	Return $aPerm
EndFunc

Func _huff_compressCanonicalHuffTable2(ByRef $aHuffTable)
	Local $bLengthArray = __huff_createLengthArrayCompressed($aHuffTable)

	Local $aSymbolsInOrder[UBound($aHuffTable)]
	For $i = 0 To UBound($aHuffTable) - 1 Step 1
		$aSymbolsInOrder[$i] = Asc($aHuffTable[$i][$__HUFF_eHUFFVALUE])
	Next
	Local $bSymbolsInOrder = CompressSymbolList($aSymbolsInOrder)

;~ 	ConsoleWrite('Symbollistlen: ' & BinaryLen($bSymbolsInOrder) & @CRLF)

	Local $tHuffCanonic = DllStructCreate("align 1;Byte Lengths[" & BinaryLen($bLengthArray) & "]; Byte Symbols[" & BinaryLen($bSymbolsInOrder) & "]")
	DllStructSetData($tHuffCanonic, 1, $bLengthArray)
	DllStructSetData($tHuffCanonic, 2, $bSymbolsInOrder)

;~ 	ConsoleWrite('Lengths: ' & $bLengthArray & @CRLF)
;~ 	ConsoleWrite('Symbols: ' & $bSymbolsInOrder & @CRLF)


	Return _bin_StructToBin($tHuffCanonic)
EndFunc


Func DecompressSortedList(ByRef $sBinary)
	Local $iStartLen = StringLen($sBinary)
	Local $iMin = _BinToDecA($sBinary)
	$sBinary = StringTrimLeft($sBinary, @extended)
	Local $iMax = _BinToDecA($sBinary)
	$sBinary = StringTrimLeft($sBinary, @extended)
	Local $iUboundMinus1 = _BinToDecA($sBinary)
	$sBinary = StringTrimLeft($sBinary, @extended)

	Local $aHist[$iMax - $iMin + 1]
	For $i = 0 To UBound($aHist) - 1 Step 1
		$aHist[$i] = 1 / ($i+1)^3
		If $aHist[$i] < 0.001 Then $aHist[$i] = 0.001
	Next
	Local $T[UBound($aHist) * 2][3]
	__AHE_BuildTreeFromSymbolHistogram($aHist, $T)

	Local $sList = '' ; Zu faul jetzt auf die schnelle eine UDF mit dynamischen Arrays zu verwenden.

;~ 	_ArrayDisplay($aLUT)
	For $i = 0 To $iUboundMinus1 Step 1
		$ii = __AHE_TreeSingleLookup($T, $sBinary)
		$sList &= ($ii + $iMin) & '|'
	Next

	Local $aList = StringSplit(StringTrimRight($sList, 1), '|', 2)
	For $i = 1 To UBound($aList) - 1 Step 1
		$aList[$i] += $aList[$i-1]
	Next
	Return SetExtended($iStartLen - StringLen($sBinary), $aList)

EndFunc

Func RestoreCharacters($bBinary)
	Local $iLen = 0, $sBinary = ''
	For $i = 0 To BinaryLen($bBinary) - 1 Step 1 ; Das ist höchst ineffizient hier, weil die Länge bei mir nirgends gespeichert wird.
		$sBinary &= _DecToBin(BinaryMid($bBinary, $i + 1 , 2), 8)
	Next
	$sBinary = _BinCap8($sBinary, True)
	$iLen += @extended
	Local $aPerm = Decompress4($sBinary) ; entfernt [1. PERMUTATION] aus $sBinary (da es von Links arbeitet und die bits auffrisst)
	$iLen += @extended
	Local $aList = DecompressSortedList($sBinary)
	$iLen += @extended

	; Aus der Permutation und der sortierten Liste die Originalliste machen.
	Local $aCopy[UBound($aList)]
	For $i = 0 To UBound($aList) - 1 Step 1
		$aCopy[$i] = Chr($aList[$aPerm[$i]])
	Next

	Return SetExtended($iLen / 8, $aCopy)
EndFunc



Func Decompress4(ByRef $s) ; TODO
	Local $iStartLen = StringLen($s)
	Local $iLen = _BinToDecA($s), $iBitOffset = @extended + 1, $aRet[$iLen], $iBitrate = 0, $ii = 0
	$s = StringTrimLeft($s, $iBitOffset - 1)
	For $i = 0 To $iLen - 1 Step 1
		$aRet[$i] = $i
	Next
	For $i = 0 To $iLen - 2 Step 1
		$iBitrate = ($iLen - $i) = 0 ? 0 : Ceiling(Log($iLen - $i)/Log(2))
		If $iBitrate > 1 Then
			Local $aHist[$iLen - $i]
			For $j = 0 To UBound($aHist) - 1 Step 1
				$aHist[$j] = 1
			Next
			Local $T[UBound($aHist) * 2][3]
			__AHE_BuildTreeFromSymbolHistogram($aHist, $T)
			$ii = __AHE_TreeSingleLookup($T, $s)
		Else
			$ii = Int(StringLeft($s, 1))
			$s = StringTrimLeft($s, 1)
		EndIf
		Swap($aRet[$i], $aRet[$ii + $i])
	Next
	Return SetExtended($iStartLen - StringLen($s), $aRet)
EndFunc


Func _huff_decompressCanonicalHuffTable2(ByRef $bHuffCompressed)
	; The first 2 bytes contain information about the maximum number of bits for the values as well as the maximum number of bits needed to encode the number per length.
	Local $iLenMax = Int(BinaryMid($bHuffCompressed, 1, 1)), _
		  $nBitsMax = Int(BinaryMid($bHuffCompressed, 2, 1))


	; restores the array in which the number of bits of length of the elements in the bitstream is written one after the other.
	Local $aBitsPerElement[$iLenMax], $nBitsForLengths
	For $i = 1 To $iLenMax
		$aBitsPerElement[$i-1] = _Min(2^$i, $nBitsMax)
		$nBitsForLengths += $aBitsPerElement[$i-1]
	Next

	; rebuilds the array from the bitstream with the number of elements per code length
	Local 	$iStartLengths = 3, _
			$iSizeLengths  = Ceiling($nBitsForLengths / 8), _ 		           							; lengths-array: start and size
			$bLengthArea   = BinaryMid($bHuffCompressed, $iStartLengths, $iSizeLengths), _         		; the raw length array binary
			$aElsPerLength = _bin_BitStreamToArray($bLengthArea, $aBitsPerElement), _              		; reconstructed array from binary  , $nBytes4Length = @extended
			$iStartChars   = $iStartLengths + $iSizeLengths                                     		; start of chars-area
			;$nSizeCharArea = _bin_BinToDataType(BinaryMid($bHuffCompressed, $iStartChars, 2), "USHORT") ; size in bytes for the chars string

	; Determine the total size of the huffman table
	Local $nElements = 0
	For $i In $aElsPerLength
		$nElements += $i
	Next

	; Restore characters
	Local $aChars = RestoreCharacters(BinaryMid($bHuffCompressed, $iStartChars))
	Local $nSizeCharArea = @extended - 2
;~ 	Local $aChars = StringSplit(BinaryToString(BinaryMid($bHuffCompressed, $iStartChars + 2, $nSizeCharArea), 4), "", 2)

	; reconstruct the values of the canonical Huff table based on the number of respective elements per bit length:
	Local 	$aHuffTable[$nElements][$_HUFF_TABLE_ELEMENT_SIZE], $iVal = 0, $iEl = 0, $iLength = 1

	For $iElements In $aElsPerLength
		For $i = 0 To $iElements - 1
			$iVal += 1

			$aHuffTable[$iEl][$__HUFF_CODEVALUE] = $iVal - 1
			$aHuffTable[$iEl][$__HUFF_eCODELENGTH] = $iLength
			$aHuffTable[$iEl][$__HUFF_eHUFFVALUE] = $aChars[$iEl]
			;~ $aHuffTable[$iEl][$__HUFF_eHUFFCODESTRING] = __huff_Int2BinString($iVal - 1, $iLength)

			$iEl += 1
		Next
		$iVal = BitShift($iVal, -1)
		$iLength += 1
	Next

	; values are still different, because a mirrorbits still has to be done
;~ 	ConsoleWrite($iStartChars + $nSizeCharArea + 2 & @CRLF)
	Return SetExtended($iStartChars + $nSizeCharArea + 2, $aHuffTable)
EndFunc












; Tokenbasierte Kompression - ersetzt wiederholende Teile durch Nummern im Text
Func _strcmp_compressByWordRepetition($sString)
	Local 	$mTmp[3], $aTmp[2], $mPos, $iLen, _
			$mWords[], _
			$iPos = 1, _
			$sWord, $iWord = 0

	; Bereits vorhandene Präfixnummern escapen:
	$sString = StringRegExpReplace($sString, '(?s)\b(\d+)', Chr(27) & "$1")

	; Einzelne Wörter aus dem String extrahieren
	Do
		$aMatch = StringRegExp($sString, '(?s)\G.*?(\b[a-zA-ZäöüßÄÖÜ][\wäöüßÄÖÜ]{2,}\b)', 1, $iPos)
		IF @error Then ExitLoop
		$iPos = @extended
		$sWord = $aMatch[0]

		If MapExists($mWords, $sWord) Then
			$aTmp = $mWords[$sWord]
			$mTmp = $aTmp[1]
			MapAppend($mTmp, $iPos - StringLen($sWord))
			$aTmp[1] = $mTmp
		Else
			Local $mTmp[]
			Local $aTmp[2] = [$iWord, $mTmp]
		EndIf
		$mWords[$sWord] = $aTmp

		$iWord += 1
	Until 0

	; bereite die notwendigen Replaces auf
	Local $aReplaces[$iWord][3], $iIndRepl = 0
	For $sWord In MapKeys($mWords)
		$iLen = StringLen($sWord)
		$aTmp = $mWords[$sWord]
		$iWord = $aTmp[0]
		$mPos = $aTmp[1]

		If Ubound($mPos) < 1 Then ContinueLoop
		If $iLen <= Stringlen($iWord) Then ContinueLoop

		For $i In MapKeys($mPos)
			$iPos = $mPos[$i]

			$aReplaces[$iIndRepl][0] = $iPos
			$aReplaces[$iIndRepl][1] = $iLen
			$aReplaces[$iIndRepl][2] = $iWord

			$iIndRepl += 1

		Next
	Next
	Redim $aReplaces[$iIndRepl][3]
	_ArraySort($aReplaces)

	; Wörter durch Nummern im Text selbst ersetzen
	For $i = UBound($aReplaces) - 1 To 0 Step -1
		$sString = 	StringLeft($sString, $aReplaces[$i][0] - 1) & _
					$aReplaces[$i][2] & _
					StringTrimLeft($sString, $aReplaces[$i][0] + $aReplaces[$i][1] -1)
	Next

	Return $sString
EndFunc


; Tokenbasierte Dekompression - stellt einen mit _strcmp_compressByWordRepetition() komprimierten String wieder her
Func _strcmp_decompressByWordRepetition($sString)
	Local 	$aTmp[3], _
			$mWords[]
			$iPos = 1

	; Einzelne Wörter aus dem String extrahieren
	Do
		$aMatch = StringRegExp($sString, '(?s)\G.*?(\b[a-zA-ZäöüßÄÖÜ][\wäöüßÄÖÜ]{2,}\b|\b(?<!\x1B)\d+\b)', 1, $iPos)
		IF @error Then ExitLoop
		$iPos = @extended

		$aTmp[0] = $aMatch[0]
		$aTmp[1] = $iPos - StringLen($aMatch[0])
		$aTmp[2] = StringLen($aMatch[0])
		MapAppend($mWords, $aTmp)
	Until 0

	Local $aWords = _map_IntMap2Array($mWords)
	$aWords = _ArrayAinATo2d($aWords)

	; Nummern wieder durch Buchstaben ersetzen
	Local $iWord
	For $i = UBound($aWords) - 1  To 0 Step -1
		If Not StringRegExp($aWords[$i][0], "^\d+$", 0) Then ContinueLoop

		$iWord = Int($aWords[$i][0])
		If $iWord >= UBound($aWords) Then ContinueLoop
		;~ ConsoleWrite($iWord & @CRLF)
		$sString = 	StringLeft($sString, $aWords[$i][1] - 1) & _
					$aWords[$iWord][0] & _
					StringTrimLeft($sString, $aWords[$i][1] + $aWords[$i][2] -1)
	Next

	; Escapte Zahlen wieder unescapen:
	$sString = StringRegExpReplace($sString, '(?s)\x1B(\d+)', "$1")

	Return $sString
EndFunc

; #FUNCTION# ======================================================================================
; Name ..........: _map_IntMap2Array()
; Description ...: returns the values of a map only (useful for array-list like maps produced by MapAppend())
; Syntax ........: _map_IntMap2Array(ByRef $aMap)
; Parameters ....: ByRef $aMap - a map variable
; Return values .: 1D-array containing the values
; Author ........: aspirinjunkie
; Modified ......: 2022-07-13
; =================================================================================================
Func _map_IntMap2Array(ByRef $aMap)
	Local $aRet[UBound($aMap)]
	Local $iInd = 0
	For $vEl In $aMap
		$aRet[$iInd] = $vEl
		$iInd += 1
	Next
	Return $aRet
EndFunc   ;==>_map_IntMap2Array


; #FUNCTION# ======================================================================================
; Name ..........: _ArrayAinATo2d()
; Description ...: Convert a Arrays in Array into a 2D array
; Syntax ........: _ArrayAinATo2d(ByRef $A)
; Parameters ....: $A             - the arrays in array which should be converted
; Return values .: Success: a 2D Array build from the input array
;                  Failure: Null
;                     @error = 1: $A is'nt an 1D array
;                            = 2: $A is empty
;                            = 3: first element isn't a array
; Author ........: AspirinJunkie
; =================================================================================================
Func _ArrayAinATo2d(ByRef $A)
	If UBound($A, 0) <> 1 Then Return SetError(1, UBound($A, 0), Null)
	Local $N = UBound($A)
	If $N < 1 Then Return SetError(2, $N, Null)
	Local $u = UBound($A[0])
	If $u < 1 Then Return SetError(3, $u, Null)

	Local $a_Ret[$N][$u]

	For $i = 0 To $N - 1
		Local $t = $A[$i]
		If UBound($t) > $u Then ReDim $a_Ret[$N][UBound($t)]
		For $j = 0 To UBound($t) - 1
			$a_Ret[$i][$j] = $t[$j]
		Next
	Next
	Return SetExtended($N, $a_Ret)
EndFunc   ;==>_ArrayAinATo2d






#Region UDF Zeug von Mars
; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Erzeugt einen Lookup Table zum enkodieren/dekodieren aus einer Wahrscheinlichkeitsliste.
;                  Aufbau:
;                  $aP[0]  = Wahrscheinlichkeit, dass eine Zahl die Länge  1 Bit hat
;                  $aP[1]  =                                               2
;                  $aP[n]  =                                               n
;                  $aP[30] =                                              31
;                  Da der Maximalwert des Enkoders/Dekoders uint31-1 ist, ist $aP grundsätzlich 31 Einträge groß (Array[31])
; ===============================================================================================================================
Func _DecToBinPrefixTable($aP = 0)
	; $aP[31] <- mehr als 31Bit geht nicht. Enthält die Wahrscheinlichkeiten für jede Bitrate.
	If Not IsArray($aP) Then
		Local $_[31]
		For $i = 0 To UBound($_) - 1 Step 1
			$_[$i] = 1 / 1.05^$i ; Initiale Wahrscheinlichkeiten je Bitrate. Leicht exponentiell, fast gleichverteilt.
		Next
		$aP = $_
	EndIf
	; Normalisieren, falls es im Input vergessen wurde
	Local $s = 0
	For $i = 0 To UBound($aP) - 1 Step 1
		$s += $aP[$i]
	Next
	For $i = 0 To UBound($aP) - 1 Step 1
		$aP[$i] /= $s
	Next
	Local $HT[UBound($aP) * 2][3], $L1D[UBound($aP)], $L2D[UBound($aP)][2]
	__AHE_BuildTreeFromSymbolHistogram($aP, $HT) ; geklaut von Adaptive Huffman Encoder
	__AHE_TreeToLookupRec($L1D, $HT) ; geklaut von Adaptive Huffman Encoder
	For $i = 0 To UBound($L1D) - 1 Step 1
		$L2D[$i][0] = StringLen($L1D[$i]) ; Die Länge schonmal speichern
		$L2D[$i][1] = $L1D[$i]
	Next
	Return $L2D
EndFunc

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Adaptives enkodieren von Integern (bis uint31 - 1) via Prefix Tabelle.
;                  In $aLUT ist ein eindeutiger Lookup Table für die Prefixes. Diesen kann man z.B. via
;                  Huffman generieren.
; ===============================================================================================================================
Func _DecToBinA($d, $aLUT = 0)
	If Not IsArray($aLUT) Then $aLUT = $D2B_DPT
	Local $iBits = Ceiling(Log($d+1+($d=0?1:0))/Log(2))
	If $iBits = 1 Then
		Return $aLUT[$iBits - 1][1] & _DecToBin($d, $iBits)
	Else
		Return $aLUT[$iBits - 1][1] & StringTrimLeft(_DecToBin($d, $iBits), 1)
		; Wir wisseen: hier steht IMMER eine '1', also kann die 1 weg.
		; Begründung: Da wir die Zahlen je nach Bitrate kodieren würde die
		;             Bitrate um 1 sinken, wenn vorne eine '0' stehen würde,
		;             also ist hier immer eine '1'. Ausnahme ist der Fall
		;             für ein einziges Bit was '0' oder '1' sein kann und für
		;             die Zahlen 0 oder 1 steht.
	EndIf
EndFunc

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Adaptives dekodieren von Links. In @extended ist die Länge der dekodierten Zahl in Bin.
;                  In $aLUT ist ein eindeutiger Lookup Table für die Prefixes. Diesen kann man z.B. via
;                  Huffman generieren.
; ===============================================================================================================================
Func _BinToDecA($b, $aLUT = 0)
		If Not IsArray($aLUT) Then $aLUT = $D2B_DPT
	For $iBits = 1 To 30 Step 1 ; Könnte man über partial match tree lösen. Hab aber keine Lust. Daher linear durchprobieren.
		If StringLeft($b, $aLUT[$iBits - 1][0]) = $aLUT[$iBits - 1][1] Then
			If $iBits = 1 Then
				Return SetExtended($iBits + $aLUT[$iBits - 1][0], _BinToDec(StringMid($b, $aLUT[$iBits - 1][0] + 1, $iBits)))
			Else
				Return SetExtended($iBits + $aLUT[$iBits - 1][0] - 1, _BinToDec(('1' & StringMid($b, $aLUT[$iBits - 1][0] + 1, $iBits - 1))))
			EndIf
		EndIf
	Next
	Return SetError(1, 0, "ERROR: Verwendeter Prefix Lookuptable passt nicht zur eingegebenen Binärzahl.")
EndFunc

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: False: Verlängert eine Binärzahl zur Umrechnung ins B256 System | True: Entfernt die Verlängerung
; ===============================================================================================================================
Func _BinCap8($sBin, $bUnCap = False)
	Local Static $aLeft[8] = ['00000000', '0000001', '000001', '00001', '0001', '001', '01', '1']
	If Not $bUnCap Then Return SetExtended(StringLen($aLeft[Mod(StringLen($sBin), 8)]), $aLeft[Mod(StringLen($sBin), 8)] & $sBin)
	For $i = 0 To 7 Step 1
		If StringLeft($sBin, StringLen($aLeft[$i])) = $aLeft[$i] Then Return SetExtended(StringLen($aLeft[$i]), StringTrimLeft($sBin, StringLen($aLeft[$i])))
	Next
EndFunc   ;==>_BinCap8

; --------------------------------------------------------|
; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Wandelt eine Dualzahl(String) in eine Dezimalzahl um
; ===============================================================================================================================
Func _BinToDec($s)
	Local $l = StringLen($s)
	Return $l < 9 ? $D2BC[$s] : $l < 17 ? $D2BC[StringTrimRight($s, 8)] * 256 + $D2BC[StringRight($s, 8)] : $l < 25 ? _
	$D2BC[StringTrimRight($s, 16)] * 65536 + $D2BC[StringRight(StringTrimRight($s, 8), 8)] * 256 + $D2BC[StringRight( _
	$s, 8)] : BitShift($D2BC[StringTrimRight($s, 24)], -24) + $D2BC[StringRight(StringTrimRight($s, 16), 8)] * 65536 _
	+ $D2BC[StringRight(StringTrimRight($s, 8), 8)] * 256 + $D2BC[StringRight($s, 8)]
EndFunc   ;==>_BinToDec

; #FUNCTION# ====================================================================================================================
; Author ........: Mars
; Description ...: Ermittelt eine Dualzahl(String) aus einer Dezimalzahl die kleiner als 2^31 ist
; ===============================================================================================================================
Func _DecToBin($d, $l)
	Return StringRight('00000000000000000000000000000000' & ($d < 256 ? $D2BA[$d] : $d < 65536 ? $D2BA[$d / 256] & $D2BB[BitAND($d, 255)] _
	: $d < 16777216 ? $D2BA[$d / 65536] & $D2BB[BitAND($d / 256, 255)] & $D2BB[BitAND($d, 255)] : $D2BA[BitShift($d, 24)] & $D2BB[BitAND($d / _
	65536, 255)] & $D2BB[BitAND($d / 256, 255)] & $D2BB[BitAND($d, 255)]), $l)
EndFunc   ;==>_DecToBin

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Initialisiert die DecToBin UDF
; ===============================================================================================================================
Func __DecToBinStartup()
	Local Static $bReady = False
	If $bReady Then Return
	Local $t = DllStructCreate('char[64]'), $p = _
			DllStructGetPtr($t), $hDll = DllOpen('msvcrt.dll')
	For $i = 0 To 255 Step 1
		DllCall($hDll, 'ptr:cdecl', '_i64toa', 'int64', _
				$i, 'ptr', $p, 'int', 2)
		$D2BA[$i] = DllStructGetData($t, 1)
		$D2BB[$i] = StringRight('0000000' & $D2BA[$i], 8)
		$D2BC[$D2BA[$i]] = $i
	Next
	DllClose($hDll)
	$bReady = True
EndFunc   ;==>_DecToBinStartup

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Geklaut von mir selbst. (Adaptive Huffman Encoder)
; ===============================================================================================================================
Func __AHE_TreeSingleLookup(ByRef $__AHET, ByRef $sPath)
	Local $i = 0, $n = 1
	Do
		If StringMid($sPath, $n, 1) = '0' Then
			$i = $__AHET[$i][0]
		Else
			$i = $__AHET[$i][2]
		EndIf
		$n += 1
	Until $__AHET[$i][2] = ''
	$sPath = StringTrimLeft($sPath, $n - 1)
	Return $__AHET[$i][0]
EndFunc

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Geklaut von mir selbst. (Adaptive Huffman Encoder)
; ===============================================================================================================================
Func __AHE_SymbolHistogramToLookup(ByRef $aHist)
	Local $T[UBound($aHist) * 2][3], $LUT[UBound($aHist)]
	__AHE_BuildTreeFromSymbolHistogram($aHist, $T)
	__AHE_TreeToLookupRec($LUT, $T)
	Return $LUT
EndFunc

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Geklaut von mir selbst. (Adaptive Huffman Encoder)
; ===============================================================================================================================
Func __AHE_TreeToLookupRec(ByRef $aLookup, ByRef $__AHET, $i = 0, $sPath = '')
	If $__AHET[$i][2] = '' Then
		$aLookup[$__AHET[$i][0]] = $sPath
	Else
		__AHE_TreeToLookupRec($aLookup, $__AHET, $__AHET[$i][0], $sPath & '0')
		__AHE_TreeToLookupRec($aLookup, $__AHET, $__AHET[$i][2], $sPath & '1')
	EndIf
EndFunc   ;==>__AHE_TreeToLookupRec

; #INTERNAL# ====================================================================================================================
; Author ........: Mars
; Description ...: Geklaut von mir selbst. (Adaptive Huffman Encoder) Vermutlich die beste Funktion die ich je geschrieben habe.
; ===============================================================================================================================
Func __AHE_BuildTreeFromSymbolHistogram(ByRef $aSymHist, ByRef $__AHET)

	Local $iRi = UBound($__AHET) - 1, $t, $n, $n2
	For $i = 0 To UBound($aSymHist) - 1 Step 1 ; Beginn von 0 bis 255 mit Leafs füllen
		$__AHET[$i][0] = $i             ; If Leaf: Char, Else LeftIndex
		$__AHET[$i][1] = $aSymHist[$i]  ; Propability
		$__AHET[$i][2] = ''             ; If Leaf: '', Else RightIndex
	Next

	Local $__AHEE = UBound($aSymHist)  ;         | Func BuildMinHeap()
	For $i = Int($__AHEE / 2) To 0 Step -1 ; | (wendet eigentlich nur Heapify auf das halbe Array an)
		$n = $i                            ; | Func Heapify()
		While 1                            ; |
			$t = 2 * $n                    ; |
			$n2 = ($t < $__AHEE And $__AHET[$t][1] < $__AHET[$n][1]) ? $t : $n
			$t += 1                        ; |
			If $t < $__AHEE And $__AHET[$t][1] < $__AHET[$n2][1] Then $n2 = $t
			If $n2 = $n Then ExitLoop      ; |
			$t = $__AHET[$n][0]            ; |  [0] = wichtig, den kopieren wir :D
			$__AHET[$n][0] = $__AHET[$n2][0] ;| [1] = wichtig, kann man auch kopieren
			$__AHET[$n2][0] = $t           ; |  [2] = '' für alle Elemente, brauchen wir also hier nicht.
			$t = $__AHET[$n][1]            ; | Der Vorherige Arrayinhalt von [2] ist auch egal und muss nicht
			$__AHET[$n][1] = $__AHET[$n2][1] ;| überschrieben werden, da kann also sonstiger Unfug drinstehen.
			$__AHET[$n2][1] = $t           ; |
			$n = $n2                       ; |
		WEnd                               ; | EndFunc Heapify
	Next                                   ; | EndFunc BuildMinHeap

	For $i = 0 To UBound($aSymHist) - 2 Step 1
		$__AHET[$iRi][0] = $__AHET[0][0]   ; | Func HeapRemoveMin()
		$__AHET[$iRi][1] = $__AHET[0][1]   ; |
		$__AHET[$iRi][2] = $__AHET[0][2]   ; | kombiniert mit Min ans Ende schieben
		$__AHEE -= 1                       ; | und Heapbedingungerneuern.
		$__AHET[0][0] = $__AHET[$__AHEE][0] ; |
		$__AHET[0][1] = $__AHET[$__AHEE][1] ; |
		$__AHET[0][2] = $__AHET[$__AHEE][2] ; |
		$n = 0                             ; | Func Heapify()
		While 1
			$t = 2 * $n
			$n2 = ($t < $__AHEE And $__AHET[$t][1] < $__AHET[$n][1]) ? $t : $n
			$t += 1
			If $t < $__AHEE And $__AHET[$t][1] < $__AHET[$n2][1] Then $n2 = $t
			If $n2 = $n Then ExitLoop
			$t = $__AHET[$n][0]
			$__AHET[$n][0] = $__AHET[$n2][0]
			$__AHET[$n2][0] = $t
			$t = $__AHET[$n][1]
			$__AHET[$n][1] = $__AHET[$n2][1]
			$__AHET[$n2][1] = $t
			$t = $__AHET[$n][2]
			$__AHET[$n][2] = $__AHET[$n2][2]
			$__AHET[$n2][2] = $t
			$n = $n2                       ; | EndFunc Heapify
		WEnd ; ----------------------------- | EndFunc HeapRemoveMin

		$__AHET[$iRi - 1][0] = $__AHET[0][0] ; | Func HeapRemoveMin()
		$__AHET[$iRi - 1][1] = $__AHET[0][1] ; | Nochmal. wir wollen ja die 2 kleinsten Elemente.
		$__AHET[$iRi - 1][2] = $__AHET[0][2]
		$__AHEE -= 1
		$__AHET[0][0] = $__AHET[$__AHEE][0]
		$__AHET[0][1] = $__AHET[$__AHEE][1]
		$__AHET[0][2] = $__AHET[$__AHEE][2]
		$n = 0                             ; | Func Heapify()
		While 1
			$t = 2 * $n
			$n2 = ($t < $__AHEE And $__AHET[$t][1] < $__AHET[$n][1]) ? $t : $n
			$t += 1
			If $t < $__AHEE And $__AHET[$t][1] < $__AHET[$n2][1] Then $n2 = $t
			If $n2 = $n Then ExitLoop
			$t = $__AHET[$n][0]
			$__AHET[$n][0] = $__AHET[$n2][0]
			$__AHET[$n2][0] = $t
			$t = $__AHET[$n][1]
			$__AHET[$n][1] = $__AHET[$n2][1]
			$__AHET[$n2][1] = $t
			$t = $__AHET[$n][2]
			$__AHET[$n][2] = $__AHET[$n2][2]
			$__AHET[$n2][2] = $t
			$n = $n2                       ; | EndFunc Heapify
		WEnd ; ----------------------------- | EndFunc HeapRemoveMin

		$__AHET[$__AHEE][0] = $iRi         ; | Func HeapInsert(NewNode)
		$__AHET[$__AHEE][1] = 1 / 0        ; | Aus den vorher gefundenen 2 kleinsten Elementen entsteht
		$__AHET[$__AHEE][2] = $iRi - 1     ; | eine neue Node die man per Insert in den Heap stopft.
		$n = $__AHEE                       ; | Func HeapDecrease()
		If $__AHET[$n][1] >= $__AHET[$iRi][1] + $__AHET[$iRi - 1][1] Then
			$__AHET[$n][1] = $__AHET[$iRi][1] + $__AHET[$iRi - 1][1]
			While $n > 0 And $__AHET[$n][1] < $__AHET[Int($n / 2)][1]
				$n2 = Int($n / 2)
				$t = $__AHET[$n][0]
				$__AHET[$n][0] = $__AHET[$n2][0]
				$__AHET[$n2][0] = $t
				$t = $__AHET[$n][1]
				$__AHET[$n][1] = $__AHET[$n2][1]
				$__AHET[$n2][1] = $t
				$t = $__AHET[$n][2]
				$__AHET[$n][2] = $__AHET[$n2][2]
				$__AHET[$n2][2] = $t
				$n = $n2
			WEnd
		EndIf                              ; | EndFunc HeapDecrease
		$__AHEE += 1                       ; | EndFunc HeapInsert
		$iRi -= 2 ; Reverse Index - 2
	Next
EndFunc   ;==>__AHE_BuildTreeFromSymbolHistogram
#EndRegion