Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-exr

Source of release 0.6.2

0.6.2 / src / piz.lucb

## 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())