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 <gl...@gclements.plus.com> _______________________________________________ grass-dev mailing list grass-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-dev