Dormant Last read · last published · next check
Read 5 days ago and current, but nothing has been published for 3 years.
In this series I described how to build a patcher that can make very good (near minimal size) "coarse grain" patches, and run near maximum possible speed (IO limited). Posts in the series : cbloom rants- Patcher Part 1 - Introduction with context and defining terminology and goals cbloom rants- Patcher Part 2 - Some Rolling Hashes cbloom rants- Patcher Part 3 - How rsync works cbloom rants-…
In the real world, a lot of the issues for making a very fast patcher are in the practical matters of parallelism and file IO, so let's dig into those a bit. I believe that it is bad practice to take unnecessarily slow algorithms and just throw them onto threads to make your program fast by using tons of threads. So first we tried to make the patcher algorithms as fast as possible on a single…
We have a scheme to cut our file into content-defined chunks . So let's use that to make a patcher. For each file, we can construct a "signature" analogous to the rsync signature (which is a hash of chunks of constant length at regular intervals). Our signature is all the CDC chunk locations, and then a hash of each chunk. We will use the hash to look up the contents of each chunk; it is not a…
Just for my own entertainment, a brief aside to prove some facts we used in the last post. After drawing N random numbers in [0,1] , the chance that the next number you draw is a new minimum is 1/(N+1) which is also equivalent to : The expectation (mean) of the min of N random numbers in [0,1] is 1/(N+1) this is important to us because it means the branch for the min changing in the core CDC loop…
The alternative to rsync-style patch generation is to use content-defined chunking (CDC). There's enough to say about CDC that I'll do a whole post just about finding the chunks and won't talk about patching specifically here. Content-defined chunking (CDC) is the idea of using the values of the bytes in the local area to choose where chunk boundaries go. By using only the values of the bytes, and…
rsync is not a patcher; it is a method for transmitting differences of data over a network connection. You can however build a patcher ("rdiff") on the rsync method, and that is commonly used, so I think it's useful to look at how it works, because it gives us a standard reference point. Because of its origin as a network transmission method, "rdiff" has limitations as a patcher which means it…
Let's go through some options for rolling hashes. By "rolling hash" I mean a hash that works on a finite window of bytes, and that window slides incrementally across a buffer. To compute a rolling hash efficiently, you may want be able to incrementally add new bytes to the hash and subtract out bytes as they leave the window (emphasis on "may"). We'll need two types of rolling hash in later…
I will descibe in this series the patcher that I wrote which is able to find "perfect" patches at full IO-bound speed; eg. 5 GB/s on current gen SSD's. (more on what "perfect" means exactly later). I wanted to sanity check some of the patch sizes I was seeing from other sources, so I wanted my own reference results to know what was possible. At first I didn't care about speed, I just wanted…
This is an attempt to survey possible reasonable options for float to int casts for data compression. As mentioned in the previous post ( Notes on float and multi-byte delta compression ), when we work with float data in compression, we usually need to reinterpret the bits to an integer so that we can do things like deltas in a way that is either lossless, or with intentional loss in a…
When attempting to encode and compress delta values that are larger than 1 byte, and then feeding them to a back-end compressor which inherently works on bytes, you need to transform them to make the larger integer values more friendly to the byte-based compressor. Say you have S16 or S32 values that have a mean around zero. For example maybe you started with U32 or F32 values and took deltas of…
In accordance with Epic Games required social media policy, I am disclosing that I am an employee of Epic Games and that all opinions expressed here are my own and do not reflect those of Epic blah blah blah.
I'm going to look at how the Alpha channel should be weighted vs the RGB components when measuring distortions in RGBA textures, when that RGBA texture is used for alpha blending. (aside: of course many RGBA 4-channel images are not actually using A for opacity in alpha blending and this discussion does not apply to those; if your RGBA image is really 4 scalar channels of the same type of signal…
I wrote before in Topics in Quantization for Games some general basics on quantization. We're going to continue from there, but focus just on the specific case : GPU convention quantization of n-bit unsigned values (UNORM). As noted before, there are two viable conventions for uniform linear quantizers; either "floor" quantization (with bias on reconstruct) or "round" quantization (bias on…
Oodle 2.9.0 is now out. The full changelog is : ## Release 2.9.0 - March 23, 2021 $* *fix* : OodleLZ_Compress had an encoder crash bug in the Optimal level encodes on data in sizes just slightly over a 256KB chunk (eg. 262145) with a repeated substring at the very end $* *change* : Mac libs and dylibs are now fat binaries with x64 and ARM64 $* *change* : Tex : Oodle Texture no longer checks for…
The BWT (Burrows Wheeler Transform) has long fascinated people for its ability to capture complex correlations with a very simple inverse transform. Unfortunately despite that inverse transform being very simple, it is also slow. I will briefly review the inverse BWT (i-BWT) and then look at ways to speed it up. Jump to the end for the punch line : speed results and source code. Let's briefly…
Oodle Texture does rate-distortion optimization (RDO) BCN encoding, optimizing the BCN encoding for an R-D two axis score such that the size of the BCN texture after a following lossless compression is reduced while the distortion (difference from original) is not increased too much. One way to think about RDO conceptually is as rate allocation . Rate allocation is when an encoder intentionally…
Oodle 2.8.14 is out. The full changelog is at RAD . The highlights are : ## Release 2.8.14 - February 15, 2021 $* *enhancement* : BC7 encoding is faster ; slightly different encodings at higher speed with similar quality $* *new* : Mac ARM64 build now provided ; Mac example exes are fat x64+arm64 $* *new* : Apple tvOS build now provided $* *deprecation* : Mac 32 bit x86 build no longer provided…
AVIF is an image format derived from I-frames of AV1 video (similar to HEIC/HEIF from H265/HEVC). See also my 2014 Test of BPG , which is an H265 I-frame image format. Here are some links I've found on AVIF : AVIF image format supported by Cloudflare Image Resizing GitHub - AOMediaCodeclibavif libavif - Library for encoding and decoding .avif files GitHub - googlebrunsli Practical JPEG Repacker…
A couple of tips and tools for working with JPEG files. I use : jhead jpegcrop Of course you can use exiftool and jpegtran but these are rather simpler. 1. Strip all personal data before uploading images to the web. JPEG EXIF headers contain things like date shot and location. If you don't want Google to scrape that and use it to track your movements and send drones to follow you carrying…
Oodle 2.8.13 fixes an issue in Oodle Texture with consistency of encodings across machine architectures. We try to ensure that Oodle Texture creates the same encodings regardless of the machine you run on. So for example if you run on machines that have AVX2 or not, our optional AVX2 routines won't change the results, so you get binary identical encodings. We had a mistake that was causing some…
The Sony PS5 will have the fastest data loading ever available in a mass market consumer device, and we think it may be even better than you have previously heard. What makes that possible is a fast SSD, an excellent IO stack that is fully independent of the CPU, and the Kraken hardware decoder. Kraken compression acts as a multiplier for the IO speed and disk capacity, storing more games and…
I want to address some topics in quantization, with some specifics for games. We do "quantization" any time we take a high precision value (a floating point, or higher-bit integer) and store it in a smaller value. The quantized value has less precision. Dequantization takes you back to the space of the input and should be done to minimize the desired error function. I want to encourage you to…
Oodle Texture 2.8.11 adds support for RDO encoding of "BC1_WithTransparency" and BC2. We now support RDO encoding of all BC1-7 variants. In Oodle, "BC1_WithTransparency" doesn't necessarily mean that the texture has any 1-bit transparency. (for background: BC1 can encoding alpha values of 0 or 255 (1.0), which binary on/off alpha; when alpha is 0 the color is always 0 or black). It means that the…
Oodle Texture RDO can be used with any lossless back-end compressor. RDO does not itself make data smaller, it makes the data more compressible for the following lossless compressor, which you use for package compression. For example it works great with the hardware compressors in the PS5 and the Xbox Series X. I thought I'd have a look at how various options for the back end lossless compressor…
Oodle 2.8.9 is now shipping, with the aforementioned speed fix for large textures. Oodle Texture RDO is always going to be slower than non-RDO encoding, it simply has to do a lot more work. It has to search many possible encodings of the block to BCN, and then it has to evaluate those possible encodings for both R & D, and it has to use more sophisicated D functions, and it has to search for…