File size: 10,119 Bytes
53a6e90
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
"""HN5 store: IQLP primitives on the keep-graph, not a codec switch."""
from __future__ import annotations
import bz2, lzma, re, struct, zlib
from collections import defaultdict
MAGIC = b"HN51"
GID_RAW, GID_POOL, GID_SKEL0 = 0, 1, 2
_DIGIT = re.compile(br"\d+")
XML_DICT = (
    b'xmlns:android="http://schemas.android.com/apk/res/android"',
    b'android:layout_width="match_parent"',
    b'android:layout_height="match_parent"',
    b'android:text="@string/app_name"',
    b'android:textSize="',
    b'@drawable/ic_launcher_',
    b'@+id/activity_',
    b"<LinearLayout ", b"</LinearLayout>", b"<TextView ", b"<ImageView ",
    b'android:src="', b'android:id="',
)

def dict_pack(blob: bytes) -> bytes:
    out, i, n = bytearray(), 0, len(blob)
    while i < n:
        hit = None
        for di, d in enumerate(XML_DICT):
            if blob.startswith(d, i) and (hit is None or len(d) > len(hit[1])):
                hit = (di, d)
        if hit is not None:
            out.append(1); out.append(hit[0]); i += len(hit[1])
        else:
            if blob[i] == 1: raise ValueError("reserved marker")
            out.append(blob[i]); i += 1
    return bytes(out)

def dict_unpack(blob: bytes) -> bytes:
    out, i, n = bytearray(), 0, len(blob)
    while i < n:
        if blob[i] == 1:
            out.extend(XML_DICT[blob[i+1]]); i += 2
        else:
            out.append(blob[i]); i += 1
    return bytes(out)

def identity_baselines(concat: bytes):
    return {"zlib9": len(zlib.compress(concat, 9)), "lzma6": len(lzma.compress(concat, preset=6)),
            "lzma9": len(lzma.compress(concat, preset=9)), "bz2": len(bz2.compress(concat, 9))}

def ship_tier(*, size, r8_opt, identity_lzma, roundtrip, live_ok):
    if not roundtrip or not live_ok: return 0
    if size >= r8_opt or size >= identity_lzma: return 1
    rel = (identity_lzma - size) / float(identity_lzma)
    return 5 if rel >= 0.40 else 4 if rel >= 0.25 else 3 if rel >= 0.15 else 2 if rel >= 0.05 else 1

def skeleton_and_nums(blob: bytes):
    nums = [int(x) for x in _DIGIT.findall(blob)]
    return _DIGIT.sub(b"\x00", blob), nums

def fill_skeleton(skel: bytes, nums):
    out, it = bytearray(), iter(nums)
    for byte in skel:
        if byte == 0: out.extend(str(next(it)).encode("ascii"))
        else: out.append(byte)
    return bytes(out)

def freeze_constant_slots(skel: bytes, rows):
    if not rows: return skel, rows
    width = len(rows[0])
    variable = [c for c in range(width) if any(row[c] != rows[0][c] for row in rows)]
    constants = {c: rows[0][c] for c in range(width) if c not in set(variable)}
    out, hole = bytearray(), 0
    for byte in skel:
        if byte == 0:
            if hole in constants: out.extend(str(constants[hole]).encode("ascii"))
            else: out.append(0)
            hole += 1
        else: out.append(byte)
    return bytes(out), [[row[c] for c in variable] for row in rows]

def try_c_string_pool(blob: bytes):
    if blob.count(b"\0") < 8: return None
    best, n, i = None, len(blob), 0
    while i < n:
        prev = blob[i-1] if i else 0
        if i and 32 <= prev <= 126:
            i += 1; continue
        toks, j = [], i
        while j < n:
            k = blob.find(b"\0", j)
            if k < 0: break
            tok = blob[j:k]
            if not (1 <= len(tok) <= 80) or any(b < 32 or b > 126 for b in tok): break
            toks.append(tok); j = k+1
        if len(toks) >= 8:
            uniq = len(set(toks))
            if uniq / len(toks) <= 0.5:
                lengths = [len(t) for t in toks]
                mean = sum(lengths)/len(lengths)
                var = sum((x-mean)**2 for x in lengths)/len(lengths)
                dups = len(toks)-uniq
                key = (dups, -int(var), j-i)
                if best is None or key > best[0]:
                    best = (key, i, j, toks)
                    if dups >= 200: break
        i += 1
    if best is None: return None
    _, start, end, toks = best
    return blob[:start], toks, blob[end:]

def _u32(n): return struct.pack("<I", n)
def _u16(n):
    if n > 0xFFFF: raise ValueError("u16 overflow")
    return struct.pack("<H", n)

def encode_body(blobs):
    n = len(blobs)
    gids = [GID_RAW]*n
    pools, skels, nums_of = {}, defaultdict(list), {}
    for i, blob in enumerate(blobs):
        pool = try_c_string_pool(blob)
        if pool is not None:
            gids[i] = GID_POOL; pools[i] = pool; continue
        if b"\x00" in blob: continue
        skel, nums = skeleton_and_nums(blob)
        if not nums: continue
        skels[skel].append(i); nums_of[i] = nums
    groups = []
    for skel, idxs in skels.items():
        width = len(nums_of[idxs[0]])
        if len(idxs) < 2 or any(len(nums_of[i]) != width for i in idxs): continue
        frozen, rows = freeze_constant_slots(skel, [nums_of[i] for i in idxs])
        frozen = dict_pack(frozen)
        gid = GID_SKEL0 + len(groups)
        if gid > 255: continue
        for i, row in zip(idxs, rows):
            gids[i] = gid; nums_of[i] = row
        groups.append((frozen, idxs))
    out = bytearray(MAGIC); out.extend(_u32(n))
    runs = []
    for gid in gids:
        if runs and runs[-1][0] == gid: runs[-1] = (gid, runs[-1][1]+1)
        else: runs.append((gid, 1))
    out.extend(_u16(len(runs)))
    for gid, cnt in runs:
        out.append(gid); out.extend(_u16(cnt))
    out.extend(_u32(len(groups)))
    for skel, idxs in groups:
        idxs_s = sorted(idxs)
        width = len(nums_of[idxs_s[0]]) if idxs_s else 0
        max_num = max((max(nums_of[i], default=0) for i in idxs_s), default=0)
        width_b = 0 if max_num < 16 else 1 if max_num < 256 else 2
        out.extend(_u32(len(skel))); out.extend(_u16(len(idxs_s))); out.extend(struct.pack("BB", width, width_b)); out.extend(skel)
        flat = [v for i in idxs_s for v in nums_of[i]]
        if width_b == 0:
            if len(flat)%2: flat.append(0)
            for a,b in zip(flat[0::2], flat[1::2]): out.append((a&15)|((b&15)<<4))
        elif width_b == 1: out.extend(bytes(flat))
        else:
            for v in flat: out.extend(_u16(v))
    pool_idxs = [i for i,g in enumerate(gids) if g==GID_POOL]
    out.extend(_u32(len(pool_idxs)))
    for i in pool_idxs:
        prefix, toks, suffix = pools[i]
        uniq = list(dict.fromkeys(toks)); id_of = {t:j for j,t in enumerate(uniq)}
        ids = [id_of[t] for t in toks]; id_b = 1 if len(uniq)<256 else 2
        joined = b"\0".join(uniq) + (b"\0" if uniq else b"")
        out.extend(_u16(len(prefix))); out.extend(_u16(len(suffix))); out.extend(_u16(len(toks))); out.extend(_u16(len(uniq))); out.append(id_b)
        out.extend(prefix); out.extend(suffix); out.extend(_u32(len(joined))); out.extend(joined)
        for v in ids:
            if id_b==1: out.append(v)
            else: out.extend(_u16(v))
    raw_idxs = [i for i,g in enumerate(gids) if g==GID_RAW]
    out.extend(_u32(len(raw_idxs)))
    for i in raw_idxs:
        b = blobs[i]; out.extend(_u32(len(b))); out.extend(b)
    return bytes(out)

def decode_body(body: bytes):
    if body[:4] != MAGIC: raise ValueError("bad magic")
    n = struct.unpack_from("<I", body, 4)[0]
    n_runs = struct.unpack_from("<H", body, 8)[0]; off = 10; gids = []
    for _ in range(n_runs):
        gid = body[off]; cnt = struct.unpack_from("<H", body, off+1)[0]; off += 3; gids.extend([gid]*cnt)
    if len(gids) != n: raise ValueError("gid run mismatch")
    blobs = [None]*n
    def take(k):
        nonlocal off; s = body[off:off+k]; off += k; return s
    def u32():
        nonlocal off; v = struct.unpack_from("<I", body, off)[0]; off += 4; return v
    def u16():
        nonlocal off; v = struct.unpack_from("<H", body, off)[0]; off += 2; return v
    n_groups = u32()
    for gi in range(n_groups):
        skel_len = u32(); count = u16(); width, width_b = body[off], body[off+1]; off += 2
        skel = take(skel_len); gid = GID_SKEL0 + gi
        idxs = [i for i,g in enumerate(gids) if g==gid]
        if len(idxs) != count: raise ValueError("skel count mismatch")
        nvals = count * width; flat = []
        if width_b == 0:
            packed = take((nvals+1)//2)
            for b in packed: flat.append(b&15); flat.append((b>>4)&15)
            flat = flat[:nvals]
        elif width_b == 1: flat = list(take(nvals))
        else:
            for _v in range(nvals): flat.append(u16())
        for row_i, i in enumerate(idxs):
            blobs[i] = fill_skeleton(dict_unpack(skel), flat[row_i*width:(row_i+1)*width])
    n_pool = u32(); pool_idxs = [i for i,g in enumerate(gids) if g==GID_POOL]
    if n_pool != len(pool_idxs): raise ValueError("pool count mismatch")
    for i in pool_idxs:
        plen, slen, n_tok, n_uniq = u16(), u16(), u16(), u16(); id_b = body[off]; off += 1
        prefix, suffix = take(plen), take(slen); joined = take(u32())
        uniq = joined.split(b"\0")
        if uniq and uniq[-1]==b"": uniq = uniq[:-1]
        toks = []
        for _t in range(n_tok):
            toks.append(uniq[body[off]] if id_b==1 else uniq[u16()])
            if id_b==1: off += 1
        blobs[i] = prefix + b"\0".join(toks) + b"\0" + suffix
    n_raw = u32(); raw_idxs = [i for i,g in enumerate(gids) if g==GID_RAW]
    if n_raw != len(raw_idxs): raise ValueError("raw count mismatch")
    for i in raw_idxs: blobs[i] = take(u32())
    if any(b is None for b in blobs): raise ValueError("incomplete decode")
    return [b for b in blobs if b is not None]

def encode_store(blobs):
    body = encode_body(blobs)
    cands = [("hn5-zlib", bytes([1])+zlib.compress(body,9)), ("hn5-lzma", bytes([2])+lzma.compress(body, preset=6)), ("hn5-bz2", bytes([3])+bz2.compress(body,9))]
    name, store = min(cands, key=lambda kv: len(kv[1]))
    return len(store), name, store

def decode_store(store):
    if not store: raise ValueError("empty store")
    tag, blob = store[0], store[1:]
    if tag==1: body = zlib.decompress(blob)
    elif tag==2: body = lzma.decompress(blob)
    elif tag==3: body = bz2.decompress(blob)
    else: raise ValueError(f"unknown store tag {tag}")
    return decode_body(body)