In my previous post, I introduced the rationale behind my efforts to determine how to decompress binary images and textual data held by our Cerner HIS. This <very long> post will discuss the final library and how I produced the working code.
In my preliminary research, I had read and heard that Cerner had attempted to obfuscate or otherwise “hide” the compressed data from their customers. I also encountered several comments where people had found that the algorithm was Lempel–Ziv–Welch (“LZW”) – a common lossless compression algorithm. Given the wide range of implementation options available for LZW, I feared the worst.
At first, I approached the problem expecting to find some intended obfuscation; but to my surprise, there was none. As it turned out, Cerner deploys their compression using the standard LZW algorithm making decompression readily available to their customers. However, there are a number of deployment options that an LZW implementer can select from and so the fun challenge was to determine what path Cerner had chosen for their particular implementation. Of course, Cerner could have made all this easy by publishing an API so we can more easily use our data….
To begin with, I used a handful of “BLOBs” from our CE_BLOB table and knowing the decompressed values, I determined what I thought was the final solution. However, when I pulled a very large file to test, I found that I had more work to do since my initial approach did not work for the larger files (more below…).
So let’s review the basics of LZW – strictly from the decompress perspective:
- LZW uses a decompression table that can be created by the consumer (“client”) at run time. Therefore, there’s no need to transfer or store the table on the client side.
- The table can be determined at run time; but there are a number of assumptions that must be understood by the client and the compressor. We’ll look at some of these shortly.
- Any time two or more characters repeat, their decompressed values are read from the table and not from the byte stream. This proved to be the most challenging aspect: to determine the table entries to verify the assumptions of decompression; but knowing that the table I had created may be (and frequently was) incorrect.
- Tables can be cleared at some predetermined time and reinitialized.
- Tables can be customized with some predetermined values.
Frankly, Cerner could have been creative with #4 and/or #5 and thus make it very difficult to reconstruct the table. But I quickly found that they did neither which made things much easier to figure out.
As it turned out, #3 was the only thing I needed to determine and because I had the encrypted BLOBs from the database, and the original text, it was just a matter of determining the variables that they chose for their implementation.
So what variables? Let’s review a bit (computer pun) about bits and bytes in the computer world.
At the lowest level, computers store everything as ones and zeros; or to be more precise as positive or negative values (it used to be +5volts or –5volts but that may no longer be correct).
From these “bits” of information, a byte is created and a byte is comprised of 8 bits.
In the early days of computing, we could express just about everything in 127 characters and so 7 bits were adequate. For example, the number 127 in decimal turns out to be 1111111 in binary (base 2). Eventually, the computer world decided to use all 8 bits in the byte and so ASCII was “extended” to the full range of a byte or 256 characters. In other words, the ASCII Lookup Table is set by convention at 256 characters and this is standard across computers.
The thing to remember is that the numbers are index positions in the lookup table. For ASCII, this table has 256 entries starting with entry 0. So the character at entry position 0 by convention is NULL. Similarly, the letter X is at index location 88 decimal and is expressed in binary as 1011000.
In practice, binary data is typically stored in an array of bytes and individual bytes can be represented by a number from 0 to 255 (zero based so that’s 256 characters). If we have a number that’s larger than 255, it will not fit into a single byte but rolls over into another byte. So the number 256 is represented as one more than the maximum of one byte of 11111111; so 256 in binary is 1 0000 0000. [This can be confusing but think of it in decimal: if you have a value of 999,999 and add just 1 to it, it becomes 1,000,000].
If we don’t need compression, we would just use the standard 8 bits in each byte and we’d be set. But for LZW (and most other) compression routines, repeating characters are represented with a new entry in the lookup table. But dang, we just said that the ASCII table already takes up all the places possible so we must use indexes larger than 255 and so we must roll over into another byte if we need numbers greater than 255.
This is the first place that LZW allows us to make a choice from several alternatives:
- We can specify a fixed table size that can accommodate the typical source file size. If we know the size and composition of the source files, this makes the most sense. But given the nature of health data, this is not a good approach for us.
- We can set a fixed table size that allows us to clear the table after it fills up. This is easy on the programmer but not optimal for good compression.
- The final choice is to slowly grow the bit size to expand to meet the size of the index. For example, we know that indexes as large as 511 would fit in a 9 bit size. And a 10 bit number size would allow us to store indexes as large as 1023. This has the advantage of improving compression; but the problem is that we need to make assumptions about our data and to choose the bit size-break (when we move to the next larger bit sized number) and the appropriate time.
Cerner opted for #3 but that left us with the challenge of figuring out where they made these bit size-breaks; that is, when they moved from 9 bit numbers to 10 and so on.
NOTE: most textbook implementations of LZW show the algorithm as #1 with the maximum number held in 12 bits which is a convenient byte and a half. Therefore, a table in this convention could not exceed 4095 entries. This is even more convenient for the programmer since the bits always break on a byte boundary; that is, “take 8 bits from the first byte and add 4 bits from the next one” and then “take the leftover 4 bits and add them to the 8 bits from the next byte”. This is “Textbook” LZW but not very efficient in the real world.
OK, so let’s focus on the Cerner implementation because I’m sure you’re getting tired.
As we have already observed, they increase the maximum index size at set places in the byte stream (our #3 above). Since the bit size-breaks are fixed for their implementation and are somewhat arbitrary, the only way I could find to determine this location was to take a variety of compressed BLOBs, run them through the decompression code, and find out where the table values didn’t match; in other words, the decompressed string did not match the pre-compressed string. Fortunately, these “bit size-breaks” always occurred at the same places in all the files (meaning it was a set place and not based on a variable) and my code reflects those positions.
The concept of these byte splits (or “bit splits”) may be confusing so let me explain with an example.
If we are in the middle of the byte stream and we have three bytes with these values in order:
0010 1111
1110 0001
0011 1101
Now, if we are using the Textbook LZW split of 12 bits, our two codes would be (note: for the sake of demonstration, we are ignoring the shift of the first byte; in practice, this must be shifted first):
001011111110 all 8 bits from the first byte and 4 bits from the second for our 12
000100111101 which is the four bits left from the second byte and all of the last byte
So in these three bytes, we have two lookup codes: 766 and 317
But these same three bytes would represent different codes if we use a different split size of say 10 bits where our two codes would be:
0010111111 which is 191
1000010011 which is 531
and we’d have the following bits left over: 1101.
When the bit split size is smaller, we have the capacity for more codes (numbers) in the same number of bytes since these numbers are smaller. The trick is keep the bit size low enough to represent numbers (the Lookup Table index values) that are efficient but high enough to account for highly random character arrangements in the source file and thus the need for more index locations (less compression) and larger numbers.
The key point here is that split size (how many bits represent the lookup codes) is critical for things to work but somewhat arbitrarily chosen by the implementation developer. Since I had the original text (net yet compressed which should match the decompressed string), I could walk through the code as it created the lookup table byte by byte and compare the output with the original text and once I found a discrepancy, note the location and shift up the bit size for the next sequence of index numbers accordingly. Of course I could have written a sub-program to do this work for me; but instead I used a specially constructed pre-compressed sequence of characters (text) that made this very efficient (finding the discrepancies) and it proved quicker and easier than writing the subroutine.
For this implementation, they use 9 bit numbers for the first 285 bytes, they then use 10 bit numbers up to 925, and so on (see the code) up to 14 bit numbers beginning at byte 12061.
Since our maximum bit size is 14, our maximum Lookup Table index size is binary 11 1111 1111 1111 which in decimal is 16,383. Therefore, our Lookup Table cannot hold more than 16,383 index locations. If we deduct the 256 ASCII characters, our table for new index entries falls to 16,127. After this, compression would need to be switched off for ensuing bytes. Cerner apparently handles this by breaking files larger than roughly twice this number into subsequent BLOBs. In other words, they assume (correctly I imagine) that most files (text or image) will have at least a 2X compression ratio at the bit level. That is, on average at least half of the byte pairs will be repeating or better. Given the nature of the source data, this seems to be a reasonable approach for both image and text.
The astute reader will see that there was one more problem to deal with (which is the surprise I alluded to earlier in this post). For the Textbook LZW sample using 12 bit numbers, and with our 9 and 10 bit numbers; we will always break on a byte boundary. In other words, we build up our code (the index number) by using 8 bits from one byte and 1 or more bits from the next byte. In the case of a 9 bit number, our 1 bit will easily break at the 8th bit as we proceed through our incrementing shits (more on this shortly). Similarly, our 10 and 12 bit words break at the bit boundary (since the bits we take from the second byte divide into our 8 bit byte with no remainder). But, our 11 bit number will not break at the boundary and so we must take three bytes to make our number. That is, we take the Leftover, the full middle byte, and the current shift from the last byte.
Another example will illustrate.
If we take a 12 bit number, we start with zero left over, take the full 8 bits from the middle byte (which really is the next byte in sequence), and then 4 bits from the right byte (again the next in sequence). In the next iteration we have 4 bits left over from the previous iteration and take 8 bits from the middle byte and since we have 12 bits, we don’t need the new right byte.
However, if we have an 11 bit number, we again start with zero left over, take the full 8 bits from the middle byte (next in sequence), and then 3 bits from the right byte (the next in sequence). We have 5 left over from the previous (left) byte, and take 6 from the middle byte to give us our 11 bits. But the next iteration is where it gets interesting. We have 2 bits leftover from our Left Byte (8 – 6), we use the full 8 bits from the middle byte, but we now need 1 bit from the right byte (the next in sequence). The point is that for the first time, we actually use bits from three bytes and this must be handled in the code.
I found one online post that complained that Cerner had started their decompression with standard LZW; but later in the decompression, they introduced something that was not in the LZW spec. I suspect that this three-byte-shift threw them off because I have to admit, it took some mental energy to figure out how and when they did this.
Finally, for very large files I had difficulty determining the closing character sequence at the end of the byte stream so I could stop decompression. I suspect that this is why Cerner includes the decompressed (or pre-compressed) file size in their row data along with the BLOB. In other words, these three byte shifts make it difficult to find the closing characters and so we need the actual files size to complete decompression correctly.
Therefore, to call the pure managed code version of the decompress, you should pass in this file size along with the BLOB.
As I mentioned before, this was a fun puzzle to solve and I hope this explains what the code is doing and answers any question you might have. If you see a way to do this more efficiently, please leave a comment and I can modify the code if it makes sense.
Posts
