Question to make sense of the algorithm

[Andersama]

If I'm not mistaken the masks used are for the algorithm presuming it's reading the input string backwards?

Was trying to implement this in c and I'm still having trouble. I got curious if the algorithm can be "flipped" the other way around. Instead of reading what I'm assuming is 6 bits from the end, having it read 6 bits from the front. I think this changes the mask from (63 & 62 & 31 & 30) to (63 & 62 & 61 & 60)?

[jxskiss]

Yes, I think it can work forwards, but will be a little more complex to implement.

[Andersama]

Unfortunately in my confusion I lost my best working attempt. It seemed like the algorithm might work fine if performed forwards, I just never got it to pass any of my fuzzing attempts so I'm guessing I'm making some fundamental mistakes

Here's a rough start in c

struct base62_encode_result_t encode_base62(char* dst, size_t dst_len, const char* input, size_t in_len, char* alphabet) {
	base62_encode_result_t r = { 0 };

	size_t i = 0;

	uint32_t tmp_buf = 0;
	uint32_t tmp_buf_bits = 0;

	size_t encoding_bits = in_len * 8;
	size_t processed_bits = 0;

	//const uint32_t detect_mask = (0x37 & 0x36);
	const uint32_t detect_mask = (bits5_mask << 1); //11_11_10
	//const uint8_t detect_constant = ;
	uint32_t output_bits = 0;

	for (; i < in_len; i++) {
		//load a byte into the buffer (8 bits)
		tmp_buf = (tmp_buf << 8) | input[i];
		tmp_buf_bits += 8;
		// make clearer
		// tmp_buf = tmp_buf & (0xffffffff >> (32 - tmp_buf_bits));
		// encode the bits

		//0111 1000
		//0111_10 00xx_xx

		// trying to encode the leading msb
		
		//63 -> 11_11_11 (too big) only encode 5 bits, remap to 01_11_11
		//62 -> 11_11_10 (too big) only encode 5 bits, remap to 01_11_11
		//61 -> 11_11_01
		//60 -> 11_11_00

		// 31 -> 01_11_11 (may have been 63) seeing this 
		// 30 -> 01_11_10
		
		//3 -> 00_00_11
		//2 -> 00_00_10
		//1 -> 00_00_01
		//0 -> 00_00_00

		do {
			uint32_t shift_back = (tmp_buf_bits >= 6) ? tmp_buf_bits-6 : 0;
			uint32_t bits_6 = (tmp_buf >> shift_back) & bits6_mask; //we can't encode 62 or 63 they're out of bounds
			uint32_t fbits_5 = bits_6 >> 1;

			//since 62 and 63 are invalid 6 bit options, we can mask with 5 bits
			uint8_t e6_byte = alphabet[bits_6]; //encoding the full 6 bit pattern
			//note if we're (30 | 31) we use this
			uint8_t e5_byte = alphabet[fbits_5]; //encoding the 5 bit pattern, (handles 63 (0111111) as (63>>1) and 62 (0111110) as (62>>1)) 0111110 

			uint32_t use_leading_5bits = (bits_6 & (detect_mask)) == detect_mask; //if 62 or 63 encode 11_11_11
			uint32_t encodes_5bits = (bits_6 & (base62_common_bitmask)) == base62_common_bitmask;
			//when we shift 62 or 63 in order to handle 5 bits we need to have 01_11_11 and 01_11_10 (31 and 30) signal that we're only encoding 5 bits

			size_t rem_bits = (encoding_bits - processed_bits);

			uint8_t out_byte = use_leading_5bits ? e5_byte : e6_byte;
			//in this loop since we always have > 6 bits we can always encode at least 5 bits
			uint32_t encoded_bits = encodes_5bits ? 5 : 6;
				//&& ((rem_bits > 6) || (bits6_mask > bits5_mask)) ? 5 : 6;

			//we "remove" the bits in the temporary buffer
			//discard(&tmp_buf, tmp_buf_bits - 6, encoded_bits);
			tmp_buf_bits -= encoded_bits;
			processed_bits += encoded_bits;
			//
			//output_bits = tmp_buf_bits >= 24 ? tmp_buf_bits : output_bits;
			//output_bits = output_bits > encoded_bits ? (output_bits-encoded_bits) : 0;

			if (r.char_count < dst_len) {
				dst[r.char_count] = out_byte;
				r.char_count++;
			}
			r.required_count++;
			//should take a while before this gets close to being filled
			//we can make this larger if we want
		} while (output_bits >= 6);
	}

	//exit when we've written enough bits to handle the bytestream
	while (processed_bits < encoding_bits) { 
		//shift in 0s if we don't have enough bits
		uint32_t needs_bits = (tmp_buf_bits < 6) ? 6 - tmp_buf_bits : 0;

		tmp_buf = (tmp_buf << needs_bits);
		tmp_buf_bits += needs_bits;

		uint32_t shift_back = (tmp_buf_bits >= 6) ? tmp_buf_bits - 6 : 0;
		uint32_t bits_6 = (tmp_buf >> shift_back) & bits6_mask; //we can't encode 62 or 63 they're out of bounds
		uint32_t fbits_5 = bits_6 >> 1;
		//uint32_t bits_4 = bits_6 & detect_mask; // bits5_mask; // 

		//since 62 and 63 are invalid 6 bit options, we can mask with 5 bits
		uint8_t e6_byte = alphabet[bits_6]; //encoding the full 6 bit pattern
		//note if we're (30 | 31) we use this
		uint8_t e5_byte = alphabet[fbits_5]; //encoding the 5 bit pattern, (handles 63 (0111111) as (63>>1) and 62 (0111110) as (62>>1)) 0111110 

		uint32_t use_leading_5bits = (bits_6 & (detect_mask)) == detect_mask;
		uint32_t encodes_5bits = (bits_6 & (base62_common_bitmask)) == base62_common_bitmask;

		size_t rem_bits = (encoding_bits - processed_bits);

		uint8_t out_byte = use_leading_5bits ? e5_byte : e6_byte;
		//in this loop since we always have > 6 bits we can always encode at least 5 bits
		uint32_t encoded_bits = encodes_5bits ? 5 : 6;
		//&& ((rem_bits > 6) || (bits6_mask > bits5_mask)) ? 5 : 6;

		//we "remove" the bits in the temporary buffer
		//discard(&tmp_buf, tmp_buf_bits - 6, encoded_bits);
		tmp_buf_bits -= encoded_bits;
		processed_bits += encoded_bits;

		if (r.char_count < dst_len) {
			dst[r.char_count] = out_byte;
			r.char_count++;
		}
		r.required_count++;
	}
	return r;
}

[Andersama]

I'm thinking there might be a nicer way to encode / decode with 60 and 61 indicating 4 bits as opposed to 5.

EG: for every 6 bits, if we're in the range [63, 60] we can drop 2 bits for the next step instead of 1 for the variable length encoding.

I'm not sure how to preserve the 5 bits easily otherwise.

Edit: I have successfully managed to get this working, since everything is either 4 bits or 6 bits it was fairly easy.

Ok, after having gotten the 4 bit version working, the 5 bit approach was more intuitive since it's just a matter of what mask is picked and how to manipulate the extra bit.

Figured out the 5 bit approach, the original algorithm almost works forwards and backwards, the trick is that instead of using 0b011111 as a mask to get the index for the encoded value we have to move the msb of the 6 bit string to the lsb so that we map 63 and 62 to 31 while 31 and 30 map to 30. It just so happens there's a number of inputs where the original algorithm works very similarly to the forwards approach.

[jxskiss]

I'm glad to hear that it works, the forwarding way can also be used to implement streaming encoding/decoding.

(I choosed to not implement streaming in this package, I think it's a better choice to use base64 or other encoding to handle streaming data, just use base62 to process human-oriented short data 😄 )