The length of the number of leading zeros probably should be 5 bits

[lemolatoon]

I found in this crate, the number of leading zeros is encoded in 6 bits where the control bit is '11'. However, according to Gorilla's paper, it should be encoded in 5 bits.

(b) (Control bit ‘1’) Store the length of the number of leading zeros in the next 5 bits, then store the length of the meaningful XORed value in the next 6 bits. Finally store the meaningful bits of the XORed value.

The corresponding codes are here.

tsz-rs/src/encode/std_encoder.rs

Lines 132 to 138 in b3e2dce

	// if the number of leading and trailing zeroes in this xor are not less than the
	// leading and trailing zeroes in the previous xor then we store a control bit and
	// use 6 bits to store the number of leading zeroes and 6 bits to store the number
	// of significant digits before storing the significant digits themselves
	self.w.write_bit(Bit::One);
	self.w.write_bits(u64::from(leading_zeroes), 6);

tsz-rs/src/decode/std_decoder.rs

Line 143 in b3e2dce

self.leading_zeroes = self.r.read_bits(6).map(|n| n as u32)?;

Is there a specific reason to use 6 bits for the leasing zeros in this crate?

[jeromefroe]

Hi @lemolatoon! It's been a while since I've worked on this crate so I don't recall for sure, but I think I may have just misread the paper and used 6 bits instead of 5 when implementing it 🤦

[lemolatoon]

@jeromefroe Thanks for your reply! I understand the circumstance. I could write some patches to fix this, but it would be a big breaking change. I will keep it. If you think this should be fixed, I'll send a Pull Request, so I would like you to let me know.

[jeromefroe]

If you want to fix it, I'd be more than happy to accept the pull request. It would just have to be released as a new version since as you noted it would be a breaking change.

[lemolatoon]

I was exercising around the Gorilla Compression. I found that If we have more than or equal to 32 bits of leading zeros, we cannot encode it in 5 bits. In that case, we should treat it as 31 bits of leading zeros, and the rest of zeroes as significant bits (in other words, meaningful bits).
I found another implementation of Gorilla, and they do like that.

https://github.com/panagiotisl/chimp/blob/main/src/main/java/fi/iki/yak/ts/compression/gorilla/Compressor.java#L81-L84

I an thinking about writing patches and open pull requests for this issue when I am free.

Thank you!