1/* Copyright (C) 2007-2008 The Android Open Source Project
2**
3** This software is licensed under the terms of the GNU General Public
4** License version 2, as published by the Free Software Foundation, and
5** may be copied, distributed, and modified under those terms.
6**
7** This program is distributed in the hope that it will be useful,
8** but WITHOUT ANY WARRANTY; without even the implied warranty of
9** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10** GNU General Public License for more details.
11*/
12#include <inttypes.h>
13#include "varint.h"
14
15// Define some constants for powers of two.
16static const int k2Exp6 = 64;
17static const uint32_t k2Exp7 = 128;
18static const int k2Exp13 = 8192;
19static const uint32_t k2Exp14 = 16384;
20static const int k2Exp20 = (1 * 1024 * 1024);
21static const uint32_t k2Exp21 = (2 * 1024 * 1024);
22static const int k2Exp27 = (128 * 1024 * 1024);
23static const uint32_t k2Exp28 = (256 * 1024 * 1024);
24static const uint64_t k2Exp35 = (32LL * 1024LL * 1024LL * 1024LL);
25static const uint64_t k2Exp42 = (4LL * 1024LL * 1024LL * 1024LL * 1024LL);
26
27// Encodes the 64-bit value "value" using the varint encoding.  The varint
28// encoding uses a prefix followed by some data bits.  The valid prefixes
29// and the number of data bits are given in the table below.
30//
31// Prefix     Bytes  Data bits
32// 0          1      7
33// 10         2      14
34// 110        3      21
35// 1110       4      28
36// 11110      5      35
37// 111110     6      42
38// 11111100   9      64
39// 11111101   reserved
40// 11111110   reserved
41// 11111111   reserved
42char *varint_encode(uint64_t value, char *buf) {
43  if (value < k2Exp7) {
44    *buf++ = value;
45  } else if (value < k2Exp14) {
46    *buf++ = (2 << 6) | (value >> 8);
47    *buf++ = value & 0xff;
48  } else if (value < k2Exp21) {
49    *buf++ = (6 << 5) | (value >> 16);
50    *buf++ = (value >> 8) & 0xff;
51    *buf++ = value & 0xff;
52  } else if (value < k2Exp28) {
53    *buf++ = (0xe << 4) | (value >> 24);
54    *buf++ = (value >> 16) & 0xff;
55    *buf++ = (value >> 8) & 0xff;
56    *buf++ = value & 0xff;
57  } else if (value < k2Exp35) {
58    *buf++ = (0x1e << 3) | (value >> 32);
59    *buf++ = (value >> 24) & 0xff;
60    *buf++ = (value >> 16) & 0xff;
61    *buf++ = (value >> 8) & 0xff;
62    *buf++ = value & 0xff;
63  } else if (value < k2Exp42) {
64    *buf++ = (0x3e << 2) | (value >> 40);
65    *buf++ = (value >> 32) & 0xff;
66    *buf++ = (value >> 24) & 0xff;
67    *buf++ = (value >> 16) & 0xff;
68    *buf++ = (value >> 8) & 0xff;
69    *buf++ = value & 0xff;
70  } else {
71    *buf++ = (0x7e << 1);
72    *buf++ = (value >> 56) & 0xff;
73    *buf++ = (value >> 48) & 0xff;
74    *buf++ = (value >> 40) & 0xff;
75    *buf++ = (value >> 32) & 0xff;
76    *buf++ = (value >> 24) & 0xff;
77    *buf++ = (value >> 16) & 0xff;
78    *buf++ = (value >> 8) & 0xff;
79    *buf++ = value & 0xff;
80  }
81  return buf;
82}
83
84// Encodes the 35-bit signed value "value" using the varint encoding.
85// The varint encoding uses a prefix followed by some data bits.  The
86// valid prefixes and the number of data bits is given in the table
87// below.
88//
89// Prefix     Bytes  Data bits
90// 0          1      7
91// 10         2      14
92// 110        3      21
93// 1110       4      28
94// 11110      5      35
95char *varint_encode_signed(int64_t value, char *buf) {
96  if (value < k2Exp6 && value >= -k2Exp6) {
97    *buf++ = value & 0x7f;
98  } else if (value < k2Exp13 && value >= -k2Exp13) {
99    *buf++ = (2 << 6) | ((value >> 8) & 0x3f);
100    *buf++ = value & 0xff;
101  } else if (value < k2Exp20 && value >= -k2Exp20) {
102    *buf++ = (6 << 5) | ((value >> 16) & 0x1f);
103    *buf++ = (value >> 8) & 0xff;
104    *buf++ = value & 0xff;
105  } else if (value < k2Exp27 && value >= -k2Exp27) {
106    *buf++ = (0xe << 4) | ((value >> 24) & 0xf);
107    *buf++ = (value >> 16) & 0xff;
108    *buf++ = (value >> 8) & 0xff;
109    *buf++ = value & 0xff;
110  } else {
111    *buf++ = (0x1e << 3);
112    *buf++ = (value >> 24) & 0xff;
113    *buf++ = (value >> 16) & 0xff;
114    *buf++ = (value >> 8) & 0xff;
115    *buf++ = value & 0xff;
116  }
117  return buf;
118}
119