Here is a straightforward port of some easy code.

randtable.c has a lookup table with seemingly-random numbers. This table is used by the following macros in bzlib_private.h:

extern Int32 BZ2_rNums[512];

#define BZ_RAND_DECLS                          \
   Int32 rNToGo;                               \
   Int32 rTPos                                 \

#define BZ_RAND_INIT_MASK                      \
   s->rNToGo = 0;                              \
   s->rTPos  = 0                               \

#define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)

#define BZ_RAND_UPD_MASK                       \
   if (s->rNToGo == 0) {                       \
      s->rNToGo = BZ2_rNums[s->rTPos];         \
      s->rTPos++;                              \
      if (s->rTPos == 512) s->rTPos = 0;       \
   }                                           \
   s->rNToGo--;

Here, BZ_RAND_DECLS is used to declare two fields, rNToGo and rTPos, into two structs (1, 2). Both are similar to this:

typedef struct {
   ...
   Bool     blockRandomised;
   BZ_RAND_DECLS
   ...
} DState;

Then, the code that needs to initialize those fields calls BZ_RAND_INIT_MASK, which expands into code to set the two fields to zero.

At several points in the code, BZ_RAND_UPD_MASK gets called, which expands into code that updates the randomization state, or something like that, and uses BZ_RAND_MASK to get a useful value out of the randomization state.

I have no idea yet what the state is about, but let's port it directly.

Give things a name

It's interesting to see that no code except for those macros uses the fields rNToGo and rTPos, which are declared via BZ_RAND_DECLS. So, let's make up a type with a name for that. Since I have no better name for it, I shall call it just RandState. I added that type definition in the C code, and replaced the macro-which-creates-struct-fields with a RandState-typed field:

-#define BZ_RAND_DECLS                          \
-   Int32 rNToGo;                               \
-   Int32 rTPos                                 \
+typedef struct {
+   Int32 rNToGo;
+   Int32 rTPos;
+} RandState;

...

-      BZ_RAND_DECLS;
+      RandState rand;

Since the fields now live inside a sub-struct, I changed the other macros to use s->rand.rNToGo instead of s->rNToGo, and similarly for the other field.

Turn macros into functions

Now, three commits (1, 2, 3) to turn the macros BZ_RAND_INIT_MASK, BZ_RAND_MASK, and BZ_RAND_UPD_MASK into functions.

And now that the functions live in the same C source file as the lookup table they reference, the table can be made static const to avoid having it as read/write unshared data in the linked binary.

Premature optimization concern: doesn't de-inlining those macros cause performance problems? At first, we will get the added overhead from a function call. When the whole code is ported to Rust, the Rust compiler will probably be able to figure out that those tiny functions can be inlined (or we can #[inline] them by hand if we have proof, or if we have more hubris than faith in LLVM).

Port functions and table to Rust

The functions are so tiny, and the table so cut-and-pasteable, that it's easy to port them to Rust in a single shot:

#[no_mangle]
pub unsafe extern "C" fn BZ2_rand_init() -> RandState {
    RandState {
        rNToGo: 0,
        rTPos: 0,
    }
}

#[no_mangle]
pub unsafe extern "C" fn BZ2_rand_mask(r: &RandState) -> i32 {
    if r.rNToGo == 1 {
        1
    } else {
        0
    }
}

#[no_mangle]
pub unsafe extern "C" fn BZ2_rand_update_mask(r: &mut RandState) {
    if r.rNToGo == 0 {
        r.rNToGo = RAND_TABLE[r.rTPos as usize];
        r.rTPos += 1;
        if r.rTPos == 512 {
            r.rTPos = 0;
        }
    }
    r.rNToGo -= 1;
}

Also, we define the RandState type as a Rust struct with a C-compatible representation, so it will have the same layout in memory as the C struct. This is what allows us to have a RandState in the C struct, while in reality the C code doesn't access it directly; it is just used as a struct field.

// Keep this in sync with bzlib_private.h:
#[repr(C)]
pub struct RandState {
    rNToGo: i32,
    rTPos: i32,
}

See the commit for the corresponding extern declarations in bzlib_private.h. With those functions and the table ported to Rust, we can remove randtable.c. Yay!

A few cleanups

After moving to another house one throws away useless boxes; we have to do some cleanup in the Rust code after the initial port, too.

Rust prefers snake_case fields rather than camelCase ones, and I agree. I renamed the fields to n_to_go and table_pos.

Then, I discovered that the EState struct doesn't actually use the fields for the randomization state. I just removed them.

Exegesis

What is that randomization state all about?

And why does DState (the struct used during decompression) need the randomization state, but EState (used during compression) doesn't need it?

I found this interesting comment:

      /*-- 
         Now a single bit indicating (non-)randomisation. 
         As of version 0.9.5, we use a better sorting algorithm
         which makes randomisation unnecessary.  So always set
         the randomised bit to 'no'.  Of course, the decoder
         still needs to be able to handle randomised blocks
         so as to maintain backwards compatibility with
         older versions of bzip2.
      --*/
      bsW(s,1,0);

Okay! So compression no longer uses randomization, but decompression has to support files which were compressed with randomization. Here, bsW(s,1,0) always writes a 0 bit to the file.

However, the decompression code actually reads the blockRandomised bit from the file so that it can see whether it is dealing with an old-format file:

GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);

Later in the code, this s->blockRandomised field gets consulted; if the bit is on, the code calls BZ2_rand_update_mask() and friends as appropriate. If one is using files compressed with Bzip2 0.9.5 or later, those randomization functions are not even called.

Talk about preserving compatibility with the past.

Explanation, or building my headcanon

Bzip2's compression starts by running a Burrows-Wheeler Transform on a block of data to compress, which is a wonderful algorithm that I'm trying to fully understand. Part of the BWT involves sorting all the string rotations of the block in question.

Per the comment I cited, really old versions of bzip2 used a randomization helper to make sorting perform well in extreme cases, but not-so-old versions fixed this.

This explains why the decompression struct DState has a blockRandomised bit, but the compression struct EState doesn't need one. The fields that the original macro was pasting into EState were just a vestige from 1999, which is when Bzip2 0.9.5 was released.

What is Bedrock Linux?

From their website:

Bedrock Linux is a meta Linux distribution which allows users to utilize features from other, typically mutually exclusive distributions. Essentially, users can mix-and-match components as desired. For example, one could have:

• The bulk of the system from an old/stable distribution such as CentOS or Debian.
• Access to cutting-edge packages from Arch Linux.
• Access to Arch’s AUR.
• The ability to automate compiling packages with Gentoo’s portage
• Library compatibility with Ubuntu, such as for desktop-oriented proprietary software.
• Library compatibility with CentOS, such as for workstation/server oriented proprietary software.

All at the same time, all working together like one, largely cohesive operating system.

So, what is this thing? Bedrock Linux is a package manager compatibility overlay. Ever wanted to use CentOS or Arch packages on your Debian system? Bedrock Linux will let you do that.

Strata

A stratos in Bedrock Linux is a package management overlay. For example, if you want to add a CentOS Strata, you run:

$ sudo brl fetch centos

The BRL app will then download yum and it’s required apps and libraries into the overlay. Once it’s done you can then yum install whatever you want.

Have multiple versions of the same package? Use:

$ strat [stratus name] [packagename]

For example with the Nano editor:

tux@debian:~$ strat arch nano -V
GNU nano, version 4.2
(C) 1999-2011, 2013-2019 Free Software Foundation, Inc.
(C) 2014-2019 the contributors to nano
Email: nano@nano-editor.org Web: https://nano-editor.org/
Compiled options: --enable-utf8
tux@debian:~$ strat debian nano -V
GNU nano, version 2.7.4
(C) 1999..2016 Free Software Foundation, Inc.
(C) 2014..2016 the contributors to nano
Email: nano@nano-editor.org Web: https://nano-editor.org/
Compiled options: --disable-libmagic --disable-wrapping-as-root --enable-utf8
tux@debian:~$ strat centos nano -V
GNU nano version 2.3.1 (compiled 04:47:52, Jun 10 2014)
(C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
2008, 2009 Free Software Foundation, Inc.
Email: nano@nano-editor.org Web: http://www.nano-editor.org/
Compiled options: --enable-color --enable-extra --enable-multibuffer --enable-nanorc --enable-utf8

There are problems

It’s not as easy as it sounds. In order to install Bedrock Linux, you must have a compatible base OS. Here is the list that’s currently on the website:

Hijack-able distros are suitable base installations. Fetch-able distros can be used as overlays.

However this isn’t entirely true or at least not up to date. My first attempt was with OpenSUSE Tumbleweed. After installing, it failed to boot. My second attempt was with Fedora 30. Same resume. It worked on the third try with vanilla Debian. Finally, while Fedora is listed as fetch-able, I couldn’t install it because the brl application couldn’t find a suitable mirror.

Should I give it a try?

Yes! It’s a very interesting project, but don’t do it on any machine where you need your data to be protected. A spare VM is the ideal platform until it becomes more stable.

There is a lot of activity in the bzip2 repository!

Perhaps the most exciting thing is that Dylan Baker made a merge request to add Meson as a build system for bzip2; this is merged now into the master branch.

The current status is this:

• Both Meson and Autotools are supported.
• We have CI runs for both build systems.

A plea for help: add CI runners for other platforms!

Do you use *BSD / Windows / Solaris / etc. and know how to make Gitlab's CI work for them?

The only runners we have now for bzip2 are for well-known Linux distros. I would really like to keep bzip2 working on non-Linux platforms. If you know how to make Gitlab CI runners for other systems, please send a merge request!

Why two build systems?

Mainly uncertainty on my part. I haven't used Meson extensively; people tell me that it works better than Autotools out of the box for Windows.

Bzip2 runs on all sorts of ancient systems, and I don't know whether Meson or Autotools will be a better fit for them. Time will tell. Hopefully in the future we can have only a single supported build system for bzip2.

I have just done a git push --force-with-lease to bzip2's master branch, which means that if you had a previous clone of this repository, you'll have to re-fetch it and rebase any changes you may have on top.

I apologize for the inconvenience!

But I have a good excuse: Julian Seward pointed me to a repository at sourceware where Mark Wielaard reconstructed a commit history for bzip2, based on the historical tarballs starting from bzip2-0.1. Bzip2 was never maintained under revision control, so the reconstructed repository should be used mostly for historical reference (go look for bzip2.exe in the initial commit!).

I have rebased all the post-1.0.6 commits on top of Mark's repository; this is what is in the master branch now.

There is a new rustify branch as well, based on master, which is where I will do the gradual port to Rust.

I foresee no other force-pushes to the master branch in the future. Apologies again if this disrupts your workflow.

Update: Someone did another reconstruction. If they weave the histories together, I'll do another force-push, the very last one, I promise. If you send merge requests, I'll rebase them myself if that happens.

Today I had a very pleasant conversation with Julian Seward, of bzip2 and Valgrind fame. Julian has kindly agreed to cede the maintainership of bzip2 to me.

Bzip2 has not had a release since 2010. In the meantime, Linux distros have accumulated a number of bug/security fixes for it. Seemingly every distributor of bzip2 patches its build system. The documentation generation step is a bit creaky. There is no source control repository, nor bug tracker. I hope to fix these things gradually.

This is the new repository for bzip2.

Ways in which you can immediately help by submitting merge requests:

• Look at the issues; currently they are around auto-generating the version number.

• Create a basic continuous integration pipeline that at least builds the code and runs the tests.

• Test the autotools setup, courtesy of Stanislav Brabec, and improve it as you see fit.

The rustification will happen in a separate branch for now, at least until the Autotools setup settles down.

I hope to have a 1.0.7 release soon, but this really needs your help. Let's revive this awesome little project.

I am using openSUSE Leap 15.0 since beta even in production environments because it proved to be a rock-solid and stable enterprise class OS. With openSUSE Leap 15.1 we now got the SUSE Enterprise Linux 15 Service Pack 1 updates in openSUSE Leap. We will walk through my experience with openSUSE Leap 15.0 and how I updated it to Leap 15.1 on all my machines.

My openSUSE Leap 15.0 experience

Everything started with Fedora 28 and an update that went wrong. Well, to be precise, the update was s...