1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Endian-neutral encoding: 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// * Fixed-length numbers are encoded with least-significant byte first 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// * In addition we support variable length "varint" encoding 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// * Strings are encoded prefixed by their length in varint format 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#ifndef STORAGE_LEVELDB_UTIL_CODING_H_ 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#define STORAGE_LEVELDB_UTIL_CODING_H_ 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <stdint.h> 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <string.h> 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <string> 16fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/slice.h" 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "port/port.h" 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Standard Put... routines append to a string 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern void PutFixed32(std::string* dst, uint32_t value); 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern void PutFixed64(std::string* dst, uint64_t value); 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern void PutVarint32(std::string* dst, uint32_t value); 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern void PutVarint64(std::string* dst, uint64_t value); 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern void PutLengthPrefixedSlice(std::string* dst, const Slice& value); 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Standard Get... routines parse a value from the beginning of a Slice 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// and advance the slice past the parsed value. 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern bool GetVarint32(Slice* input, uint32_t* value); 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern bool GetVarint64(Slice* input, uint64_t* value); 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern bool GetLengthPrefixedSlice(Slice* input, Slice* result); 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Pointer-based variants of GetVarint... These either store a value 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// in *v and return a pointer just past the parsed value, or return 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// NULL on error. These routines only look at bytes in the range 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// [p..limit-1] 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern const char* GetVarint32Ptr(const char* p,const char* limit, uint32_t* v); 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern const char* GetVarint64Ptr(const char* p,const char* limit, uint64_t* v); 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Returns the length of the varint32 or varint64 encoding of "v" 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern int VarintLength(uint64_t v); 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Lower-level versions of Put... that write directly into a character buffer 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// REQUIRES: dst has enough space for the value being written 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern void EncodeFixed32(char* dst, uint32_t value); 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern void EncodeFixed64(char* dst, uint64_t value); 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Lower-level versions of Put... that write directly into a character buffer 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// and return a pointer just past the last byte written. 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// REQUIRES: dst has enough space for the value being written 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern char* EncodeVarint32(char* dst, uint32_t value); 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern char* EncodeVarint64(char* dst, uint64_t value); 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Lower-level versions of Get... that read directly from a character buffer 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// without any bounds checking. 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline uint32_t DecodeFixed32(const char* ptr) { 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (port::kLittleEndian) { 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Load the raw bytes 61179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint32_t result; 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memcpy(&result, ptr, sizeof(result)); // gcc optimizes this to a plain load 63179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 655fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return ((static_cast<uint32_t>(static_cast<unsigned char>(ptr[0]))) 665fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[1])) << 8) 675fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[2])) << 16) 685fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[3])) << 24)); 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline uint64_t DecodeFixed64(const char* ptr) { 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (port::kLittleEndian) { 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Load the raw bytes 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t result; 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memcpy(&result, ptr, sizeof(result)); // gcc optimizes this to a plain load 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t lo = DecodeFixed32(ptr); 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t hi = DecodeFixed32(ptr + 4); 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return (hi << 32) | lo; 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Internal routine for use by fallback path of GetVarint32Ptr 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern const char* GetVarint32PtrFallback(const char* p, 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const char* limit, 88179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint32_t* value); 89179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline const char* GetVarint32Ptr(const char* p, 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const char* limit, 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint32_t* value) { 92179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (p < limit) { 93179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint32_t result = *(reinterpret_cast<const unsigned char*>(p)); 94179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if ((result & 128) == 0) { 95179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *value = result; 96179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return p + 1; 97179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 98179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 99179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return GetVarint32PtrFallback(p, limit, value); 100179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 101179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 10245b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 103179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 104179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#endif // STORAGE_LEVELDB_UTIL_CODING_H_ 105