From: Thomas Rast Date: Wed, 26 Jun 2013 23:12:45 GMT Subject: Re: [PATCH 09/16] documentation: add documentation for the bitmap format Message-ID: <87vc50lb4i.fsf@linux-k42r.v.cablecom.net> In-Reply-To: Vicent Martí writes: > On Tue, Jun 25, 2013 at 5:58 PM, Thomas Rast wrote: >> >> Please document the RLW format here. > > Har har. I was going to comment on your review of the Ewah patchset, > but might as well do it here: the only thing I know about Ewah bitmaps > is that they work. And I know this because I did extensive fuzz > testing of my C port. Unfortunately, the original Java code I ported > from has 0 comments, so any documentation here would have to be > reverse-engineered. I think the below would be a reasonable documentation, to be appended after your description of the EWAH format. Maybe Colby can correct me if I got anything wrong. You can basically read this off from the implementation of ewah_each_bit() and the helper functions it uses. -- 8< -- The compressed bitmap is stored in a form of run-length encoding, as follows. It consists of a concatenation of an arbitrary number of chunks. Each chunk consists of one or more 64-bit words H L_1 L_2 L_3 .... L_M H is called RLW (run length word). It consists of (from lower to higher order bits): - 1 bit: the repeated bit B - 32 bits: repetition count K (unsigned) - 31 bits: literal word count M (unsigned) The bitstream represented by the above chunk is then: - K repetitions of B - The bits stored in `L_1` through `L_M`. Within a word, bits at lower order come earlier in the stream than those at higher order. The next word after `L_M` (if any) must again be a RLW, for the next chunk. For efficient appending to the bitstream, the EWAH stores a format to the last RLW in the stream. -- Thomas Rast trast@{inf,student}.ethz.ch