sdk/emulator/qtools/decoder.cpp

   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 }