Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2197

random formats: BTLZA (LZ77+Arithmetic), BTIC1C (video codec) status, ...

Show all headers | View raw

(re-attempt at sending)


recently designed and (mostly) implemented this:
http://cr88192.dyndns.org:8080/wiki/index.php/BTLZA

basically, it is intended as a "Deflate alternative" for a few use-cases 
of mine (such as my BTIC family of video codecs), the main goal being to 
improve compression without (too severely) hurting decode speeds.

its design is basically as an extended form of Deflate with a few 
extensions:
support for larger matches (currently up to 64kB);
support for larger sliding window (theoretically up to 4GB, currently 
hard-coded in the encoder at 256KiB);
an optional arithmetic coder stage (*).


the decoder is also binary backwards compatible with Deflate, and most 
structural changes to the bitstream have been "fairly modest".

it was partly an extension/outgrowth of a prior strategy, namely feeding 
Deflated data through an arithmetic coder, but in this case, merges them 
together into a single bitstream format. (mostly after noting Deflate+AC 
to be "basically usable", and figured I would expand on it slightly, and 
a larger window and similar would be nice, ...).

it has mostly been designed/implemented over the past several days.

actually, this is the second iteration of the design, I had designed and 
largely implemented a prior version, but it quickly developed nasty 
levels of cruft, and was largely redesigned.


*: it uses a bit-at-a-time arithmetic coder which is applied after 
Huffman encoding the symbols and similar (the Huffman codes and 
extra-bits and similar are just sort of fed through the arithmetic coder 
fairly directly, rather than using multiple passes).

the Huffman coding is used mostly to reduce the number of bits that need 
to be fed through the arithmetic coder (helps with speed, less certain 
about compression effects).

there are currently 2 major modes here:
Arithmetic Mode A, which basically feeds the bits through the arithmetic 
coder with a single global context model (doesn't differentiate bits);
Arithmetic Mode B, which uses several different models for different 
types of bits, but is a bit slower and more expensive at present (and is 
not fully implemented).

most testing thus far has been in mode A.


a quick test, although it does hurt decode performance somewhat, video 
decoding (with my BTIC1C codec, DXTn route) remains at around 145-200 
megapixels per second while using the arithmetic coder (sufficient for 
720p and 1080p, vs about 400 Mpix/sec with the plain Huffman variant).

(note: BTIC1C uses Deflate, or now BTLZA, as its backend encoder).

I am less certain, but this may be potentially more due to the larger 
window size than due to the arithmetic (there was a compression boost 
seen when still using the plain-Huffman variant, though the AC does 
still seem to offer a minor improvement, ~ 10-15%).


I had noticed when debugging that while there are large numbers of 
matches with short runs and distances, there are occasional matches with 
much larger distances and match lengths, ...


here is with the video codec I am using the new backend to compress:
http://cr88192.dyndns.org:8080/wiki/index.php/BTIC1C

compression is improved somewhat, with it able to give passably good 
video quality at around 0.19 bpp. though the size/quality is still a bit 
weak vs H.264, at least I am partly getting outside of "comically bad" 
territory, with videos ~ 1.5x-2x larger than the H.264 input videos 
(generally off of YouTube), and not "drastically worse" video quality.

note, turning down the quality, it is possible to get below 0.1 bpp, but 
as-is, this is still pretty much "looks like crap" territory (would need 
to get good image quality at ~ 0.06 bpp to be more competitive on this 
front with H.264).

in general, it seems to be compressing BTIC frames from around 
200-400KiB down to around 30-50KiB (vs around 50-80KiB for plain 
Deflate), where for example, the VQ pixel blocks would be 2MB, and the 
raw video frame pixels at about 8MB.

well, and nevermind issues like the current encoder still mostly using 
RGB555, as I haven't really finished with the work needed for directly 
using RGB23 or RGB31F (RGB23=RGB787+Pbit, RGB31F=3x10bit+Pbit with 
colors as a 10-bit minifloat).

though, ironically, RGB23 and 31F colors are partly available via the 
use of indexed colors (the indexed colors may use higher-depth colors in 
the palettes and use them intermixed with RGB555, seemingly with the 
encoder preferring RGB555 for I-frames and index-color for P-frames, 
likely due to some of the error-tolerance heuristics).

but, at least, doesn't seem to be doing too badly for a design that 
arguably "sucks pretty hard"...


though not directly useful for BTIC1C, one feature that was did come to 
mind as a possibility (undecided, it would add a lot of complexity and 
could probably make sense for a more specialized entropy backend) would 
be a special mode/meta-format to allow integer data (represented in a 
UTF-8 like format) to be recognized and encoded more efficiently using a 
VLC-scheme (and possibly also "vector packing", where a vector of 
numbers is recognized as being able to be encoded in a dense bit-packed 
format).

if implemented, the rule would still be that the integers decode to an 
equivalent pattern of bytes.

likely encoding in such a mode:
0x00-0x7F: treated as raw byte symbols;
0x80-0xBF: single byte integer (0..63 or -32..31);
0xC0-0xDF: two-byte integer (0..2047 or -1024..1023);
0xE0-0xEF: three-byte integer (0..65535, or -32768..32767);
0xF0-0xF7: four-byte integer (0..2M, ± 1M);
0xF8-0xFB: five-byte integer (0..64M, ± 32M);
0xFC-0xFD: six-byte integer (0..2G, ± 1G);
0xFE: seven-byte integer (0..64G, ± 32G);
0xFF: 9+ byte integers.

though, possibly, the encoder could limit matching to the 32-bit range, 
and not match over-long cases.

say, for example, we have a format making use of DCT or WHT or similar, 
it could dump a lot of its data into a byte buffer in a UTF-8 like 
format and encode it like this, rather than needing to drag along a 
bunch of code needed for a dedicated entropy-coder backend (IME, using 
normal Deflate or similar seems to do fairly weak here vs using a 
dedicated block-VLC).


thoughts?...

Back to comp.compression | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

random formats: BTLZA (LZ77+Arithmetic), BTIC1C (video codec) status, ... BGB <cr88192@hotmail.com> - 2014-01-18 02:12 -0600
  Re: random formats: BTLZA (LZ77+Arithmetic), BTIC1C (video codec) status, ... Jarek Duda <dudaj@interia.pl> - 2014-02-05 08:21 -0800
    Re: random formats: BTLZA (LZ77+Arithmetic), BTIC1C (video codec) status, ... BGB <cr88192@hotmail.com> - 2014-02-05 13:31 -0600

csiph-web