Optimizing storage of cmap_UniCNS_X_ranges (MuPDF/SumatraPDF)

tmp-cmap-analysis.md

Optimizing storage of cmap_UniCNS_X_ranges

Analysis of mupdf/source/pdf/cmaps/UniCNS-X.h and how to shrink it while keeping the same operations.

Current shape

pdf_range is three unsigned shorts (low, high, out) — 6 bytes per entry. This table has 16,377 ranges → ~98 KB of .rodata (the .h is ~406 KB of C text only because of hex literals).

Lookup does a binary search on sorted intervals and maps:

result = out + (cpt - low)

(pdf_lookup_cmap / pdf_lookup_cmap_full in pdf-cmap.c.)

Data properties (UniCNS-X)

Property	Value
Singletons (low == high)	15,402 (94%)
True multi-code ranges	975 (6%)
Max span high-low+1	95 (fits in a uint8_t)
Already maximally merged	yes (no adjacent linear runs to fuse)
out range	1 … 0x499c (15 bits)
Codepoints	all BMP (≤ 0xFFE4)
Successive low deltas	~98% are 1–15

So almost everything is a sparse singleton map with a small side table of short runs.

Goal

Keep the same operations:

1. Point query: codepoint → CID (or −1)
2. Optional: full mapping (same for this cmap; no many-to-one)
3. Same asymptotic cost: O(log n) binary search is fine

No need to preserve the exact pdf_range[] layout if you adapt the lookup (or expand once at first use).

Options (best ROI first)

1. Split singletons vs ranges — ~31% smaller, same speed

Storage

// 975 × 6 B
static const pdf_range cmap_UniCNS_X_runs[] = { ... };

// 15402 × 4 B  (exact key → out)
static const uint16_t cmap_UniCNS_X_keys[] = { ... };
static const uint16_t cmap_UniCNS_X_vals[] = { ... };

Total ≈ 67.5 KB (vs 98.3 KB).

Lookup

1. binary search runs[] by [low, high]   // ~10 comparisons
2. if miss: binary search keys[] for exact cpt
3. if hit: return vals[i]

Same complexity as today (still ~14 comparisons on the big table). No decompression, random-access friendly, works in place as const data.

This is the best practical first step for UniCNS-X / UniGB-X / similar tables.

2. Fixed 5-byte records — ~17%, one table

Every span fits in a byte:

struct { uint16_t low; uint8_t span_m1; uint16_t out; } // packed, 5 B
// high = low + span_m1

≈ 82 KB. Needs packed (or three parallel arrays: u16[], u8[], u16[]) so the compiler doesn’t pad back to 6.

Parallel SoA (lows[], spans[], outs[]) is often cleaner than packed structs and still 5 bytes/entry.

Weaker than (1), but a smaller code change if you keep a single binary-search loop.

3. Unicode page table — ~33%

BMP → 256 pages of 256 codepoints. Only ~150 pages are used.

page_dir[page] → list of {lo8, hi8, out}   // 4 B each

≈ 66–67 KB. Lookup: index page, then binary/linear search a short list (often tens of entries). Can be slightly faster than one big binary search (better locality).

Slightly more code; page-crossing ranges must be split (there are only 5 in this file).

4. Compress for the binary, expand once — ~47% on disk / image

Keep a compact blob; materialize pdf_range[] (or the split tables) on first pdf_load_builtin_cmap("UniCNS-X").

Good encoding for this data:

for each range in order:
  uleb(low - prev_low)     // deltas tiny: ~1 byte
  uleb(high - low)         // 0 for 94% of rows
  u16 out                  // or zigzag-sleb delta(out)

Rough size:

Encoding	Size
delta-low + span + u16 out	~65 KB
same, only on singletons + raw runs	~52 KB
zlib of raw 6-byte records	~91 KB (poor — already structured)
zlib of delta-SoA	~67 KB

~52 KB compressed + temporary ~98 KB RAM if you expand to full pdf_range[].
Or expand to the split layout (~67 KB RAM) and never keep the 6-byte form.

Tradeoff: first-use CPU, extra loader code, no pure .rodata binary search unless you keep an index.

5. Don’t bother with pure zlib of the current layout

Deflating the existing 6-byte records only gets to ~91 KB — the table is already dense and irregular in out. Structure-aware packing beats generic compression here.

What I would actually do

Recommended path for Sumatra/MuPDF-style code:

1. Primary: scheme (1) singleton keys/vals + small pdf_range run table

   • ~31% .rodata savings on this file alone
   • same operations, same big-O
   • no runtime decode
   • generalizes to UniGB-X, UniJIS-X, UniKS-X, and the large Adobe-*-UCS2 tables if they have the same singleton-heavy shape

2. Optional polish: store the generated tables as a binary .inc / unsigned char[] blob (or uint16_t arrays without {0x..,0x..,0x..} text) so the source/compile cost drops even when the runtime layout stays simple.

3. Only if binary size is critical: scheme (4) with ULEB deltas, expand at load into (1)’s layout.

4. Skip trying to merge more ranges — analysis shows the table is already maximal for linear runs.

Sketch of lookup for scheme (1)

// runs: multi-code intervals, sorted by low
// keys/vals: singletons, sorted by key

int lookup(unsigned cpt) {
    // 1) ranges (few hundred)
    int lo = 0, hi = run_len - 1;
    while (lo <= hi) {
        int m = (lo + hi) >> 1;
        if (cpt < runs[m].low) hi = m - 1;
        else if (cpt > runs[m].high) lo = m + 1;
        else return runs[m].out + (cpt - runs[m].low);
    }
    // 2) exact singleton
    lo = 0; hi = key_len - 1;
    while (lo <= hi) {
        int m = (lo + hi) >> 1;
        if (cpt < keys[m]) hi = m - 1;
        else if (cpt > keys[m]) lo = m + 1;
        else return vals[m];
    }
    return -1;
}

Wire this either as a specialized path for builtin compact cmaps, or expand into a normal pdf_cmap once and keep existing pdf_lookup_cmap unchanged (simpler, pays RAM after load).

Size summary (UniCNS-X only)

Layout	Approx. size	Runtime decode?
Current pdf_range[16377]	98.3 KB	no
Packed 5-byte / SoA	81.9 KB	no
Singletons 4 B + runs 6 B	67.5 KB	no
Page lists (4 B entries)	~66 KB	no
ULEB stream (expand on load)	~52 KB stored	yes

Caveats

• File is auto-generated (cmapdump); change the generator / a post-process step, not hand-edit UniCNS-X.h.
• pdf_cmap currently expects pdf_range *ranges. Either:
  • expand compact form → classic pdf_range[] at load (minimal invader into MuPDF), or
  • add a compact representation + lookup branch (more invasive, less RAM).
• Align/packing: measure with sizeof; MSVC vs clang differ on packed structs — SoA avoids that.
• Same optimization is likely even more valuable across all large cmaps (Adobe-Japan1-UCS2.h is bigger than UniCNS-X).