[GRASS-dev] Grass SVN in Android, display issue

[Glynn Clements]

Sören Gebbert wrote:

> >> i have tested the raster3d library and most of the related modules intensively.
> >> I rediscovered an ugly bug in the 3D raster run length encoding (RLE)
> >> compression implementation  and modified the library test to catch it.
> >> I am unable to fix the RLE compression bug.
> >
> > Can you elaborate on this RLE bug?
> 
> As far as i understand the RLE encoding/decoding algorithm in
> lib/raster3d/rle.c is buggy.
> The functions rle_length2code() and rle_code2length implement wrong
> length computation for strings larger than 129031 characters.
> I have put some comments in the code.

Right. Clearly that case hasn't happened in practice, because it would
result in fairly obvious errors.

> The length computation:
> length = 254 ^ c + 254 * b + a; b, a < 254
> works only for c <= 2. For c == 3 the implementation should be:
> length = 254 ^ 3 + 254 ^ 2 * c + 254 * b + a; c, b, a < 254

Indeed. Clearly, there's no way that all values up to 254^3 can be
represented with only two "value" bytes.

The ideal solution would be to store runs of >= 254^2 as multiple
runs. That would maintain backward compatibility while avoiding the
bug. But that would require re-writing Rast3d_rle_encode() and
Rast3d_rle_count_only(); there's no way that G_rle_codeLength and
rle_length2code can be fixed, as they assume that any length can be
encoded.

> However, i do not understand the advantage of having RLE first and a
> LZ77 or LZ78 compression afterwards.
> Shouldn't be the LZ77/78 compression sufficient for compression of
> float/double values?

For sparse data, using RLE first can often provide a noticeable
improvement.

> Oh well, i did not know that the G_lzw_* functions don't exist.
> Its a bit confusing that the option that switches on the LZ77
> compression is called RASTER3D_USE_LZW ... .

RASTER3D_USE_LZW switches on "real" compression (either LZW or LZ77,
depending upon the USE_LZW_COMPRESSION macro).

When LZW was replaced by LZ77, presumably the RASTER3D_USE_LZW name
was kept in order to avoid changing the external API.

Given how long it has been since LZW was supported, and that LZW and
LZ77 are mutually exclusive at compile time, there seems little point
in keeping any of the LZW code.

-- 
Glynn Clements <glynn at gclements.plus.com>