1 // Copyright 2006 The Android Open Source Project
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6 #include <assert.h>
7 #include "decoder.h"
8 #include "trace_common.h"
9
10 // This array provides a fast conversion from the initial byte in
11 // a varint-encoded object to the length (in bytes) of that object.
12 int prefix_to_len[] = {
13 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
14 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
15 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
16 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
17 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
18 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
19 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
20 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
21 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
22 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
23 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
24 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
25 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
26 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
27 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
28 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 9, 9, 17, 17
29 };
30
31 // This array provides a fast conversion from the initial byte in
32 // a varint-encoded object to the initial data bits for that object.
33 int prefix_to_data[] = {
34 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
35 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
36 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
37 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
38 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
39 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
40 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
41 112, 113, 114, 115, 116, 117, 118, 119,
42 120, 121, 122, 123, 124, 125, 126, 127,
43 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
44 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
45 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
46 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
47 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
48 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
49 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
50 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 0, 0, 0, 0
51 };
52
53 signed char prefix_to_signed_data[] = {
54 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
55 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
56 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
57 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
58 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
59 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
60 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
61 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
62 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
63 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
64 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
65 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
66 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
67 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
68 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
69 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
70 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
71 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
72 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
73 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
74 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
75 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
76 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
77 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
78 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
79 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
80 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
81 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
82 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
83 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
84 0x00, 0x01, 0x02, 0x03, 0xfc, 0xfd, 0xfe, 0xff,
85 0x00, 0x01, 0xfe, 0xff, 0x00, 0xff, 0x00, 0xff,
86 };
87
Decoder()88 Decoder::Decoder()
89 {
90 filename_ = NULL;
91 fstream_ = NULL;
92 next_ = NULL;
93 end_ = NULL;
94 }
95
~Decoder()96 Decoder::~Decoder()
97 {
98 Close();
99 delete[] filename_;
100 }
101
Close()102 void Decoder::Close()
103 {
104 if (fstream_) {
105 fclose(fstream_);
106 fstream_ = NULL;
107 }
108 }
109
Open(char * filename)110 void Decoder::Open(char *filename)
111 {
112 if (filename_ != NULL) {
113 delete[] filename_;
114 }
115 filename_ = new char[strlen(filename) + 1];
116 strcpy(filename_, filename);
117 fstream_ = fopen(filename_, "r");
118 if (fstream_ == NULL) {
119 perror(filename_);
120 exit(1);
121 }
122
123 int rval = fread(buf_, 1, kBufSize, fstream_);
124 if (rval != kBufSize) {
125 if (ferror(fstream_)) {
126 perror(filename_);
127 exit(1);
128 }
129 if (!feof(fstream_)) {
130 fprintf(stderr, "Unexpected short fread() before eof\n");
131 exit(1);
132 }
133 }
134 next_ = buf_;
135 end_ = buf_ + rval;
136 }
137
FillBuffer()138 void Decoder::FillBuffer()
139 {
140 assert(next_ <= end_);
141
142 if (end_ - next_ < kDecodingSpace && end_ == &buf_[kBufSize]) {
143 // Copy the unused bytes left at the end to the beginning of the
144 // buffer.
145 int len = end_ - next_;
146 if (len > 0)
147 memcpy(buf_, next_, len);
148
149 // Read enough bytes to fill up the buffer, if possible.
150 int nbytes = kBufSize - len;
151 int rval = fread(buf_ + len, 1, nbytes, fstream_);
152 if (rval < nbytes) {
153 if (ferror(fstream_)) {
154 perror(filename_);
155 exit(1);
156 }
157 if (!feof(fstream_)) {
158 fprintf(stderr, "Unexpected short fread() before eof\n");
159 exit(1);
160 }
161 }
162 end_ = &buf_[len + rval];
163 next_ = buf_;
164 }
165 }
166
Read(char * dest,int len)167 void Decoder::Read(char *dest, int len)
168 {
169 while (len > 0) {
170 int nbytes = end_ - next_;
171 if (nbytes == 0) {
172 FillBuffer();
173 nbytes = end_ - next_;
174 if (nbytes == 0)
175 break;
176 }
177 if (nbytes > len)
178 nbytes = len;
179 memcpy(dest, next_, nbytes);
180 dest += nbytes;
181 len -= nbytes;
182 next_ += nbytes;
183 }
184 }
185
186 // Decode a varint-encoded object starting at the current position in
187 // the array "buf_" and return the decoded value as a 64-bit integer.
188 // A varint-encoded object has an initial prefix that specifies how many
189 // data bits follow. If the first bit is zero, for example, then there
190 // are 7 data bits that follow. The table below shows the prefix values
191 // and corresponding data bits.
192 //
193 // Prefix Bytes Data bits
194 // 0 1 7
195 // 10 2 14
196 // 110 3 21
197 // 1110 4 28
198 // 11110 5 35
199 // 111110 6 42
200 // 11111100 9 64
201 // 11111101 reserved
202 // 11111110 reserved
203 // 11111111 reserved
Decode(bool is_signed)204 int64_t Decoder::Decode(bool is_signed)
205 {
206 int64_t val64;
207
208 if (end_ - next_ < kDecodingSpace)
209 FillBuffer();
210
211 #if BYTE_ORDER == BIG_ENDIAN
212 uint8_t byte0 = *next_;
213
214 // Get the number of bytes to decode based on the first byte.
215 int len = prefix_to_len[byte0];
216
217 if (next_ + len > end_) {
218 fprintf(stderr, "%s: decoding past end of file.\n", filename_);
219 exit(1);
220 }
221
222 // Get the first data byte.
223 if (is_signed)
224 val64 = prefix_to_signed_data[byte0];
225 else
226 val64 = prefix_to_data[byte0];
227
228 next_ += 1;
229 for (int ii = 1; ii < len; ++ii) {
230 val64 = (val64 << 8) | *next_++;
231 }
232 #else
233 // If we are on a little-endian machine, then use large, unaligned loads.
234 uint64_t data = *(reinterpret_cast<uint64_t*>(next_));
235 uint8_t byte0 = data;
236 data = bswap64(data);
237
238 // Get the number of bytes to decode based on the first byte.
239 int len = prefix_to_len[byte0];
240
241 if (next_ + len > end_) {
242 fprintf(stderr, "%s: decoding past end of file.\n", filename_);
243 exit(1);
244 }
245
246 // Get the first data byte.
247 if (is_signed)
248 val64 = prefix_to_signed_data[byte0];
249 else
250 val64 = prefix_to_data[byte0];
251
252 switch (len) {
253 case 1:
254 break;
255 case 2:
256 val64 = (val64 << 8) | ((data >> 48) & 0xffull);
257 break;
258 case 3:
259 val64 = (val64 << 16) | ((data >> 40) & 0xffffull);
260 break;
261 case 4:
262 val64 = (val64 << 24) | ((data >> 32) & 0xffffffull);
263 break;
264 case 5:
265 val64 = (val64 << 32) | ((data >> 24) & 0xffffffffull);
266 break;
267 case 6:
268 val64 = (val64 << 40) | ((data >> 16) & 0xffffffffffull);
269 break;
270 case 9:
271 data = *(reinterpret_cast<uint64_t*>(&next_[1]));
272 val64 = bswap64(data);
273 break;
274 }
275 next_ += len;
276 #endif
277 return val64;
278 }
279