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. 16static const int k2Exp6 = 64; 17static const uint32_t k2Exp7 = 128; 18static const int k2Exp13 = 8192; 19static const uint32_t k2Exp14 = 16384; 20static const int k2Exp20 = (1 * 1024 * 1024); 21static const uint32_t k2Exp21 = (2 * 1024 * 1024); 22static const int k2Exp27 = (128 * 1024 * 1024); 23static const uint32_t k2Exp28 = (256 * 1024 * 1024); 24static const uint64_t k2Exp35 = (32LL * 1024LL * 1024LL * 1024LL); 25static 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 42char *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 95char *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