igorholt's picture
HN5 IQLP store codec
53a6e90 verified
Raw History Blame Contribute Delete
10.1 kB
"""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)