summaryrefslogtreecommitdiff
path: root/src/varint.c
blob: da7e480d767773ab89e31074db36204dc65ad141 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdint.h>

void
encode_varint(uint8_t *data, uint32_t *write, int64_t value, uint32_t left)
{
	uint32_t pos = 0;

	if (value < 0) {
		*write = 0;
		return;
	}

	if (value < 0x80) {
		data[pos++] = value & 0xFF;
	} else if (value < 0x4000) {
		data[pos++] = 0x80 | ((value & 0xFF00 ) >> 8);
		data[pos++] = value & 0xFF;
	} else if (value < 0x200000) {
		data[pos++] = 0xC0 | ((value & 0xFF0000) >> 16);
		data[pos++] = ((value & 0xFF00) >> 8) & 0xFF;
		data[pos++] = value & 0xFF;
	} else if (value < 0x10000000) {
		data[pos++] = 0xE0 | ((value ) >> 24);
		data[pos++] = (value >> 16) & 0xFF;
		data[pos++] = (value >> 8) & 0xFF;
		data[pos++] = value & 0xFF;
	} else if (value < 0x100000000LL) {
		data[pos++] = 0xF0;
		data[pos++] = (value >> 24) & 0xFF;
		data[pos++] = (value >> 16) & 0xFF;
		data[pos++] = (value >> 8) & 0xFF;
		data[pos++] = value & 0xFF;
	} else {
		data[pos++] = 0xF4;
		data[pos++] = (value >> 56) & 0xFF;
		data[pos++] = (value >> 48) & 0xFF;
		data[pos++] = (value >> 40) & 0xFF;
		data[pos++] = (value >> 32) & 0xFF;
		data[pos++] = (value >> 24) & 0xFF;
		data[pos++] = (value >> 16) & 0xFF;
		data[pos++] = (value >> 8) & 0xFF;
		data[pos++] = value & 0xFF;
	}

	*write = pos;
}

int64_t
decode_varint(uint8_t *data, uint32_t *read, uint32_t left)
{
	int64_t varint = 0;

	/* 1 byte with 7 · 8 + 1 leading zeroes */
	if ((data[0] & 0x80) == 0x00) {
		varint = data[0] & 0x7F;
		*read = 1;
	/* 2 bytes with 6 · 8 + 2 leading zeroes */
	} else if ((data[0] & 0xC0) == 0x80) {
		varint = ((data[0] & 0x3F) << 8) | data[1];
		*read = 2;
	/* 3 bytes with 5 · 8 + 3 leading zeroes */
	} else if ((data[0] & 0xE0) == 0xC0) {
		varint = (((data[0] & 0x1F) << 16) |
			    (data[1] << 8) | (data[2]));
		*read = 3;
	/* 4 bytes with 4 · 8 + 4 leading zeroes */
	} else if ((data[0] & 0xF0) == 0xE0) {
		varint = (((data[0] & 0x0F) << 24) | (data[1] << 16) |
			  (data[2] << 8) | (data[3]));
		*read = 4;
	} else /* if ((data[pos] & 0xF0) == 0xF0) */ {
		switch (data[0] & 0xFC) {
		/* 32-bit positive number */
		case 0xF0:
			varint = ((data[1] << 24) | (data[2] << 16) |
				  (data[3] << 8) | data[4]);
			*read = 1 + 4;
			break;
		/* 64-bit number */
		case 0xF4:
			varint =
				((int64_t)data[1] << 56) | ((int64_t)data[2] << 48) |
				((int64_t)data[3] << 40) | ((int64_t)data[4] << 32) |
				(data[5] << 24) | (data[6] << 16) |
				(data[7] <<  8) | (data[8] <<  0);
			*read = 1 + 8;
			break;
		/* Negative varint */
		case 0xF8:
			/* FIXME: handle endless recursion */
			varint = -decode_varint(&data[1], read, left - 1);
			*read += 1;
			break;
		/* Negative two bit number */
		case 0xFC:
			varint = -(int)(data[0] & 0x03);
			*read = 1;
			break;
		}
	}

	return varint;
}