Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-jpeg

Source of release 0.10.0

0.10.0 / src / jpeg / idct.lucb

#==============================================================================================
#
#   jpeg/idct - The exact separable IDCT, full size and DCT-scaled
#
#   DESCRIPTION:
#       The inverse DCT in f64, rows then columns, with exact cosines: at full size
#       f(x) = sum_k c(k)/2 F(k) cos((2x+1)k pi/16), c(0) = 1/sqrt 2, rounded to the
#       nearest sample and clamped. Zero coefficients and all-zero rows are skipped,
#       which only omits additions of zero, so results do not depend on the skipping.
#
#       A scaled IDCT gives N < 8 points a block, each the mean of the 8 / N full-size
#       points it covers before rounding: a box-filtered reduction, as libjpeg's
#       reduced IDCTs compute in fixed point. Averaging the cosines first keeps it one
#       separable transform of the same coefficients: N = 1 is the block's DC.
#
#==============================================================================================

## Cosines for N = 1, 2, 4 and 8 points: table `level` (0..3, N = 1 << level)
## holds c(k) times the mean of cos((2n+1)k pi/16) over the 8 / N full-size points
## n that point x covers, at [level * 64 + x * 8 + k], and transposed at
## [level * 64 + k * 8 + x] in `by_frequency`. N = 8 is the plain full-size table.
struct Cosines:
    var table: f64[256]
    var by_frequency: f64[256]

    static func make() -> Cosines:
        var result = Cosines()
        for level in 0..<(usize)4:
            let n = (usize)1 << level
            let span = 8 // n
            for x in 0..<n:
                for k in 0..<(usize)8:
                    let weight = 0.7071067811865476 if k == 0 else 1.0
                    var value = math.cos((f64)((2 * x + 1) * k) * 3.141592653589793 / 16.0) * weight
                    if span > 1:
                        var sum = 0.0
                        for j in 0..<span:
                            sum += math.cos((f64)((2 * (x * span + j) + 1) * k) * 3.141592653589793 / 16.0)
                        value = sum / (f64)span * weight
                        # Frequencies a box of this width cancels are exactly zero.
                        if math.abs(value) < 0.000000000001:
                            value = 0.0
                    result.table[level * 64 + x * 8 + k] = value
                    result.by_frequency[level * 64 + k * 8 + x] = value
        return result

## The table level of an N-point IDCT.
func cosine_level(n: usize) -> usize:
    return 0 if n == 1 else 1 if n == 2 else 2 if n == 4 else 3

## One block's coefficients, dequantized by `quant` (natural order), to an
## `nh` x `nw` tile at `out`, rows `stride` apart.
## `across` is the `nw`-point cosine table by frequency, `down` the `nh`-point
## table by position.
func idct_block(block: const i16*, quant: const f64*, across: const f64*, down: const f64*, nw: usize, nh: usize, out: u8*, stride: usize):
    # The nonzero coefficients of each row as a bit mask, which rows have any, and
    # whether any lies beyond the first column.
    var masks: u32[8] = ---
    var rows: u32 = 0
    var wide: u32 = 0
    for y in 0..<(usize)8:
        let words = (const u64*)(block + (y << 3))
        let mask = nonzero4(words[0]) | (nonzero4(words[1]) << 4)
        masks[y] = mask
        rows |= (u32)(mask != 0) << (u32)y
        wide |= mask
    if rows == 0:
        for y in 0..<nh:
            let line = out + y * stride
            for x in 0..<nw:
                line[x] = 128
        return
    # Rows: temp[y][x] = 1/2 sum_k F(y, k) cos_x(k), for nonzero rows only, summed
    # in k order. With only the first column the cosine, and so the row, is flat.
    var temp: f64[64] = ---
    let t = &temp[0]
    var left = rows
    while left != 0:
        let y = (usize)lowest_bit[left]
        left &= left - 1
        let row = block + (y << 3)
        let q = quant + (y << 3)
        let line = t + (y << 3)
        if wide <= 1:
            line[0] = (0.0 + ((f64)row[0] * q[0]) * across[0]) * 0.5
            continue
        if nw == 8:
            # Eight points, the full-size case, with the sums in registers.
            var s0 = 0.0
            var s1 = 0.0
            var s2 = 0.0
            var s3 = 0.0
            var s4 = 0.0
            var s5 = 0.0
            var s6 = 0.0
            var s7 = 0.0
            var terms = masks[y]
            while terms != 0:
                let k = (usize)lowest_bit[terms]
                terms &= terms - 1
                let a = (f64)row[k] * q[k]
                let basis = across + (k << 3)
                s0 = s0 + basis[0] * a
                s1 = s1 + basis[1] * a
                s2 = s2 + basis[2] * a
                s3 = s3 + basis[3] * a
                s4 = s4 + basis[4] * a
                s5 = s5 + basis[5] * a
                s6 = s6 + basis[6] * a
                s7 = s7 + basis[7] * a
            line[0] = s0 * 0.5
            line[1] = s1 * 0.5
            line[2] = s2 * 0.5
            line[3] = s3 * 0.5
            line[4] = s4 * 0.5
            line[5] = s5 * 0.5
            line[6] = s6 * 0.5
            line[7] = s7 * 0.5
            continue
        for x in 0..<nw:
            line[x] = 0.0
        var terms = masks[y]
        while terms != 0:
            let k = (usize)lowest_bit[terms]
            terms &= terms - 1
            let a = (f64)row[k] * q[k]
            let basis = across + (k << 3)
            for x in 0..<nw:
                line[x] = line[x] + basis[x] * a
        for x in 0..<nw:
            line[x] = line[x] * 0.5
    # Columns: out[y][x] = 1/2 sum_k temp[k][x] cos_y(k) + 128.
    if wide <= 1:
        # Every column alike: one value a row.
        for y in 0..<nh:
            let basis = down + (y << 3)
            var sum = 0.0
            var terms = rows
            while terms != 0:
                let k = (usize)lowest_bit[terms]
                terms &= terms - 1
                sum = sum + t[k << 3] * basis[k]
            let value = sample(sum)
            let line = out + y * stride
            for x in 0..<nw:
                line[x] = value
        return
    if rows == 1:
        # The first row only: cos_y(0) is the same for every y, so every row alike.
        let first = down[0]
        for x in 0..<nw:
            out[x] = sample(0.0 + t[x] * first)
        for y in 1..<nh:
            let line = out + y * stride
            for x in 0..<nw:
                line[x] = out[x]
        return
    if nw == 8:
        for y in 0..<nh:
            let basis = down + (y << 3)
            var s0 = 0.0
            var s1 = 0.0
            var s2 = 0.0
            var s3 = 0.0
            var s4 = 0.0
            var s5 = 0.0
            var s6 = 0.0
            var s7 = 0.0
            var terms = rows
            while terms != 0:
                let k = (usize)lowest_bit[terms]
                terms &= terms - 1
                let c = basis[k]
                let line = t + (k << 3)
                s0 = s0 + line[0] * c
                s1 = s1 + line[1] * c
                s2 = s2 + line[2] * c
                s3 = s3 + line[3] * c
                s4 = s4 + line[4] * c
                s5 = s5 + line[5] * c
                s6 = s6 + line[6] * c
                s7 = s7 + line[7] * c
            let line = out + y * stride
            line[0] = sample(s0)
            line[1] = sample(s1)
            line[2] = sample(s2)
            line[3] = sample(s3)
            line[4] = sample(s4)
            line[5] = sample(s5)
            line[6] = sample(s6)
            line[7] = sample(s7)
        return
    var sums: f64[8] = ---
    let acc = &sums[0]
    for y in 0..<nh:
        let basis = down + (y << 3)
        for x in 0..<nw:
            acc[x] = 0.0
        var terms = rows
        while terms != 0:
            let k = (usize)lowest_bit[terms]
            terms &= terms - 1
            let c = basis[k]
            let line = t + (k << 3)
            for x in 0..<nw:
                acc[x] = acc[x] + line[x] * c
        let line = out + y * stride
        for x in 0..<nw:
            line[x] = sample(acc[x])

## Which of four 16-bit lanes of `w` are nonzero, as bits 0..3.
inline func nonzero4(w: u64) -> u32:
    # Each lane's two bytes or'ed into its low byte; + 0xFF carries into bit 8 when
    # nonzero; the four carries gathered to bits 48..51 by one multiply.
    let low = (w | (w >> 8)) & 0x00FF00FF00FF00FF
    let carries = ((low + 0x00FF00FF00FF00FF) >> 8) & 0x0001000100010001
    return (u32)((carries *% 0x0001000200040008) >> 48) & 15

## The index of the lowest set bit of an 8-bit mask.
let lowest_bit: u8[256] = [0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0]

## A column sum to a sample: floor(sum / 2 + 128.5) clamped to 0..255.
inline func sample(sum: f64) -> u8:
    return floor8(sum * 0.5 + 128.5)

## 2^52 + 2^51: adding it to a float below 2^51 in magnitude leaves the nearest
## integer in the low bits of the result.
let magic: f64 = 6755399441055744.0

## floor(v) clamped to 0..255, for |v| < 2^50, without a float-to-integer call
## or a branch: the nearest integer, less one where that rounded up.
inline func floor8(v: f64) -> u8:
    let t = v + magic
    let n = (i64)(t.bits() -% 0x4338000000000000) -% (i64)(t - magic > v)
    let low = n & ~(n >> 63)
    return (u8)(low | ((255 -% low) >> 63))