Step by Step solution about How to resolve the algorithm Variable-length quantity step by step in the C programming language

Overview: This C program demonstrates a custom encoding/decoding scheme for 64-bit unsigned integers. It encodes integers into sequences of bytes, ensuring that each byte except the last is set to the most significant bit (128). The last byte has the most significant bit cleared to mark the end of the sequence. Conversely, it can decode these sequences back to their original integer values.

Explanation:

to_seq(uint64_t x, uint8_t *out):

• Takes a 64-bit unsigned integer x and encodes it into an array of bytes out.
• Finds the highest-order bit group that is not all zeros, indicating the number of bytes needed.
• Iterates through the bytes and stores the 7 least significant bits of x in each byte, setting the most significant bit (MSB) to 128 for all except the last byte.
• The MSB of the last byte is cleared to mark the end of the sequence.

from_seq(uint8_t *in):

• Decodes a sequence of bytes in into a 64-bit unsigned integer.
• Iteratively shifts the current result left by 7 bits and adds the 7 least significant bits of the current byte in in.
• Continues until the MSB of the current byte in in is 0, indicating the end of the sequence.

main() function:

• Defines an array x of various 64-bit unsigned integer values.
• Calls to_seq to encode each value into a byte array s and prints the encoded sequence.
• Calls from_seq to decode the encoded sequence and prints the decoded value.

Sample Run: The program prints the following output:

seq from 7f: [ 7f ] back: 7f
seq from 4000: [ 81 80 00 ] back: 4000
seq from 0: [ 00 ] back: 0
seq from 3ffffe: [ 81 ff ff 7e ] back: 3ffffe
seq from 1fffff: [ ff ff 7f ] back: 1fffff
seq from 200000: [ 81 80 80 00 ] back: 200000
seq from 3311a1234df31413: [ b3 88 e8 a4 b4 ef cc a8 13 ] back: 3311a1234df31413

This demonstrates the ability of the encoding/decoding scheme to handle a range of integer values and encode them into compact byte sequences.

#include <stdio.h>
#include <stdint.h>

void to_seq(uint64_t x, uint8_t *out)
{
	int i, j;
	for (i = 9; i > 0; i--) {
		if (x & 127ULL << i * 7) break;
	}
	for (j = 0; j <= i; j++)
		out[j] = ((x >> ((i - j) * 7)) & 127) | 128;

	out[i] ^= 128;
}

uint64_t from_seq(uint8_t *in)
{
	uint64_t r = 0;

	do {
		r = (r << 7) | (uint64_t)(*in & 127);
	} while (*in++ & 128);

	return r;
}

int main()
{
	uint8_t s[10];
	uint64_t x[] = { 0x7f, 0x4000, 0, 0x3ffffe, 0x1fffff, 0x200000, 0x3311a1234df31413ULL};

	int i, j;
	for (j = 0; j < sizeof(x)/8; j++) {
		to_seq(x[j], s);
		printf("seq from %llx: [ ", x[j]);

		i = 0;
		do { printf("%02x ", s[i]); } while ((s[i++] & 128));
		printf("] back: %llx\n", from_seq(s));
	}

	return 0;
}


seq from 7f: [ 7f ] back: 7f
seq from 4000: [ 81 80 00 ] back: 4000
seq from 0: [ 00 ] back: 0
seq from 3ffffe: [ 81 ff ff 7e ] back: 3ffffe
seq from 1fffff: [ ff ff 7f ] back: 1fffff
seq from 200000: [ 81 80 80 00 ] back: 200000
seq from 3311a1234df31413: [ b3 88 e8 a4 b4 ef cc a8 13 ] back: 3311a1234df31413