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 88 Decoder::Decoder() 89 { 90 filename_ = NULL; 91 fstream_ = NULL; 92 next_ = NULL; 93 end_ = NULL; 94 } 95 96 Decoder::~Decoder() 97 { 98 Close(); 99 delete[] filename_; 100 } 101 102 void Decoder::Close() 103 { 104 if (fstream_) { 105 fclose(fstream_); 106 fstream_ = NULL; 107 } 108 } 109 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 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 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 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
