09-04-12 - Encoding Values in Bytes Part 4

Just some random addenda. The main post series is here :

cbloom rants 09-02-12 - Encoding Values in Bytes Part 1
cbloom rants 09-02-12 - Encoding Values in Bytes Part 2
cbloom rants 09-02-12 - Encoding Values in Bytes Part 3

1. I mentioned prefix byte length codes in the first post. This is a code in which you first send the # of bytes using a bit prefix code, then the remainder. A small note on that :

Obviously you have unary :

1 + 7 bits
10 + 14 bits
110 + 21 bits
1110 + 28 bits

If the max you send is 4 bytes then we're actually wasting a bit on the last code; it should just be 111 + 29 bits :

1 + 7 bits
10 + 14 bits
110 + 21 bits
111 + 29 bits

and obviously you have the fixed two bit code :

00 + 6 bits
01 + 14 bits
10 + 22 bits
11 + 30 bits

what I didn't mention before is that for a max of 4 bytes these are the *only* prefix codes. All other prefix codes are just the xor of these or are strictly worse.

2. The unary prefix code is always nice, because it can be decoded branchlessly with countlz (BSF/BSR). (see for example Elias Gamma or Exp-Golomb coding).

The decoder for mod-128 (with the flag bits at the head, and little endian) is :

const uint32 mod128_mask[] = { (1UL<<7)-1, (1UL<<14)-1, (1UL<<21)-1, (1UL<<29)-1 };
const uint32 mod128_base[] = { 0, (1UL<<7)-1, ((1UL<<14)-1) + ((1UL<<7)-1), 
                                ((1UL<<21)-1) + ((1UL<<14)-1) + ((1UL<<7)-1) };

int DecodeMod128LEBranchless(U8PC & from)
{
    uint32 dw = *( (uint32 *) from );
    unsigned long index;
    _BitScanForward(&index,dw);
    index = MIN(index,3);
    int count = index+1;
    int shift = MIN(count,3);
    from += count;
    dw >>= shift;
    dw &= mod128_mask[index];
    dw += mod128_base[index];
    return (int) dw;
}

and the encoder is left as an exercise for the reader. (as is an endian-independent version)

The code above provides the maximum code space; it adds the base of each range and it doesn't waste a bit for the top range. Obviously it can be faster (no MIN's) if you do waste the bit.

3. I was playing with LZ4 offsets and it's an obvious place to use EncodeMod.

Say you have an existing LZ codec that writes offsets in 2 bytes. You want to leave it alone except for the offset IO.

You can add > 65536 offset support by changing the offset to EncodeMod.

One obvious scheme is : 0 + 15 bit offsets, 1 + 23 bit offsets. This is EncodeMod( 15 bits ) on the first word followed by a raw byte (EncodeMod(0)).

But that is not ideal; you want more of the offsets in the 32768 to 65536 range to get into the first 2 bytes. Well, just lower your mod. EncodeMod( 14 bits ) gives you up to (32768+16384) in the first 2 bytes, and 22 bits for longer offsets. EncodeMod( 13 bits ) gives you up to 57344 (65536-8192) in the first 2 bytes, and 21 bits for long offsets.

The next thing you could do is be able to send a few low offsets in just 1 byte. The most important one is actually just the RLE offset (offset=1). We do not want to use something like 1 bit + 7 bit payload, because that puts too many offsets in 1 byte and it takes away too much of our 2 byte range (we still want as many offsets as possible to be sent in 2 bytes). We can get that in using EncodeMod. Instead of outputing 2 bytes at first, we do 1 byte with a high mod - something like mod 254. This saves just a few values to fit in 1 byte and most of that byte range is left over for the second byte.

So to send an LZ offset you might do : mod 255 , mod 64, mod 0 ; then the thresholds are

1,48961,4226881

for 1-3 byte offset encoding.

(I don't suggest you actually do this for LZ offsets; it's intended as an example of the kind of thinking that goes into good code design).

4. File sizes are a common case for this, so I did a brute force optimize.

I gathered all the file sizes on my computer. (you may question whether my computer is a representative sample).

(BTW reminder to self : beware circular symbolic links in dir traversals these days; lots of old software that does dir traversals can infinite loop these days)

Anyhoo I tried mod byte-by-byte encoding and optimized the parameters for a 3-step series. The optimal was :

B-B-B-mod :
best : 251, 27, 15 : 1228288
cost per :  2.129383

you can see it has reserved a little space for tiny file sizes to go in 1 byte, then most go in 2 bytes, and not much space is reserved for the very large rare files.

More efficient is an encodemod which goes word-then-bytes , and uses only pow2 mods. The optimal for that is :

W-B-pow2
best : 13 , 4 : 1232113
cost per :  2.136096

only barely higher average cost. (13,4 are bit counts; eg. mods of 1<<13 and 1<<4)

Compare to a simple scheme I've used in the past :

write 16 bits if size < (1<<15) , else 32 bits, else 64 bits :

16-32-64 : cost per : 2.33855

this is not a great scheme and yet it's only slightly worse on average; clearly not a lot of win to be had on this front.

09-02-12 - Encoding Values in Bytes Part 3

Okay, now that we have some background we can bring together the two ends of the story : encoding variable length numbers, and encodings in bytes using variable ranges.

What we want to do should be obvious. We want to use some amount of range, like [0 , (T-1)] to send a value <= (T-1) immediately, and use the rest of the range [T, base-1] to send some part of a value that's >= T. (eg. base = 256 for bytewise encoding)

With our background this should be pretty obvious so I'll jump straight to the code. The trick is in the case that it doesn't all fit in the current byte, we'll use modulo to output part of the value in the space we're given.

First a recursive implementation which is more obviously symmetric between the encoder and decoder :

(In this implementation I put the "can send immediately" in the top part of the word, and I put the "here's part of the value but there's more to follow" in the bottom part of the word, which is the opposite of the description above).

typedef uint8 U8;
typedef uint8 * U8P;
typedef const uint8 * U8PC;

U8 * EncodeMod(U8 * to, int val, int mod)
{
    ASSERT( mod >= 1 && mod <= 255 );
    const int upper = 256 - mod;
    if ( val < upper )
    {
        *to++ = (U8)(mod + val);
        return to;
    }
    else
    {
        // val >= upper
        val -= upper;
        int top    = val / mod;
        int bottom = val % mod;
        *to++ = (U8)bottom;
        return EncodeMod(to,top,mod);
    }
}

int DecodeMod(U8PC & from, int mod)
{
    const int upper = 256 - mod;
    int byte = *from++;
    if ( byte >= mod )
    {
        return (byte - mod);
    }
    else
    {
        int val = DecodeMod(from,mod);
        val *= mod;
        val += byte + upper;
        return val;
    }
}

but of course you don't actually want to use recursive functions; the less obviously symmetric non-recursive implementation is :

U8 * EncodeMod(U8 * to, int val, int mod)
{
    ASSERT( mod >= 1 && mod <= 255 );
    const int upper = 256 - mod;
    for(;;)
    {
        
        if ( val < upper )
        {
            *to++ = (U8)(mod + val);
            return to;
        }
        else
        {
            // val >= upper
            val -= upper;
            int lower = val % mod;
            *to++ = (U8)lower;
            val /= mod;
        }
    }
}

int DecodeMod(U8PC & from, int mod)
{
    const int upper = 256 - mod;
    int mul = 1;
    int val = 0;
    for(;;)
    {
        int byte = *from++;
        if ( byte >= mod )
        {
            val += (byte - mod)*mul;
            break;
        }
        else
        {
            val += (byte+upper)*mul;
            mul *= mod;
        }
    }
    return val;
}

and furthermore in practice you probably don't want to eat the cost of the divide and modulo in the encoder (it's only a mul in the decoder, but still). So you can require that mod is a power of 2. The implementation is obvious :

U8 * EncodeModPow2(U8 * to, int val, int bits)
{
    ASSERT( bits >= 0 && bits < 8 );
    const int mod = (1<<bits);
    const int upper = 256 - mod;
    for(;;)
    {
        
        if ( val < upper )
        {
            *to++ = (U8)(mod + val);
            return to;
        }
        else
        {
            // val >= upper
            val -= upper;
            int lower = val & (mod-1);
            *to++ = (U8)lower;
            val >>= bits;
        }
    }
}

int DecodeModPow2(U8PC & from, int bits)
{
    const int mod = (1<<bits);
    const int upper = 256 - mod;
    int shift = 0;
    int val = 0;
    for(;;)
    {
        int byte = *from++;
        if ( byte >= mod )
        {
            val += (byte - mod)<<shift;
            return val;
        }
        else
        {
            val += (byte+upper)<<shift;
            shift += bits;
        }
    }
}

Now in all this code we're outputing a byte at a time, but of course you could start with 2 bytes, or go 1-1-2 or whatever.

EncodeMod is a superset of some of the previous encodings we've looked at.

For example, mod = 1 is a 1-1-1-1 flag value encoding. That is, we reserve only one value in the range to indicate more bytes follow.

mod = 128 is a unary flag-bit encoding (the 1 bit flag + 7 bit payload scheme).

(mod over 128 is valid but a weird thing to do (*!*). mod = 0 is send a byte. mod = 256 is send one byte from a multi-byte word; eg. to send a uint16 in 16 bits is encodemod 256 then encodemod 0 ).

In between EncodeMod can generate intermediate encodings. Here is a sampling of the values at which EncodeMod steps up to using the next # of bytes :

mod   1 : 255,510,765,1020,1275,1530,1785,2040,2295,
mod   2 : 254,762,1778,3810,7874,16002,32258,64770,129794,
mod   3 : 253,1012,3289,10120,30613,92092,276529,
mod   5 : 251,1506,7781,39156,196031,
mod   8 : 248,2232,18104,145080,
mod  13 : 243,3402,44469,578340,
mod  21 : 235,5170,108805,
mod  34 : 222,7770,264402,
mod  55 : 201,11256,619281,
mod  89 : 167,15030,1337837,
mod 144 : 112,16240,2338672,
mod 233 : 23,5382,1254029,

bits  0 : 255,510,765,1020,1275,1530,1785,2040,2295,
bits  1 : 254,762,1778,3810,7874,16002,32258,64770,129794,
bits  2 : 252,1260,5292,21420,85932,343980,
bits  3 : 248,2232,18104,145080,
bits  4 : 240,4080,65520,1048560,
bits  5 : 224,7392,236768,
bits  6 : 192,12480,798912,
bits  7 : 128,16512,2113664,

eg. mod = 1 (the old 1-1-1-1 encoding) sends values < 255 in 1 byte, < 510 in 2 bytes, etc. So for example at mod 13 we van only get up to 242 in 1 byte, but we can get a lot more in 2 bytes (< 3402).

EncodeMod is flexible but it cannot generate all possible variable length integer encodings in bytes. As a counterexample, if we try to reproduce the 2-flag-bits thresholds (0,0x40,0x4040,0x404040) the closest I can get with EncodeMod is to do mod 192, then 170, then 127, which gives thresholds of (0,0x40,0x40C0,0x408040). One of the differences here is that EncodeMod has no upper limit, it can encode infinite values (just like flag-value and unary-flag-bits encodings), but the fixed-number-of-flag bit (or finite length prefix code) type encodings do have an upper limit, so are not reserving any space for "there are still bigger values".

Finally, some charts showing the number of bytes required to send a value with various mods. The charts all show the same data, just at different zooms of the X axis. You should be able to see that low mod is best for small values, high mod is best for large values, and they cross somewhere in between. (the rightmost point is not the next byte step, it's a generated clip with the chart boundary; all the other points indicate a step up in the number of bytes output).

ADDENDUM : *!* : actually encodemod with a mod over the midpoint is totally useful and reasonable.

09-02-12 - Encoding Values in Bytes Part 2

A short post for a small concept : encoding using division of words into ranges.

If you're trying to put two different things in a byte (eg. in Part 1 we were putting either "the value fits in this byte and here it is" or "the value does not fit in this byte and here's a portion of it"), you can obviously use a flag bit.

eg. say you're trying to send either some number of apples (A's) or some number of bananas (B's) in a byte. You could send :

0 bit + 7 bits more = 7 bits of A's
1 bit + 7 bits more = 7 bits of B's

and you can write the decoder in a bit-twiddling manner :

{

    int byte = *ptr++;
    int isB   = byte & 0x80;
    int count = byte & 0x7F;

}

but you can also write the same decoder in a value-checking manner :

{
    int byte = *ptr++;

    if ( byte >= 128 )
    {
        isB = true;
        count = byte - 128;
    }
    else
    {
        isB = false;
        count = byte;
    }

}

(of course you should follow with a count++ in all cases unless you want to be able to send a count of 0)

But writing it in a value-checking manner makes it obvious that we don't need to put the divider in the middle. We could just as easily do :

{
    int byte = *ptr++;

    if ( byte >= 90 )
    {
        isB = true;
        count = byte - 90;
    }
    else
    {
        isB = false;
        count = byte;
    }

}

and now we have [0-89] for A's and [90-255] for B's ; this distribution may be better if your data is not symmetric.

To first approximation, the division point should be the probability of A's vs. B's ; eg. midpoint = P(A)*256. (this is not exactly right; it depends on the distribution of magnitudes of A's and B's ; plus there are some ugly quantization boundary effects, but it is roughly right).

Of course flag-value encodings that we saw last time are a special case of this with the divider shoved all the way to one end.

{
    int byte = *ptr++;

    if ( byte >= 255 )
    {
        isB = true;
        count = byte - 255;
    }
    else
    {
        isB = false;
        count = byte;
    }

}

and a "B" is something that doesn't fit in one byte.

Now this is obviously a kind of proto-arithmetic-coder. It doesn't carry left over range from one byte to the next, but it's trying to divide the output range of the current byte based on the probability of the symbol.

In particular for one simple case, it does exactly what you expect :

Say you have a random source of 0's and 1's (eg. bits) with some probability P0 of 0 (and 1-P0 of 1). You decide to encode them using RLE, that is you'll send a run length of either 0's or 1's. You want to put the run length in a byte (or nibble, or whatever). You can do it by sending a word which is broken into two ranges; one range for a run of 0's and another range for a run of 1's. Thusly :

EncodeRun( bool isRun0 , int runLen , int divider )
{
    ASSERT( runLen > 0 );

    if ( isRun0 )
    {
        // I get [0,divider-1] in the output

        for(;;)
        {
            if ( runLen <= divider )
            {
                *output++ = runLen-1;
                return;
            }
            else
            {
                *output++ = divider-1;
                runLen -= (divider-1);
                ASSERT( runLen >= 1 );
            }
        }
    }
    else
    {
        // I get [divider,base-1] in the output
        //  (eg. base = 256 for bytes, 16 for nibbles, etc.)

        int range = base-divider;

        for(;;)
        {
            if ( runLen <= range )
            {
                *output++ = divider + runLen-1;
                return;
            }
            else
            {
                *output++ = base-1; // divider + (range-1)
                runLen -= (range-1);
                ASSERT( runLen >= 1 );
            }
        }
    }
}

Note there's no flag for "doesn't fit in one byte" here; if we have more 0's than fit in one run, we just send another run of 0's following the first. eg. runs of 0's and 1's don't strictly alternate in this encoding.

Anyway, this encoder has just been a very concrete demonstration to get us to this statement :

For a random source with probability P0 of a 0, the optimal value of "divider" is divider = P0 * base. That is, you split the range proportional to the probability of each type of value.

(it may be either the floor or ceil of that float). (and it may not be true very close to the edges, eg. at divider=1 or base-2).

This was just an exercise to prove that our intuition is correct - the divider corresponds to the probability of each type of thing.

I'm sure that this technique has been well known to practitioners of the art forever. Back when LZRW was written, the tiniest last ounce of efficiency was needed, so the bit-packing approaches were preferred. With better CPU's now we can afford to do a branch or table lookup, which lets us put the divider away from the middle. So far as I know this technique was first used in a mainstream product in LZO (*). Recently Sean helped clarify my thinking about it.

In the next part we will bring together parts 1 and 2.

* = ADDENDUM : LZO uses this scheme to send a match or literal(s) in a byte. I don't recall the exact scheme in LZO, but say for example you wanted to send either a literal run len or a match length in an LZ encoder in a 4 bit nibble. You could send 1 bit for a match/literal flag, and then 3 bits of match len or literal run len. Instead, we now see that's equal to a threshold of 8, and we can put that threshold somewhere else to minimize our output. eg. it could be 10, then you have [0,9] for matches and [10,15] for literals.

In LZO the threshold is a constant, presumably tweaked over some test set, but other ideas are obvious. The threshold could be transmitted in the header of the file and the encoder could optimize it for the file in question. The threshold could also be dynamic, then you have an adaptive bytewise entropy coder of sorts. The adaptation schemes are obvious because as we have shown the threshold acts very much like a probability, so you can use the standard schemes that are known for binary arithmetic coders (eg. threshold += (threshold>>5) type of stuff, or rung-ladder, etc). (rung-ladder is a table-driven state machine, eg. threshold = table[state].threshold ; state = table[state].after_match and then optimize the tables somehow).

If I recall correctly, LZO also does some semi-arithmetic-codery stuff, in the sense that if not all of the range is needed to flag what you are currently sending, that value range can be carried over into a later encoding. Again, this not the exact LZO scheme but you could imagine a decoder that works like this : grab a nibble; a value in [0-11] is a match (with perhaps 1 bit of offset and the rest is match lengths), a value in [12-15] flags a literal; now obviously you don't need 4 values to send a single bit flag, so we keep (nibble-12) and add it to the next match length we decode.

ADDENDUM 2 : just to emphasize what I'm saying in the last paragraph because I think it's important.

When designing heuristic / bit-packing compression codes, you should *not* take the view point of "hey a literal flag takes 1 bit so I will allocate one bit of space for it".

What you should do is find the probability of events; (eg. literal vs. match); and allocate space in the code based on probability. Then, once you have done that, figure out a way to use the values in the code productively.

09-02-12 - Encoding Values in Bytes Part 1

A very basic level of data compression is just sending values in bytes. I'm gonna do a few posts on this topic, first some review.

A common case is you want to send some value which has a large max (or perhaps infinite or unknown max) but has a much lower mean. Obviously you don't want to just output all the bits/bytes needed for the max value all the time.

(to be quite concrete : one standard situation is transmitting a file size. A file size could take up to 64 bits but most file sizes fit in 16 bits. Sending 64 bits all the time is silly, you want some kind of variable length encoding that using 2 bytes when possible, then more if necessary. Of course because of Kraft inequality you will no longer be able to send a value of (2^64 -1) in 8 bytes, because you are compressing some of the values you must expand some)

Let's run through the standard ways to do this :

Flag Value Encodings

These reserve a flag value in the range to mean "more bytes follow". The most basic form is like :

{
    U8 *ptr; int value; // given

    while( value >= 255 )
    {
        value -= 255;
        *ptr++ = 255;
    }
    *ptr++ = value;
}

That is, we reserve one value in the byte (255) to be a flag meaning "more bytes follow". Values lower than 255 can be sent right away. If more bytes follow, we try again to just send it in one byte.

There are various other options for flag-value encodings. I like to name them by the number of bytes send in each step. So the example above is "1-1-1-1-..." encoding. (it's the "unary" of byte encoding; that is, 1-1-1-1 encoding sends small values in the fewest possible bytes, but it sends large values in the most possible bytes (of any prefix code)).

But there are other options : 1-2-4-8 (try to send just 1 byte, then try to send 2 bytes (flag value 65535), then try in 4), 1-1-2-3-4-5 , etc. (and you don't have to start with 1; for file sizes you might use 2-3-5-8 (though really for file sizes a flag bit encoding is probably better)).

In fact while the simplicity of 1-1-1-1 encoding is appealing, it's almost never the best way to go, because in the rare chance that you have some degenerate data with a very large value, it can expand a lot. (eg. to send 100,000 in 1-1-1-... encoding takes 393 bytes). Even if 1-1-1- is theoretically optimal on your data, you should use 1-1-1-2-4 or something like that to limit the maximum output in bad cases.

Here's the number of bytes sent for some flag value encodings :

  value :   1-1-1-1   1-1-2-3   1-2-3-4
    200 :         1         1         1
    400 :         2         2         3
    600 :         3         4         3
   1000 :         4         4         3
   1600 :         7         4         3
   2600 :        11         4         3
   4200 :        17         4         3
   6800 :        27         4         3
  11000 :        44         4         3
  17800 :        70         4         3
  28800 :       113         4         3
  46600 :       183         4         3
  75400 :       296         7         6

Flag Bit Encodings

The next very common method is a flag bit (or bits) to indicate more bytes follow. This lets you send large values in fewer bytes at the cost of sending small values in more bytes.

The flag bits can be sent with any prefix code (eg. Huffman, unary, etc) of course. Some common simple cases :

One flag bit at a time

(aka unary flag bits, or 7-bit words). You do this encoding thusly :

{
    U8 *ptr; int value; // given

    while( value >= 128 )
    {
        value -= 128;
        *ptr++ = value & 0x7F;
        value >>= 7;
    }
    *ptr++ = value;
}

To decode it, you check if the top bit of each byte is on. The top bit is being on means "more bytes follow". Whether or not the top bit is on, you always have 7 bits of payload to add to your value. That is, the encoding is like :

0     - 127      :  0 + 7 bits
128   - 16511    :  1 + 7 bits ; 0 + 7 bits    [or 10 + 14 bits]
16512 - 0x20407F :  1 + 7, 1 + 7, 0 + 7        [or 110 + 21 bits]

Another common case is :

N flag bits

In this case you just send a fixed number of flag bits; eg. 2 bits to 1-5 bytes. The encoding is :

0        - 63      : 00 + 6 bits
0x40     - 16447   : 01 + 6+8 bits
0x4040   - 4210751 : 10 + 6+8+8 bits
0x404040 - 1.078e9 : 11 + 6+8+8+8 bits

Now of course you can combine the two, and you can use the same kind of nomenclature as before, but this time referring to the number of flag bits ; eg. 1 flag bit, then 1 more, then 2, then 3. But as noted previously this is really just a prefix code for the number of bits.

Flag bit and flag value are really just two extremes of a related continuum, which we shall see in a later post.

09-01-12 - Good Computer Days

I was throwing out some old papers and found this :

It was really nice of them to include "/loc" (perhaps by accident?).

Man I miss the days when I was excited to explore a virtual world, and felt like nobody but me and the developer had seen it before, and I drew my own maps and wrote down notes of stuff I wanted to come back to later.

I feel like the internet has ruined that. Sure you could choose not to look on the net, but that's like choosing to enter a boxing ring with a blindfold on; everyone else has a massive massive advantage over you. Even in single player games it feels dumb to me; it's like people who hike up mountains when there's a tram or road up it; for me it totally ruins the hike if I get to the top and find a parking lot full of people who got there the easy way.

One of my favorites was the Amiga game "Dungeon Master" where you made spells by putting together these elemental symbols. You would find scrolls and clues in the game with combos that worked, but you could also sort of deduce them (they were semi-logical), and when you figured one out it was like an awesome eureka moment, and you wrote it down in your little scratch pad. Nowadays that kind of system can't even be in games at all because everyone would just look up all the combos right away (some dumb devs do still try to use this kind of system, but don't let you use a combo until you have unlocked it (by purchase or level up or whatever), which ruins all the joy from it and makes it quite pointless).

09-01-12 - LZP1.h

In my continuing STB-ificiation of old code, I did a single file header version of the original "LZP1" (this is "LZP1b" in the nomenclature of this recent LZP1 post ).

It's here : lzp1.h

As noted previously, this is no longer a good way to do fast data compression; it's too branchy, it doesn't take advantage of the large amount of RAM available, etc. This is mainly a historical curiosity.

This header was just ripped out of the LZP code that has long been available here, at cbloom.com .

One thing that has really struck me, being away from compression for a while and then coming back to it, is that so many of the new ideas are just old ideas that weren't practical at the time. When you're working on something, you have tons of ideas that you throw out because they take too much memory, or they're too slow, or whatever. But in 5-10 years those ideas will be good, and 5-10 years is not really that far away. If we were dick-heads we could have patented every idea that we ruled out because it was "not practical" at the moment.

(that's not to disparage the new ideas; what most people who are not practitioners of the dark arts don't realize is that the valuable contribution is almost always the tiny details that make something work; the general idea was probably obvious to researchers 20 years ago, they just didn't pursue it for whatever reason)

08-19-12 - Packages in Standard C

So we've talked about DLL's a few times and how fucked up they are. What you really want is something like a DLL that you can statically put in your app so it's not a separate file. We'll call this a "package". But I was reminded the other day that C libs are also fucked up.

Last week at RAD we discovered that some of our Xenon libs were several megabytes bigger than they need to be simply because we included "xtl.h" in a few files. What was happening was that xtl.h has a ton of inline functions in it, and the compiler goes ahead and compiles all of them and sticks them in your OBJ even if you don't use them (of course this is another problem with C that I'd like to see fixed - there's no need to waste all that time compiling functions that I don't use - but that's another rant).

Of course when you make a lib, all it does is cram together your obj's. It doesn't strip the uncalled functions (that's left to the linker, later on).

So DLL's are fucked and we wanted them to be "packages" ; and libs are also fucked and we want them to be packages too!

What I think a "package" in C should be :

• 1. You provide an explicit list of exports (perhaps by adding an __export decorator). Only exported symbols are accessible from outside the package. (you may also have some explicit imports if you are not a leaf package).

• 2. All internal references in the package are resolved at package build time. This lets you find "link errors" without having to make an exe that pulls in every obj in the lib to test for missing references.

  This also lets you strip all un-referenced and un-exported symbols.

• 3. LTCG or anything funny like that which is delayed to the link stage could be done on the package.

• 4. Symbols of the same name that are in different packages do not conflict. This is such a huge disaster in C and a source of very unpredictable and hard to deal with bugs. Just because some lib used a global "int x" and my lib uses a global "int x" doesn't mean I want them to be the same variable.

• 5. If your package uses some libs, they should (optionally) be linked into the package and made "private" not exported; that way multiple packages that use different variants of libs can be put together in one app without conflict.

So that's all background material. What this post is about is this : it occurs to me that you can get most of this in standard C by making your own "libpackager" tool.

libpackager should take a lib and output a lib. You have to also provide it a list of exports (or you could use some decorator that it can parse to mark the exports). It can parse the obj's in the lib and find all the symbols and do its own "link" step to eliminate unreferenced symbols, then remake the obj's without those symbols. So this gives us #2, which is a pretty big win.

You could also do #4 by having libpackager decorate all the internal symbol names that are neither import nor export. This is roughly equivalent to if you had put all your internal symbols in some namespace.

You could even do #5 ; make libpackage go and grab the libs you reference, stuff their obj's into your lib also. Then your copy of the lib and your references get name-decorated so they don't conflict with someone else. eg. say you want to make "oodle.lib" as a package and you use "radmemset" from "radutil.lib" , packager could grab radutil.lib and stuff it in; then since radmemset is now an internal reference, it gets changed to "oodlelib_radmemset". Now when you put "oodle.lib" and "bink.lib" both into your app, if they used different versions of radmemset, they will not cross-link because the libs have been made into fake "packages". (this step should be optional because sometimes you do want cross-links).

One annoying complication is that this doesn't work with the stdlib in a straightforward way. I would very much like to be able to "package" all references to stdlib in this way, but stdlib is not just a normal lib, it also has some special cheating connections to the crt0 startup code, so you can't just go and rename all its symbols to oodlelib_memset and such. Perhaps this could be resolved, which would be nice to avoid all those garbage problems that arise because some lib was built for libc and some other lib was built for libcmtd , etc.

I think this all is pretty straightforward (other than the stdlib issues). The only hard part is parsing the lib and obj formats on every platform and build variant that you need to support.

(BTW a bit of web searching indicates that the gcc tools on some platforms (Mac) provide some of this; there seems to be some special attributes for exports from libs and perhaps a lib tool that does dead strips; it's hard to follow gcc docs)

08-17-12 - Defines

In the category of "stuff everyone should know by now" : doing "#if" is much better than "#ifdef" for boolean toggles that you want to be able to set from the compiler command line.

The "ifdef way" is like :

code :

#ifdef STUFF
  .. stuff a ..
#else
  .. stuff b ..
#endif

command line :

compiler -DSTUFF %*
or
compiler %*

Whereas the "if way" is :

code :

#ifndef STUFF
  // stuff not set
  // could #error here
  // or #define STUFF to 0 or 1
#endif

#if STUFF
  .. stuff a ..
#else
  .. stuff b ..
#endif

command line :

compiler -DSTUFF=1 %*
or
compiler -DSTUFF=0 %*

Why is the "if way" so much better ?

1. You can tell if the user set STUFF or not. In the ifdef way, not setting it is one of the boolean values, so you can't tell if the user made any intentional selection or not. Sometimes you want to ensure that something was selected explicitly because it's too dangerous to fall back to a default automatically.

2. You can easily change the default value when STUFF is not set. You can just do #ifndef STUFF #define STUFF 0 or #ifndef STUFF #define STUFF 1. To change the default with the ifdef way, you have to change the sense of the boolean (eg. instead of STUFF use NOTSTUFF) and then all your builds break because they are setting STUFF intead of NOTSTUFF (and that breakage is totally fragile and non-detectable because of point #1).

3. There's no way to positively say "not STUFF" in the ifdef way. The way not stuff is set is by not passing anything ot the command line, but frequently it's hard to track down exactly how the command line is being set through the convoluted machinations of the IDE or make system. If some other bad part of the build script has put a -DSTUFF on your command line, you can't easily undo that by just tacking something else on the end of the command line.

I think it's incontrovertible that the "if way" is just massively better, and everyone should use it all the time, and never use ifdef. And yet I myself still use ifdef frequently. I'm not really sure why, I think it's just because I grew up using ifdef for toggles, and I'm so used to seeing it in other people's code that it just comes out of my fingers naturally.

---

Anyway, I was thinking about this because I had some problems with some #defines at RAD, and I chased down the problem and cleaned it up, and it seemed to me that it was a pretty good example of "cbloom style robustination". I've never met anyone who writes code quite like me (some are thankful for that, I know); I try to write code that is hard to use wrong (but without adding crazy complexity or overhead the way Herb Sutter style code does).

(disclaimer : this is not intended as a passive aggressive back-handed way of calling out some RAD coder; the RAD code in question is totally standard style that you would see anywhere, and it wasn't broken, just hard for me to use)

Anyhoo, the code in question set up the function exporting for Oodle.h ; it was controlled by two #defines :

#ifdef MAKEDLL
    #define expfunc __declspec(dllexport)
#else
#ifdef MAKEORIMPORTLIB
    #define expfunc extern
#else
    #define expfunc __declspec(dllimport)
#endif
#endif

Okay, so there are four usage cases :

1. building Oodle as a LIB - use -DMAKEORIMPORTLIB
2. building Oodle as a DLL - use -DMAKEDLL
3. building an app that uses Oodle as a LIB - use -DMAKEORIMPORTLIB
4. building an app that uses Oodle as a DLL - use no define

and that all works fine (*). But I found it hard to use; for example if I try to stick a -DMAKEXE on the command line and somebody already set -DMAKEDLL, it doesn't do what I expected; and there's no way to definitely say "I want dllimport".

(* = actually it also works if you use -DMAKEORIMPORTLIB in case 4; specifying "dllimport" for functions is actually optional and only used by the compiler as an optimization)

So anyway here's the robustinated version :

    #ifdef MAKEDLL
        #define expfunc __declspec(dllexport)
        
        #if defined(MAKELIB) || defined(IMPORTLIB) || defined(IMPORTDLL)
            #error multiple MAKE or IMPORT defines
        #endif
    #elif defined(IMPORTDLL)
        #define expfunc __declspec(dllimport)
        
        #if defined(MAKELIB) || defined(MAKEDLL) || defined(IMPORTLIB)
            #error multiple MAKE or IMPORT defines
        #endif
    #elif defined(MAKELIB)
        #define expfunc extern
        
        #if defined(MAKEDLL) || defined(IMPORTLIB) || defined(IMPORTDLL)
            #error multiple MAKE or IMPORT defines
        #endif
    #elif defined(IMPORTLIB)
        #define expfunc extern
        
        #if defined(MAKELIB) || defined(MAKEDLL) || defined(IMPORTDLL)
            #error multiple MAKE or IMPORT defines
        #endif
    #else
        #error  no Oodle usage define set
    #endif

and usage is obvious because there's a specific define for each case :

1. building Oodle as a LIB - use -DMAKELIB
2. building Oodle as a DLL - use -DMAKEDLL
3. building an app that uses Oodle as a LIB - use -DIMPORTLIB
4. building an app that uses Oodle as a DLL - use -DIMPORTDLL

and it's much harder to use incorrectly, because you have to set one and only one. Also it's a little bit less implementation tied, in the sense that the fact that MAKELIB and IMPORTLIB are actually the same thing is hidden from the user in case that ever changes.

(and of course I instinctively used #ifdef for toggles when I wrote this instead of using #if)

---

I used to think that "robustinated" code was the One True Way to write code, and I wrote advocacy articles about it and tried to educate others and so on. I basically have given up on that because it's too frustrating and tiring trying to convince people about coding practices. And in my old age I'm more humble and no longer so sure that it is better (because the code becomes longer, and short to-the-point code has inherent advantages; also robustination takes coder time which could be spent on other things; lastly robustination also tends to make compiles slower which hurts rapid iteration).

But I do know it's the right way for *me* to write code. When I first came to RAD I tried very hard to write code the "RAD way" so that the style would be consistent and so on. That was a huge mistake, it was very painful for me and made me write very bad code and take much longer than I should have. Only after a few years in did I realize that to be productive I have to write code my way. In particular I need the code to be very strongly self-checking.

08-12-12 - Unicode on Windows Summary Page

Making another summary page for myself to link to.

Posts about the disaster of Unicode on Windows : (mainly with respect to old apps and/or console apps)

cbloom rants 06-14-08 - 3
cbloom rants 06-15-08 - 2
cbloom rants 06-21-08 - 3
cbloom rants 11-06-09 - IsSameFile
cbloom rants 06-07-10 - Unicode CMD Code Page Checkup
cbloom rants 10-11-10 - DeUnicode v1.0
cbloom rants 10-11-10 - Windows 1252 to ASCII best fit
cbloom rants 07-28-12 - DeUnicode 1.1

Brief summary : correctly handling unicode (*) file names in a console app on windows is almost impossible. cblib has some functions to do the best I believe you can do (MakeUnicodeNameFullMatch), but it's so complicated and error prone that I suggest you should not try it. Also never use printf with wchars, it's badly broken; do your own conversion.

(* = actually the problem occurs even for non-unicode 8-bit character names (eg. any time the "A" "OEM" and "ConsoleCP" encodings could be different); Windows console apps only work reliably on file names that are 7-bit ascii).

08-11-12 - Technical Writing

Whenever I give people my technical writing to review, one of the first comments out of most people's mouths is "you need to remove the use of 'I' , and the asides, and the run-on sentences, and this bit where you say 'fuck' is unprofessional, and blah blah".

Fie! Fie I say to you!

One of the great tragedies of modern technical writing is that it has gotten so fucking standard and boring. There is absolutely no reason for it. It does not make it clearer or easier to read, in fact it makes it worse in every way - less clear, less fun, less human.

If you read actual great technical writing, it has humanity and humor. For me the absolute giants of technical writing are Feynman and Einstein. There's lots of cleverness and little winks for the advanced reader and lots of non-standard ways of writing things. If they followed Boring Technical Style Guide it would suck all the personality and beauty from their writing. (I also like Isaac Asimov's technical writing and John Baez's).

I think computer writing has become particularly bad in the last 10 years or so. The books are all Microsoft-press-style bullet point garbage. Blogs (eg. finger files) started out in the early days as sort of wonderful ramshackle things where each one was different and reflected the writer's personality, but recently there has developed this standard "technical blog style" that everyone follows.

Standard Technical Blog Style is very pedantic and condescending; the author acts like some expert from on high (regardless of their actual expertise level). There are as many self-plugs as possible. I find it vomitacious.

A while ago someone wrote a blog series about floating point stuff; it really bothered me for various reasons. One was that the topic has been covered many times in the past (by Chris Lomont for example, also FS Acton, Kahan, Hecker, etc) (if you actually want to learn about floating points, Kahan's web page is a good place to start). Another is that it just rolled out the same old crap without actually talking about solutions (like "use epsilons for floating point compares" ; wow that is super non-useful advice; tell me something real like how to make a robust BSP engine with floating point code). But maybe the most bothersome thing about it all was that it was written in Standard Boring Dicky Technical Blog Style when you can go out right now and buy a wonderful book by Forman S. Acton on floating point which is not only much much more useful, but it's also written with cleverness and humanity. (Kahan's writing is also delightfully quirky). It's kind of like taking a beautifully funky indie movie and remaking it as mainstream shlock; it's not only a waste of time, but offensive to those of us who appreciate the aesthetic pleasure that is possible in technical writing.

Anyway, if you are considering doing some blogging or technical writing, here is my advice to you :

1. Make it informal. Use I. Use incomplete sentences. Tell stories about your personal experience with the topic. When you put in some really complicated code or equations or whatever, explain what it means with colloquial, conversational english.

2. Don't look at any reference material for a writing style to copy. Their style fucking sucks. Don't copy it. If you listen to people telling you the "right way" to do things, you will be aspiring to mediocrity. (err, ahem, but do listen to me).

3. Do not use an artifical impersonal voice to add "gravity" or a false air of expertise, it doesn't work. Be humble; admit it when you aren't sure about something. Also don't pad small ideas with more text to make them seem bigger. There's nothing wrong with a one sentence idea. 90% of AltDev blogs should be one paragraph or less.

4. Do not waste time editing that could be spent making the content better. I bet you didn't actually run fair comparison tests against competing methods. Go do that instead. I will not judge you by the purpleness of your prose but rather by the content of your creation.

5. Stop writing blogs about shit that is already very well covered in books. Your writing should always be from the perspective of your domain-specific experience on a topic. Don't write yet another introduction to Quaternions, write about how you've used them differently or some application you've found that you think is worth writing about. Real domain-specific experience is what make your writing valuable.

6. Habeas Corpus. Show me the money. If you're writing about some new technique, provide code, provide an exe, prove it. If I can't repro your results, then I don't believe you. Document the tiny details and embarassing hacks. The vast majority of technical writers don't write up what they *actually* use. Instead they write up the idealized clean version of the algorithm that they think is more elegant and more scientific. Often the most useful thing in your work are the hacks for weird cases that didn't work right. People are usually too proud of the main idea; hey guess what, thousands of people have had that idea before, but didn't think it was worth pursuing or didn't get the details quite right; the value is usually in the tweak constants or the little fudgey bits that you figured out.