The Android Open Source Project | 8b23a6c | 2009-03-03 19:30:32 -0800 | [diff] [blame] | 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. |
| 16 | static const int k2Exp6 = 64; |
| 17 | static const uint32_t k2Exp7 = 128; |
| 18 | static const int k2Exp13 = 8192; |
| 19 | static const uint32_t k2Exp14 = 16384; |
| 20 | static const int k2Exp20 = (1 * 1024 * 1024); |
| 21 | static const uint32_t k2Exp21 = (2 * 1024 * 1024); |
| 22 | static const int k2Exp27 = (128 * 1024 * 1024); |
| 23 | static const uint32_t k2Exp28 = (256 * 1024 * 1024); |
| 24 | static const uint64_t k2Exp35 = (32LL * 1024LL * 1024LL * 1024LL); |
| 25 | static 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 |
| 42 | char *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 |
| 95 | char *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 | } |