// WebP lossless (VP8L) encoder: length-limited Huffman codes, a cost-based
// (shortest path) LZ77 parse with 2-D distance codes and the color cache,
// meta prefix codes from clustered tile histograms, and the subtract-green,
// predictor, cross-color and color-indexing (palette) transforms. Several
// configurations are written and the smallest is kept.
///|
/// Huffman code lengths for `freqs`, limited to `limit` bits (frequencies
/// are flattened until the tree fits, like libwebp). Unused symbols get 0.
fn vp8l_huffman_lengths(
freqs : FixedArray[Int32],
limit : Int32,
) -> FixedArray[Int32] {
let n = freqs.length()
let lengths = FixedArray::make(n, 0)
let syms : Array[Int32] = []
for s in 0.. 0 {
syms.push(s)
}
}
if syms.length() == 0 {
return lengths
}
if syms.length() == 1 {
lengths[syms[0]] = 1
return lengths
}
let mut count_min = 1
while true {
let m = syms.length()
// Nodes 0..m-1 are leaves; internal nodes follow. Two-queue merge.
let weight = FixedArray::make(2 * m, 0)
let parent = FixedArray::make(2 * m, -1)
let order = syms.copy()
for i in 0..= next || weight[idx[li]] <= weight[qi]) {
li += 1
idx[li - 1]
} else {
qi += 1
qi - 1
}
}
for _ in 0..<(m - 1) {
let a = pick()
let b = pick()
weight[next] = weight[a] + weight[b]
parent[a] = next
parent[b] = next
next += 1
}
let mut max_len = 0
let depth = FixedArray::make(2 * m, 0)
for i = next - 2; i >= 0; i = i - 1 {
depth[i] = depth[parent[i]] + 1
}
for i in 0.. max_len {
max_len = depth[i]
}
}
if max_len <= limit {
for i in 0.. FixedArray[Int32] {
let codes = FixedArray::make(lengths.length(), 0)
let count = FixedArray::make(17, 0)
for l in lengths {
count[l] += 1
}
count[0] = 0
let next = FixedArray::make(17, 0)
let mut code = 0
for l in 1..<=16 {
code = (code + count[l - 1]) << 1
next[l] = code
}
for s in 0.. 0 {
codes[s] = webp_reverse_bits(next[l], l)
next[l] += 1
}
}
codes
}
///|
/// Write the code lengths of a normal prefix code: run-length tokens
/// (16 = repeat previous, 17 / 18 = zero runs) coded with a 7-bit-limited
/// code-length code. The full alphabet is always described.
fn vp8l_write_code_lengths(
bw : WebPBitWriter,
lengths : FixedArray[Int32],
) -> Unit {
let tokens : Array[Int32] = [] // token | extra << 8
let n = lengths.length()
let mut i = 0
while i < n {
let v = lengths[i]
let mut run = 1
while i + run < n && lengths[i + run] == v {
run += 1
}
i += run
if v == 0 {
while run > 0 {
if run >= 11 {
let r = if run > 138 { 138 } else { run }
tokens.push(18 | ((r - 11) << 8))
run -= r
} else if run >= 3 {
tokens.push(17 | ((run - 3) << 8))
run = 0
} else {
tokens.push(0)
run -= 1
}
}
} else {
tokens.push(v)
run -= 1
while run > 0 {
if run >= 3 {
let r = if run > 6 { 6 } else { run }
tokens.push(16 | ((r - 3) << 8))
run -= r
} else {
tokens.push(v)
run -= 1
}
}
}
}
let tfreq = FixedArray::make(19, 0)
for t in tokens {
tfreq[t & 0xff] += 1
}
let tlen = vp8l_huffman_lengths(tfreq, 7)
let tcode = vp8l_codes(tlen)
let mut num = 4
for k in 0..<19 {
if tlen[vp8l_code_length_order[k]] > 0 && k + 1 > num {
num = k + 1
}
}
bw.put_bits(0, 1) // normal code
bw.put_bits(num - 4, 4)
for k in 0.. 0 }).count() <= 1
for t in tokens {
let s = t & 0xff
if !single {
bw.put_bits(tcode[s], tlen[s])
}
match s {
16 => bw.put_bits(t >> 8, 2)
17 => bw.put_bits(t >> 8, 3)
18 => bw.put_bits(t >> 8, 7)
_ => ()
}
}
}
///|
/// Write a prefix code for `lengths` (simple code when possible). Returns
/// the bit-reversed codes to emit symbols with (lengths 0 = zero bits).
fn vp8l_write_prefix_code(
bw : WebPBitWriter,
lengths : FixedArray[Int32],
) -> FixedArray[Int32] {
let used : Array[Int32] = []
for s in 0.. 0 {
used.push(s)
}
}
if used.length() == 0 {
// Unused alphabet: a one-symbol code.
bw.put_bits(1, 1)
bw.put_bits(0, 1)
bw.put_bits(0, 1)
bw.put_bits(0, 1)
lengths.fill(0)
return FixedArray::make(lengths.length(), 0)
}
if used.length() <= 2 && used.iter().all(fn(s) { s < 256 }) {
bw.put_bits(1, 1)
bw.put_bits(used.length() - 1, 1)
if used[0] < 2 {
bw.put_bits(0, 1)
bw.put_bits(used[0], 1)
} else {
bw.put_bits(1, 1)
bw.put_bits(used[0], 8)
}
if used.length() == 2 {
bw.put_bits(used[1], 8)
} else {
lengths[used[0]] = 0 // one symbol: zero bits
}
return vp8l_codes(lengths)
}
vp8l_write_code_lengths(bw, lengths)
if used.length() == 1 {
lengths[used[0]] = 0
}
vp8l_codes(lengths)
}
///|
/// Prefix code and extra bits for a length / distance value >= 1:
/// (symbol, extra bit count, extra value).
fn vp8l_prefix_encode(v : Int32) -> (Int32, Int32, Int32) {
let d = v - 1
if d < 4 {
return (d, 0, 0)
}
let mut h = 0
while d >> (h + 1) != 0 {
h += 1
}
let second = (d >> (h - 1)) & 1
(2 * h + second, h - 1, d & ((1 << (h - 1)) - 1))
}
///|
/// LZ77 match candidates of every position of `px`: for position i the
/// entries `offs[i] ..< offs[i + 1]` of (distance code, length), in
/// increasing code and length order (each longer than the cheaper ones).
priv struct VP8LCands {
offs : FixedArray[Int32]
code : Array[Int32]
len : Array[Int32]
dsym : FixedArray[Int32] // distance prefix symbol | extra bits << 8
}
///|
/// Distance -> plane code (1..120) for the short 2-D distances of an image
/// `xsize` wide (0: no plane code).
fn vp8l_dist_codes(xsize : Int32) -> FixedArray[Int32] {
let t = FixedArray::make(xsize * 8 + 16, 0)
for c = 120; c >= 1; c = c - 1 {
let d = vp8l_plane_distance(xsize, c)
if d < t.length() {
t[d] = c
}
}
t
}
///|
fn vp8l_dist_to_code(codes : FixedArray[Int32], d : Int32) -> Int32 {
if d < codes.length() && codes[d] > 0 {
codes[d]
} else {
d + 120
}
}
///|
/// LZ77 search: the nearest plane codes always tried, and the depth of the
/// hash chain.
let vp8l_near_codes = 24
///|
let vp8l_chain_tries = 32
///|
/// Near-match length beyond which the hash chain is not searched.
let vp8l_long_match = 256
///|
fn vp8l_match_candidates(px : FixedArray[Int32], xsize : Int32) -> VP8LCands {
let n = px.length()
let offs = FixedArray::make(n + 1, 0)
let code : Array[Int32] = []
let len : Array[Int32] = []
let hash_bits = 16
let head = FixedArray::make(1 << hash_bits, -1)
let prev = FixedArray::make(n, -1)
let max_dist = (1 << 20) - 121
let codes = vp8l_dist_codes(xsize)
let hash = fn(i : Int32) -> Int32 {
let h = (px[i].reinterpret_as_uint() * 0x1E35A7BDU) ^
(px[i + 1].reinterpret_as_uint() * 0x9E3779B1U)
(h >> (32 - hash_bits)).reinterpret_as_int()
}
let match_len = fn(i : Int32, j : Int32) -> Int32 {
let max = if n - i > 4096 { 4096 } else { n - i }
let mut l = 0
while l < max && px[i + l] == px[j + l] {
l += 1
}
l
}
// Short 2-D distances (the cheapest plane codes) in code order.
let near : Array[Int32] = []
let near_code : Array[Int32] = []
for c in 1..<=vp8l_near_codes {
let d = vp8l_plane_distance(xsize, c)
if !near.contains(d) {
near.push(d)
near_code.push(c)
}
}
// A match of length l at i - 1 continues with length l - 1 at i, which
// keeps long runs linear.
let near_run = FixedArray::make(near.length(), 0)
let mut prev_chain_len = 0
let mut prev_chain_dist = 0
for i in 0.. 1 {
near_run[k] - 1
} else {
match_len(i, i - d)
}
near_run[k] = l
if l > best_len {
best_len = l
code.push(near_code[k])
len.push(l)
}
}
}
if i + 1 < n {
let h = hash(i)
let mut cand = head[h]
let mut tries = vp8l_chain_tries
let mut chain_len = best_len
let mut chain_dist = 0
if prev_chain_len - 1 > best_len && prev_chain_len > vp8l_dp_len_cap {
chain_len = prev_chain_len - 1
chain_dist = prev_chain_dist
tries = 0
}
let max_len = if n - i > 4096 { 4096 } else { n - i }
if best_len >= vp8l_long_match {
tries = 0 // a long 2-D match is good enough
}
while cand >= 0 && tries > 0 && i - cand <= max_dist {
// Quick reject: a longer match must also match at `chain_len`.
if chain_len >= max_len || px[cand + chain_len] != px[i + chain_len] {
cand = prev[cand]
tries -= 1
continue
}
let l = match_len(i, cand)
if l > chain_len {
chain_len = l
chain_dist = i - cand
}
cand = prev[cand]
tries -= 1
}
prev_chain_len = if chain_dist > 0 { chain_len } else { 0 }
prev_chain_dist = chain_dist
if chain_dist > 0 {
let c = vp8l_dist_to_code(codes, chain_dist)
// Keep the list ordered by code: drop cheaper-looking entries
// with a larger code (a far distance can map to a small code).
while code.length() > offs[i] && code[code.length() - 1] >= c {
ignore(code.pop())
ignore(len.pop())
}
code.push(c)
len.push(chain_len)
}
prev[i] = head[h]
head[h] = i
}
}
offs[n] = code.length()
let dsym = FixedArray::makei(code.length(), fn(k) {
let (ds, de, _) = vp8l_prefix_encode(code[k])
ds | (de << 8)
})
{ offs, code, len, dsym, }
}
///|
/// Greedy parse (longest match of at least 3) from the candidates: kinds
/// (0 literal, 1 cache hit, 2 copy), copy length / distance code in `a` /
/// `b`; literals and cache hits keep the pixel index in `a` (and the cache
/// key in `b`).
fn vp8l_greedy_parse(
cands : VP8LCands,
hits : FixedArray[Int32],
) -> (Array[Int32], Array[Int32], Array[Int32]) {
let kinds : Array[Int32] = []
let aa : Array[Int32] = []
let bb : Array[Int32] = []
let n = hits.length()
let mut i = 0
while i < n {
let e = cands.offs[i + 1]
if e > cands.offs[i] && cands.len[e - 1] >= 3 {
kinds.push(2)
aa.push(cands.len[e - 1])
bb.push(cands.code[e - 1])
i += cands.len[e - 1]
} else if hits[i] >= 0 {
kinds.push(1)
aa.push(i)
bb.push(hits[i])
i += 1
} else {
kinds.push(0)
aa.push(i)
bb.push(0)
i += 1
}
}
(kinds, aa, bb)
}
///|
/// Color cache hits of `px` (the cache state at a pixel does not depend on
/// the parse: every pixel is inserted in order).
fn vp8l_cache_hits(
px : FixedArray[Int32],
cache_bits : Int32,
) -> FixedArray[Int32] {
let n = px.length()
let hits = FixedArray::make(n, -1)
if cache_bits == 0 {
return hits
}
let size = 1 << cache_bits
let cache = FixedArray::make(size, 0)
let valid = FixedArray::make(size, false)
for i in 0.. (
FixedArray[Int32],
FixedArray[Int32],
FixedArray[Int32],
FixedArray[Int32],
FixedArray[Int32],
) {
let (kinds, aa, bb) = parse
let cache_size = if cache_bits > 0 { 1 << cache_bits } else { 0 }
let gf = FixedArray::make(280 + cache_size, 0)
let rf = FixedArray::make(256, 0)
let bf = FixedArray::make(256, 0)
let af = FixedArray::make(256, 0)
let df = FixedArray::make(40, 0)
for t in 0..> 8) & 0xff] += 1
rf[(c >> 16) & 0xff] += 1
bf[c & 0xff] += 1
af[(c >> 24) & 0xff] += 1
} else if kinds[t] == 1 {
gf[280 + bb[t]] += 1
} else {
gf[256 + vp8l_prefix_encode(aa[t]).0] += 1
df[vp8l_prefix_encode(bb[t]).0] += 1
}
}
(gf, rf, bf, af, df)
}
///|
/// Estimated bits of each symbol of a histogram (unused symbols get a
/// penalty, as they would need a code of their own).
fn vp8l_symbol_costs(h : FixedArray[Int32]) -> FixedArray[Double] {
let mut total = 0
for c in h {
total += c
}
let lt = vp8l_log2_fix(total + 1).to_double() / 256.0
FixedArray::makei(h.length(), fn(s) {
if h[s] > 0 {
lt - vp8l_log2_fix(h[s]).to_double() / 256.0
} else {
lt + 2.0
}
})
}
///|
/// Number of DP refinement passes of the cost-based LZ77 parse.
let vp8l_lz77_passes = 2
///|
/// Longest copy lengths tried exhaustively by the DP parse (longer
/// matches are also tried at their full length).
let vp8l_dp_len_cap = 16
///|
/// Transform candidates fully coded besides subtract green alone (the
/// others are dropped after a quick estimate), and the predictor tile
/// size.
let vp8l_full_candidates = 2
///|
let vp8l_pred_bits = 4
///|
/// Tile size (log2) of the meta prefix code image, raised on large images
/// to keep at most `vp8l_meta_max_tiles` tiles.
let vp8l_meta_bits = 4
///|
let vp8l_meta_max_tiles = 1024
///|
/// Quick estimate of the bits of an image (no LZ77): the better of
/// literals only and literals with an 8-bit color cache.
fn vp8l_quick_bits(px : FixedArray[Int32]) -> Double {
let hits = vp8l_cache_hits(px, 8)
// Literal histograms of all pixels / of the cache misses, and the green
// alphabet with the cache symbols.
let lit = FixedArray::make(4 * 256, 0)
let miss = FixedArray::make(4 * 256, 0)
let gc = FixedArray::make(256 + 256, 0)
for i in 0..> 24) & 0xff
let r = (c >> 16) & 0xff
let g = (c >> 8) & 0xff
let b = c & 0xff
lit[a] += 1
lit[256 + r] += 1
lit[512 + g] += 1
lit[768 + b] += 1
if hits[i] >= 0 {
gc[256 + hits[i]] += 1
} else {
miss[a] += 1
miss[256 + r] += 1
gc[g] += 1
miss[768 + b] += 1
}
}
let plain = vp8l_hist_bits(lit, 0, 256) +
vp8l_hist_bits(lit, 256, 256) +
vp8l_hist_bits(lit, 512, 256) +
vp8l_hist_bits(lit, 768, 256)
let cached = vp8l_hist_bits(miss, 0, 256) +
vp8l_hist_bits(miss, 256, 256) +
vp8l_hist_bits(gc, 0, 512) +
vp8l_hist_bits(miss, 768, 256)
if plain < cached {
plain
} else {
cached
}
}
///|
/// Entropy (bits) of the counts `h[off ..< off + len]`.
fn vp8l_hist_bits(h : FixedArray[Int32], off : Int32, len : Int32) -> Double {
let mut total = 0
for i in off..<(off + len) {
total += h[i]
}
let lt = vp8l_log2_fix(total)
let mut bits = 0
for i in off..<(off + len) {
let c = h[i]
if c > 0 {
bits += c * (lt - vp8l_log2_fix(c)) // fits: counts * 2^13 at most
}
}
bits.to_double() / 256.0
}
///|
/// Prefix symbol | extra bits << 8 of each copy length.
let vp8l_len_prefix : FixedArray[Int32] = FixedArray::makei(4097, fn(l) {
if l == 0 {
0
} else {
let (s, e, _) = vp8l_prefix_encode(l)
s | (e << 8)
}
})
///|
/// Cost-based LZ77 parse: a shortest path over literals / cache hits and
/// the candidate copies, with symbol costs taken from the previous parse.
fn vp8l_lz77(
px : FixedArray[Int32],
cands : VP8LCands,
cache_bits : Int32,
) -> (Array[Int32], Array[Int32], Array[Int32]) {
let n = px.length()
let hits = vp8l_cache_hits(px, cache_bits)
let greedy = vp8l_greedy_parse(cands, hits)
if cache_bits == 0 {
return vp8l_lz77_refine(px, cands, cache_bits, hits, greedy)
}
// With a cache, literals and cache hits only can be the better start
// (noisy images with few distinct residual colors): refine whichever
// starting parse is estimated cheaper.
let k = Array::make(n, 0)
let a = Array::make(n, 0)
let b = Array::make(n, 0)
for i in 0..= 0 {
k[i] = 1
b[i] = hits[i]
}
}
let cached = (k, a, b)
let init = if vp8l_parse_bits(px, cache_bits, cached) <
vp8l_parse_bits(px, cache_bits, greedy) {
cached
} else {
greedy
}
vp8l_lz77_refine(px, cands, cache_bits, hits, init)
}
///|
/// Estimated bits of a parse: the entropy of its symbols plus extra bits.
fn vp8l_parse_bits(
px : FixedArray[Int32],
cache_bits : Int32,
parse : (Array[Int32], Array[Int32], Array[Int32]),
) -> Double {
let (gf, rf, bf, af, df) = vp8l_parse_histograms(px, cache_bits, parse)
let mut bits = 0.0
for h in [gf, rf, bf, af, df] {
let mut total = 0
for c in h {
total += c
}
let lt = vp8l_log2_fix(total)
for c in h {
if c > 0 {
bits += c.to_double() * (lt - vp8l_log2_fix(c)).to_double() / 256.0
}
}
}
let (kinds, aa, bb) = parse
for t in 0.. (Array[Int32], Array[Int32], Array[Int32]) {
let n = px.length()
let mut parse = init
let cost = FixedArray::make(n + 1, 0.0)
let from_len = FixedArray::make(n + 1, 0)
let from_code = FixedArray::make(n + 1, 0)
let from_cache = FixedArray::make(n + 1, false)
let len_cost = FixedArray::make(4097, 0.0)
let mut max_cands = 0
for i in 0.. max_cands {
max_cands = c
}
}
let sfx_cost = FixedArray::make(max_cands, 0.0)
let sfx_k = FixedArray::make(max_cands, 0)
for _ in 0..> 8).to_double()
}
cost.fill(1.0e300)
cost[0] = 0.0
for i in 0..> 8) & 0xff] +
rc[(c >> 16) & 0xff] +
bc[c & 0xff] +
ac[(c >> 24) & 0xff]
let use_cache = hits[i] >= 0 && gc[280 + hits[i]] < lit
let lit = if use_cache { gc[280 + hits[i]] } else { lit }
if c0 + lit < cost[i + 1] {
cost[i + 1] = c0 + lit
from_len[i + 1] = 0
from_cache[i + 1] = use_cache
}
let s = cands.offs[i]
let e = cands.offs[i + 1]
// Candidates come in increasing code / length order; a copy of
// length l uses the cheapest candidate at least l long.
// Suffix minimum of the distance costs.
let mut run_cost = 1.0e300
let mut run_k = e
for k = e - 1; k >= s; k = k - 1 {
let d = cands.dsym[k]
let c = dc[d & 0xff] + (d >> 8).to_double()
if c < run_cost {
run_cost = c
run_k = k
}
sfx_cost[k - s] = run_cost
sfx_k[k - s] = run_k
}
let mut lo = 1
for k in s.. vp8l_dp_len_cap { vp8l_dp_len_cap } else { hi }
for l in lo..<=top {
let c = base + len_cost[l]
if c < cost[i + l] {
cost[i + l] = c
from_len[i + l] = l
from_code[i + l] = code
}
}
if hi > top && hi >= lo {
let c = base + len_cost[hi]
if c < cost[i + hi] {
cost[i + hi] = c
from_len[i + hi] = hi
from_code[i + hi] = code
}
}
lo = hi + 1
}
}
// Trace back.
let kinds : Array[Int32] = []
let aa : Array[Int32] = []
let bb : Array[Int32] = []
let mut p = n
while p > 0 {
let l = from_len[p]
if l == 0 {
kinds.push(if from_cache[p] { 1 } else { 0 })
aa.push(p - 1)
bb.push(if from_cache[p] { hits[p - 1] } else { 0 })
p -= 1
} else {
kinds.push(2)
aa.push(l)
bb.push(from_code[p])
p -= l
}
}
kinds.rev_in_place()
aa.rev_in_place()
bb.rev_in_place()
parse = (kinds, aa, bb)
}
parse
}
///|
/// Write one entropy-coded image (`main`: the level-0 image, which also
/// carries the meta prefix bit). `lz` is an LZ77 parse of `px` (copy
/// distances as codes) or None
/// for literals only.
fn vp8l_write_image(
bw : WebPBitWriter,
px : FixedArray[Int32],
cache_bits : Int32,
lz : (Array[Int32], Array[Int32], Array[Int32])?,
main : Bool,
meta : (Int32, Int32)?,
) -> Unit {
let n = px.length()
let (kinds, aa, bb) = match lz {
Some(t) => t
None => {
let k = Array::make(n, 0)
let a = Array::makei(n, fn(i) { i })
(k, a, Array::make(n, 0))
}
}
// Final tokens: 0 literal (argb in ta), 1 cache (key), 2 copy.
let cache_size = if cache_bits > 0 { 1 << cache_bits } else { 0 }
let tk : Array[Int32] = []
let ta : Array[Int32] = []
let tb : Array[Int32] = []
for t in 0.. {
tk.push(0)
ta.push(px[aa[t]])
tb.push(0)
}
1 => {
tk.push(1)
ta.push(bb[t])
tb.push(0)
}
_ => {
tk.push(2)
ta.push(aa[t])
tb.push(bb[t])
}
}
}
// Group of every token: with meta prefix codes, the cluster of the tile
// its first pixel is in.
let ntok = tk.length()
let tgroup = FixedArray::make(ntok, 0)
let gsize = 280 + cache_size
let hs = gsize + 768 + 40
let (num_groups, meta_img) = match meta {
Some((xsize, bits)) => {
// Larger tiles on large images bound the per-tile histograms.
let mut mbits = bits
while mbits < 9 &&
vp8l_subsample(xsize, mbits) * vp8l_subsample(n / xsize, mbits) >
vp8l_meta_max_tiles {
mbits += 1
}
let tw = vp8l_subsample(xsize, mbits)
let th = vp8l_subsample(n / xsize, mbits)
let tile = FixedArray::make(ntok, 0)
let mut pos = 0
for t in 0..> mbits) * tw + ((pos % xsize) >> mbits)
pos += if tk[t] == 2 { ta[t] } else { 1 }
}
let th_ = vp8l_tile_histograms(tk, ta, tb, tile, tw * th, gsize)
let assign = vp8l_cluster_tiles(th_, tw * th, gsize)
let mut g = 0
for v in assign {
if v + 1 > g {
g = v + 1
}
}
for t in 0..> 8 << 16) | ((v & 0xff) << 8)
})
(g, Some((mbits, img)))
}
None => (1, None)
}
// Histograms per group.
let hist = FixedArray::make(num_groups * hs, 0)
for t in 0.. {
let c = ta[t]
hist[o + ((c >> 8) & 0xff)] += 1
hist[o + gsize + ((c >> 16) & 0xff)] += 1
hist[o + gsize + 256 + (c & 0xff)] += 1
hist[o + gsize + 512 + ((c >> 24) & 0xff)] += 1
}
1 => hist[o + 280 + ta[t]] += 1
_ => {
hist[o + 256 + vp8l_prefix_encode(ta[t]).0] += 1
hist[o + gsize + 768 + vp8l_prefix_encode(tb[t]).0] += 1
}
}
}
if cache_bits > 0 {
bw.put_bits(1, 1)
bw.put_bits(cache_bits, 4)
} else {
bw.put_bits(0, 1)
}
if main {
match meta_img {
Some((mbits, img)) => {
bw.put_bits(1, 1)
bw.put_bits(mbits - 2, 3)
vp8l_write_image(bw, img, 0, None, false, None)
}
None => bw.put_bits(0, 1) // no meta prefix codes
}
}
// Codes of each group: green, red, blue, alpha, distance.
let lens : Array[FixedArray[Int32]] = []
let codes : Array[FixedArray[Int32]] = []
let seg_off = [0, gsize, gsize + 256, gsize + 512, gsize + 768]
let seg_len = [gsize, 256, 256, 256, 40]
for g in 0.. {
let c = ta[t]
let g = (c >> 8) & 0xff
let r = (c >> 16) & 0xff
let b = c & 0xff
let a = (c >> 24) & 0xff
bw.put_bits(gc[g], gl[g])
bw.put_bits(codes[g5 + 1][r], lens[g5 + 1][r])
bw.put_bits(codes[g5 + 2][b], lens[g5 + 2][b])
bw.put_bits(codes[g5 + 3][a], lens[g5 + 3][a])
}
1 => {
let s = 280 + ta[t]
bw.put_bits(gc[s], gl[s])
}
_ => {
let (ls, le, lv) = vp8l_prefix_encode(ta[t])
bw.put_bits(gc[256 + ls], gl[256 + ls])
bw.put_bits(lv, le)
let (ds, de, dv) = vp8l_prefix_encode(tb[t])
bw.put_bits(codes[g5 + 4][ds], lens[g5 + 4][ds])
bw.put_bits(dv, de)
}
}
}
}
///|
/// Token histograms of every tile (layout per tile: green / length /
/// cache, red, blue, alpha, distance).
fn vp8l_tile_histograms(
tk : Array[Int32],
ta : Array[Int32],
tb : Array[Int32],
tile : FixedArray[Int32],
ntiles : Int32,
gsize : Int32,
) -> FixedArray[Int32] {
let hs = gsize + 768 + 40
let h = FixedArray::make(ntiles * hs, 0)
for t in 0.. {
let c = ta[t]
h[o + ((c >> 8) & 0xff)] += 1
h[o + gsize + ((c >> 16) & 0xff)] += 1
h[o + gsize + 256 + (c & 0xff)] += 1
h[o + gsize + 512 + ((c >> 24) & 0xff)] += 1
}
1 => h[o + 280 + ta[t]] += 1
_ => {
h[o + 256 + vp8l_prefix_encode(ta[t]).0] += 1
h[o + gsize + 768 + vp8l_prefix_encode(tb[t]).0] += 1
}
}
}
h
}
///|
/// Estimated header bits of a prefix code with `used` symbols.
let vp8l_code_header_bits : Double = 40.0
///|
let vp8l_code_symbol_bits : Double = 3.0
///|
/// Estimated bits of one histogram set (5 codes): entropy plus headers.
fn vp8l_histo_cost(h : FixedArray[Int32], off : Int32, gsize : Int32) -> Double {
let segs = [
(0, gsize),
(gsize, 256),
(gsize + 256, 256),
(gsize + 512, 256),
(gsize + 768, 40),
]
let mut bits = 0.0
for seg in segs {
let (so, sl) = seg
let mut used = 0
for i in 0.. 0 {
used += 1
}
}
bits += vp8l_hist_bits(h, off + so, sl)
if used > 1 {
bits += vp8l_code_header_bits + used.to_double() * vp8l_code_symbol_bits
} else {
bits += 8.0
}
}
bits
}
///|
/// Cluster tile histograms into prefix-code groups: tiles are first binned
/// by the entropy of their green / red / blue symbols, then clusters are
/// merged greedily while that lowers the estimated bits. Returns the group
/// of every tile.
fn vp8l_cluster_tiles(
th : FixedArray[Int32],
ntiles : Int32,
gsize : Int32,
) -> FixedArray[Int32] {
let hs = gsize + 768 + 40
let assign = FixedArray::make(ntiles, 0)
// Entropy signature (bits per token) of each non-empty tile.
let sig = FixedArray::make(ntiles * 3, 0.0)
let nonempty = FixedArray::make(ntiles, false)
let lo = [1.0e300, 1.0e300, 1.0e300]
let hi = [-1.0, -1.0, -1.0]
for t in 0.. hi[k] {
hi[k] = e
}
}
}
// Initial clusters: bins of 4 x 4 x 4 signature levels.
let bin_of = FixedArray::make(64, -1)
let cl : Array[FixedArray[Int32]] = []
let members : Array[Array[Int32]] = []
for t in 0.. 3 {
3
} else {
v
}
}
key = key * 4 + q
}
if bin_of[key] < 0 {
bin_of[key] = cl.length()
cl.push(FixedArray::make(hs, 0))
members.push([])
}
let c = bin_of[key]
let h = cl[c]
for i in 0.. Double {
for i in 0.. best {
best = gain[a * m + b]
ba = a
bb = b
}
}
}
if ba < 0 {
break
}
for i in 0.. Int32 {
// libwebp's VP8LSubPixels: per-channel a - b (mod 256).
let ag = 0x00ff00ff + (a & 0xff00ff00) - (b & 0xff00ff00)
let rb = 0xff00ff00 + (a & 0x00ff00ff) - (b & 0x00ff00ff)
(ag & 0xff00ff00) | (rb & 0x00ff00ff)
}
///|
/// Prior for the predictor statistics: counts (width - |v|) * scale.
let vp8l_pred_prior_width = 16
///|
let vp8l_pred_prior_scale = 4
///|
/// log2(x) * 256 (fixed point) for x >= 1, in 32-bit arithmetic (Int64 is
/// slow on the js target).
fn vp8l_log2_fix(x : Int32) -> Int32 {
let mut ip = 0
while ip < 30 && 2 << ip <= x {
ip += 1
}
// Mantissa in [1, 2) with 15 fractional bits, refined by squaring.
let mut m = (if ip <= 15 { x << (15 - ip) } else { x >> (ip - 15) }).reinterpret_as_uint()
let mut frac = 0
for k in 0..<8 {
m = (m * m) >> 15
if m >= 2U << 15 {
m = m >> 1
frac = frac | (1 << (7 - k))
}
}
ip * 256 + frac
}
///|
/// Choose a predictor mode per tile and return (residuals, mode image).
fn vp8l_predict_image(
px : FixedArray[Int32],
w : Int32,
h : Int32,
bits : Int32,
) -> (FixedArray[Int32], FixedArray[Int32]) {
let tw = vp8l_subsample(w, bits)
let th = vp8l_subsample(h, bits)
let modes = FixedArray::make(tw * th, 0)
let res = FixedArray::make(w * h, 0)
let size = 1 << bits
// Residual histograms (A, R, G, B) of the tiles decided so far.
// A prior peaked at residual 0 keeps the first tiles from locking the
// statistics onto a bad mode.
let acc = FixedArray::makei(4 * 256, fn(i) {
let v = i & 0xff
let d = if v >= 128 { 256 - v } else { v }
if d < vp8l_pred_prior_width {
(vp8l_pred_prior_width - d) * vp8l_pred_prior_scale
} else {
0
}
})
let acc_total = FixedArray::make(4, 0)
for k in 0..<4 {
for v in 0..<256 {
acc_total[k] += acc[k * 256 + v]
}
}
let cost_tab = FixedArray::make(4 * 256, 0)
for ty in 0.. w { w } else { x0 + size }
let y1 = if y0 + size > h { h } else { y0 + size }
// Each mode is scored by the bits its residuals would take under
// the residual statistics accumulated so far (libwebp-style), which
// favors modes that keep the histograms peaked.
for k in 0..<4 {
let t = acc_total[k] + 256
let lt = vp8l_log2_fix(t)
for v in 0..<256 {
cost_tab[k * 256 + v] = lt - vp8l_log2_fix(acc[k * 256 + v] + 1)
}
}
let mut best = 0
let mut best_cost = 0x7fffffff
for mode in 0..<14 {
let mut cost = 0
for y in y0..> 24) & 0xff] +
cost_tab[256 + ((r >> 16) & 0xff)] +
cost_tab[512 + ((r >> 8) & 0xff)] +
cost_tab[768 + (r & 0xff)]
}
}
if cost < best_cost {
best_cost = cost
best = mode
}
}
modes[ty * tw + tx] = 0xff000000 | (best << 8)
for y in y0..> 24) & 0xff] += 1
acc[256 + ((r >> 16) & 0xff)] += 1
acc[512 + ((r >> 8) & 0xff)] += 1
acc[768 + (r & 0xff)] += 1
for k in 0..<4 {
acc_total[k] += 1
}
}
}
}
}
for y in 0..> bits) * tw + (x >> bits)] >> 8) & 0xf,
px,
pos,
w,
)
}
res[pos] = vp8l_sub_pixels(px[pos], pred)
}
}
(res, modes)
}
///|
/// Encode `img` as a VP8L bitstream (the payload of a `VP8L` chunk).
fn vp8l_encode(img : ImageData) -> Bytes {
let w = img.width
let h = img.height
let n = w * h
let argb = FixedArray::make(n, 0)
let mut has_alpha = false
for i in 0.. Bytes {
let n = w * h
let header = fn(bw : WebPBitWriter) {
if !with_header {
return
}
bw.put_bits(0x2F, 8)
bw.put_bits(w - 1, 14)
bw.put_bits(h - 1, 14)
bw.put_bits(if has_alpha { 1 } else { 0 }, 1)
bw.put_bits(0, 3)
}
let mut best : Bytes? = None
let consider = fn(bw : WebPBitWriter) {
bw.flush()
match best {
Some(b) if b.length() <= bw.buf.length() => ()
_ => best = Some(bw.to_bytes())
}
}
// Candidate 1: palette (color indexing) for <= 256 colors.
let colors : Map[Int32, Int32] = Map([])
for i in 0.. 256 {
break
}
colors[argb[i]] = 0
}
}
if colors.length() <= 256 {
let palette = colors.keys().collect()
palette.sort_by(fn(a, b) {
let ua = a.reinterpret_as_uint()
let ub = b.reinterpret_as_uint()
if ua < ub {
-1
} else if ua > ub {
1
} else {
0
}
})
for i, c in palette {
colors[c] = i
}
let num = palette.length()
let bits = if num > 16 {
0
} else if num > 4 {
1
} else if num > 2 {
2
} else {
3
}
let pw = vp8l_subsample(w, bits)
let packed = FixedArray::make(pw * h, 0xff000000)
let bpp = 8 >> bits
for y in 0..> bits)
packed[o] = packed[o] | (idx << (8 + (x & ((1 << bits) - 1)) * bpp))
}
}
let deltas = FixedArray::make(num, 0)
for i in 0..> 8) & 0xff
sg[i] = (c & 0xff00ff00) |
((((c >> 16) - g) & 0xff) << 16) |
((c - g) & 0xff)
}
// Candidates: subtract green alone, and the predictor with or without
// subtract green, each with or without cross color. They are ranked by
// the estimated bits of a quick parse; the best few are fully coded.
let pending : Array[
(
Bool,
(Int32, FixedArray[Int32])?,
(Int32, FixedArray[Int32])?,
FixedArray[Int32],
Double,
),
] = []
let add = fn(
use_sg : Bool,
pred : (Int32, FixedArray[Int32])?,
cc : (Int32, FixedArray[Int32])?,
main : FixedArray[Int32],
) {
pending.push((use_sg, pred, cc, main, vp8l_quick_bits(main)))
}
add(true, None, None, sg)
for use_sg in [true, false] {
let base = if use_sg { sg } else { argb }
let (res, modes) = vp8l_predict_image(base, w, h, vp8l_pred_bits)
add(use_sg, Some((vp8l_pred_bits, modes)), None, res)
for cbits in [4] {
let (cres, mult) = vp8l_cross_color_image(res, w, h, cbits)
add(use_sg, Some((vp8l_pred_bits, modes)), Some((cbits, mult)), cres)
}
}
// Subtract green alone (the first candidate) is always coded: it gains
// most from LZ77, which the estimate leaves out.
let first = pending[0]
let rest = pending[1:].to_owned()
rest.sort_by(fn(x, y) { x.4.compare(y.4) })
let chosen = [first]
for t in 0.. Int32 {
let (use_sg, pred, cc, main, _) = entry
let bw = WebPBitWriter::new()
header(bw)
if use_sg {
bw.put_bits(1, 1)
bw.put_bits(2, 2) // subtract green
}
match pred {
Some((pbits, modes)) => {
bw.put_bits(1, 1)
bw.put_bits(0, 2) // predictor
bw.put_bits(pbits - 2, 3)
vp8l_write_image(bw, modes, 0, None, false, None)
}
None => ()
}
match cc {
Some((cbits, mult)) => {
bw.put_bits(1, 1)
bw.put_bits(1, 2) // cross color
bw.put_bits(cbits - 2, 3)
vp8l_write_image(bw, mult, 0, None, false, None)
}
None => ()
}
bw.put_bits(0, 1)
vp8l_write_image(bw, main, cache_bits, Some(lz), true, meta)
consider(bw)
bw.buf.length()
}
// Single prefix code for every candidate and cache size; meta prefix
// codes (clustered tile histograms) for the smallest one of each cache
// size only.
let caches = [0, 8]
let top = Array::make(caches.length(), None)
let top_size = Array::make(caches.length(), 0x7fffffff)
for entry in chosen {
let cands = vp8l_match_candidates(entry.3, w)
for k, cache_bits in caches {
let lz = vp8l_lz77(entry.3, cands, cache_bits)
let size = write(entry, cache_bits, lz, None)
if size < top_size[k] {
top_size[k] = size
top[k] = Some((entry, lz))
}
}
}
for k, cache_bits in caches {
match top[k] {
Some((entry, lz)) =>
ignore(write(entry, cache_bits, lz, Some((w, vp8l_meta_bits))))
None => ()
}
}
best.unwrap()
}
///|
/// Cross-color transform of `px` (predictor residuals): per tile, the
/// green-to-red, green-to-blue and red-to-blue multipliers minimizing the
/// residual bits under the statistics accumulated so far. Returns
/// (transformed pixels, multiplier image).
fn vp8l_cross_color_image(
px : FixedArray[Int32],
w : Int32,
h : Int32,
bits : Int32,
) -> (FixedArray[Int32], FixedArray[Int32]) {
let tw = vp8l_subsample(w, bits)
let th = vp8l_subsample(h, bits)
let mult = FixedArray::make(tw * th, 0xff000000)
let out = FixedArray::make(w * h, 0)
let size = 1 << bits
// Red / blue histograms with a prior peaked at 0 (as for the predictor).
let acc = FixedArray::makei(2 * 256, fn(i) {
let v = i & 0xff
let d = if v >= 128 { 256 - v } else { v }
if d < vp8l_pred_prior_width {
(vp8l_pred_prior_width - d) * vp8l_pred_prior_scale
} else {
0
}
})
let acc_total = FixedArray::make(2, 0)
for k in 0..<2 {
for v in 0..<256 {
acc_total[k] += acc[k * 256 + v]
}
}
let cost_tab = FixedArray::make(2 * 256, 0)
let tg = FixedArray::make(size * size, 0)
let tr = FixedArray::make(size * size, 0)
let tb = FixedArray::make(size * size, 0)
let trs = FixedArray::make(size * size, 0)
let signed = fn(v : Int32) { if v >= 128 { v - 256 } else { v } }
let mut prev_g2r = 0
let mut prev_g2b = 0
let mut prev_r2b = 0
for ty in 0..| w { w } else { x0 + size }
let y1 = if y0 + size > h { h } else { y0 + size }
let mut cnt = 0
for y in y0..> 8) & 0xff)
tr[cnt] = (c >> 16) & 0xff
tb[cnt] = c & 0xff
cnt += 1
}
}
for k in 0..<2 {
let lt = vp8l_log2_fix(acc_total[k] + 256)
for v in 0..<256 {
cost_tab[k * 256 + v] = lt - vp8l_log2_fix(acc[k * 256 + v] + 1)
}
}
// Bits of red for green-to-red multiplier t (plus a small bias
// towards the previous tile's value, which codes cheaply).
let pg2r = prev_g2r
let pg2b = prev_g2b
let pr2b = prev_r2b
for i in 0.. Int32 {
let mut c = 0
for i in 0..> 5)) & 0xff]
}
c + (if t == pg2r { 0 } else { 256 })
}
let blue_cost = fn(g2b : Int32, r2b : Int32) -> Int32 {
let mut c = 0
for i in 0..> 5) - ((r2b * trs[i]) >> 5)
c += cost_tab[256 + (v & 0xff)]
}
c +
(if g2b == pg2b { 0 } else { 256 }) +
(if r2b == pr2b { 0 } else { 256 })
}
// Coarse-to-fine search over the signed range.
let search = fn(start : Int32, f : (Int32) -> Int32) -> Int32 {
let mut best = start
let mut best_c = f(start)
for cand in [0, pg2r, pg2b, pr2b] {
let c = f(cand)
if c < best_c {
best_c = c
best = cand
}
}
let mut step = 32
while step >= 1 {
let center = best
for d in [-step, step] {
let cand = center + d
if cand >= -128 && cand <= 127 {
let c = f(cand)
if c < best_c {
best_c = c
best = cand
}
}
}
step = step >> 1
}
best
}
let g2r = search(pg2r, red_cost)
let g2b0 = search(pg2b, fn(t) { blue_cost(t, pr2b) })
let r2b = search(pr2b, fn(t) { blue_cost(g2b0, t) })
let g2b = search(g2b0, fn(t) { blue_cost(t, r2b) })
prev_g2r = g2r
prev_g2b = g2b
prev_r2b = r2b
mult[ty * tw + tx] = 0xff000000 |
((r2b & 0xff) << 16) |
((g2b & 0xff) << 8) |
(g2r & 0xff)
let mut i = 0
for y in y0..> 5)) & 0xff
let nb = (tb[i] - ((g2b * tg[i]) >> 5) - ((r2b * trs[i]) >> 5)) & 0xff
out[pos] = (c & 0xff00ff00) | (nr << 16) | nb
acc[nr] += 1
acc[256 + nb] += 1
acc_total[0] += 1
acc_total[1] += 1
i += 1
}
}
}
}
(out, mult)
}
| |