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 } 119
