1 /* Copyright 2015 the unarr project authors (see AUTHORS file).
2 License: LGPLv3 */
3
4 /* adapted from https://code.google.com/p/theunarchiver/source/browse/XADMaster/XADPrefixCode.m */
5
6 #include "rar.h"
7
rar_new_node(struct huffman_code * code)8 bool rar_new_node(struct huffman_code *code)
9 {
10 if (!code->tree) {
11 code->minlength = INT_MAX;
12 code->maxlength = INT_MIN;
13 }
14 if (code->numentries + 1 >= code->capacity) {
15 /* in my small file sample, 1024 is the value needed most often */
16 int new_capacity = code->capacity ? code->capacity * 2 : 1024;
17 void *new_tree = calloc(new_capacity, sizeof(*code->tree));
18 if (!new_tree) {
19 warn("OOM during decompression");
20 return false;
21 }
22 memcpy(new_tree, code->tree, code->capacity * sizeof(*code->tree));
23 free(code->tree);
24 code->tree = new_tree;
25 code->capacity = new_capacity;
26 }
27 code->tree[code->numentries].branches[0] = -1;
28 code->tree[code->numentries].branches[1] = -2;
29 code->numentries++;
30 return true;
31 }
32
rar_add_value(struct huffman_code * code,int value,int codebits,int length)33 bool rar_add_value(struct huffman_code *code, int value, int codebits, int length)
34 {
35 int lastnode, bitpos, bit;
36
37 free(code->table);
38 code->table = NULL;
39
40 if (length > code->maxlength)
41 code->maxlength = length;
42 if (length < code->minlength)
43 code->minlength = length;
44
45 lastnode = 0;
46 for (bitpos = length - 1; bitpos >= 0; bitpos--) {
47 bit = (codebits >> bitpos) & 1;
48 if (rar_is_leaf_node(code, lastnode)) {
49 warn("Invalid data in bitstream"); /* prefix found */
50 return false;
51 }
52 if (code->tree[lastnode].branches[bit] < 0) {
53 if (!rar_new_node(code))
54 return false;
55 code->tree[lastnode].branches[bit] = code->numentries - 1;
56 }
57 lastnode = code->tree[lastnode].branches[bit];
58 }
59
60 if (code->tree[lastnode].branches[0] != -1 || code->tree[lastnode].branches[1] != -2) {
61 warn("Invalid data in bitstream"); /* prefix found */
62 return false;
63 }
64 code->tree[lastnode].branches[0] = code->tree[lastnode].branches[1] = value;
65 return true;
66 }
67
rar_create_code(struct huffman_code * code,uint8_t * lengths,int numsymbols)68 bool rar_create_code(struct huffman_code *code, uint8_t *lengths, int numsymbols)
69 {
70 int symbolsleft = numsymbols;
71 int codebits = 0;
72 int i, j;
73
74 if (!rar_new_node(code))
75 return false;
76
77 for (i = 1; i <= 0x0F; i++) {
78 for (j = 0; j < numsymbols; j++) {
79 if (lengths[j] != i)
80 continue;
81 if (!rar_add_value(code, j, codebits, i))
82 return false;
83 if (--symbolsleft <= 0)
84 return true;
85 codebits++;
86 }
87 codebits <<= 1;
88 }
89 return true;
90 }
91
rar_make_table_rec(struct huffman_code * code,int node,int offset,int depth,int maxdepth)92 static bool rar_make_table_rec(struct huffman_code *code, int node, int offset, int depth, int maxdepth)
93 {
94 int currtablesize = 1 << (maxdepth - depth);
95
96 if (node < 0 || code->numentries <= node) {
97 warn("Invalid data in bitstream"); /* invalid location to Huffman tree specified */
98 return false;
99 }
100
101 if (rar_is_leaf_node(code, node)) {
102 int i;
103 for (i = 0; i < currtablesize; i++) {
104 code->table[offset + i].length = depth;
105 code->table[offset + i].value = code->tree[node].branches[0];
106 }
107 }
108 else if (depth == maxdepth) {
109 code->table[offset].length = maxdepth + 1;
110 code->table[offset].value = node;
111 }
112 else {
113 if (!rar_make_table_rec(code, code->tree[node].branches[0], offset, depth + 1, maxdepth))
114 return false;
115 if (!rar_make_table_rec(code, code->tree[node].branches[1], offset + currtablesize / 2, depth + 1, maxdepth))
116 return false;
117 }
118 return true;
119 }
120
rar_make_table(struct huffman_code * code)121 bool rar_make_table(struct huffman_code *code)
122 {
123 if (code->minlength <= code->maxlength && code->maxlength <= 10)
124 code->tablesize = code->maxlength;
125 else
126 code->tablesize = 10;
127
128 code->table = calloc(1ULL << code->tablesize, sizeof(*code->table));
129 if (!code->table) {
130 warn("OOM during decompression");
131 return false;
132 }
133
134 return rar_make_table_rec(code, 0, 0, 0, code->tablesize);
135 }
136
rar_free_code(struct huffman_code * code)137 void rar_free_code(struct huffman_code *code)
138 {
139 free(code->tree);
140 free(code->table);
141 memset(code, 0, sizeof(*code));
142 }
143