/*
* Copyright (C) 2022.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 3 as
* published by the Free Software Foundation.
*
* 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
* General Public License for more details.
*/
package test.display;
import java.nio.ByteBuffer;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import test.util.BitReaderLR;
public class HuffmanDecoder
{
private HuffmanNode root
;
/** binary search table is used to calculate offset into symbol array */
List<TreeLevelData
> searchTab =
new ArrayList<>();
/** lookup table that is used when lookup bits > 0 */
private byte[] lookupTable
;
/** for decoding strings */
private ByteBuffer decodeBuf =
ByteBuffer.
allocate(1000);
private boolean huffmanDecodingFailed
;
private int lookupBits
;
/** the symbol array */
private byte[] symbols
;
private int[] symbols32
;
private int[] frequencies =
new int[256];
private int symWidth
;
/**
* Reconstruct Huffman tree, not done by Garmin software.
*/
public void buildHuffmanTree
() {
root =
null;
final int lastLevel = searchTab.
get(0).
depth;
List<LinkedList<Integer>> symbolsBylevel =
new ArrayList<>();
for (int i =
0; i
<= lastLevel
; i++
) {
symbolsBylevel.
add(new LinkedList<>());
}
for (int i =
0; i
< lookupTable.
length/
2; i++
) {
int stat = lookupTable
[i
*2];
if (stat
% 2 ==
1) {
int lvl = stat /
2;
int val = lookupTable
[i
*2+
1];
LinkedList<Integer> lst = symbolsBylevel.
get(lvl
);
if (lst.
isEmpty() || lst.
getLast() != val
)
lst.
add(val
);
}
}
long lastOff = symbols.
length;
for (int i = searchTab.
size() -
1; i
>=
0; i--
) {
TreeLevelData info = searchTab.
get(i
);
int len =
(int) (lastOff - info.
offset);
lastOff = info.
offset;
if (len
< 0) {
setHuffmanDecodingFailed
(true);
break;
}
LinkedList<Integer> lst = symbolsBylevel.
get(info.
depth);
for (int k =
0; k
< len
; k++
) {
if(symWidth ==
8)
lst.
add(symbols
[info.
offset + k
] & 0xff
);
else
lst.
add(symbols32
[info.
offset + k
]);
}
}
int code = -
1;
boolean firstCode =
true;
for (int i =
0; i
< symbolsBylevel.
size(); i++
) {
LinkedList<Integer> vals = symbolsBylevel.
get(i
);
if (firstCode
)
code =
1 << i
;
else
code
<<=
1;
if (!vals.
isEmpty()) {
firstCode =
false;
while (!vals.
isEmpty()) {
code--
;
String x =
Integer.
toBinaryString(code
);
if (x.
length() < i
) {
// add leading zeros to code
x =
"0000000000000000000000000000000000000".
substring(0, i - x.
length()) + x
;
}
addHuffmanNode
(x, vals.
removeLast());
}
}
}
}
private void addHuffmanNode
(String bits,
int v
) {
if (root ==
null) {
root =
new HuffmanNode
(null,
null,
null);
}
HuffmanNode next = root
;
while (!bits.
isEmpty()) {
if ((next.
left !=
null || next.
right !=
null) && next.
val !=
null) {
throw new IllegalArgumentException("bad tree:" + v
);
}
char bit = bits.
charAt(0);
bits = bits.
substring(1);
if (bit ==
'0') {
if (next.
left ==
null)
next.
left =
new HuffmanNode
(null,
null,
null);
else {
if (next.
val !=
null)
throw new IllegalArgumentException("bad tree:" + v
);
}
next = next.
left;
} else {
if (next.
right ==
null)
next.
right =
new HuffmanNode
(null,
null,
null);
else {
if (next.
val !=
null)
throw new IllegalArgumentException("bad tree:" + v
);
}
next = next.
right;
}
}
if (next.
val !=
null || next.
left !=
null || next.
right !=
null)
throw new IllegalArgumentException("bad tree:" + v
);
next.
val = v
;
}
static class HuffmanNode
{
Integer val
;
HuffmanNode left =
null, right =
null;
HuffmanNode
(Integer val
) {
this.
val = val
;
}
public HuffmanNode
(Integer val, HuffmanNode left, HuffmanNode right
) {
this.
val = val
;
this.
left = left
;
this.
right = right
;
}
}
static class TreeLevelData
{
final int minCode
;
final int depth
;
final int offset
;
public TreeLevelData
(int minCode,
int depth,
int offset
) {
super();
this.
minCode = minCode
;
this.
depth = depth
;
this.
offset = offset
;
}
@
Override
public String toString
() {
return "TreeLevelData [minCode=" + minCode +
", depth=" + depth +
", offset=" + offset +
"]";
}
}
/**
* Decode Huffman encoded string using lookup tables.
* Something like this is probably implemented in MapSource/Basecamp.
* @return decoded String
*/
public String decodeWithTable
(BitReaderLR br,
Charset charset
) {
int n = decodeWithTable
(br
);
return new String(decodeBuf.
array(),
0, n -
1, charset
);
}
private int decodeSymbolWithTable
(BitReaderLR br
) {
final long startPos = br.
getBitPosition();
final int symBytes = symWidth
>> 3;
final int searchTabWidth =
1 + symBytes
;
// fill buffer from huffman bitstream
final int maxCodeLen = searchTab.
get(0).
depth;
int buf = br.
get(lookupBits
);
// bounds for binary search
int minIdx
;
int maxIdx
;
if (lookupBits
> 0) {
// interpret top huffmanLookupBits bits as int
int off = buf
;
off
*= searchTabWidth
;
int stat = lookupTable
[off
];
int v
;
if (symWidth ==
8)
v = lookupTable
[off +
1];
else {
assert symWidth ==
32;
v = lookupTable
[off +
1] & 0xff | lookupTable
[off +
2] << 8 | lookupTable
[off +
3] << 16
| lookupTable
[off +
4] << 24;
}
if (stat
% 2 ==
1) {
// best case: lookup table contains value
int usedBits = stat /
2;
br.
setBitPosition(startPos + usedBits
);
return v
;
}
// lookup values give start values for binary search, if equal no search is needed
minIdx = stat /
2;
maxIdx = v
;
} else {
minIdx =
0;
maxIdx = searchTab.
size() -
1;
}
buf
<<= maxCodeLen - lookupBits
;
buf |= br.
get(maxCodeLen - lookupBits
);
int code = buf
;
// binary search to find entry in first table which has offset for this code
int idx = minIdx
;
while (minIdx
< maxIdx
) {
int prev = idx
;
idx =
(minIdx + maxIdx +
1) /
2;
int minCode = searchTab.
get(idx
).
minCode;
if (code
< minCode
) {
maxIdx = idx -
1;
idx = prev
;
} else if (code
> minCode
)
minIdx = idx
;
else {
minIdx = idx
;
maxIdx = idx
;
}
}
TreeLevelData tabEntry = searchTab.
get(idx
);
int symIdx =
((code - tabEntry.
minCode) >> (maxCodeLen - tabEntry.
depth)) + tabEntry.
offset;
if (symIdx
< 0 || symIdx
* symBytes
>= symbols.
length) {
// print handle ArrayIndexOutOfBounds exception that will happen
IllegalStateException e =
new IllegalStateException(
String.
format("Failed to decode data starting at bit position %d", startPos
));
e.
printStackTrace();
throw e
;
}
br.
setBitPosition(startPos + tabEntry.
depth);
if (symWidth ==
8)
return symbols
[symIdx
] & 0xff
;
int off = symIdx
* symBytes
;
return symbols
[off
] & 0xff | symbols
[off +
1] << 8 | symbols
[off +
2] << 16
| symbols
[off +
3] << 24;
}
/**
* Decode Huffman encoded string using lookup tables.
* Something like this is probably implemented in MapSource/Basecamp.
* @return number of decoded bytes in buffer
*/
private int decodeWithTable
(BitReaderLR br
) {
decodeBuf.
clear();
while (true) {
int v = decodeSymbolWithTable
(br
);
if (symWidth ==
8)
decodeBuf.
put((byte) v
);
else
decodeBuf.
putInt(v
);
if (v ==
0)
break;
}
return decodeBuf.
position();
}
/** used to verify the results of decodeWithTable, not done by Garmin software */
public int decodeWithTree
(BitReaderLR br
) {
if (root ==
null) {
buildHuffmanTree
();
}
StringBuilder code =
new StringBuilder(); // for debugging
HuffmanNode next = root
;
while (true) {
if (!br.
hasRemaining()) {
return decodeBuf.
position();
}
if (next ==
null) {
// invalid code found
decodeBuf.
put((byte) '?');
return decodeBuf.
position();
}
if (next.
val !=
null) {
if (next.
val ==
0)
return decodeBuf.
position();
int v = next.
val;
decodeBuf.
put((byte) v
);
next = root
;
code.
setLength(0);
}
int bit = br.
get1();
code.
append(bit ==
1 ? '1' :
'0');
if (next.
val ==
null) {
next = bit ==
0 ? next.
left : next.
right;
}
}
}
private String decodeWithTree
(BitReaderLR br,
Charset charset
) {
int n = decodeWithTree
(br
);
return new String(decodeBuf.
array(),
0, n -
1, charset
);
}
public String decode
(BitReaderLR br,
boolean doubleCheck,
Charset charset
) {
if (isHuffmanDecodingFailed
())
return "";
long pos = br.
getBitPosition();
String s = decodeWithTable
(br, charset
);
if (doubleCheck
) {
long pos1 = br.
getBitPosition();
br.
setBitPosition(pos
);
String sTree = decodeWithTree
(br, charset
);
if (!sTree.
equals(s
)) {
setHuffmanDecodingFailed
(true);
// log error "string decoding failed, strings are different"
}
if (pos1
!= br.
getBitPosition()) {
// log error "string decoding failed, reader positions different"
setHuffmanDecodingFailed
(true);
br.
setBitPosition(pos1
);
}
}
return s
;
}
public void addSearchTab
(int minCodeShifted,
int depth,
int offset
) {
searchTab.
add(new TreeLevelData
(minCodeShifted, depth, offset
));
}
public void initFreq
() {
Arrays.
fill(frequencies,
0);
}
public int[] getFreq
() {
return frequencies
;
}
/**
* @return the lookupBits
*/
public int getLookupBits
() {
return lookupBits
;
}
/**
* @param lookupBits the lookupBits to set
*/
public void setLookupBits
(int lookupBits
) {
this.
lookupBits = lookupBits
;
}
/**
* @param lookupTable the lookupTable to set
*/
public void setLookupTable
(byte[] lookupTable
) {
this.
lookupTable = lookupTable
;
}
/**
* @param symbols the 8-bit symbols to set
*/
public void setSymbols
(byte[] symbols
) {
this.
symbols = symbols
;
}
/**
* @return the huffmanDecodingFailed
*/
public boolean isHuffmanDecodingFailed
() {
return huffmanDecodingFailed
;
}
/**
* @param huffmanDecodingFailed the huffmanDecodingFailed to set
*/
public void setHuffmanDecodingFailed
(boolean huffmanDecodingFailed
) {
this.
huffmanDecodingFailed = huffmanDecodingFailed
;
}
public void setSymWidth
(int symWidth
) {
this.
symWidth = symWidth
;
}
public int getSymWidth
() {
return symWidth
;
}
int readSymbol
(BitReaderLR br
) {
return decodeSymbolWithTable
(br
);
}
}