2012/9/24 Glynn Clements <gl...@gclements.plus.com>: > > 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.
So this bug is not fixable at all? >> 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. I would prefer to disable RLE and keep the code only for backward compatibility. > >> 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. I will try to remove the LZW compression code from the raster3d lib so that full backward compatibility is assured. Best regards Soeren > > -- > Glynn Clements <gl...@gclements.plus.com> _______________________________________________ grass-dev mailing list grass-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-dev