dymokomi/luce-exr
Source of release 0.6.1
## PIZ range/Huffman/wavelet decoding, ported from the OpenEXR algorithms.
## SPDX-License-Identifier: BSD-3-Clause (see LICENSES/OpenEXR.txt).
## Copyright (c) Contributors to the OpenEXR Project.
import memory
from luce_raster.binary import Reader, Buffer
from luce_raster.model import Raster, Chunk
from luce_raster.errors import corrupt
struct Bits:
var data: const u8[]
var position: usize
var end: usize
func read(count: usize) -> u64!:
if count > self.end - self.position:
error(corrupt, "truncated PIZ bitstream")
var value: u64 = 0
for i in 0..<count:
value = (value << 1) | (u64)((self.data[self.position // 8] >> (7 - self.position % 8)) & 1)
self.position += 1
return value
func huffman(data: const u8[], out: u16[]) -> !:
var r = Reader(data = data)
let first_symbol = (usize)(try r.uint(4))
let last_symbol = (usize)(try r.uint(4))
let table_bytes = (usize)(try r.uint(4))
let bit_count = (usize)(try r.uint(4))
_ = try r.uint(4)
if first_symbol > last_symbol or last_symbol > 65536:
error(corrupt, "invalid PIZ Huffman symbol range")
let lengths = try new usize[65537] in memory.heap
defer free(lengths) in memory.heap
let table = try r.take(table_bytes)
var bits = Bits(data = table, end = table.length * 8)
var symbol = first_symbol
var counts: u64[59]
while symbol <= last_symbol:
let length = (usize)(try bits.read(6))
if length >= 59:
let run = (usize)(try bits.read(8)) + 6 if length == 63 else length - 59 + 2
if run > last_symbol + 1 - symbol:
error(corrupt, "PIZ Huffman zero run exceeds table")
symbol += run
else:
lengths[symbol] = length
counts[length] += 1
symbol += 1
if (bits.position + 7) // 8 != table_bytes:
error(corrupt, "PIZ Huffman table length mismatch")
var first: u64[59]
var offsets: usize[59]
var next: usize[59]
var code: u64 = 0
var length: usize = 58
while length > 0:
first[length] = code
code = (code + counts[length]) >> 1
if first[length] + counts[length] > ((u64)1 << length):
error(corrupt, "oversubscribed PIZ Huffman tree")
length -= 1
for i in 2..<(usize)59:
offsets[i] = offsets[i - 1] + (usize)counts[i - 1]
next[i] = offsets[i]
let symbols = try new usize[65537] in memory.heap
defer free(symbols) in memory.heap
for i in first_symbol..<last_symbol + 1:
let n = lengths[i]
if n > 0:
symbols[next[n]] = i
next[n] += 1
let encoded = try r.take((bit_count + 7) // 8)
if r.position != data.length:
error(corrupt, "trailing bytes in PIZ Huffman payload")
bits = Bits(data = encoded, end = bit_count)
var used: usize = 0
while bits.position < bits.end:
var value: u64 = 0
var decoded: usize = 65537
for n in 1..<(usize)59:
value = (value << 1) | (try bits.read(1))
if value >= first[n] and value - first[n] < counts[n]:
decoded = symbols[offsets[n] + (usize)(value - first[n])]
break
if decoded == 65537:
error(corrupt, "invalid PIZ Huffman code")
if decoded == last_symbol:
let run = (usize)(try bits.read(8))
if used == 0 or run > out.length - used:
error(corrupt, "invalid PIZ repeated symbol run")
for i in 0..<run:
out[used] = out[used - 1]
used += 1
else:
if used == out.length:
error(corrupt, "PIZ Huffman output exceeds chunk")
out[used] = (u16)decoded
used += 1
if used != out.length:
error(corrupt, "PIZ Huffman output size mismatch")
func pair(low: u16, high: u16, small: bool) -> (u16, u16):
if small:
let hi = (i32)(i16)high
let a = (i32)(i16)low + (hi & 1) + (hi >> 1)
return ((u16)a, (u16)(a - hi))
let b = ((i32)low - ((i32)high >> 1)) & 65535
return ((u16)(((i32)high + b - 32768) & 65535), (u16)b)
func wavelet(data: u16[], base: usize, width: usize, height: usize, step: usize, small: bool):
let minimum = width if width < height else height
var p: usize = 1
while p <= minimum:
p <<= 1
p >>= 1
var p2 = p
p >>= 1
while p > 0:
var y: usize = 0
while y + p2 <= height:
var x: usize = 0
while x + p2 <= width:
let a = base + (y * width + x) * step
let b = a + p * step
let c = a + p * width * step
let d = c + p * step
let (i00, i10) = pair(data[a], data[c], small)
let (i01, i11) = pair(data[b], data[d], small)
let (aa, bb) = pair(i00, i01, small)
let (cc, dd) = pair(i10, i11, small)
data[a] = aa
data[b] = bb
data[c] = cc
data[d] = dd
x += p2
if (width & p) != 0:
let a = base + (y * width + x) * step
let b = a + p * width * step
let (aa, bb) = pair(data[a], data[b], small)
data[a] = aa
data[b] = bb
y += p2
if (height & p) != 0:
var x: usize = 0
while x + p2 <= width:
let a = base + (y * width + x) * step
let b = a + p * step
let (aa, bb) = pair(data[a], data[b], small)
data[a] = aa
data[b] = bb
x += p2
p2 = p
p >>= 1
pub func decode(image: const Raster*, chunk: Chunk, data: const u8[], out: u8[]) -> !:
var r = Reader(data = data)
let minimum = (usize)(try r.uint(2))
let maximum = (usize)(try r.uint(2))
if maximum >= 8192:
error(corrupt, "invalid PIZ bitmap range")
var bitmap: u8[8192]
if minimum <= maximum:
let bytes = try r.take(maximum - minimum + 1)
memory.copy(bitmap[minimum..], bytes, bytes.length)
let lut = try new u16[65536] in memory.heap
defer free(lut) in memory.heap
var count: usize = 0
for i in 0..<(usize)65536:
if i == 0 or (bitmap[i >> 3] & ((u8)1 << (i & 7))) != 0:
lut[count] = (u16)i
count += 1
let hufbytes = (usize)(try r.uint(4))
let words = try new u16[out.length // 2] in memory.heap
defer free(words) in memory.heap
try huffman(try r.take(hufbytes), words)
if r.position != data.length:
error(corrupt, "trailing PIZ payload")
var base: usize = 0
for channel in image.channels:
let step: usize = 1 if channel.kind == .float16 else 2
for j in 0..<step:
wavelet(words, base + j, chunk.width, chunk.height, step, count <= 16384)
base += chunk.width * chunk.height * step
var offset: usize = 0
for y in 0..<chunk.height:
base = 0
for channel in image.channels:
let step: usize = 1 if channel.kind == .float16 else 2
for x in 0..<chunk.width * step:
let code = (usize)words[base + y * chunk.width * step + x]
if code >= count:
error(corrupt, "PIZ range code outside bitmap")
let value = lut[code]
out[offset] = (u8)value
out[offset + 1] = (u8)(value >> 8)
offset += 2
base += chunk.width * chunk.height * step
func forward_pair(a: u16, b: u16, small: bool) -> (u16, u16):
if small:
let aa = (i32)(i16)a
let bb = (i32)(i16)b
return ((u16)((aa + bb) >> 1), (u16)(aa - bb))
let aa = ((i32)a + 32768) & 65535
let difference = aa - (i32)b
let middle = ((aa + (i32)b) >> 1) + (32768 if difference < 0 else 0)
return ((u16)middle, (u16)difference)
func forward_wavelet(data: u16[], base: usize, width: usize, height: usize, step: usize, small: bool):
let minimum = width if width < height else height
var p: usize = 1
while p * 2 <= minimum:
let p2 = p * 2
var y: usize = 0
while y + p2 <= height:
var x: usize = 0
while x + p2 <= width:
let a = base + (y * width + x) * step
let b = a + p * step
let c = a + p * width * step
let d = c + p * step
let (i00, i01) = forward_pair(data[a], data[b], small)
let (i10, i11) = forward_pair(data[c], data[d], small)
let (aa, cc) = forward_pair(i00, i10, small)
let (bb, dd) = forward_pair(i01, i11, small)
data[a] = aa
data[b] = bb
data[c] = cc
data[d] = dd
x += p2
if (width & p) != 0:
let a = base + (y * width + x) * step
let b = a + p * width * step
let (aa, bb) = forward_pair(data[a], data[b], small)
data[a] = aa
data[b] = bb
y += p2
if (height & p) != 0:
var x: usize = 0
while x + p2 <= width:
let a = base + (y * width + x) * step
let b = a + p * step
let (aa, bb) = forward_pair(data[a], data[b], small)
data[a] = aa
data[b] = bb
x += p2
p = p2
struct Writer:
var out: Buffer*
var pending: u32
var count: usize
var bits: usize
func put(value: u64, count: usize) -> !:
self.bits += count
var n = count
while n > 0:
n -= 1
self.pending = (self.pending << 1) | (u32)((value >> n) & 1)
self.count += 1
if self.count == 8:
try self.out.byte((u8)self.pending)
self.count = 0
self.pending = 0
func flush() -> !:
if self.count > 0:
try self.out.byte((u8)(self.pending << (8 - self.count)))
self.count = 0
self.pending = 0
## Fixed-length canonical Huffman codes over the used wavelet alphabet, with
## repeat codes. Size fallback is handled by EXR; the stream is standard PIZ.
pub func encode(image: const Raster*, chunk: Chunk, order: const usize[], data: const u8[], out: Buffer*) -> !:
let words = try new u16[data.length // 2] in memory.heap
defer free(words) in memory.heap
var reader = Reader(data = data)
var bitmap: u8[8192]
for y in 0..<chunk.height:
var base: usize = 0
for c in order:
let step: usize = 1 if image.channels[c].kind == .float16 else 2
for x in 0..<chunk.width * step:
let value = (u16)(try reader.uint(2))
words[base + y * chunk.width * step + x] = value
bitmap[(usize)(value >> 3)] |= (u8)1 << (value & 7)
base += chunk.width * chunk.height * step
bitmap[0] &= 254
let lut = try new u16[65536] in memory.heap
defer free(lut) in memory.heap
var count: usize = 0
for i in 0..<(usize)65536:
if i == 0 or (bitmap[i >> 3] & ((u8)1 << (i & 7))) != 0:
lut[i] = (u16)count
count += 1
var minimum: usize = 8191
var maximum: usize = 0
for i in 0..<bitmap.length:
if bitmap[i] != 0:
minimum = i if i < minimum else minimum
maximum = i
try out.uint((u64)minimum, 2)
try out.uint((u64)maximum, 2)
if minimum <= maximum:
try out.put(bitmap[minimum..<maximum + 1])
for i in 0..<words.length:
words[i] = lut[(usize)words[i]]
var base: usize = 0
for c in order:
let step: usize = 1 if image.channels[c].kind == .float16 else 2
for j in 0..<step:
forward_wavelet(words, base + j, chunk.width, chunk.height, step, count <= 16384)
base += chunk.width * chunk.height * step
let codes = try new u32[65537] in memory.heap
defer free(codes) in memory.heap
var used: usize = 0
var first: usize = 65536
var last: usize = 0
for value in words:
let index = (usize)value
if codes[index] == 0:
codes[index] = 1
used += 1
first = index if index < first else first
last = index if index > last else last
last += 1
codes[last] = 1
used += 1
var width: usize = 1
while ((usize)1 << width) < used:
width += 1
var table = Buffer()
defer table.close()
var table_bits = Writer(out = &table)
var code: u32 = 0
var i = first
while i <= last:
if codes[i] != 0:
codes[i] = code + 1
code += 1
try table_bits.put((u64)width, 6)
i += 1
else:
var run: usize = 1
while run < 261 and i + run <= last and codes[i + run] == 0:
run += 1
if run >= 6:
try table_bits.put(63, 6)
try table_bits.put((u64)(run - 6), 8)
elif run >= 2:
try table_bits.put((u64)(run + 57), 6)
else:
try table_bits.put(0, 6)
i += run
try table_bits.flush()
var encoded = Buffer(maximum = out.maximum)
defer encoded.close()
var bits = Writer(out = &encoded)
i = 0
while i < words.length:
let value = (usize)words[i]
try bits.put((u64)(codes[value] - 1), width)
i += 1
var run: usize = 0
while run < 255 and i + run < words.length and (usize)words[i + run] == value:
run += 1
if run * width > width + 8:
try bits.put((u64)(codes[last] - 1), width)
try bits.put((u64)run, 8)
i += run
try bits.flush()
try out.uint((u64)(20 + table.used + encoded.used), 4)
try out.uint((u64)first, 4)
try out.uint((u64)last, 4)
try out.uint((u64)table.used, 4)
try out.uint((u64)bits.bits, 4)
try out.uint(0, 4)
try out.put(table.view())
try out.put(encoded.view())