4 ms·
Given that 85^5 > 2^32, it's a little strange that they also didn't specify what happens if the text encodes a number that doesn't fit in 4 bytes.
by gary_0 3y ago
Given that 85^5 > 2^32, it's a little strange that they also didn't specify what happens if the text encodes a number that doesn't fit in 4 bytes.
- dullcrisp 3y agoThen it’s invalid, same as if it includes unexpected characters or isn’t a multiple of five characters long.
- gary_0 3y agoThe "reference implementation" in C seems to just let the int wrap around. It also does an out of bounds array access if the string contains non-ASCII chars.
- dullcrisp 3y agoSounds like the reference implementation only specifies what should be done with valid values then? I’d avoid using it in production without separate validation.
- Dwedit 3y agoYou could theoretically put 1, 2, or 3 byte sequences into the space between 4294967296 and 4437053124. That gap holds over 27 bits of information. Example: 0 to 4294967295 = 4 bytes 4294967296 to 4311744511 = 3 bytes (subtract 4294967296 first) 4311744512 to 4311810047 = 2 bytes (subtract 4311744512 first) 4311810048 to 4311810303 = 1 byte (subtract 4311810048 first) Then you're still left with 125242821 remaining numbers, over 26 bits.
- tromp 3y agoThat is one way to extend the encoding from 4-byte chunks to arbitrary byte lengths. Another is to encode 4k+i bytes as 5k+1+i base-85 characters, for 0<i<4. That way the encoding length immediately determines the input length. And there's again plenty of space since 85^{i+1} > 256^i for i < 4. This leaves encoding lengths of 5k+1 unused. These could be used to support arbitrary bit lengths, i.e. for encoding an input of 4(k-1) bytes + i bits, with 0<i<32. Set the final byte to i, and let the preceding 5 base-85 characters encode the i bits with 0 padding.