dymokomi/luce-compress
Source of release 0.9.0
## Large whole buffers on several threads, as pigz splits them: deflated in
## independent 1 MiB segments (each with a fresh window, ended by a sync
## flush, the last by a final block) joined into one zlib stream with the
## segments' Adler-32s combined, which any inflater reads; and inflated the
## same way when a stream's sync flushes mark exactly such segments, which
## is checked (each segment's size, its end at the next, the Adler-32) with
## a fallback to one thread for any other stream. The segment size is fixed,
## so the bytes do not depend on the machine.
import memory
import os
import thread
import flate
pub let segment_bytes: usize = 1048576
## Buffers larger than this go on several threads.
pub let parallel_above: usize = 2097152
## One segment's work: its input, where its output goes, what it made.
struct Piece:
var start: usize
var end: usize
var out: u8[]
var used: usize
var produced: usize
var adler: u32
var failed: bool
struct Work:
var input: const u8[]
var output: u8[]
var pieces: Piece[]
var level: i32
## `entry(context, index)` for every index below `count`, on this thread and
## up to (processors - 1) more; a thread that cannot start leaves its share
## to the others.
struct Crew:
var next: @usize
var count: usize = 0
var entry: func(void*?, usize) -> unit = skip
var context: void*? = none
func skip(context: void*?, index: usize):
_ = context
_ = index
func crew_loop(context: void*?):
let crew = (Crew*)(context else return)
while true:
let index = crew.next.add(1, .relaxed)
if index >= crew.count: return
crew.entry(crew.context, index)
func run(count: usize, entry: func(void*?, usize) -> unit, context: void*?):
var crew = Crew()
crew.next.store(0, .relaxed)
crew.count = count
crew.entry = entry
crew.context = context
var handles: thread.Handle[63]
var started: usize = 0
let wanted = (usize)os.cpus()
let helpers = (count if count < wanted else wanted) -| 1
while started < helpers and started < handles.length:
handles[started] = thread.spawn(crew_loop, (void*)&crew, 0, "luce-compress") catch failure:
_ = failure
break
started += 1
crew_loop((void*)&crew)
for at in 0..<started:
handles[at].join() catch failure: _ = failure
func deflate_piece(context: void*?, index: usize):
let work = (Work*)(context else return)
let piece = &work.pieces[index]
let slice = work.input[piece.start..<piece.end]
piece.out = new u8[flate.deflate_bound(slice.length)] --- in memory.heap catch failure:
_ = failure
piece.failed = true
recover empty()
if piece.failed: return
piece.used = flate.deflate_raw(slice, work.level, piece.out, piece.end == work.input.length) catch failure:
_ = failure
piece.failed = true
recover 0
piece.adler = flate.adler32(slice)
## `data` (over `parallel_above` bytes) as a zlib stream at `level`, its
## segments deflated in parallel; on memory.heap, the caller frees it.
pub func deflate(data: const u8[], level: i32) -> u8[]!:
let count = (data.length + segment_bytes - 1) // segment_bytes
let pieces = try new Piece[count] --- in memory.heap
for at in 0..<count:
let start = at * segment_bytes
pieces[at] = Piece(start = start, end = start + segment_bytes if data.length - start > segment_bytes else data.length, out = empty(), used = 0, produced = 0, adler = 1, failed = false)
defer release(pieces)
var work = Work(input = data, output = empty(), pieces = pieces, level = level)
run(count, deflate_piece, (void*)&work)
var total: usize = 6
for piece in pieces:
if piece.failed: error(memory.exhausted, "out of memory deflating a segment")
total += piece.used
let out = try new u8[total] --- in memory.heap
let header = flate.zlib_header(level)
out[0] = header[0]
out[1] = header[1]
var at: usize = 2
var adler: u32 = 1
for index in 0..<count:
let piece = &pieces[index]
memory.copy(out[at..], piece.out[..<piece.used], piece.used)
at += piece.used
adler = piece.adler if index == 0 else flate.adler32_combine(adler, piece.adler, piece.end - piece.start)
out[at] = (u8)(adler >> 24)
out[at + 1] = (u8)(adler >> 16)
out[at + 2] = (u8)(adler >> 8)
out[at + 3] = (u8)adler
return out
func release(pieces: Piece[]):
for piece in pieces:
if piece.out.length > 0: free(piece.out) in memory.heap
free(pieces) in memory.heap
func empty() -> u8[]:
var none_yet: u8[]
return none_yet
## Where a zlib stream's payload has sync flushes (`00 00 FF FF`): the
## offsets just after each, in order, into `starts` (as room allows); the
## count, stopping past `most`. Words with no 0xFF byte are skipped eight
## bytes at a time.
func scan(data: const u8[], most: usize, starts: usize[]) -> usize:
if data.length < 10: return 0
let end = data.length - 4
var found: usize = 0
var at: usize = 2
let ones: u64 = 0x0101010101010101
let highs: u64 = 0x8080808080808080
while at + 8 <= end:
let inverted = ~memory.read[u64]((void*)&data[at])
# A zero byte of ~word is a 0xFF byte of the word.
if ((inverted -% ones) & ~inverted & highs) == 0:
at += 8
continue
for k in 0..<(usize)8:
let p = at + k
if p >= 4 and p + 2 <= end and data[p] == 255 and data[p + 1] == 255 and data[p - 1] == 0 and data[p - 2] == 0:
if found < starts.length: starts[found] = p + 2
found += 1
if found > most: return found
at += 8
# The tail, byte by byte.
var p = (at if at > 4 else 4)
while p + 2 <= end:
if data[p] == 255 and data[p + 1] == 255 and data[p - 1] == 0 and data[p - 2] == 0:
if found < starts.length: starts[found] = p + 2
found += 1
if found > most: return found
p += 1
return found
## How many sync flushes (`00 00 FF FF`) a zlib stream's payload holds, up
## to `most + 1`.
pub func markers(data: const u8[], most: usize = 65536) -> usize:
var none_yet: usize[]
return scan(data, most, none_yet)
## Where the segments of a zlib stream (`data`, header and Adler-32
## included) start in its DEFLATE payload: after each sync flush; at most
## `most` of them, else none (not such a stream).
func boundaries(data: const u8[], most: usize) -> usize[]?!:
let starts = try new usize[most + 1] --- in memory.heap
let found = scan(data, most, starts)
if found > most:
free(starts) in memory.heap
return none
let exact = try new usize[found] --- in memory.heap
memory.copy(exact, starts[..<found], found)
free(starts) in memory.heap
return exact
func inflate_piece(context: void*?, index: usize):
let work = (Work*)(context else return)
let piece = &work.pieces[index]
let limit = (index + 1) * segment_bytes
let room = work.output[index * segment_bytes..<(limit if limit < work.output.length else work.output.length)]
let (used, produced) = flate.inflate_raw_bounded(work.input[piece.start..<piece.end], room) catch failure:
_ = failure
piece.failed = true
recover (0, 0)
if piece.failed: return
piece.used = used
piece.produced = produced
piece.adler = flate.adler32(room[..<produced])
## Inflate `data`, a zlib stream, into `output` (room for the whole result)
## on several threads when its sync flushes mark 1 MiB segments: the bytes
## made, or none when the stream is not so split (or does not check out),
## for a one-thread inflate to decide. With `exact`, the result must fill
## `output`.
pub func inflate(data: const u8[], output: u8[], exact: bool) -> usize?!:
if data.length < 10 or output.length <= parallel_above: return none
let most = (output.length + segment_bytes - 1) // segment_bytes - 1
let starts = (try boundaries(data, most)) else return none
defer free(starts) in memory.heap
if starts.length == 0 or (exact and starts.length != most): return none
let count = starts.length + 1
let pieces = try new Piece[count] --- in memory.heap
defer release(pieces)
for at in 0..<count:
let start = 2 if at == 0 else starts[at - 1]
pieces[at] = Piece(start = start, end = starts[at] if at < starts.length else data.length - 4, out = empty(), used = 0, produced = 0, adler = 1, failed = false)
var work = Work(input = data, output = output, pieces = pieces, level = 0)
run(count, inflate_piece, (void*)&work)
# Every segment whole and ending where the next starts; the last may be
# short; the Adler-32 of all of it the stream's.
var total: usize = 0
var adler: u32 = 1
for index in 0..<count:
let piece = pieces[index]
if piece.failed or piece.used != piece.end - piece.start: return none
if index + 1 < count and piece.produced != segment_bytes: return none
adler = piece.adler if index == 0 else flate.adler32_combine(adler, piece.adler, piece.produced)
total += piece.produced
if exact and total != output.length: return none
let at = data.length - 4
let stored = ((u32)data[at] << 24) | ((u32)data[at + 1] << 16) | ((u32)data[at + 2] << 8) | (u32)data[at + 3]
if stored != adler: return none
return total